Regular Model Checking Upside-Down: An Invariant-Based Approach
0
📈
Sign in to get full access
Overview
- Regular model checking is a technique for verifying infinite-state systems where configurations are represented as finite words.
- It applies to systems with regular initial configurations and length-preserving transition relations.
- To verify safety properties, regular model checking iteratively computes automata recognizing larger regular sets of reachable configurations.
- Since this procedure often does not terminate, acceleration, abstraction, and widening techniques have been developed.
Plain English Explanation
Regular model checking is a method for verifying the safety of systems that have an infinite number of possible states. In these systems, each state can be represented as a finite sequence of symbols, like a word. The key requirements are that the initial states form a regular set (can be recognized by a finite automaton) and the transitions between states preserve the length of the word.
To check safety properties, regular model checking works by iteratively computing larger and larger sets of reachable states, represented as automata. If one of these automata includes an "unsafe" state, then the system is not safe. However, this process often does not terminate, so researchers have developed techniques like acceleration, abstraction, and widening to help compute a regular superset of the reachable states.
Technical Explanation
The paper proposes a complementary approach to regular model checking. Instead of computing the reachable states from the initial states, it starts with the set of all possible states and computes increasingly smaller regular supersets. This is based on the observation that the set of reachable states is equal to the intersection of all inductive invariants of the system.
Since the intersection of invariants is generally non-regular, the paper introduces the concept of
The paper then studies the complexity of determining if this automaton accepts any unsafe configurations. It is shown that this problem is in EXPSPACE for all b ≥ 0, and PSPACE-complete for b=1. Finally, the paper investigates how large b needs to be to prove safety properties for a number of benchmark systems.
Critical Analysis
The proposed approach provides a novel perspective on regular model checking by starting from the set of all configurations rather than the initial states. This allows leveraging the notion of inductive invariants, which are fundamental to program verification.
However, the reliance on b-bounded invariants introduces an approximation that may limit the approach's effectiveness. Depending on the system, a large value of b may be required to obtain sufficiently precise invariants. The complexity results also suggest that the method may face scalability challenges, especially for larger values of b.
Further research could explore techniques to automatically infer tighter b-bounded invariants, or investigate ways to combine this approach with other regular model checking methods to leverage their complementary strengths. Evaluating the approach on a wider range of realistic benchmarks would also help assess its practical utility.
Conclusion
This paper presents a new direction for regular model checking by starting from the set of all configurations and computing increasingly smaller regular supersets based on bounded inductive invariants. While this approach offers a fresh perspective, it also faces potential challenges related to the precision of the approximation and the computational complexity. Continued research to address these limitations could lead to further advancements in the verification of infinite-state systems.
This summary was produced with help from an AI and may contain inaccuracies - check out the links to read the original source documents!
Related Papers
📈
0
Regular Model Checking Upside-Down: An Invariant-Based Approach
Javier Esparza, Mikhail Raskin, Christoph Welzel-Mohr
Regular model checking is a well-established technique for the verification of infinite-state systems whose configurations can be represented as finite words over a suitable alphabet. It applies to systems whose set of initial configurations is regular, and whose transition relation is captured by a length-preserving transducer. To verify safety properties, regular model checking iteratively computes automata recognizing increasingly larger regular sets of reachable configurations, and checks if they contain unsafe configurations. Since this procedure often does not terminate, acceleration, abstraction, and widening techniques have been developed to compute a regular superset of the set of reachable configurations. In this paper we develop a complementary approach. Instead of approaching the set of reachable configurations from below, we start with the set of all configurations and compute increasingly smaller regular supersets of it. We use that the set of reachable configurations is equal to the intersection of all inductive invariants of the system. Since the intersection is in general non-regular, we introduce $b$-bounded invariants, defined as those representable by CNF-formulas with at most $b$ clauses. We prove that, for every $b geq 0$, the intersection of all $b$-bounded inductive invariants is regular, and show how to construct an automaton recognizing it. We study the complexity of deciding if this automaton accepts some unsafe configuration. We show that the problem is in textsc{EXPSPACE} for every $b geq 0$, and textsc{PSPACE}-complete for $b=1$. Finally, we study how large must $b$ be to prove safety properties of a number of benchmarks.
Read more7/31/2024
📉
0
Computing Inductive Invariants of Regular Abstraction Frameworks
Philipp Czerner, Javier Esparza, Valentin Krasotin, Christoph Welzel-Mohr
Regular transition systems (RTS) are a popular formalism for modeling infinite-state systems in general, and parameterised systems in particular. In a CONCUR 22 paper, Esparza et al. introduce a novel approach to the verification of RTS, based on inductive invariants. The approach computes the intersection of all inductive invariants of a given RTS that can be expressed as CNF formulas with a bounded number of clauses, and uses it to construct an automaton recognising an overapproximation of the reachable configurations. The paper shows that the problem of deciding if the language of this automaton intersects a given regular set of unsafe configurations is in $textsf{EXPSPACE}$ and $textsf{PSPACE}$-hard. We introduce $textit{regular abstraction frameworks}$, a generalisation of the approach of Esparza et al., very similar to the regular abstractions of Hong and Lin. A framework consists of a regular language of $textit{constraints}$, and a transducer, called the $textit{interpretation}$, that assigns to each constraint the set of configurations of the RTS satisfying it. Examples of regular abstraction frameworks include the formulas of Esparza et al., octagons, bounded difference matrices, and views. We show that the generalisation of the decision problem above to regular abstraction frameworks remains in $textsf{EXPSPACE}$, and prove a matching (non-trivial) $textsf{EXPSPACE}$-hardness bound. $textsf{EXPSPACE}$-hardness implies that, in the worst case, the automaton recognising the overapproximation of the reachable configurations has a double-exponential number of states. We introduce a learning algorithm that computes this automaton in a lazy manner, stopping whenever the current hypothesis is already strong enough to prove safety. We report on an implementation and show that our experimental results improve on those of Esparza et al.
Read more7/22/2024
0
Receding-Constraint Model Predictive Control using a Learned Approximate Control-Invariant Set
Gianni Lunardi, Asia La Rocca, Matteo Saveriano, Andrea Del Prete
In recent years, advanced model-based and data-driven control methods are unlocking the potential of complex robotics systems, and we can expect this trend to continue at an exponential rate in the near future. However, ensuring safety with these advanced control methods remains a challenge. A well-known tool to make controllers (either Model Predictive Controllers or Reinforcement Learning policies) safe, is the so-called control-invariant set (a.k.a. safe set). Unfortunately, for nonlinear systems, such a set cannot be exactly computed in general. Numerical algorithms exist for computing approximate control-invariant sets, but classic theoretic control methods break down if the set is not exact. This paper presents our recent efforts to address this issue. We present a novel Model Predictive Control scheme that can guarantee recursive feasibility and/or safety under weaker assumptions than classic methods. In particular, recursive feasibility is guaranteed by making the safe-set constraint move backward over the horizon, and assuming that such set satisfies a condition that is weaker than control invariance. Safety is instead guaranteed under an even weaker assumption on the safe set, triggering a safe task-abortion strategy whenever a risk of constraint violation is detected. We evaluated our approach on a simulated robot manipulator, empirically demonstrating that it leads to less constraint violations than state-of-the-art approaches, while retaining reasonable performance in terms of tracking cost, number of completed tasks, and computation time.
Read more8/29/2024
📊
0
A HAT Trick: Automatically Verifying Representation Invariants Using Symbolic Finite Automata
Zhe Zhou, Qianchuan Ye, Benjamin Delaware, Suresh Jagannathan
Functional programs typically interact with stateful libraries that hide state behind typed abstractions. One particularly important class of applications are data structure implementations that rely on such libraries to provide a level of efficiency and scalability that may be otherwise difficult to achieve. However, because the specifications of the methods provided by these libraries are necessarily general and rarely specialized to the needs of any specific client, any required application-level invariants must often be expressed in terms of additional constraints on the (often) opaque state maintained by the library. In this paper, we consider the specification and verification of such representation invariants using symbolic finite automata (SFA). We show that SFAs can be used to succinctly and precisely capture fine-grained temporal and data-dependent histories of interactions between functional clients and stateful libraries. To facilitate modular and compositional reasoning, we integrate SFAs into a refinement type system to qualify stateful computations resulting from such interactions. The particular instantiation we consider, Hoare Automata Types (HATs), allows us to both specify and automatically type-check the representation invariants of a datatype, even when its implementation depends on stateful library methods that operate over hidden state. We also develop a new bidirectional type checking algorithm that implements an efficient subtyping inclusion check over HATs, enabling their translation into a form amenable for SMT-based automated verification. We present extensive experimental results on an implementation of this algorithm that demonstrates the feasibility of type-checking complex and sophisticated HAT-specified OCaml data structure implementations.
Read more4/3/2024