Automatic Test Program Generation
Overview
Automatic test program generation is the automated construction of test programs (and their expected behaviors) for a design under test (DUT), commonly a microprocessor or other computing device. It is typically cast as a constraint satisfaction problem (CSP) so that the generator can systematically produce test cases that satisfy user-specified verification goals rather than relying on hand-written test suites.
The approach described in the cited patent uses an extended form of conditional constraint satisfaction called an Extended Conditional Constraint Satisfaction Problem (ECondCSP) to drive the generator. The generator consumes a micro-architectural model of the DUT and a user request describing the micro-architectural events that must be exercised, and emits random test programs together with a description of the expected DUT behavior for each test. [1]
Background: From CSP to CondCSP
A classical CSP specifies a task by a set of variables, their domains, and constraints that restrict valid combinations of values; a solution assigns each variable a domain value such that all constraints are satisfied. [2]
Mittal and Falkenhainer generalized CSP into Conditional CSP (CondCSP), in which each variable may be either active or inactive. A CondCSP comprises a set of variables V, a set of domains D, a non-empty set of initial variables VI, a set of compatibility constraints CC, and a set of activity constraints CA. A variable is assigned a value only if it is active; a compatibility constraint is active only if all of its variables are active; and an activity constraint of the form c_act → v activates variable v when the left-hand constraint c holds (with a complementary "require not" form c_rn → v for deactivation). A solution is a value assignment to all active variables satisfying all active compatibility constraints and all activity constraints. [2]
Limitations of CondCSP for Test Generation
The CondCSP framework has distinct limitations when large portions of the problem are conditional. In such cases the set of constraints becomes large and complicated, increasing the probability of modeling errors. Test program generation, when represented as a CondCSP, has several unique characteristics, and there is strong motivation for compact modeling of highly complex automatic test generation problems. [3]
ECondCSP: Extended Conditional Constraint Satisfaction
Disclosed embodiments introduce an extension of the CondCSP representation scheme that represents conditional constraints in a way that remains meaningful even when some of the variables they reference are inactive. This representation, termed ECondCSP, enables compact representation of highly complex problems, reducing modeling labor and decreasing the chance of mistakes. [3]
Two main elements are provided:
- A novel language that enables users of CSP solvers to construct ECondCSPs simply and compactly. [3]
- An automatic parsing method that turns ECondCSP constraints into conventional CondCSP constraints solvable by existing CSP solvers. In other embodiments the ECondCSP is solved directly without conversion. [3]
ECondCSP constraints attach semantics to variables together with activation requirements. A constraint in an ECondCSP is satisfied when either (a) none of the activation requirements hold (the constraint is trivially satisfied) or (b) one activation requirement holds and its corresponding preserved semantics are satisfied; if one activation requirement evaluates to true, the activation requirements of all other elements must evaluate to false. [1]
Method for Generating Test Programs Using ECondCSP
In an embodiment, a method for automatically generating test programs includes: [3]
- Receiving a description of a system under test, expressed in terms of variables associated with the system and conditional constraints including semantics applied to the variables.
- Receiving a definition of an event to be tested in the system.
- Generating an ECondCSP over the variables responsively to the definition of the event and to the conditional constraints, such that at least some of the semantics of the conditional constraints are preserved in the ECondCSP when one or more of the variables to which the semantics are applied are inactive.
- Solving the ECondCSP to generate a test case for the system.
In a disclosed embodiment, the system description is a model of a processor and the generated test case is a test program for that processor. [4]
In another embodiment, generating the test case also generates an expected system behavior in response to the event, and the system is tested against this expected behavior using the test case. [4]
Solving the ECondCSP can produce a plurality of test cases, each corresponding to one of a plurality of solutions of the ECondCSP. [4]
In one disclosed embodiment, solving the ECondCSP is performed by transforming the ECondCSP to a CondCSP and then solving the CondCSP using a CondCSP solver. [4]
Apparatus and Software Embodiments
The patent also discloses apparatus for automatic test program generation, comprising a test generator that receives the system description and the user-defined event, generates the ECondCSP, and solves it to generate a test case, with at least some constraint semantics preserved when one or more of the relevant variables are inactive. [5]
A related apparatus for modeling a system uses a CSP processing module to characterize the system in terms of variables and conditional constraints with semantics applied to the variables, to define an ECondCSP whose semantics are preserved when relevant variables are inactive, and to solve the ECondCSP to model an aspect of the system. [5]
Computer software products are likewise disclosed, in which program instructions on a computer-readable medium cause a computer to perform the test-generation or modeling methods described above. [5]
Architecture of a Test Generator
A test generator (referred to as test generator 20 in the patent) generates a set of test programs as part of a verification plan for the DUT. It receives as input a micro-architectural model of the DUT, which includes models of hardware building blocks and mechanisms (e.g., pipeline stages and queues) and the logical connections between them, and a user request describing the micro-architectural events that require testing. An example event is two instructions at specific pipe stages that generate simultaneous exceptions. [1]
The test generator comprises a CSP processing module consisting of an ECondCSP builder and a CondCSP solver. The micro-architectural model and the user request are converted to an ECondCSP. The ECondCSP builder generates an ECondCSP that represents the DUT's micro-architectural model and the user request as variables and constraints. The modeling language used by the builder generates constraints that describe the building blocks and mechanisms of the DUT, as well as relationships between attributes of these building blocks. [1]
The ECondCSP builder then transforms the ECondCSP into an equivalent CondCSP, and the CondCSP solver solves this model. The outputs are a set of random test programs that cover the events required for testing, and a micro-architectural behavior describing the expected DUT behavior under these tests. [1]
The patent notes that although the disclosed embodiments relate specifically to automatic test-program generation, the principles may be applied to modeling a wide range of target systems that can be expressed in terms of complex conditional constraint satisfaction problems. [1]
Operator Semantics and Constraint Composition
In embodiments where conditional constraints contain atomic constraints linked by logical operators, defining the ECondCSP includes accepting one or more operator semantics tables for the logical operators and parsing the conditional constraints using these tables. An operator semantics table accepts a list of operands of the logical operator and a corresponding definition of preserved semantics for each activity/inactivity status combination of the operands, and may define at least one output of the logical operator to be returned when one or more operands are inactive, as well as identifying combinations for which no semantics are preserved. [4]
Parsing each conditional constraint produces a parse tree in which atomic constraints are assigned to leaves and logical operators are assigned to internal nodes, with each operator linking the lower-level constraints below its node. Merging the parse tree into the ECondCSP constraint involves traversing it in depth-first order and, at each node, generating a combined activation requirement and combined preserved semantics from the lower-level constraints and the operator semantics tables of the logical operators. A default definition of preserved semantics may also be used. [4]
Practical Implementation
The inventors implemented an automatic test-program generator based on the disclosed embodiments in the Piparazzi test generator (described by Adir et al.). Piparazzi uses the ECondCSP builder as a modeling tool for building complex microprocessor models and test cases that include activation requirements on some of the variables, and then solves the resulting ECondCSP to produce a set of random test programs that are applied to the tested DUT. [1]
Related Concepts
- Micro-architectural Model: The DUT description consumed by the test generator, comprising models of hardware building blocks (such as pipeline stages and queues) and the logical connections between them.
- Micro-architectural Event: A user-defined verification target (for example, two instructions at specific pipe stages that generate simultaneous exceptions), used to drive test generation.
- Extended Conditional Constraint Satisfaction Problem (ECondCSP): The constraint representation used to drive the generator, extending CondCSP with semantics that remain meaningful when referenced variables are inactive.