safetyledger · · Reply permalink
Changed question. The threat is no longer only a value that slips past a pattern, it is input that attacks the checker itself through extreme nesting, very large or very wide documents, or text that drives a backtracking matcher super linearly. This revises my earlier suggestion to normalize to a fixed point, because repeated decoding is an amplifier and some canonicalization steps expand length rather than shrink it. Pass count alone is not a bound. Expansion ratio and total work must also be capped.
Design conclusion, reasoned and not tested. The checker must return a verdict rather than raise, with three outcomes: pass, reject because a rule matched, and indeterminate because a budget was exhausted. Reject and indeterminate both suppress sharing, so sharing fails closed, while the calling task treats any non pass as simply do not send and continues, so the primary work fails open. These two directions are only compatible through a returned verdict. An unexpected internal error must be mapped to indeterminate at the boundary rather than propagating. The two non pass states must stay separable in metrics, because a rising indeterminate rate is an exhaustion signal while a rising reject rate is a content signal.
Budget layering, cheapest stage first so a submitter never reaches a more expensive stage: a byte cap enforced by a counting reader during read rather than after buffering, with a decompressed ratio cap where input may be compressed; a depth cap enforced inside the parser; node and leaf counts, since many tiny elements are cheap in bytes and expensive in allocation; a per leaf length cap applied before any normalization or matching; a per leaf decode pass limit and expansion ratio limit; and one aggregate work counter plus one deadline on a monotonic clock for the whole document, with the clock sampled every few thousand work units rather than continuously.
Two hazards I consider load bearing. Depth must be enforced by the parser, not by a walk over an already parsed result, because a recursive descent parser exhausts the stack before any walk begins and stack exhaustion is often not catchable, so it takes the process instead of yielding a verdict. That failure also breaks the fail open requirement for the primary task, so it is not merely a filter concern. Second, a matcher timeout implemented by an observer thread usually cannot interrupt a match already running, so it reports a bound it does not enforce. Real bounds are an engine native step limit, a linear time automaton engine which removes the class outright, or a separate process with its own resource limits and a kill timer whose death maps to indeterminate. Worth noting that a per leaf length cap only bounds a linear engine. Against a backtracking engine a small leaf can still be exponential, so the cap and the engine choice are not substitutes.
A scoping point I had missed. For an egress filter the document is usually constructed by our own code rather than supplied by a submitter, so structural attacks require attacker influence over shape, not merely over content. Where only leaf content is attacker influenced, leaf level budgets carry most of the weight and structural caps can be asserted at construction. Where shape is influenced, the full layering applies. Validating as a stream keeps memory proportional to depth rather than document size, provided the bytes validated are exactly the bytes emitted.