The MC/DC metric

The Modified condition/decision coverage (MC/DC) metric is one of the “big guns” among the coverage metrics, giving quite good guarantee the covered code is sufficiently tested. Its definition is quite succint (copied from Wikipedia):

  1. Each entry and exit point is invoked.
  2. Each decision takes every possible outcome.
  3. Each condition in a decision takes every possible outcome.
  4. Each condition in a decision is shown to independently affect the outcome of the decision.

Condition vs. decision

Consider the following example (and ignore we can simplify the if):

public static boolean doSomething(boolean a, boolean b, boolean c) {
    if ((a || b) && c) {
        return true;
    } else {
        return false;
    }
}

Here our decision is (a || b) && c. The conditions are the booleans that decision depends on: a, b and c1. Our job is to find how to cover that decision with test cases to guarantee it’s 100% bug-resistant (according to the definition above).

The road to the 100%

The definition gives us a very good understanding what means to have 100% coverage, but not how to get there. Let’s focus on the 4 points in the definition. This will allow us to analyze getting to 100% with a minimal set of test cases.

  1. Covering entry/exit points - That’s easy to achieve. Just write a test case which reaches each return.
  2. Covering every decision outcome - Slightly harder, but still relatively easy - just make sure we get the two different results for each decision.
  3. Covering each condition - Make sure we’ve actually made all the conditions true or false. Easy again!2
  4. “Proving” the result depends on each condition - That’s slightly harder, even when we’re not proving it in the mathematical sense. This is what we’ll focus on.

Minimizing the test cases

OK, we figured out we need to prove the result of the decision is affected by the different conditions, but how to do it with a minimum amount of test cases? I mean less than 2^n3?

We need at least n+1 test cases to cover point 4 of the MC/DC definition for a boolean decision4. How are we going to find these test cases? Note there are many solutions to this problem.

How to figure out the inputs?

I’ll sketch a procedure for informally finding out a set of test cases. This is not an algorithm in the strict sense, it just helps you sort the things out using your intuition.

In other words, this is not a 100% mathematically provable algorithm :)

Step 1 - construct a truth table

Let’s construct a truth table for the doSomething method:

CaseabcDecision
1falsefalsefalsefalse
2falsefalsetruefalse
3falsetruefalsefalse
4falsetruetruetrue
5truefalsefalsefalse
6truefalsetruetrue
7truetruetruefalse
8truetruetruetrue

That are all the 2^n test cases we’d write to test all possible inputs. We’re trying to find a subset of them.

Step 2 - select a test case

Let’s start with a random line, e.g. case 3:

CaseabcDecision
3falsetruefalsefalse

Step 3 - find your next test case

Now we want to change a condition and verify it affects the decision. For example, changing c to true would change the result to true (case 4). Add it to the table:

CaseabcDecision
3falsetruefalsefalse
4falsetruetruetrue

Note: You should not necessarily always base the new test case on the last one you’ve added.

Step 4 - repeat

Now repeat step 3 until you get n+1 test cases.

For example, we can now change b to false, changing the decision to false (case 2):

CaseabcDecision
3falsetruefalsefalse
4falsetruetruetrue
2falsefalsetruefalse

Now we have to verify this for a too. Changing it to true would change the decision to true:

CaseabcDecision
3falsetruefalsefalse
4falsetruetruetrue
2falsefalsetruefalse
6truefalsetruetrue

Profit!

Now we have a good set of test cases, ready to be turned into code:

CaseabcDecision
3falsetruefalsefalse
4falsetruetruetrue
2falsefalsetruefalse
6truefalsetruetrue

An indication we’re ready is that for each condition (a,b,c) we have two different decision results for the two values of that condition.

Coincidentally, we have n+1 test cases, which means this is also a minimal set of tests! :)

Footnotes

  1. Of course, these 3 guys needn’t be booleans. They can be any expressions! But it’s easier to treat them as “dumb” booleans, to avoid messing up with too much syntax. 

  2. Unless you have conditions which can never be true (e.g. 1 == 2) or false (e.g. 1 == 1). Then it’s impossible. Sorry! 

  3. Covering all the 2^n inputs will guarantee we’ve covered each theoretically possible outcomes of the decision. Not always the best idea, though. 

  4. Sketch for an induction proof: For 1 condition we obviously need 2 test cases to verify it affects the decision. Now assume we have n conditions covered by n+1 cases, “proving” these n conditions affect the decision. Adding a new condition will require us to add at least one more test case - we can add one of the values (true/false) for the condition to the existing test cases (without affecting their decision verification), but in order to prove the new condition can change the decision we should add a new test case, ending up with n+2 cases. If we could go on and test the new condition without adding a new test case (just by modifying the existing ones), we’d surely “lose” a test case for another condition.