Using an induction prover for verifying arithmetic circuits

We show that existing theorem proving technology can be used effectively for mechanically verifying a family of arithmetic circuits. A theorem prover implementing: (i) a decision procedure for quantifier-free Presburger arithmetic with uninterpreted function symbols; (ii) conditional rewriting; and (iii) heuristics for carefully selecting induction schemes from terminating recursive function definitions; and (iv) well integrated with backtracking, can automatically verify number-theoretic properties of parameterized and generic adders, multipliers and division circuits. This is illustrated using our theorem prover Rewrite Rule Laboratory (RRL). To our knowledge, this is the first such demonstration of the capabilities of a theorem prover mechanizing induction.

The above features of RRL are briefly discussed using illustrations from the verification of adder, multiplier and division circuits. Extensions to the prover likely to make it even more effective for hardware verification are discussed. Furthermore, it is believed that these results are scalable, and the proposed approach is likely to be effective for other arithmetic circuits as well.

Authors and Affiliations

1. Department of Computer Science, University of New Mexico, Albuquerque, NM 87131, USA; E-mail: kapur@cs.unm.edu, , , , , , US

   Deepak Kapur

2. Microprocessor Division, HAL Computer Systems, Fujitsu Inc., Campbell, CA 95014, USA; E-mail: subu@hal.com, , , , , , US

   Mahadevan Subramaniam

Reprints and permissions