Current Trends In Hardware Verification And Automated Theorem Proving

This report describes the partially completed correctness proof of the Viper 'block model'. Viper [7,8,9,11,23] is a microprocessor designed by W. J. Cullyer, C. Pygott and J. Kershaw at the Royal Signals and Radar Establishment in Malvern, England, (henceforth 'RSRE') for use in safety-critical applications such as civil aviation and nuclear power plant control. It is currently finding uses in areas such as the de ployment of weapons from tactical aircraft. To support safety-critical applications, Viper has a particulary simple design about which it is relatively easy to reason using current techniques and models. The designers, who deserve much credit for the promotion of formal methods, intended from the start that Viper be formally verified. Their idea was to model Viper in a sequence of decreasingly abstract levels, each of which concentrated on some aspect ofthe design, such as the flow ofcontrol, the processingofinstructions, and so on. That is, each model would be a specification of the next (less abstract) model, and an implementation of the previous model (if any). The verification effort would then be simplified by being structured according to the sequence of abstraction levels. These models (or levels) of description were characterized by the design team. The first two levels, and part of the third, were written by them in a logical language amenable to reasoning and proof.

This volume constitutes the refereed proceedings of the 1993 Higher-Order Logic User's Group Workshop, held at the University of British Columbia in August 1993. The workshop was sponsored by the Centre for Integrated Computer System Research. It was the sixth in the series of annual international workshops dedicated to the topic of Higher-Order Logic theorem proving, its usage in the HOL system, and its applications. The volume contains 40 papers, including an invited paper by David Parnas, McMaster University, Canada, entitled "Some theorems we should prove".

This volume contains the contributions presented at the International Workshop on Current Trends in Applied Formal Methods organized October 7-9, 1998, in Boppard, Germany. The main objective of the workshop was to draw a map of the key issues facing the practical application of formal methods in industry. This appears to be particularly timely with safety and security issues becoming a real obstacle to industrial software and hardware development. As a consequence, almost all major companies have now set up departments or groups to work with formal methods and many European countries face a severe labour shortage in this new field. Tony Hoare's prediction of the art of software (and hardware) development becoming a proper engineering science with its own body of tools and techniques is now becoming a reality. So the focus of this application oriented workshop was not so much on spe cial academic topics but rather on the many practical aspects of this emerging new technology: verification and validation, and tool support and integration into the software life-cycle. By evaluating the state of the art with respect to industrial applications a discussion emerged among scientists, practising engi neers, and members of regulatory and funding agencies about future needs and developments. This discussion lead to roadmaps with respect to the future of this field, to tool support, and potential application areas and promising market segments. The contributions of the participants from industry as well as from the respective national security bureaus were particularly valuable and highly appreciated.

We are invited to deal with mathematical activity in a sys tematic way [ ... ] one does expect and look for pleasant surprises in this requirement of a novel combination of psy chology, logic, mathematics and technology. Hao Wang, 1970, quoted from(Wang, 1970). The field of mathematics has been a key application area for automated theorem proving from the start, in fact the very first automatically found the orem was that the sum of two even numbers is even (Davis, 1983). The field of automated deduction has witnessed considerable progress and in the last decade, automated deduction methods have made their way into many areas of research and product development in computer science. For instance, deduction systems are increasingly used in software and hardware verification to ensure the correctness of computer hardware and computer programs with respect to a given specification. Logic programming, while still falling somewhat short of its expectations, is now widely used, deduc tive databases are well-developed and logic-based description and analysis of hard-and software is commonplace today.

This book constitutes the proceedings of the 8th International Conference on Higher Order Logic Theorem Proving and Its Applications, held in Aspen Grove, Utah, USA in September 1995. The 26 papers selected by the program committee for inclusion in this volume document the advances in the field achieved since the predecessor conference. The papers presented fall into three general categories: representation of formalisms in higher order logic; applications of mechanized higher order logic; and enhancements to the HOL and other theorem proving systems.

This book constitutes the refereed proceedings of the 12th International Conference on Theorem Proving in Higher Order Logics, TPHOLs '99, held in Nice, France, in September 1999. The 20 revised full papers presented together with three invited contributions were carefully reviewed and selected from 35 papers submitted. All current aspects of higher order theorem proving, formal verification, and specification are discussed. Among the theorem provers evaluated are COQ, HOL, Isabelle, Isabelle/ZF, and OpenMath.

The HOL system is a higher order logic theorem proving system implemented at Edinburgh University, Cambridge University and INRIA. Its many applications, from the verification of hardware designs at all levels to the verification of programs and communication protocols are considered in depth in this volume. Other systems based on higher order logic, namely Nuprl and LAMBDA are also discussed. Features given particular consideration are: novel developments in higher order logic and its implementations in HOL; formal design and verification methodologies for hardware and software; public domain availability of the HOL system. Papers addressing these issues have been divided as follows: Mathematical Logic; Induction; General Modelling and Proofs; Formalizing and Modelling of Automata; Program Verification; Hardware Description Language Semantics; Hardware Verification Methodologies; Simulation in Higher Order Logic; Extended Uses of Higher Order Logic. Academic and industrial researchers involved in formal hardware and software design and verification methods should find the publication especially interesting and it is hoped it will also provide a useful reference tool for those working at software institutes and within the electronics industries.

These proceedings contain the papers presented at a workshop on Designing Correct Circuits, jointly organised by the Universities of Oxford and Glasgow, and held in Oxford on 26-28 September 1990. There is a growing interest in the application to hardware design of the techniques of software engineering. As the complexity of hardware systems grows, and as the cost both in money and time of making design errors becomes more apparent, so there is an eagerness to build on the success of mathematical techniques in program develop ment. The harsher constraints on hardware designers mean both that there is a greater need for good abstractions and rigorous assurances of the trustworthyness of designs, and also that there is greater reason to expect that these benefits can be realised. The papers presented at this workshop consider the application of mathematics to hardware design at several different levels of abstraction. At the lowest level of this spectrum, Zhou and Hoare show how to describe and reason about synchronous switching circuits using UNilY, a formalism that was developed for reasoning about parallel programs. Aagaard and Leeser use standard mathematical tech niques to prove correct their implementation of an algorithm for Boolean simplification. The circuits generated by their formal synthesis system are thus correct by construction. Thuau and Pilaud show how the declarative language LUSTRE, which was designed for program ming real-time systems, can be used to specify synchronous circuits.