U.S. Department of Transportation
Federal Highway Administration
1200 New Jersey Avenue, SE
Washington, DC 20590
Federal Highway Administration Research and Technology
Coordinating, Developing, and Delivering Highway Transportation Innovations
|This report is an archived publication and may contain dated technical, contact, and link information|
Publication Number: FHWA-RD-04-080
Date: September 2004
Software Reliability: A Federal Highway Administration Preliminary Handbook
PDF Version (697 KB)
PDF files can be viewed with the Acrobat® Reader®
Chapter 1: Introduction
Scope and Purpose of This Handbook
The overall objective of this handbook is to provide a reference to aid highway engineers, software developers, and project managers in software verification and validation (V&V), and in producing reliable software. Specifically, the handbook:
Current Status: The scope of the project to produce this handbook was not large enough to address many of the problems involving software that were uncovered along the way. A decision was made to concentrate on wrapping and estimating numerical errors, because these seemed important, widely applicable, not adequately addressed in the available literature, and tractable.
Intended Audience: Some mathematical and computer programming experience is assumed, especially the chapters relating to informal proofs, scale up, and estimation of numerical errors.
The Need for Software V&V in Highway Engineering
Software development is a relatively new activity used by an ancient profession. Construction and roadway engineering began in prehistoric times, and over time, the industry has raised the standards in design, construction, practice documentation. Through modernizing and improving design, construction, and maintenance, new approaches and technologies have been incorporated into civil engineering practice.
Many of the new tools and technologies initially did not achieve the levels of reliability and standardization that the civil engineering profession demanded; software development and computer programs fall into this category.
Software planning and development should emulate construction project planning, design, and construction, integrating testing and evaluation. The end result will be more reliable software and transportation systems.
Software developers must use tools to improve software and catch design problems at an early stage of the software development life cycle, when fixing these problems is relatively inexpensive and easy. These tools must be easy to use for both the software designer and for the software developer, and not just for those with unusual mathematical training.
In traditional software engineering, developers claim that testing is an integral part of the design and development process. However, as programming techniques become more advanced and complex, there is little consensus on what testing is necessary or how to perform it. Furthermore, many of the procedures that have been developed for V&V are so poorly documented that only the originator can reproduce the procedures. The complexity and uncertainty of these procedures has led to the inadequate testing of software systems (even operational systems). As software becomes more complex, it becomes more difficult to produce correct software, and the penalties for errors will increase.
Definitions of Correctness Criteria
V&V is the traditional terminology for the process of ensuring that software performs as required for its intended task. Verification is the process of checking that the software meets its specifications, i.e., that the software was built correctly. Validation is the process of checking that the software performs properly when used, i.e., that the correct software was built.
The V&V approach to software correctness assumes that good specifications exist. As discussed below, specifications for highway software often evolve over time. Therefore, this handbook has expanded the traditional concept of V&V to include the preparation, maintenance, and use of good specifications. Software reliability is "the probability of failure-free operation of a computer program for a specified time in a specified environment."(1)
The study of software reliability often emphasizes predicting software failures. As Leveson observes, not all failures are important for software safety.(2) In addition, predicting failures is less important than finding and fixing failures. For these reasons, predicting failure as an end in itself will not be emphasized in this handbook.
Software correctness is a set of criteria that defines when software is suitable for engineering applications that:(3)
Software correctness is a broad definition of what it means for software to perform correctly. Because it emphasizes accuracy, safety, and acceptable operation of a system containing software, software correctness is a useful concept by which to judge highway-related software.
Overview of V&V Techniques
Categories of V&V Techniques
In an extensive catalog of V&V techniques, Wallace et al. divide V&V techniques into three categories.(4)
Important Techniques for Highway Software
Here are short definitions of some V&V techniques that are important for use on highway software. These techniques are discussed more extensively in later chapters of the handbook.
Wrapping: The inclusion of code that checks a software module in the module itself, and reports success or failure to the module caller. To make wrapping practical for engineering problems, a simple form of executable specifications has been developed, along with software for executing the specifications.
Informal Proofs: Mathematical proofs at about the level of rigor of engineering applications of calculus. These proofs establish mathematical properties of the abstract algorithm expressed by a computer program.
Numerical Error Estimation: A technique is provided for estimating the numerical error in a computation due to measurement errors of the inputs, numerical instabilities, and roundoff errors during the computation.
In choosing methods to highlight in the handbook, the goal has been to improve current practice. Therefore, techniques that are in widespread current use, such as dataflow diagrams, have not been included. Another reason for leaving out many of the static techniques is that, in contrast to practice in other engineering fields, the static methods do not examine the final work product with either theory or experiment.
In addition, methods for which writing the specifications in a formal specification language is at least as difficult as writing the software itself have been excluded, because these methods are judged to be too expensive, too error-prone, and too foreign to current practitioners to be practical.
Special V&V Requirements of Highway Engineering Software
Applying traditional software V&V techniques to highway software is particularly difficult because the specifications for that software are usually complex and incomplete. This is because software like CORSIM (a tool that simulates traffic and traffic control conditions on combined surface streets and freeway networks) models real-world systems that have complex, often conflicting requirements placed on them. In addition, the long life and wide application of some highway software means that the original software specifications cannot anticipate all the tasks the software will be asked to perform during its lifetime. The traditional specify-develop-validate life cycle is not completely practical in the real world. Accordingly, the techniques presented in this handbook are designed to fit into a real-world situation in which a program and its specifications evolve over time. The wrapping technique and accompanying SpecChekTM tool have been provided to meet this need.
Correctness of Numerical Computations
Many complex numerical computations occur in highway engineering, such as large finite-element calculations and complex simulations. These large calculations use numerical algorithms such as matrix inversion, numerical integration, and relaxation solution of differential equations that are known to generate errors. Numerical errors and instabilities due to the finite precision of computer arithmetic are hard to detect if they occur deep in these computations. Therefore, a method for computing an approximate error along with numerical results has been developed so that error estimates can be pushed through a computation. Using this method, it is possible to determine whether a numerical calculation contains numerical errors.
Safety Critical Software Applications
Many software applications in highway engineering are safety critical. Some highway software, such as collision avoidance software in intelligent transportation systems (ITS), will be run millions of times under a wide variety of conditions. If a bug exists, these conditions are likely to expose it. Consequently, a very high standard of software reliability is required for safety-critical highway software.
Organization of Handbook
Chapter 1, "Introduction" (this chapter) introduces V&V terminology, discusses the special problems of V&V for highway software, and outlines handbook contents.
Chapter 2, "Testing," discusses what is learned about software from testing, criteria for choosing test cases, and practical testing limitations.
Chapter 3, "Safe Introduction of Software Using Scale Up," explains how software can be introduced in its environment using scale up.
Chapter 4, "Informal Proofs," defines a framework for informal proofs about programs, introduces proof techniques for informal proofs, and discusses applications. It contains simple examples of informal proofs and lists their limitations.
Chapter 5, "Wrapping," explains how verification code within a program can make the program self-testing, documents how to use executable specifications to implement wrapping for highway software and discusses a sample highway application. It outlines the benefits and limitations to wrapping.
Chapter 6, "Estimating Numerical Errors," explains a method for computing the expected numerical errors in a numerical computation.
Chapter 7, "Information Sources and Tools," lists some of the most important sources of information about V&V and some available tools that can help achieve software correctness.