Generating Input Data Structures For Automated Program Testing

摘要

Automatic test data generation usually concerns identifying input values that cause a selected path to execute. If a given path involves pointers, then input values may be represented in terms of two-dimensional dynamic data structures such as lists or trees. Thus, it is very important to identify the shape of the input data structure describing how many nodes are required and how nodes are connected each other. The approach presented in this paper makes use of the points-to information for each statement in the selected path for the shape generation. It also converts each statement into a static single assignment (SSA) form without pointer dereferences. The SSA form serves as a system of constraints to be solved to yield input values for non-pointer types. An empirical evaluation shows that shape generation can be achieved in linear time in terms of the number of pointer dereference operations.