Channels ▼
RSS

C/C++

Detecting Bugs in Safety-Critical Code


Static Analysis and Systematic Testing

Again, safety-critical developers are required to demonstrate coverage. There are of course different kinds of coverage, and the risk the code carries dictates which kind of coverage is required. In the DO-178B Standard for aviation, the riskiest code requires 100-percent modified condition/decision coverage (MCDC). The next two most risky classes require 100-percent decision coverage and statement coverage, respectively. The least risky code, such as the inflight entertainment system, has no coverage requirements at all.

Most developers are familiar with statement coverage, and anyone who has tried to test with 100-percent statement coverage knows how difficult it is to achieve. Decision coverage is more stringent—it requires that all branches in the control flow are taken. You must make test cases that force all your conditional expressions to evaluate both true and false. MCDC coverage is stronger still, and means that all subexpressions in a conditional should be evaluated to both true and false. Consider what this means in terms of the number of test cases for this code snippet:

if (a || b || c)
   foo();


Table 1 shows the number of test cases required to achieve full coverage for each coverage criterion, and example values required of the inputs.

Coverage a b c
Statement (1 case) 1
Decision (2 cases) 1
0 0 0
MCDC (4 cases) 1
0 1
0 0 1
0 0 0

Table 1: The number of test cases required for full coverage.

Clearly, achieving full coverage is nontrivial. What can make it extremely frustrating is if it is fundamentally impossible. If your program contains unreachable code, then you cannot even get full statement coverage, never mind decision or MCDC. Similarly, if your code contains redundant conditions (conditions that are either always true or always false), then you might achieve statement coverage, but not decision coverage.

A developer may spend hours trying to develop a test case before it becomes evident that it is impossible. If you know going in that this is the case, then you don't have to waste time on it.

In Figure 3, the value of variable rest (which is an unaliased automatic integer) must be at least 3 by the time you get to line 12. The decrement means it is at least 2 at the comparison, so the condition never evaluates to false. The following line 13 is also redundant by the same reasoning, and appears in a different report. This is a fairly simple example, and many humans would have spotted this in a code review because all the relevant expressions are in the same vicinity. If the bodies of the conditionals had been larger or if the conditions themselves had been embedded in a function or a macro, then the weakness would not have been as easy to spot. However, the static-analysis tool would not have been fooled.

[Click image to view at full size]

Figure 3: Redundant condition warning from CodeSonar.

These kinds of issues correlate well with bugs, too. Consider Figure 4, in which the column on the left shows the condition that cannot be satisfied: pb->type can never be equal to 3. This value comes from a call to get_type(); see Figure 5. The error is on line 30 and is clearly a typo—the programmer missed the final X.

[Click image to view at full size]

Figure 4: Fragment of a report from CodeSonar illustrating a redundant condition.

[Click image to view at full size]

Figure 5: The body of get_type, showing that there is an error on line 30.

Conclusion

Bugs are a plague on our profession and bad for business. That's why advanced static-analysis tools should be in every programmer's toolbox, and not just for safety-critical systems. They help find real errors, and reduce cost.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video