nginx的正则回溯和灾难性回溯

正则的回溯

我们先了解一下什么是回溯

https://zhuanlan.zhihu.com/p/27417442

这篇文章将的比较详细，我选取其中一个例子给大家简单介绍一下

当用 /".*"/  匹配字符串 "acd"ef 时，下面是匹配过程

简单总结一下

贪婪匹配 (.*) 后面紧跟字符 g，（.*）的匹配范围是 g匹配范围的父集，这种写法必定会导致字符 g 的匹配失败而产生回溯

字符串中 g 到 (.*) 所匹配的字符结尾间的字符越多，回溯次数越多。如果字符串中没有g，则会全部回溯

我们线上nginx 都采用的 正则匹配，平时我们提单新增location的时候如果正则写地很随意就很容易写回溯的正则影响nginx匹配的效率。下面我举一个例子

location ~ ^/re/(.*)/g 

这个正则就是一个不好的写法

    用 .* 匹配范围太广，不够明确。这个正则可以匹配多种 url 比如 /re/aaa/g/eee   /re/aaa/bbb/g/eee /re/aaa/geee  等

    此外使用 .* 会引起回溯， g 后面的字符越多，回溯越严重，造成性能损耗

    

假如业务的url是  /re/aaa/g/eee   /re/aaa/bbb/g/eee /re/aaa/geee 这三种都有，那实际更好的写法是

location ~ ^/re/[^g]+/g 

我在nginx上分别压测了一下上面两种配置，url 为 /re/aa/gaaaaaaaaa ，g后面有10个字符，第一种写法54336 第二种是 55964 ，第二比第一种性能提高了3%，如果url更长性能差距会更大

灾难性回溯

如果说上面的回溯造成的一点性能上的损失还可以接受的话，那灾难性回溯造成的影响就很难忽略了

灾难性回溯简单来说就是在正则表达式中过于粗暴得使用了 *、+ 和 ？等量词限定符的组合和嵌套，导致在匹配某些特定类型的字符串的时候，回溯次数随着字符串长度的增加而指数级上升。这会造成服务的cpu资源占用很高而影响正常的业务逻辑执行

下面举两个的例子

regex = /^(\w+s?)*$/
test_str = "An input string that takes a long time or even makes this regexp to hang!"
 
regex = /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/
test_str = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

大家可以用自己常用的语言试一下上面两个例子，看看自己所用语言的正则引擎有没有回溯的问题

https://zh.javascript.info/regexp-catastrophic-backtracking

这篇文章介绍了灾难性回溯的过程，以 (d+)*$ 匹配 12345! 为例，由于 * 的存在，正则引擎匹配到！失败后，会尝试

\d+\d+
\d+\d+\d+

......

多种方式排列组组合来匹配字符串，随着数字长度的增加，回溯次数会成指数级增长

https://regex101.com/r/LbX3JI/1

大家可以在这里开启debug 工具来直观的感受一下回溯过程

之前说到nginx 使用的是pcre库，这就会存在灾难性回溯的问题

好消息是在测试中发现nginx 对回溯次数是有限制的

虽然没有查到具体的值是多少，翻了nginx源码，nginx在调用pcre_exec() 的是时候貌似没有特别设置限制次数，根据pcre 文章的介绍，默认值是 1000万，经过测试差不多是这个值，回溯次数超过1000万的时候，nginx 会中断请求 返回500，error log 中报错pcre_exec() failed: -8 

nginx lua 模块则可以通过设置 lua_regex_match_limit 100000; 来手动限制lua函数中的回溯次数

坏消息是这并不能根本性的解决回溯的问题， nginx 默认1000万的回溯次数仍会消耗大量cpu资源。

nginx 发生灾难性回溯造成影响

会造成集群故障

由于灾难性回溯会消耗大量cpu资源，单个nginx worker 7qps的异常请求就能把cpu 使用到100%，对于一个10台40核服务器的nginx集群，几千qps的请求就能干崩整个集群

异常定位非常困难

灾难性回溯造成线上影响的排查很困难，故障的产生需要一些特定流量才会触发，流量的增加和配置的上线时间节点不一定一致，对于缺乏经验的同学来说想要定位到异常配置需要花费大量时间

几种nginx配置中不推荐的正则写法

下面几种配置的写法不会造成灾难性回溯，但是我们极不推荐这些写法，他们很有可能在某些需求下错写成易造成灾难性回溯的正则

我都以location 配置为例

lcoation ~ ^/test(/.*)*$

这个写法如果不熟悉nginx同学可能觉得没啥问题，但实际上他等价于 lcoation ~ ^/test

location ~ ^/test/(-\w+)*$ 

这种写法括号里有分隔符 - ，他不会造成灾难性回溯，但是如果改成 location ~ ^/test/(-?w+)*$  就会有灾难性回溯的风险，而写正则的同学可能完全意识不到这二者影响大小的区别

类似的还有这种写法

lcoation ~ ^/test/(\w+/?)*$

这个乍一看去好像很合理，没有用 .* ，甚至还考虑到了url随后有无斜杠两种情况，但它会造成灾难性回溯

简单总结一下nginx 配置中容易造成灾难性回溯的写法

在正则中使用了 * + 嵌套，并紧随其后有其他字符的匹配。比如$

(\w*)*$ 

(\w+)*$ 

(\w+)+$ 

(\w*)+$

(\w*)*/

(\w*)*\d

嵌套正则匹配完后，发现其后面的正则匹配失败时便会回溯

如何解决

根本的解决办法就是跟换正则引擎，但这对于我们nginx来说成本太高，并且有兼容现有正则的问题

避免 .* 的使用，减少回溯

尽量避免线上nginx中使用复杂正则

禁止使用 量词限定符 * + 的正则嵌套

以上就是本篇文章的全部内容。正则的实现原理是很复杂的，我们平时在写正则的时候往往就是能匹配到就行而忽略了正则的匹配原理，这样时间长了就可能会踩到意想不到的坑里