Automated polynomial formal verification using generalized binary decision diagram patterns

With the ongoing digitization, digital circuits have become increasingly present in everyday life. However, as circuits can be faulty, their verification poses a challenging but essential challenge. In contrast to formal verification techniques, simulation techniques fail to fully guarantee the correctness of a circuit. However, due to the exponential complexity of the verification problem, formal verification can fail due to time or space constraints. To overcome this challenge, recently <i>Polynomial Formal Verification</i> (PFV) has been introduced. Here, it has been shown that several circuits and circuit classes can be formally verified in polynomial time and space. In general, these proofs have to be conducted manually, requiring a lot of time. However, in recent research, a method for automated PFV has been proposed, where a proof engine automatically generates human-readable proofs that show the polynomial size of a <i>Binary Decision Diagram</i> (BDD) for a given function. The engine analyses the BDD and finds a pattern, which is then proven by induction. In this article, we formalize the previously presented BDD patterns and propose algorithms for the pattern detection, establishing new possibilities for the automated proof generation for more complex functions. Furthermore, we show an exemplary proof that can be generated using the presented methods.This article is part of the theme issue 'Emerging technologies for future secure computing platforms'.