[llvm-cov][MC/DC][Qualification] No MCDC coverage measured for minimal expressions

[escherle-validas]

No MCDC coverage measured for minimal expressions

Criticality: HIGH

During qualification of MCDC coverage at Validas we found that
no MCDC coverage is measured when there is a boolean term consisting only of one atom.
In the case of a single element MCDC is defined and should be measured.
In the attached example the term "if (v0)" is not instrumented at all for MCDC.
The problem occurs within Rust and C++ (see attached reduced examples).

Rust example

Test_000001.zip

C++ example:

Test_000001.zip

[evodius96]

MC/DC for one condition is trivially deducible from branch coverage. Because MC/DC is really only useful when there are logical operators, and because of the cost of instrumentation, MC/DC was not enabled for single-condition expressions. However, it could be added in the future. This behavior also corresponds to the behavior of other coverage vendors.

[escherle-validas]

To our knowledge CTC can handle this and IMHO it would be great if LLVM Cov could also could deal with it. It is true that MC/DC is trivially deducible from branch coverage, but it requires to do two analysis (instead of one).

[christensson]

According to A Practical Tutorial on Modified Condition/Decision Coverage, NASA/TM-2001-210876, which seems to be widely used as a definition of MC/DC coverage, MC/DC coverage is defined in section 2.3, table 1 as a combination of a few different metrics:

• (a) "Every point of entry and exit in the program has been invoked at least once"
• (b) "Every decision in the program has taken all possible outcomes at least once"
• (c) "Every condition in a decision in the program has taken all possible outcomes at least once"
• (d) "Every condition in a decision has been shown to independently affect that decision’s outcome"

The same thing applies to "Decision Coverage" which is defined as:

• (a) "Every point of entry and exit in the program has been invoked at least once"
• (b) "Every decision in the program has taken all possible outcomes at least once"

llvm-cov reports line coverage, branch coverage and MC/DC coverage. The "branch coverage" is bullet (b) above which clearly is differentiated by name from "Decision Coverage".

The thing is that MC/DC coverage from llvm-cov is really only covering bullet (c) and (d) still having a name that suggests that it follows the MC/DC definition.

Also, the wikipedia article of MC/DC shares the same definition.

[christensson]

To follow-up on my comment above true MC/DC coverage could be calculated from llvm-cov output by combining the following metrics:

• "function coverage" (Bullet (a) in comment above)
• "branch coverage" (Bullet (b) in comment above)
• "MC/DC" (Bullet (c) and (d) in comment above)

[evodius96]

Hi @christensson !

true MC/DC coverage could be calculated from llvm-cov output by combining the following metrics:

Yes, that is precisely the idea. What I have added to llvm-cov is the ability to track features unique to MC/DC with the understanding that a user must also rely on branch coverage to get everything else required by the spec, so there is no need to instrument costly, redundant tracking when these metrics are enabled by the other criteria. Branch coverage also provides instrumentation for things like switch statements and range-based loops. (In llvm-cov, 100% branch coverage implies 100% function coverage, line and region coverage). Branch coverage metrics are included in the summary report by default. I think that perhaps this should understand be made clearer in the documentation (and perhaps also in the visualization, although I'm not sure how yet).

[escherle-validas]

It might be logically correct that MCDC for terms that consist of a single atom can be deduced using Branch coverage. But I think that this is rather error-prone if the user has to analyze this manually and has to check two different metrics. What happens if 100 % MCDC and only 99 % Branch Coverage are reported? In this case I have doubts that the user will notice this coverage gap. So in our opinion it is not a good idea to leave the user with this additional task which could be performed safely and automatically by LLVM cov.

[evodius96]

Hi @escherle-validas

OK -- we'll have to think about how to roll the Branch Coverage metrics into the MC/DC summary, but I think it can be done. I'm not sure I would weight this with HIGH criticality since the information is reported, just not together.

[christensson]

I think the way to approach the problem highlighted by @escherle-validas is to report metrics according to what I interpret as the "standard", see references in my previous comment above.

[chapuni]

Could we introduce "Condition coverage" in llvm-cov?

• Condition on Stmt and CondOp: Counted as "one condition". True when all subconditions are satisfied. Use MC/DC independence pairs for binary logical ops.
• binary logical ops in expr: Handled and counted as "one condition" with MC/DC.
• Switch: Handled whole switch as one condition. True when all cases are satisfied.

I am planning to propose "switch group" in covmap. It will be a variant of Decision and MCDCBranch.
#125407 will make nested Decisions available.

[evodius96]

Hi @chapuni thanks for looking at this!

Could we introduce "Condition coverage" in llvm-cov?

Based on the definition of MC/DC, I think this "Condition coverage" ought to be included as part of overall MC/DC rather than a separate coverage criteria. Basically what users have to do today is look at both the the MC/DC independence pair metric as well as branch coverage. Ideally, MC/DC would include one metric that includes all of that (including switches, as you mention).

[horenmar]

I was surprised by this behaviour this week, when I was experimenting with Clang's source coverage modes and got this output from llvm-cov report with MCDC enabled.

Filename                                                          Functions  Missed Functions  Executed       Lines      Missed Lines     Cover    Branches   Missed Branches     Cover    MC/DC Conditions    Missed Conditions     Cover
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
/... snip .../clang-coverage-test/path-vs-mcdc/path-vs-mcdc.cpp           1                 0   100.00%          19                 0   100.00%           6                 0   100.00%                   0                    0         -
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
TOTAL                                                                     1                 0   100.00%          19                 0   100.00%           6                 0   100.00%                   0                    0         -

It took me a while to figure out that I am not doing anything wrong, Clang just tries to be clever and skips MCDC for simple conditions.

IMO, this is correct

MC/DC for one condition is trivially deducible from branch coverage.

but not particularly helpful. I understand wanting to optimize the instrumentation, but would it be possible to have the llvm-cov tool reconstruct the MCDC information based on the same logic? That would at least reduce the surprise factor for users who see no MCDC coverage of a function/file (because it was optimized away).

----edit----

Looking around, it seems that there isn't enough information for llvm-cov to know whether the profile doesn't contain mcdc information because the binary wasn't mcdc instrumented, or because there were no complex conditions. That means that the reconstruction would have to be heuristics based on either

1. The user asked for MCDC report, trust the user that he had the binary instrumented.
2. Look if the mcdc counters are present for any other condition in the data. If yes, the binary was instrumented. If not, well then 🤷