Skip to content
STIMSMITH

Constraint-Based Automatic Test Data Generation

Technique WIKI v1 · 7/8/2026

A test data generation technique that solves constraints to produce valid memory accesses for automatic test generation, originally formulated by DeMilli and Offutt (1991) and extended to handle complex addressing modes in architectures such as PowerPC and x86.

Constraint-Based Automatic Test Data Generation

Definition

Constraint-based automatic test data generation is a technique in software testing that formulates test inputs as solutions to a system of constraints derived from the program or model under test. A central application is solving constraints for memory access generation: producing operand addresses that satisfy the addressing-mode requirements of the target instruction set, so that generated tests can exercise code without triggering spurious memory faults.

Origin

The foundational reference is the IEEE Transactions on Software Engineering paper:

R.A. DeMilli, A. Jefferson Offutt. "Constraint-based automatic test data generation." IEEE Transactions on Software Engineering. 1991;17(9):900-910. doi:10.1109/32.92910.

This work introduced the constraint-satisfaction framing of the test data generation problem.

Application to Test Program Generation

The approach was instantiated in IBM's Model-Based Test-Generator, which embeds a generic constraint-solving algorithm for address generation. Key characteristics reported in the literature:

  • A framework and algorithm that accepts plug-in models of new addressing modes, allowing the tool to be extended to additional instruction sets.
  • Support for complex addressing modes of the PowerPC, x86, and other architectures.
  • Use as the central memory-access-generation mechanism inside an automatic test generation pipeline.

The NP-completeness of general constraint satisfaction is acknowledged via the classical reference:

M. R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. 1979.

Practical Considerations

  • Flexibility — because the algorithm is parameterized by addressing-mode models, new architectures can be added without rewriting the solver core.
  • Generality — the same framework can be reused wherever memory accesses must be generated that obey a target's addressing rules.
  • Complexity — solving the underlying constraint problems can be NP-complete in the general case.

Related Work

The technique intersects with AI-based approaches to test automation, e.g., Laurence Moseley, "Innovative applications of artificial intelligence 4," Engineering Applications of Artificial Intelligence, 1994;7(1):85-86, doi:10.1016/0952-1976(94)90047-7.

See Also

LINKED ENTITIES

1 links
Constraint satisfaction for test program generation MENTIONS

CITATIONS

5 sources
5 citations
[1] Constraint-based automatic test data generation was introduced by DeMilli and Offutt in IEEE TSE 1991 (17(9):900-910). Constraint-based automatic test data generation
[2] A framework and algorithm for address constraint satisfaction was implemented in the Model-Based Test-Generator at IBM Research - Haifa. Constraint satisfaction for test program generation
[3] The algorithm handles complex addressing modes in PowerPC, x86, and other architectures. Constraint satisfaction for test program generation
[4] The framework is generic and allows flexibility in modeling new addressing modes for memory access generation. Constraint satisfaction for test program generation
[5] Constraint satisfaction is an NP-complete problem in the general case (Garey and Johnson, 1979). Constraint satisfaction for test program generation