Paul King created GROOVY-12122:
----------------------------------
Summary: 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
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 hardening of
Groovy's
own internal regex call sites.
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.
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 can 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 a
{{RegexTimeoutException}} once exceeded; because the regex engine calls
{{charAt()}}
continuously while backtracking, a runaway match is interrupted with no extra
thread and
no {{Thread.interrupt}} plumbing.
Three deliverables, from lowest-level to most ergonomic:
* *(a) Internal hardening* -- wrap regex matches against user-supplied input in
Groovy's
own runtime and tools (templating, {{groovysh}} completion, builders),
exactly as JLine
did across its modules. Invisible; no public API change.
* *(b) Runtime helper ({{RegexGuard}})* -- an explicit guarded-match API for
user code and
for anything the annotation cannot reach:
{code:groovy}
RegexGuard.matches(pattern, input, Duration.ofMillis(200)) // -> boolean,
throws on timeout
RegexGuard.matcher(pattern, input, Duration.ofMillis(200)) // -> Matcher over
a guarded input
{code}
* *(c) Scoped annotation ({{@SafeRegex}})* -- at method / class / package
level; an AST
transform rewrites the regex match operations lexically within scope to the
{{RegexGuard}}
path, 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.matches(~/(a+)+$/,
input, 200ms)
}
}
{code}
The guard is on *matching*, not on {{~/.../}} compilation, so the transform
rewrites the
match operations ({{=~}}, {{==~}}, {{String#matches}},
{{replaceAll}}/{{replaceFirst}},
{{split}}, {{Matcher}} operations), not {{Pattern.compile}}.
h3. Naming
|| Concern || Name || Notes ||
| Scoped annotation | {{@SafeRegex}} | in {{groovy.transform}}, alongside
{{@TimedInterrupt}} et al. |
| Runtime helper | {{RegexGuard}} | distinct from the annotation to avoid a
clash |
| Timeout exception | {{RegexTimeoutException}} | unchecked; lets callers
distinguish a ReDoS abort from a normal non-match |
h2. Scope
*In scope*
* Runtime deadline guard ({{TimeoutCharSequence}}-style), thread-free
* Internal hardening of Groovy's own user-input regex sites
* {{RegexGuard}} helper and {{@SafeRegex}} scoped annotation for user code
* {{RegexTimeoutException}} type
*Out of scope / deferred*
* Making the guard the default for {{=~}} / {{==~}} (behaviour change +
overhead)
* Static ReDoS pattern detection -- a possible future {{RegexChecker}}
extension, not this ticket
* Rewriting the regex engine or adopting a non-backtracking (RE2-style) engine
h2. Limitations
* {{@SafeRegex}} rewrites only *lexically-visible* regex ops -- scoped
hardening, not
whole-program. A regex executed inside a called library method is not
rewritten; use
{{RegexGuard}} explicitly there.
* The deadline fires only while the engine is calling {{charAt}} (the
backtracking phase) --
true of catastrophic cases but not a hard guarantee for every pathological
state.
* Each {{charAt}} pays a small deadline check ({{System.nanoTime}}), so the
guard is opt-in /
internal-only, never a blanket default.
* Reduces hang risk; it is not a correctness or a data-at-rest control.
h2. Relationship to existing 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}} | *missing* |
*Yes -- the actual backstop* |
{{RegexChecker}} only validates that a literal pattern compiles; it says
nothing about
backtracking. This ticket fills the runtime layer none of the others cover. It
also
composes with GEP-25: a regex applied to a {{@Tainted}} string is a ReDoS sink,
and a
{{RegexGuard}}-guarded (or {{@SafeRegex}}-scoped) match is its runtime
sanitizer.
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 reimplement the idea
rather than take
a core dependency on JLine. Do not copy code; implement from the technique.
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
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
