Abstract: Some Statistical Software Testing approaches rely on sampling the feasible paths in the control flow graph of the program; the difficulty comes from the tiny ratio of feasible paths. This paper presents an adaptive sampling mechanism called EXIST for Exploration/eXploitation Inference for Software Testing, able to retrieve distinct feasible paths with high probability. EXIST proceeds by alternatively exploiting and updating a distribution on the set of program paths. An original representation of paths, accommodating long-range dependencies and data sparsity and based on extended Parikh maps, is proposed. Experimental validation on real-world and artificial problems demonstrates dramatic improvements compared to the state of the art.
Introduction: The Needle in the Haystack
In Statistical Software Testing (SST), the primary goal is to generate test cases by sampling paths through a program's Control Flow Graph (CFG). A CFG maps out every possible sequence of instructions within a software module. However, a significant bottleneck exists: many of these theoretical paths are infeasible. For instance, a path might include two contradictory logical statements, such as if (x > 0) followed by if (x < 0) without any intervening change to the variable $x$.
In large-scale software, the fraction of paths that are actually executable (feasible) is often astronomically small—ranging from $10^{-5}$ down to $10^{-15}$. Uniformly sampling paths at random in such a sparse space is statistically futile. Previous machine learning attempts often failed because the "target concept" (the set of feasible paths) is too sparse for standard discriminant learning techniques to grasp.
The EXIST Framework
The authors propose EXIST (Exploration/eXploitation Inference for Software Testing), which reframes path generation as an iterative search and learning problem. The framework relies on several key innovations:
Extended Parikh Maps
Standard Parikh maps count node occurrences but lose sequence information. EXIST utilizes an "Extended Parikh Map" representation that tracks the "next informative symbol" after specific node occurrences. This allows the model to capture long-range dependencies—such as the requirement that taking a specific branch early in the program necessitates taking a corresponding branch later—without the state-space explosion typical of high-order Markov models.
The EXIST Loop and Seeded Initialization
The system operates in a loop: it starts with a small set of labeled paths, builds a probabilistic model, generates a candidate path, and uses a constraint solver (the "oracle") to check feasibility.
A critical component is the Seeded Procedure. Feasible paths often belong to distinct logical "islands" (disjunctions). Averaging probabilities across all known feasible paths often results in an infeasible "average" path that satisfies no specific logic. The Seeded Procedure uses "least general generalization" (lgg) to group paths into conjunctive sub-concepts, ensuring the model focuses on one logical branch at a time during generation.
Experimental Validation
The authors evaluated EXIST on both real-world and synthetic benchmarks:
- Fct4: A real-world module with 36 nodes and 46 edges (feasibility ratio $\approx 10^{-5}$).
- Artificial Benchmarks: Problems categorized by difficulty: Easy ($10^{-2}$), Medium ($10^{-5}$ to $10^{-3}$), and Hard ($10^{-15}$ to $10^{-14}$).
Key Results
The results demonstrate that the "Seeded" variants of the algorithms—particularly SeededGreedy (SG)—consistently outperform standard approaches. In "Hard" problems where random sampling would find zero feasible paths in 10,000 trials, SG found over 5,000 distinct feasible paths.
Interestingly, the research revealed a counter-intuitive sensitivity: providing the system with too many initial feasible paths (e.g., 1000 vs 50) can actually degrade performance. A larger initial set is more likely to span multiple logical sub-concepts, causing the model to over-generalize and produce infeasible "hybrid" paths.
Conclusion and Future Directions
EXIST successfully addresses the sparsity of feasible paths by combining adaptive probabilistic modeling with logical seeding. The authors conclude that while exploration is a staple of machine learning, in extremely sparse "Hard" problems, a greedy exploitation of known valid logical structures is often more productive. Future work includes applying these techniques to reachability testing in massive automata and developing formal estimates for "hitting times" to find the first feasible path in unknown environments.
Reference: Baskiotis, N., Sebag, M., Gaudel, M. C., & Gouraud, S. (2007). A Machine Learning Approach for Statistical Software Testing. IJCAI, 2274-2279.
Summary updated