Abstract
Scenario-Based Modeling (SBM) is an intuitive paradigm for building complex systems through independent scenario objects. However, modern applications like autonomous vehicles require "Rich Events" involving continuous data, which complicates traditional model-checking and repair. This paper presents a framework for the automated repair of Rich Scenario-Based Models (rSBM). By utilizing SMT solvers to partition infinite state spaces into finite transition graphs, the authors identify safety violations and generate non-intrusive "patch" objects to fix them, preserving the original system logic.
Introduction: The Challenge of Rich Events
Scenario-Based Modeling (SBM) allows developers to build complex systems by composing small, independent "scenario objects" that describe specific behaviors. While this approach is intuitive, repairing these models after deployment is risky; fixing one bug often introduces another due to hidden dependencies between scenarios.
Existing research has addressed repair 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, are inapplicable. This paper bridges that gap by introducing a method to handle continuous data within the SBM framework.
Methods: From Continuous Data to Finite Graphs
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, 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. This patch 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.
Key Insights: Predicates and Non-Intrusive Repair
- The Power of Predicates: The core realization is 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: A core tenet of SBM is that system behavior can be changed by adding new scenarios. The authors leverage this for "non-intrusive" repairs. The "patch" is just another scenario object that says "don't do that" at specific moments, avoiding modifications to the original source code.
- Leveraging Off-the-Shelf Solvers: By restricting constraints to first-order, quantifier-free linear real arithmetic, the authors ensure that state discovery can be handled efficiently by existing SMT solvers.
Results: Drone Navigation Case Study
The paper provides a proof-of-concept demonstration using a drone control model with variables for vertical and horizontal angular velocities ($v, h$).
- 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 specific sequences of events that violated safety properties.
- Automated Patching: The system generated a patch object that monitors the drone's state and blocks specific assignments only when they would lead to a "bad" outcome.
Conclusion and Future Work
While partitioning predicates helps, the composite transition graph of many scenario objects can still grow exponentially. Future work includes exploring "sub-modeling" to manage state explosion and improving the scalability of the power set iteration. The authors also plan a full implementation on an existing rSBM platform to evaluate performance on more complex, real-world benchmarks.
Summary updated