EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Sound Termination and Non-termination Analysis of C Programs with Bit-Precise Bounded Semantics and Advanced Constructs

Negar Fathi, Hiroshi Unno, Tachio Terauchi, Rahul Purandare

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →