118 algorithm outputs the minimal element by a pencil-and-paper proof. |
118 algorithm outputs the minimal element by a pencil-and-paper proof. |
119 But having the ordering relation taking regular expression as parameters |
119 But having the ordering relation taking regular expression as parameters |
120 causes the transitivity of their ordering to not go through. |
120 causes the transitivity of their ordering to not go through. |
121 |
121 |
122 |
122 |
123 \subsection{Static Analysis of Evil Regex Patterns} |
123 When a regular expression engine does not behave as intended (for example, |
124 When a regular expression does not behave as intended, |
124 getting excruciatingly slow on |
125 people usually try to rewrite the regex to some equivalent form |
125 a relatively simple regex pattern $(a^*)^*b$ |
|
126 and a string $a\ldots a$ that is obviously |
|
127 not part of that regex) |
|
128 programmers usually try to rewrite the regex to some equivalent form. |
|
129 |
126 or they try to avoid the possibly problematic patterns completely, |
130 or they try to avoid the possibly problematic patterns completely, |
127 for which many false positives exist\parencite{Davis18}. |
131 for which many false positives exist\parencite{Davis18}. |
|
132 \subsection{Static Analysis of Evil Regex Patterns} |
128 Animated tools to "debug" regular expressions such as |
133 Animated tools to "debug" regular expressions such as |
129 \parencite{regexploit2021} \parencite{regex101} are also popular. |
134 \parencite{regexploit2021} \parencite{regex101} are also popular. |
130 We are also aware of static analysis work on regular expressions that |
135 We are also aware of static analysis work on regular expressions that |
131 aims to detect potentially expoential regex patterns. Rathnayake and Thielecke |
136 aims to detect potentially expoential regex patterns. Rathnayake and Thielecke |
132 \parencite{Rathnayake2014StaticAF} proposed an algorithm |
137 \parencite{Rathnayake2014StaticAF} proposed an algorithm |