{"id":"GHSA-4qx8-w7c3-pj3p","summary":"toml-node: Quadratic-complexity DoS via many array-of-tables headers in toml.parse()","details":"## Summary\n\n`toml.parse()` is vulnerable to a quadratic-complexity (O(n²)) denial-of-service via many\narray-of-tables (`[[name]]`) headers. `addTableArray()` in `lib/compiler.js` rescans two\nentire bookkeeping Sets on every `[[name]]` header without pruning unrelated or distinct\nentries, so a document containing n such headers costs O(n²) compiler work. A ~321KB document\nof 20,000 distinct-named `[[name]]` blocks takes ~10.3 seconds to parse — a completely\nordinary-looking TOML shape (a flat settings block plus one or more array-of-tables sections),\nnot a contrived edge case. This is a separate, unpatched code path from the previously fixed\nstack-overflow DoS (`GHSA-82x6-q7mm-w9cf`) and requires no key nesting or dotted keys at all.\n\n## Affected component / version\n\n- Package: `toml` (npm), repository `BinaryMuse/toml-node`\n- Function: `addTableArray()` in `lib/compiler.js`\n- Confirmed present in the audited checkout at commit `1b2ac40` (2026-07-16), one commit past\n  the `v5.0.0` tag (a changelog-only change) — i.e. present in `v5.0.0`, the latest release.\n  Not exhaustively verified against every prior release, but the affected function is\n  unrelated to `v5.0.0`'s BigInt/Temporal changes (per `CHANGELOG.md`), so the defect likely\n  predates that release as well.\n\n## Details\n\n`toml.parse(input, options)` (`index.js:5-9`) forwards the caller-supplied string to\n`parser.parse()` and then `compiler.compile()` with no length or structural validation. Every\n`[[name]]` (array-of-tables) header is routed (`reduce()`, `lib/compiler.js:43`) to\n`addTableArray()` (`lib/compiler.js:218-245`), which performs two full linear scans on every\ncall:\n\n```js\nassignedPaths.forEach(function(p) {\n  if (isSameOrSubPath(p, quotedPath)) assignedPaths.delete(p);\n});\nvalueAssignments.forEach(function(p) {\n  if (isSameOrSubPath(p, quotedPath)) valueAssignments.delete(p);\n});\n```\n(`lib/compiler.js:228-233`)\n\n`assignedPaths` and `valueAssignments` accumulate one entry per top-level key/table/array path\never assigned in the entire document. Each scan prunes only entries matching the *currently\nreopened* path via `isSameOrSubPath()` (`lib/compiler.js:319-321`: `path === prefix ||\npath.indexOf(prefix + \".\") === 0`); anything else — an unrelated top-level key, or simply a\n*different* array-of-tables name — is never removed and is rescanned in full on every\nsubsequent `[[name]]` header for the rest of the parse. `Set.prototype.forEach` has no early\nexit, so this is unconditionally O(current Set size) on every call, giving O(n²) total work\nfor n such headers.\n\n## Proof of Concept\n\nThe sharpest reproduction needs no unrelated keys at all — just N array-of-tables headers with\nN *distinct* names, since nothing is ever pruned when no name repeats:\n\n```js\nconst toml = require('toml');\n\nfunction distinctArrayHeaders(n) {\n  let out = '';\n  for (let i = 0; i \u003c n; i++) out += `[[a${i}]]\\nv = 1\\n`;\n  return out;\n}\n\n// ~321 KB input -- takes ~10.3 seconds\ntoml.parse(distinctArrayHeaders(20000));\n```\n\nMeasured timings (Node, direct execution against this repo):\n\n| Variant | n | input size | time |\n|---|---|---|---|\n| N distinct-named `[[name]]` headers, no unrelated keys | 20,000 | 321 KB | 10.3 s |\n| Same N with all-same-name headers (self-pruning, control) | 20,000 | 240 KB | 78 ms |\n| M unrelated top-level keys + N same-name `[[name]]` headers | M=N=32,000 | 906 KB | 42.3 s |\n\nThe ~130x gap between the distinct-name and same-name cases at identical N and comparable\ninput size isolates the mechanism precisely: the bug is unbounded Set growth from never-pruned\nentries, not string length or any other confound. A product-law check (varying M and N\nindependently in the mixed variant) further confirmed genuine O(M·N) complexity.\n\n## Impact\n\nNode.js is single-threaded — this synchronous, multi-second-to-tens-of-seconds compile blocks\nthe entire process event loop, standard uncontested Node.js behavior. The triggering document\nshape — flat top-level config keys plus one or more array-of-tables sections (e.g. a `[db]`\nsettings block plus a `[[servers]]` list) — is unremarkable, common real-world TOML, not an\nedge case. No authentication or special access is required; only the ability to get one TOML\nstring parsed by an application using this library.\n\n## Suggested remediation\n\nAvoid scanning the entire `assignedPaths`/`valueAssignments` Sets on every `[[name]]` header.\nIndex entries by their top-level path segment (e.g. a `Map\u003cstring, Set\u003cstring\u003e\u003e` keyed by the\nfirst key component) so `addTableArray()` only ever scans the bucket relevant to the path\nbeing reopened, in time proportional to that bucket's size rather than the whole document's\naccumulated path count:\n\n```js\nvar assignedByRoot = new Map(); // root segment -\u003e Set\u003cfullPath\u003e\n\nfunction addTableArray(node) {\n  var path = node.value;\n  var root = path[0];\n  var bucket = assignedByRoot.get(root) || new Set();\n  bucket.forEach(function(p) {\n    if (isSameOrSubPath(p, quotedPath)) bucket.delete(p);\n  });\n  // ...rest of addTableArray unchanged, reading/writing the per-root bucket\n  // instead of the global assignedPaths/valueAssignments Sets\n}\n```\n\nAs with the sibling finding, an input-size or table-count limit would also help as\ndefense-in-depth.\n\n## Credit\n\nDiscovered and reported by SecDim Security Research\nsecdim.com | @secdim | security@secdim.com","aliases":["CVE-2026-114141"],"modified":"2026-10-22T16:45:03.724071259Z","published":"2026-10-22T16:38:44Z","database_specific":{"github_reviewed":true,"github_reviewed_at":"2026-10-22T16:38:44Z","nvd_published_at":"2026-10-21T21:17:56Z","cwe_ids":["CWE-407"],"severity":"HIGH"},"references":[{"type":"WEB","url":"https://github.com/BinaryMuse/toml-node/security/advisories/GHSA-4qx8-w7c3-pj3p"},{"type":"ADVISORY","url":"https://nvd.nist.gov/vuln/detail/CVE-2026-114141"},{"type":"WEB","url":"https://github.com/BinaryMuse/toml-node/commit/609c873fffea0a27ebe5b4dd098eed2b3daf3606"},{"type":"PACKAGE","url":"https://github.com/BinaryMuse/toml-node"},{"type":"WEB","url":"https://github.com/BinaryMuse/toml-node/releases/tag/v5.0.1"}],"affected":[{"package":{"name":"toml","ecosystem":"npm","purl":"pkg:npm/toml"},"ranges":[{"type":"SEMVER","events":[{"introduced":"0"},{"fixed":"5.0.1"}]}],"database_specific":{"source":"https://github.com/github/advisory-database/blob/main/advisories/github-reviewed/2026/10/GHSA-4qx8-w7c3-pj3p/GHSA-4qx8-w7c3-pj3p.json","last_known_affected_version_range":"\u003c= 5.0.0"}}],"schema_version":"1.9.0","severity":[{"type":"CVSS_V4","score":"CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N"}]}