IDS18-J Prevent Regex Injection

Java's regular expression facilities are wide ranging and powerful which can lead to unwanted modification of the original regular expression string to form a pattern that matches too widely, possibly resulting in far too much information being matched.

The primary means of preventing this vulnerability is to sanitize a regular expression string coming from untrusted input. Additionally, the programmer should look into ways of avoiding using regular expressions from untrusted input, or perhaps provide only a very limited subset of regular expression functionality to the user.

Constructs and properties of Java regular expressions to watch out for include:

• match flags used in non-capturing groups (These override matching options that may or may not have been passed into the compile() method.)
• greediness
• grouping

Noncompliant Code Example

This noncompliant code example searches a log file of previous searches for keywords that match a regular expression to present search suggestions to the user. The function suggestSearches() is repeatedly called to bring up suggestions for the user for auto-completion. The full log of previous searches is stored in the logBuffer StringBuffer object. StringBuffer is typical for this use-case because appends are relatively expensive on Strings but cheaper on StringBuilders and StringBuffers. Furthermore, the StringBuffer class is thread-safe. The strings in logBuffer are periodically copied to the log String object for use in searchSuggestions().

The regex used to search the log is:

^(" + search + ".*),[0-9]+?,[0-9]+?$

This regex matches against an entire line of the log and searches for old searches beginning with the entered keyword. The anchoring operators and use of the reluctance operators mitigate some greediness concerns. The grouping characters allow the program to grab only the keyword while still matching the IP and timestamp. Because the log String contains multiple lines, the MULTILINE flag must be active to force the anchoring operators to match against newlines. By all appearances, this is a strong regex.

However, this class does not sanitize the incoming regular expression, and as a result, exposes too much information from the log file to the user.

A non-malicious use of the searchSuggestions() method would be to enter "C" to match "Charles" and "Cecilia". However, a malicious user could enter

 ?:)(^C.*,[0-9]+?,[0-9]+?$)|(?:

which grabs the entire log line rather than just the old keywords. The outer parentheses of the malicious search string defeat the grouping protection. Using the OR operator allows injection of any arbitrary regex. Now this use will reveal all times and IPs the keyword 'C' was searched.

import java.util.HashSet;
import java.util.Set;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class ExploitableLog {
    private static StringBuffer logBuffer = new StringBuffer();
    private static String log = logBuffer.toString();
    
    public static Set<String> suggestSearches(String search) {
        Set<String> searches = new HashSet<String>();
        
        // Construct regex from user string
        String regex = "^(" + search + ".*),[0-9]+?,[0-9]+?$";
        int flags = Pattern.MULTILINE;
        Pattern keywordPattern = Pattern.compile(regex, flags);
        
        // Match regex
        Matcher logMatcher = keywordPattern.matcher(log);
        while (logMatcher.find()) {
            String found = logMatcher.group(1);
            searches.add(found);
        }
        
        return searches;
    }
    
    public static void append(CharSequence str) {
        logBuffer.append(str);
        log = logBuffer.toString(); //update log string on append
    }

    static {
        // this is supposed to come from a file, but its here as a string for
        // illustrative purposes
        append("Alice,1267773881,2147651408\n");
        append("Bono,1267774881,2147351708\n");
        append("Charles,1267775881,1175523058\n");
        append("Cecilia,1267773222,291232332\n");
    }
}

Compliant Solution

One compliant solutions is to parse out the sensitive information prior to matching and then running the user-supplied regex against that. Depending on how encapsulated the search keywords are, a malicious user may be able to grab a list of all the keywords (If there are a lot of keywords, this may cause a denial of service). Alternatively, whitelisting certain characters (such as letters and digits) and then passing the filtered keyword onto the regex mitigates the vulnerability. Blacklisting might be difficult due to the variability of the regex language.

This compliant solution filters out non-alphanumeric characters from the search string using Java's Character.isLetterOrDigit(). This removes the grouping parentheses and the OR operator which triggers the injection.

import java.util.HashSet;
import java.util.Set;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class FilteredLog {
    private static StringBuffer logBuffer = new StringBuffer();
    private static String log = logBuffer.toString();
    
    public static Set<String> suggestSearches(String search) {
        Set<String> searches = new HashSet<String>();
        
        // Filter user input
        StringBuilder sb = new StringBuilder(search.length());
        for (int i = 0; i < search.length(); ++i) {
            char ch = search.charAt(i);
            if (Character.isLetterOrDigit(ch))
                sb.append(ch);
        }
        search = sb.toString();
        
        // Construct regex from user string
        String regex = "^(" + search + ".*),[0-9]+?,[0-9]+?$";
        int flags = Pattern.MULTILINE;
        Pattern keywordPattern = Pattern.compile(regex, flags);
        
        // Match regex
        Matcher logMatcher = keywordPattern.matcher(log);
        while (logMatcher.find()) {
            String found = logMatcher.group(1);
            searches.add(found);
        }
        
        return searches;
    }
    
    public static void append(CharSequence str) {
        logBuffer.append(str);
        log = logBuffer.toString(); //update log string on append
    }

    static {
        // this is supposed to come from a file, but its here as a string for
        // illustrative purposes
        append("Alice,1267773881,2147651408\n");
        append("Bono,1267774881,2147351708\n");
        append("Charles,1267775881,1175523058\n");
        append("Cecilia,1267773222,291232332\n");
    }
}

Risk Assessment

References

[[MITRE 09]] CWE ID 625 "Permissive Regular Expressions"
[[CVE 05]] CVE-2005-1949