Mihaela Mihaljevic
bb094aa13c
The streaming-vs-tree differential previously exercised group references only
through the shallow g0/g1 mutual cycle, too weak to gate a future pushdown
content-model matcher whose call/return correctness hinges on deep group
nesting. Add a deep LINEAR group-reference chain (c0 -> ... -> c{chainDepth},
single ref per level so its inlined size is O(depth), not 2^depth) reachable
from any leaf, so the two engines are compared over deep call/return without the
exponential build a doubling chain would trigger. Run divergence-free over the
standing 2000-seed gate and a 60000-seed campaign.
Reconcile docs/release-hurdles.md Part 2 with the deleted positionCap and record
the one remaining structural residual, distinct from occurrence unrolling: the
per-instance NFA build still inlines group references, so a 2^K-inlining schema
makes automaton construction exponential on first instance validation. Document
the pushdown/RTN matcher as the general fix, gated by this hardened differential
(FP-critical: naive sub-model sharing without a stack is unsound).
291 lines
15 KiB
Swift
291 lines
15 KiB
Swift
import Foundation
|
|
import Testing
|
|
@testable import PureXML
|
|
|
|
/// Reproducible xorshift64* generator: a seed that triggers a crash or hang
|
|
/// reproduces the exact input, so a fuzz failure is debuggable rather than a
|
|
/// one-off. Deterministic by construction (no system entropy).
|
|
private struct SeededRNG: RandomNumberGenerator {
|
|
private var state: UInt64
|
|
|
|
init(seed: UInt64) {
|
|
state = seed == 0 ? 0x9E37_79B9_7F4A_7C15 : seed
|
|
}
|
|
|
|
mutating func next() -> UInt64 {
|
|
state ^= state >> 12
|
|
state ^= state << 25
|
|
state ^= state >> 27
|
|
return state &* 0x2545_F491_4F6C_DD1D
|
|
}
|
|
}
|
|
|
|
/// Builds structurally varied XSD schemas and XML instances to exercise the
|
|
/// schema compiler and validator across the input space, not just curated cases.
|
|
/// It deliberately reaches the hang/crash-prone shapes: deep nesting, large and
|
|
/// inverted occurrences, pointless (`maxOccurs="0"`) particles, wildcards,
|
|
/// element/group references and reference cycles, substitution-group chains,
|
|
/// `simpleType` restriction cycles, `complexContent` restrictions (the particle
|
|
/// restriction core), and pathological regex patterns.
|
|
private struct SchemaGenerator {
|
|
var rng: SeededRNG
|
|
|
|
private static let names = ["a", "b", "c", "head", "m1", "m2", "root"]
|
|
private static let leafTypes = ["xs:string", "xs:integer", "xs:int", "xs:decimal", "xs:boolean", "B", "R", "s0", "s1"]
|
|
private static let compositors = ["sequence", "choice", "all"]
|
|
private static let patterns = ["a*", "(a+)+", "[a-", "a{2,1}", #"\p{L}+"#, "(.*)*", "", ".{0,9}"]
|
|
|
|
private mutating func pick<Element>(_ options: [Element]) -> Element {
|
|
options[Int.random(in: 0 ..< options.count, using: &rng)]
|
|
}
|
|
|
|
private mutating func toss() -> Bool {
|
|
Bool.random(using: &rng)
|
|
}
|
|
|
|
/// A random occurrence attribute fragment, including the degenerate and
|
|
/// illegal shapes (zero, unbounded, large, and inverted min > max).
|
|
private mutating func occurrence() -> String {
|
|
switch Int.random(in: 0 ..< 8, using: &rng) {
|
|
case 0: ""
|
|
case 1: " minOccurs=\"0\""
|
|
case 2: " minOccurs=\"0\" maxOccurs=\"unbounded\""
|
|
case 3: " maxOccurs=\"\(Int.random(in: 0 ... 5, using: &rng))\""
|
|
case 4: " minOccurs=\"\(Int.random(in: 0 ... 4, using: &rng))\" maxOccurs=\"\(Int.random(in: 0 ... 6, using: &rng))\""
|
|
case 5: " maxOccurs=\"0\""
|
|
case 6: " minOccurs=\"5\" maxOccurs=\"2\""
|
|
default: " maxOccurs=\"\(pick([10, 250, 1000]))\""
|
|
}
|
|
}
|
|
|
|
private mutating func leaf() -> String {
|
|
switch Int.random(in: 0 ..< 5, using: &rng) {
|
|
case 0: "<xs:element name=\"\(pick(Self.names))\" type=\"\(pick(Self.leafTypes))\"\(occurrence())/>"
|
|
case 1: "<xs:any\(occurrence()) processContents=\"\(pick(["strict", "lax", "skip"]))\"/>"
|
|
case 2: "<xs:element ref=\"\(pick(Self.names))\"\(occurrence())/>"
|
|
// `c0` enters the deep linear chain (deep call/return), `g0`/`g1` the
|
|
// shallow mutual cycle (the visiting-group guard and sibling calls).
|
|
case 3: "<xs:group ref=\"\(pick(["g0", "g1", "c0"]))\"\(occurrence())/>"
|
|
default: "<xs:element name=\"\(pick(Self.names))\"\(occurrence())/>"
|
|
}
|
|
}
|
|
|
|
// A deep LINEAR group-reference chain (c0 -> c1 -> … -> c{chainDepth}): each
|
|
// level references the next exactly once, so its inlined size is O(depth), not
|
|
// 2^depth. It exercises deep group call/return nesting (the correctness a
|
|
// future pushdown content-model matcher hinges on) and keeps the streaming and
|
|
// tree validators differentially compared over it, WITHOUT the exponential
|
|
// inlined blowup a doubling chain would trigger in the per-instance NFA build
|
|
// (that doubling case is pinned separately by SchemaDeterminismGroupBlowupTests).
|
|
#if os(WASI)
|
|
private static let chainDepth = 3
|
|
#else
|
|
private static let chainDepth = 6
|
|
#endif
|
|
|
|
private mutating func chainGroups() -> [String] {
|
|
var groups: [String] = []
|
|
for level in 0 ..< Self.chainDepth {
|
|
let compositor = pick(Self.compositors)
|
|
let element = "<xs:element name=\"\(pick(Self.names))\"\(occurrence())/>"
|
|
let next = "<xs:group ref=\"c\(level + 1)\"\(occurrence())/>"
|
|
// Vary which side the recursive reference sits on so the chain exercises
|
|
// a group call as both a sequence head and a tail (distinct follow sets).
|
|
let body = toss() ? element + next : next + element
|
|
groups.append("<xs:group name=\"c\(level)\"><xs:\(compositor)>\(body)</xs:\(compositor)></xs:group>")
|
|
}
|
|
groups.append("<xs:group name=\"c\(Self.chainDepth)\"><xs:sequence>"
|
|
+ "<xs:element name=\"\(pick(Self.names))\"\(occurrence())/></xs:sequence></xs:group>")
|
|
return groups
|
|
}
|
|
|
|
private mutating func particle(_ depth: Int) -> String {
|
|
if depth <= 0 || toss() {
|
|
return leaf()
|
|
}
|
|
let compositor = pick(Self.compositors)
|
|
let children = (0 ..< Int.random(in: 0 ... 3, using: &rng)).map { _ in particle(depth - 1) }.joined()
|
|
return "<xs:\(compositor)\(occurrence())>\(children)</xs:\(compositor)>"
|
|
}
|
|
|
|
private mutating func modelGroup(_ depth: Int) -> String {
|
|
let compositor = pick(Self.compositors)
|
|
let children = (0 ..< Int.random(in: 0 ... 4, using: &rng)).map { _ in particle(depth - 1) }.joined()
|
|
return "<xs:\(compositor)>\(children)</xs:\(compositor)>"
|
|
}
|
|
|
|
mutating func schema() -> String {
|
|
let qualified = toss()
|
|
let header = "<xs:schema xmlns:xs=\"http://www.w3.org/2001/XMLSchema\""
|
|
+ (qualified ? " targetNamespace=\"urn:t\" xmlns:t=\"urn:t\" elementFormDefault=\"qualified\"" : "")
|
|
+ ">"
|
|
var parts = [header]
|
|
// Named groups that may reference each other (g0 <-> g1 cycle exercises the
|
|
// visiting-group guard).
|
|
parts.append("<xs:group name=\"g0\">\(modelGroup(2))</xs:group>")
|
|
parts.append("<xs:group name=\"g1\">\(modelGroup(2))</xs:group>")
|
|
// The deep linear chain c0 -> … -> c{chainDepth}, reachable from any leaf
|
|
// via `<xs:group ref="c0">`.
|
|
parts.append(contentsOf: chainGroups())
|
|
// Global elements with a substitution chain (m2 -> m1 -> head).
|
|
parts.append("<xs:element name=\"head\" type=\"\(pick(Self.leafTypes))\"/>")
|
|
parts.append("<xs:element name=\"m1\" substitutionGroup=\"head\"/>")
|
|
parts.append("<xs:element name=\"m2\" substitutionGroup=\"m1\"/>")
|
|
// simpleType restriction cycle (s0 <-> s1) plus facets and a pattern.
|
|
parts.append("<xs:simpleType name=\"s0\"><xs:restriction base=\"\(pick(["xs:string", "s1"]))\">"
|
|
+ "<xs:maxLength value=\"\(Int.random(in: 0 ... 9, using: &rng))\"/><xs:pattern value=\"\(pick(Self.patterns))\"/>"
|
|
+ "</xs:restriction></xs:simpleType>")
|
|
parts.append("<xs:simpleType name=\"s1\"><xs:restriction base=\"s0\"/></xs:simpleType>")
|
|
// A base complex type and a complexContent restriction of it (the particle
|
|
// restriction core), plus an extension that may cycle.
|
|
parts.append("<xs:complexType name=\"B\">\(modelGroup(3))</xs:complexType>")
|
|
parts.append("<xs:complexType name=\"R\"><xs:complexContent><xs:restriction base=\"B\">\(modelGroup(3))"
|
|
+ "</xs:restriction></xs:complexContent></xs:complexType>")
|
|
parts.append("<xs:element name=\"root\" type=\"\(pick(["B", "R", "s0", "xs:string"]))\"/>")
|
|
parts.append("</xs:schema>")
|
|
return parts.joined()
|
|
}
|
|
|
|
private mutating func instanceElement(_ name: String, _ depth: Int) -> String {
|
|
if depth <= 0 || toss() {
|
|
return toss() ? "<\(name)/>" : "<\(name)>\(pick(["", "x", "42", "true", " "]))</\(name)>"
|
|
}
|
|
let children = (0 ..< Int.random(in: 0 ... 3, using: &rng)).map { _ in instanceElement(pick(Self.names), depth - 1) }.joined()
|
|
return "<\(name)>\(children)</\(name)>"
|
|
}
|
|
|
|
mutating func instance() -> String {
|
|
let namespace = toss() ? " xmlns=\"urn:t\"" : ""
|
|
let children = (0 ..< Int.random(in: 0 ... 3, using: &rng)).map { _ in instanceElement(pick(Self.names), 3) }.joined()
|
|
return "<root\(namespace)>\(children)</root>"
|
|
}
|
|
}
|
|
|
|
/// Generative robustness fuzzing for the schema engine and parser. The bar is
|
|
/// interactive safety (production-readiness stopper 4): on arbitrary, possibly
|
|
/// hostile input the validator must never crash and must always terminate. A
|
|
/// trap aborts the test process (a visible failure); the `.timeLimit` trait
|
|
/// turns a true hang into a failure rather than a blocked run. Seeds are fixed
|
|
/// so any failure reproduces. No reference oracle is asserted here: this
|
|
/// characterizes termination and crash-freedom, not verdict correctness.
|
|
@Suite("Schema fuzz (generative robustness)")
|
|
struct SchemaFuzzTests {
|
|
// The harness finds native crashes and hangs; under the ~30x-slower WASI
|
|
// runtime a handful of iterations only proves it compiles and runs there, so
|
|
// the counts drop to keep that gate fast. Raise the native bounds for a
|
|
// deeper, longer fuzz campaign.
|
|
#if os(WASI)
|
|
private static let schemaIterations: UInt64 = 15
|
|
private static let parserIterations: UInt64 = 40
|
|
private static let differentialIterations: UInt64 = 15
|
|
#else
|
|
private static let schemaIterations: UInt64 = 250
|
|
private static let parserIterations: UInt64 = 600
|
|
private static let differentialIterations: UInt64 = 2000
|
|
#endif
|
|
|
|
// The `.timeLimit` trait (native hang detection) is not supported by the
|
|
// single-threaded WASI test runtime, so it is applied only off-WASI; on WASI
|
|
// the engine's own occurrence/state caps still guarantee termination.
|
|
#if os(WASI)
|
|
@Test("Schema compile and instance validation never crash or hang")
|
|
#else
|
|
@Test("Schema compile and instance validation never crash or hang", .timeLimit(.minutes(1)))
|
|
#endif
|
|
func test_schemaAndInstanceFuzz() {
|
|
for seed in UInt64(1) ... Self.schemaIterations {
|
|
var generator = SchemaGenerator(rng: SeededRNG(seed: seed))
|
|
let xsd = generator.schema()
|
|
// The schema text is also valid XML; the parser must handle it too.
|
|
_ = try? PureXML.parse(xsd)
|
|
guard let document = try? PureXML.Schema.Document(xsd) else { continue }
|
|
let xml = generator.instance()
|
|
let errors = (try? document.validate(xml)) ?? []
|
|
_ = errors.isEmpty
|
|
_ = try? document.validate(streaming: xml)
|
|
}
|
|
}
|
|
|
|
// Standing differential gate: the streaming validator is a separate
|
|
// implementation of the same semantics as the tree validator (the conformance
|
|
// oracle), so it must AGREE with it on every input. This enforces what manual
|
|
// hunting only sampled: the streaming path never rejects a document the tree
|
|
// accepts (no false positive) and never accepts one the tree rejects. Streaming
|
|
// may emit additional errors on an already-invalid document (issue #206), so the
|
|
// tree's errors must be a subset of streaming's; it may never miss one, and the
|
|
// two must agree on whether the document is valid. A failure prints the seed,
|
|
// schema, instance, and both error sets, so it reproduces exactly.
|
|
#if os(WASI)
|
|
@Test("Streaming validation agrees with the tree validator on every fuzzed document")
|
|
#else
|
|
@Test("Streaming validation agrees with the tree validator on every fuzzed document", .timeLimit(.minutes(1)))
|
|
#endif
|
|
func test_streamingMatchesTreeDifferential() {
|
|
for seed in UInt64(1) ... Self.differentialIterations {
|
|
var generator = SchemaGenerator(rng: SeededRNG(seed: seed))
|
|
let xsd = generator.schema()
|
|
guard let document = try? PureXML.Schema.Document(xsd) else { continue }
|
|
let xml = generator.instance()
|
|
guard let tree = try? document.validate(xml),
|
|
let streamed = try? document.validate(streaming: xml)
|
|
else { continue }
|
|
let treeReasons = Set(tree.map(\.reason))
|
|
let streamedReasons = Set(streamed.map(\.reason))
|
|
let detail = "seed \(seed)\n tree: \(treeReasons.sorted())\n stream: \(streamedReasons.sorted())\n xsd: \(xsd)\n xml: \(xml)"
|
|
#expect(tree.isEmpty == streamed.isEmpty, "streaming/tree verdict disagreement (\(detail))")
|
|
#expect(treeReasons.isSubset(of: streamedReasons), "streaming missed a tree error (\(detail))")
|
|
}
|
|
}
|
|
|
|
#if os(WASI)
|
|
@Test("The parser never crashes on arbitrary byte sequences")
|
|
#else
|
|
@Test("The parser never crashes on arbitrary byte sequences", .timeLimit(.minutes(1)))
|
|
#endif
|
|
func test_parserByteFuzz() {
|
|
let palette = Array("<>/=\"'?! &;:-[]xmlABC\n\t".utf8)
|
|
for seed in UInt64(1) ... Self.parserIterations {
|
|
var rng = SeededRNG(seed: seed)
|
|
let length = Int.random(in: 0 ... 200, using: &rng)
|
|
var bytes: [UInt8] = []
|
|
bytes.reserveCapacity(length)
|
|
for _ in 0 ..< length {
|
|
bytes.append(Bool.random(using: &rng) ? palette[Int.random(in: 0 ..< palette.count, using: &rng)] : UInt8.random(in: 0 ... 255, using: &rng))
|
|
}
|
|
_ = try? PureXML.parse(bytes: bytes)
|
|
}
|
|
}
|
|
|
|
/// Opt-in DEEP fuzz campaign (production-readiness stopper #3: correctness
|
|
/// bounded, not sampled). The standing tests above keep a fast, hang-guarded
|
|
/// 2000/250/600-iteration sample for every CI run; this runs the same
|
|
/// streaming-vs-tree differential over `PUREXML_FUZZ_ITERATIONS` seeds when
|
|
/// that variable is set, so a long campaign is reproducible without editing the
|
|
/// bounds. It carries no `.timeLimit` (a 60k-seed run legitimately exceeds a
|
|
/// minute); termination is still guaranteed by the engine's own occurrence and
|
|
/// state caps. A divergence prints the seed, schema, and instance, exactly like
|
|
/// the standing gate, so it reproduces. Run:
|
|
/// `PUREXML_FUZZ_ITERATIONS=60000 swift test --filter test_deepFuzzCampaign`.
|
|
@Test("Deep fuzz campaign (opt-in via PUREXML_FUZZ_ITERATIONS)")
|
|
func test_deepFuzzCampaign() {
|
|
guard let raw = ProcessInfo.processInfo.environment["PUREXML_FUZZ_ITERATIONS"],
|
|
let iterations = UInt64(raw), iterations > 0
|
|
else { return }
|
|
for seed in UInt64(1) ... iterations {
|
|
var generator = SchemaGenerator(rng: SeededRNG(seed: seed))
|
|
let xsd = generator.schema()
|
|
_ = try? PureXML.parse(xsd)
|
|
guard let document = try? PureXML.Schema.Document(xsd) else { continue }
|
|
let xml = generator.instance()
|
|
guard let tree = try? document.validate(xml),
|
|
let streamed = try? document.validate(streaming: xml)
|
|
else { continue }
|
|
let treeReasons = Set(tree.map(\.reason))
|
|
let streamedReasons = Set(streamed.map(\.reason))
|
|
let detail = "seed \(seed)\n tree: \(treeReasons.sorted())\n stream: \(streamedReasons.sorted())\n xsd: \(xsd)\n xml: \(xml)"
|
|
#expect(tree.isEmpty == streamed.isEmpty, "streaming/tree verdict disagreement (\(detail))")
|
|
#expect(treeReasons.isSubset(of: streamedReasons), "streaming missed a tree error (\(detail))")
|
|
}
|
|
}
|
|
}
|