PaperlayerView exact revision on arXiv

Source-linked AI summary

An Extensive Empirical Study on Evaluation Metrics for Combinatorial Interaction Testing

Lisha Qin, Chenhui Cui, Tao Li, Rubing Huang, Shikai Guo, Lei Ma

arXiv:2610.02560v1cs.SE

TL;DR

Choosing among available metrics for evaluating combinatorial test suites remains an open challenge. The paper surveys black-box metrics and studies their fault-detection correlations across projects and scenarios; its overall ranking identifies VCC as the best evaluated predictor.

  • Problem

    No prior study had systematically addressed how to select among the many metrics for assessing or selecting candidate combinatorial test suites.

    Source: §1 · p. 3

  • Method

    The paper surveys black-box metrics and their complexity, then studies correlations with fault-detection effectiveness across eight projects, 32 scenarios, and 295,624 suites.

    Source: §1 · p. 3, §7 · p. 37

  • Results

    The overall ranking identifies Value Combination Coverage (VCC) as the best-performing predictor among the evaluated candidates.

    Source: §7 · p. 37

  • Takeaways & Limitations

    VCC offers the strongest predictive capability among the evaluated candidates under a ranking that also considers computational overhead.

    Source: §7 · p. 37

    The study simplifies input parameter models and uses Hamming distance exclusively for all distribution-based metrics.

    Source: §5.6.1 · p. 36

Abstract

from arXiv · show

Combinatorial interaction testing (CIT) is a black-box testing method that has received extensive attention in both research and practice over recent years. Its primary objective is to construct an effective combinatorial test suite that detects software failures caused by parameter interactions. As a fundamental component of the CIT testing process, the evaluation metric plays a critical role in assessing and comparing combinatorial test suites, as well as in evaluating various test generation techniques. For CIT practitioners, selecting an appropriate evaluation metric is both important and challenging, given the wide variety of available options. Nevertheless, no prior work has systematically addressed this problem. To fill this gap, this paper first provides a comprehensive survey of black-box evaluation metrics for combinatorial test suites, offering rigorous definitions, clear classifications, illustrative examples, and complexity analyses. We then conduct an extensive empirical study involving eight open-source projects, encompassing 32 test scenarios and 295,624 combinatorial test suites. In this study, we examine the correlation between each static evaluation metric and fault-detection effectiveness using two correlation measures. Experimental results show that the Value Combination Coverage (VCC) metric serves as a valid predictor for test-suite evaluation. However, distribution-based metrics generally incur lower computational costs than interaction coverage-based ones. The choice of an appropriate metric should also account for the test suite's inherent properties, as these characteristics can substantially influence the effectiveness of the evaluation. Finally, we provide practical guidelines to assist CIT practitioners in selecting suitable evaluation metrics for assessing or comparing combinatorial test suites.

1 Introduction

CIT reduces the cost of exhaustive testing by covering selected parameter-value combinations, but practitioners still face an unresolved choice among evaluation metrics. This paper surveys black-box metrics, studies their relationship to fault detection, and offers selection guidance.

1 Introduction

  • CIT tests selected parameter-value combinations rather than all possible combinations, trading testing effectiveness against efficiency.Prior evidence cited in the introduction reports that 2-wise testing detected over 70% of faults and 3-wise testing approximately 90%.Source: §1 · p. 2
  • Evaluation metrics guide judgments of CIT effectiveness or efficiency and help select among candidate test suites.The paper focuses on evaluating CIT techniques through their test suites, not on evaluating the SUT after CIT.Source: §1 · p. 2
  • The study surveys black-box evaluation metrics, analyzes their complexity, tests metric–fault-detection correlations, and provides selection guidelines.The empirical study covers eight open-source projects, 32 scenarios, and 295,624 test suites.Source: §1 · p. 3
  • The paper addresses the lack of prior work on choosing among the many available metrics for assessing or selecting candidate suites.It focuses on black-box measures because CIT treats the SUT as a processor without requiring access to source code or internal workings.Source: §1 · pp. 2–3

