Abstract
T2 (TERMINATOR 2) is an open-source tool designed for the automatic verification of complex temporal properties in infinite-state C programs. By reducing nuanced liveness and safety properties into simpler queries solvable by modern SMT solvers, T2 provides a robust framework for proving termination, non-termination, and advanced CTL* properties. Experimental results demonstrate that T2's reduction-based architecture outperforms existing specialized tools in both speed and versatility across diverse real-world benchmarks, including Windows kernel drivers and database back-ends.
Introduction
Software verification has traditionally focused on safety properties—ensuring that "nothing bad ever happens," such as buffer overflows or null pointer dereferences. However, many critical requirements are liveness properties, which guarantee that "something good eventually happens," such as a loop terminating, a request being handled, or a lock being released. Proving liveness is inherently more difficult than proving safety, particularly for infinite-state programs where variables can take on an unbounded range of values.
T2 represents an evolution of the original TERMINATOR project, offering an open-source platform capable of handling a broad class of temporal logics, including CTL, Fair-CTL, and CTL*. It bridges the gap between high-level C code and low-level mathematical logic, providing a modern, automated pipeline for analyzing complex software systems.
System Architecture and Methodology
T2 acts as a bridge between high-level programming and low-level mathematical logic. The process begins with an LLVM-based front-end that translates C code into an intermediate representation, which is then converted into a "native format" consisting of program locations and transition rules.
The core of T2's power lies in its back-end, which decomposes complex temporal properties into a series of simpler tasks through a reduction strategy. Instead of solving complex properties in one giant leap, T2 breaks them down into safety, termination, and non-termination checks:
- Safety Proving: Utilizing algorithms like Impact or Z3’s GPDR/Spacer to check if certain undesirable states are reachable.
- Termination Proving: Synthesizing "lexicographic ranking functions"—mathematical proofs that a program's state is "counting down" toward a finish line.
- Non-termination Proving: Searching for "recurrent sets," which provide proof that a program can become trapped in an infinite loop.
This architecture allows T2 to leverage highly optimized safety provers for complex temporal logic tasks. For Fair-CTL, T2 employs "prophecy variables" to encode future path choices into the current state, enabling the verification of properties that hold only under fair execution paths. T2 is uniquely positioned as the only tool capable of automatically proving CTL* properties for infinite-state programs, a logic that captures nuanced behaviors beyond the reach of LTL or standard CTL.
Experimental Evaluation
The effectiveness of T2 was evaluated using two extensive benchmark sets: 1,222 integer transition systems from the 2015 Termination Competition and 56 CTL benchmarks drawn from real-world systems like the Windows OS kernel I/O subsystem and the PostgreSQL database server back-end.
Performance Results
In termination benchmarks, T2 (specifically the T2-GPDR configuration) demonstrated superior performance compared to state-of-the-art tools like AProVE. T2-GPDR solved 627 instances with an average time of 23.6 seconds, whereas AProVE averaged 49.1 seconds for its successful cases. On temporal logic benchmarks, T2 successfully verified every single one of the 56 Windows/PostgreSQL benchmarks, requiring only 2.7 seconds on average per example.
The results highlight that T2's modular architecture is remarkably robust across different types of software, proving that a reduction-based approach can be more efficient than complex "portfolio" solvers that bundle many different techniques.
Conclusion and Future Work
T2 demonstrates that a modular architecture based on property reduction is highly effective for temporal verification. While currently limited to linear integer arithmetic and abstract memory models, it remains a state-of-the-art solution for infinite-state programs. Future development aims to enhance support for non-linear arithmetic, complex data structures (the heap), and concurrency, further extending its utility for modern software engineering.
Summary updated