Uploaded image for project: 'SonarJava'
  1. SonarJava
  2. SONARJAVA-3779

FP in S5852 when a failing match does not trigger catastrophic backtracking

    Details

    • Type: False-Positive
    • Status: Open
    • Priority: Major
    • Resolution: Unresolved
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: Rules
    • Labels:

      Description

      To detect whether a regex is susceptible to ReDoS, we check that it both contains a loop (or sequence of loops) with the potential for catastrophic backtracking. We then check whether the continuation of the loop can lead to a match failure that would trigger backtracking.

      However, some times a match failure might just trigger a small number of backtracking steps, rather than triggering the full catastrophic backtracking. Specifically this is the case if the remaining part of the regex after the repetition can match everything that the repetition's body can match, e.g. in the case of `\s*\s` or `\s*[\s\w]` in partial matches. In such a case the repetition would stop at the first non-space character, fail, backtrack one character and then succeed. Since undoing one iteration of the loop is always enough to make the match succeed, no catastrophic backtracking can happen here.

      To fix this, it probably suffices to check whether a repetition is a subset of its continuation in addition to checking whether the repetition can fail. This check should not be performed when the continuation is anchored at the end (i.e. when there's a full match or an end-of-line/input boundary at the end) because supersetOf does not support boundaries and it can't be a superset in that case anyway.

      My assumption is that FPs due to this will be rare as regular expressions like this should be relatively uncommon.

      str.replaceAll("\\s*\\s", ""); // FP
      str.replaceAll("\\s*[\\s\\w]", ""); // FP
      str.replaceAll("\\s*,", ","); // Noncompliant
      str.replaceAll("\\s+$", ""); // Noncompliant
      
      str.matches("(.+)/(.+)/(.+)"); // Noncompliant: true positive
      str.matches("(?s)(.+)/(.+)/(.+)"); // FP
      

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                Unassigned
                Reporter:
                sebastian.hungerecker Sebastian Hungerecker
              • Votes:
                0 Vote for this issue
                Watchers:
                1 Start watching this issue

                Dates

                • Due:
                  Created:
                  Updated: