Abstract
The 2021 ARCH-COMP competition for Cyber-Physical Systems (CPS) falsification introduced a rigorous validation pipeline to address the reproducibility crisis in the field. By re-simulating reported counterexamples through an independent reference checker, the competition moved beyond self-reporting to ensure scientific accuracy. This report summarizes the performance of eight state-of-the-art tools across diverse benchmarks, highlighting the challenges of numerical noise, versioning, and complex conjunctive requirements.
Introduction
Cyber-Physical Systems (CPS), which integrate discrete logic with continuous physical processes, are notoriously difficult to verify. Falsification tools offer a practical alternative to formal proof by searching for specific input sequences that cause a system to violate its formal requirements. Historically, these competitions relied on self-reported results. The 2021 ARCH-COMP report marks a significant shift by introducing independent validation of these results to ensure that a reported "failure" is a genuine violation of the model's specifications.
Methods
The competition evaluated eight tools, including newcomers FalCAuN and ForeSee. These tools employ various search strategies to identify counterexamples:
- Optimization-based: Minimizing a "robustness" metric (measuring how close a system is to violation) using algorithms like Nelder-Mead or CMA-ES.
- Reinforcement Learning: Training agents (e.g., A3C) to learn how to steer the system toward a violation.
- Automata Learning: Abstracting the system into simpler models to find logical flaws.
The core innovation of the 2021 report was the validation pipeline. Participants submitted falsifying input traces in a standardized CSV format. The organizers then re-simulated these inputs using an independent reference checker built on the FalStar framework to verify if the violation held up under scrutiny.
Benchmarks and Requirements
The competition utilized the ARCH benchmark suite, representing a wide array of CPS challenges. The formal requirements for these systems are expressed using Signal Temporal Logic (STL), which allows for precise definitions of safety and performance bounds over time.
Key benchmarks included:
- Automatic Transmission (AT): Models checking gear shifts and engine speed constraints.
- Fuel Control (AFC): An automotive powertrain model.
- Neural-network Controller (NN): A magnet levitation system controlled by a neural network.
- Chasing Cars (CC): A multi-car platoon scenario.
- F16 Aircraft: A ground collision avoidance system.
- Steam Condenser (SC): A thermal system controlled by a recurrent neural network.
A significant addition in 2021 was the introduction of conjunctive requirements (e.g., AT6abc). These require a tool to find a single input sequence that violates multiple conditions simultaneously, greatly increasing the search difficulty.
Key Insights and Results
The validation process revealed several critical issues that previously went unnoticed:
- The "Near-Miss" Problem: Some tools reported failures based on discrete-time abstractions that were slightly inaccurate, leading to "passes" in the continuous-time reference simulation.
- Numerical Fragility: Even minor changes, such as switching MATLAB versions or adjusting ODE solver settings, could turn a "falsified" requirement back into a "satisfied" one.
- Human Error: Validation uncovered configuration mistakes, such as tools searching incorrect input ranges or misinterpreting discrete values in the transmission model.
In terms of performance, tools like zlscheck and S-TaLiRo demonstrated high success rates across most benchmarks. However, validation often downgraded reported successes. For instance, in the AT6a benchmark, one tool reported 46 falsifications, but only 12 were successfully validated. Conjunctive requirements proved particularly challenging; only a few tools, such as S-TaLiRo using the minSOAR framework, were able to consistently falsify these complex properties.
Conclusion
The 2021 ARCH-COMP report underscores the necessity of standardization and independent validation in CPS testing. While falsification tools are becoming more powerful, the "reproducibility crisis" caused by numerical noise and abstraction errors remains a significant hurdle. Future work will focus on fully automating the validation pipeline and pushing toward higher-dimensional models and more complex neural-network-in-the-loop systems.
Summary updated