2 Background

The background defines the valid input space and the test objects used in CIT, then explains covering arrays and test-case ordering. These concepts establish what candidate suites contain and how their cases may be prioritized.

2 Background

  • The background introduces the input parameter model, test suite, and test sequence as the core objects for the subsequent discussion.The paper later uses shortened terms such as “test suite” for “combinatorial test suite.”Source: §2 · p. 3, §2.2.2 · p. 6

2.1 Input Parameter Model

  • An input parameter model records the SUT’s parameters, their possible values, and any constraints; only assignments satisfying those constraints are valid.The model is represented as IPM(P, V, R), with R holding constraints among parameter values.Source: §2.1 · p. 4

2.2.1 Combinatorial Test Suite.

  • A combinatorial test suite is any subset of the valid test space, while a λ-wise covering array covers every valid λ-wise value combination at least once.The example’s 2-wise covering array uses 9 of 34 valid test cases to cover all valid 2-wise combinations.Source: §2.2.1 · p. 5

2.2.2 Combinatorial Test Sequence.

  • A test sequence fixes the execution order of a suite’s cases, enabling prioritization when limited resources prevent running them all.Prioritization methods either reorder cases within an existing suite or account for priority during suite generation.Source: §2.2.2 · p. 6

3 Black-box Metrics for Evaluating Test Suites

The section organizes black-box evaluation around test-suite properties and relates suite metrics to sequence evaluation. It surveys interaction-coverage metrics, including variants designed to distinguish suites or account for different strengths.

3 Black-box Metrics for Evaluating Test Suites

  • The survey defines test-suite metrics and connects each property-based measure to test-sequence evaluation through an accumulated curve.For suites, the property count can be measured directly; for sequences, the paper uses the accumulated property rate, with a linear connection by default.Source: §3 · pp. 6–7

3.1 Interaction Coverage-Based Metrics

  • VCC measures the proportion of valid λ-wise value combinations covered, while VID assesses coverage relative to the maximum possible for a suite of that size.VID can further compare suites tied at 100% VCC; the surveyed interaction-coverage metrics also include BVCC and tuple density.Source: §3.1 · p. 8, §3.1.2 · p. 8

3.1.4 Tuple Density.

  • Tuple density evaluates a λ-wise covering array using its (λ+1)-wise coverage, but, like BVCC, applies only to covering arrays.The paper motivates this strength because higher-strength combinations grow exponentially, while (λ+1)-wise coverage can indicate higher-strength coverage.Source: §3.1.4 · p. 9

3.1.5 Weighted Multiple Value Combination Coverage.

  • WMVCC accounts for multiple strengths, using weights assigned in advance to combine coverage across strengths.The paper describes equal, random, and empirical weight schemes; its empirical scheme assigns progressively smaller weights to higher strengths.Source: §3.1.5 · p. 9, §3.1.4 · p. 9
  • PCC measures covered value combinations within a specific parameter combination, while SVCC and (q, λ)-completeness summarize parameter combinations meeting full-coverage or threshold criteria.At q = 1.0, (q, λ)-completeness reduces to SVCC.Source: §3.1.6 · p. 10, §3.1.7 · p. 10

3.2 Distribution-Based Metrics

The section describes distribution-based metrics that assess test-case spread or value frequencies, followed by mutation-based metrics that assess fault detection. It distinguishes static metrics from the program mutation score, which requires execution.

3.2 Distribution-Based Metrics

  • Six distribution-based metrics are surveyed: discrepancy, dispersion, diversity, similarity, novelty score, and divergence.They assess test-case distribution using locations, distances, or parameter-value occurrences.Source: §3.2 · p. 10

