Combinatorial Coverage

Definition

Combinatorial coverage is a measure of the proportion of all possible combinations of input parameter values that have been exercised by a given test set or data sample. The concept originated in combinatorial interaction testing (CIT) in software testing, where it is used to identify faults by systematically varying parameter combinations. In its simplest form, combinatorial coverage reaches 100% when every possible combination of values for the parameters under test has been applied. For example, a two-input NAND gate's combinatorial coverage reaches 100% when all four possible input combinations (00, 01, 10, 11) are applied.

Application in Hardware (Post-Silicon) Validation

Combinatorial coverage has been used as a building block in the broader discussion of coverage metrics for validating hardware logic. In post-silicon validation of System-on-Chip (SoC) designs, coverage analysis is widely used to quantify validation effectiveness. Traditional pre-silicon code-based coverage metrics—such as statement, branch, and path coverage—are not directly applicable to post-silicon environments because silicon houses hardware logic rather than RTL source code. Applying such metrics requires additional on-chip logic to capture and extract coverage information, which adds design time and cost.

To address this, alternative metrics based on data-flow among interconnected blocks have been proposed. Data-flow-based coverage metrics generalize functionality by measuring the data streams between nodes, enabling validation effectiveness to be quantified across functionally differing units in post-silicon validation.

Application in Machine Learning

Combinatorial coverage has been systematically adapted from software testing to characterize test and training sets for machine learning (ML) models, offering a holistic approach to ML training and testing. The adaptation applies combinatorial interaction testing principles to simple features derived from inputs and outputs of ML models, rather than to the internal structure of models such as neural network internals. This makes the approach usable by parties who supply training and test data but lack intellectual property rights to the models themselves.

Documented applications include:

• Selecting test sets that stress ML model performance.
• Selecting training sets that lead to robust model performance.
• Selecting data for fine-tuning models to new domains.

The MNIST handwritten digits dataset has been used to demonstrate these applications, showing combinatorial coverage can be used to identify subsets that exercise model behavior in meaningful ways.

Combinatorial Coverage Metrics for ML

Combinatorial coverage metrics have been explored as an alternative to distribution-based metrics for assessing whether operational or test data differs from training data. Out-of-distribution (OOD) data is known to increase the probability of ML classification errors, so metrics that anticipate where errors are likely are valuable.

Set-Difference Coverage Metrics (SDCCMs)

Set-difference coverage metrics (SDCCMs) measure the difference between coverage achieved on test/operational data and coverage achieved on training data. SDCCMs have been shown to correlate with classification error, but the strength of this correlation has been observed to be highly dataset-dependent.

Metric Learning to Improve Coverage Metrics

Metric learning—a machine learning technique that learns latent spaces in which data from different classes are pushed further apart—has been shown to improve the ability of SDCCMs to anticipate classification error. In a study across six open-source datasets, metric learning increased the difference between SDCCMs computed on correctly classified data and SDCCMs computed on incorrectly classified data. Paired t-tests validated the statistical significance of these findings, supporting the conclusion that metric learning improves coverage metrics' ability to identify when OOD data is likely to degrade model performance.

Relation to Coverage Metrics

Combinatorial coverage is one component within the broader category of coverage metrics. Standardized coverage metrics are an active research area across domains including hardware validation and machine learning, with ongoing work to innovate metrics that quantify functionality rather than just structural elements.

Advantages and Criticisms

Prior work has criticized the use of combinatorial coverage in machine learning. Recent work has addressed these criticisms directly, providing a rebuttal that advocates the use of coverage metrics in ML applications on the basis that they operate on observable input/output features rather than requiring access to model internals.