71 lines
2.7 KiB
Markdown
71 lines
2.7 KiB
Markdown
# 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.
|