65 lines
2.1 KiB
Markdown
65 lines
2.1 KiB
Markdown
# UNDF: UNDF-2026-000000475
|
||
# nodejs-0001 — CWE-407 in Module._resolveFilename paths dedup
|
||
|
||
**Severity:** MEDIUM
|
||
**File:** `lib/internal/modules/cjs/loader.js`
|
||
**Symbol:** `Module._resolveFilename` — `ArrayPrototypeIncludes(paths, lookupPaths[j])`
|
||
|
||
## Defect
|
||
|
||
When `require.resolve(id, { paths: [...] })` is called with an explicit `paths`
|
||
array of length P, the implementation deduplicates lookup paths using a linear
|
||
scan of the accumulator array:
|
||
|
||
```js
|
||
for (let i = 0; i < options.paths.length; i++) { // O(P)
|
||
const lookupPaths = Module._resolveLookupPaths(request, fakeParent); // O(L)
|
||
for (let j = 0; j < lookupPaths.length; j++) { // O(L)
|
||
if (!ArrayPrototypeIncludes(paths, lookupPaths[j])) { // O(P*L) scan of accumulator
|
||
ArrayPrototypePush(paths, lookupPaths[j]);
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
`_resolveLookupPaths` returns up to ~20 node_modules ancestor directories per
|
||
input path. The accumulator `paths` grows to P×L entries. Each
|
||
`ArrayPrototypeIncludes` call scans the entire accumulator: O(P×L) per check,
|
||
called P×L times total → **O(P²×L²)** overall.
|
||
|
||
At P=50 input paths and L=10 lookup paths per entry, the accumulator reaches
|
||
500 entries and the dedup loop performs ~250,000 comparisons instead of ~500.
|
||
|
||
## Fix
|
||
|
||
Replace the accumulator array + linear scan with a `Set` for O(1) membership:
|
||
|
||
```js
|
||
const pathsSet = new Set();
|
||
const paths = [];
|
||
|
||
for (let i = 0; i < options.paths.length; i++) {
|
||
const path = options.paths[i];
|
||
fakeParent.paths = Module._nodeModulePaths(path);
|
||
const lookupPaths = Module._resolveLookupPaths(request, fakeParent);
|
||
|
||
for (let j = 0; j < lookupPaths.length; j++) {
|
||
if (!pathsSet.has(lookupPaths[j])) { // O(1)
|
||
pathsSet.add(lookupPaths[j]);
|
||
ArrayPrototypePush(paths, lookupPaths[j]);
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
## Complexity
|
||
|
||
| Scenario | Before | After |
|
||
|---|---|---|
|
||
| P=50 paths, L=10 lookup paths each | O(P²×L²) = ~250k ops | O(P×L) = ~500 ops |
|
||
| Ratio at P=50, L=10 | 500× | 1× |
|
||
|
||
## Source location
|
||
|
||
`lib/internal/modules/cjs/loader.js` — `Module._resolveFilename`, the
|
||
`ArrayIsArray(options.paths)` / non-relative branch, lines ~1408–1414.
|