Expression analysis for preventing cyberattacks
A method for assessing a regular expression for vulnerability to ReDoS attacks includes receiving a regular expression for evaluating a string defined by ordered set of characters from an alphanumeric input device, and evaluating the regular expression for determining if a parsing operation of the string according to the regular expression results in a disproportionate resource consumption. The evaluation determines if the resource consumption constitutes a Regular expression Denial of Service (ReDoS) attack by providing a vulnerability indication of a single valid attack string, rather than attempting to find all possible attack strings. The valid attack string is defined by an input string for which evaluation based on the regular expression would result in disproportionate resource consumption.
1 . A method for assessing a regular expression for vulnerability to ReDoS attacks, comprising:
receiving a regular expression;
generating a syntax tree based on the regular expression;
evaluating the regular expression by traversing the syntax tree for identifying loop constructs for determining if a parsing operation of a string according to the regular expression results in a disproportionate resource consumption based on a plurality of self transitions defining a quadratic or exponential computability, by determining a state represented by a node in the syntax tree, and concluding a self transition from the state to itself based on an input character; and
rendering, based on the evaluation, an indication of a vulnerability of the regular expression to resource consumption attacks.
2 . The method of claim 1 wherein the evaluation further comprises identifying a pair of loops associated by a bridge transition.
3 . The method of claim 1 wherein the evaluation further comprises identifying nested loops.
4 . The method of claim 1 wherein evaluating further comprises:
identifying potentially vulnerable sub-patterns defined by a suspect construct in the regular expression; and
determining if the suspect constructs are indicative of a quadratic or exponential computability burden.
5 . The method of claim 1 further comprising a non-exhaustive evaluation of the regular expression for identifying at least one string resulting in the quadratic or exponential computability.
6 . The method of claim 5 wherein the vulnerability indication is based on a valid attack string, the valid attack string defined by string for which evaluation based on the regular expression would result in disproportionate resource consumption, further comprising identifying the valid attack string prior to performing an exhaustive traversal of potential attack strings.
7 . The method of claim 6 further comprising evaluating a syntax tree based on the valid attack string before traversing all paths of the syntax tree for determining a plurality of valid attack strings.
8 . The method of claim 1 wherein evaluating further comprises:
identifying loop constructs in the regular expression;
determining if the loop constructs define a loop within a loop, each loop having a self transition based on a transition value in common with the other loop; or
determining if the loop constructs define a first loop, followed by a bridge, followed by a second loop, the bridge denoted by a transition value in common with at least one of the first loop or second loops.
9 . The method of claim 8 further comprising:
for each of the identified loop constructs:
generating a logic equation representation of the loop construct;
solving the logic equation to identify a satisfying string expression;
returning the satisfying string expression as the indication of vulnerability of the regular expression, or
if no satisfying expression is returned by an SMT (Satisfiable Modulo Theories) analysis, return that no indication of vulnerability exists.
10 . The method of claim 8 further comprising:
determining, for loop constructs defined by a loop within a loop, if each loop has a self transition and the transition labels correspond to a common value.
11 . The method of claim 8 further comprising:
determining, for loop constructs defined by three loop constructs including a first loop, transition and second loop, if a string exists that satisfies transitions to all three loop constructs.
12 . The method of claim 8 further comprising:
forming a logic expression based on an intersection of the loop constructs in the regular expression,
identifying a syntax of a logic engine responsive to the logic expression;
encoding the logic expression as a set of constraints, each loop construct defining a constraint in the logic expression, in a syntax based on the logic engine; and
invoking the logic engine for concluding either:
a string satisfying each of the constraints; or
an indication that no such string can be found.
13 . The method of claim 1 further comprising:
traversing the syntax tree for identifying the loop constructs; and
traversing the syntax tree from the identified loop for identifying a loop in a child node denoting a nested loop; and
traversing the syntax tree from the identified loop for identifying a sibling node denoting a bridged loop.
14 . A computing device for assessing a regular expression for vulnerability to ReDoS attacks, comprising:
an interface for receiving a regular expression;
a regular expression processor for generating a syntax tree based on the regular expression, and
evaluating the regular expression by traversing the syntax tree for identifying loop constructs for determining if a parsing operation of a string according to the regular expression results in a disproportionate resource consumption based on a plurality of self transitions defining a quadratic or exponential computability, by determining a state represented by a node in the syntax tree, and concluding a self transition from the state to itself based on an input character; and
a rendering device for rendering, based on the evaluation, an indication of a vulnerability of the regular expression to resource consumption attacks.
15 . A computer program embodying program code on a non-transitory computer readable storage medium that, when executed by a processor, performs steps for assessing a regular expression for vulnerability to resource consumption attacks, the method comprising:
receiving a regular expression;
generating a syntax tree based on the regular expression;
evaluating the regular expression by traversing the syntax tree for identifying loop constructs for determining if a parsing operation of a string according to the regular expression results in a disproportionate resource consumption based on a plurality of self transitions defining a quadratic or exponential computability, by determining a state represented by a node in the syntax tree, and concluding a self transition from the state to itself based on an input character; and
rendering, based on the evaluation, an indication of a vulnerability of the regular expression to resource consumption attacks.