The VIPER microprocessor chip is one of the results of a research program on high-integrity computing being carried out at the Royal Signals and Radar Establishment at Malvern, England. RSRE (which is a research station belonging to the British Ministry of Defence) has been developing formal methods of specifying and analysing software for some 15 years, but only in 1983 did we begin to look at the equally challenging problem of computer hardware. Correctness of computer hardware has only become an issue because of the pressure from computer users (civil and military) to put programmable electronics into ever more critical systems. The medical, automotive, and avionic communities now all use general purpose microprocessors in systems which could place the lives of their customers at risk, and the threshold is constantly being pushed higher: computer control offers so many advantages in cost, performance, and flexibility that its temptations are rarely resistible. Conventional microprocessor chips, however, are neither well enough specified nor accurately enough implemented for life-critical (or securitycritical) applications. Every month sees another press report of problems in widely-used devices. VIPER, like the FM8501 and 8502, was born of the need for a microprocessor with a precise, formal, specification, the highest possible assurance that the physical device conforms to it, and the special characteristics needed for high-integrity applications. Computational Logic Incorporated were commissioned by NASA to review the work on VIPER, under a long-standing framework for collaboration in aerospace research between NASA and the Royal Aerospace Establishment in Britain. Information on VIPER was supplied by ourselves and by Marconi Electronic Devices Ltd. VIPER was developed in response to a number of UK military requirements. We made an early decision (in 1984) to fabricate chips as a demonstration of what could be done, and therefore limited ourselves to technologies which offered a reasonably quick route to silicon. Gordon's LCF-LSM system (which has now matured into HOL, see the references at the end of the report) was the obvious choice, since a full account of it had been published with a tutorial example of hardware verification -a simple &bit machine now called "Tamarack." HOL is syntactically quite similar to the hardware description language ELLA, so we decided to live with an informal (though technically easy) step in the design process by changing languages in the middle. A strongly-typed language like HOL is a big help when writing a specific& tion (it detects a large proportion of errors) and a theorem prover for it is available. ELLA is an established HDL with a wealth of tools, some *This work was supported in part at Computational Logic, Inc. by NASA Langley Research Center through the Defense Advanced Research Projects Agency, ARPA Order 584155. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of Computational Logic, Inc., NASA, the Defense Advanced Research Projects Agency or the U S . Government. CH3033-8~91~0000-0091$01 .OO 0 1 9 9 1 IEEE 91 of which can r e h e a block-level description into a gate-level design with almost no human intervention. We changed at the point of least effort; the process could easily be mechanised though for a device as simple as VIPER this did not seem worth while. From the language change downwards, the VIPER design was fist verified by a process of "intelligent exhaustive simulation'' whose coverage depends on the set of test vectors applied. These vectors (which contain "don't cares" in profusion) are generated by the ELLA simulator from a hand-written program. Though we believe this method to be sound (it is in fact pessimistic: it rejects some correct circuits but should never accept a wrong one) it depends too much on human assiduity for comfort, so we have replaced it. The new technique, developed by Clive Pygott at RSRE and based on the work of R. E. Bryant, is called NODEN; it was used in August 1989 to repeat the low-level verification of the latest version of VIPER. This device (VIPER 1 A ) is designed to operate in pairs and has built-in comparators to check for address and data bus errors. The comparators have too many inputs for the NODEN analyser to check them, but the rest of the design was confirmed to be correct. The upper levels of the verification were done by Avra Cohn at the University of Cambridge, England, using the HOL Theorem Prover. The proof is not complete in a number of areas concerning the meaning of computer arithmetic; these points have been documented by Cohn herself and are commented on further in this report. We are confident from careful (but informal) argument, simulation, and testing of actual chips that the implementation is correct, but as Fetzer[l2] and others have pointed out it is not justified in strictly mathematical terms to claim a "proof" of any physical device. Hardware, of any kind, is fundamentally different from computer software in that a truly formal proof (a "demonstration" in Fetzer's terms) of correctness is not possible. Physical devices wear out and break down, and no amount of formal logic can guarantee immunity: ultimately physics makes its own rules. With VIPER we have put almost as much effort into guarding against hardware breakdown (using parity bits, master/slave operation, built-in test, and self-testable logic) as into assuring correctness of the design. The two aspects are of course complementary, for most redundant systems are built round the assumption that the channels will fail independently. If there is a common design fault, they may all fail together. This report and Avra Cohn's work confirm our impression that more remains to be done, both to build up confidence in the existing VIPER design and to develop new techniques of design and verification which avoid the limitations of present methods. CLI themselves aremajor contributors to this field; in the UK we are sponsoring work on methods of refining a functional specification by correctness preserving transformations, so that the eventual gate-level design is "correct by construction." The f i s t test vehicle for this work will probably be a much faster (but upwards compatible) development of VIPER. At the silicon level, we are insuring against faults in the CAD software and manufacturing process (which are below the end-point of our verification work) by sponsoring a second, independent, gate-level design of the chip using a different technology. In the longer term we feel that a combination of methods will usually be needed to achieve the highest assurance. A design may be pronounced "correct by construction" by a faulty software tool; to guard against -9 2 proven to implement its top-level specification (the instruction interpreter). This is not a unique point of view; a recent paper by one of the Cambridge University consultants arrives at a similar conclusion [4]. Section 2 contains an informal description of the VIPER microprc+ cessor. The analysis of VIPER begins in Section 3 with an outline of the abstract layers used to specify VIPER. Section 4 covers each of the proofs, and attempted proofs of correspondence between the levels in the specification. A schematic block diagram of the contents of Sections 3 and 4 appears as Figure 1 . The conclusion contains a discussion of some of the broader issues in managing formal hardware verification projects, using the VIPER project as an example. Throughout the report we contrast the specification and verification approach used for VIPER with that used during the specification and verification of the FM8502 microprocessor [25] .
In REF "a few" errors in the specification are reported and two discussed in detail.
Report on the formal specification and partial verification of the VIPER microprocessor
COMPASS '91, Proceedings of the Sixth Annual Conference on Computer Assurance
COMPASS '91, Proceedings of the Sixth Annual Conference on Computer Assurance
Computer Science