Structural Sampling for Statistical Software Testing

Abstract

Structural Statistical Software Testing exploits the control flow
graph of the program being tested to construct test cases. 
While test cases can easily be extracted from {em feasible paths} in the control 
flow graph, that is, paths which are actually exerted for some 
values of the program input, the feasible path region is a tiny fraction 
of the graph paths (less than $10^{-5}]$ for medium size programs).
The S4T algorithm presented in this paper aims to address this limitation; 
as an Active Relational Learning Algorithm, it uses the few feasible paths
initially available to sample new feasible paths. The difficulty comes 
from the  non-Markovian nature of the feasible path concept, due to the 
long-range dependencies between the nodes in the control flow graph. 
Experimental validation on real-world and artificial problems 
demonstrates significant improvements compared to the state of the art.