Skip to content

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.") }

```

Standards

  • PCI_STANDARDS:
    • REQ_6_2
    • REQ_6_4