As I’ve said before, MC/DC analysis is the bane of Level-A development under DO-178B. It is not well understood, either by developers or by verification engineers. Automated analysis tools will perform the analysis, but that may not occur until verification has begun. Fixes at this stage are far less desirable than avoiding issues in the first place. So how do we ensure that MC/DC issues do not occur in the first place?
There are several good resources dedicated to performing MC/DC analysis, perhaps the best of which is NASA’s tutorial on the topic. But few will brave the length of that document, and then perform enough of these analyses to gain a true understanding of how MC/DC issues can be avoided. In fact, to date, some of the most knowledgeable experts in the field have not been entirely successful in devising coding rules that will guarantee a clean MC/DC analysis; and as such this topic remains somewhat of a dark art.
Actually, a little understanding can go along way towards attaining a clean analysis. When applied with this understanding, basic software engineering techniques can all but eliminate issues with MC/DC.
Let’s begin with the basics; MC/DC applies only at the source level, and never at the assembly language level. Why is this? Because MC/DC differs from regular branch coverage only when multiple conditions are involved; only simple conditions exist at the object or assembly level. In reality, MC/DC analysis is actually a technique designed to be applied at the source code level as an equivalent to branch coverage analysis at the object level; and as difficult as MC/DC is thought to be, it is generally considered to be easier than its object code equivalent. Short-circuit operators that exist to enhance performance in certain high-level languages create “hidden” branch paths, which can lead to branch coverage holes at the object level. These operators are the whole reason for MC/DC analysis. Even at source level, if no compound conditions were used, simple branch coverage analysis would suffice; there would be no MC/DC issue; but this approach is impractical for most development. While it can be a valuable tactic when used sparingly, when applied universally it will actually impair code quality in terms of structure and readability.
So what can we do reduce the incidence of gaps in MC/DC coverage? There are several things that can help. They may be used individually or in combination, as appropriate.
Eliminate. MC/DC coverage does not permit for the existence of constants in conditions. This is because, in unoptimized code, it creates a branch that can never be executed. Optimization rules are permitted, but never presumed to exist by DO-178B.
Simplify. Reduce conditional logic to canonical form using boolean algebra or karnaugh maps. Some of you haven’t heard those words since your freshman year of college. It’s not nearly as tough as it sounds, and like so many things, it becomes second nature with a bit of practice.
Factor. Some condition clauses unnecessarily complicate all kinds of analyses. Specifically, functions or expressions with side-effects should be either moved outside of the compound decision-logic or should be placed logically before any short-circuit operators. If a function is guaranteed to always return the same result in unbroken code; then it is effectively a constant. It may be prudent to test the result, but this is effectively defensive programming. As such, it should be handled in a separate decision branch, not as part of the regular execution flow. Defensive programming was the topic of a recent article.
Prioritize. The biggest issues with MC/DC happen when complex conditions lead to poor understanding of the underlying execution flow; logical knots result that can be difficult to sort out. One way to avoid this is to impose a strict logical order on short-circuit operators used. Here is a very simple rule (at least it sounds simple) that can help to avoid those knots: Ensure that the statement is structured such that only one “short-circuit” may occur for any combination of conditions. That means that any logically subsequent short-circuit operators will not be evaluated following the first shorting. A logical-and shorts when the first term evaluates to false; that is, the second term is never evaluated. A logical-or shorts when the first term evaluates to a true; and again, the second term is not evaluated. Note that only short-circuit operators need to be considered here; as any term containing other logical or math operators does not affect the underlying branch structure. These concepte probably warrants a few examples*. Under the previous rule, the expression ( a || (b || c) || d ) would be perfectly legal, as any combination which contains only the logical-or operator and parentheses would indeed terminate further evaluation on any true clause. Likewise, ( a && (b && c) && d ) would terminate on any false term; again, perfectly legal. It is only when we begin mixing the operators that we begin to see issues. The expression ( (a && b) || c ) is logically sound, but violates the rule, in that, if a is false, the logical-and is short-circuited, yet the logical-or is still evaluated, whereas ( c || (a && b)) presents no such issue, and is therefore acceptable. The expressions (a && b && c) || ( d && e && f) and ( a || b || c) && ( d || e || f) both violate the rule, and should be avoided. It is important to note that there is nothing inherently wrong with the logic of these statements. They just increase the probability that MC/DC coverage analysis will find issues. In fact absent of logic defects, if all of the above rules are strictly adhered to MC/DC analysis results should almost always match the branch coverage analysis results. That’s good. Unfortunately, it is not always practical to apply the above rules strictly. So what else can we do?
Substitute. We can begin to avoid the MC/DC problem by simply reducing our dependence on the short-circuit operators. Some optimizers do this for us in the background; yet some people call it cheating. This is probably the most controversial (and needlessly so) solution to the MC/DC issue. So what am I talking about? Replacing the logical short-ciruit operators with their bitwise counterparts. I’ve been told that doing so “violates the spirit of the language” or that it “obscures the intent of the design”, or even that it is somehow cheating on MC/DC to stoop to this level of syntactic trickery. I strongly disagree with all of those points. If a and b are booleans (guaranteed to contain only a logical-true or logical-false); then there is absolutely no difference in results of the expressions (c || a && b) versus (c | a & b). Yet, while the outcome is the same, the former creates a branch, whereas the latter results in simple mathematical operations, which is often much more efficient than the short-circuit branch. While this way of doing thing is less common, the operations are well understood and not at all confusing, and rationale can be clarified with comments. For any programming language that will allow it, how does this violate the language or the design intent. As to cheating on MC/DC, the purpose is to ensure that all “hidden” branches are covered. Removing unnecessary branches is the intended outcome. We are removing them in a way that does not alter our design. I don’t believe this is cheating in any way; and I strongly advocate it, provided that it documented such that it does not impair design intent or clarity of function.
Separate. As stated earlier, MC/DC is equivalent to branch coverage for conditions with a single term; and where it is reasonable to do so, things may be made simpler by making some or all of the hidden branches explicit by breaking up one decision into two or more. I have no rule-of-thumb for when this is the right choice; there are many factors that can affect it, but readability and maintainability should be heavily considered.
As you are working to reduce your MC/DC exposure, take note that branch and MC/DC coverage rules apply everywhere that logical-operators are used. This is because, disregarding optimization, compilers will typically create branch operations to evaluate any logical operator. This includes all logical operators, short-circuit or not. For example, one common, but typically ineffective “cheat” uses the logical-operators to perform boolean assignments, as such:
a = (b && d);
which will often translate to the object code equivalent of
if (b && d)
{
a = true;
}
else
{
a = false;
}
which is actually still shorthand for the fully expanded translation, which is more closely represented in C (with the hidden branches now visible) as:
if (b != 0)
{
if ( d != 0 )
{
goto then__;
}
else
{
goto else__;
}
}
else
{
goto else__;
}
then__:
tempreg = true;
goto done__;
else__:
tempreg = false;
done__:
a = tempreg;
As before, there is nothing inherently wrong with this structure, but because it creates hidden branches, it does not change the coverage obligation, and hence may not provide any benefit with respect to MC/DC. On the other hand, the equivalent (for pure booleans) a = ( b & d ); is a straight mathematical assignment, which creates no hidden branches, and is already in is translated approximately verbatim.
The application of MC/DC analysis and the issues surrounding it are often hotly debated. If you are in a position to be concerned about MC/DC, you would do well to confer with your friendly DER before applying these strategies, or any other.
|
Max is a father, a husband, and a man of many interests. He is also a consulting software architect with over 3 decades experience in the design and implementation of complex software. View his Linked-In profile at http://www.linkedin.com/pro/swarchitect |
subscribe
Comments