Acronym

16.1 Introduction to Formal Methods

Engineering as a whole relies heavily on mathematical models to make informed judgments about designs. However, software development has traditionally been less formal—maybe even ad hoc at times, with testing at the end of the project to confirm its goodness. The goal of formal methods is to bring the same mathematical basis used for other engineering disciplines to the digital world, to both software and programmable hardware. Formal methods apply logic and discrete mathematics to model “the behavior of a system and to formally verify that the system design and implementation satisfy functional and safety properties” [1].

Although I am not a formal methodist, I have been exposed to formal methods for over 15 years and have a great respect for both the technical discipline of formal methods and its incredible potential to improve the quality and safety of digital systems.

Formal methods have been advocated by academia for years. Some of the brightest, most educated, and most passionate people I know are formal methodists. They have been persistent in their research and pursuing their convictions. It is exciting to see that their hard work is starting to connect with applied engineering.

To date, formal methods have had more application in the electronic hardware world—primarily because the hardware tools are more standardized and stable, allowing formal methods to be rolled into the day-to-day activities of the engineers. Software tools and technology (such as requirements and design methodology, languages, target dependencies) are still changing rapidly. Software engineering hasn’t reached the level of maturity of electronic hardware and other engineering disciplines.

Daniel Jackson et al. summarize the state of formal methods in software engineering well. They explain that traditional software development relies on human inspection and testing in order to validate and verify. Formal methods utilize testing as well, but they also use notations and languages for rigorous analysis. Formal methods also use tools to reason about the properties of requirements, designs, and code. “Practitioners have been skeptical about the practicality of formal methods. Increasingly, however, there is evidence that formal methods can yield systems of very high dependability in a cost-effective manner…” [2].

Some standards (such as ISO/IEC^* 15408, Common Criteria for Information Technology Security Evaluation, and the United Kingdom’s Defence Standard 00-55, Requirements for Safety Related Software in Defence Systems) require at least some application of formal methods for the most critical levels.^† DO-178B identified formal methods as an acceptable alternative method. However, for the civil aviation world, formal methods have scarcely been used. Some avionics and tool vendors are beginning to use formal methods, and their use is expected to continue to grow. It seems that the practical experience and the supporting formal methods tools have finally reached a level of maturity to be used by the aviation industry.

My first introduction to formal methods was really quite humorous. I was asked to present an overview of DO-178B and the Federal Aviation Administration’s (FAA) software-related policy and guidance at a Defense Advanced Research Projects Agency (DARPA) meeting in the Washington, DC, area. I had presented the topic many times, so I simply replaced the title page and added some background information to my PowerPoint presentation, took the metro to Crystal City, and arrived to give the presentation. I was first on the agenda; therefore, not long after I arrived, I was introduced and began giving the presentation. Probably 5 minutes into the 60-minute presentation, I started seeing unusual looks on the faces of the audience. There were about 50 people and I had never met any of them before. Some looked confused. Many of them looked disgusted or flat out mad. Some of the looks just cannot be described. I knew I had hit a nerve of some sort, but I had no idea what it could be, so I just kept on talking. They didn’t laugh at any of my jokes, so I just quit trying to add humor. When I finally got to the question and answer time, I learned “the rest of the story.” I was speaking to a group of formal methodists who had no experience with the real world of civil aviation. I, on the other hand, had certified several aircraft but had no experience with formal methods. And, so the two worlds collided. I got away relatively unscathed and was happy to get back to my safe office that afternoon. I’ve learned more about formal methods since that time and have great hopes for their role in the future of safety-critical software.

16.2 What Are Formal Methods?

A 2002 document published by National Aeronautics and Space Administration (NASA) entitled NASA Langley’s research and technology-transfer program in formal methods describes formal methods as follows:

Formal methods refers to the use of techniques from logic and discrete mathematics in the specification, design, and construction of computer systems (both hardware and software) and relies on a discipline that requires the explicit enumeration of all assumptions and reasoning steps. Each reasoning step must be an instance of a relatively small number of allowed rules of inference. In essence, system verification is reduced to a calculation that can be checked by a machine. In principle, these techniques can produce error-free design; however, this requires a complete verification from the requirements down to the implementation, which is rarely done in practice. Thus, formal methods is the applied mathematics of computer systems engineering. It serves a similar role in computer design as Computational Fluid Dynamics (CFD) plays in aeronautical design, providing a means of calculating and hence predicting what the behavior of a digital system will be prior to its implementation.

The tremendous potential of formal methods has been recognized by theoreticians for a long time, but the formal techniques have remained the province of a few academicians, with only a few exceptions… It is important to realize that formal methods is not an all-or-nothing approach [1].

