Loop-Based Slicing and Input-Driven Concretization: An Empirical Study of Termination and Non-Termination Analysis
Summary
The FocusTNT C front end, developed by Negar Fathi et al., empirically studies lightweight, tool-independent source-level preprocessing for C/C++ program (non-)termination analysis. FocusTNT applies loop-based slicing to isolate loop-level obligations and input-driven concretization to specialize nondeterministic inputs into selected scenarios. The study evaluated four configurations (Base, Slice, Cncrt, Slice+Cncrt) across six analyzers (Athena, Proton, UAutomizer, AProVE, CPAchecker, 2LS) on 117 C/C++ programs derived from real-world non-termination bugs and their fixes. Results indicate that preprocessing benefits are not uniform, depending on the analyzer, task, and program features. Slicing offers conservative structural isolation, while concretization can improve detectability for specific scenarios but narrows semantic scope. The combination of slicing and concretization is not consistently additive. The findings provide guidance for application developers interpreting verification outcomes and tool developers enhancing analyzer robustness.
Key takeaway
For research scientists and software engineers performing (non-)termination analysis on C/C++ programs, consider adaptively applying source-level preprocessing. If your current analyzer struggles with complex contexts or nondeterministic inputs, using loop-based slicing might isolate relevant code, or input-driven concretization could expose specific input-dependent behaviors. Be aware that benefits are tool-specific and not always additive; evaluate preprocessing effects on your specific verification tasks.
Key insights
Lightweight source-level preprocessing can reshape (non-)termination verification tasks for existing C/C++ analyzers.
Principles
- Preprocessing benefits vary by analyzer and task.
- Loop-based slicing isolates loop-relevant program structure.
- Input-driven concretization specializes nondeterministic inputs.
Method
FocusTNT generates program variants using loop-based slicing and/or input-driven concretization, then analyzes each variant with off-the-shelf (non-)termination tools, aggregating results via Algorithm 1.
Topics
- Termination Analysis
- Non-Termination Analysis
- Program Slicing
- Input Concretization
- C/C++ Verification
- FocusTNT
Best for: AI Scientist, Research Scientist, Software Engineer
Related on AIssential
See Counsel's argued verdicts on the open AI decisions leaders are weighing →
Editorial summary, takeaway, and curation by AIssential. Original article published by cs.SE updates on arXiv.org.