一条正则表达式引起的拒绝服务

什么是正则表达式？

正则表达式是对字符串操作的一种逻辑公式，就是用事先定义好的一些特定字符、及这些特定字符的组合，组成一个“规则字符串”，这个“规则字符串”用来表达对字符串的一种过滤逻辑。

?

正则表达式有什么作用及好处？

给定一个正则表达式和另一个字符串，我们可以达到如下的目的：

1. 给定的字符串是否符合正则表达式的过滤逻辑（称作“匹配”）：

2. 可以通过正则表达式，从字符串中获取我们想要的特定部分。

特点：

1. 灵活性、逻辑性和功能性非常强；

2. 可以迅速地用极简单的方式达到字符串的复杂控制。

3. 对于刚接触的人来说，比较晦涩难懂。

由于正则表达式主要应用对象是文本，因此它在各种文本编辑器场合都有应用，小到著名编辑器EditPlus，大到Microsoft Word、Visual Studio等大型编辑器，都可以使用正则表达式来处理文本内容。

?

虽然正则表达式有这么多的好处，但是使用过程中还是会出现一些问题，下文是我转载的有关正则表达式引发的开发问题的解决文章，如果你也踩过正则表达式的坑，那么下面的建议希望对你有用~

?

背??景：

从创造之初，正则表达式就是一样让程序员们又爱又恨的机制。爱它，因为在检测输入、提取目标字符串的过程中其无可替代的强大能力；恨它，因为其复杂的语法与超高的灵活性，用着用着就掉进了“大坑”。可以说，使用正则表达式的过程，就是一边解决问题，一边继续创造问题的过程。

?

这不，在某系统安全进行安全扫描的时候，银联科技安全团队在研究某原型系统登录邮箱字段进行fuzz的时候引起了CPU冲高。经过排查溯源，一个“画风清奇”的漏洞——ReDoS（正则表达式拒绝服务攻击）隆重登场。

?

ReDoS其原因非常简单，是因为这样的一个正则表达式：

^([a-z0-9A-Z]+[-|_|.]?)+[a-z0-9A-Z]@([a-z0-9A-Z]+(-[a-z0-9A-Z]+)?.)+[a-zA-Z]{2,}$

?

开发同学对这个式子再熟悉不过了，是一个校验邮箱格式的正则表达式，其原型来源于RegexLib（一个常用的表达式网站）。但在实际对特定字符串“aaaaaaaaaaaaaa!”进行匹配的时候，居然让CPU卡死了。

?

复??现：

既然发现了疑似的问题，那么作为一名靠谱的安全人员，首先第一个问题就是：

?

为了在模拟环境复现这个漏洞，我们编写了特定的Python脚本：

?

在这个脚本中，我们构造了长度为1到30的字符串，这个字符串以n个“a”开头，以一个“！”结尾，然后使用有问题的正则来对这些字符串进行匹配，其部分结果如下：

?

15个“a”的时候消耗的时间只有0.0049秒，看来我们的正则工作的很好呀~

继续向下：

?

20个“a”的时候消耗时间变成了0.1787秒，好像有哪里不对？

?

25个“a”的时候消耗时间已经达到了5.6302秒，已经非常长了。

?

到了有29个“a”的时候，一次正则匹配居然要运行90多秒！

?

通过验证，我们发现这个程序的运行时间和“a”的个数呈指数形式上升（如下图所示），每多一个a，匹配的运行时间就会翻倍！翻倍！翻倍！（重要的事情说三遍）

?

?

分??析：

这个问题的元凶就是正则表达式的实现引擎：有限状态自动机?(Finite State Automation: FSA)。FSA中又可以分为两类：非确定型有限状态自动机(Nondeterministic Finite Automation: NFA)和确定型有限状态自动机(Deterministic Finite Automation: DFA)。这两种引擎虽然都能匹配正则，但是工作原理却天差地别：

?

