正则表达式安全研究

当探讨计算机科学中的模式匹配技术时，正则表达式（Regular Expressions，通常简称regexp）无疑是一项强大的工具。它广泛应用于文本处理的各个方面，如搜索、编辑或者操控字符串。正则表达式允许用户通过定义特定的字符组合来查找、替换以及操作文本，其应用范围从简单的数据校验到复杂的系统日志分析等不一而足。正则表达式使用广泛，如果使用不当，会带来一些安全问题。

本文主要讨论正则表达式引起的ReDoS拒绝服务，侧信道泄露，权限绕过，数据校验，回溯限制以及正则执行问题。

正则表达式底层通常会使用NFA非确定性有限自动机来实现，将正则匹配转换为路径匹配。举几个例子：

表达式一a：消耗1个字符a，可以从起始0到达终态1实现match

表达式二a*：消耗0个或多个字符a，可以从起始0到达终态1实现match，图中ε表示空串

空字符串可以直接从0->1找到一条访问路径, aa形式的字符串可以0->2->3->4->2->3->4->1的方式找到一条访问路径实现match

到此时似乎一切都没什么问题？看接下来的一个表达式

表达式三(a*)*b：其NFA图如下：

可以看到现在的6-..>7之间的所有路径本质和表达式二一致，如果把它当作一个整体并从更高层次看0->4之间的所有路径像是一个更大的表达式二，11->12路径形式则与表达式一等同。即表达式三由两个表达式二的图以"父图和子图"的方式嵌套并添加一个表达式一构成。

现在考虑如下输入及测试：

可以看到输入每增加一个a字符，那么正则表达式消耗时间约增加一倍。

回溯问题：正则表达式匹配的时候，先按照贪婪匹配所有的a，之后尝试匹配b的时候发现匹配失败，说明当前路径不匹配，那么会进行路径回退，然后尝试另一条路径，由于"表达式二"的重复嵌套，会造成回退的路径非常多，计算量非常大，最终造成了ReDoS拒绝服务。

对于满足如下几条性质的正则表达式，会存在指数回溯问题 【时间负载度为O(2^n)，n是字符的个数】

因此之前的测试search("(a*)*b","a"*25)就满足上面的3个性质，下面看一些其它例子：

正则表达式：

分析：表达式中片段(([-.]|[_]+)?([a-zA-Z0-9]+))* ， 其中的+满足条件1，*满足条件2，条件3只要构造特定输入数据就能满足。

测试：

分析：表达式片段(([a-z])+.)+   ，第一个+满足条件1，第二个+满足条件2，条件3只要构造特定输入数据就能满足。

测试：

时间延迟通常可以作为一种侧信道技术来泄露目标信息，SQL时间盲注就是一种典型的场景。

之前介绍的ReDoS拒绝服务就存在时间延迟，那在某种程度上ReDoS能否作为侧信道来使用呢？

考虑下面场景，允许用户控制正则表达式，且来匹配一个固定的字符串。

通过上面的例子，可以看到在允许用户控制正则表达式的情况下，ReDoS反而变成了一种基于时间的侧信道泄露。当然这里只是一个理想中的情况，但思想上比较有意思分享一下。

Apache Shiro是一个安全框架，提供了认证、授权、加密、会话管理等一系列安全功能，可以简化应用程序中的身份验证和授权操作。

Shiro有两种表达式可以匹配路径，一种是AntPathMatcher，另一种是RegExPatternMatcher，其中RegExPatternMatcher用于路径的正则匹配。

这里以CVE-2022-32532为例，在Shiro<1.9.1前，若使用RegExPatternMatcher，且需权限检查的路由类似/user/.*时（存在.*），会造成权限绕过。

上述问题产生的源码：

JAVA默认的Pattern.compile(pattern) 模式中.默认不匹配换行，除非启用了DOTALL模式。

因此当用户使用/user/%0d或者/user/%0a类似的url请求时，%0d和%0a会被解码为rn，/user/%0d或者/user/%0a因而不会匹配/user/.*，也就不需要进行权限检查，可以直接访问类似如下的路由：

在PHP中，由于DOT .不匹配换行，所以只要构造seq-3212412ncustom_data 就可以绕过这里的检测，$matches[1]将会是3212412。若$idata被后续直接用于SQL拼接（认为检查通过），则通过custom_data造成SQL注入。

/^seq-(.*)/s这种方式DOT .才会匹配换行。

可以看到最大回溯限制为1000000，且不匹配返回值为0。

可以看到最大回溯限制为1000000，且匹配返回值为1。

可以看到最大回溯限制为1000000，原始数据理论上是匹配的，但当超过回溯限制1000000次时，可以看到匹配返回值为bool(false)。如果/.*(-).*/is意图本身是黑名单检测，那么这种场景就会造成黑名单的绕过。

正则替换函数preg_replace配合/e可产生代码执行，是PHP专有参数。

preg_replace() - /e modifier is deprecated since PHP 5.5 and removed since PHP 7.0

注意：这里的/e从php7.0开始被移除。

综上所述，正则表达式作为文本处理的重要工具，在提高工作效率的同时，也要求使用者具备一定的安全意识与实践技巧。通过合理设计与应用正则表达式，不仅可以增强数据处理的准确性和效率，还能有效避免潜在的安全问题。

1.  Regular expression Denial of Service - ReDoS

2.  A Rough Idea of Blind Regular Expression Injection Attack