[
https://issues.apache.org/jira/browse/GROOVY-12122?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Paul King resolved GROOVY-12122.
--------------------------------
Fix Version/s: 6.0.0-beta-1
Resolution: Fixed
> Provide a Regex timeout facility
> --------------------------------
>
> Key: GROOVY-12122
> URL: https://issues.apache.org/jira/browse/GROOVY-12122
> Project: Groovy
> Issue Type: Improvement
> Components: regex
> Reporter: Paul King
> Assignee: Paul King
> Priority: Major
> Labels: GEP
> Fix For: 6.0.0-beta-1
>
>
> h2. Summary
> Add an opt-in, thread-free runtime guard against Regular Expression Denial of
> Service
> (ReDoS / catastrophic backtracking) for Groovy's regex features, offered as a
> runtime
> helper ({{RegexGuard}}), a scoped annotation ({{@SafeRegex}}), and
> type-checker awareness
> of both. Everything is opt-in; no existing code changes behaviour.
> h2. Motivation
> Groovy makes regex frictionless -- {{=~}}, {{==~}}, {{~/.../}},
> {{String#matches}},
> {{replaceAll}}, {{split}}, and the {{Matcher}} sugar -- which also makes
> ReDoS easy to
> reach when a pattern (or its input) comes from outside the program: scripts,
> build files,
> web handlers, {{ConfigSlurper}}, templating.
> {{java.util.regex}} has *no native timeout*, so a crafted input against a
> backtracking-prone pattern can hang the calling thread indefinitely. Nothing
> in Groovy
> guards against this today. Note the trust boundary is usually the *input*,
> not the
> pattern: the textbook ReDoS applies a hardcoded, developer-written validator
> to
> attacker-supplied text, so "don't run untrusted code" is not a sufficient
> answer.
> Thread interruption does not help: the regex engine never checks the
> interrupt flag, so
> neither {{@ThreadInterrupt}} nor {{@TimedInterrupt}} can stop a runaway match
> -- the hang
> is inside a single JDK library call, not in user code where those transforms
> insert checks.
> JLine 4.3.1 shipped a {{SafeRegex}} utility using the well-known
> {{TimeoutCharSequence}}
> technique to close four CVEs (GHSA-r2xf-8xr9-62gw, GHSA-2v9w-34q6-wpqx,
> GHSA-ph9c-7hw9-vhhw, GHSA-5q95-hrpc-m3w3). We apply the same idea.
> h2. Proposal
> Bound regex matching by a wall-clock deadline, without a watchdog thread. The
> input
> {{CharSequence}} is wrapped so that {{charAt()}} checks a deadline and throws
> an unchecked
> {{RegexTimeoutException}} once it has passed; because the regex engine
> re-reads input
> characters continuously while backtracking, a runaway match is interrupted
> with no extra
> thread and no {{Thread.interrupt}} plumbing. The clock is consulted once
> every 512 reads,
> so evaluations finishing in fewer reads never pay for a clock call.
> Four ways to apply it, from most explicit to most ergonomic.
> *(a) Explicit guarded evaluation* -- guarded equivalents of the match and
> find operators,
> with a {{long}} millisecond or {{Duration}} timeout:
> {code:groovy}
> RegexGuard.matches(pattern, input, 200) // -> boolean
> RegexGuard.matcher(pattern, input, Duration.ofMillis(200)) // -> Matcher
> over guarded input
> {code}
> *(b) Guarded data* -- attach a single total deadline to the sequence itself.
> Wrap
> untrusted input once at a trust boundary and pass it around freely; every
> regex evaluated
> against it shares the one budget, including Groovy's {{CharSequence}}
> extension methods
> and anything handing the sequence to {{java.util.regex}} untouched:
> {code:groovy}
> def safe = RegexGuard.guard(untrusted, 200)
> safe.findAll(~/\d+/)
> {code}
> *(c) Ambient scope* -- a per-evaluation timeout for the dynamic extent of a
> closure on the
> current thread, covering the regex operators and the {{CharSequence}}
> extension methods,
> including in methods called from the closure:
> {code:groovy}
> def groups = RegexGuard.guard(200) {
> input.findGroups(/(\d+)\.(\d+)\.(\d+)/)
> }
> {code}
> Nested scopes only tighten -- the smaller per-evaluation timeout wins -- and
> an explicit
> timeout from (a) is likewise capped by an active ambient timeout.
> *(d) Scoped annotation ({{@SafeRegex}})* -- an AST transform rewrites the
> match ({{==~}})
> and find ({{=~}}) operators lexically within the annotated scope to guarded
> calls, so no
> call-site changes are needed. Fits the existing {{@TimedInterrupt}} /
> {{@ThreadInterrupt}}
> / {{@ConditionalInterrupt}} family in {{groovy.transform}}:
> {code:groovy}
> @SafeRegex(millis = 200)
> class Handler {
> boolean check(String input) {
> input ==~ /(a+)+$/ // rewritten -> RegexGuard.matchRegex(input,
> /(a+)+$/, 200)
> }
> }
> {code}
> The annotation may be placed on a class, method, constructor, field or local
> variable
> declaration; on a field or local variable only the initializer expression is
> guarded. Its
> single attribute is {{millis}} (default {{1000}}, must be a positive
> constant). A guarded
> field initializer runs, as usual, in the constructor -- or in the static
> initializer for a
> static field, where a timeout surfaces as {{ExceptionInInitializerError}}
> whose cause is
> the {{RegexTimeoutException}}.
> The transform targets the operator-order entry points {{matchRegex(input,
> pattern,
> millis)}} and {{findRegex(input, pattern, millis)}} rather than
> {{matches(pattern, input, millis)}}, so a rewritten expression still
> evaluates its
> operands left to right exactly as the original operator did.
> The guard is on *matching*, not on {{~/.../}} compilation:
> {{Pattern.compile}} is not
> subject to backtracking and is not guarded.
> h3. Naming
> || Concern || Name || Notes ||
> | Scoped annotation | {{@SafeRegex}} | in {{groovy.transform}}, alongside
> {{@TimedInterrupt}} et al. |
> | Runtime helper | {{RegexGuard}} | in {{groovy.util.regex}}; distinct from
> the annotation to avoid a clash |
> | Timeout exception | {{RegexTimeoutException}} | unchecked; lets callers
> distinguish a ReDoS abort from a normal non-match |
> | Operator-order entry points | {{matchRegex}} / {{findRegex}} | mirror
> {{ScriptBytecodeAdapter}} naming and operand order; used by the transform |
> Both {{RegexGuard}} and {{@SafeRegex}} are marked {{@Incubating}}, {{@since
> 6.0.0}}.
> h3. Implementation notes
> * The ambient scope in (c) is held in an
> {{org.apache.groovy.runtime.async.ScopedLocal}},
> which delegates to {{java.lang.ScopedValue}} on JDK 25+ and falls back to a
> save-and-restore {{ThreadLocal}} below, so the binding cannot outlive its
> closure.
> * A process that never installs an ambient guard never touches that scoped
> local: a
> monotonic static flag short-circuits the lookup, leaving a single cached
> read on the
> regex path.
> * Deadlines are only ever compared as {{System.nanoTime()}} differences,
> which stays
> correct across wrap-around; a timeout large enough to overflow the deadline
> therefore
> reads as "effectively no timeout" rather than expiring immediately.
> h2. Scope
> *In scope*
> * Runtime deadline guard ({{TimeoutCharSequence}}-style), thread-free
> * {{RegexGuard}} helper: explicit guarded evaluation, guarded data, and
> ambient closure scope
> * {{@SafeRegex}} scoped annotation rewriting the {{==~}} and {{=~}} operators
> * {{RegexTimeoutException}} type
> * {{RegexChecker}} (groovy-typecheckers) awareness of guarded evaluation, so
> code inside a
> {{@SafeRegex}} scope keeps full regex checking after the rewrite
> * Documentation in the operator, metaprogramming and type-checker guides
> *Out of scope / deferred*
> * *Internal hardening of Groovy's own regex call sites* ({{groovysh}}
> completion,
> templating, builders) -- proposed originally, not implemented here;
> deferred to a
> follow-up so this ticket stays a purely opt-in, additive change
> * Making the guard the default for {{=~}} / {{==~}} (behaviour change +
> overhead)
> * Rewriting the {{String#matches}} / {{replaceAll}} / {{split}} family of
> method calls
> within a {{@SafeRegex}} scope -- only the two operators are rewritten; use
> {{RegexGuard}} explicitly for the rest (see _Possible future work_ below)
> * Static ReDoS pattern detection -- a possible future {{RegexChecker}}
> extension
> * Guarding {{Pattern.compile}}
> * Rewriting the regex engine or adopting a non-backtracking (RE2-style) engine
> h2. Limitations
> * {{@SafeRegex}} rewrites only the *lexically visible* {{==~}} and {{=~}}
> operators --
> scoped hardening, not whole-program. Regex evaluation via method calls, or
> occurring in
> code called from the annotated scope, is not rewritten; use {{RegexGuard}}
> there, whose
> ambient and guarded-data forms do reach both.
> * Direct JDK calls bypass the guard. On a {{String}} receiver,
> {{matches(String)}},
> {{replaceAll(String, String)}}, {{replaceFirst(String, String)}} and
> {{split(String)}}
> dispatch to {{java.lang.String}} and never enter Groovy's runtime. Their
> {{Pattern}}-argument variants are extension methods and are covered.
> * The deadline fires only while the engine is reading input characters (the
> backtracking
> phase) -- true of catastrophic cases, but not a hard guarantee for every
> pathological
> state. A well-behaved evaluation over a short input may still succeed after
> the deadline.
> * The clock is consulted every 512 character reads rather than on every read,
> so overshoot
> past the deadline is bounded by those reads; pathological patterns perform
> millions of
> reads per second, so in practice the overshoot is negligible.
> * The ambient scope is thread-confined: threads spawned within the closure
> are not covered
> (on JDK 25+ the binding does propagate into {{StructuredTaskScope}} forks).
> * Reduces hang risk; it is not a correctness or a data-at-rest control.
> h2. Relationship to existing/planned features
> || Layer || Mechanism || Status || Covers ReDoS? ||
> | Compile-time validity | {{RegexChecker}} (groovy-typecheckers) | ships | No
> -- pattern *syntax* only |
> | Compile-time ReDoS lint | possible {{RegexChecker}} extension | idea |
> Partially |
> | Untrusted-input tracking | GEP-25 {{@Tainted}} -> regex sink | draft |
> Identifies risky matches |
> | *Runtime guard (this ticket)* | {{RegexGuard}} / {{@SafeRegex}} |
> *implemented* | *Yes -- the actual backstop* |
> {{RegexChecker}} only validates that a literal pattern compiles; it says
> nothing about
> backtracking. As part of this ticket it was extended to recognise the guarded
> forms, so
> the rewrite performed by {{@SafeRegex}} does not blind it: bad regex literals
> are still
> reported, and matcher group-count inference survives the rewrite.
> h2. Interaction with GROOVY-12123 (Groovy 7)
> This ticket targets Groovy 6. GROOVY-12123 (constant regex hoisting) targets
> Groovy 7, so
> it lands second and owns the interaction: by then the guarded forms above are
> already
> shipped and in use. Within a single compilation the two still touch the same
> expressions,
> so the hoisting pass must be aware of the compile-phase ordering:
> * If hoisting runs after {{@SafeRegex}} (which rewrites at
> {{SEMANTIC_ANALYSIS}}), it sees
> {{RegexGuard.matchRegex(input, /(a+)+$/, 200)}} instead of a bare operator.
> The pattern
> is the *second* argument of {{matchRegex}} / {{findRegex}} -- and the
> *first* of a
> hand-written {{matches}} / {{matcher}} -- and must still be recognised as a
> hoistable
> constant and lifted to a {{static final}} field.
> * If hoisting runs first and produces a {{static final Pattern P}}, nothing
> further is
> needed: {{@SafeRegex}} rewrites a {{==~}} / {{=~}} expression whatever its
> right operand
> is, and {{RegexGuard}} accepts a {{Pattern}} directly, so {{input ==~ P}}
> already guards
> correctly today.
> Desired combined result: the constant {{Pattern}} is compiled once into a
> {{static final}}
> field *and* each match wraps the input in the deadline guard.
> h2. Possible future work
> *Guarding regex method calls within a {{@SafeRegex}} scope.* The transform
> rewrites only
> the {{==~}} and {{=~}} operators, so a call such as
> {{input.replaceAll(/(a+)+$/, 'x')}}
> inside an annotated scope stays unguarded. This deserves its own ticket
> rather than a
> documentation footnote, because for the most common shape -- a {{String}}
> receiver with
> {{String}} arguments -- a compile-time rewrite is the *only* mechanism that
> can work:
> {{matches(String)}}, {{replaceAll(String, String)}}, {{replaceFirst(String,
> String)}} and
> {{split(String)}} all dispatch to {{java.lang.String}} and never enter
> Groovy's runtime, so
> no runtime hook, the ambient guard included, can ever observe them. Their
> {{Pattern}}-argument variants are extension methods and are already covered.
> Such a rewrite would have to be receiver-aware, since these names exist on
> unrelated types
> ({{List#replaceAll(UnaryOperator)}}, Groovy's own
> {{Collection#split(Closure)}}) and the
> receiver type is generally unknown at {{SEMANTIC_ANALYSIS}}. Two workable
> routes:
> * redirect to a runtime-dispatching helper that guards a {{CharSequence}}
> receiver and
> otherwise forwards the call unchanged, preserving dynamic semantics; or
> * restrict the rewrite to statically-typed code, where the receiver type is
> known.
> *Whole-body guarding as an additional {{@SafeRegex}} strategy.* Instead of
> rewriting
> individual expressions, the transform could wrap an annotated body in the
> ambient guard
> (form (c) above). That would cover everything reachable dynamically on the
> calling thread
> -- the operators, the {{CharSequence}} extension methods, and regex in
> *called* methods,
> which a lexical rewrite can never reach.
> The two strategies are complementary rather than one dominating the other, so
> this would
> be an opt-in mode alongside the current rewrite, not a replacement:
> * Dynamic scope covers called code; lexical scope does not.
> * Lexical scope covers a closure defined in the annotated scope but invoked
> later, or on
> another thread, because the rewrite is baked into the closure's body.
> Dynamic scope
> would not, since the binding unwinds when the annotated method returns.
> * Dynamic scope costs a scoped binding per invocation, and what is guarded
> then depends on
> the call graph rather than on what is visible in the source, which is
> harder to audit.
> * Neither closes the {{java.lang.String}} dispatch gap described above.
> h2. Licensing / reuse
> JLine is BSD-3 (ASF category A) and already on the {{groovysh}} classpath
> (jline-builtins/jansi), so {{groovysh}} may use JLine's {{SafeRegex}}
> directly. For *core*
> Groovy the technique is ~20 lines and well-known, so it is reimplemented from
> the
> technique rather than taking a core dependency on JLine. No code was copied.
> h2. References
> * JLine 4.3.1 release notes -- SafeRegex / TimeoutCharSequence:
> https://github.com/jline/jline3/releases/tag/4.3.1
> * CWE-1333: Inefficient Regular Expression Complexity:
> https://cwe.mitre.org/data/definitions/1333.html
> * OWASP -- Regular expression Denial of Service (ReDoS):
> https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS
> * Related: GEP-25 (Data-flow Security -- taint tracking); {{RegexChecker}} in
> groovy-typecheckers; {{@TimedInterrupt}} / {{@ThreadInterrupt}} /
> {{@ConditionalInterrupt}} in groovy.transform
> * Relates to: GROOVY-12123 (constant regex hoisting -- compile-once static
> final Pattern fields): https://issues.apache.org/jira/browse/GROOVY-12123
> * Pull request: https://github.com/apache/groovy/pull/2668
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
