Grande Salle de VERIMAG
22 April 2010 - 14h00
All-Paths Test Generation for Programs with Internal Aliases in PathCrawler
by Nikolay Kosmatov from CEA - LISI
Abstract: We present the problem of aliases arrising in the context of automatic test generation for all-paths test criterion using
constraint logic programming in a depth-first search.
We classify aliases into two groups: external aliases, existing already at the entry point of the
function under test (due to pointer inputs), and internal ones, created during its symbolic execution.
We propose an original extension of the depth-first test generation method for C programs with internal
aliases. It limits the enumeration of inputs and the generation of superfluous test cases.
Initial experiments show that our method can
considerably improve the performances of the
existing tools on programs with aliases.
We show also that all-paths test generation is NP-hard even
for the simplest programs in presence of aliases.
For a more restrictive class containing programs
with strong restrictions, all-paths test generation in
polynomial time becomes possible.
