Lattice-Based Semantics for Combinatorial Model Evolution

Combinatorial test design (CTD) is an effective test design technique, considered to be a testing best practice. CTD provides automatic test plan generation, but it requires a manual definition of the test space in the form of a combinatorial model. As the system under test evolves, e.g, due to iterative development processes and bug fixing, so does the test space, and thus, in the context of CTD, evolution translates into frequent manual model definition updates.

In this work, we show that the Boolean semantics currently in use by CTD tools to interpret the model is inadequate for combinatorial model evolution, and propose to replace it with a new lattice-based semantics that (1) provides a consistent interpretation of atomic changes to the model via Galois connections, and (2) exposes which additional parts of the model must change following an atomic change, in order to restore validity. We further use the new lattice-based semantics to define new higher-level atomic operations for combinatorial model evolution. Finally, we identify recurring abstraction and refinement patterns in the evolution of 42 real-world industrial models, and use the new lattice-based semantics to define new higher-level atomic constructs that encapsulate these patterns.

The proposed lattice-based semantics and related new modeling constructs advance the state-of-the-art in CTD with a new foundation for model evolution and with better tools for change comprehension and management.