Formal Verification of Hardware Components in Critical Systems

Abstract EN

Hardware components, such as memory and arithmetic units, are integral part of every computer-controlled system, for example, Unmanned Aerial Vehicles (UAVs).

The fundamental requirement of these hardware components is that they must behave as desired; otherwise, the whole system built upon them may fail.

To determine whether or not a component is behaving adequately, the desired behaviour of the component is often specified in the Boolean algebra.

Boolean algebra is one of the most widely used mathematical tools to analyse hardware components represented at gate level using Boolean functions.

To ensure reliable computer-controlled system design, simulation and testing methods are commonly used to detect faults; however, such methods do not ensure absence of faults.

In critical systems’ design, such as UAVs, the simulation-based techniques are often augmented with mathematical tools and techniques to prove stronger properties, for example, absence of faults, in the early stages of the system design.

In this paper, we define a lightweight mathematical framework in computer-based theorem prover Coq for describing and reasoning about Boolean algebra and hardware components (logic circuits) modelled as Boolean functions.

To demonstrate the usefulness of the framework, we (1) define and prove the correctness of principle of duality mechanically using a computer tool and all basic theorems of Boolean algebra, (2) formally define the algebraic manipulation (step-by-step procedure of proving functional equivalence of functions) used in Boolean function simplification, and (3) verify functional correctness and reliability properties of two hardware components.

The major advantage of using mechanical theorem provers is that the correctness of all definitions and proofs can be checked mechanically using the type checker and proof checker facilities of the proof assistant Coq.