Comparing White-box and Black-box Test Prioritization

Christopher Henard*, Mike Papadakis*, Mark Harman+, Yue Jia+, and Yves Le Traon*

*Interdisciplinary Centre for Security Reliability and Trust (SnT), University of Luxembourg, Luxembourg
+University College London (UCL), Gower Street, London
Contact: *{firstname.lastname}@uni.lu,+{firstname.lastname}@ucl.ac.uk

Resources regarding the paper

• Empirical study data
• Additional Results
• White-box approaches
• Black-box approaches
• FAQ

Empirical study data

• Browse or Download the 5 subject programs (v0 to v5 and v0_gcov (instrumented version)).
• Browse or Download the regression test suites and inputs of the 5 subject programs.
• Browse or Download the outputs on V0 for the 5 subject programs and each test case.
• Browse or Download the prioritized test suite for the 5 subject programs and all the runs. Each file per run contains the test case indices.
• Browse or Download the input models for the subject programs.
• Browse or Download the mutants for the subject programs.

Additional Results

• WB approaches: results for Table 3 (p-values and A12 metric). Each approach has 2500 values (100 runs x 5 versions x 5 programs) that are compared against the 2500 values of another approach. The stars indicate that the value is lower than 2.2E-16.

  Comparison	p-value	A12
  AS VS TS	0.0*	0.75
  TB VS TS	0.0*	0.40
  TB VS AS	0.0*	0.18
  AB VS TS	0.0*	0.75
  AB VS AS	0.25	0.51
  AB VS TB	0.0*	0.82
  TB VS TS	0.50	0.51
  TB VS AS	0.0*	0.29
  TB VS TB	0.0*	0.64
  TB VS AB	0.0*	0.29
  AB VS TS	0.0*	0.73
  AB VS AS	0.0*	0.40
  AB VS TB	0.0*	0.79
  AB VS AB	0.0*	0.38
  AB VS TB	0.0*	0.69
  ASS VS TS	0.0*	0.75
  ASS VS AS	0.10	0.49
  ASS VS TB	0.0*	0.81
  ASS VS AB	0.0*	0.48
  ASS VS TB	0.0*	0.71
  ASS VS AB	0.0*	0.59
  ASB VS TS	0.0*	0.75
  ASB VS AS	0.39	0.51
  ASB VS TB	0.0*	0.82
  ASB VS AB	0.78	0.50
  ASB VS TB	0.0*	0.72
  ASB VS AB	0.0*	0.62
  ASB VS ASS	0.01	0.52
  SD VS TS	0.0*	0.76
  SD VS AS	0.0*	0.38
  SD VS TB	0.0*	0.83
  SD VS AB	0.0*	0.36
  SD VS TB	0.0*	0.74
  SD VS AB	0.07	0.49
  SD VS ASS	0.0*	0.39
  SD VS ASB	0.0*	0.37
  BD VS TS	0.0*	0.77
  BD VS AS	7.8E-14	0.44
  BD VS TB	0.0*	0.83
  BD VS AB	0.0*	0.43
  BD VS TB	0.0*	0.72
  BD VS AB	0.03	0.52
  BD VS ASS	4.5E-09	0.45
  BD VS ASB	0.0*	0.43
  BD VS SD	0.0*	0.58



