Automatic Repair of Vulnerable Regular Expressions

A regular expression is called vulnerable if there exist input strings on which the usual backtracking-based matching algorithm runs super linear time. Software containing vulnerable regular expressions are prone to algorithmic-complexity denial of service attack in which the malicious user provides input strings exhibiting the bad behavior. Due to the prevalence of regular expressions in modern software, vulnerable regular expressions are serious threat to software security. While there has been prior work on detecting vulnerable regular expressions, in this paper, we present a first step toward repairing a possibly vulnerable regular expression. Importantly, our method handles real world regular expressions containing extended features such as lookarounds, capturing groups, and backreferencing. (The problem is actually trivial without such extensions since any pure regular expression can be made invulnerable via a DFA conversion.) We build our approach on the recent work on example-based repair of regular expressions by Pan et al. [Pan et al. 2019] which synthesizes a regular expression that is syntactically close to the original one and correctly classifies the given set of positive and negative examples. The key new idea is the use of linear-time constraints, which disambiguate a regular expression and ensure linear time matching. We generate the constraints using an extended nondeterministic finite automaton that supports the extended features in real-world regular expressions. While our method is not guaranteed to produce a semantically equivalent regular expressions, we empirically show that the repaired regular expressions tend to be nearly indistinguishable from the original ones.