Bounded Structural Model Finding with Symbolic Data Constraints
This work addresses the need for more integrated and efficient bounded model finding in software design validation, though it appears incremental as it builds upon existing rewriting logic frameworks.
The authors tackled the problem of bounded model finding for software design validation by introducing the Maude Model Finder (MMF), a native approach that eliminates the semantic gap and external tool dependencies, achieving termination, soundness, and completeness within declared bounds.
Bounded model finding is a key technique for validating software designs, usually obtained by translating high-level specifications into SAT/SMT problems. Although effective, such translations introduce a semantic gap and a dependency on external tools. We present the \emph{Maude Model Finder} (MMF), a native approach that brings bounded model finding to the Maude rewriting logic framework. MMF provides a schema-parametric engine that repurposes symbolic reachability for structural solving, generating finite object configurations from class declarations and graph and data constraints without bespoke generators. Technically, MMF explores a constrained symbolic rewriting system over runtime states modulo an equational theory; SMT is used only to prune states by constraint satisfiability and to discharge entailment checks for subsumption and folding. We contribute a bounded, obligation-driven calculus that separates object creation from reference assignment and supports symmetry reduction by folding via Maude's ACU matching. We establish termination, soundness, and completeness of the bounded construction within the declared bounds, and justify folding via a coverage-preserving subsumption test. We focus on the calculus and its properties, illustrating it on running examples supported by a Maude prototype.