[C#] Improve "isExponentialRegex" detection logic in ReDoSQuery.qll to prevent false negatives
Nobody has claimed this yet.
Assessment
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Newbie friendliness
- 48/100
Research direction
Start with csharp/ql/lib/semmle/code/csharp/security/dataflow/ReDoSQuery.qll, especially lines 58–72, and trace how the cs/redos query uses isExponentialRegex and regexpMatch. Compare the existing matching logic with the listed nested-quantifier and overlapping-alternation examples. Done means the query detects these variants without losing its existing coverage or introducing problematic matching behavior.
Written by the indexing model from the issue text.
Description
Hello,
In the C# security analysis suite, the query Denial of Service from comparison of user input against expensive regex (cs/redos) relies heavily on underlying helper logic to flag regular expressions with potential exponential behavior. Specifically, in csharp/ql/lib/semmle/code/csharp/security/dataflow/ReDoSQuery.qll (lines 58–72). This uses a set of hardcoded regular expressions via regexpMatch to identify string literals that represent exponential (ReDoS-vulnerable) regular expressions.
While these three variations catch patterns like ([a-z]+.)+, they are fragile syntactic approximations. This approach misses variations of overlapping or nested quantifiers, creating a scenario where dangerous regex structures easily bypass the query's detection due to minor structural variations.
For example the query overlooks risky patterns like these:
- Nested Quantifiers without literals:
(a*)*b or (x+)* - Overlapping Alternations/Sequences:
(x+x+)+y - Complex or Distant Structural Paths: Patterns that contain non-trivial prefixes/suffixes or specific character class structures can fail to match the strict capture-group structures defined in the QL code. Depending on the engine evaluating these meta-regexes, they could themselves face performance degradation when scanning highly complex, non-matching input paths.
This issue stood out because these specific pattern variants can easily slip through the ReDoS query undetected. This creates a gap between the security results and the actual risk. I'm wondering if it would be possible address this in a future version?
Version: 2.26.0
- Dominant language
- CodeQL
- Stars
- 10.1k
- Forks
- 2.1k
- Avg merge
- 2d 16h
- Merged PRs (30d)
- 143
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from github/codeql
-
agentic-workflows
Difficulty 2/5 1-3 hours Newbie friendliness 70/100
-
false-positive javascript
Difficulty 2/5 1-3 hours Newbie friendliness 84/100
-
C#: cs/simplifiable-boolean-expression false positive on Nullable<bool> compared with a literal Open
Difficulty 2/5 1-3 hours Newbie friendliness 82/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
-
false-positive
Difficulty 2/5 1-3 hours Newbie friendliness 70/100
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
punkpeye/mcp-remote#369 ·
-
Mend: dependency security vulnerability untriaged
Difficulty 1/5 Under an hour Newbie friendliness 86/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
-
bug
Difficulty 1/5 Under an hour Newbie friendliness 90/100
cisagov/vulnrichment#337 ·
-
bug DUP Reservations
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
bcgov/reserve-rec-public#896 ·