An Integrated Approach to Verifying Large Circuits : A Case Study

Through the use of compositionality and abstraction, it is possible to extend automatic model checking techniques so that large circuits can be verified. This paper presents a case study verification of Benchmark 22 of the IFIP WG10.5 Benchmark Suite for Hardware Verification (a systolic array multiplier containing 115 000 gates). Both the timing and functionality of the circuit are verified (a significant error was discovered in the original benchmark). This illustrates that an appropriate logical framework can support an efficient, integrated tool for verification that incorporates a number of different verification techniques. A specialised theorem prover implements a compositional theory based on symbolic trajectory evaluation (STE). STE, an efficient model checking technique that can support large state spaces because of its natural and easily used method of abstraction, provides the underlying computational engine. The rest of the compositional theory allows a human verifier to use knowledge of the structure of the circuit to overcome some of the computational limitations of model checking. Using STE with its compositional theory, large circuits can be verified in detail using reasonable computational resources.