Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Student works
  4. An optimizing compiler for JavaScript regular expressions
 
semester or other student projects

An optimizing compiler for JavaScript regular expressions

Tevaearai, Zacharie Timothée  
July 9, 2024

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.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

Tevaearai, Zacharie - Rawr: An optimizing compiler for JavaScript regular expressions (Master semester project).pdf

Type

Main Document

Version

Not Applicable (or Unknown)

Access type

openaccess

License Condition

CC BY

Size

470.87 KB

Format

Adobe PDF

Checksum (MD5)

3df2b516d7f69f7cccf8552130416e16

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés