Using a constraint satisfaction formulation and solution techniques for random test program generation

Automatic generation of test programs plays major role in the verification of modern processors and hardware systems. In this paper, we formulate the generation of test programs as a constraint satisfaction problem and develop techniques for dealing with the challenges we face, most notably: huge variable domains (e.g., magnitude of 264) and the need to randomly generate "well distributed" samplings of the solution space. We describe several applications of our method, which include specific test generators targeted at various parts of a design or stages of the verification process.