A Machine Learning Approach for Statistical Software Testing

By Nicolas Baskiotis et al.

Read the original document by opening this link in a new tab.

Table of Contents

1. Introduction
2. Related Work
3. Prior knowledge and Representation
4. Overview of EXIST
4.1 Position of the problem
4.2 The search space
4.3 Decision module
4.4 The Init module

Summary

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. The approach aims to overcome the difficulties in Statistical Software Testing approaches that rely on sampling the feasible paths in the control flow graph of a program. It introduces a new learning framework, EXIST, which gradually enriches a set of labelled paths with new paths generated by the system and labelled by a constraint solver. The paper discusses the exploration vs exploitation trade-off in the context of identifying distinct feasible paths and presents a probabilistic model based on the extended Parikh map representation for path generation. The Decision module iteratively selects the next node in the path based on conditional probabilities, while the Init module estimates these probabilities using a Seeded Init option to handle the disjunctive nature of the target concept. Experimental validation on real-world and artificial problems shows significant improvements compared to existing approaches.