.png){kind=icon}
.png){kind=icon}
Return
Effective State Encoding for Breadth-First Generation of Complex Structures
.png){kind=icon}
PRE
AI
DOI：10.1109/TR.2019.2911989.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Generation of complex heap structures is required for many software testing and verification techniques, which are used to enhance software reliability. It enables them to work for programs dependent on such structures. Generating all the valid structures within a size bound is time-consuming, and it is hard to predict an input size completely generatable within a time bound. This is due to the depth-first traversal of the candidate space. However, an efficient breadth-first traversal requires a compact state encoding to store candidates for exploration in the next level. In this paper, we present present a novel state encoding technique that stores an incomplete representation of state that can be recovered during search. We build upon the Korat algorithm-demonstrated to effectively generate tests and find bugs for many software programs-and present iKorat, an incremental algorithm for breadth-first exploration of the search space. Our encoding enables a more efficient implementation of iterative deepening that avoids redundant work. Standard iterative deepening algorithms allow a breadth-first search when the underlying algorithm is depth-first by repeating the work of earlier iterations. iKorat, however, uses information from smaller sizes to avoid redundant work for larger sizes. It also enables a new technique for parallelizing Korat by communicating candidates using our encoding. piKorat generates structures of larger sizes in parallel as soon as incremental information is available from smaller sizes. Our evaluation shows that iKorat-based iterative deepening is more efficient than Korat and that piKorat naturally extends the technique for parallel generation of complex structures.
Keywords:
Automatic testing
automatic test pattern generation
automatic test case generation
incremental test case generation
iterative deepening
parallel test case generation
software reliability
software testing
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
5.7
Papers:
2.7K
Citations:
8.5K