Generating Tests by Exploiting Designed Behavior

Mark Harper ShirleyAAAI 1986

Introduction

As VLSI (Very Large Scale Integration) components grow in complexity, traditional test generation methods—relying on gate-level structural analysis and constraint propagation—face a computational explosion. Human experts, however, bypass this by reasoning about a device's intended function (e.g., "this is an ADD instruction"). This paper proposes automating this "teleological" reasoning to generate tests for complex datapaths efficiently.

The Designed-Behavior Hypothesis

The core of this approach is the Designed-Behavior Hypothesis: the state space of what a circuit can do (potential behavior) is massive, but the space of what it was designed to do is relatively small and manageable. By restricting the search to intended operational modes, test generation becomes tractable.

The hierarchy of circuit behaviors, highlighting how designed behavior is a small subset of all potential behaviors.

System Architecture

The proposed system automates test generation through three primary stages:

  1. Preprocessing: Using symbolic simulation, the system generates behavior graphs. Variables (e.g., ?Addend) represent data, creating a database of information flow during standard operations like a CPU's instruction set.
  2. Micro-planning: This stage matches specific testing goals (e.g., exercising an ALU function) against behavior graphs to identify high-level instructions that provide the necessary controllability and observability.
  3. Macro-planning: A best-first search identifies the sequence of operations required to set up register states and move results to observable output pins.

Evaluation: The MARK-2 Microprocessor

The system was evaluated using the MARK-2, a 16-bit horizontally microprogrammed processor. The circuit consists of 16 components and 91 nodes, featuring a sequencer with 80 lines of microcode and 23 instructions.

Schematic of the MARK-2 microprocessor, illustrating the complex datapath and control structures used for evaluation.

Key Results and Insights

The system generated prototype tests for the MARK-2 datapath in approximately one minute on a Symbolics 3640. While it successfully covered the entire datapath, it failed on the controller (sequencer and FSM). The authors argue this failure is a "feature," highlighting areas where the Designed-Behavior Hypothesis does not hold and signaling a need for "Design for Testability" (DFT) modifications.

Teleology as a Constraint

Knowing the "purpose" of a circuit provides a natural abstraction. If an input sequence doesn't correspond to a valid command, the planner ignores it, drastically reducing the search space. This "failing fast" allows engineers to identify untestable areas early in the design cycle.

Limitations and Future Work

The method currently struggles with the non-linear logic of control units and assumes a complete list of operations is provided. Furthermore, it relies on symbolic inversion of functions; extremely complex data transformations may still pose challenges. Future work suggests applying this method to other complex building blocks like UARTs and graphics controllers.

Conclusion

By exploiting designed behavior, this approach offers a powerful alternative to gate-level algorithms for complex VLSI datapaths. It provides a path toward faster test generation and early identification of untestable design regions, bridging the gap between human expertise and automated tools.

Summary updated

BibTeX
@inproceedings{shirley1986generating,
  author = {Mark Harper Shirley},
  title = {{Generating Tests by Exploiting Designed Behavior}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure