Verifying certified software: making the most of the tools you have

by Mathew P.D. Slager , TechOnline India - September 08, 2011

It's better to verify software not just at the formal verification step but throughout the software development process. Still, a common question is how to implement verification protocols and techniques throughout the process using tools available in the market today.

A DO-178B Level A certification is perhaps the highest certificate of reliability that can be rewarded to a piece of software. Nothing says reliable like meeting the requirements of a standard designed for software where even a single fault can result in an airplane crashing and the loss of human life. Like many reliability standards, it places strict requirements on how a software product is designed, developed and verified.

Software projects pursuing this certification will often follow a traditional software lifecycle model. Modern implementations of these processes have two key components in common: First, they all involve an iterative process, whether within a product cycle or between product cycles. Second, they all involve a Design->Write Code->Verify pathway.

A critical component of this pathway is the final step: Verification.

The reality of software development is no matter how good the design is going into the implementation and code development stages, software developers are bound to introduce mistakes and errors. In large and complex systems, this is especially true and problems may not be limited to simple coding errors but can extend to a problem with the system architecture itself.

Generally, it is too expensive to wait until the final integration steps of a software development schedule to perform the majority of the verification efforts to uncover the problems. Studies have shown that errors found in the final stages of the development process can be 50 to 200 times more expensive to fix than those found early on.[2]

This is often the result of the associated rework required to modify the software or system architecture to account for the design and implementation flaws; in fact, it is common for a project to expend 50% of its effort in avoidable rework [2]. It can also influence an organization’s ability to get to market quickly. IBM has previously found that products with lower defect counts have shorter schedules[6].

One can therefore surmise that there are strong advantages to performing verification of software not just at the formal verification step but also throughout the entire software development process. Once that conclusion is made, a common question heard is how to implement verification protocols and techniques throughout the development process using tools available on the market today, a topic this article will attempt to address.

Often this will require an investment in tooling to achieve some of these capabilities. It should be understood that the development of reliable and certifiable software could be significantly more expensive than traditional software practices, but that significant cost savings can still be achieved by intelligent investment in proper tools and in the selection of appropriately refined processes[2].

And this investment is not without purpose, since not only are these best practices for the development of safety-critical software, but some of the techniques and processes discussed are actually required by various safety and reliability standards, notably DO-178B which requires that software verification be an integral and iterative component at each phase of project development.

 

Purpose of a coding standard

Some of the best development practices can begin before the first line of code is written or even before the software is designed, by selecting and enforcing a coding standard for the project.

Coding standards have various purposes, two of which are to reduce faults in the program, and to increase the maintainability of the software. The last point is important, a significant amount of time and cost associated with a software project is spent in the maintenance phase, often as high as 60%.[7]

Section 11.8 of the DO-178B standard requires that a project develop a Software Code Standard, as part of the life cycle data to be collected in conjunction with the certification effort. All FAA approvals will require that these documents be submitted to the U.S. DOT for evaluation[8].

It is important that the Software Code Standard be enforced throughout the development lifecycle. It has been empirically demonstrated that retrofitting a coding standard into existing software may introduce more faults than it helps prevent, if it is not done with extreme care.[3]


Automatically enforced standards

Making use of tools that can automatically enforce coding standards is a simple way to ensure that the coding standard is consistently applied across a project. The popular MISRA C: 2004 coding standard (Figure 1 below) has been adopted by many in the industry and it was designed with automatic enforcement in mind, something that is supported by all good compilers on the market.

 

Figure 1. Automated MISRA C enforcement example

 

Several tools will also allow the automatic enforcement of other coding standards; Green Hills Software’s MULTI  IDE even provides an option to enforce the same coding standards they use to develop their software.

Automatic enforcement is important; research has suggested that the introduction of automatic enforcement and detection tools has led to a significant decrease in memory-related bugs in software[5].

