[Paper] Disjunction Composition of BDD Transition Systems for Model-Based Testing

Source: arXiv - 2602.17237v1

Overview

The paper presents a compositional technique for model‑based testing (MBT) in Behavior‑Driven Development (BDD). By turning BDD scenarios into formal transition systems and then combining them with a “disjunction composition” operator, the authors enable testers to generate a single, integrated test model that still preserves the fault‑detecting power of each original scenario.

Key Contributions

• Formal definition of disjunction composition for BDD transition systems, allowing alternative behaviors to be merged without loss of testing coverage.
• Symbolic semantics that link equivalence of transition systems to identical test outcomes, providing a rigorous guarantee that the composed model is as effective as the set of individual models.
• Proof of testing‑power preservation, showing that any test case that would fail on a component model will also fail on the composed model (and vice‑versa).
• Industrial case study demonstrating how the technique scales to real‑world BDD suites and reduces the effort required to maintain test models.

Methodology

1. Translate BDD Scenarios → Transition Systems
   • Each textual “Given‑When‑Then” scenario is parsed into a finite‑state transition system (states = system contexts, edges = actions).
2. Define Disjunction Composition
   • The operator builds a new transition system whose behavior is the union of the component systems’ behaviors. Technically, it creates a product automaton with a special “choice” state that nondeterministically selects one of the original systems to follow.
3. Introduce Symbolic Semantics
   • Instead of enumerating every concrete state, the authors use symbolic representations (e.g., predicates over variables) to capture sets of states compactly.
4. Prove Equivalence → Same Test Failures
   • They show that if two BDD transition systems are symbolically equivalent, any test generated from one will produce the same pass/fail result on the other. This underpins the claim that the composed model does not dilute testing power.
5. Validate with an Industrial Case Study
   • The authors applied the approach to a large BDD suite from a safety‑critical domain, measuring model size, test generation time, and defect detection rates before and after composition.

Results & Findings

• Model Size Reduction: The composed transition system was roughly 30 % smaller than the naïve union of all individual models, thanks to shared states and symbolic abstraction.
• Test Generation Speed: Generating test cases from the composed model took half the time compared with generating from each scenario separately.
• Coverage Preservation: Mutation analysis showed no loss in fault detection; the composed model caught the same set of injected bugs as the original suite.
• Industrial Feedback: Developers reported easier maintenance of BDD specifications because alternative flows could now be expressed once and reused across features.

Practical Implications

• Streamlined Test Pipelines: Teams can feed a single, compositional model into existing MBT tools (e.g., GraphWalker, Spec Explorer) instead of juggling dozens of tiny models.
• Reduced Technical Debt: When BDD scenarios evolve, only the affected component needs updating; the composition operator automatically reflects the change in the integrated test model.
• Better Agile‑MBT Alignment: The approach bridges the gap between BDD’s textual, stakeholder‑friendly format and the formal models required for high‑coverage automated testing, making MBT more palatable in fast‑moving agile projects.
• Scalability for Safety‑Critical Systems: The symbolic semantics keep state explosion in check, which is crucial for domains like automotive, aerospace, or medical devices where exhaustive testing is mandatory.

Limitations & Future Work

• Assumption of Deterministic Scenarios: The current composition works best when individual BDD transition systems are deterministic; handling highly nondeterministic or probabilistic scenarios remains an open challenge.
• Tooling Integration: The prototype implementation is research‑grade; tighter integration with mainstream BDD frameworks (Cucumber, Behave) and MBT tools is needed for industry adoption.
• Extending Beyond Disjunction: The authors plan to explore conjunction and sequencing composition operators to model more complex interactions (e.g., mandatory combined behaviors).

Bottom line: By formalizing how alternative BDD scenarios can be merged without sacrificing test effectiveness, this work gives developers a practical pathway to combine the readability of BDD with the rigor of model‑based testing—potentially saving time, reducing bugs, and keeping agile teams aligned.*

Authors

• Tannaz Zameni
• Petra van den Bos
• Arend Rensink

Paper Information

• arXiv ID: 2602.17237v1
• Categories: cs.SE, cs.FL
• Published: February 19, 2026
• PDF: Download PDF