Address Constraint Satisfaction

Overview

Address Constraint Satisfaction is a technique used in automatic test program generation. It addresses the central problem of solving constraints for memory access generation by providing a generic algorithmic framework that decides how generated memory accesses should be resolved against architectural addressing rules. The technique was introduced by Lewin, Fournier, Levinger, Roytman, and Shurek at IBM Research - Haifa in their 2002 paper "Constraint satisfaction for test program generation."

Motivation

Automatic test program generators must produce instruction sequences that perform memory accesses through architectures' addressing modes. Because each architecture defines complex rules for how effective addresses are computed (base registers, index registers, scaling factors, displacements, segment selectors, and so on), the generator must enforce those rules while still producing tests that exercise specific memory locations. The paper frames this problem explicitly as a constraint satisfaction problem, drawing on prior work such as constraint-based automatic test data generation.

Implementation: Model-Based Test-Generator (MBTG)

The algorithm was implemented in the Model-Based Test-Generator (MBTG). MBTG is a tool for automatic test generation; the algorithm embedded in it uses a generic model of addressing so that new addressing modes can be added flexibly without rewriting the core engine. The MBTG implementation is the canonical reference implementation of Address Constraint Satisfaction.

Supported Architectures and Addressing Modes

The technique handles complex addressing modes, including those defined for:

• PowerPC Architecture — addressing modes used by PowerPC instructions.
• x86 Architecture — addressing modes used by x86 instructions, including segment-prefixed and scaled-index forms.
• Other architectures — the generic model is intended to allow extension to additional instruction set architectures beyond PowerPC and x86.

Algorithmic Approach

The Address Constraint Satisfaction algorithm solves the constraints produced by memory access generation requests. Because constraint satisfaction in this form is, in general, related to NP-hard problems (cf. Garey and Johnson, Computers and Intractability), the paper treats it as a constraint-solving framework rather than a single fixed procedure, and the generic model allows the underlying solver strategy to be adapted to the addressing mode being modeled.

Related Work

The technique builds on prior constraint-based test data generation, in particular DeMilli and Offutt's "Constraint-based automatic test data generation" (IEEE TSE, 1991). The application of AI techniques to software engineering contexts (Moseley, 1994) provides additional background.

Applications

Address Constraint Satisfaction is used wherever automatic test generators must produce instruction sequences that perform valid memory accesses across diverse instruction set architectures, particularly within IBM's Model-Based Test-Generator for PowerPC and x86 verification.

See Also

• Constraint satisfaction for test program generation — the originating paper.
• Model-Based Test-Generator (MBTG) — the implementing tool.
• Complex Addressing Modes — the concept used.
• PowerPC Architecture — an architecture supported.
• x86 Architecture — an architecture supported.