Industrial Applications of Formal Methods to Model, Design and Analyze Computer Systems

Formal methods are mathematically-based techniques, often supported by reasoning tools, that can offer a rigorous and effective way to model, design and analyze computer systems. The purpose of this study is to evaluate international industrial experience in using formal methods. The cases selected are representative of industrial-grade projects and span a variety of application domains. The study had three main objectives:

· To better inform deliberations within industry and government on standards and regulations;
· To provide an authoritative record on the practical experience of formal methods to date; and

À To suggest areas where future research and technology development are needed.

This study was undertaken by three experts in formal methods and software engineering: Dan Craigen of ORA Canada, Susan Gerhart of Applied Formal Methods, and Ted Ralston of Ralston Research Associates. Robin Bloomfield of Adelard was involved with the Darlington Nuclear Generating Station Shutdown System case.

Support for this study was provided by organizations in Canada and the United States. The Atomic Energy Control Board of Canada (AECB) provided support for Dan Craigen and for the technical editing provided by Karen Summerskill. The U.S. Naval Research Laboratories (NRL), Washington, DC, provided support for all three authors. The U.S. National Institute of Standards and Technology (NIST) provided support for Ted Ralston.

Inhalt

Volume 1 Purpose, Approach, Analysis, and Conclusions

1. An International Survey of Industrial Applications of Formal Methods
   Introduction
2. Formal Methods
   2.1 An Historical Perspective
   2.2 What is Formal Methods?
   2.3 What are the Limits of Formal Methods?
   2.4 Specific Formal Methods
3. Case Summary
   3.1 Regulatory Cluster
   3.2 Commercial Cluster
   3.3 Exploratory Cluster
4. Methodology
   4.1 Areas of Interest
   4.2 Acquisition of Information
   4.3 Questionnaires
   4.4 Analytic Framework
   4.5 Cluster Analysis
5. Regulatory Cluster Analysis
   5.1 Introduction
   5.2 Cases
   5.3 Observations
   5.4 Analysis
6. Commercial Cluster Analysis
   6.1 Introduction
   6.2 Cases
   6.3 Observations
   6.4 Analysis
7. Exploratory Cluster Analysis
   7.1 Introduction
   7.2 Cases
   7.3 Observations
   7.4 Analysis
8. Key Events and Timing
   8.1 Starter
   8.2 Booster
   8.3 Current State
   8.4 Timing
9. Analysis of Formal MEthods R & D Summary
   9.1 Regulatory Cluster
   9.2 Commercial Cluster
   9.3 Overall Observations
10. Findings, Observations and Conclusions
    10.1 Maturing of Formal Methods
    10.2 Scale of Application
    10.3 Primary Uses of Formal Methods
    10.4 System Certification
    10.5 Tool Support
    10.6 Technology Transfer
    10.7 Formal Methods Skills are Building
    10.8 Code Level Application of Formal Methods
    10.9 Inadequate Cost Models
11. References
    Volume 2 Case Studies
12. Structured Systems Analysis and Design Method Toolset
    1.1 Case Description
    1.2 Interview Summary
    1.3 Evaluation
    1.4 Conclusions
13. IBM's Customer Information Control System
    2.1 Case Description
    2.2 Questionnaire 1
    2.3 Interview Summary
    2.4 Evaluation
    2.5 Conclusions
14. Cleanroom Software Methodology
    3.1 Case Description
    3.2 Interview Summary: IBM
    3.3 Interview Summary: NASA Goddard Center
    3.4 Evaluation
    3.5 Conclusions
15. Darlington: Trip Computer Software
    4.1 Case Description
    4.2 Interview Summary
    4.3 Evaluation
    4.4 Conclusions
16. LaCoS Esprit Project
    5.1 Case Description
    5.2 Questionnaire 1
    5.3 Interview Summary
    5.4 Evaluation
    5.5 Conclusions
17. Multinet Gateway
    6.1 Case Description
    6.2 Interview Summary
    6.3 Evaluation
    6.4 Conclusions
18. SACEM-A Railway Signalling System
    7.1 Case Description
    7.2 Questionnaire 1
    7.3 KVS
    7.4 CTDC Calcutta
    7.5 Interview Summary
    7.6 Evaluation
    7.7 Conclusions
19. NIST Token-Based Access Control System (TBACS)
    8.1 Case Description
    8.2 Questionnaire 1
    8.3 Interview Summary
    8.4 Evaluation
    8.5 Conclusions
20. Teltronix-Use of Z Method on Oscilloscopes
    9.1 Case Description
    9.2 Questionnaire 1
    9.3 Interview Summary
    9.4 Evaluation
    9.5 Conclusions
21. Traffic Alert and Collision Avoidance System (TCAS)
    10.1 Case Description
    10.2 Interview Summary
    10.3 Evaluation
    10.4 Conclusions
22. INMOS Transputer-Use of Formal Methods in Hardware Verification
    11.1 Case Description
    11.2 Interview Summary
    11.3 Evaluation
    11.4 Conclusions
23. Hewlett-Packard Medical Instruments Analytical Information Base (AIB) Component Monitoring System
    12.1 Case Description
    12.2 Interview Summary
    12.3 Evaluation
    Appendix A: Biographies of Authors
    Appendix B: Formal Methods Techniques
    B.1 Software Cost Reduction (SCR)
    B.2 B
    B.3 Cleanroom
    B.4 Formal Development Methodology (FDM)
    B.5 Gypsy Verification Environment
    B.6 Hoare Logic
    B.7 Hewlett-Packard Specification Language (HP-SL)
    B.8 OCCAM/Communicating Sequential Processes (CSP)
    B.9 RAISE
    B.10 TCAS Methodology
    B.11 Z
    Appendix C: Initial Questionnaire
    Appendix D: Questionnaire for Structured Interview
    Appendix E: Review Committee
    Appendix F: Acknowledgments