Automatically Generating Search Heuristics for Concolic Testing

Sooyoung Cha ( Korea University )

Concolic testing is a hybrid software testing technique that combines symbolic and concrete executions [concolic=concrete+symbolic]. A key challenge in concolic testing is how to effectively explore the program’s execution paths to achieve high code coverage in a limited time budget. Concolic testing employs a search heuristic to address this challenge, which favors exploring particular types of paths that are most likely to maximize the final coverage. However, manually designing a good search heuristic is nontrivial and typically ends up with suboptimal and unstable outcomes.

In this talk, I will present a technique to automatically generate search heuristics for concolic testing. To this end, we define a class of search heuristics, namely a parameterized heuristic, and present an algorithm that efficiently finds an optimal heuristic for each subject program. I will start with a brief introduction to concolic testing.