Paper Info
Title
IC-Cut: A Compositional Search Strategy for Dynamic Test Generation
Abstract
We present IC-Cut, short for \"Interface-Complexity-based Cut\", a new compositional search strategy for systematically testing large programs. IC-Cut dynamically detects function interfaces that are simple enough to be cost-effective for summarization. IC-Cut then hierarchically decomposes the program into units defined by such functions and their sub-functions in the call graph. These units are tested independently, their test results are recorded as low-complexity function summaries, and the summaries are reused when testing higher-level functions in the call graph, thus limiting overall path explosion. When the decomposed units are tested exhaustively, they constitute verified components of the program. IC-Cut is run dynamically and on-the-fly during the search, typically refining cuts as the search advances. We have implemented this algorithm as a new search strategy in the whitebox fuzzer SAGE, and present detailed experimental results obtained when fuzzing the ANI Windows image parser. Our results show that IC-Cut alleviates path explosion while preserving or even increasing code coverage and bug finding, compared to the current generational-search strategy used in SAGE.
Year
DOI
Venue
2015
10.1007/978-3-319-23404-5_19
International SPIN Workshop on Model Checking of Software
Field
DocType
Volume
Code coverage,Data mining,Automatic summarization,Fuzz testing,Computer science,Call graph,Theoretical computer science,Dynamic testing,Parsing,Limiting
Conference
9232
ISSN
Citations 
PageRank 
0302-9743
7
0.53
References 
Authors
15
2
Name
Order
Citations
PageRank
Maria Christakis120016.69
Patrice Godefroid23622275.78