Lightweight data-flow analysis for execution-driven constraint solving.

J. H. Siddiqui, D. Marinov, and S. Khurshid.
IEEE International Conference on Software Testing Verification and Validation (ICST 2012)


Constraint-based testing is a methodology for finding bugs in code, which has been successfully used for testing real systems. A key element of the methodology is generation of test inputs from input constraints, i.e., properties of desired inputs, which is performed by solving the constraints. We present a novel approach to optimize input generation from imperative constraints, i.e., constraints written as predicates in an imperative language. A well known technique for solving such constraints is execution-driven monitoring, where the given predicate is executed on candidate inputs to filter and prune invalid inputs, and generate valid ones. Our insight is that a lightweight static data-flow analysis of the given imperative constraint can enable more efficient solving. This paper describes an approach that embodies our insight and evaluates it using a suite of well-studied subject constraints. The experimental results show our approach provides substantial speedup over previous work.
(ICST 2012), Montreal, Canada, April 2012. (Acceptance rate: 26%, 39/145)


@inproceedings { icst2012,
author = { }, }