An optimizing compiler for JavaScript regular expressions
Modern regex languages have evolved significantly from traditional regular expressions, incorporating features that complicate the matching process. Many modern regex engines, including JavaScript’s, use a backtracking algorithm that can exhibit exponential complexity, leading to vulnerabilities such as Regular Expression Denial of Service (ReDoS) attacks. While some approaches demonstrate that a large subset of these regex patterns can be executed in linear time, existing linear-time engines for JavaScript are generally two orders of magnitude slower on average compared to their backtracking counterparts. This performance gap hinders widespread adoption, highlighting the need for fasteron average solutions. This report introduces Rawr, an optimizing compiler that translates a subset of JavaScript’s regular expressions into WebAssembly (Wasm). The resulting Wasm code executes in linear time and outperforms the current linear engine of V8.
Tevaearai, Zacharie - Rawr: An optimizing compiler for JavaScript regular expressions (Master semester project).pdf
Main Document
Not Applicable (or Unknown)
openaccess
CC BY
470.87 KB
Adobe PDF
3df2b516d7f69f7cccf8552130416e16