Mutation Testing in C and LLVM: Toolset and Examples

SRCIROR: A Toolset for Mutation Testing of C Source Code and LLVM Intermediate Representation Farah Hariri and August Shi ASE 2018 Demo Montpellier, France September 5, 2018 CCF-1409423 CCF-1421503

Mutation Testing Check quality of test suite Mut 1 Mutant Generation Mut 2 Program Run Tests Generated using mutation operators Compute Mutation Score # ??????? ?????? # ??????? ????????? 2

Example (C Language) int max(int arr[], int size) { int i; int max = INT_MIN; for (i = 0; i < size; i++) { if (arr[i] > max) { max = arr[i]; } } return max; } void testSingle() { int arr[1] = {1}; int expected = 1; int actual = max(arr, 1); assert(expected == actual); } Test Passes void testMulti() { int arr[3] = {1, 3, 2}; int expected = 3; int actual = max(arr, 3); assert(expected == actual); } Test Passes 3

Example (C Language) int max(int arr[], int size) { int i; int max = INT_MIN; for (i = 1; i < size; i++) { if (arr[i] > max) { max = arr[i]; } } return max; } void testSingle() { int arr[1] = {1}; int expected = 1; int actual = max(arr, 1); assert(expected == actual); } Test Fails void testMulti() { int arr[3] = {1, 3, 2}; int expected = 3; int actual = max(arr, 3); assert(expected == actual); } Constant Replacement Change 0 to 1 Test Passes 4

Example (LLVM) definei32 @max(i32* %arr, i32 %size) #0 { %1 = alloca i32*, align 8 %2 = alloca i32, align 4 storei32 0, i32* %i, align 4 } void testSingle() { int arr[1] = {1}; int expected = 1; int actual = max(arr, 1); assert(expected == actual); } void testMulti() { int arr[3] = {1, 3, 2}; int expected = 3; int actual = max(arr, 3); assert(expected == actual); } 5

Example (LLVM) definei32 @max(i32* %arr, i32 %size) #0 { %1 = alloca i32*, align 8 %2 = alloca i32, align 4 storei321, i32* %i, align 4 } void testSingle() { int arr[1] = {1}; int expected = 1; int actual = max(arr, 1); assert(expected == actual); } Test Fails Constant Replacement Change 0 to 1 void testMulti() { int arr[3] = {1, 3, 2}; int expected = 3; int actual = max(arr, 3); assert(expected == actual); } Test Passes 6

SRCIROR Mutation testing tool for SRC and IR levels Easier to interpret Only applicable to C language SRCIROR SRC SRC mutants .c file .c file Compilation Compilation command command IR IR Mutation tool for any language that compiles to LLVM Generates many mutants mutants 7

Python script that intercepts compiler commands, redirects to SRCIROR (CC= ) SRC-Level .c file .c file AST Python Wrapper Clang AST Parser AST Matcher Compilation command command Compilation Mutation Opportunities Rewriter SRCIROR (SRC) Mutant .c files Compiler Output new .c mutant files Compiled as normal later Find mutation opportunities on Clang syntax tree Binaries 8

Python script that intercepts compiler commands, redirects to SRCIROR (CC= ) IR-Level .ll bitcode file .c file Python Wrapper Find Mutations LLVM Pass -S -emit-llvm Compilation command Mutation Opportunities Construct Mutants LLVM Pass SRCIROR (IR) Mutant .ll files Compiler Pass for new .ll mutant files Compiled as normal later Force to generate LLVM bitcode Binaries Pass for finding mutation opportunities 9

Mutation Operators Same mutation operators on both levels Arithmetic Operator Replacement Logical Connector Replacement Relational Operator Replacement Integer Constant Replacement Extend SRC operators as Clang AST matchers Extend IR operators as new LLVM passes 10

Preliminary Experiments Evaluate on programs from Coreutils Measure # mutants, equivalent mutants, duplicated mutants, mutation scores Generate covered mutants Trivial Compiler Equivalence1 for equivalent/duplicated mutants 1Mike Papadakis et. al, "Trivial compiler equivalence: A large scale empirical study of a simple, fast and effective equivalent mutant detection technique , ICSE 2015 11

Results (SRC) Program Tests Overhead SRC #M #E E% #D D% #NEND factor 31 32.14 364 12 3.3 37 10.2 315 head 85 54.06 946 43 4.5 123 13.0 780 seq 37 72.96 989 40 4.0 123 12.4 826 stat 68 150.96 1619 72 4.4 246 15.2 1301 unexpand 38 18.02 343 8 2.3 37 10.8 298 Overall 259 328.14 4261 175 4.1 566 13.3 3520 12

Results (IR) Program Tests Overhead IR #M #E E% #D D% #NEND factor 31 20.92 599 60 10.0 64 10.7 475 head 85 157.38 2611 174 6.7 312 11.9 2125 seq 37 431.02 4441 362 8.2 595 13.4 3484 stat 68 562.50 7127 375 5.3 934 13.1 5818 unexpand 38 36.53 1166 54 4.6 214 18.4 898 Overall 259 1208.35 15944 1025 6.4 2119 13.3 12800 13

Results (Scores) Program SRC IR Raw NEND Raw NEND factor 52.5 53.0 20.4 24.8 head 44.0 44.7 8.0 9.7 seq 56.4 58.5 16.2 20.1 stat 16.4 16.5 5.1 5.9 unexpand 65.0 66.4 18.3 22.6 Overall 38.8 40.1 10.2 12.1 14

Conclusion We develop SRCIROR, a mutation testing tool for C, at both SRC and IR levels At SRC level, use Clang to parse, match, and mutate program At IR level, use LLVM passes to mutate bitcode instructions Open-source and publically available https://github.com/TestingResearchIllinois/srciror 15

BACKUP 16

Incorporating Coverage Leverage coverage to only generate mutants on lines that are covered by the tests Use GCov for SRC level Made our custom LLVM pass to find IR level coverage (which IR instructions are covered) 17

Splitting Coreutils Tests Existing Coreutils tests are single big test script for each tool We split each test script into multiple test scripts, each one with one call into the tool Allows for more in-depth mutation analysis per test Artifacts available online: http://mir.cs.illinois.edu/farah/artifacts/coreutils- artifact.tar.gz 18

DELETED 19

SRCIROR Mutation testing tool for C, SRC and IR Same mutation operators for both levels SRC level mutates C syntax directly Easier to interpret Specifically only for C language IR level mutates LLVM IR bitcode Mutation testing for any language that compiles to LLVM Generates many mutants 20