SAT-Powered Plant Synthesis: Automating the Missing Link in Closed-Loop Verification

TL;DR

In industrial automation, verifying a controller is only half the battle; you need a model of the physical "plant" it controls. This paper introduces a method to automatically build these plant models (as nondeterministic Moore automata) using two inputs: execution traces (what the plant did) and LTL properties (what the plant must/mustn't do). By leveraging incremental SAT solvers, the authors transform a tedious manual modeling task into a precise, automated optimization problem.

Background: The Closed-Loop Challenge

Formal verification via model checking often happens in an "open-loop" setting, where the controller's inputs are assumed to be anything. This leads to "state space explosion"—the checker explores thousands of impossible scenarios (like a water tank filling up even when the valve is closed).

A closed-loop approach, which includes a plant model, constrains the search to realistic physical behaviors. However, building these plant models manually is a bottleneck. The authors' insight is to treat plant modeling as a synthesis problem: can we find the smallest state machine that "explains" our simulation data and satisfies our safety rules?

Methodology: From Traces to SAT Formulas

The method represents the plant as a Nondeterministic Moore Automaton. Nondeterminism is key here—it allows the model to capture sensor noise, human intervention, or discretization errors without needing a complex, purely deterministic mathematical model.

The SAT Workflow

The synthesis process follows a sophisticated iterative loop:

1. Positive Trace Encoding: All recorded behaviors (traces) are converted into constraints. If a trace says "Input A leads to Output B," the SAT solver must ensure a path exists in the generated automaton.
2. Incremental Solving: The solver tries to find a state machine with a fixed number of states $|S|$.
3. Counterexample Refinement: If the generated model violates an LTL property (e.g., "The tank should never overflow"), the solver finds a "counterexample" (a trace the model can do but shouldn't). This is fed back into the solver as a negative trace constraint.

Figure 1: The architecture of the proposed synthesis method, showing the interplay between traces, LTL properties, and the SAT solver.

Logic Behind the Transitions

The authors use specific Boolean variables:

• $x_{v,s}$: Does node $v$ in the trace graph map to state $s$ in the automaton?
• $y_{s1,s2,i}$: Is there a transition from state $s1$ to $s2$ on input $i$?
• $z_{s,o}$: Does state $s$ produce output $o$?

The SAT solver balances these variables to ensure the automaton is complete (has a response for every input) and minimal.

Experimental Results

The authors tested the method on three distinct scenarios:

1. Pneumatic Cylinder: A simple smoke test resulting in a 3-state model.
2. Water Level Control: A more complex system from a heat production plant. The system synthesized an 80-state model in under 6 minutes.
3. Nuclear Power Plant (NPP): Using data from the professional simulation environment Apros, the method created a 12-state model for an emergency pump system.

Performance Comparison

When compared to traditional State Merging (like the GK-tails algorithm), the SAT-based approach demonstrated superior precision. While state merging is computationally faster, it often ignores non-safety LTL properties and produces models that are significantly larger (3x the states), making them less efficient for downstream model checking.

Table 1: Computational performance on water level control instances, showing efficient scaling up to 80 states.

Critical Insight & Conclusion

This work represents a major step toward "intelligent discretization." By using SAT solvers, the authors don't just compress data; they ensure the resulting model obeys the laws of the system (LTL properties).

Limitations: The primary bottleneck is the SAT solver's memory usage when dealing with extremely long traces (the NPP case required 4GB of RAM). Furthermore, highly complex dynamics might still require manual partitioning of the plant into smaller, modular components.

The Takeaway: For engineers working on safety-critical PLCs or industrial robots, this method provides a "Push-Button" way to generate formal models from simulation data, significantly reducing the manual overhead of formal verification.