Mihaela Mihaljevic
20b96fbfd4
enforceNestingLimit (Parser.Events.swift) bounds PHYSICAL collection depth in the raw event stream, since it counts sequenceStart/ mappingStart events directly. It does nothing against an anchor-expansion bomb: a handful of shallow, small anchors each aliased many times, each alias nested inside the next, keeps raw event depth at a constant 2 per line while the LOGICAL tree an alias resolves to grows exponentially in the number of alias levels. A 25-level, fan-out-9 document (~1.5KB) expands past 9^25 logical nodes; before this fix, parse accepted it in under 2ms, and any full-tree walk downstream (JSON representability checking, JSON writing, validation) never terminated. Added a total expanded-node budget, charged incrementally as the document streams through the composer rather than by walking anything: every scalar charges 1, every completed container charges 1 for its own wrapper (children already charged their own cost as they completed), and every alias resolution charges the target's CACHED expanded size -- computed once when the anchor was defined, looked up in O(1). This makes a nested bomb's true compounded size visible arithmetically within a few alias levels, without ever materializing or walking the exponential tree it would otherwise produce. A document with genuinely wide but non-exponential alias reuse (the same small anchor referenced thousands of times at one level, no nesting) stays comfortably inside the budget and parses normally. Verified via the full existing test suite (674 tests, all passing, zero regressions -- including the YAML Test Suite conformance corpus and the tagged round-trip corpus), two new tests proving the bomb is rejected (in under 2ms) and that wide non-exponential fan-out still parses, and swiftformat/swiftlint --strict clean on all five touched files. PureYAML.Parsing.EventComposer and Tagged.EventComposer (two other, separate composer implementations in this package, used by the diagnostic-validation and tagged-parsing entry points respectively) share the same architectural gap and would benefit from the same fix, but are not reachable from the confirmed exploit path this change closes -- disclosed, not fixed here.
27 lines
1.6 KiB
Swift
27 lines
1.6 KiB
Swift
extension PureYAML.Parsing.EventStreamComposer {
|
|
/// Charges `cost` new expanded nodes against the document's remaining
|
|
/// ``EventStreamComposer/expandedNodeBudget``, throwing `expansionTooLarge` the moment it
|
|
/// runs out.
|
|
///
|
|
/// `enforceNestingLimit` (`Parser.Events.swift`) bounds PHYSICAL collection depth in the raw
|
|
/// event stream; it does nothing against an anchor-expansion ("billion laughs") bomb, where a
|
|
/// handful of shallow, small anchors are each aliased many times, each alias nested inside the
|
|
/// next, so the LOGICAL tree an alias resolves to is exponential in the number of alias levels
|
|
/// while the physical document stays kilobytes -- a 25-level, fan-out-9 document already
|
|
/// expands past 9^25 logical nodes.
|
|
///
|
|
/// Called once per scalar, alias resolution, or completed container -- never re-derived from
|
|
/// a walk -- so a bomb is rejected within a few alias levels, long before its true size could
|
|
/// ever be materialized: each charge is the MARGINAL cost this one node adds, with any nested
|
|
/// alias expansion it contains already folded into a prior charge (cached in
|
|
/// ``EventStreamComposer/anchorSizes``) and looked up in O(1), never re-counted here.
|
|
/// ``EventStreamComposer/expandedNodeBudget``'s initial 5,000,000 is far past any real
|
|
/// document's node count.
|
|
mutating func chargeExpansion(_ cost: Int, mark: PureYAML.Parsing.Mark) throws {
|
|
expandedNodeBudget -= cost
|
|
guard expandedNodeBudget >= 0 else {
|
|
throw PureYAML.Parsing.ParseError.expansionTooLarge(line: mark.line, column: mark.column)
|
|
}
|
|
}
|
|
}
|