# Mesa3D — CWE-407 Disclosure Brief
**2026-03-27 · Patch available — awaiting upstream merge**

## Finding

One O(n²) defect in Mesa3D's NIR compiler parallel copy resolver. The dead-node scan in `parallel_copy_resolve` uses O(N²) membership checking at 7 sites in `src/compiler/nir/`. Patch ready for upstream review.

## The Defects

**mesa-0001 (PATCHED — HIGH):** `src/compiler/nir/` (7 sites)

```c
/* parallel_copy_resolve — dead-node scan per resolve: */
/* At 7 sites in nir/ — all follow this pattern: */
for (unsigned i = 0; i < num_copies; i++) {
    /* Check if destination is a source of another copy: */
    for (unsigned j = 0; j < num_copies; j++) {  /* O(N²) nested scan */
        if (copies[i].dest == copies[j].src) { ... }
    }
}
/* O(N²) dead-node detection across 7 sites */
```

Nested loop dead-node scan O(N²) per parallel copy resolve at 7 NIR compiler sites. Fix: `bitset` membership for O(N). **7 sites affected.**

## Complexity Proof

For N copies per parallel copy resolve:
- Nested scan: O(N²) per resolve call
- Fixed: `bitset` of source IDs → O(N) per resolve
- 7 sites compound the impact
- **7 sites measured.**

## Impact

All Mesa3D users — Mesa is the open-source OpenGL/Vulkan graphics driver used in Linux (AMD, Intel, ARM GPU stacks), Android, and embedded systems. NIR (New Intermediate Representation) is the core IR for Mesa's shader compiler. Parallel copy resolution runs during shader compilation for every draw call that compiles a new shader. Complex shaders with many parallel assignments hit O(N²) during compilation. Mesa powers GPU compute and graphics on billions of devices.

## The Fix

Replace nested scan with `bitset` membership at all 7 sites:

```c
/* Before: O(N²) nested scan */
for (unsigned i = 0; i < num_copies; i++) {
    for (unsigned j = 0; j < num_copies; j++) {
        if (copies[i].dest == copies[j].src) { ... }
    }
}

/* After */
/* CWE-407 fix: bitset of source IDs for O(N) dead-node detection. */
uint64_t src_bitset = 0;
for (unsigned j = 0; j < num_copies; j++) {
    src_bitset |= (1ULL << copies[j].src);
}
for (unsigned i = 0; i < num_copies; i++) {
    if (src_bitset & (1ULL << copies[i].dest)) { ... }
}
```

## Patch

`defects/mesa/patch/mesa-0001-nir-parallel-copy-bitset.patch`

## What We Ask

1. Confirm receipt and assign a GitHub Security Advisory or issue reference.
2. Validate the patch against your NIR compiler and shader test suite.
3. Assess CVE eligibility — O(N²) shader compilation overhead at 7 sites in Mesa NIR.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

Contact: see cover email. This brief is confidential until coordinated disclosure.
