Information Technology Reference
In-Depth Information
useful information regarding the differences between faulty and correct concrete pro-
gram states. DREAM abstractions directly aid in program repair by summarizing repair
actions and helping users comprehend concrete repair actions better.
7Conluion
Data structure repair, a runtime approach designed to keep program state (i.e., data
structures) consistent in the event of software or hardware errors, has seen improve-
ments in recent years. However, it still suffers from low performance and lack of scala-
bility. We introduced repair abstractions to enhance the efficiency and scalability of data
structure repair. Our insight is that if an error is due to a fault in software or hardware,
it is likely to recur. Therefore, we can abstract the concrete repair actions taken to fix a
particular state and reuse them when a similar error is detected in future.
We implemented the idea of repair abstractions in the DREAM (Data structure Re-
pair using Efficient Abstraction Methods) tool. DREAM piggybacks on other repair
frameworks and records concrete repair actions they take to fix a particular erroneous
state. DREAM abstracts the concrete actions and attempts to reuse them when a similar
error is detected, eliminating the need to go to the underlying repair framework again.
Hence, DREAM amortizes the repair cost from the cases it has to invoke the underlying
repair framework among many repairs.
We combined DREAM with two data structure repair frameworks: Cobbler that uses
a combination of SAT solvers and heuristics, and Juzi that implements a dedicated
search engine for repair. The experimental evaluation of the use of DREAM in ac-
cordance with these two frameworks on basic and complex data structures showed that
DREAM offers significant performance improvement. We envision that repair abstrac-
tions can be a valuable addition to data structure repair frameworks. DREAM's ability
to integrate with different repair frameworks provides a promising step towards making
repair scale to real applications.
Acknowledgments.
This work is partially supported by the National Science Founda-
tion under Grant No. CCF-0845628.
References
1. Al-Naffouri, B.Y.: MintEra: A testing environment for Java programs. Master's thesis, MIT
(2004)
2. Artzi, S., Dolby, J., Tip, F., Pistoia, M.: Directed test generation for effective fault localiza-
tion. In: ISSTA (2010)
3. Boyapati, C., Khurshid, S., Marinov, D.: Korat: Automated testing based on Java predicates.
In: ISSTA (2002)
4. Clarke, L.A., Rosenblum, D.S.: A historical perspective on runtime assertion checking in
software development. SIGSOFT Software Engineering Notes, 31(3) (2006)
5. Demsky, B.: Data Structure Repair Using Goal-Directed Reasoning. PhD thesis. MIT (2006)
6. Demsky, B., Rinard, M.: Automatic detection and repair of errors in data structures. In:
OOPSLA (2003)
