Test Configuration Coverage & Optimization

Problem Statement

Pigweed supports a vast matrix of configuration options in the embedded space, making exhaustive testing impossible. We need a systematic approach to selecting test configurations that maximizes coverage under fixed compute budgets or minimizes cost.

Context

  • Dimensions:
    • Build Systems: 5+ (Bazel, GN, CMake, etc.)
    • Host OS: Mac, Windows, Linux
    • Host Arch: x86, ARM64
    • Target Arch: RISC-V, ARM Cortex-M, Xtensa, etc.
    • Compiler: Clang/LLVM, GCC
    • Language Standards: C++17, C++20, C++23, Python versions
    • Build Options: Sanitizers (ASAN, TSAN, MSAN), Fuzzers, Optimization levels, Memory configs

Requirements

  1. Input Model:
    • Mutually exclusive parameters (e.g., OS: [Mac, Win, Lin])
    • Hard Constraints (e.g., “Windows does not support BuildSystem=Soong”)
    • Costing Model (e.g., Mac is 50x more expensive than Linux)
    • Explicit Coverage Goals (e.g., “We must cover every OS”, “We must cover every Compiler x CppStd pair”).
  2. Execution/Optimization:
    • Minimize total cost of selected configurations.
    • Guarantee that all explicit coverage goals are met.
    • Identify “Coverage Gaps” (valid options that were skipped).
  3. Scale:
    • Must handle domains with > $10^8$ possible combinations.

Implemented Solution: Two-Phase Optimization

We implemented a Declarative Modeling approach using Google OR-Tools (CP-SAT).

1. Declarative Model

We define the problem using high-level dataclasses in Python, ensuring type safety and validation.

  • Parameter: A dimension of variation (e.g., “Compiler”) with a list of Options.
  • Option: A choice (e.g., “GCC”) with an integer cost.
  • Exclusion: A hard constraint prohibiting specific combinations (e.g., IF OS=Win THEN Compiler!=GCC).
  • PointConstraint: A mandatory requirement to include a specific partial configuration (e.g., MUST HAVE {OS: Win, Target: Qemu32}).
  • CoverageGoal: An explicit request to cover all valid combinations of a subset of parameters (e.g., ["Compiler", "CppStd"]).

2. Large Domain Handling (Sampling)

