分析正则表达式性能问题
发布时间：2021-12-14 23:17:46 所属栏目：安全 来源：互联网
导读：关于FUSE FUSE是一款功能强大的渗透测试安全工具，可以帮助广大研究人员在最短的时间内迅速寻找出目标软件系统中存在的文件上传漏洞。 FUSE本质上是一个渗透测试系统，主要功能就是识别无限制可执行文件上传（UEFU）漏洞。关于UEFU无限制可执行文件上传漏洞
|
关于FUSE FUSE是一款功能强大的渗透测试安全工具，可以帮助广大研究人员在最短的时间内迅速寻找出目标软件系统中存在的文件上传漏洞。 FUSE本质上是一个渗透测试系统，主要功能就是识别无限制可执行文件上传（UEFU）漏洞。关于UEFU无限制可执行文件上传漏洞的相关内容，可以参考这篇【文章】，该文章发表于NDSS2020。关于如何配置和执行FUSE，请参阅以下内容。 工具安装 当前版本的FUSE支持在Ubuntu 18.04和Python 2.7.15环境下工作。 首先，我们需要使用下列命令安装好FUSE正常运行所需的依赖组件： # apt-get install rabbitmq-server # apt-get install python-pip # apt-get install git 接下来，将该项目源码克隆至本地： $ git clone https://github.com/WSP-LAB/FUSE 并切换至项目目录下配置好依赖环境： $ cd FUSE && pip install -r requirements.txt 如果你想要使用selenium实现无头浏览器验证的话，你还需要安装好Chrome和Firefox Web驱动器。【文档】 工具使用 FUSE配置 FUSE使用了用户提供的配置文件来为目标PHP应用程序指定参数。在测试目标Web应用程序之前，必须将相关参数提供给脚本执行。具体请参考项目的README文件或配置文件参考样例。 针对文件监控器的配置样例（可选）： $ vim filemonitor.py ... 10 MONITOR_PATH='/var/www/html/' <- Web root of the target application 11 MONITOR_PORT=20174 <- Default port of File Monitor 12 EVENT_LIST_LIMITATION=8000 <- Maxium number of elements in EVENT_LIST ... FUSE执行 FUSE： $ python framework.py [Path of configuration file] 文件监控器： $ python filemonitor.py Cloudflare WAF 的引擎还是 backtraking，所以导致错误的正则写法产生回溯问题，最终 ReDos（正则表 达式拒绝服务攻击）。它会导致计算量急剧的放大，使大量网站访问出现了 502。 正则引擎原理 提到正则表达式引擎，首先需要涉及到一个概念：有限状态自动机。 有限状态自动机（FSM "finite state machine" 或者FSA "finite state automaton" ）是为研究有限内存 的计算过程和某些语言类而抽象出的一种计算模型。有限状态自动机拥有有限数量的状态，每个状态 可以迁移到零个或多个状态，输入字串决定执行哪个状态的迁移。 传统正则表达式引擎分为两类，分别是 NFA（非确定性有限状态自动机）和 DFA（确定性有限状态自动机）。 最直观的区别就是 NFA 在语法解析的时候，构造出的一个有向图。然后通过深搜的方式，去一条路径一 条路径的递归尝试，因此速度较慢，不过实现的功能更丰富，对正则编写功底较高，否则容易因为回溯造 成性能问题。DFA 会把正则表达式转换成一个图的邻接表，然后通过跳表的形式判断一个字符串是否匹 配该正则，因此匹配速度较快，但是不支持捕获组和断言等功能。 Cloudflare 的正则分析 (?:(?:"|'|]|}||d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|-|+)+[)]*;?((?:s|-|~|!|{}||||+)*.*(?:.*=.*))) Cloudflare WAF 简化正则之后的出问题的其实是.*.*=.*这个模式。这个模式看起来并不是很复杂，要求 正则引擎匹配任何值 = 任何值，但是这会导致非常严重的回溯问题。 在正则表达式中 . 表示匹配单个字符，而.*表示尽可能多的匹配字符（贪婪匹配，可以是零个字符），在 使用贪婪匹配或者惰性匹配或者或匹配进入到匹配路径选择的时候，遇到失败的匹配路径，尝试走另外一 个匹配路径的这种行为，称作回溯。因此 .*.*=.* 表示匹配零个或多个字符，然后匹配零个或多个字符， 然后匹配一个 = 字符，然后匹配零个或多个字符。 我们使用 a=b来作为测试文本，正则引擎为 PCRE2（PHP>=7.3）。 第一个 .* 贪婪匹配 0 个字符 第二个 .* 贪婪匹配剩余全部字符 = 尝试匹配，由于没有更多字符可以匹配了，匹配失败 引擎向前回溯 第二个 .* 贪婪匹配到字符 a= = 尝试匹配字符 b，匹配失败 引擎向前回溯 第二个 .* 贪婪匹配到字符 a = 尝试匹配字符 b, 匹配失败 = 尝试向前匹配 =，匹配成功 第三个 .* 贪婪匹配 0 个字符 第三个 .* 贪婪匹配剩余全部字符，正则完成全部字符匹配 不同语言自带的正则性能比较 避免此类问题的方法就是尽可能使用高效的正则表达式引擎，比如 RE2、Rust、PCRE等，不同的引擎之 间有着较大的性能差异，这里使用 Regex进行测试，测试仅供横向对比参考，不同的表达式在不同的引擎 上各有优劣，实际速度与计算机性能相关。 正则表达式为.*.*=.*;，测试文本为a=bb…bb（100 个 b），进行多次测试。 PHP（PCRE），耗时 0.7ms-1ms JavaScript速度较快，0.4ms-0.6ms Python耗时 0.7ms-0.8ms Golang最慢，耗时大于 165ms Java耗时大于 5ms 注：JavaScript 在 Chrome Console 中使用表达式X(.+)+X的测试耗时超过 20s，而在 Regex的测试中 耗时约为 200ms ，可能是对 JavaScript 的实现不同导致的。从 Chrome 88 开始，Chrome 新增了一 项实验性非回溯 RegExp 引擎，它可以保证在字符串长度变大的情况下保持线性的时间变化，可以在 添加启动参数--enable-experimental-regexp_engine-on-excessive-backtracks在过多的回溯上 启用对非回溯引擎的回退（NFA 与 DFA 混用）。 优化建议 某些格式的正则表达式可能涉及大量查找最佳匹配工作，会导致性能的降低，甚至产生预期之外的结果。 正则表达式的很多优化技巧都是围绕着减少回溯这样一个原则进行优化的。 例如要匹配;之前并且包括该字符的文本，不要使用模式.*;，此模式将匹配文本中最后一个;字符之前的 文本，其中包括匹配的文本中前面的所有;，使用[^;]*;则可以避免很多无效的匹配。 同样的，.*模式会强制匹配到文本的末端并开始查找最佳匹配导致性能较差，除非要匹配到所有剩余数据。 具有冗余嵌套重复的表达式，如([a-z0-9]+)*会导致查找最佳匹配时进行多次搜索，尽可能使用精准匹 配条件来使表达式保持简单。 使用取反^代替.进行精准匹配也是不错的选择，如匹配字符串<div style="color: red">123456</div>，表达式<div[^?>]+>[^<]+</div>只用了 14 次匹配，而表达式<div.*?>.*?</div>的匹配次数达到了 39 次。 总结 造成 Cloudflare 这次事件的原因是使用了性能较差的正则引擎以及有问题的正则表达式，造成了灾难性 的回溯（然而大部分语言的正则引擎都是使用NFA）。使用 DFA 或许是个好办法，但是不支持断言等功 能使会易用性降低。平时写正则的时候尽可能少用模糊匹配可以有效缓解回溯问题。关于 NFA 与 DFA 原 理更详细的解释可以参考这篇文章 DFA和NFA。 （编辑：源码门户网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