3.2.1 Discrepancy.

  • Discrepancy measures how densely test cases occupy subdomains, with smaller values indicating a more even distribution.The paper defines subdomains within the test space and evaluates the test cases located in them.Source: §3.2.1 · pp. 10–11

3.2.2 Dispersion.

  • Dispersion tracks the largest empty spherical region around a test case, whereas diversity sums nearest-neighbor distances; smaller dispersion and higher diversity indicate better distribution.The paper uses Hamming distance for its dispersion calculations.Source: §3.2.2 · p. 11, §3.2.3 · p. 11

3.2.4 Similarity.

  • Similarity aggregates distances between distinct test-case pairs, while novelty averages distances to ε nearest neighbors and generalizes similarity and diversity.Novelty reduces to similarity when ε = |T| − 1 and to diversity when ε = 1.Source: §3.2.4 · p. 11, §3.2.5 · pp. 11–12

3.2.6 Divergence.

  • Divergence compares observed parameter-value frequencies with an ideal uniform distribution using χ²-divergence in this study.A larger divergence value indicates a more effective test suite under the metric’s stated assumption of equal value frequencies.Source: §3.2.6 · p. 12

3.3.1 Program Mutation Score.

  • Mutation-based metrics score tests by the proportion of non-equivalent mutants killed; PMS measures program faults detected by executing the suite.PMS is also called fault-detection effectiveness.Source: §3.3 · p. 12, §3.3.1 · p. 13

3.3.2 Input-parameter-model Mutation Score.

  • IMS applies mutation analysis to an input-parameter model by altering constraints and checking whether suite tests trigger the faulty constraints.The paper illustrates the metric’s calculations for an example suite, while excluding PMS because it requires program information.Source: §3.3.2 · pp. 13–14, Figure 3 · p. 13

3.3 Mutation-Based Metrics

  • Only PMS is dynamic because it requires real-time SUT execution; the other evaluation metrics are static and do not require execution.Static metrics can be computed without executing the SUT.Source: §3.3.2 · p. 14

3.4 Complexity Analysis for Calculating Static Evaluation Metrics

The complexity analysis focuses on static metrics computable from test suites and input-parameter models. It separates storage costs from computation costs and compares metrics by category and required information.

3.4 Complexity Analysis for Calculating Static Evaluation Metrics

  • The analysis evaluates static-metric complexity using a two-layer structure for storing and searching λ-wise value combinations.The first layer indexes parameter combinations; the second stores coverage counts for their derived value combinations.Source: §3.4 · p. 14, §3.4.1 · p. 15

3.4.2 Space Complexity Analysis.

  • Space costs vary by metric: interaction-coverage metrics store combinations, while distribution metrics generally store test cases or neighbor data, and IMS also stores faulty constraints.Discrepancy additionally stores sampled subdomains; dispersion, diversity, and similarity use O(k × n) space, while novelty stores ε neighbors.Source: §3.4.2 · pp. 15–16

3.4.3 Time Complexity Analysis.

  • Time costs include building and updating the combination structure for interaction metrics, while distribution metrics incur metric-specific costs such as pairwise distances or nearest-neighbor searches.IMS checks faulty constraints against test cases, and the analysis summarizes per-metric space and time complexities in Table 3.Source: §3.4.3 · pp. 16–18

4 Experimental Methodology

The methodology compares static evaluation metrics against fault-detection effectiveness while measuring their computational cost. It varies programs, scenarios, fault sets, and test-suite construction to support this comparison.

4.1 Research Questions

  • Five research questions compare metrics within and across interaction-coverage, distribution-based, and mutation-based categories, and examine effectiveness correlations and computational efficiency.The questions also test interaction-coverage strength choices and whether multiple-strength metrics outperform single-strength metrics.Source: §4.1 · pp. 19–20

4.2 Basic Framework

  • The experiment extracts each program’s IPM, creates scenarios and test suites, measures static metric values and cost, executes suites against faults, and analyzes correlations.Metric evaluation is constrained to 24 hours per suite.Source: §4.2 · pp. 20–21

