Efficient solving of structural constraints

Bassem Elkarablieh, Darko Marinov, Sarfraz Khurshid

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Structural constraint solving is being increasingly used for software reliability tasks such as systematic testing or error recovery. For example, the Korat algorithm provides constraint-based test generation: given a Java predicate that describes desired input constraints and a bound on the input size, Korat systematically searches the bounded input space of the predicate to generate all inputs that satisfy the constraints. As another example, the STARC tool uses a constraint-based search to repair broken data structures. A key issue for these approaches is the efficiency of search. This paper presents a novel approach that significantly improves the efficiency of structural constraint solvers. Specifically, most existing approaches use backtracking through code re-execution to explore their search space. In contrast, our approach performs checkpoint-based backtracking by storing partial program states and performing abstract undo operations. The heart of our approach is a light-weight search that is performed purely through code instrumentation. The experimental results on Korat and STARC for generating and repairing a set of complex data structures show an order to two orders of magnitude speed-up over the traditionally used searches.

Original languageEnglish (US)
Title of host publicationISSTA'08
Subtitle of host publicationProceedings of the 2008 International Symposium on Software Testing and Analysis 2008
Pages39-49
Number of pages11
DOIs
StatePublished - Dec 16 2008
Event2008 International Symposium on Software Testing and Analysis, ISSTA 2008 - Seattle, WA, United States
Duration: Jul 20 2008Jul 24 2008

Publication series

NameISSTA'08: Proceedings of the 2008 International Symposium on Software Testing and Analysis 2008

Other

Other2008 International Symposium on Software Testing and Analysis, ISSTA 2008
CountryUnited States
CitySeattle, WA
Period7/20/087/24/08

    Fingerprint

Keywords

  • Backtracking
  • Model checking
  • Systematic testing

ASJC Scopus subject areas

  • Computer Science Applications
  • Software

Cite this

Elkarablieh, B., Marinov, D., & Khurshid, S. (2008). Efficient solving of structural constraints. In ISSTA'08: Proceedings of the 2008 International Symposium on Software Testing and Analysis 2008 (pp. 39-49). (ISSTA'08: Proceedings of the 2008 International Symposium on Software Testing and Analysis 2008). https://doi.org/10.1145/1390630.1390637