Static detection of DoS vulnerabilities in programs that use regular expressions

DOI10.1007/978-3-662-54580-5_1MaRDI QIDQ3303917zbMATH OpenOpenAlexFDO

Authors Valentin Wüstholz, Oswaldo Olivo, Marijn J. H. Heule, Isil Dillig

Publication date 5 August 2020

Published in Tools and Algorithms for the Construction and Analysis of Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.04045

zbMATH Keywords

abstract domainattack patterninput stringregular expressionsecurity vulnerability

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Formal languages and automata (68Q45)

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.

Recommendations

• Analyzing catastrophic backtracking behavior in practical regular expression matching
• Automata-based symbolic string analysis for vulnerability detection
• Information Security and Cryptology
• scientific article; zbMATH DE number 2219597
• String Analysis via Automata Manipulation with Logic Circuit Representation

Cites work

• Analyzing catastrophic backtracking behavior in practical regular expression matching
• Analyzing matching time behavior of backtracking regular expression matchers by using ambiguity of NFA
• Automata-based symbolic string analysis for vulnerability detection
• scientific article; zbMATH DE number 1701764 (Why is no real title available?)
• scientific article; zbMATH DE number 2090837 (Why is no real title available?)
• Programming Techniques: Regular expression search algorithm
• The essence of command injection attacks in web applications

Cited in

(4)

• On the decidability of infix inclusion problem
• How to settle the ReDoS problem: back to the classical automata theory
• Trading plaintext-awareness for simulatability to achieve chosen ciphertext security
• On the decidability of infix inclusion problem

Describes a project that uses

Uses Software

• Stranger
• FlowDroid
• PQL
• TAJ

This page was built for publication: Static detection of DoS vulnerabilities in programs that use regular expressions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3303917)