原文地址：https://alphahinex.github.io/2024/10/13/java-regex-catastrophic-backtracking/
description: "Java 正則表達式的災難性回溯問題可能導致應用程序的拒絕服務。本文介紹了如何重現(xiàn)蔫仙、風險原因游岳、風險評估掰烟、如何避免锁蠕、修復示例等內容统求。"
date: 2024.10.13 10:26
categories:
- Java
tags: [Java, Regex]
keywords: regex, backtracking, catastrophic backtracking, java, security, performance, denial of service, DoS, ReDoS, OWASP, CWE, S5852
現(xiàn)象重現(xiàn)
新建一個 Backtracking.java 文件池磁，內容如下：
public class Backtracking {
public static void main(String[] args) {
System.out.println(System.getProperty("java.version"));
System.out.println("The first regex evaluation will never end in JDK <= 9:");
System.out.println(java.util.regex.Pattern.compile("(a+)+").matcher(
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"+
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"+
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"+
"aaaaaaaaaaaaaaa!").matches()); // Sensitive
System.out.println("and the second regex evaluation will never end in any versions of the JDK:");
System.out.println(java.util.regex.Pattern.compile("(h|h|ih(((i|a|c|c|a|i|i|j|b|a|i|b|a|a|j))+h)ahbfhba|c|i)*").matcher(
"hchcchicihcchciiicichhcichcihcchiihichiciiiihhcchi"+
"cchhcihchcihiihciichhccciccichcichiihcchcihhicchcciicchcccihiiihhihihihi"+
"chicihhcciccchihhhcchichchciihiicihciihcccciciccicciiiiiiiiicihhhiiiihchccch"+
"chhhhiiihchihcccchhhiiiiiiiicicichicihcciciihichhhhchihciiihhiccccccciciihh"+
"ichiccchhicchicihihccichicciihcichccihhiciccccccccichhhhihihhcchchihih"+
"iihhihihihicichihiiiihhhhihhhchhichiicihhiiiiihchccccchichci").matches()); // Sensitive
}
}
編譯并執(zhí)行：
$ java -version
java version "1.8.0_121"
Java(TM) SE Runtime Environment (build 1.8.0_121-b13)
Java HotSpot(TM) 64-Bit Server VM (build 25.121-b13, mixed mode)
$ javac Backtracking.java
$ java Backtracking
1.8.0_121
The first regex evaluation will never end in JDK <= 9:
在 Java 8 環(huán)境下平窘，此段程序永遠不會執(zhí)行結束，且該 Java 進程會持續(xù)跑滿 CPU跌榔。
在 Java 11 環(huán)境下异雁，第一個表達式能執(zhí)行結束，但第二個表達式依然會持續(xù)消耗大量資源：
$ java -version
openjdk version "11.0.23" 2024-04-16 LTS
OpenJDK Runtime Environment Microsoft-9394293 (build 11.0.23+9-LTS)
OpenJDK 64-Bit Server VM Microsoft-9394293 (build 11.0.23+9-LTS, mixed mode, sharing)
$ java Backtracking
11.0.23
The first regex evaluation will never end in JDK <= 9:
false
and the second regex evaluation will never end in any versions of the JDK:
風險原因
Using slow regular expressions is security-sensitive 對這個問題進行了描述：大多數(shù)正則表達式引擎使用回溯（backtracking）來嘗試正則表達式在評估輸入時的所有可能執(zhí)行路徑僧须，在某些情況下纲刀，這可能會導致性能問題，稱為災難性回溯（catastrophic backtracking）情況皆辽。在最壞的情況下芍锦，正則表達式的復雜度與輸入大小成指數(shù)關系文捶，這意味著一個精心構造的小輸入（如20個字符）可以觸發(fā)災難性回溯并導致應用程序的拒絕服務壁熄。超線性正則表達式復雜度也可能導致相同的影響敲董，在這種情況下，需要一個精心構造的大輸入（數(shù)千個字符）空另。
風險評估
要確定代碼中是否存在此風險盆耽，可以嘗試回答如下問題：
- 輸入是用戶控制的。
- 輸入大小沒有限制為少量的字符扼菠。
- 沒有設置超時來限制正則表達式的評估時間摄杂。
如果任何一個問題的回答為 是，那么就可能存在風險循榆。
如何避免
在所有下述情況中析恢，災難性回溯只有在正則表達式的有問題部分后面跟隨一個可能失敗的模式時才會發(fā)生，從而導致回溯實際發(fā)生秧饮。請注意映挂，當執(zhí)行完全匹配（例如使用 String.matches）時泽篮，正則表達式的結尾被視為一個可能失敗的模式，因為它只有在到達字符串結尾時才會成功柑船。
- 如果正則表達式包含非占有性重復帽撑，如
r*或r*?，表示可以匹配零次或多次r鞍时，但不會占有匹配的字符（即允許回溯）亏拉，如果r可以在相同輸入上產生不同的可能匹配（可能長度不同），最壞情況下的匹配時間可能是指數(shù)級的逆巍。這種情況可能發(fā)生在r包含可選部分及塘、交替或額外重復時。使用JDK 9或更高版本時蒸苇，如果重復是貪婪的且整個正則表達式不包含反向引用磷蛹，則運行時間會優(yōu)化為多項式或線性。 - 如果多個非占有性重復可以匹配相同內容且是連續(xù)的或僅由可選分隔符分隔溪烤，可能會導致多項式時間復雜度。例如庇勃，
a*b*沒有問題檬嘀，因為a*和b*匹配不同的東西，而a*_a*也沒有問題责嚷，因為重復部分由一個_分隔鸳兽，并且不能匹配該_。然而罕拂，a*a*和.*_.*具有二次運行時間揍异。 - 如果你正在執(zhí)行部分匹配（如使用
Matcher.find、String.split爆班、String.replaceAll等）衷掷，并且正則表達式未錨定到字符串的開頭，尤其難以避免二次運行時間柿菩。例如戚嗅，str.split("\\s*,")在完全由空格組成的字符串（或至少包含大量不跟隨逗號的空格序列）上將以二次時間運行。
為避免這些問題枢舶，可以采取以下策略：
- 如果適用懦胞，使用有界量詞（例如用
{1,5}代替+）限制重復次數(shù)。 - 重構嵌套量詞（
nested quantifiers）以限制內部組可以被外部量詞匹配的數(shù)量凉泄。例如(ba+)+這種嵌套量詞情況不會導致性能問題躏尉，實際上，只有存在每個組重復一次b字符時后众，內部組才能匹配胀糜。 - 使用占有量詞（
possessive quantifiers）和原子分組（atomic grouping）優(yōu)化正則表達式稼锅。 - 使用否定字符類代替
.來排除分隔符。例如僚纷，二次正則表達式.*_.*可以通過將其更改為[^_]*_.*變?yōu)榫€性矩距。
如果無法重寫正則表達式以避免性能問題，可以考慮以下方法：
- 不使用正則表達式解決問題怖竭。
- 使用非回溯的正則表達式實現(xiàn)锥债，如Google的 RE2 或 RE2/J。
- 使用多次處理痊臭，預處理或后處理字符串哮肚，或使用多個正則表達式。一個例子是將
str.split("\\s*,\\s*")替換為str.split(",")广匙，然后在第二步中修剪字符串中的空格允趟。 - 使用
Matcher.find()時，通逞恢拢可以通過使所有可能失敗的部分可選來使正則表達式不可失敗潮剪，這將防止回溯。當然分唾，這意味著你將接受比預期更多的字符串抗碰，但這可以通過使用捕獲組來檢查可選部分是否匹配，然后在它們不匹配時忽略匹配來處理绽乔。例如弧蝇，正則表達式x*y可以替換為x*(y)?，然后將對matcher.find()的調用替換為matcher.find() && matcher.group(1) != null折砸。
修復示例
NewBacktracking.java
public class NewBacktracking {
public static void main(String[] args) {
System.out.println(System.getProperty("java.version"));
System.out.println("The first regex evaluation will end after modify:");
System.out.println(java.util.regex.Pattern.compile("(a+)++").matcher(
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"+
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"+
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"+
"aaaaaaaaaaaaaaa!").matches()); // Sensitive
System.out.println("and the second regex evaluation will end after modify:");
System.out.println(java.util.regex.Pattern.compile("(h|h|ih(((i|a|c|c|a|i|i|j|b|a|i|b|a|a|j))++h)ahbfhba|c|i)*").matcher(
"hchcchicihcchciiicichhcichcihcchiihichiciiiihhcchi"+
"cchhcihchcihiihciichhccciccichcichiihcchcihhicchcciicchcccihiiihhihihihi"+
"chicihhcciccchihhhcchichchciihiicihciihcccciciccicciiiiiiiiicihhhiiiihchccch"+
"chhhhiiihchihcccchhhiiiiiiiicicichicihcciciihichhhhchihciiihhiccccccciciihh"+
"ichiccchhicchicihihccichicciihcichccihhiciccccccccichhhhihihhcchchihih"+
"iihhihihihicichihiiiihhhhihhhchhichiicihhiiiiihchccccchichci").matches()); // Sensitive
}
}
$ diff Backtracking.java NewBacktracking.java
1c1
< public class Backtracking {
---
> public class NewBacktracking {
4,5c4,5
< System.out.println("The first regex evaluation will never end in JDK <= 9:");
< System.out.println(java.util.regex.Pattern.compile("(a+)+").matcher(
---
> System.out.println("The first regex evaluation will end after modify:");
> System.out.println(java.util.regex.Pattern.compile("(a+)++").matcher(
10,11c10,11
< System.out.println("and the second regex evaluation will never end in any versions of the JDK:");
< System.out.println(java.util.regex.Pattern.compile("(h|h|ih(((i|a|c|c|a|i|i|j|b|a|i|b|a|a|j))+h)ahbfhba|c|i)*").matcher(
---
> System.out.println("and the second regex evaluation will end after modify:");
> System.out.println(java.util.regex.Pattern.compile("(h|h|ih(((i|a|c|c|a|i|i|j|b|a|i|b|a|a|j))++h)ahbfhba|c|i)*").matcher(
$ javac NewBacktracking.java
$ java NewBacktracking
1.8.0_121
The first regex evaluation will end after modify:
false
and the second regex evaluation will end after modify:
true
參考資料
- Using slow regular expressions is security-sensitive
- OWASP - Top 10 2017 Category A1 - Injection
- CWE- CWE-400 - Uncontrolled Resource Consumption
- CWE- CWE-1333 - Inefficient Regular Expression Complexity
- owasp.org - OWASP Regular expression Denial of Service - ReDoS
- stackstatus.net(archived) - Outage Postmortem - July 20, 2016
- regular-expressions.info - Runaway Regular Expressions: Catastrophic Backtracking
- docs.microsoft.com - Backtracking with Nested Optional Quantifiers