Consequently, making use of tools that can effectively enforce coding standards should be an essential step in the selection of a development environment for projects seeking a software certification for safety or reliability, both in terms of ensuring a reduction in software faults, and in demonstrating to a certifying body the project’s commitment to the certification process.

 

Static analysis

Static analyzers are development tools that analyze a project’s source code in an effort to find a variety of bugs, which include buffer overflows, resource leaks, bad memory references and many other security and reliability problems.

They are a significant improvement over automated coding standards tools, since they will analyze more than just syntax and language semantics. Instead, they will analyze how the source code works, and what it is attempting to accomplish.
Since memory-related problems (notably NULL dereferences) and security-related issues still comprise a significant portion of the bugs found in software projects,[5] this kind of deep analysis could significantly help in the reduction of software faults.

A good static analyzer will even find bugs across multiple source files in your project, as shown in Figure 2 below, where the pointer p is expected to be initialized by the call to func1() but source analysis finds that it will not be initialized in this case. 

 

Figure 2. Static analysis across source files

 

One advantage of static analysis is its ability to be performed before a program is ever run in the target system, finding bugs in software before a single instruction is ever executed. Many static analysis tools are separate from the compiler tool suite, and often require complex setup and configuration before they can be used due to differences in the compiler C/C++ language front-end and the C/C++ language front-end used by the static analysis tool.

This often results in these tools not being used until late in the implementation process or at the final integration stage. As discussed earlier in this article, a cost savings can be achieved by catching problems as early as possible.

Consequently, tools that allow for the use of a static analysis pass every time a file is compiled, without adding any hassle to the developer or significant increase in build times, would be the ideal candidates for a static analysis solution. Some solutions are integrated into the same binary as the compiler used in the project, allowing this sort of frequent low-overhead usage to be implemented in a project.

When considering the DO-178B certification process, static analyzers are a powerful tool for ensuring a software application conforms to the SCS being used for the certification effort.

They also help enforce adherence to the SCS early on with the engineering team responsible. Most static analysis tools can also analyze software complexity, a metric that will be necessary to obtain as part of the certification process.

Perhaps the most important benefit is their ability to ensure the accuracy of the program, identifying software faults early on before time is wasted debugging the system in a live environment.

 

Structural coverage analysis: DO-178B requirements

According to the DO-178B standard, applicants must prove that software verification test cases cover the software structures, specifically the conditions and paths. This allows the effectiveness of the software verification process to be evaluated.

The level of coverage required depends on the type of certification being sought. DO-178B Level C software only requires statement coverage, which requires proving that every statement in the program has been executed at least once by the software verification tests.

DO-178B Level B software extends that by adding a requirement to demonstrate decision coverage, which requires proving that every branch pathway in the program has been reached at least once by the software verification tests.
Less formally, this means that every conditional branch (decision) has been both reached, taken and not taken. DO-178B Level A software requires that modified condition/decision coverage (MC/DC) is proven. MC/DC coverage is defined in Section 6 of the standard:

 

“every point of entry and exit in the program has been invoked at least once, every condition in a decision has taken all possible outcomes at least once, every decision in the program has taken all possible outcomes at least once, and each condition in a decision has been shown to independently affect that decisions outcome. A condition is shown to independently affect a decisions outcome by varying just that condition while holding fixed all other possible conditions.”[4]

Assisted unit testing

The common method to demonstrate coverage is to develop a series of unit tests for the program in conjunction with a profiling tool to verify that the unit tests achieved complete coverage. However, relying on human analysis of profiling information to verify test coverage of the software can be error prone. Furthermore, most profiling tools are not designed with MC/DC in mind.

Nonetheless, tools do exist which can help verify that a program was tested as required by MC/DC analysis. For example, G-cover, a tool designed specifically for DO-178B certification efforts, uses the object code and debug information in a program to automatically generate a set of debugger scripts that can be used to identify every conditional statement in a program.

This approach has the advantage of being independent of the source code input language as it works equally well on C, C++ and Ada code. It is also effective at identifying conditional statements that may not be obvious when examining the source code.

