Premium
Generating input data structures for automated program testing
Author(s) -
Chung Insang,
Bieman James M.
Publication year - 2009
Publication title -
software testing, verification and reliability
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.216
H-Index - 49
eISSN - 1099-1689
pISSN - 0960-0833
DOI - 10.1002/stvr.388
Subject(s) - pointer (user interface) , computer science , statement (logic) , path (computing) , data structure , algorithm , pointer analysis , test data , data mining , theoretical computer science , programming language , static analysis , artificial intelligence , political science , law
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. Copyright © 2008 John Wiley & Sons, Ltd.