# Linear Matching of JavaScript Regular Expressions

**Authors:** Aurèle Barrière, Clément Pit-Claudel  
**arXiv:** [2311.17620](https://arxiv.org/abs/2311.17620)  
**Date:** 2023-11-29  
**Summary page:** https://www.summarizepaper.com/en/arxiv-id/2311.17620v1/

## Key points

- The paper discusses complexities and vulnerabilities in modern regex languages, particularly in JavaScript applications.
- It highlights the evolution of regex languages, leading to exponential complexity blowups and denial-of-service vulnerabilities.
- The study explores differences in regex semantics across languages and their impact on algorithmic design and worst-case matching complexity.
- Authors identify a subset of JavaScript's regex language that can be matched with linear time guarantees.
- New algorithms are introduced to address incorrect, inefficient, or overly restrictive existing algorithms while maintaining linear complexity.
- Nonbacktracking algorithms for matching lookarounds in linear time are described, including support for captureless lookbehinds and leveraging JavaScript properties for unrestricted lookaheads and lookbehinds.
- New time and space complexity tradeoffs for regex engines are presented with practical solutions validated through a prototype implementation.
- Some algorithms have been integrated into the V8 JavaScript implementation used in Chrome and Node.js.

## Summary

, , , , 

The paper "Linear Matching of JavaScript Regular Expressions" delves into the complexities and vulnerabilities associated with modern regex languages, particularly in JavaScript applications. It highlights how these languages have evolved from traditional regular expressions, introducing features that can lead to exponential complexity blowups and denial-of-service vulnerabilities. The study explores the differences in regex semantics across languages and their impact on algorithmic design and worst-case matching complexity. The authors provide a fresh perspective on JavaScript's regex semantics by identifying a subset of the language that can be matched with linear time guarantees. They uncover instances where existing algorithms are incorrect, inefficient, or overly restrictive, and introduce novel algorithms to address these issues while maintaining linear complexity. Additionally, the paper introduces nonbacktracking algorithms for matching lookarounds in linear time, including support for captureless lookbehinds and leveraging JavaScript properties for unrestricted lookaheads and lookbehinds. Furthermore, it describes new time and space complexity tradeoffs for regex engines, offering practical solutions validated through a prototype implementation. Some of these algorithms have been integrated into the V8 JavaScript implementation used in Chrome and Node.js. Overall, this research advances the state-of-the-art in linear regex matching and provides valuable insights into optimizing performance and security in regex processing.