A Machine Learning approach for Statistical Software Testing

Nicolas Baskiotis (1, 2) , Michèle Sebag (1, 2) , Marie-Claude Gaudel (2) , Sandrine-Dominique Gouraud (2)

1 TANC - Algorithmic number theory for cryptology
2 LRI - Laboratoire de Recherche en Informatique

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.

Domaines: Apprentissage [cs.LG]; Génie logiciel [cs.SE]

Nicolas Baskiotis, Michèle Sebag, Marie-Claude Gaudel, Sandrine-Dominique Gouraud. A Machine Learning approach for Statistical Software Testing. Twentieth International Joint Conference on Artificial Intelligence, Jan 2007, Hyderabad, India. ⟨inria-00112681⟩