Static Detection of DoS Vulnerabilities in Programs that use Regular Expressions (Extended Version)

2017/01/15 by Wüstholz, Valentin, Olivo, Oswaldo, Heule, Marijn J. H. +1 · 1 citation
#Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Programming Languages (cs.PL) #Software Engineering (cs.SE)

paper · doi:10.48550/arxiv.1701.04045

Abstract

In an algorithmic complexity attack, a malicious party takes advantage of the worst-case behavior of an algorithm to cause denial-of-service. A prominent algorithmic complexity attack is regular expression denial-of-service (ReDoS), in which the attacker exploits a vulnerable regular expression by providing a carefully-crafted input string that triggers worst-case behavior of the matching algorithm. This paper proposes a technique for automatically finding ReDoS vulnerabilities in programs. Specifically, our approach automatically identifies vulnerable regular expressions in the program and determines whether an "evil" input string can be matched against a vulnerable regular expression. We have implemented our proposed approach in a tool called REXPLOITER and found 41 exploitable security vulnerabilities in Java web applications.

Cited by

• Lost in Translation? Converting RegExes for Log Parsing into Dynatrace Pattern Language

Related

• Static Analysis for Regular Expression Denial-of-Service Attacks
• SoK: A Literature and Engineering Review of Regular Expression Denial of Service (ReDoS)
• Improving Developers' Understanding of Regex Denial of Service Tools through Anti-Patterns and Fix Strategies
• IRIS: LLM-Assisted Static Analysis for Detecting Security Vulnerabilities
• HotFuzz: Discovering Algorithmic Denial-of-Service Vulnerabilities Through Guided Micro-Fuzzing