Regular expression denial of service
Regular expression denial of service
Description
Regular Expression Denial of Service (ReDoS) is a security vulnerability that occurs when user input is utilized to construct a regular expression. In the presence of a carefully crafted regex pattern, the application may expend a substantial amount of resources, potentially resulting in a denial of service.
Some examples of evil patterns include:
(a+)+([a-zA-Z]+)*(a|aa)+(a|a?)+(.*a){x} for x > 10
And the following code examples are illustrations of incorrect implementations:
```java import java.util.regex.*;
public class RegexVulnerabilityExample { public static void main(String[] args) { // Function to read user input, potentially malicious String userInput = getUserInput();
// Constructing a regular expression using user input
Pattern pattern = Pattern.compile(userInput);
// Using the regular expression
Matcher matcher = pattern.matcher("input_string");
boolean matchFound = matcher.find();
if (matchFound) {
System.out.println("Match found!");
} else {
System.out.println("No match found!");
}
} ```
```swift import Foundation
func checkRegex(input: String, regex: String) {
// Constructing a regular expression using user input
do {
let regex = try NSRegularExpression(pattern: userInput)
let range = NSRange(location: 0, length: input.utf16.count)
let matchRange = regex.rangeOfFirstMatch(in: input, options: [], range: range)
if matchRange.location != NSNotFound {
print("Match found!")
} else {
print("No match found!")
}
} catch {
print("Error: Invalid regular expression")
}
}
// Call the function with user input checkRegex(input: "input_string",regex: "redos") ```
```dart import 'package:flutter/material.dart'; import 'package:flutter/services.dart';
void main() { runApp(MyApp()); }
class MyApp extends StatelessWidget { @override Widget build(BuildContext context) { return MaterialApp( home: Scaffold( appBar: AppBar( title: Text('Regex Vulnerability Example'), ), body: Center( child: ElevatedButton( onPressed: () { // Function to read user input, potentially malicious String userInput = getUserInput();
// Constructing a regular expression using user input
RegExp regex = RegExp(userInput);
// Using the regular expression
String inputString = "input_string";
bool matchFound = regex.hasMatch(inputString);
if (matchFound) {
print("Match found!");
} else {
print("No match found!");
}
},
child: Text('Test Regex'),
),
),
),
);
} ```
Recommendation
To mitigate Regular Expression Denial of Service (ReDoS) vulnerabilities consider the following recommendations:
-
Minimize Dependency on User Input: Whenever feasible, minimize the reliance on user-supplied input for constructing regular expressions (regex). Consider alternative approaches or design patterns that reduce the need for dynamic regex generation based on user input. By limiting exposure to potentially malicious patterns, you can significantly decrease the risk of ReDoS vulnerabilities.
-
Validate User Input: Implement robust validation mechanisms to ensure that user-provided input for regex construction adheres to predefined criteria. Validate the length, complexity, and structure of input patterns to mitigate the risk of maliciously crafted expressions. By validating input at the outset, you can preemptively identify and reject potentially harmful patterns.
-
Implement Rate Limiting and Timeout Mechanisms: Apply rate limiting and timeout mechanisms to restrict the execution time and resource consumption associated with regex evaluation. Set appropriate limits on the complexity and duration of regex matching operations to prevent excessive computational overhead. By imposing reasonable constraints on regex processing, you can mitigate the risk of ReDoS attacks and ensure the stability of your application under varying input conditions.
```java import java.util.Scanner; import java.util.concurrent.*;
public class TimeoutDatabaseCheckExample { public static void main(String[] args) { // Create a Scanner object to read user input Scanner scanner = new Scanner(System.in);
// Prompt the user to enter a regex pattern
System.out.print("Enter a regex pattern: ");
String regexPattern = scanner.nextLine();
// Set the timeout duration in milliseconds
long timeoutDuration = 1000; // 1 second
// Create an ExecutorService with a single thread
ExecutorService executor = Executors.newSingleThreadExecutor();
// Submit the database check task to the executor
Future<Boolean> future = executor.submit(() -> {
// Perform the database check operation
return checkDatabase(regexPattern);
});
try {
// Wait for the result with timeout
boolean recordExists = future.get(timeoutDuration, TimeUnit.MILLISECONDS);
// Check if the record exists in the database
if (recordExists) {
System.out.println("Record exists in the database!");
} else {
System.out.println("Record not found in the database.");
}
} catch (TimeoutException e) {
// Handle timeout
System.out.println("Database operation timed out.");
} catch (InterruptedException | ExecutionException e) {
// Handle other exceptions
e.printStackTrace();
} finally {
// Shutdown the executor
executor.shutdown();
}
// Close the scanner
scanner.close();
}
// Hypothetical database check function
public static boolean checkDatabase(String regexPattern) {
// Perform the database check operation here
// For demonstration purposes, assume the record exists if the regex pattern matches
return Pattern.compile(regexPattern).matcher("record_from_database").find();
}
}
```
```swift import Foundation
// Function to perform database check func checkDatabase(forRegexPattern regexPattern: String) -> Bool { // Perform the database check operation here // For demonstration purposes, assume the record exists if the regex pattern matches let inputString = "record_from_database" return inputString.range(of: regexPattern, options: .regularExpression) != nil }
// Function to perform database check with timeout func checkDatabaseWithTimeout(forRegexPattern regexPattern: String, timeout: TimeInterval) -> Bool? { var result: Bool?
// Create a dispatch group
let group = DispatchGroup()
// Create a dispatch queue
let queue = DispatchQueue.global()
// Enter the dispatch group
group.enter()
// Asynchronously perform the database check operation
queue.async {
result = checkDatabase(forRegexPattern: regexPattern)
// Leave the dispatch group when the operation is complete
group.leave()
}
// Wait for the operation to complete with timeout
let dispatchResult = group.wait(timeout: .now() + timeout)
// Check if the operation timed out
if dispatchResult == .timedOut {
// Return nil indicating timeout
return nil
}
// Return the result of the database check operation
return result
}
// Function to get regex pattern from user input func getRegexPatternFromUser() -> String { print("Enter the regex pattern:") guard let input = readLine() else { return "" } return input }
// Example usage let regexPattern = getRegexPatternFromUser() let timeoutDuration = 1.0 // Timeout duration in seconds
if !regexPattern.isEmpty { if let recordExists = checkDatabaseWithTimeout(forRegexPattern: regexPattern, timeout: timeoutDuration) { if recordExists { print("Record exists in the database!") } else { print("Record not found in the database.") } } else { print("Database operation timed out.") } } else { print("Invalid regex pattern.") }
```
Links
- OWASP : Regular expression Denial of Service - ReDoS
- CWE-1333: Inefficient Regular Expression Complexity
Standards
- PCI_STANDARDS:
- REQ_6_2
- REQ_6_4
- OWASP_MASVS_L1:
- MSTG_PLATFORM_2
- OWASP_MASVS_L2:
- MSTG_PLATFORM_2
- OWASP_MASVS_v2_1:
- MASVS_CODE_4
- SOC2_CONTROLS:
- CC_2_1
- CC_4_1
- CC_7_1
- CC_7_2
- CC_7_4
- CC_7_5
- CC_9_1