ARCH-COMP 2021 Category Report: Falsification with Validation of Results

Gidon Ernst, Paolo Arcaini, Ismail Bennani, Aniruddh Chandratre, Alexandre Donzé, Georgios Fainekos, Goran Frehse, Khouloud Gaaloul, Jun Inoue, Tanmay Khandait, Logan Mathesen, Claudio Menghi, Giulia Pedrielli, Marc Pouzet, Masaki Waga, Shakiba Yaghoubi, Yoriyuki Yamagata, Zhenya Zhang

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.

Table of STL formulas for the ARCH-COMP 2021 benchmarks.

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

BibTeX
@inproceedings{ernst2021arch,
  author = {Gidon Ernst and Paolo Arcaini and Ismail Bennani and Aniruddh Chandratre and Alexandre Donzé and Georgios Fainekos and Goran Frehse and Khouloud Gaaloul and Jun Inoue and Tanmay Khandait and Logan Mathesen and Claudio Menghi and Giulia Pedrielli and Marc Pouzet and Masaki Waga and Shakiba Yaghoubi and Yoriyuki Yamagata and Zhenya Zhang},
  title = {{ARCH-COMP 2021 Category Report: Falsification with Validation of Results}},
  booktitle = {ARCH@ADHS},
  year = {2021},
  doi = {10.29007/xwl1},
}
Figure