• BB approaches: results for Table 3 (p-values and A12 metric). Each approach has 2500 values (100 runs x 5 versions x 5 programs) that are compared against the 2500 values of another. In the paper, the t-W approach gathers the values obtaine dfor t=2 to 4, thus having 7500 values. Here, the detailed results for each t-value are presented. The stars indicate that the value is lower than 2.2E-16.

  Comparison	p-value	A12
  3-W VS 2-W	0.41	0.49
  4-W VS 2-W	0.0*	0.48
  IMD VS 2-W	0.22	0.49
  TIMM VS 2-W	2.9E-16	0.57
  AIMM VS 2-W	0.0*	0.58
  MiOD VS 2-W	0.0*	0.84
  MaOD VS 2-W	0.0*	0.57
  ID-NCD VS 2-W	0.80	0.50
  ID-Lev VS 2-W	3.9E-05	0.53
  I-TSD VS 2-W	7.1E-11	0.45
  O-TSD VS 2-W	0.0*	0.62
  4-W VS 3-W	0.02	0.48
  IMD VS 3-W	0.57	0.50
  TIMM VS 3-W	0.0*	0.57
  AIMM VS 3-W	0.0*	0.59
  MiOD VS 3-W	0.0*	0.84
  MaOD VS 3-W	0.0*	0.58
  ID-NCD VS 3-W	0.23	0.51
  ID-Lev VS 3-W	1.2E-07	0.54
  I-TSD VS 3-W	2.8E-08	0.45
  O-TSD VS 3-W	0.0*	0.63
  IMD VS 4-W	0.07	0.51
  TIMM VS 4-W	0.0*	0.59
  AIMM VS 4-W	0.0*	0.61
  MiOD VS 4-W	0.0*	0.84
  MaOD VS 4-W	0.0*	0.60
  ID-NCD VS 4-W	0.0*	0.53
  ID-Lev VS 4-W	8.1E-15	0.56
  I-TSD VS 4-W	0.0*	0.47
  O-TSD VS 4-W	0.0*	0.64
  TIMM VS IMD	0.0*	0.57
  AIMM VS IMD	0.0*	0.61
  MiOD VS IMD	0.0*	0.85
  MaOD VS IMD	0.0*	0.58
  ID-NCD VS IMD	0.10	0.51
  ID-Lev VS IMD	5.7E-08	0.54
  I-TSD VS IMD	6.3E-12	0.44
  O-TSD VS IMD	0.0*	0.64
  AIMM VS TIMM	0.69	0.50
  MiOD VS TIMM	0.0*	0.87
  MaOD VS TIMM	0.04	0.48
  ID-NCD VS TIMM	1.6E-12	0.44
  ID-Lev VS TIMM	4.9E-05	0.47
  I-TSD VS TIMM	0.0*	0.39
  O-TSD VS TIMM	2.5E-08	0.55
  MiOD VS AIMM	0.0*	0.83
  MaOD VS AIMM	0.11	0.49
  ID-NCD VS AIMM	0.0*	0.43
  ID-Lev VS AIMM	4.2E-11	0.45
  I-TSD VS AIMM	0.0*	0.36
  O-TSD VS AIMM	2.8E-16	0.57
  MaOD VS MiOD	0.0*	0.10
  ID-NCD VS MiOD	0.0*	0.10
  ID-Lev VS MiOD	0.0*	0.09
  I-TSD VS MiOD	0.0*	0.14
  O-TSD VS MiOD	0.0*	0.17
  ID-NCD VS MaOD	5.0E-08	0.46
  ID-Lev VS MaOD	1.1E-07	0.46
  I-TSD VS MaOD	0.0*	0.37
  O-TSD VS MaOD	0.0*	0.60
  ID-Lev VS ID-NCD	0.44	0.51
  I-TSD VS ID-NCD	1.8E-06	0.46
  O-TSD VS ID-NCD	0.0*	0.63
  I-TSD VS ID-Lev	0.0*	0.41
  O-TSD VS ID-Lev	0.0*	0.63
  O-TSD VS I-TSD	0.0*	0.66



• Test suite execution time per program:

  Program	Test Suite Exec. Time (s)
  Grep	26
  Sed	8
  Flex	23
  Make	15
  Gzip	9



• Ratio of the mean prioritization time to the test suite for the three best white-box and blakc-box approaches:

  	White-box			Black-box
  Program	AB	ASS	ASB	4-W	IMD	I-TSD
  Grep	104%	0.5%	0.5%	1,824%	7.5%	2,430.5%
  Sed	47.5%	1.25%	1.25%	3,936.25%	8.75%	3,627.5%
  Flex	154.8%	0.87%	0.43%	363.5%	8.26%	1,957.4%
  Make	16.7%	0.7%	0.7%	40%	35.3%	28.5%
  Gzip	11.1%	1.1%	1.1%	1,260%	3.33%	388.9%
  Avg	83.5%	0.9%	0.8%	1,484.8%	12.6%	1,686.6%

White-box approaches

• Executable jar and source code of all the approaches
• To use the prioritization approaches, run one of the following command depending on the approach you would like to run:

  		java -jar Prioritization.jar TS testSuiteFile gcovFilesDir
  		java -jar Prioritization.jar AS testSuiteFile gcovFilesDir
  		java -jar Prioritization.jar TB testSuiteFile gcovFilesDir
  		java -jar Prioritization.jar AB testSuiteFile gcovFilesDir
  		java -jar Prioritization.jar TM testSuiteFile gcovFilesDir
  		java -jar Prioritization.jar AM testSuiteFile gcovFilesDir
  		java -jar Prioritization.jar ASS testSuiteFile gcovFilesDir spanningStatementsFile
  		java -jar Prioritization.jar ASB testSuiteFile gcovFilesDir spanningBranchesFile
  		java -jar Prioritization.jar SD testSuiteFile statementMatrixFile
  		java -jar Prioritization.jar BD testSuiteFile branchMatrixFile
  		

  For instance, you can run TS with the following command:

  
  		java -jar Prioritization.jar TS test_suites/grep/grep.tests wb_info/grep_wbinfo_v0/
  		

  Each command prints on the standard output the prioritized test suite by printing the test case indices. The two following points give more information regarding the testSuiteFile, gcovFilesDir, statement/branchMatrixFile and spanning/BranchesFile.
