Source-Based Code Coverage Analysis with LLVM
Learn about Source-Based Code Coverage and Branch Coverage, explore LLVM Coverage Visualization, and delve into MC/DC for thorough testing of safety-critical code with LLVM. Discover the limitations of Branch Coverage and how MC/DC can help ensure coverage of critical paths during testing.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
MC/DC: Enabling easy-to-use safety- critical code coverage analysis with LLVM Alan Phipps, Texas Instruments 2022 LLVM Developers Meeting 1
What is Source-based Code Coverage? A measurement for how thoroughly code has been executed during testing Ideally all sections of code have an associated test Un-executed code may be at higher risk of having lurking bugs Presently Supported Coverage criteria (in increasing level of granularity) Function Percentage of code functions executed at least once Line Percentage of code lines executed at least once Region Percentage of code statements executed at least once Branch (Recently added) Percentage of condition branches taken at least once 2
LLVM Coverage Visualization LLVM Coverage Utility (llvm-cov) 3
What is Branch Coverage? Condition A leaf-level boolean expression (cannot be broken down into simpler boolean exprs) if (x == 2) A condition yields a Branch that evaluates to either true or false Decision A boolean expression composed of conditions and zero or more logical operators if ((x == 2) && (y == 4)) A decision without a logical operator is a condition 9| 2|bool foo (int x, int y) { 10| 2| if ((x > 0) && (y > 0)) ------------------ | Branch (10:7): [True: 1, False: 1] | Branch (10:18): [True: 0, False: 1] ------------------ 11| 0| return true; 12| 2| 13| 2| return false; 14| 2|} LLVM Branch Coverage provides a measurement of Condition outcomes. i.e. whether conditions evaluate to both true and false 4
The Limits of Branch Coverage bool test(bool A, bool B, bool C, bool D) { return (A && B) || C; } When testing, how can we know that we ve covered all critical paths? Result A B C A F - F F True:2 False:1 F - T T B False:1 T T - T True:1 C T F T T True:1 False:1 T F F F 100% Branch Coverage leaves out critical paths 5
What is MC/DC? Modified Condition/Decision Coverage A metric pertaining to conditions in a Boolean expression decision in which: Each condition has been shown to affect that decision outcome independently Modified refers to changing the test input to yield a different test path Given n conditions, there are 2n total possible test paths (exponential) Only n+1 test paths required to show MC/DC (linear) 6
Example return ((A && B) || C); Test Vector 1 Result A B C F - F F 2 F - T T 3 T T - T 4 T F T T 5 T F F F MC/DC is achieved if an Independence Pair can be found for each condition As the condition outcome is varied between True/False, the Result also varies True/False All other condition outcomes are held fixed or don t-care (unevaluatable/masked out) 7
Example return ((A && B) || C); Test Vector 1 Result A B C A Pair * F - F F 2 F - T T 3 T T - T * 4 T F T T 5 T F F F MC/DC is achieved if an Independence Pair can be found for each condition As the condition outcome is varied between True/False, the Result also varies True/False All other condition outcomes are held fixed or don t-care (unevaluatable/masked out) 8
Example return ((A && B) || C); Test Vector 1 Result A B C A Pair * B Pair F - F F 2 F - T T 3 T T - T * * 4 T F T T 5 T F F F * MC/DC is achieved if an Independence Pair can be found for each condition As the condition outcome is varied between True/False, the Result also varies True/False All other condition outcomes are held fixed or don t-care (unevaluatable/masked out) 9
Example return ((A && B) || C); Test Vector 1 Result A B C A Pair * B Pair C Pair * F - F F 2 F - T T * 3 T T - T * * 4 T F T T 5 T F F F * MC/DC is achieved if an Independence Pair can be found for each condition As the condition outcome is varied between True/False, the Result also varies True/False All other condition outcomes are held fixed or don t-care (unevaluatable/masked out) 10
Example return ((A && B) || C); Test Vector 1 Result A B C A Pair * B Pair C Pair * F - F F 2 F - T T * 3 T T - T * * 4 T F T T (*) 5 T F F F * (*) MC/DC is achieved if an Independence Pair can be found for each condition As the condition outcome is varied between True/False, the Result also varies True/False All other condition outcomes are held fixed or don t-care (unevaluatable/masked out) 11
LLVM Coverage Visualization + MC/DC Branch Coverage View Condition Aliases C{1, 2, 3, } and Source Location Mapping Actual Executed Test Vectors Calculated Metrics for Expression 13
When is MC/DC really important? Required for safety-critical embedded application development Automotive(ISO 26262 Road vehicles Functional Safety standard) Aviation (DO-178 Aviation standard) Applicable also to Railway, Industrial, Medical, and Space LLVM is being used increasingly in the embedded space Supporting MC/DC in LLVM makes sense to facilitate embedded development 14
What has been done? What can LLVM do? LOG-based MC/DC (most common and very robust) Code is instrumented to track condition outcomes of a test vector Data is output to a file (or stdout) during execution and used as input to a tool Today, LLVM really only has raw profile counter data in memory Counters really aren t suitable to tracking test vector execution, and they don t scale well Goal: Support LOG-based MC/DC without outputting data to a file Leverage clang-based instrumentation to track condition outcomes Efficiently store the data to memory where it can be extracted by coverage tools 16
Design Concept: Bitmap Coverage Objects Track a global bitmap in memory in which each bit represents an executed test vector Instrumented per Boolean expression with two or more conditions Treated like profile counters but handled differently and kept in a separate section in memory Variable-length, depending on number of possible test vectors (between 8 bits and 2n bits) 2-3 conditions: (A && B) || C 8-bits 4 conditions: (A && B) || (C && D) 16-bits 5 conditions: (A && B) || (C && D) || E 32-bits 0 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 We ll limit the number of conditions measured to six to keep everything small 17
How do Bitmap bits map to test vectors? if ( (A && B) || (C && D) ) Test Vector Test Vector Value A B C D A B C D 1 T T - - 1 1 1 0 0 12 2 T F T T 2 1 0 1 1 11 3 T F T F 3 1 0 1 0 10 4 T F F - 4 1 0 0 0 8 5 F - T T 5 0 0 1 1 3 6 F - T F 6 0 0 1 0 2 7 F - F - 7 0 0 0 0 0 Goal: instrument the evaluation of each condition in a Boolean expression The resulting value gives us an index into a global, Decision-level Bitmap 18
How do Bitmap bits map to test vectors? The value of each test vector execution yields an index into a Global bitmap i.e. Each bit in the global mask represents a test vector if ( (A && B) || (C && D) ) Test Vector Value A B C D 1 1 1 0 0 12 2 1 0 1 1 11 3 1 0 1 0 10 Global Bitmap 4 1 0 0 0 8 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 5 0 0 1 1 3 6 0 0 1 0 2 7 0 0 0 0 0 19
How do Bitmap bits map to test vectors? The value of each test vector execution yields an index into a Global Bitmap i.e. Each bit in the global mask represents a test vector if ( (A && B) || (C && D) ) Test Vector Value A B C D 1 1 1 0 0 12 2 1 0 1 1 11 3 1 0 1 0 10 Global Bitmap 4 1 0 0 0 8 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 5 0 0 1 1 3 6 0 0 1 0 2 7 0 0 0 0 0 20
Source Region Mapping (A && B) || (C && D) Introduce a new Decision mapping region type Ties a Boolean expression to source code Contains index of a Decision-level Bitmap Contains number of conditions A T:2,F:3 ID:1 T F B ID:2 T:-,F:3 Extend existing Branch Regions to include IDs Represents Control Flow through conditions F T C T:4,F:- ID:3 F Keep language-specific information away from llvm-cov! Only give it what it needs to do the MC/DC analysis IDs allow llvm-cov to construct list of possible test vectors T D T:-,F:- ID:4 F T 21
Visualization (llvm-cov) Extract the Branch Region IDs and build the list of possible test vectors Test Vector Value A B C D Function (foo) - CodeRegion1 (9:24-10:23) - CodeRegion2 (11:0-11:12) - CodeRegion3 (12:0-14:0) MCDCDecisionRegion: - MCDCDecisionRegion (10:4-10:23) MCDCBranchRegions: - MCDCBranchRegion1 (10:5-10:11) - MCDCBranchRegion2 (10:16-10:22) - MCDCBranchRegion3 (10:27-10:33) - MCDCBranchRegion4 (10:38-10:44) 1 1 1 0 0 12 2 1 0 1 1 11 3 1 0 1 0 10 4 1 0 0 0 8 5 0 0 1 1 3 6 0 0 1 0 2 7 0 0 0 0 0 22
Visualization (llvm-cov) Construct the list of executed test vectors Function (foo) - CodeRegion1 (9:24-10:23) - CodeRegion2 (11:0-11:12) - CodeRegion3 (12:0-14:0) MCDCDecisionRegion: - MCDCDecisionRegion (10:4-10:23) MCDCBranchRegions: - MCDCBranchRegion1 (10:5-10:11) - MCDCBranchRegion2 (10:16-10:22) - MCDCBranchRegion3 (10:27-10:33) - MCDCBranchRegion4 (10:38-10:44) Test Vector Value A B C D 1 1 1 0 0 12 2 1 0 1 1 11 3 1 0 1 0 10 Global Bitmap 4 1 0 0 0 8 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 5 0 0 1 1 3 6 0 0 1 0 2 7 0 0 0 0 0 23
Visualization (llvm-cov) Look for an Independence Pair for each Condition Test Vector Result A B C D 2 T F T T T 3 T F T F F 5 F - T T T 24
Visualization (llvm-cov) Look for an Independence Pair for each Condition Test Vector Result A-Pair A B C D 2 T F T T T - 3 T F T F F - 5 F - T T T - Condition A: No Independence Pair Found 25
Visualization (llvm-cov) Look for an Independence Pair for each Condition Test Vector Result A-Pair B-Pair A B C D 2 T F T T T - - 3 T F T F F - - 5 F - T T T - - Condition B: No Independence Pair Found 26
Visualization (llvm-cov) Look for an Independence Pair for each Condition Test Vector Result A-Pair B-Pair C-Pair A B C D 2 T F T T T - - - 3 T F T F F - - - 5 F - T T T - - - Condition C: No Independence Pair Found 27
Visualization (llvm-cov) Look for an Independence Pair for each Condition Test Vector Result A-Pair B-Pair C-Pair D-Pair A B C D 2 T F T T T - - - * 3 T F T F F - - - * 5 F - T T T - - - Condition D: Independence Pair Found! A-Pair: not covered B-Pair: not covered C-Pair: not covered D-Pair: covered MC/DC Coverage for Expression: 25% 28
Current State of LLVM MC/DC Implementation is complete -- in the process of upstreaming the work! Phabricator Review https://reviews.llvm.org/D136385 Will be included with stock LLVM Source-based Code Coverage But enabled in clang via command-line option clang fprofile-instr-generate fcoverage-mapping fmcdc foo.cc o foo A lot of ways to improve MC/DC and Branch Coverage! Want to be involved? Contact me! a-phipps@ti.com 2020 Branch Coverage Presentation https://www.youtube.com/watch?v=H1hvtJPGWNQ 29
Thank you! Acknowledgements Vedant Kumar, Apple 30
