InSPeCT: Iterated local search for solving path conditions

• Main Authors: CHEN, Fuxiang, GUNAWAN, Aldy, LO, David, KIM, Sunghun
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2019
• Subjects: Iterated Local search; Path condition; Automated test case generation; Infeasible solutions; Computer Sciences; Databases and Information Systems; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/4521; https://ink.library.smu.edu.sg/context/sis_research/article/5524/viewcontent/Inspect_CASE_2019_av.pdf
• Institution: Singapore Management University

Automated test case generation is attractive as it can reduce developer workload. To generate test cases, many Symbolic Execution approaches first produce Path Conditions (PCs), a set of constraints, and pass them to a Satisfiability Modulo Theories (SMT) solver. Despite numerous prior studies, automated test case generation by Symbolic Execution is still slow, partly due to SMT solvers’ high computationally complexity. We introduce InSPeCT, a Path Condition solver, that leverages elements of ILS (Iterated Local Search) and Tabu List. ILS is not computational intensive and focuses on generating solutions in search spaces while Tabu List prevents the use of previously generated infeasible solutions. InSPeCT is evaluated against two state-of-the-art solvers, MLB and Z3, on ten Java subject programs of varying size and complexity. The results show that InSPeCT is able to solve 16% more PCs than MLB and 41% more PCs than Z3. On average, it is 103 and 5 times faster than Z3 and MLB, respectively. It also generates tests with higher test coverage than both MLB and Z3.