# Is it always possible to get MC/DC coverage on an $n$-input Boolean function with $n + 1$ test cases?

In software engineering, there is a coverage metric for testing called modified condition/decision coverage, or MC/DC for short. This metric is well-known in the avionics industry due to showing up in the DO-178B and DO-178C standards as part of the testing requirements for Level A airborne software.

One way of thinking about MC/DC is in terms of Boolean functions. For an $n$-input Boolean function $f : \{0, 1\}^n \rightarrow \{0, 1\}$, MC/DC coverage is achieved if we can show that each of the $n$ input variables of $f$ has an independent effect on the output of $f$. That is, we have to exhibit pairs of input strings $x$ and $y$ such that $f(x) \neq f(y)$ and $x$ and $y$ differ only at a single position $i$. MC/DC coverage is achieved if we can find such pairs of strings for each input position $0 \leq i < n$.

Now, test rig time on avionics hardware is often expensive. Companies have a strong desire to minimize the number of test cases that have to be run on their devices to achieve certification.* Obviously, if it is possible to achieve MC/DC coverage at all on some $n$-input function, then it can be done with $2n$ inputs: simply list all $n$ pairs of inputs individually. However, it is often possible to reuse the same input string to show the effect of multiple input variables. For example, if $f$ is a 4-input AND gate, then we can show the effect of all 4 input variables by evaluating $f$ at just 5 input strings: $\{1111, 0111, 1011, 1101, 1110\}$. This works because the necessary 4 pairs are $[\{1111, 0111\}, \{1111, 1011\}, \{1111, 1101\}, \{1111, 1110\}]$.

This prompts the question in the title: Is it always possible to get MC/DC coverage on an $n$-input Boolean function with $n + 1$ test cases (assuming that it is possible to get MC/DC coverage at all)?

To state this question more formally, I will use the following definitions:

• Call two $n$-bit strings $i$-adjacent if they have Hamming distance $1$, differing only at position $i$ ($0 \leq i < n$).
• Call an $n$-input Boolean function $f$ dependent on all of its inputs if for all $0 \leq i < n$ there exist $i$-adjacent strings $x$ and $y$ such that $f(x) \neq f(y)$.
• Let $f$ be an $n$-input Boolean function, and let $T$ be a list of $n$ unordered pairs of $n$-bit strings. Then $T$ gets MC/DC coverage on $f$ if for all $0 \leq i < n$, we have $T_i = \{v_1, v_2\}$, $v_1$ and $v_2$ are $i$-adjacent, and $f(v_1) \neq f(v_2)$.

Then my question is as follows: For any $n$-input Boolean function $f$ that is dependent on all of its inputs, does there always exist a list $T$ that gets MC/DC coverage on $f$ such that $|\bigcup_{0 \leq i < n} T_i| = n + 1$?

I have tried for a while to construct a counterexample function, but in every case I have found that either I could contrive a set of $n + 1$ test cases that works, or else the function ends up not actually depending on one or more of its input variables. For an example of a simple function that has an $n + 1$ solution that is not immediately obvious, consider the function $f(a, b, c, d) = (a \vee b) \wedge (c \vee d)$. The 5-element set $\{1010, 0010, 0110, 1000, 1001\}$ gets MC/DC coverage on this function, because we have $[\{1010, 0010\}, \{0010, 0110\}, \{1010, 1000\}, \{1000, 1001\}]$.

I have also made some minor efforts to prove the statement using subtrees of hypercube graphs, but I feel like my combinatorics background is not strong enough (or I'm missing something obvious). It's easy enough to check all the cases by hand for $n \leq 2$, but for $n \geq 3$ I'm stuck.

UPDATE: I have run a computer search with an SMT solver and determined that there are no counterexamples with $n \leq 4$.
UPDATE 2: Here is a restatement of the problem in terms of hypercube graphs. Let $G$ be the $n$-dimensional hypercube graph, and let $f$ be a vertex coloring of $G$ with two colors (not requiring that adjacent vertices have different colors). Let $G'$ be the subgraph of $G$ obtained by removing any edge whose vertices are both the same color, so that the vertex coloring is proper. Suppose $G'$ contains an edge along each dimension. Then, does there always exist a set of $n + 1$ vertices such that the induced subgraph of $G'$ on these vertices also contains an edge along each dimension?
Also, here is a proof that it is not possible to use fewer than $n + 1$ vertices for any $f$. Suppose that we have a subgraph $H$ of the $n$-dimensional hypercube graph with $n$ edges and $k \leq n$ vertices. Since there are not more vertices than edges, $H$ must contain a cycle. But if $H$ contains a cycle, then it has to contain two edges that are both along the same dimension. Since there are only $n$ edges and at least two of them are along the same dimension, $H$ can't have edges along all $n$ dimensions. Note that this is purely a pigeonhole principle argument; it does not in any way depend upon $f$.
• the negation of your statement for a given function $f : B^n \to B$ is : for any fixed binary string $a_1,\ldots ,a_n$ there exists $i$ such that $f(a_1,\ldots,a_{i-1},\lnot a_i,a_{i+1}, \ldots,a_n) = f(a_1,\ldots,a_{i-1},a_i,a_{i+1}, \ldots,a_n)$ which implies that .... – reuns Feb 8 '16 at 21:47