CEA LIST
In structural testing of programs, the all-paths coverage criterion requires to generate a set of test cases such that every possible execution path of the program under test is executed by one test case. This task becomes very complex in presence of aliases, i.e. differents ways to address the same memory location. In practice, the presence of aliases may result in enumeration of possible inputs and/or generation of several test cases for the same path.
This article presents the problem of aliases in the context of classical depth-first test generation method. We give a simple proof that the all-paths test generation problem is NP-hard even for the simplest C programs with aliases.
We propose an original extension of the depth-first test generation method for programs with aliases. It limits the enumeration of inputs and the generation of superfluous test cases. An easily understandable toy implementation of the complete algorithm in Prolog language is provided.