Dynamic symbolic data structure repair

ABSTRACT

Generic repair of complex data structures is a new and exciting area of research. Existing approaches can integrate with good software engineering practices such as program assertions. But in practice there is a wide variety of assertions and not all of them satisfy the style rules imposed by existing repair techniques. I.e., a "badly" written assertion may render generic repair inefficient or ineffective. In this paper we build on the state of the art in generic repair and discuss how generic repair can work effectively with a wider range of correctness conditions.

We motivate how dynamic symbolic techniques enable generic repair to support a wider range of correctness conditions and present DSDSR, a novel repair algorithm based on dynamic symbolic execution. We implement the algorithm for Java and report initial empirical results to demonstrate the promise of our approach for generic repair.

References

1. C. Boyapati, S. Khurshid, and D. Marinov. Korat: Automated testing based on Java predicates. In Proc. ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA), pages 123--133. ACM, July 2002.
2. É. Bruneton, R. Lenglet, and T. Coupaye. ASM: a code manipulation tool to implement adaptable systems. In Proc. ACM SIGOPS France Journées Composants 2002: Systèmes à composants adaptables et extensibles (Adaptable and extensible component systems), Nov. 2002.
3. G. A. Cohen, J. S. Chase, and D. L. Kaminsky. Automatic program transformation with Joie. In Proc. USENIX Annual Technical Symposium, pages 167--178. USENIX, June 1998.
4. B. Demsky. Data Structure Repair Using Goal-Directed Reasoning. PhD thesis, Massachusetts Institute of Technology, 2006.
5. B. Demsky and M. C. Rinard. Automatic detection and repair of errors in data structures. In Proc. 18th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), pages 78--95. ACM, Oct. 2003.
6. B. Elkarablieh, I. Garcia, Y. L. Suen, and S. Khurshid. Assertion-based repair of complex data structures. In Proc. 22nd IEEE/ACM International Conference on Automated Software Engineering (ASE), pages 64--73. ACM, Nov. 2007.
7. B. Elkarablieh and S. Khurshid. Juzi: a tool for repairing complex data structures. In Proc. 30th ACM/IEEE International Conference on Software Engineering (ICSE), pages 855--858. ACM, May 2008.
8. P. Godefroid, N. Klarlund, and K. Sen. Dart: Directed automated random testing. In Proc. ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 213--223. ACM, June 2005.
9. G. Kudrjavets, N. Nagappan, and T. Ball. Assessing the relationship between software assertions and faults: An empirical investigation. In Proc. 17th IEEE International Symposium on Software Reliability Engineering (ISSRE), pages 204--212. IEEE, Nov. 2006.
10. M. Z. Malik, K. Ghori, B. Elkarablieh, and S. Khurshid. A case for automated debugging using data structure repair. In 24th IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE, Nov. 2009.
11. S. Mourad and D. Andrews. On the reliability of the IBM MVS/XA operating system. IEEE Transactions on Software Engineering (TSE), 13(10):1135--1139, Oct. 1987.
12. K. Sen and G. Agha. Cute and jCute: Concolic unit testing and explicit path model-checking tools. In Proc. International Conference on Computer Aided Verification (CAV), pages 419--423. Springer, Aug. 2006.
13. N. Tillmann and J. de Halleux. Pex - white box test generation for .Net. In Proc. 2nd International Conference on Tests And Proofs (TAP), pages 134--153. Springer, Apr. 2008.

Index Terms

• Computing methodologies

  • Symbolic and algebraic manipulation

• General and reference

  • Cross-computing tools and techniques

    • Reliability

• Hardware

  • Hardware validation

    • Functional verification

      • Assertion checking

• Software and its engineering

  • Software creation and management

    • Software development techniques

      • Error handling and recovery

    • Software verification and validation

  • Software notations and tools

    • General programming languages

      • Language features

        • Classes and objects

  • Software organization and properties

    • Extra-functional properties

      • Software reliability

• Theory of computation

  • Models of computation

    • Abstract machines

  • Semantics and reasoning

    • Program reasoning

      • Abstraction

      • Assertions

      • Invariants