TL;DR
This paper introduces a semi-automated approach to Design Space Exploration (DSE) for formal modeling, specifically targeting the Event-B formalism. By combining automated theory formation (using the HR system) with automated reasoning, the authors propose a tool that analyzes a designer's work "behind the scenes" to suggest alternative abstractions and model adaptations that improve both correctness and clarity.
The Challenge of Abstraction in Formal Methods
Formal methods provide mathematical rigor for software-intensive systems, but they are notoriously difficult to use. A major hurdle is finding the "right" level of abstraction.
If a model is too concrete too early, the designer gets bogged down in implementation details, making it harder to verify requirements and "locking" the team into a specific solution prematurely. Currently, finding the right abstraction is a manual, creative process of trial-and-error. The authors aim to automate the "low-level grind" of this process, providing high-level modeling guidance in real-time to help designers escape "concrete-level" traps.
Methodology: A Two-Phase Semi-Automated Loop
The authors propose a two-phase, semi-automated loop that integrates analysis and model generation.
Phase 1: Analysis via Automated Theory Formation (ATF)
The system uses Automated Theory Formation (ATF) via the HR system. It takes simulation traces (generated by the ProB model checker) and "invents" concepts and conjectures. For example, it might find that a specific event always leads to an invariant violation.
As shown in Figure 1, the HR system operates by taking base data (like a table of divisors) and applying production rules (like size or split) to derive higher-level concepts (like the Tau function or the set of Primes). In the context of formal modeling, this allows the tool to look for "near-properties"—statements that are true for most, but not all, behaviors—to provide insights into where a design is "almost" right.
Phase 2: Generation via Model Transformation
Based on the analysis, the tool applies a library of transformations to the model. This library consists of atomic operators (e.g., deleteVariable, mergeEvents), conditions for their application, and combinators that structure complex rules.
The core innovation here is the use of Abstraction Patterns. While most formal methods research focuses on refinement (moving from abstract to concrete), this work "inverts" those patterns. By moving back up to a more useful level of abstraction, designers can fix fundamental flaws before re-refining the model.
Key Insights and Ideas
- Near-Invariants as Signposts: In formal logic, a statement is usually binary (true or false). However, the authors argue that a property that is "true for 90% of cases" is a valuable heuristic, suggesting a solution that lies just beyond the current model's reach.
- Inverting Refinement: The authors recognize that you cannot "refine away" a flaw. Instead, you must often abstract away the problematic area, fix it at a higher level, and then re-refine.
- Semi-Automation: The goal isn't to replace the human designer but to act as an "intelligent assistant." The tool suggests alternatives, but the designer retains full control over the design trajectory.
Evaluation and Results
The approach was evaluated using a bank transfer protocol model intentionally designed with flaws like deadlocks and invariant violations. The tool successfully generated several distinct alternatives:
- Abstraction A1: "Atomized" sequential events to remove a problematic intermediate state.
- Adaptation A2: Introduced error-handling events to "undo" bad behavior.
- Adaptation A3: Suggested a more complex, correct invariant that accounted for internal "in-flight" transaction states.
- Abstraction A4: Produced a highly abstract view where the core requirements were naturally satisfied and easier to communicate.
Limitations and Future Work
While promising, the system currently faces challenges with manual integration, as the selection of operators still requires human intervention. Furthermore, the search space explosion inherent in unconstrained model generation requires better heuristics to prune irrelevant suggestions. Future work focuses on identifying a "small yet complete" set of atomic operators to minimize redundancy while maximizing the tool's creative reach.
Summary updated