• Federal Highway Administration >
• Publications >
• Research Publications >
• 04080 >
• 01.Cfm >
• Software Reliability: A Federal Highway Administration Preliminary Handbook

Software Reliability: A Federal Highway Administration Preliminary Handbook

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:

• Demonstrates the need for V&V of highway-related software.
• Introduces the important software V&V concepts.
• Defines the special V&V problems for highway-related software.
• Provides a reference to several new software V&V techniques developed under this and earlier related projects to address the special needs of highway-related software:
  • Wrapping, i.e., the use of embedded code to make a program self-verifying.
  • SpecChek^TM, a V&V tool to check software with its specifications.
  • Real-time computation of roundoff and other numerical errors.
  • Phased introduction of new software to minimize failures.
• Helps highway engineers, software developers, and project managers integrate software V&V into the development of new software and retrofit V&V into existing software.

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)

• Compute accurate results.
• Operate safely, and cause the system that contains the software to operate safely.
• Perform the tasks required by the system that contains the software, as explained in the software specifications.
• Achieve these goals for all inputs.
• Recognize inputs outside the domain.

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)

• Static analysis techniques are "those which directly analyze the form and structure of a product without executing the product. Reviews, inspections, audits, and data flow analysis are examples of static analysis techniques."
• Dynamic analysis techniques "involve execution, or simulation, of a development activity product to detect errors by analyzing the response of a product to sets of input data. Testing is the most frequent dynamic analysis technique."
• Formal analysis (or formal methods) "is the use of rigorous mathematical techniques to analyze the algorithms of a solution. Sometimes the software requirements may be written in a formal specification language (e.g., Z (see The World Wide Web Virtual Library: the Z Notation http://vl.zuser.org) which can be verified using a formal analysis technique like proof-of-correctness."

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.

Testing: The process of experimentally verifying that a program operates correctly. It consists of:

1. Running a sample of input data through the target program.
2. Checking the output against the predicted output.

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.

Excluded Techniques

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

Evolving Specifications

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 SpecChek^TM 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.

Table of Contents | Next