Automatic Test Program Generation

Definition

Automatic Test Program Generation (ATPG) refers to techniques that programmatically synthesize test programs—assemblies, instruction sequences, or source-level programs—from specifications, constraints, or seed inputs, in order to exercise a system under test (a hardware component, a compiler, or other software). The goal is to obtain broader, more targeted, or more cost-effective test coverage than is practical through hand-written test suites.

Two prominent application domains are:

Functional verification of microprocessors, where ATPG tools produce instruction sequences that exercise architectural features, often guided by an architecture description language (ADL) and constraint solvers.
Bug localization in Just-in-Time (JIT) compilers, where ATPG must produce paired passing and failing programs whose controlled similarity and divergence maximize the accuracy of downstream bug-localization techniques.

Microprocessor Verification (Specification-Driven ATPG)

A representative specification-driven ATPG tool is MA2TG, which uses an ADL-based architectural model together with constraint solving to generate test programs ranging from simple to complex instruction sequences. Its design makes three contributions (as reported in the MA2TG paper):

Simplified architectural modeling through an ADL specification, easing adoption and modification of the target architecture.
Constraint-directed generation of test programs using constraint-solving techniques, allowing users to specify targeted instruction sequences via a user constraints file.
Significant reductions in the number of generated test programs and overall verification time compared with purely random generation.

MA2TG was applied to the DLX processor as a demonstration of feasibility. Its placement in the literature—via citations to related ADL- and constraint-based generators such as EXPRESSION, AVPGEN, IBM's PowerPC generator, and graph-based pipelined-processor test generation—situates it within the broader line of work that uses ADLs and constraint satisfaction to bias test generation toward architecturally meaningful coverage.

Constraint Satisfaction Approaches

A foundational line of work treats test program generation as a constraint satisfaction problem. Two complementary efforts, both published in 2002 and both connected to IBM's verification program, illustrate this perspective:

Bin et al. (IBM Systems Journal, 2002) formulated random test program generation as a constraint satisfaction problem and developed solution techniques to bias the generator toward architectural coverage targets. This formulation is widely cited as a precedent for constraint-directed ATPG in industrial settings.
Lewin, Fournier, Levinger, Roytman, and Shurek (IBM Research - Haifa, 2002) focused specifically on memory access generation—one of the most intricate parts of constraint solving in test program synthesis—because complex addressing modes in modern instruction sets can produce combinatorial blow-up. They described a generic framework and algorithm, implemented in the Model-Based Test-Generator, that handles address constraint satisfaction for complex addressing modes in the PowerPC, x86, and other architectures. The framework's flexibility allows new addressing modes to be modeled without re-engineering the solver, making the approach adaptable to a variety of ISAs.

Together these efforts establish constraint satisfaction as a recurring methodological pillar of ATPG, appearing in both randomized generation (Bin et al.) and address-mode synthesis (Lewin et al.).

JIT Compiler Bug Localization (Directed ATPG)

A distinct sub-problem arises when ATPG is used to support bug localization in Just-in-Time (JIT) compilers. Bug-localization techniques typically rely on analyzing the execution behaviors of a JIT compiler across a corpus of test programs; the characteristics of those test inputs strongly affect localization accuracy.

Existing automatic test-program generation approaches have been observed to underperform for JIT bug localization. The approach in the cited arXiv paper addresses this with two guiding insights:

Generated test programs should include both passing inputs (which do not trigger the bug) and failing inputs (which do trigger the bug).
Passing inputs should be as similar as possible to the seed input, while failing inputs should be as different as possible from it.

To realize these insights, the technique performs structural analysis of the seed program to decide which parts of the code to mutate for each of the passing and failing cases. Experiments with a prototype implementation reported that the generated test inputs led to significantly improved bug-localization results compared with prior approaches.

Related Techniques and Tools

MA2TG — A functional test program generator for microprocessor verification based on ADL specifications and constraint solving.
Model-Based Test-Generator — A tool implementing a generic constraint-satisfaction framework for memory access generation across PowerPC, x86, and other architectures; the algorithm supports flexible modeling of new addressing modes.
EXPRESSION — An ADL used for retargetable compiler/simulator modeling that informs architecture-driven test generation.
Constraint-satisfaction-based random test program generation (Bin et al., IBM Systems Journal, 2002) — earlier precedent for using constraint solving to bias test-program synthesis.
AVPGEN and IBM's PowerPC verification generator — coverage- and bias-driven test-program generators for commercial microprocessor verification.
Graph-based functional test program generation for pipelined processors — an alternative modeling approach that uses graph representations of pipelines to drive test synthesis.

Key Characteristics

Specification- vs. seed-driven. Microprocessor ATPG is typically specification-driven (ADL + constraints), while JIT bug-localization ATPG is seed-driven (mutating a real program around a known bug).
Constraint-directed vs. mutation-based. MA2TG-style tools express desired test content as constraints and solve them; JIT bug-localization generators combine structural analysis with targeted mutation. Constraint-satisfaction solvers also underpin address-mode synthesis in tools such as the Model-Based Test-Generator.
Goal: coverage vs. goal: discrimination. Verification ATPG optimizes for architectural coverage and corner-case reachability; bug-localization ATPG optimizes for discriminative power between passing and failing executions.

References

Li, T., Zhu, D., Guo, Y., Liu, G., Li, S. MA2TG: A Functional Test Program Generator for Microprocessor Verification (2005).
Directed Test Program Generation for JIT Compiler Bug Localization, arXiv:2307.08885v1 (2023).
Lewin, D. R., Fournier, L. S., Levinger, M., Roytman, E., Shurek, G. Constraint satisfaction for test program generation (2002).
Wu, L.-M., Wang, K., Chiu, C.-Y. A BNF-based automatic test program generator for compatible microprocessor verification. ACM TODAES, 9(1):105–132, 2004.
Bin, E., Emek, R., Shurek, G., Ziv, A. Using a constraint satisfaction formulation and solution techniques for random test program generation. IBM Systems Journal, 41(3):386–402, 2002.
Chandra, A. K. et al. AVPGEN—A test generator for architecture verification. IEEE TVLSI, 3(2):188–200, 1995.
Aharon, A. et al. Test program generation for functional verification of PowerPC processors in IBM, 1995.
Mishra, P., Dutt, N. Graph-based functional test program generation for pipelined processors, DATE 2004.
Halambi, A. et al. EXPRESSION: a language for architecture exploration through compiler/simulator retargetability, DATE.