117 to regular expressions, and tried to establish that their |
117 to regular expressions, and tried to establish that their |
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 When faced with catastrophic backtracking, |
123 When a regular expression engine does not behave as intended (for example, |
123 sometimes programmers |
124 getting excruciatingly slow on |
124 have to rewrite their regexes in an ad hoc fashion. |
125 a relatively simple regex pattern $(a^*)^*b$ |
125 Knowing which patterns should be avoided |
126 and a string $a\ldots a$ that is obviously |
126 can be helpful. |
127 not part of that regex) |
127 \subsection{Static Analysis of Evil Regex Patterns} |
128 programmers usually try to rewrite the regex to some equivalent form. |
|
129 |
|
130 or they try to avoid the possibly problematic patterns completely, |
128 or they try to avoid the possibly problematic patterns completely, |
131 for which many false positives exist\parencite{Davis18}. |
129 for which many false positives exist\parencite{Davis18}. |
132 \subsection{Static Analysis of Evil Regex Patterns} |
|
133 Animated tools to "debug" regular expressions such as |
130 Animated tools to "debug" regular expressions such as |
134 \parencite{regexploit2021} \parencite{regex101} are also popular. |
131 \parencite{regexploit2021} \parencite{regex101} are also popular. |
135 We are also aware of static analysis work on regular expressions that |
132 We are also aware of static analysis work on regular expressions that |
136 aims to detect potentially expoential regex patterns. Rathnayake and Thielecke |
133 aims to detect potentially expoential regex patterns. Rathnayake and Thielecke |
137 \parencite{Rathnayake2014StaticAF} proposed an algorithm |
134 \parencite{Rathnayake2014StaticAF} proposed an algorithm |