4.3 Subject Programs

  • Eight programs span command-line utilities and larger configurable systems, using previously studied IPMs to reduce potential bias.The programs are FLEX, GREP, GZIP, MAKE, SED, BUSYBOX, DRUPAL, and LINUX KERNEL.Source: §4.3 · p. 21

4.4 Faults Used

  • Fault effectiveness uses verified mutation faults for the five SIR programs and previously collected real faults for BUSYBOX, DRUPAL, and LINUX KERNEL.Equivalent, duplicate, and subsumed mutants are removed from the SIR fault sets.Source: §4.4 · pp. 21–22

4.5 Test Scenarios

  • Four parameter-selection proportions (0.4, 0.6, 0.8, and 1.0) yield 36 scenarios across nine programs; omitted parameters receive defaults, and only detectable faults are evaluated.Scenarios with omitted parameters may exclude faults that require non-default values for those parameters.Source: §4.5 · p. 22

4.6 Test Suite Construction

  • Random and adaptive-random construction generate suites of sizes 2–50, with up to 100 suites per size and 295,624 suites overall.Adaptive construction selects candidates maximizing their minimum Hamming distance from previously generated cases.Source: §4.6 · p. 22, §4.6.1 · p. 22, §4.6.2 · pp. 22–23

4.7 Selected Evaluation Metrics under Comparison

  • The comparison selects metrics from interaction-coverage, distribution-based, and mutation-based categories, with parameter assignments specified for applicable metrics.Some interaction-coverage metrics are excluded because they apply only to covering arrays, duplicate another mechanism, or focus on a single parameter combination; IMS uses mutated constraints.Source: §4.7 · pp. 23–24

4.8 Correlation Analysis

  • Metric values are paired with fault-detection effectiveness and assessed using R2 and distance correlation; execution overheads are also measured.Experiments run on a 16-core Intel Xeon Silver 4314 machine with 125GB RAM, Ubuntu 22.04.4 LTS, and Java 21.0.11.Source: §4.8 · p. 24, §4.8.2 · p. 24, §4.9 · p. 25

5 Results

The results compare metric correlations with fault-detection effectiveness across interaction-, distribution-, and mutation-based metrics, then assess their computational overhead and study validity. Overall, VCC is the strongest predictor, while metric effectiveness and cost vary with strength and test-suite generation approach.

5.1 Answer to RQ1: Effectiveness Comparisons of ICBM Metrics

  • Single-strength settings usually outperformed multiple-strength settings, with VCC best at λ=3 (score 2.09); WMVCC was the exception, favoring multiple strengths.Across metrics, effectiveness varied substantially with strength; most performed well at λ=2 or 3, while WMVCC’s multiple-strength mechanism performed better.Source: §5.1.1 · pp. 28–29, §5.1.2 · pp. 29–30

5.2 Answer to RQ2: Effectiveness Comparisons of DBM Metrics

  • Discrepancy had the highest correlation across scenarios and generation approaches, closely followed by novelty; discrepancy was robust for RC, while novelty was stronger for ARC.Discrepancy measures how evenly test cases are distributed across subdomains; novelty reflects test-suite sparseness, aligning with ART’s spatial-diversity strategy.Source: §5.2 · pp. 30–32

5.3 Answer to RQ3: Effectiveness Comparisons of MBM Metrics

  • IMS correlations tended to rise with parameter count, but the six-suite SED-TS1 scenario had correlation 0.0; the authors recommend IMS for complex, large-parameter test suites.The authors note that R² may be less valid for relative metrics when relationships are nonlinear.Source: §5.3 · p. 33

5.4 Answer to RQ4: Effectiveness Comparisons of All Metrics

  • VCC ranked first among the investigated metrics, with a score of 1.35 versus 1.91 for the best distribution-based metric; it outperformed discrepancy at strengths λ=2–6.The paper concludes that VCC is the most effective predictor for comparing combinatorial test suites.Source: §5.4 · p. 34, Table 16 · p. 34