• testSuiteFile: these are the .tests files of each subject program (can be found here)
• gcovFilesDir: this is the directory containing the .gcov files for each program, e.g., wb_info/grep_wbinfo_v0/ (can be found here)
• statement/branchMatrixFile: To extract the branches or statements from the test suite and gcov files, use the ExtractBranchesStatements (source) tool as follows:

  		java -jar ExtractBranchStatements branch testSuiteFile gcovFilesDir
  		java -jar ExtractBranchStatements statement testSuiteFile gcovFilesDir
  		

  For instance, the command

  		java -jar ExtractBranchStatements statement test_suites/grep/grep.tests wb_info/grep_wbinfo_v0/ > statementMatrixFile
  		

  will print to the statementMatrixFile the list of statements along with their corresponding test case index.
• spanningStatements/BranchesFile: To calculate the spanning statements or branches from extracted branches or statements, use the spanning perl script on the extracted branches or statements. For instance, the command

  		perl subsume.pl statementMatrixFile > spanningStatementsFile
  		

  will print to the spanningStatementsFile the list of spanning statements.

Black-box approaches

• Executable jar and source code of all the approaches
• To run the approaches:
  • T-W: run the following command:

     		java -jar Prioritization.jar t-W testSuiteFile casaTestSuiteFile t
    		

    For instance, you can use the following command for 3-wise:

    		java -jar Prioritization.jar t-W test_suites/grep/grep.tests input_models/grep.casa 3
    		

  • IMD: run the following command:

     		java -jar Prioritization.jar IMD testSuiteFile casaTestSuiteFile
    		

    For instance, you can use the following command:

    		java -jar Prioritization.jar IMD test_suites/grep/grep.tests input_models/grep.casa
    		

  • TIMM and AIMM: run one of the following command:

     		java -jar Prioritization.jar TIMM testSuiteFile modelMutantsMatrixFile
    		java -jar Prioritization.jar AIMM testSuiteFile modelMutantsMatrixFile
    		

    The modelMutantsMatrixFile contains the list of input model mutants killed by each test case (one line is a mutant and a test index killing it). For instance, you can use the following command for TIMM:

    		java -jar Prioritization.jar TIMM test_suites/grep/grep.tests input_models/modelMutantMatrix_grep
    		

  • MiOD and MaOD: run one of the following command:

    		java -jar Prioritization.jar MiOD testSuiteFile outputDir
    		java -jar Prioritization.jar MaOD testSuiteFile outputDir
    		

    where outputDir is the directory containing the output of the program for each test case. For instance, you can use the following command for MaOD:

    		java -jar Prioritization.jar MaOD test_suites/gzip/gzip.tests outputs_v0/gzip_outputs/
    		

  • ID-NCD and ID-Lev: run one of the following command:

    		java -jar Prioritization.jar ID-NCD testSuiteFile
    		java -jar Prioritization.jar ID-Lev testSuiteFile
    		

    For instance, you can use the following command for ID-NCD:

    		java -jar Prioritization.jar ID-NCD test_suites/gzip/gzip.tests
    		

  • I-TSD: run the following command:

    		java -jar Prioritization.jar I-TSD testSuiteFile
    		

    For instance:

    		java -jar Prioritization.jar I-TSD test_suites/gzip/gzip.tests
    		

  • O-TSD: run the following command:

    		java -jar Prioritization.jar O-TSD testSuiteFile outputDir
    		

    For instance:

    		java -jar Prioritization.jar O-TSD test_suites/gzip/gzip.tests outputs_v0/gzip_outputs/
    		

FAQ

• Why do dome approaches take a lot of time to perform? If you need to run each approach several times, you might consider modifying the code to separate what takes time, which is generally the setup part (calculation of the distances, etc.) from the acutal prioritization. Sinc ethe setup is generally common to all the runs, it can be calculated once and loaded up at each run. The prioritization itself shouldn't take so long.
• Regarding the seeded faults and the followed process. We used a recent advance in mutation testing: subsuming mutants. As explained in Section 3.2 of the paper, these subsuming mutants are strong and are representative of dozens of other mutants that they subsume. Mutant subsumption is, essentially, thus a smarter way of exactly covering multiple mutants with a single subsuming mutant. Additional details regarding mutant subsumption and the threats to validity that mutation-based faults impose please consult the following ISSTA paper:
  
  Mike Papadakis, Christopher Henard, Mark Harman, Yue Jia, and Yves Le Traon. Threats to Validity of Mutation-Based Test Assessment, in the International Symposium on Software Testing and Analysis (ISSTA'16), 2016.