编辑推荐

网易数帆开源API网关与容器云项目，让云原生生产落地“多快好

网易汪源：统一负载与多云环境的“开放姿态”，才是云原生

网易数帆如何用 Kubernetes“原语”搞定云原生中间件

快手打新挤爆券商系统，网易数帆推出券商稳定性保障方案

探索智慧校园新模式，网易有数在教育行业的实践分享

金融行业大数据治理之路——数据模型篇

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

达芬奇密码2018-08-24 15:45

问题

一天晚上突然收到同事反馈，其使用的一个正责表达式对收货人姓名处理时，输入某种字符不能正确保存，现象为服务端请求卡死，没有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步处理才发现是不符合要求的。下面通过介绍正则表达式的匹配模式去分析一下该如何处理。