Turning evil regexes harmless
B Van Der Merwe, N Weideman… - Proceedings of the South …, 2017 - dl.acm.org
Proceedings of the South African Institute of Computer Scientists and …, 2017•dl.acm.org
We explore the relationship between ambiguity in automata and regular expressions on the
one hand, and the matching time of backtracking regular expression matchers on the other.
We focus in particular on the extreme cases where we have either an exponential amount of
ambiguity or no ambiguity at all. We also investigate techniques to reduce or remove
ambiguity from regular expressions, which can then be used to transform regular
expressions which might be exploited by using algorithmic complexity, into harmless …
one hand, and the matching time of backtracking regular expression matchers on the other.
We focus in particular on the extreme cases where we have either an exponential amount of
ambiguity or no ambiguity at all. We also investigate techniques to reduce or remove
ambiguity from regular expressions, which can then be used to transform regular
expressions which might be exploited by using algorithmic complexity, into harmless …
We explore the relationship between ambiguity in automata and regular expressions on the one hand, and the matching time of backtracking regular expression matchers on the other. We focus in particular on the extreme cases where we have either an exponential amount of ambiguity or no ambiguity at all. We also investigate techniques to reduce or remove ambiguity from regular expressions, which can then be used to transform regular expressions which might be exploited by using algorithmic complexity, into harmless equivalent expressions.