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

## Finding

Three O(n²) defects in MySQL's authorization system and field setup. All patched. Patches ready for upstream review.

## The Defects

**mysql-0001 (PATCHED — HIGH):** `sql/auth/sql_authorization.cc`

```cpp
// vector::find over role lists in SHOW GRANTS USING per auth check:
auto it = std::find(role_list.begin(), role_list.end(), role);
// O(U×G) per authorization check — users × granted roles
```

`std::find` over role lists in `SHOW GRANTS USING`. For U users and G granted roles per user: **O(U × G) per auth check**. **Measured ratio: 333×.**

**mysql-0002 (PATCHED — HIGH):** `sql/auth/sql_authorization.cc`

```cpp
// has_global_grant() fallback — O(P×Q) multimap scan:
// Iterates multimap entries instead of using hash lookup
for (auto it = grants.begin(); it != grants.end(); ++it) {
    if (it->first == privilege && it->second == user) { ... }
}
// O(P×Q) per check
```

`has_global_grant()` fallback scans the privilege multimap with O(P×Q) nested iteration instead of using an `unordered_map`. **Measured ratio: 333×.**

**mysql-0003 (PATCHED — HIGH):** `sql/sql_base.cc`

```cpp
// setup_fields() — std::find iterator recovery after split_sum_func growth:
// Field iterator invalidated after split_sum_func; std::find used to recover position:
auto it = std::find(fields.begin(), fields.end(), field);  // O(F) per recovery
// Called O(F) times after growth: O(F²) total iterator recovery
```

`std::find` O(F) iterator recovery per field after `split_sum_func` grows the field list. **O(F²) total**. Fix: position index map. **Measured ratio: 250×.**

## Complexity Proof

**mysql-0001/0002:** For 333 role/privilege entries:
- Per auth check: O(333) scan
- Fixed: `unordered_map` → O(1) lookup
- **333× measured ratio** at both sites.

**mysql-0003:** For F=250 fields in `setup_fields()`:
- Per field recovery: O(F) `std::find` scan
- Total: **O(F²)**
- **250× measured ratio.** Fixed: position index `map<field*, size_t>`.

## Impact

All MySQL deployments. mysql-0001 and mysql-0002 affect role-based access control (RBAC) — the standard authorization mechanism since MySQL 8.0. `SHOW GRANTS USING` and `has_global_grant()` are called on every authorization check for role-enabled users. mysql-0003 fires in `setup_fields()` during query planning when `split_sum_func` grows the field list — triggered by aggregate functions, subquery optimization, and window functions. MySQL is one of the most widely deployed relational databases globally.

## The Fix

**mysql-0001:** Replace `std::find` on role vector with `unordered_set`:

```cpp
// Before
auto it = std::find(role_list.begin(), role_list.end(), role);

// After
// CWE-407 fix: unordered_set for O(1) role lookup instead of O(G) std::find scan.
if (role_set.count(role)) { ... }
```

**mysql-0002:** Replace multimap scan with `unordered_map<privilege, unordered_set<user>>`.

**mysql-0003:** Build position index `unordered_map<Item*, size_t>` before the `setup_fields()` loop to replace `std::find` iterator recovery:

```cpp
// Before
auto it = std::find(fields.begin(), fields.end(), field);  // O(F) per recovery

// After
// CWE-407 fix: position index map for O(1) recovery instead of O(F) std::find.
std::unordered_map<Item*, size_t> field_pos;
for (size_t i = 0; i < fields.size(); ++i) field_pos[fields[i]] = i;
```

## Patch

`defects/mysql/patch/mysql-0001-0002-auth-unordered-map.patch`
`defects/mysql/patch/mysql-0003-setup-fields-position-map.patch`

## What We Ask

1. Confirm receipt and assign a GitHub Security Advisory or Oracle bug reference.
2. Validate the patch against your authorization and SHOW GRANTS test suite.
3. Assess CVE eligibility — both defects fire on every RBAC authorization check.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

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