DFA是“文本主导”：捏着文本串去比较正则式，看到一个子正则式，就把可能的匹配串全标注出来，然后再看正则式的下一个部分，根据新的匹配结果更新标注。

NFA则是“表达式主导”捏着正则式去比文本，吃掉一个字符，就把它跟正则式比较，匹配就记下来，然后继续匹配。一旦不匹配，就把刚吃的这个字符吐出来，一个个的吐，直到回到上一次匹配的地方。

这两种工作原理带来了构造和执行的效率的区别：NFA构造效率高，但执行效率低；DFA构造效率低，但执行效率高。虽然在效率上各有千秋，但是在功能上，NFA支持“捕获group”，“环视”，“占有优先量词”，“固话分组”等高级功能，而DFA则无法实现。因此大部分高级语言的正则表达式都是基于NFA实现的。

?

NFA一旦不匹配的时候，要吐回上一次匹配的地方。现在考虑一个极端的正则表达式：^(a+)+$，根据其构造的NFA如下图所示：

可以看到，从第二个输入的a开始，每个a的输入都有两条路径可以匹配，即匹配括号内的“+”或者括号外的“+”。如果在表达式匹配成功的时候，皆大欢喜，不需要任何的回溯；但是一旦出现不匹配的情况，那么这些复杂的路径可能性就会令人头疼了。

如果在状态5发生不匹配，有两种状态可以回溯，一种是回到状态4，还有一种是回到状态5。同理，对于状态3和状态4都有两种回溯情况。假设在实际运行中有一个字符串aaab：在“b”的位置产生了不匹配，那么产生了2种回溯的可能；之后再回溯第3个“a”，2种可能；再回溯第2个“a”，2种可能；再回溯第三个“a”，1种可能；因此一共是2*2*2=8种可能。以此类推，如果该字符串以n个连续的“a”开头，外加不少于一个的其他字符，会产生2的n次方种回溯可能性。这就从理论上验证了我们的实验结果。

再回到之前的邮箱验证正则上，我们发现：“([a-z0-9A-Z]+[-|_|.]?)+”这个小结中由于蓝色部分可以为空，事实上红色部分会产生循环嵌套，因此在匹配大小写字符和数字的时候会陷入“递归陷阱”而导致效率极低。

?

建??议：

既然正则表达式不得不用，NFA引擎的问题又将会长期存在，那如何才能写出安全的正则表达式，避免被其他开发小伙伴调侃呢？

姿势1：

尽量使用标准库中的经过验证的正则表达式。减少自编的正则表达式。

但是并不是所有库中的正则都是安全的，除了上文中的邮箱验证正则之外，像如下的这个来源于OWASP的判断java class的正则也是有问题的：

^(([a-z])+.)+[A-Z]([a-z])+$

?

姿势2：

对使用的正则表达式进行人工检查。对于一些较为简单的正则表达式，在构造之后可以进行一些检查，看看是否存在以下会产生ReDoS的结构：

?(a+)+

?([a-zA-Z]+)*

?(a|aa)+

?(a|a?)+

?(.*a){x} for x > 10

?(a[ab]*)+

?

姿势3：

对使用的正则表达式进行简单的Fuzz，针对有可能会出现“递归陷阱”的结构来构造字符串，测试运行效率。

?

姿势4（仅对.NET程序员有效）：

使用IsMatch方法中的timeout选项，设置匹配超时时间。具体方法如下（C++）：

static bool IsMatch(

String^ input,

String^ pattern,

RegexOptions options,

TimeSpan matchTimeout

)

?

姿势5：

如果表达式非常复杂，上述方法不能快速判断是否有害；或者希望对现有的大量表达式进行快速判断，欢迎各位联系我们进行讨论与深入分析！

?

参考文献

《精通正则表达式》?Jeffrey E·F·Friedl

《白帽子讲Web安全》 吴瀚清

本文作者：银联安全攻防团队?富宜宇

本文转自：“银联技术”公众号https://mp.weixin.qq.com/s/RjK8oXiwQEx61QN9SzX74w