Directed-Logical Testing for Functional Verification of Microprocessors

The length of the microprocessor development cycle is largely determined by functional verification, where contemporary practice relies primarily on constraint-based random stimulus generation to drive a simulation-based methodology. However, formal methods are, in particular, gaining wider adoption and are seen as having potential to bridge large gaps left by current techniques. And many gaps still remain. In this paper we propose directed- logical testing: a new method of stimulus generation based on purely logical techniques (i.e. formal methods). As far as we know, our methodology represents the first end-to-end mathematical formalization of the stimulus generation problem. Therefore, a major contribution of this paper is the definition of a class of logical propositions that relate the actual microprocessor implementation, the assembly program stimulus, and a coverage goal. These propositions are given in rewriting logic, and use the idea of rewriting semantics to automatically formalize within a common logical framework the microprocessor implementation and assembly programs. To solve these propositions, we demonstrate how narrowing and user-defined narrowing strategies can be used as a scalable logical framework. In addition, we describe two classes of effective strategies that can be used for many microprocessors and common coverage goals. Finally, we describe a prototype tool implementation and present empirical data to demonstrate the feasibility of our methodology. Since narrowing and user-defined narrowing strategies within rewriting logic do not yet have tool support, our prototype tool uses standard rewriting and user-defined rewriting strategies to simulate narrowing.