NDLI: Inference and enforcement of data structure consistency specifications

Please wait, while we are loading the content...

TimeAware test suite prioritization

Experimental program analysis: a new program analysis paradigm

Subdomain testing of units and systems with state

Role-Based access control consistency validation

From daikon to agitator: lessons and challenges in building a commercial tool for developer testing

Application of automated environment generation to commercial software

Inference and enforcement of data structure consistency specifications

The species per path approach to SearchBased test data generation

Looking for bugs in all the right places

Breaking up is hard to do: an investigation of decomposition for assume-guarantee reasoning

Effective typestate verification in the presence of aliasing

Run-time monitoring of architecturally significant behaviors using behavioral profiles and aspects

Automated testing of stochastic systems: a statistically grounded approach

DSD-Crasher: a hybrid analysis tool for bug finding

Coverage metrics for requirements-based testing

A model and sensitivity analysis of the quality economics of defect-detection techniques

Modular verification of code with SAT

Testing, abstraction, theorem proving: better together!

The case for analysis preserving language transformation

Performance assertions for mobile devices

Dynamic inference of abstract types

Test input generation for java containers using state matching

Using model checking with symbolic execution to verify parallel numerical programs

Inference and enforcement of data structure consistency specifications

Content Provider	ACM Digital Library
Author	Rinard, Martin Perkins, Jeff H. McCamant, Stephen Ernst, Michael D. Demsky, Brian Guo, Philip J.
Abstract	Corrupt data structures are an important cause of unacceptable program execution. Data structure repair (which eliminates inconsistencies by updating corrupt data structures to conform to consistency constraints) promises to enable many programs to continue to execute acceptably in the face of otherwise fatal data structure corruption errors. A key issue is obtaining an accurate and comprehensive data structure consistency specification. We present a new technique for obtaining data structure consistency specifications for data structure repair. Instead of requiring the developer to manually generate such specifications, our approach automatically generates candidate data structure consistency properties using the Daikon invariant detection tool. The developer then reviews these properties, potentially rejecting or generalizing overly specific properties to obtain a specification suitable for automatic enforcement via data structure repair. We have implemented this approach and applied it to three sizable benchmark programs: CTAS (an air-traffic control system), BIND (a widely-used Internet name server) and Freeciv (an interactive game). Our results indicate that (1) automatic constraint generation produces constraints that enable programs to execute successfully through data structure consistency errors, (2) compared to manual specification, automatic generation can produce more comprehensive sets of constraints that cover a larger range of data structure consistency properties, and (3) reviewing the properties is relatively straightforward and requires substantially less programmer effort than manual generation, primarily because it reduces the need to examine the program text to understand its operation and extract the relevant consistency constraints. Moreover, when evaluated by a hostile third party "Red Team" contracted to evaluate the effectiveness of the technique, our data structure inference and enforcement tools successfully prevented several otherwise fatal attacks.
Starting Page	233
Ending Page	244
Page Count	12
File Format	PDF
ISBN	1595932631
DOI	10.1145/1146238.1146266
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2006-07-21
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Dynamic invariant detection Data structure repair
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in