An empirical study on constraint optimization techniques for test generation

作     者：Zhiyi ZHANG Zhenyu CHEN Ruizhi GAO Eric WONG Baowen XU 

作者机构：State Key Laboratory for Novel Software Technology Nanjing University Department of Computer Science University of Texas at Dallas 

出 版 物：《Science China(Information Sciences)》 (中国科学:信息科学(英文版))

年 卷 期：2017年第60卷第1期

页      面：69-83页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：supported in part by National Basic Research Program of China (973 Program) (Grant No. 2014CB340702) National Natural Science Foundation of China (Grant Nos. 91418202, 61472178, 61373013) 

主　　题：test generation symbolic execution constraint solving constraint optimization static metric 

摘      要：Constraint solving is a frequent, but expensive operation with symbolic execution to generate tests for a program. To improve the efficiency of test generation using constraint solving, four optimization techniques are usually applied to existing constraint solvers, which are constraint independence, constraint set simplification, constraint caching, and expression rewriting. In this paper, we conducted an empirical study, using these four constraint optimization techniques in a well known test generation tool KLEE with 77 GNU Coreutils applications, to systematically investigate how these optimization techniques affect the efficiency of test generation. The experimental results show that these constraint optimization techniques as well as their combinations cannot improve the efficiency of test generation significantly for ALL-SIZED programs. Moreover, we studied the constraint optimization techniques with respect to two static metrics, lines of code(LOC) and cyclomatic complexity(CC), of programs. The experimental results show that the constraint set simplification technique can improve the efficiency of test generation significantly for the programs with high LOC and CC values. Theconstraint caching optimization technique can improve the efficiency of test generation significantly for the programs with low LOC and CC values. Finally, we propose four hybrid optimization strategies and practical guidelines based on different static metrics.