Structural Sampling for Statistical Software Testing
| Title | Structural Sampling for Statistical Software Testing |
| Publication Type | Journal Articles |
| Year of Publication | 2008 |
| Authors | Baskiotis N, Sebag M, De Raedt L, Dietterich T, Getoor L, Kersting K, Muggleton SH |
| Journal | Probabilistic, Logical and Relational Learning-A Further Synthesis |
| Date Published | 2008/// |
| 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. |