Publication Type
Journal Article
Version
acceptedVersion
Publication Date
6-2019
Abstract
Analyzing loops is very important for various software engineering tasks such as bug detection, test case generation and program optimization. However, loops are very challenging structures for program analysis, especially when (nested) loops contain multiple paths that have complex interleaving relationships. In this paper, we propose the path dependency automaton (PDA) to capture the dependencies among the multiple paths in a loop. Based on the PDA, we first propose a loop classification to understand the complexity of loop summarization. Then, we propose a loop analysis framework, named Proteus, which takes a loop program and a set of variables of interest as inputs and summarizes path-sensitive loop effects (i.e., disjunctive loop summary) on the variables of interest. An algorithm is proposed to traverse the PDA to summarize the effect for all possible executions in the loop. We have evaluated Proteus using loops from five open-source projects and two well-known benchmarks and applying the disjunctive loop summary to three applications: loop bound analysis, program verification and test case generation. The evaluation results have demonstrated that Proteus can compute a more precise bound than the existing loop bound analysis techniques; Proteus can significantly outperform the state-of-the-art tools for loop program verification; and Proteus can help generate test cases for deep loops within one second, while symbolic execution tools KLEE and Pex either need much more time or fail.
Keywords
Disjunctive loop summary, path dependency automaton, path interleaving
Discipline
Software Engineering
Research Areas
Software and Cyber-Physical Systems
Publication
IEEE Transactions on Software Engineering
Volume
45
Issue
6
First Page
537
Last Page
557
ISSN
0098-5589
Identifier
10.1109/TSE.2017.2788018
Publisher
Institute of Electrical and Electronics Engineers
Citation
XIE, Xiaofei; CHEN, Bihuan; ZOU, Liang; LIU, Yang; LE, Wei; and LI, Xiaohong.
Automatic loop summarization via path dependency analysis. (2019). IEEE Transactions on Software Engineering. 45, (6), 537-557.
Available at: https://ink.library.smu.edu.sg/sis_research/7100
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.