Publication Type
Conference Proceeding Article
Version
acceptedVersion
Publication Date
9-2023
Abstract
Detecting non-termination is crucial for ensuring program correctness and security, such as preventing denial-of-service attacks. While termination analysis has been studied for many years, existing methods have limited scalability and are only effective on small programs. To address this issue, we propose a practical termination checking technique, called EndWatch, for detecting non-termination through testing. Specifically, we introduce two methods to generate non-termination oracles based on checking state revisits, i.e., if the program returns to a previously visited state at the same program location, it does not terminate. The non-termination oracles can be incorporated into testing tools (e.g., AFL used in this paper) to detect non-termination in large programs. For linear loops, we perform symbolic execution on individual loops to infer State Revisit Conditions (SRC) and instrument SRC into target loops. For non-linear loops, we instrument target loops for checking concrete state revisits during execution. We evaluated EndWatch on standard benchmarks with small-sized programs and real-world projects with large-sized programs. The evaluation results show that EndWatch is more effective than the state-of-the-art tools on standard benchmarks (detecting 87% of non-terminating programs while the best baseline detects only 67%), and useful in detecting non-termination in real-world projects (detecting 90% of known non-termination CVEs and 4 unknown bugs).
Keywords
Dynamic testing, Non-termination detection, Static analysis, Testing oracle generation
Discipline
Information Security | Software Engineering
Research Areas
Software and Cyber-Physical Systems
Publication
2023 38th IEEE/ACM International Conference on Automated Software Engineering: Luxembourg, September 11-15: Proceedings
First Page
686
Last Page
697
ISBN
9798350329964
Identifier
10.1109/ASE56229.2023.00061
Publisher
IEEE
City or Country
Piscataway, NJ
Citation
ZHANG, Yao; XIE, Xiaofei; LI, Yi; CHEN, Sen; ZHANG, Cen; and LI, Xiaohong.
EndWatch: A practical method for detecting non-termination in real-world software. (2023). 2023 38th IEEE/ACM International Conference on Automated Software Engineering: Luxembourg, September 11-15: Proceedings. 686-697.
Available at: https://ink.library.smu.edu.sg/sis_research/8239
Copyright Owner and License
Authors
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1109/ASE56229.2023.00061