TLDR: A new framework called Localized Regex Repair (LRR) combines precise symbolic analysis with the generalization power of large language models (LLMs) to automatically fix regular expression denial-of-service (ReDoS) vulnerabilities. By first pinpointing the exact vulnerable part of a regex and then using an LLM to generate a targeted fix, LRR significantly improves repair rates and maintains semantic correctness, outperforming traditional rule-based methods and demonstrating contextual understanding of regexes.
Regular expressions, or regexes, are fundamental tools in modern software development, used for critical tasks like input validation and data parsing. However, their widespread use also exposes systems to a significant security threat: Regular Expression Denial of Service (ReDoS) vulnerabilities. A ReDoS attack can exploit certain regexes that exhibit super-linear time complexity, causing a system to consume excessive resources and potentially leading to service failure. Addressing these vulnerabilities is crucial for maintaining system stability and security.
Traditional approaches to repairing ReDoS vulnerabilities have faced a dilemma. Rule-based systems, while precise for known vulnerability patterns, often struggle with complex or unseen cases, failing to generalize. On the other hand, large language models (LLMs) offer broad generalization capabilities but can be unreliable for tasks demanding strict syntactic and semantic correctness, often introducing new errors.
A new research paper, titled Repairing Regex Vulnerabilities via Localization-Guided Instructions, introduces a novel solution to this problem: the Localized Regex Repair (LRR) framework. This hybrid approach aims to combine the best of both worlds, leveraging the generalization power of LLMs while ensuring reliability through precise problem identification.
How LRR Works: A Hybrid Approach
The core insight behind LRR is to separate the process of identifying the problem from the actual repair. Here’s how it functions:
- Vulnerability Localization: First, a deterministic, symbolic module analyzes the vulnerable regex. This module precisely pinpoints the exact sub-pattern responsible for the ReDoS vulnerability. This step transforms a broad, complex problem into a much smaller, more manageable one.
- Targeted LLM Repair: Once the vulnerable sub-pattern is localized, an LLM is invoked. The LLM’s task is to generate a semantically equivalent fix specifically for this isolated segment. By focusing on a constrained problem space, the LLM can apply its powerful generative abilities more reliably, avoiding the common pitfalls of trying to fix an entire complex regex at once.
This combined architecture allows LRR to successfully resolve complex repair cases that traditional rule-based methods cannot handle, while simultaneously avoiding the semantic errors often seen in LLM-only approaches.
Significant Performance Improvements
The researchers conducted extensive experiments to validate the LRR framework. They found that LRR significantly improves the repair rate of vulnerable regexes. Specifically, the framework achieved a 15.4% increase in repair rate over the state-of-the-art baseline, RegexScalpel. One of the LLM variants, Phi4, demonstrated the best repair rate at 59.00%.
An ablation study further highlighted the synergistic nature of LRR’s components. For non-reasoning LLMs, the inclusion of 5-shot Chain-of-Thought (CoT) prompting (providing examples of the repair process) was crucial, teaching the models how to fix. For reasoning-based LLMs, the precise localization of the vulnerability was most impactful, guiding the models on what to fix. This confirms that both localization and guided prompting are essential for robust performance across different LLM types.
Maintaining Quality and Contextual Understanding
Beyond just fixing vulnerabilities, LRR also prioritizes maintaining the syntactic and semantic similarity of the repaired regex to the original. Reasoning models, like Qwen3, showed a tendency to apply simpler, more stable repair strategies, resulting in better syntactic similarity. These models also produced repairs with more reliable semantic quality, achieving near-perfect Jaccard similarity scores more frequently.
A key advantage of LRR, particularly with LLMs, is its ability to perform contextual reasoning. In case studies, the LLM was able to infer the semantic intent of given regexes, even for domain-specific formats. For example, it recognized a specific pattern as a ‘git diff header’ and intelligently constrained a numerical pattern to represent plausible line counts. This context-aware understanding allows LRR to repair regexes that pure rule-based approaches simply cannot address.
Also Read:
- Assessing the Spatial Limits of LLM Reasoning with RegexPSPACE
- The Locality Dial: Bridging Interpretability and Performance in LLMs
Looking Ahead
While LRR demonstrates strong practical efficacy, the researchers acknowledge certain limitations. The symbolic localization module relies on existing heuristics, meaning its effectiveness is tied to the knowledge of known anti-patterns. Additionally, the validation of repair success is empirical, relying on dynamic detection tools rather than formal, provable guarantees of safety. Despite these, the LRR framework offers a robust and effective method for automated ReDoS vulnerability repair, paving the way for more adaptable and scalable solutions by combining precise analytical tools with powerful generative models.
