TL;DR
This paper introduces a method for the automated repair of "Rich" Scenario-Based Models (rSBM)—systems modeled using behaviors that handle continuous data rather than just discrete events. By leveraging SMT solvers to partition an infinite state space into a finite transition graph, the authors demonstrate how to automatically identify safety violations and generate "patch" objects to fix them without altering the original source code.
What Problem Does This Paper Address?
Scenario-Based Modeling (SBM) is a powerful paradigm where complex systems are built by composing small, independent "scenario objects" that describe specific behaviors (e.g., "if the water is low, add hot water"). While SBM is intuitive, repairing these models after deployment is risky; fixing one bug often introduces another due to hidden dependencies.
Existing research has solved this for "vanilla" SBM, where events are discrete and finite. However, modern systems like drones or autonomous vehicles require "Rich Events"—data-carrying variables like velocity or heading that exist on a continuous spectrum. Because there are infinitely many possible values for these variables, traditional model-checking and repair techniques (which rely on exhaustive state exploration) break down. This paper bridges that gap.
Methods
The authors propose a framework to translate "rich" scenario code into a finite transition graph that can be analyzed. The key steps are:
- Predicate Extraction: The algorithm parses the scenario object's code to find all logical predicates (e.g., $x < 5$, $v \geq 2$).
- SMT-Based State Partitioning: Even though a variable can have infinite values, the program's behavior only changes when a predicate's truth value flips. The authors use an SMT (Satisfiability Modulo Theories) solver to probe the power set of these predicates. For each combination of predicates, the solver either finds a concrete example assignment or proves the combination is impossible.
- Graph Construction: These concrete assignments are used to "trigger" the scenario object and map out its transitions, effectively turning a continuous-data program into a finite-state automaton.
- Automated Repair: Once the graph is built, the system searches for "bad" states (safety violations). It then automatically generates a patch scenario object. In the spirit of SBM, this patch doesn't modify existing code; instead, it runs alongside the original model and uses the "blocking" idiom to prevent the system from ever taking a transition that leads to a bad state.
Datasets
As a theoretical "ongoing work" paper, it does not utilize large-scale public benchmarks. Instead, it uses a Drone Control Model as a running example. This model includes variables for vertical and horizontal angular velocities ($v, h$) and specific safety properties (e.g., forbidding two sharp turns in a row).
Key Insights and Ideas
- The Power of Predicates: The "aha moment" is the realization that we don't need to check every possible value of a real-valued variable. We only need to check the boundaries defined by the code's own logic.
- Repair by Addition, Not Modification: A core tenet of SBM is that you should be able to change system behavior by adding new scenarios. The authors leverage this to perform "non-intrusive" repairs. The "patch" is just another scenario object that says "don't do that" at specific moments.
- Leveraging Off-the-Shelf Solvers: By restricting constraints to first-order, quantifier-free linear real arithmetic, the authors ensure that the heavy lifting of state discovery can be handled efficiently by existing SMT solvers in polynomial time.
Key Results
The paper provides a proof-of-concept demonstration:
- Successful Extraction: The algorithm successfully reduced a drone navigation scenario with infinite possible movements into a manageable transition graph.
- Violation Detection: The model checker identified a specific sequence of events (e.g., a vertical thrust followed by a sharp horizontal turn) that violated the safety property.
- Automated Patching: The system generated a patch object that monitors the drone's state and blocks the specific "sharp turn" assignment only when the drone is in a state where that turn would lead to a "bad" outcome.
Limitations and Future Work
- State Explosion: While partitioning predicates helps, the composite transition graph of many scenario objects can still grow exponentially. The authors suggest "sub-modeling" (breaking the system into smaller pieces) as a potential fix.
- Scalability of the Power Set: The current algorithm iterates through $2^{P_O}$ (the power set of predicates). If a scenario has many predicates, this becomes a bottleneck. The authors mention ongoing work to merge transitions and reduce SMT calls.
- Implementation: The paper describes the theory and manual examples; the next step is a full implementation on an existing rSBM platform to evaluate performance on more complex, real-world benchmarks.
Summary updated