For small domains (< 200k combinations), we fully enumerate the valid search space. For large domains (e.g., Pigweed's ~80M combinations), full enumeration is intractable. We use Random Constraint-Satisfying Sampling:

  1. Repeatedly sample random values for each parameter.
  2. Filter by is_valid() (checking Exclusion rules).
  3. Collect max_candidates (e.g., 10,000 or 100,000) valid configurations. This pool becomes the domain for the set cover optimizer.

2.5 Constructive Generation (Point Constraints)

Random sampling works well for broad coverage but struggles to find specific “needle in a haystack” configurations. For Point Constraints, we use Constructive Generation:

  1. Explicitly fix the required parameter values.
  2. Randomly sample the remaining parameters until a valid configuration is found.
  3. Inject this configuration into the candidate pool to guarantee feasibility.

3. Optimization (CP-SAT)

We model the selection as a Weighted Set Cover Problem:

  • Variables: Binary select_i for each candidate configuration.
  • Objective: Minimize $\sum (cost_i \times select_i)$.
  • Constraints: For every required interaction (derived from CoverageGoals), ensures $\sum_{c \in CoveringConfig} select_c \ge 1$.

4. Existing Coverage

We support Existing Coverage via the ExistingCoverage dataclass to respect pre-existing test investments (e.g., “This exact config runs in CQ”).

  • Opt-in Partiality: By default, existing configs are Strict (must define all parameters). This catches outdated configs immediately.
  • Partial Configs: Users can explicit opt-in to ExistingCoverage(..., partial=True) for configs that only specify a subset of parameters.
  • Strict Validation: The model validates that all existing configs (full or partial) obey Exclusion constraints and parameter definitions.

Example Output

The solver produces optimal, cost-aware test suites. For example, if “Mac” costs 500 and “Linux” costs 10:

  • It will concentrate mostly on Linux for generic coverage goals.
  • It will pick Mac only when absolutely necessary to satisfy a “Cover every OS” goal or a Mac-specific constraint.

Learnings & Best Practices

Explicit vs. Implicit Coverage

Decision: We moved away from implicit “pairwise coverage of everything” to Explicit Coverage Goals.

  • Why? Implicit pairwise explodes the logic (~$O(N^2)$ constraints) and often forces testing of irrelevant pairs (e.g., Crypto vs RustEdition might not matter).
  • Benefit: Users explicitly state what matters (e.g., CoverageGoal(["Target"]), CoverageGoal(["Compiler", "CppStd"])). This makes the solver faster and the output more meaningful.

Robust Validation

We implemented strict validation in the TestModel:

  • Duplicate Detection: Immediate errors for duplicate parameters or options.
  • Safety: immediate ValueError if a CoverageGoal refers to a typo'd parameter.
  • Feedback: “Unknown parameter ‘FuzzTset’” is better than a silent no-op.
  • Strict Existing Coverage: Configs violating constraints or missing parameters (without partial=True) raise immediate errors.

Integer Costs

Optimizers prefer Integers.

  • We use integer costs (e.g., 10, 500) instead of floats (1.0, 50.0). using floats in Mixed Integer Programming can lead to precision artifacts.
  • We stripped arbitrary scaling factors (* 100) to keep the logic transparent.

Reporting

Don't just solve; Explain.

  • The tool prints a Coverage Gap Report, identifying any parameter options that appear in zero selected configs. This highlights constraints that might be too aggressive (e.g., “Wait, why are we never testing ‘MSAN’? Oh, we excluded it on all platforms!”).

Future Work / Open Questions

  1. Deterministic Sampling:
    • random.choice is non-deterministic across runs.
    • Improvement: Allow a fixed random seed for reproducible builds.
  2. Advanced Exclusion Logic:
    • Current Exclusion is simple (“IF A=x THEN B!=y”).
    • Improvement: Support arbitrary boolean logic expressions (e.g., (A=x OR B=y) IMPLIES (C!=z)).

Design Proposal: TestModel Display

To improve debuggability, we propose a human-readable __str__ format for TestModel that mimics PICT's clarity but captures our specific features (costs, coverage goals, existing_coverage).

Goals

  1. Cleanliness: No quotes, excessive brackets, or repr() artifacts.
  2. Information Density: Show costs only when relevant (non-default).
  3. Readability: Natural language syntax for constraints (IF ... THEN ...).

Proposed Output Format

Parameters:
  OS:            Mac ($50), Win ($50), Linux
  Compiler:      GCC, Clang
  Arch:          x64, arm64
  BuildSystem:   Bazel, GN ($10)

Constraints:
  1. IF OS=Win THEN Compiler!=GCC
  2. IF Arch=arm64 THEN OS!={Win, Linux}

Point Constraints:
  1. {OS=Win, Arch=x64}

Coverage Goals:
  1. (OS, Compiler)
  2. (Arch)

Existing Coverage:
  1. {OS: Linux, Compiler: GCC, Arch: x64, BuildSystem: GN}
  2. {OS: Win} (Partial)

Formatting Rules

  1. Parameters:
    • Align values for quick scanning.
    • Show ($Cost) next to a value only if Cost > 1.
    • Comma-separated values.
  2. Constraints:
    • Format Exclusion rules as IF <Criteria> THEN <Forbidden>.
    • Use Key=Val for single values and Key!={V1, V2} for sets.
  3. Point Constraints:
    • Format as {Key=Val, ...}.
  4. Coverage Goals:
    • Simple tuple format (Param1, Param2, ...) listing the interaction dimensions.
  5. Existing Coverage:
    • Format as simplified dictionaries Key: Val.
    • Append (Partial) tag if partial=True.