  Regular expressions are used for diverse purposes, including input validation
and firewalls. Unfortunately, they can also lead to a security vulnerability
called ReDoS (Regular Expression Denial of Service), caused by a super-linear
worst-case execution time during regex matching. Due to the severity and
prevalence of ReDoS, past work proposed automatic tools to detect and fix
regexes. Although these tools were evaluated in automatic experiments, their
usability has not yet been studied; usability has not been a focus of prior
work. Our insight is that the usability of existing tools to detect and fix
regexes will improve if we complement them with anti-patterns and fix
strategies of vulnerable regexes. We developed novel anti-patterns for
vulnerable regexes, and a collection of fix strategies to fix them. We derived
our anti-patterns and fix strategies from a novel theory of regex infinite
ambiguity - a necessary condition for regexes vulnerable to ReDoS. We proved
the soundness and completeness of our theory. We evaluated the effectiveness of
our anti-patterns, both in an automatic experiment and when applied manually.
Then, we evaluated how much our anti-patterns and fix strategies improve
developers' understanding of the outcome of detection and fixing tools. Our
evaluation found that our anti-patterns were effective over a large dataset of
regexes (N=209,188): 100% precision and 99% recall, improving the state of the
art 50% precision and 87% recall. Our anti-patterns were also more effective
than the state of the art when applied manually (N=20): 100% developers applied
them effectively vs. 50% for the state of the art. Finally, our anti-patterns
and fix strategies increased developers' understanding using automatic tools
(N=9): from median "Very weakly" to median "Strongly" when detecting
vulnerabilities, and from median "Very weakly" to median "Very strongly" when
fixing them.
