Sound Termination and Non-termination Analysis of C Programs with Bit-Precise Bounded Semantics and Advanced Constructs
Proceedings of the ACM on Software Engineering · 30.06.2026 · 3 (FSE) · 4505-4528
DOI: 10.1145/3808205 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Software Engineering, online erschienen am 30.06.2026. Verfasst von Negar Fathi und 3 weiteren Autor:innen. Die Arbeit nennt 61 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Japan Society for the Promotion of Science (JSPS) KAKENHI.
Abstract (Originalsprache)
Program termination and non-termination analysis is a foundational problem in formal verification with important implications for software safety and reliability. Despite extensive research, existing techniques struggle with real-world C programs that manipulate complex data types such as pointers, arrays, and structures, or that perform low-level operations such as bitwise arithmetic and bounded integer computations. This paper introduces Athena, a framework for sound termination and non-termination analysis of C programs that models finite-width and bit-precise integer semantics and supports advanced constructs. Athena combines pointer-to-array rewriting, bounded integer semantics enforced via modulo arithmetic or bit-vector semantics, and an extended translation to Labeled Transition Systems (LTS), yielding structured, analyzable representations suitable for logic-based reasoning. Our analysis engine builds on MuVal, a modular verification engine based on the first-order fixpoint logic µCLP with background theories, and extends it with support for array, tuple, and bit-vector theories in ranking function synthesis and recurrent set detection. We evaluate Athena on the 2024 Termination Competition (TermCOMP) and on 117 real-world benchmarks featuring 445 non-termination bugs, after excluding benchmarks that rely on undefined behavior. It achieves 60.95% correctness on the real-world benchmarks and 76.28% on TermCOMP, while producing zero wrong results across both suites. These results highlight Athena’s strong combination of precision and soundness for the termination and non-termination analysis of complex C programs.
Förderung
- Japan Society for the Promotion of Science (JSPS) KAKENHI
Zitieren
APA
Fathi, N., Unno, H., Terauchi, T., & Purandare, R. (2026). Sound Termination and Non-termination Analysis of C Programs with Bit-Precise Bounded Semantics and Advanced Constructs. Proceedings of the ACM on Software Engineering, 3(FSE), 4505-4528. https://doi.org/10.1145/3808205
Vancouver
Fathi N, Unno H, Terauchi T, Purandare R. Sound Termination and Non-termination Analysis of C Programs with Bit-Precise Bounded Semantics and Advanced Constructs. Proceedings of the ACM on Software Engineering. 2026;3(FSE):4505-4528. doi:10.1145/3808205
BibTeX
@article{Fathi2026,
author = {Fathi, Negar and Unno, Hiroshi and Terauchi, Tachio and Purandare, Rahul},
title = {Sound Termination and Non-termination Analysis of C Programs with Bit-Precise Bounded Semantics and Advanced Constructs},
journal = {Proceedings of the ACM on Software Engineering},
year = {2026},
volume = {3},
number = {FSE},
pages = {4505--4528},
doi = {10.1145/3808205}
}
EUVIMED