MAGIC: Path-Guided Concolic Testing

Authors:Cui, Zhanqi, Department of Computer ScienceUniversity of Virginia Le, Wei, Department of Computer ScienceUniversity of Virginia Soffa, Mary, Department of Computer ScienceUniversity of Virginia Wang, Linzhang, Department of Computer ScienceUniversity of Virginia Li, Xuandong, Department of Computer ScienceUniversity of Virginia

Concolic testing has been proposed as an effective tech- nique to automatically test software. The goal of concolic testing is to generate test inputs to find faults by executing as many paths of a program as possible. However, due to the large state space, it is unrealistic to consider all of the program paths for test input generation. Rather than ex- ploring the paths based on the structure of the program as current concolic testing does, in this paper we generate test inputs and execute the program along the paths that have identified potential faults. We present a path-guided testing technique that combines path-sensitive static analysis with concolic testing. The program under test is statically ana- lyzed before testing to find potential faults (suspicious state- ments) and corresponding suspicious path segments. Then the program is tested, guided by static information, to avoid generating test inputs for safe paths. A tool, MAGIC, has been implemented based on our technique to test for buffer overflow. We have experimentally evaluated MAGIC on a set of C benchmarks, and the results show that compared to concolic testing, MAGIC found about 2.5 times more faults, and using the path information, MAGIC triggers the faults 25.3 times faster on average for a set of benchmarks.

All rights reserved (no additional license for public reuse)
Source Citation:

Cui, Zhanqi, Wei Le, Mary Soffa, Linzhang Wang, and Xuandong Li. "MAGIC: Path-Guided Concolic Testing." University of Virginia Dept. of Computer Science Tech Report (2011).

University of Virginia, Department of Computer Science
Published Date: