TL;DR
T2 (TERMINATOR 2) is the first open-source tool capable of automatically proving complex "temporal" properties—like whether a program will eventually finish or if a lock will always be released—for infinite-state C programs. By converting C code into mathematical models and leveraging powerful SMT solvers, T2 outperforms many existing specialized tools in both speed and the range of properties it can verify.
What Problem Does This Paper Address?
In the world of software verification, most tools focus on safety properties: ensuring that "nothing bad ever happens" (e.g., no buffer overflows). However, many critical software requirements are liveness properties: ensuring that "something good eventually happens" (e.g., a request is eventually handled, or a loop eventually terminates).
Proving liveness is significantly harder than proving safety, especially for "infinite-state" programs where variables can theoretically take on an infinite range of values. While the original TERMINATOR project made strides in this area, it was closed-source and limited. This paper introduces T2, an open-source evolution that handles a much broader class of temporal logics (CTL, Fair-CTL, and CTL*) and provides a modern, automated pipeline for analyzing real-world C code.
Methods
T2 acts as a bridge between high-level programming and low-level mathematical logic. Its architecture is split into two main parts:
- Front-end (LLVM Integration): Instead of manually rewriting programs into mathematical formulas, T2 uses the LLVM compiler framework. It takes C code, converts it to LLVM's intermediate representation, and then automatically translates that into a "native format" consisting of program locations and transition rules.
- Back-end (The Prover): T2 doesn't try to solve complex temporal properties in one giant leap. Instead, it uses a reduction strategy. It breaks down complex properties (like those in CTL*) into a series of simpler queries:
- Safety Proving: Uses the Impact algorithm or Z3’s GPDR/Spacer to check if certain states are reachable.
- Termination Proving: Synthesizes "lexicographic ranking functions"—mathematical proofs that a program's state is "counting down" toward a finish line.
- Non-termination Proving: Searches for "recurrent sets," which are essentially proof that a program can get stuck in an infinite loop.
The system is implemented in F# and relies heavily on the Z3 SMT solver to handle the underlying mathematical constraints.
Datasets
The authors evaluated T2 using two primary sets of benchmarks:
- Termination Benchmarks: A collection of 1,222 integer transition systems from the 2015 Termination Competition. These include manually crafted programs and code automatically translated from Java (e.g.,
java.util.HashSet) and C (e.g., Windows kernel drivers). - CTL Benchmarks: A set of 56 benchmarks drawn from real-world systems, including the Windows OS kernel I/O subsystem, the PostgreSQL database server back-end, and the SoftUpdates patch system.
Key Insights and Ideas
- The Power of Reduction: The most significant insight is that nearly all complex temporal properties can be decomposed into safety, termination, and non-termination checks. This allows T2 to reuse highly optimized safety provers for much more complex tasks.
- Lexicographic Ranking: Unlike some competitors that use "disjunctive" arguments (which can be computationally expensive), T2 focuses on lexicographic ranking functions. This approach is often more efficient for proving that complex nested loops eventually terminate.
- Prophecy Variables: To handle "Fair-CTL" (proving things that happen only on "fair" execution paths, like a scheduler that eventually picks every task), T2 uses "prophecy variables" to encode future path choices into the current state of the program.
- CTL* Support: T2 is highlighted as the only tool capable of automatically proving CTL* properties for infinite-state programs, a logic that can express very nuanced behaviors that LTL or standard CTL cannot.
Key Results
- Termination: In head-to-head tests against the state-of-the-art tool AProVE, T2 (using the GPDR solver) was significantly faster. T2-GPDR solved 627 instances with an average time of 23.6 seconds, while AProVE took 49.1 seconds on average for its successful cases.
- Temporal Logic: On the 56 Windows/PostgreSQL benchmarks, T2 successfully verified every single one. It required only 2.7 seconds on average per example, outperforming the competing tool Q’ARMC, which averaged 3.6 seconds.
- Versatility: The results demonstrated that T2's "simple" architecture (compared to "portfolio" solvers that bundle many different techniques) is remarkably competitive and robust across different types of software.
Limitations and Future Work
- Arithmetic Constraints: T2 currently only supports linear integer arithmetic. It struggles with programs that rely on non-linear math (like
x * y) or complex bitwise operations, though it can approximate some of these. - Heap and Memory: While there are extensions for heap-based programs, the core version discussed here treats memory somewhat abstractly. The authors aim to improve support for complex data structures (the "heap"), recursion, and concurrency in future versions.
- Completeness: While the Fair-CTL prover is relatively complete, the CTL* prover is incomplete, meaning there are some valid properties it might fail to prove even if a proof exists.
- Integer Modeling: By default, T2 treats numbers as mathematical integers. While it has a transformation to handle machine integer overflow, this adds complexity to the verification process.
Summary updated