InSPeCT: Iterated local search for solving path conditions

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, auto...

Full description

Saved in:
Bibliographic Details
Main Authors: CHEN, Fuxiang, GUNAWAN, Aldy, LO, David, KIM, Sunghun
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2019
Subjects:
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
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
Description
Summary: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.