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

## Finding

One compile-time O(n²) defect in the Lua 5.x parser. `searchupvalue()` in `lparser.c:360` performs an O(N) linear scan over upvalue names for every upvalue reference during compilation, causing O(N²) total for functions with many upvalues. Patch ready for upstream review.

## The Defects

**lua-0001 (PATCHED — HIGH):** `lparser.c:360`

```c
/* searchupvalue() — per variable reference at compile time: */
static int searchupvalue(FuncState *fs, TString *name) {
    int i;
    Upvaldesc *up = fs->f->upvalues;
    for (i = 0; i < fs->nups; i++) {  /* O(N) scan per reference */
        if (eqstr(up[i].name, name))
            return i;
    }
    return -1;
}
```

Linear scan over all N upvalues per reference. Every variable reference in an inner function that might be an upvalue calls `searchupvalue()`. For N upvalues and R references: **O(R × N)** compile-time cost.

## Complexity Proof

For N upvalues in a closure:
- Per variable reference: O(N) scan
- Total: O(R × N) — scales with upvalue count and reference count
- Fixed: fixed-size hash table in `FuncState` for O(1) per reference

## Impact

All Lua code with closures that capture many variables from enclosing scopes. Lua is the most widely embedded scripting language — used in game engines (LÖVE, Roblox, World of Warcraft), web servers (nginx/OpenResty), embedded systems, and configuration systems. Large closure-heavy Lua programs (game scripts, configuration DSLs) compile faster with the fix. The defect is compile-time only — no runtime overhead.

## The Fix

Add a fixed-size hash table in `FuncState` for O(1) upvalue lookup:

```c
/* Before */
/* O(N) linear scan per variable reference */
static int searchupvalue(FuncState *fs, TString *name) {
    for (int i = 0; i < fs->nups; i++) {
        if (eqstr(fs->f->upvalues[i].name, name)) return i;
    }
    return -1;
}

/* After */
/* CWE-407 fix: fixed-size hash table in FuncState for O(1) upvalue lookup. */
static int searchupvalue(FuncState *fs, TString *name) {
    /* hash(name->hash % UPVALUE_HASH_SIZE) → index */
    return upvalue_hash_lookup(&fs->upvalue_hash, name);
}
```

## Patch

`defects/lua/patch/lua-0001-parser-upvalue-hashtable.patch`

## What We Ask

1. Confirm receipt and assign a GitHub Security Advisory or issue reference.
2. Validate the patch against your parser and compiler test suite.
3. Assess CVE eligibility — compile-time overhead for closure-heavy Lua programs.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

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