As John Rushby states: “Formal methods allow properties of a computer system to be predicted from a mathematical model of the system by a process akin to calculation” [3].

DO-333, entitled Formal Methods Supplement to DO-178C and DO-278A, was recently published by RTCA. The DO-333 glossary defines formal methods as follows: “Descriptive notations and analytical methods used to construct, develop and reason about mathematical models of system behavior. A formal method is a formal analysis carried out on a formal model” [4]. Basically, a formal method is a formal model plus a formal analysis. A formal model is “an abstract representation of a given set of aspects of a system that is used for analysis, simulation, code generation, or any combination thereof. A formal model is a model defined using a formal notation” [4].^* A formal notation is “a notation having a precise, unambiguous, mathematically defined syntax and semantics” [4]. A formal analysis is: “The use of mathematical reasoning to guarantee that properties are always satisfied by a formal model” [4].

The formal model is typically used during the development phase of a project to establish different properties. DO-333 section FM.1.6.1 provides some examples of formal models, including graphical models, textual models, and abstract models. Such models use mathematically defined syntax and semantics [4].

Currently, formal models are typically only used to model some of the software behavior, since higher level requirements input to the model “may include properties that cannot be verified with a formal method. Models can also be insufficiently detailed to allow meaningful analysis of some properties and yet be perfectly adequate for others” [4].

Formal models can be used to describe certain properties with a high degree of assurance, thus supporting safety. Many times the models only assure certain properties. Therefore, it is important to identify the limits of the model. Properties outside those limits are addressed by other models or by traditional DO-178C approach [4].

Formal models can benefit the software development process; however, the most beneficial aspect of formal methods is the formal analysis of the formal models. Formal analysis is used to prove or guarantee that software complies with the requirements. In order to prove or guarantee compliance to requirements, a set of software properties is defined (either created or embedded in the formal analysis tool). When a set of software properties fully define a set of requirements, the formal analysis can be used to prove that the set of software properties hold true [4].

An analysis method may only be considered formal if its determination of property is sound. DO-333 explains this as follows:

Sound analysis means that the method never asserts a property to be true when it is not true. The converse case, the assertion that a property is false when it may be true, colloquially “the raising of false alarms”, is a usability issue but not a soundness issue. Furthermore, it is acceptable for a method to return “don’t know” or not to return an answer when trying to establish whether a property holds, in which case additional verification is necessary [4].

DO-333 identifies three typical categories of formal analysis [4]:

1. Deductive methods which use mathematical arguments to establish each property of a formal model. Proofs are normally constructed using a theorem proving tool to show that the software properties are sound.

2. Model checking which “explores all possible behaviors of a formal model to determine whether a specified property is satisfied.”

3. Abstract interpretation which constructs conservative representations of a programming language’s semantics for “sound determination of dynamic properties of infinite-state programs… It can be viewed as a partial execution of a computer program which determines specific effects of the program (e.g., control structure, flow of information, stack size, number of clock cycles) without actually performing all the calculations.”

These three categories of formal analysis share a couple of attributes. First, they rely on formal models. “Compliance between artifacts can never be demonstrated between an informal model and a formal model, using formal analysis. For example, using formal methods to demonstrate compliance between specification and code requires that both be formal models. Second, all of the formal analyses are generally implemented using a tool” [4]. Therefore, tools used for formal analysis may need to be qualified. See Chapter 13 for information on tool qualification.

16.3 Potential Benefits of Formal Methods

Formal methods offer a number of potential benefits, as discussed in this section. As the experience and technology matures, the benefits will likely increase.

Potential Benefit 1: Improved requirements definition. Because of the formal nature of formal models, they can ensure that requirements are complete and well thought out. Traditional requirements are often incomplete, inaccurate, ambiguous, and inconsistent. Rushby writes: “Many of the problems in software and hardware design are due to imprecision, ambiguity, incompleteness, misunderstanding, and just plain mistakes in the statement of top-level requirements, in the description of intermediate designs, or in the specifications of components and interfaces. Some of these problems can be attributed to the difficulty of describing large and complex artifacts in natural language” [3]. Using a formal model helps to identify such weaknesses earlier.

Potential Benefit 2: Reduced errors. Formal methods help to reduce reliance on human intuition and judgment by using a more rigorous and mathematically based approach. Because of the rigor required to define a formal model, it can reduce the number of errors in the requirements and/or design.

Potential Benefit 3: More errors detected. Formal analysis can find errors that might go totally undetected using traditional verification means. It can uncover errors, misunderstandings, and subtle unexpected properties that might go unnoticed using the traditional review and test approach.

