Introduction
The verification of safety-critical systems, such as autonomous vehicles and medical devices, necessitates rigorous proof that a system will never transition into an unsafe state. This is achieved through reachability analysis, which computes the set of all possible states a system can reach over time from a given range of initial conditions. While linear systems are well-understood, nonlinear dynamics—characterized by powers, products, or trigonometric functions—present significant computational challenges. The difficulty of reachability analysis scales exponentially with the number of state variables and the magnitude of initial uncertainty.
This report summarizes the findings of the ARCH-COMP17 "friendly competition," a benchmarking initiative designed to evaluate the state-of-the-art in nonlinear continuous system verification. Three prominent tools—CORA, Flow*, and Isabelle/HOL—were evaluated across a suite of benchmarks to provide a transparent landscape of current capabilities and the inherent trade-offs between computational efficiency and formal trustworthiness.
Tool Methodologies
The competition featured three tools, each employing a distinct mathematical framework to overapproximate the "flowpipe" (the set of reachable states over a time interval):
- CORA (COntinuous Reachability Analyzer): A MATLAB-based tool utilizing zonotopes. It often employs "conservative linearization," simplifying nonlinear systems into linear ones with an added error term to maintain scalability in higher dimensions.
- Flow*: A C++ tool based on Taylor Models (TM). It approximates the solution of Ordinary Differential Equations (ODEs) using high-order polynomials combined with remainder intervals, allowing for high-precision tracking of set evolution.
- Isabelle/HOL-ODE-Numerics: This tool represents the pinnacle of formal rigor. It utilizes formally verified algorithms (e.g., Runge-Kutta methods with affine arithmetic) within an interactive theorem prover. Every computational step, including roundoff error management, is mathematically proven correct, albeit at a significant cost to execution speed.
Benchmarking Suite
The tools were tested against three benchmarks of increasing complexity:
- Van der Pol Oscillator (2 variables): A classic nonlinear system with a stable limit cycle, serving as a baseline for accuracy.
- Laub-Loomis Model (7 variables): A model of enzymatic activities used to assess how tools handle increasing initial uncertainty (tested at widths $W=0.01$ and $W=0.1$).
- Controlled Quadrotor (12 variables): A high-dimensional drone model stabilized by PD controllers, involving complex trigonometric dynamics to test scalability.
Results and Comparative Analysis
The competition highlighted a clear "Trust vs. Speed" trade-off. Isabelle/HOL, while providing the highest level of formal assurance, was often orders of magnitude slower than its counterparts. Conversely, Flow* and CORA demonstrated impressive speed, particularly on lower-dimensional or less uncertain sets.
Key Performance Metrics:
- Van der Pol: Flow* was the fastest at 2 seconds, followed by Isabelle/HOL (3s) and CORA (8s).
- Laub-Loomis: CORA excelled with the smaller initial set (3s). However, as uncertainty increased ($W=0.1$), Flow* scaled more effectively (18s) compared to CORA (63s) and Isabelle (1200s). This "uncertainty explosion" demonstrated that a 10x increase in initial set width can lead to a >20x increase in computation time for some tools.
- Quadrotor: Both CORA (11s) and Flow* (12s) handled this 12-variable challenge efficiently. Isabelle/HOL did not provide results for this benchmark in this report, highlighting the current limitations of formally verified methods in high-dimensional spaces.
Conclusion
The ARCH-COMP17 report underscores that there is no "silver bullet" for nonlinear reachability analysis. Tool selection depends heavily on the specific requirements of the task—whether it be rapid iteration (Flow*, CORA) or absolute formal certainty (Isabelle/HOL). Furthermore, the performance of these tools is highly sensitive to user-defined parameters such as step size and approximation order. Future work will focus on expanding the toolset, addressing hybrid systems with discrete switches, and developing automated parameter tuning to make these powerful verification techniques more accessible to non-experts.
Summary updated