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

S5852 should use automata to increase its accuracy


    • Type: Improvement
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 6.14
    • Component/s: Rules
    • Labels:


      Currently S5852 only reports on nested repetitions (that are unbounded and non-possessive), but catastrophic backtracking can also occur when an unbounded repetition contains multiple paths that can match the same input (e.g. overlapping alternatives or an option followed by another overlapping option).

      Further in cases where a match can never fail after matching a repetition, no backtracking will occur, which isn't currently not taken into account, leading to false positives.

      To fix these issues we should extend the existing implementation as follows:

      When checking a repetition, we shouldn't just check whether it contains another repetition, but also any node with multiple outgoing "backtrackable" transitions (i.e. any disjunction or non-possessive (but possibly bounded) repetition┬╣)), such that any of the subautomata targeted by any of the transitions intersects with any of the others (which we can check using the helper method for intersections).

      After we determined that a repetition is problematic, we should then check whether its continuation can either match the empty string (but not if we know that the regex is used for full matches (e.g. as an argument to matches) or is .*. If that is the case, we shouldn't raise the issue.

      ┬╣ In some cases the node with multiple transitions will be the branch node associated with the repetition rather than the repetition itself.


          Issue Links



              • Assignee:
                sebastian.hungerecker Sebastian Hungerecker
                sebastian.hungerecker Sebastian Hungerecker
              • Votes:
                0 Vote for this issue
                2 Start watching this issue


                • Due: