正则表达式漏洞引起的问题分析

问题
     一天晚上突然收到同事反馈，其使用的一个正责表达式对收货人姓名处理时，输入某种字符不能正确保存，现象为服务端请求卡死，没有response返回给客户端；在测试环境重现该问题时通过jstack获取到的信息可以发现正则表达式在回溯处理，进一步通过RegexBuddy对该段正则表达式分析发现该该段正则表达式处理完成需要超过一百万次匹配如果有恶意用户发现该漏洞，对考拉发起ReDoS(Regular expression Denial of Service)攻击，可能会引发灾难性的后果。



根源
    从本质上讲，存在两种不同类型的正则表达式引擎：确定性有穷自动机 (DFA) 引擎和非确定性有穷自动机 (NFA) 引擎。
    DFA 对于文本串里的每一个字符只需扫描一次，比较快，但特性较少；
    NFA要翻来覆去吃字符、吐字符，速度慢，但是特性丰富，所以反而应用广泛，当今主要的正则表达式引擎.Java同样采用NFA。

^\d+$

    如果整个输入字符串仅包含数字字符，则这是一个相当简单的匹配正则表达式。^ 和 $ 字符分别表示字符串的开头和结尾，表达式 \d 表示数字字符，+ 指示将有一个或多个字符匹配。我们使用 123456X 作为输入字符串测试此表达式，那么最终又是什么情况呢？同样通过RegexBuddy分析一下，可以发现NFA总共计算出了6个路径：123456、12345、1234、123、12 和 1；经过了20步处理才发现是不符合要求的。下面通过介绍正则表达式的匹配模式去分析一下该如何处理。



正则表达式匹配模式

• 贪婪型
• 勉强型
• 占有型

贪婪型：
    X?、X*、X+、X{n，}都是最大匹配，上面的例子就是一个贪婪型。

勉强型：
    X?、X*、X+、X{n，}都是最大匹配。好，加个？就成了Laziness匹配。例如X??、X*?、X+?、X{n，}?都最小匹配。上面的例子如果改为勉强型是不是可以解决问题呢？通过实验发现是解决不了问题的。从上下两幅图中还是可以发现两者的区别的。一个从最大处开始回溯，一个在最小处回溯。


占有型：
    与最大匹配不同，还有一种匹配形式：X?+、X*+、X++、X{n，}+等，成为完全匹配。它和最大匹配一样，一直匹配所有的字符，直到文本的最后，但它不由原路返回。也就是说，一口匹配，搞不定就算了，到也干脆，偶喜欢；发现解决问题的曙光了。

    问题解决了，那么回过头来，再看开始的问题，如果将其改造为占有型不是就可以解决问题了

固化分组
    用(?>…)实现固化分组(成功匹配后，回溯时不会考虑这个匹配的字符)。也就是说，在固化分组匹配结束时，它已经匹配的文本已经固化为一个单元，只能作为整体而保留或放弃。括号内的子表达式中未尝试过的备用状态都不复存在了，所以回溯永远也不能选择其中的状态（至少是，当此结构匹配完成时，“锁定（locked in）”在其中的状态）。

    最终选择方案：^(?>[\u4e00-\u9fa5|A-Z]+\\s*\\.?\\s*)+[\u4e00-\u9fa5|A-Z]$