警惕正则分组引起的长时间回溯
0条评论背景
最近在折腾一个小工具,修改时加了一个正则匹配,启动后出现假死的情况,刚开始以为数据库连接问题,把更改的代码去掉后又恢复正常。后来逐步排查,发现是执行到一个正则匹配就卡住了。
问题原因
查阅资料,是因为正则对于+,*使用了最长匹配的方式,如果不能匹配,就会发生回溯,如果正则表达式中滥用了多个+,*等就会出现长时间回溯,CPU很高的情况。
https://stackoverflow.com/questions/34032350/high-cpu-utilization-on-regex-pattern-matching
http://www.regular-expressions.info/catastrophic.html
验证
我们使用以下代码验证
public class PatternTest {
public static void main(String[] args) throws Exception{
String input = "123456789012345";
List<String> patternList = new ArrayList<>();
patternList.add("\\w#");
patternList.add("(\\w+)+#");
patternList.add("((\\w+)+)+#");
testSpeed(input, patternList.toArray(new String[0]));
patternList = patternList.stream().map(e -> e.replace("+", "*")).collect(Collectors.toList());
testSpeed(input, patternList.toArray(new String[0]));
}
private static void testSpeed(String input, String... regex){
MyStopWatch stopWatch = new MyStopWatch();
for(String item : regex){
stopWatch.resetAndStart();
System.out.println(Pattern.matches(item, input));
System.out.println(stopWatch.getTime());
}
System.out.println("-------------------------");
}
}
最后结果:
false
1
false
6
false
1505
-------------------------
false
0
false
4
false
37108
-------------------------
结论和问题解决
可以看出,对分组使用+或者*,然后再嵌套+或者*,在不匹配的情况下,会极大的增加回溯次数,所以我们应当尽量避免这种写法,比如将(\\w+)+
写成\\w+
就可以了
发表新评论