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.
65 lines
2.8 KiB
Swift
65 lines
2.8 KiB
Swift
@testable import PureYAML
|
|
import Testing
|
|
|
|
@Suite("Parsing Aliases")
|
|
struct ParsingAliasTests {
|
|
@Test("Resolves anchors and aliases through the event composer")
|
|
func test_anchorsAndAliases() throws {
|
|
let root = try requireMapping(PureYAML.parse(
|
|
"""
|
|
first: &item {name: Example}
|
|
second: *item
|
|
""",
|
|
))
|
|
|
|
#expect(root?["first"] == root?["second"])
|
|
guard case let .mapping(second)? = root?["second"] else {
|
|
recordIssue("expected aliased mapping")
|
|
return
|
|
}
|
|
#expect(second["name"] == .string("Example"))
|
|
}
|
|
|
|
/// The regression this guards: `enforceNestingLimit` (Parser.Events.swift) bounds PHYSICAL
|
|
/// collection depth in the raw event stream, which does nothing against an anchor-expansion
|
|
/// ("billion laughs") bomb -- a handful of shallow, small anchors 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 like this one expands past 9^25 logical nodes; before this fix,
|
|
/// `PureYAML.parse` accepted it in under 2ms (the nesting cap never fires, since raw event
|
|
/// depth per line stays at 2) and any full-tree walk downstream (JSON representability
|
|
/// checking, JSON writing, validation) never terminated.
|
|
@Test("Rejects a nested anchor-expansion bomb instead of accepting an astronomically large tree")
|
|
func test_rejectsAnchorExpansionBomb() {
|
|
var yaml = "a0: &a0 [x, x, x]\n"
|
|
for level in 1 ... 25 {
|
|
let previous = "*a\(level - 1)"
|
|
let refs = Array(repeating: previous, count: 9).joined(separator: ", ")
|
|
yaml += "a\(level): &a\(level) [\(refs)]\n"
|
|
}
|
|
yaml += "bomb: *a25\n"
|
|
|
|
#expect {
|
|
try PureYAML.parse(yaml)
|
|
} throws: { error in
|
|
guard case .expansionTooLarge = error as? PureYAML.Parsing.ParseError else { return false }
|
|
return true
|
|
}
|
|
}
|
|
|
|
/// The fix must not reject ordinary, non-exponential alias reuse: the same small anchor
|
|
/// referenced many times at ONE level (no nesting) stays comfortably inside the budget.
|
|
@Test("A large but non-exponential alias fan-out still parses")
|
|
func test_wideNonExponentialFanOutStillParses() throws {
|
|
let refs = Array(repeating: "*item", count: 5000).joined(separator: ", ")
|
|
let yaml = "item: &item {name: Example}\nlist: [\(refs)]\n"
|
|
|
|
let root = try requireMapping(PureYAML.parse(yaml))
|
|
guard case let .sequence(list)? = root?["list"] else {
|
|
recordIssue("expected a sequence")
|
|
return
|
|
}
|
|
#expect(list.count == 5000)
|
|
}
|
|
}
|