java-topology/whitepaper/outreach/vscode.md

Visual Studio Code — CWE-407 Disclosure Brief

2026-04-13 · Patches available — awaiting upstream merge

Finding

Four O(n²) defects in VS Code across the extension gallery service, extension dependency resolution, settings sync merge, and configuration override comparison. All patched. All use Array.includes() inside loops — O(n) linear scan where Set.has() gives O(1).

The Defects

vscode-0001 (PATCHED — MEDIUM): src/vs/platform/extensionManagement/common/extensionGalleryService.ts:659

// In getExtensions — fires on every extension gallery query:
const uuids = result.map(r => r.identifier.uuid);
for (const e of extensionInfos) {
    if (e.uuid && !uuids.includes(e.uuid)) {  // O(M) per extension

Extension gallery deduplicates results by UUID using Array.includes(). O(N*M) where N = extension infos, M = results.

vscode-0002 (PATCHED — MEDIUM): src/vs/platform/extensionManagement/common/abstractExtensionManagementService.ts:448

// In getAllDepsAndPacks — fires on every extension install:
const getAllDepsAndPacks = (extension, profileLocation, allDepsOrPacks: string[]) => {
    for (const id of depsOrPacks) {
        if (allDepsOrPacks.includes(id.toLowerCase())) {  // O(D) per dep
            continue;
        }
        allDepsOrPacks.push(id.toLowerCase());

Recursive dependency/pack traversal accumulates IDs into an array, checking includes() on every iteration. O(D²) where D = total transitive dependencies + packs.

vscode-0003 (PATCHED — MEDIUM): src/vs/platform/userDataSync/common/extensionsMerge.ts:259 (+ 7 other files)

// In compare() — fires on every settings sync:
const added = toKeys.filter(key => !fromKeys.includes(key));  // O(N*M)
const removed = fromKeys.filter(key => !toKeys.includes(key));  // O(N*M)

Eight compare() functions across the userDataSync system compute set-differences using filter + includes(). O(N*M) per compare. Affects extensions, settings, global state, snippets, keybindings, prompts, and profiles sync.

vscode-0004 (PATCHED — LOW-MEDIUM): src/vs/platform/configuration/common/configurationModels.ts:1248

// In configuration compare — fires on every config change:
const addedOverrideIdentifiers = toOverrideIdentifiers.filter(
    key => !fromOverrideIdentifiers.includes(key)  // O(N) per identifier
);

Configuration override comparison uses includes() for set-difference of language-specific override identifiers. O(N*M) where N, M = override identifier counts.

Complexity Proof

vscode-0001: At N=200 extensions, M=200 results:

• Defective: 200 × 200 = 40,000 comparisons
• Fixed: 200 × 1 = 200 Set lookups
• ~100× speedup.

vscode-0002: At D=50 transitive dependencies:

• Defective: 50 × 49 / 2 = ~1,225 comparisons
• Fixed: 50 hash lookups
• ~25× speedup.

vscode-0003: At N=500 settings keys:

• Defective: 500 × 500 = 250,000 comparisons (per sync file)
• Fixed: 500 × 1 = 500 Set lookups
• ~250× speedup. Multiply by 8 sync file types.

vscode-0004: At N=30 language overrides:

• Defective: 30 × 30 = 900 comparisons
• Fixed: 30 × 1 = 30 Set lookups
• ~30× speedup.

Impact

VS Code serves tens of millions of developers worldwide. The settings sync defects (0003) fire on every sync merge across 8 different data types — every time a developer opens VS Code on a second machine, all 8 compare functions run. The extension gallery defect (0001) fires on every marketplace query. The dependency resolution defect (0002) fires on every extension install. Users with many extensions (50-200 is typical for professional developers) and many settings hit all four paths regularly.

The settings sync path (0003) compounds: 8 separate compare() functions each run O(N²) independently. A developer with 500 settings, 200 extensions, 100 keybindings, and 50 snippets runs 8 quadratic comparisons on every sync.

The Fix

All four fixes convert Arrays to Sets before the membership-testing loop.

vscode-0001:

// Before
const uuids = result.map(r => r.identifier.uuid);
if (e.uuid && !uuids.includes(e.uuid))

// After — O(1) Set lookup
const uuids = new Set(result.map(r => r.identifier.uuid));
if (e.uuid && !uuids.has(e.uuid))

vscode-0002: Thread a Set<string> through the recursive calls:

if (!seenDepsOrPacks) { seenDepsOrPacks = new Set(allDepsOrPacks); }
if (seenDepsOrPacks.has(lowerId)) { continue; }
seenDepsOrPacks.add(lowerId);

vscode-0003: Convert both key arrays to Sets before filtering:

const fromKeysSet = new Set(fromKeys);
const toKeysSet = new Set(toKeys);
const added = toKeys.filter(key => !fromKeysSet.has(key));
const removed = fromKeys.filter(key => !toKeysSet.has(key));

Patch

Fixes available: defects/vscode/patch/vscode-0001-0004-*.patch

Four patches across extensionGalleryService.ts, abstractExtensionManagementService.ts, extensionsMerge.ts (+ 7 sibling sync files), and configurationModels.ts.

vscode-0001: 100× speedup at 200 extensions. vscode-0002: 25× at 50 dependencies. vscode-0003: 250× at 500 settings keys (× 8 sync types). vscode-0004: 30× at 30 overrides.

What We Ask

Patches are ready for review.

1. Confirm receipt and assign a GitHub issue reference (microsoft/vscode).
2. Assess severity — vscode-0003 fires on every settings sync across 8 data types; vscode-0001 fires on every marketplace query.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the VS Code team in the public disclosure. Preferred acknowledgment format welcome.

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