This is an important distinction for Level A certified software, where the correlation between optimized or instrumented object code and its associated source code statements may not be clear. Section 6.4.4.2 of the DO-178B standard states:

“The structural coverage analysis may be performed on the source code, unless the software is level A and the compiler generates object code that is not directly traceable to source code statements. Then, additional verification should be performed on the object code to establish the correctness of such generated code sequences. A compiler-generated array bound check in the object code is an example of object code that is not directly traceable to the source code[4].”

The tool can then be used in conjunction with user-supplied test vectors or unit tests to collect information on how the tests covered the program, and to generate a final report of that analysis, such as the simple report shown in Figure 3 below.

 

Figure 3. Sample report excerpt from G-cover

 

Using an automated tool like this is the best way to analyze your software for MC/DC coverage; relying on human analysis is bound to miss conditional statements in the program since it is usually not obvious what a language statement will be translated into by a compiler, especially when optimizations are enabled.

Trace solutions

Tools like G-cover are one means to demonstrate coverage of a program. However, advancements in microprocessor hardware design have allowed for new techniques to be deployed that can allow code to be run close to full speed (i.e.: without instrumentation), collecting coverage information in real-time. This is achieved by utilizing the trace ports found on modern processors, such as those found on ARM and Power based microprocessors.

Trace, simply defined, is a protocol a processor follows to log every memory access and every branch the processor makes, usually to a dedicated bus embedded in the processor.

An external debug probe can then connect to this interface and collect the data in real-time as it happens. The amount of data that can be collected is limited only by the amount of memory the debug probe has to store data. However, in reality, a secondary barrier can exist in terms of how long it takes to transfer this data to the host PC and analyze it.
Even though four gigabytes seems like a huge buffer size, given the number of branches and memory accesses in a program, and the speed at which modern processors run, this is not enough to capture the entire execution of a program over time. Nonetheless, for simple unit testing of program components, it can be quite useful.

For example, Figure 4 below shows a trace tool listing all the branches in a program. By examining which branches were reached and which of those were actually taken, one can quickly ascertain if the test vector reached the desired portions of the program.

A good debugger will be able to correlate graphically this information with the source code, where the debugger has highlighted statements that were never executed. These kinds of visualizations get the results of the data immediately in front of the software developer, allowing them to identify patterns and other information quickly.

 

Figure 4. Branch statistics collected from trace

This level of detail can easily facilitate coverage analysis for DO-178B Level B and Level C requirements. By correlating the output from multiple runs of various unit tests, one may be able to extrapolate or at least estimate MC/DC coverage by examining differences in branch patterns assuming all other branch pathways can be kept fixed.

Clearly, a key advantage of these tools would seem to be their ability to be utilized throughout the development and debugging process. In fact, there is evidence that suggests that the proper, judicious application of tools like this can generally improve the robustness of a system[1].

Given these advantages, system architects are encouraged to select hardware that provides a trace port; although this may not be cost efficient for a production system given the currently high cost of processor pin counts, it should at least be considered for testing and development models.

Evaluating the alternatives

The requirements of the DO-178b standard are rigorous, and it can be expected that the efforts required to successfully achieve the certification are both laborious and financially expensive. However, there is a perhaps unexpected benefit to some of the stringent requirements of the standard.

As examined in this article, the Software Code Standard requirements, as well as the requirement Structural Coverage Analysis not only have the intended benefit of increasing the robustness and reliability of the software being developed by reducing the risk of fault.

But they also help ensure software faults are both found and repaired early can both reduce the schedule and overall cost of the certification effort, as pointed out by McConnel [6] and Boehm and Papaccio [2].

This is of course most likely to be achieved when the appropriate tools and policies are put in place for the project to reduce the effort and therefore cost of implementing these procedures over the lifetime of the certification project.

