这是一个创建于 1966 天前的主题，其中的信息可能已经有所发展或是发生改变。
转自阮一峰推特
七月初，cloudflare 曾经全球中断服务，原因是一个正则表达式耗尽了 CPU 资源。
今天，他们公布了这个正则表达式。
(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))
看着是很复杂，简化以后，出问题是这个模式 ..=.* ，它会导致急剧放大的计算量。后面链接详细解释，为什么这个模式有问题。
28 条回复 • 2019-07-15 10:50:01 +08:00
 |
1
wikinee OP 英文的看不懂了。。。
|
 |
2
yukiww233 2019-07-13 12:51:35 +08:00
正则地狱
|
 |
3
Sylv 2019-07-13 14:14:34 +08:00 via iPhone
粗略浏览了下，其实和飞机失事一样，并不是单一问题导致的，而是一连串原因导致保险措施失效。
|
 |
4
caomu 2019-07-13 14:15:28 +08:00 via Android  5
当你有一个问题，想用正则解决时，你就有两个问题了。
|
 |
5
keith1126 2019-07-13 14:16:04 +08:00 9
当初 v2 上面还有一大群人说是因为政治原因被我国攻击...
真是有趣啊 |
 |
6
doing1 2019-07-13 14:23:52 +08:00
说实话，看着感觉有点乱，我晕了
|
 |
7
rrfeng 2019-07-13 14:38:30 +08:00 via Android
反正我绝不在一个正则里写多个 .*
因为我自己都会看不懂了。 |
 |
8
xiadong1994 2019-07-13 14:39:33 +08:00 4
简单来说就是 .*.*=.* 这种正则在匹配的时候会造成太多回溯使时间复杂度飙升。解决方案是把正则转换成 NFA （非确定有限自动机）这样时间复杂度就是对于输入数据线性的。难道主流正则实现不是基于 NFA 的？我记得编译原理学正则的时候就是用的 NFA 啊……
|
 |
9
miaomiao888 2019-07-13 14:45:16 +08:00 14
@keith1126 时间刚好赶上 H.K 那事
对一个惯犯有这种怀疑也太正常了 |
 |
10
cest 2019-07-13 14:50:44 +08:00
所以测试时没注意 benchmark 差了些就上线了?
|
 |
11
gam2046 2019-07-13 14:50:45 +08:00
>> Some of these alerts hit my watch and I jumped out of the meeting I was in and was on my way back to my desk when a leader in our Solutions Engineering group told me we had lost 80% of our traffic. I ran over to SRE where the team was debugging the situation. In the initial moments of the outage there was speculation it was an attack of some type we ’ d never seen before.
这怕是要举国家之力，才有可能让全球节点都挂掉吧，甚至我觉得哪怕除了美国以外，其他国家以国家之力都做不到，毕竟出口带宽就这么点。 |
 |
12
anzu 2019-07-13 14:54:59 +08:00
在 python 中试了一下很快呀
re.match('.*.*=.*', 'x=xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx').group() |
 |
13
kelaredbull 2019-07-13 14:57:29 +08:00 via Android
@miaomiao888 程序员每天都在写 bug，你为什么不怀疑呢
|
|
14
keith1126 2019-07-13 14:58:37 +08:00 1
|
|
15
miaomiao888 2019-07-13 15:07:39 +08:00 10
@keith1126 所以谷歌为什么无法访问，某网站为什么被重置，请从技术角度出发？
我只是解释你说的某些人从政治角度怀疑的合理性 引一条推：@Solitude_Sola 被 G.F.W 折磨多年都有了自我加害的心理问题，上不去一个网站一口咬定是自己翻不出去，折腾老半天代理，甚至重新部署。这才确定了是那个网站服务器宕机了。 |
 |
16
KuroNekoFan 2019-07-13 15:11:26 +08:00 1
刚出事那会挺多人都觉得是 cn gov 级别的攻击...不过 wall 真的，从任何角度来说都是非常恶心的玩意
|
 |
18
uyhyygyug1234 2019-07-13 16:26:02 +08:00
哈哈哈，日了狗，这是故障报告要写给大众看啊。程序员一定压了很大。
另外，waf minor release 看的出来，他们用的是 jira。。。。 |
 |
19
UnluckyNinja 2019-07-13 16:53:12 +08:00
楼主把简化后的正则打错了
|
 |
20
jinliming2 2019-07-13 18:58:05 +08:00
嗯，测试了一下，CPU i7-9700K，字符串 `'a=xxx...xxx'`（后跟 2 万个 x ），正则 `/.*.*=.*/` 需要大约 0.3 秒跑出结果。。。
for 循环 100 次，就可以感受到速度真的很慢了。。。 |
 |
21
operawang 2019-07-13 19:05:56 +08:00
@jinliming2 把 a=去掉再试试，文章说不匹配更耗资源。
|
 |
22
snw 2019-07-13 19:41:56 +08:00
|
 |
23
U2FsdGVkX1 2019-07-13 21:54:00 +08:00
@miaomiao888 有一部分留言像是带节奏，说白了就是没石锤的预测当真了，早就脱离怀疑范围了
|
 |
25
skyeycirno 2019-07-13 21:59:41 +08:00
又扩大了一点黑名单，真好
|
 |
26
hoyixi 2019-07-13 22:01:51 +08:00
这么长&复杂的正则，就算是我自己写的，上个厕所撒泡尿，恐怕我就忘了是神马玩意了
|
|
27
wikinee OP @UnluckyNinja 雨我无瓜，我复制过来的，被吞掉了
|
|
28
wikinee OP |
Select Language