Title :
A Search Strategy Guided by Uncovered Branches for Concolic Testing
Author :
Qixing Dong ; Jun Yan ; Jian Zhang ; Fanping Zeng
Author_Institution :
Sch. of Comput. Sci. & Technol., Univ. of Sci. & Technol. of China, Hefei, China
Abstract :
Test generation plays an important role in software testing. Concolic testing runs concrete executions on programs simultaneously with symbolic executions. It faces the same problem as symbolic execution when generating test inputs, namely the combinatorial explosion of the path space. Most of the existing approaches can search only a fraction of the path space. Therefore, how to cover as many branches as possible with a few test inputs becomes an important research issue. Upon this issue, the paper proposes a heuristic search strategy based on inter-procedural control flow graph. The proposed strategy calculates the approximate mathematic expectation of uncovered branches. Then this expectation guides the search process to select the optimal branch to form a path condition. According to the path condition, the test input that may cover a large number of uncovered branches is generated. Experiments on three classes of test benchmarks show that, compared to the other strategies, the proposed strategy can significantly reduce the number of test inputs for covering reachable branches, and achieve high branch coverage quickly.
Keywords :
approximation theory; flow graphs; program testing; search problems; combinatorial explosion; concolic testing; interprocedural control flow graph; mathematic expectation approximation; optimal branch; path space; search process; search strategy; software testing; symbolic executions; test generation; uncovered branches; Bismuth; Computer science; Educational institutions; Search problems; Software; Space exploration; Testing; concolic testing; dynamic symbolic execution; test generation; uncovered branch expectation;
Conference_Titel :
Quality Software (QSIC), 2013 13th International Conference on
Conference_Location :
Najing
DOI :
10.1109/QSIC.2013.68