The Software Code Standard adopted for the project should be enforced automatically by the compiler as much as possible; not just at some designated milestone toward the end of development but throughout the lifetime of the project at every compiler invocation. This can be further assisted by the use of a good static analysis tool.

Ideally, the tool selected would be both fast and tied in with the build system to ensure the majority, if not all, policies are both checked and enforced at every compile. Ideally such a tool will be able to analyze the program as a whole, finding problems that can only be recognized when examining data and control flow across multiple compilation units.

Secondly, good software tools should be used to assist with Structural Coverage Analysis. Exactly which tool and approach is selected may depend on which of a Level A, B or C certification the project is going for.

For a level A certification MC/DC analysis is required, but it can be quite difficult to analyze when the correlation between high-level source code and the object code produced by the compiler may not be obvious.

The compiler may have altered high-level decision statements in such a way that no decision is performed in the object code, and conversely, it may have introduced new decisions that may not have been expected based solely on an examination of the high-level source code.

Working with a tool like G-cover, discussed earlier, is a great way to get both a better understanding of the decisions in the software and to quickly verify MC/DC coverage of the software’s test suite.

For less stringent coverage requirements such as those needed for a Level B or C certification, the recent adoption of trace hardware by many semiconductor companies is a new and very promising tool to quickly analyze more basic decision coverage.

By providing full visibility into the history of a piece of code, including full awareness of how every decision in a code path was handled, trace hardware enables a user to quickly and repeatedly assess how well their test vectors are covering their software.

Furthermore, one should not overlook the general advantages such information provides a software developer during development and debugging of an application, especially paired with an advanced graphical debugger that enables them to visually analyze the information. This alone could reduce the overall software development costs if employed correctly.
Regardless of which specific tools are selected for a project, it is of paramount importance that they both be selected and deployed as early in the project planning process as possible.

As Boogerd and Moonen [3] point out, for example, the improper or late application of a coding standard can actually both increase the cost of a project and increase the likelihood of the resultant software having faults.

So the tools exist to facilitate the DO-178b Software Code Standard and Structural Analysis requirements, but one should not be late in adopting their use.

 

About the author:

Matthew Slager has been with Green Hills Software since 2001. He is currently a Director in the Advanced Products Engineering Group. For the past five years Slager has lead engineering units in key technology areas including secure real-time operating systems and associated debug environments. He has worked within embedded industry for more than 14 years with previous engineering engagements in telecommunications and aerospace. Mr. Slager earned his Bachelor of Mathematics with majors in both computer science and combinatorics from the University of Waterloo, Canada.

References:

1. Berner, Stefan, Weber, Rolland and Keller, Rudolf K., “Enhancing Software Testing by Judicious Use of Code Coverage Information”, IEEE 29th International Conference on Software Engineering, May 2007
2. Boehm, Barry W. and Papaccio, Philip N., “Understanding and Controlling Software Costs”, IEEE Transactions on Software Engineering, Vol. 14, No. 10, Oct. 1988, pp.1462-1477
3. Boogerd, Cathal and Moonen, Leon, “Assessing the value of Coding Standards: An Empirical Study”, IEEE International Conference on Software Maintenance, Oct. 2008, pp. 277-286
4. DO-178B, Software Considerations in Airborne Systems and Equipment Certification, Dec. 1992, RTCA
5. Li, Z., Tan, L., Wang, X, Lu, S., Zhou, Y. and Zhai, C., “Have Things Changed Now? An Empirical Study of Bug Characteristics in Modern Open Source Software”, in Proceedings of the 1st workshop on Architectural and system support for improving software dependability, ACM, pp25-33
6. McConnel, Steve, “Software Quality at Top Speed”, Software Development, Aug. 1996
7. Pressman, Roger S., Software Engineering: A Practitioner’s Approach, 5e, 2001, New York, NY: McGraw-Hill
8. Software Approval Guidelines, Jun. 2003, U.S. Department of Transportation, Federal Aviation Administration

About Author

Comments

blog comments powered by Disqus