Notes on coverage

This post is a collection of notes and (slightly cleaned up) summary of the research that went into my talk Mastering MC/DC from First Principles at Techtown this year.

The history of code coverage

The idea of code coverage is actually quite old. The oldest reference I found is the 1963 paper Systematic Mistake Analysis of Digital Computer Programs. Going through its references I also found another gem, A Control System For Logical Block Diagnosis With Data Loading, from 1960. This paper describes a system for writing tests for programs and running them, and it is fascinating just how sharp the observations were and how they are still true today. Here are a few quotes.

Standard diagnostic systems require that the programmer read in sample data with his program and then follow the data through the program by means of memorydumps and breakpoint printing.

Amusingly, printf debugging is older than printf. Printing whatever is in memory is an obvious and simple technique so it absolutely makes sense that it’s well established quite early in computers. It then goes on:

For many programs this procedure is certainly satisfactory, but there are instances where additional aid from the diagnostic program is desirable.

Which rings true today. Printf is quite useful, but it has some severe limitations.

The approach which seems to be simplest and most efficient in this instance is to test the subroutine or logical block of instructions as a separate entity, that is, supply it with the selected test data, let the computer execute it, and then print out the results. To make the approach reasonable, it should be possible to execute all the necessary tests during one run.

It’s describing a test runner/driver and framework (like catch2, boost.test, google test, pytest, etc) and this is how we test programs today. It is bizarre reading such a modern description when they elaborate specific test runs using punch cards:

1. Print Card. This card is the control card for all breakpoint printing and memory or tape dumping.

The RUN card is one of the principal new features of the system and gives the programmer much greater control of the diagnostic run […]

Comes to show, really, that ideas truly last, while computer systems come and go. Automation of program debugging from 1961 is another paper that describes automated test suites.

The idea of coverage doesn’t show up in that paper, but does so 1963 Systematic Mistake Analysis paper, which is a goldmine. They don’t actually use the term coverage, but they clearly explain the concept. From the introduction:

The purpose of work reported here has been to develop a systematic way in which a programmer may test, all realistic combinations of input data, and hence all portions of a given program. Although at first this seems to be an arduous task, its handling is simplified by an orderly approach, and its reward is a greater assurance of the correctness and reliability of the program. The potential number of test cases is given by 2^B, where B is the number of branchpoints in the flowchart.

What blew my mind is that this paper also describes the core property of prime path coverage; that loops must be entered, taken at least once, and skipped. My prime path coverage implementation landed in GCC 15, 65 years later.

One interesting thing with these papers, and a lot (most?) papers from the era, is that they discuss and describe programs in terms of flow charts or flow graphs and trees, and code does not really show up much. From the conclusion of Systematic Mistake Analysis: The tree is therefore an effective aid in the formulation of a test deck containing, for a given problem, all combinations of input that can be expected to occur. zcov is built on the idea that the graph is an excellent way of analyzing programs structure and coverage, and this paper demonstrates that neatly.

The history of MC/DC

The first paper I have found that references MC/DC is Applicability of modified condition/decision coverage to software testing from 1994. This paper thoroughly covers MC/DC, the motivation, and the strengths of the metric. Interestingly, it notes that MC/DC was not well known, but has been used for years in the avionics industry, and MC/DC was mandated by DO-178B in as early as 1992. I haven’t figured out exactly when MC/DC was developed, but presumably sometime in the late 80s.

MC/DC has long been mandated for safety critical systems in spaceflight, automotive, trains, and presumably in other systems where faults could lead to death, harm, and massive damage. Its use outside of those industries are still somewhat limited. SQLite stands out as an example, but considering its use in aviation it falls under that regulation.

The early 2000s saw two influential texts on MC/DC; A Practical Tutorial on Modified Condition/Decision Coverage and An Investigation of Three Forms of the Modified Condition Decision Coverage (MCDC) Criterion. These are good reads for understanding MC/DC and how to do it (by hand). I would not really recommend doing MC/DC by hand unless absolutely necessary as it is very error prone (and a bit dull), but their methods greatly influenced my GCC design.

Unique-cause MC/DC has received most of the focus, which is an interesting historical artefact. In the 2001 report Rationale for Accepting Masking MC/DC in Certification Projects (CAST-6)¹ by the Certification Authorities Software Team they note that masking MC/DC should be acceptable.

When DO-178B was written, the research on masking MC/DC was still being carried out; therefore, unique-cause MC/DC was the technique documented. Since that time, research has shown that masking MC/DC also meets the intent of the MC/DC objective. Therefore, it is proposed that masking MC/DC be considered an acceptable method for meeting MC/DC by applicants striving to meet the objectives of DO-178B, level A.

Chilenski notes in his conclusion that masking MC/DC should be the preferred form. I personally support this conclusion and find masking MC/DC a more natural form which leverages Boolean algebra to great effect; it is more permissive when forming independence pairs and require fewer tests (but equivalent significant tests) while meeting the objective.

Structural coverage

Black box testing is designing test cases based on the specification (how the program/function is supposed to work) without regard for the program structure. White box testing is designing test cases based on the structure and uses the specification to predict the outcome of the test. Structural coverage is a measure of how our tests exercise the structures and components of the program.