5.5 Answer to RQ5: Efficiency Comparisons

  • Discrepancy’s 405,358.32 ms runtime greatly exceeded diversity’s 85.65 ms; overall, ICBM metrics cost significantly more than DBM metrics.The discrepancy calculation requires 1,000 repetitions; ICBM cost reflects processing many parameter combinations.Source: §5.5 · pp. 35–36

5.6 Threats to Validity

  • External validity is bounded by simplified parameter models, Hamming distance for all DBM metrics, and a limited set of subject programs.For internal validity, timeouts may constrain scalability; scripts were manually cross-validated on small examples. Construct validity used R² and R to measure correlation.Source: §5.6.1 · p. 36, §5.6.2 · p. 36, §5.6.3 · p. 36

6 Practical Guidelines

The guidelines favor evaluation metrics according to predictive performance, computational overhead, and the properties of the test suite. They recommend VCC for prediction, while noting distinct considerations for single-strength metrics, DBMs, and complex suites.

6 Practical Guidelines

  • When computational overhead is ignored, VCC is the most suitable metric; within ICBMs, it balances high effectiveness with minimal overhead.Source: §6 · p. 37
  • Single-strength ICBMs generally outperform multiple-strength counterparts and are recommended as valid predictors for test-suite evaluation.WMVCC requires multiple-strength evaluation, but its performance remains dependent on VCC baseline metrics.Source: §6 · p. 37
  • DBM metric selection should align with the test-suite generation approach because generation approaches influence the subsequent evaluation.The authors recommend matching the metric to the suite's properties for more reliable and accurate assessment.Source: §6 · p. 37
  • IMS is recommended for high-complexity suites, particularly those with numerous parameters or constraints.The recommendation is based on IMS's strong predictive capability for subjects with many parameters.Source: §6 · p. 37
  • DBMs other than Discrepancy are preferable to ICBMs when time efficiency matters because they have lower computational overhead.Source: §6 · p. 37

7 Conclusions and Future Work

Across eight projects, the study found VCC performed best among evaluated metrics, while DBMs generally had low computational cost and single-strength metrics were more cost-effective than multiple-strength metrics. It identifies extensions to the study as future work.

7 Conclusions and Future Work

  • VCC performed best among the evaluated candidates, while DBMs generally incurred low computational cost.Source: §7 · p. 37
  • Single-strength metrics were more cost-effective than multiple-strength metrics, and IMS was highly suitable for subjects with numerous parameters.Source: §7 · p. 37
  • Future work could evaluate more metrics across broader sets of programs and test suites, including more intricate and larger-scale programs.Source: §7 · p. 37
  • The comparative performance of individual metrics and aggregated metric groups for predicting test-suite quality remains unexamined.Source: §7 · p. 37
  • The authors identify evaluation of suites generated through alternatives such as search-based tools or LLMs as another direction for future work.Source: §7 · p. 38

A Correlation Values for ICBM

Appendix A reports correlation values for selected top-performing ICBM metrics under RT and ART. It selects the final strength results using the lowest correlation across strengths.

A Correlation Values for ICBM

B Correlation Values for Novelty

Appendix B presents correlation values for Novelty across different assignments under RT and ART, using both R2 and R values.

B Correlation Values for Novelty

C Rankings of Correlation Values

Appendix C catalogs correlation-value rankings across metrics and testing approaches. Rank 1 denotes the highest correlation; 0 marks cases not evaluated because of strength constraints or a 24-hour execution limit.

C Rankings of Correlation Values

D Computation Time of ICBM Metrics

Appendix D reports computation times for ICBM metrics across strengths λ=1–6. It identifies strength constraints and timeouts as reasons a subject may be unevaluated.

D Computation Time of ICBM Metrics

Loading 2610.02560v1…