Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

11-2022

Abstract

Termination is a crucial program property. Non-termination bugs can be subtle to detect and may remain hidden for long before they take effect. Many real-world programs still suffer from vast consequences (e.g., no response) caused by non-termination bugs. As a classic problem, termination proving has been studied for many years. Many termination checking tools and techniques have been developed and demonstrated effectiveness on existing wellestablished benchmarks. However, the capability of these tools in finding practical non-termination bugs has yet to be tested on real-world projects. To fill in this gap, in this paper, we conducted the first large-scale empirical study of non-termination bugs in real-world OSS projects. Specifically, we first devoted substantial manual efforts in collecting and analyzing 445 non-termination bugs from 3,142 GitHub commits and provided a systematic classification of the bugs based on their root causes. We constructed a new benchmark set characterizing the real-world bugs with simplified programs, including a non-termination dataset with 56 real and reproducible non-termination bugs and a termination dataset with 58 fixed programs. With the constructed benchmark, we evaluated five state-of-the-art termination analysis tools. The results show that the capabilities of the tested tools to make correct verdicts have obviously dropped compared with the existing benchmarks. Meanwhile, we identified the challenges and limitations that these tools face by analyzing the root causes of their unhandled bugs. Finally, we summarized the challenges and future research directions for detecting non-termination bugs in real-world projects.

Keywords

Non-termination Bug, Benchmarking, Empirical Study

Discipline

Programming Languages and Compilers | Software Engineering

Research Areas

Intelligent Systems and Optimization

Publication

Proceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering, Singapore, 2022 November 14-18

First Page

256

Last Page

268

ISBN

97814503941302

Identifier

10.1145/3540250.3549129

Publisher

ACM

City or Country

Singapore

Additional URL

http://doi.org/10.1145/3540250.3549129

Download

Share

COinS