In formal verification, the "state-space explosion" problem is the primary obstacle to proving that a system is safe. Traditional model checking often attempts to build a complete map of every possible state a system can reach before checking if any of those states violate a property. For complex systems—like distributed protocols or real-time controllers—this map is often too large to fit in memory, or even infinite.
On-the-fly verification (also known as local or incremental verification) shifts the paradigm from "build then check" to "check while building." Instead of constructing a global model, these algorithms explore the system's state space like a traveler using a flashlight in a dark cave: they only illuminate the paths necessary to reach a conclusion.
The Intuition of Local Exploration
The core insight behind on-the-fly methods is that most of a system's theoretical state space is irrelevant to a specific property. As Kim Guldstrand Larsen argued in Efficient Local Correctness Checking, we can avoid the dreaded state-space explosion by translating correctness problems into Boolean Equation Systems (BES) and solving them locally.
This is often more efficient than "pre-calculating" safety requirements. In Validating Generalized Plans in the Presence of Incomplete Information, Marianne Winslett demonstrated that "Prove-As-You-Go" strategies outperform "Prove-Ahead" strategies because they focus exclusively on states that are actually reachable during execution. By ignoring the "impossible" states that a system never encounters, the verifier saves massive amounts of computation.
Incremental Automata and Synthesis
This incremental philosophy extends to reactive synthesis—the process of automatically generating a strategy that satisfies a logical goal. Standard synthesis for Linear Temporal Logic (LTL) typically requires building a massive deterministic automaton upfront, a process that is "doubly exponential" in complexity.
Recent work by Giuseppe De Giacomo and Moshe Y. Vardi in Synthesis for LTL and LDL on Finite Traces highlights the need for on-the-fly determinization. By generating successor states only as needed, tools like those described in On-the-fly Synthesis for LTL over Finite Traces can often find a winning strategy or prove a goal is impossible without ever constructing the full state space. This allows synthesis engines to terminate early, bypassing the theoretical bottlenecks of the logic.
Real-Time and Multi-Agent Systems
On-the-fly techniques are particularly vital for systems with continuous variables, such as time. The tool UPPAAL, introduced by Johan Bengtsson, Paul Pettersson, and Wang Yi, pioneered this approach for timed automata. As detailed in Model-Checking for Real-Time Systems, UPPAAL explores the state space dynamically, generating "diagnostic traces" (counter-examples) the moment a violation is found.
In the realm of multi-agent systems, where the number of agents can cause exponential growth, on-the-fly graph exploration remains the gold standard. The CGAAL model checker by Nicolaj Ø. Jensen and colleagues uses heuristics to guide this exploration, allowing it to verify complex strategic properties orders of magnitude faster than tools that rely on global model construction.
From Initial States to Live States
While traditional verification starts from a "blank slate" (the initial system state), on-the-fly methods can also be applied to running systems. CrystalBall takes this to the extreme by initializing model checking from live-state snapshots of deployed distributed systems.
By starting the search from the system's current operational context rather than its birth, the verifier bypasses the millions of interleavings that occurred in the past. This allows it to "see" impending bugs just a few steps ahead in the future, enabling the system to steer itself away from inconsistencies in real-time.
Why It Works: Early Termination and Pruning
The success of on-the-fly verification rests on two pillars:
- Early Termination: If a bug exists, an on-the-fly search might find it in the first few branches, allowing the algorithm to stop immediately.
- Dynamic Pruning: By analyzing dependencies during the search—such as "urgent" behaviors in timed systems (Start Pruning When Time Gets Urgent)—the verifier can mathematically prove that entire branches of the state space are redundant and can be safely ignored.
By treating the state space as a graph to be discovered rather than a data structure to be stored, on-the-fly verification makes the analysis of industrial-scale systems computationally feasible.