The word structure has echoes of Dijkstra’s famous essay Go To Statement Considered Harmful which argues in favours of structured blocks like while loops, if-then-else, etc. in favour of plain gotos. Another way of thinking about structure is the control flow graph (or diagram or chart, to use the 1960s terminology). By thinking of structure this way, and expanding individual conditions to blocks in the control flow graph, the structure becomes immediate and obvious as opposed to the familiar reading as source code. With this perspective it is clear that line (or even statement) coverage is very underwhelming. Here is an example from zcov, the SQLite function validJulianDay, which “unpacks” the expression return iJD<=0 && iJD<=INT_464269060799999 into its actual structure.

Chilenski and Miller provide an insight in the Applicability of MC/DC paper:

An alternative approach that leverages the strength of both techniques is to develop functional tests from the specification and measure coverage against a structural criterion. In this way, the structural criterion is utilised as a test data adequacy criterion, rather than a test data selection criterion.

This immediately became my favourite way of approaching about coverage. It has never been about meeting some arbitrary metric (except for regulation purposes, I suppose), but rather as an effective tool and finding discrepancies between the specification, the program, and the test suite. Any such discrepancy should be carefully investigated and understood. Both Hayhurst et al. and Chilenski 2001 discuss the testing technique at length, emphasising the importance of deriving test cases from intended behaviour and not incidental behaviour, we want tests to verify that the program does what it is supposed to, not lock in what it already does. Hayhurst et al. notes that including verification activities in every development step “builds in” quality, because “testing or analyzing in” quality at the end of the lifecycle is impractical. I would even argue impractical is a very soft way of putting it; no testing effort can fix a broken design, and earlier feedback (where coverage can be very valuable) can identify design problems before they settle.

For all of this to work we need to always derive tests from the specification (black box) and not just mindlessly target code that happened to not be covered after the first batch of tests. Both testing and coverage tends to really pay off when coverage is already high; is an investment, and the value we draw from it is proportional to the effort we put in, and we find more problems (in both implementation an design) the more tests we write. What we want is not really the test itself, although it functions nicely to detect regressions, what we want is the process of writing tests.

Coverage is a very objective measure and gives a signal on when to stop testing. If we find our tests adequate with respect to the requirements that also achieve (strong, e.g. MC/DC, not line) coverage we can stop testing and be confident that our program does what it is supposed to and nothing more. We can use it to avoid pointless tests; if a test does not meaningfully improve coverage it is likely that the behaviour it tests is already handled by some other test case, and I would argue a more minimal test suite is usually the better one. Coverage can be useful for challenging assumptions; if we design a test and expect that it should exercise some new structure (e.g. show the independence of a condition) and it does not something is wrong and we have a good seed for an analysis.

What I think is a mistake is adding tests for the sake of improving coverage. It is mostly a pointless (but expensive!) effort as the real value to draw from coverage is the strong feedback into the relationship between the program, the specification, and the tests. However, using coverage to drive refactoring and redesign is an excellent use of the tool.

Simplified MC/DC

MC/DC is usually defined this way:

• Every statement in the program has been executed
• Every point of entry and exit has been invoked at least once
• Every control statement has taken all possible outcomes
• Every non-constant condition in a Boolean expression has taken on true and false
• Every non-constant condition in a Boolean expression as been shown to independently affect that expression’s outcome

It is a bit of a mouthful, and I think we can generally simplify this to:

• Every condition has taken on true and false
• Every condition has been shown to independently affect the outcome

The other properties are downstream of these two properties anyway (maybe except in the case of tautologies?), and we can focus on what makes MC/DC different.

The independence criterion is the key property of MC/DC. Simply put, every condition should be able to decide the result of the Boolean expression. While it sounds obvious it is a bit subtle, but I like looking at it from the outside; if a condition cannot decide the outcome, why is it there, and is that really what we intended? What it means is that we disallow strongly coupled conditions which could force us to redesign. Such a rewrite usually means a simplification, which is undeniably a good thing. In An Investigation of Three Forms of MCDC Appendix B, Chilenski shows that MC/DC is a weak measure of equivalence class coverage. Since many bugs happen at value boundaries it makes sense to pay some extra attention here.

References

• A Control System For Logical Block Diagnosis With Data Loading, M. Senko, Communications of the ACM, April 1960
• Automation of program debugging, K. Jacoby and H. Layton, Proceedings of the 1961 16th ACM national meeting
• Systematic Mistake Analysis of Digital Computer Programs, J. C. Miller and C. J. Maloney, Communications of the ACM, February 1963
• Applicability of modified condition/decision coverage to software testing,
• A Practical Tutorial on Modified Condition/Decision Coverage, K. J. Hayhurst et al., 2001
• An Investigation of Three Forms of the Modified Condition Decision Coverage (MCDC) Criterion, J. Chilenski, 2001
• Rationale for Accepting Masking MC/DC in Certification Projects (CAST-6), Certification Authorities Software Team, 2001
• Go To Statement Considered Harmful, E. W. Dijkstra, Communications of the ACM, March 1968