PUFFERDOS: Efficient and Effective Attack String Generation for Regular Expression Denial of Service Vulnerabilities

2018-06-07 · Source: cs.SE updates on arXiv.org · Field: Technology & Digital — Cybersecurity & Data Privacy, Artificial Intelligence & Machine Learning, Software Development & Engineering · Depth: Expert, extended

Summary

PufferDoS is a novel hybrid framework designed to generate efficient and effective attack strings for Regular Expression Denial-of-Service (ReDoS) vulnerabilities. It addresses limitations of existing tools by synthesizing attack inputs that are both feasible within realistic length budgets and validated at the program level. The system first defines three vulnerable patterns based on formal verification and then employs a structure-driven approach to generate candidate attack strings. These strings are subsequently refined and validated using ReDoS-specific compositional concolic execution, ensuring real-world exploitability. In evaluations, PufferDoS produced attack strings that were 97.2x to 3872.4x shorter than those from the state-of-the-art tool RENGAR, achieving equivalent matching time thresholds. It successfully reproduced 96.8% of ReDoS CVEs, outperforming RENGAR's 77.4%, and discovered 59 previously undisclosed exploitable ReDoS instances across 12 real-world projects, 25 more than RENGAR.

Key takeaway

For AI Security Engineers assessing ReDoS vulnerabilities in Python applications, traditional tools often yield impractical attack strings. You should integrate PufferDoS into your security testing pipeline to uncover and validate real-world exploitable ReDoS vulnerabilities. Its ability to generate significantly shorter, more effective attack strings, especially for Loop-Intersect-Loop (LIL) patterns, allows better prioritization. This helps fix high-impact vulnerabilities often ignored due to perceived low severity or unrealistic exploit conditions.

Key insights

PufferDoS generates efficient, program-validated ReDoS attack strings using formal patterns and specialized concolic execution.

Principles

• Regex matching cost increases with more reachable stop points.
• Shorter repetition units in attack strings amplify matching cost.
• Separating stop points of adjacent loop expressions increases cost.

Method

PufferDoS identifies vulnerable regex patterns (EOL, LIL, PML), synthesizes compact attack strings using pattern-specific rules, then refines them via ReDoS-specific compositional concolic execution.

In practice

• Apply PufferDoS to identify and exploit ReDoS in Python applications.
• Focus remediation efforts on Loop-Intersect-Loop (LIL) patterns for highest impact.

Topics

• Regular Expression Denial-of-Service
• Attack String Generation
• Concolic Execution
• Software Security
• Python Ecosystem
• Vulnerability Analysis

Code references

• doyensec/regexploit

Best for: CTO, VP of Engineering/Data, Director of AI/ML, AI Scientist, AI Security Engineer, Research Scientist

Related on AIssential

• When Poison Fails After Retrieval: Revisiting Corpus Poisoning under Chunking and Reranking Pipelines — Effective RAG corpus poisoning requires accounting for multi-stage retrieval, particularly chunking and reranking, to maintain attack consistency.
• Mistletoe: Stealthy Acceleration-Collapse Attacks on Speculative Decoding — Speculative decoding's efficiency is vulnerable to stealthy attacks that degrade draft token acceptance without altering output semantics.
• GAS-Leak-LLM: Genetic Algorithm-Based Suffix Optimization for Black-Box LLM Jailbreaking — GAS-Leak-LLM uses a genetic algorithm to evolve adversarial suffixes, effectively jailbreaking black-box LLMs and exposing safety vulnerabilities.
• ContextualJailbreak: Evolutionary Red-Teaming via Simulated Conversational Priming — Evolutionary red-teaming with multi-turn conversational priming effectively jailbreaks LLMs, revealing alignment robustness asymmetries.
• DIG: Oracle-Guided Directed Input Generation for One-Day Vulnerabilities — Patch analysis with LLMs can synthesize explicit vulnerability preconditions, guiding effective PoC generation.
• Safe-FedLLM: Delving into the Safety of Federated Large Language Models — LoRA weight patterns can effectively distinguish malicious from benign updates in federated LLM training.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.SE updates on arXiv.org.