Potential Benefit 4: Increased confidence in safety properties. Using formal methods to model and verify the safety characteristics of a system can boost confidence in safety and quality.

Potential Benefit 5: Increased confidence for highly complex systems. Formal methods offer the ability to more thoroughly analyze input and output space. For highly complex functions, formal methods can verify functionality more thoroughly than traditional testing that only exercisesaportion of the input and output space.

Potential Benefit 6: Improved quality in error-prone areas. While it may be impractical to apply formal methods to all of the software design, it can effectively be applied in areas that are error-prone. These tend to also be the most complex areas.

Potential Benefit 7: More effective tool implementation. Commercial tools (e.g., automatic code generators) are being developed for use by multiple avionics manufacturers. When formal methods are used to build the tools, it can improve the robustness of the tool and decrease the amount of additional verification required by the tool user. For example, an automatic code generation tool developed using formal methods may reduce or eliminate the need for structural coverage analysis on the tool’s output, since formal methods ensure the tool will not generate inaccurate, untraceable, incomplete, or extraneous code.

Potential Benefit 8: Reduced cost. While the application of formal methods might require more rigor and resources initially, it has the potential to find errors earlier and with more certainty. This can reduce the overall cost of the software development, since finding errors late in the process is quite costly.

Potential Benefit 9: Maintainable software. Since formal methods have the potential to produce cleaner requirements and architecture, they can make the system easier to maintain. It’s worth noting that even with formal methods, caution must be exercised when reusing or modifying existing software.

16.4 Challenges of Formal Methods

There are a number of challenges that projects face when implementing formal methods.

Challenge 1: Lack of education leads to a high fear factor. Most software engineers and their managers are still uneducated and even afraid of formal methods.

The symbology looks strange and many engineers may not have the mathematical background to apply the tools. This challenge can be overcome by training and user-friendly tools.

Challenge 2: Formal methods are not applicable to all problems. Formal methods have their limits. It is important to use them where they are most effec tive and where they have the most potential (e.g., complex or problematic functions).

Challenge 3: It can be difficult to mix formal and not-so-formal methods. Since most projects apply formal methods to a subset of the overall requirements definition and verification activities, the formal methods must be integrated with a more traditional process. There may be situations where formal methods are used with other not-so-traditional techniques, such as object-oriented technology or model-based development. To address the challenge, it’s important to keep the big picture in mind and to remember the objectives that drive the activities.

Challenge 4: Limited number of formal methods experts available. There is not an abundance of formal methods practitioners out there, so this can be a barrier to successful use of the techniques. As noted in Challenge #1, training and user-friendly tools can help alleviate this challenge as well.

Challenge 5: Formal methods can be resource intensive. Formal methods require specialized skills and tools. They can also be quite challenging to apply. For this reason it is best to use them in the most critical, complex, and error-prone areas, where they will have the most return on investment.

Challenge 6: Too much confidence in the verification ability of formal methods. There can be a misconception that formal methods can guarantee correctness. They do offer greater confidence in the software’s compliance to the requirements; however, as Bowen and Hinchey explain: “If the organization has not built the right system (validation), no amount of building the system right (verification) can overcome that error” [5].

Challenge 7: False assumptions exist about testing. Some contend that formal methods mean no testing is needed. Formal methods can help to reduce the likelihood of certain errors or help to detect them, but they must be accompanied with appropriate testing [5]. DO-333 emphasizes the need to test the software, even when applying formal methods. In particular, target-based testing is needed to verify the hardware/software integration.

Challenge 8: Industry and certification guidance are not yet standardized. If three people were asked to explain formal methods, they would probably provide at least four answers. The completion of DO-333 is a major step toward standardization; however, there are still many project-by-project issues to be resolved.

Challenge 9: Tool support is still incomplete. The formal methods tools have improved significantly over the last few years, but there is still considerable work needed to make the tools practical for the aviation community. The tools need to fit well into the software life cycle and be usable by domain experts. If the tools are not practical for those who have the domain expertise (e.g., a flight controls engineer), they will not be effectively used, and the aforementioned potential benefits will not be realized.

16.5 DO-333 Overview

16.6 Other Resources

This chapter has merely provided an introduction to formal meth ods. There are numerous books, reports, and articles on formal methods. There are people who have committed many years of their lives to this subject. They’ve been quite industrious at generating reports to educate. If you choose to use formal methods in a project, you’ll want to exam ine the topic much deeper and probably hire some specialists to assist and educate your team. The “References” section includes some of the resources I’ve found most useful. Each reference points to other beneficial resources.