Number SRI-CSL-93-7.
Computer Science Laboratory, SRI International, Menlo Park, CA.
December, 1993.

This report was prepared to supplement a forthcoming chapter on formal methods in the FAA Digital Systems Validation Handbook. Its purpose is to outline the technical basis for formal methods in computer science, to explain the use of formal methods in the specification and verification of software and hardware requirements, designs, and implementations, to identify the benefits, weaknesses, and difficulties in applying these methods to digital systems used in critical applications, and to suggest factors for consideration when formal methods are offered in support of certification.

The report assumes a serious interest in the engineering of critical systems, and a willingness to read occasional mathematical formulas and specialized terminology, but assumes no special background in formal logic or mathematical specification techniques. (An appendix provides a rapid introduction to formal logic for those to whom this topic is new.) The discussion should be accessible to most people with an engineering background. It may also be of use to those who develop or advocate formal methods and are interested in their use in support of certification for critical systems.

The particular focus of this report is computer systems used on-board aircraft. Some background on these systems is provided so that those concerned with critical computer systems in other contexts may be able to reinterpret the airplane-specific material to suit their own field.

@techreport{Rushby93:FAA,
    AUTHOR = {John Rushby},
    TITLE = {Formal Methods and the Certification of Critical Systems},
    INSTITUTION = {Computer Science Laboratory, {SRI} International},
    YEAR = {1993},
    NUMBER = {{SRI-CSL-93-7}},
    ADDRESS = {Menlo Park, {CA}},
    MONTH = {dec},
    NOTE = {Also issued under the title "Formal Methods and Digital Systems Validation for Airborne Systems" as {NASA} Contractor Report 4551, December 1993.},
    URL = {http://www.csl.sri.com/papers/csl-93-7/}
}

• csl-93-7.dvi.gz
• csl-93-7.ps.gz