Fitness-Guided Path Exploration in Automated Test Generation

Fall 2008 CSE Colloquium Series

Dr. Tao Xie

Assistant Professor
Department of Computer Science
North Carolina State University

Date: November 7
Time: 11:00 AM - 12:00 PM
1260 Anthony Hall

Host: Laura Dillon

Abstract

Dynamic symbolic execution is a structural testing technique that systematically explores feasible paths of the program under test by running the program with different test inputs. Its main goal is to find a set of test inputs that lead to the coverage of particular test targets, e.g., specific statements or violated assertions. In theory, it is undecidable whether a test target can be covered, and in practice the number of feasible paths explodes. Nevertheless, for many programs, heuristic search strategies can often cover a test target quickly by analyzing only a few potentially feasible paths.

We have developed a novel approach called Fitnex, a search strategy that uses state-dependent fitness values (computed through a fitness function) to guide path exploration. The fitness function measures how close an already discovered feasible path is to a particular test target. Our new search strategy gives paths with better fitness values higher priority in the search. As a result, the search needs to consider fewer paths to cover test targets faster. Our new fitness-guided search strategy can be integrated with other strategies that are effective for exploration problems where the fitness heuristic fails. We have implemented the new approach in Pex, an automated structural testing tool developed at Microsoft Research for .NET programs. The evaluation results show that the new approach is effective since it consistently achieves high code coverage faster than existing search strategies. This is joint work with Nikolai Tillmann, Peli de Halleux, and Wolfram Schulte from Microsoft Research.

Biography

Tao Xie is an Assistant Professor in the Department of Computer Science at North Carolina State University. He received his Ph.D. in Computer Science from the University of Washington in 2005. He leads the Automated Software Engineering Research Group at North Carolina State University. His research is around two major themes: automated software testing and mining software engineering data. He is Program Co-Chair of 2009 IEEE International Conference on Software Maintenance (ICSM). He has served on a number of conference program committees such as ISSTA, ASE, AOSD, and WWW. Besides doing research, he has contributed to understanding the software engineering research community by building various community webs.