正则表达式原理与ReDos攻击

发表于

问题背景

在研究 ReDos攻击 时，涉及到两个问题

  1. 实现正则表达式的算法，比如NFA和DFA是什么？
  2. 我们用的编程语言如Python、PHP等的正则功能是怎么实现的？

研究过程

正则表达式算法

关于NFA和DFA的讲解和实现，推荐读者看 16 | NFA和DFA：如何自己实现一个正则表达式工具？ 这篇文章，讲得深入浅出，并配有Java代码demo。

我用Python实现了课程的内容，代码在 regex。

这一部分我想说的是：

在研究ReDos攻击时，我们只要知道”NFA算法中回溯可能会造成计算量暴增，从而导致ReDos”这个结论就可以。

不过知道一些算法原理，我感觉可以在我们验证语言是采用哪种算法时心里更有底一些。想要自动化检测可能产生ReDos的正则时，对正则原理也需要知道。

编程语言的正则是怎么实现的？

我测试了下面几个语言的正则，我自己把他们划分成两类：

  • 第一类
    • C (pcre库)
    • Lua
    • Nginx (ngx.re模块)
    • PHP
  • 第二类
    • Python

测试代码我放在了 regex_test

我划分这两类仅仅依据”是否依赖PCRE库”

第一类

先说结论：依赖PCRE实现的正则只要配置好最大回溯次数的，就没有ReDos问题。

我把”基于PCRE库实现的正则功能”的算到了第一类中，PCRE的详细介绍可以查看man手册。

PCRE库是有两套API接口的。执行man pcrematching命令可以在man帮助手册查看到算法相关的描述。

一套是基于NFA算法，调用pcre_exec等函数来做正则匹配；另一套是基于DFA算法，调用pcre_dfa_exec等函数来做正则匹配。

默认用的都是NFA算法，但是PCRE库提供配置选项，可以控制最大回溯次数，超过了回溯次数后就不匹配了。

其他语言也同样有配置选项来控制最大回溯次数，比如

PHP的pcre扩展中, 提供了俩个设置项

  
1
2
pcre.backtrack_limit //最大回溯数
pcre.recursion_limit //最大嵌套数


Nginx提供 `lua_regex_match_limit` 指令限制回溯次数

第二类

先说结论：这一类语言如果没有”最大回溯次数的配置”选项，很容易出现ReDos问题。

我把”自己实现正则算法”的归在了第二类。

这里我只看了Python语言的re模块。

CPython的re模块在c层面相关的文件有

1
2
Modules/_sre.c
Modules/sre_lib.h

具体的代码逻辑也没有细看，根据测试结果来看re模块也应该是NFA算法，且源码中没有看到调用PCRE的api所以应该不是基于PCRE实现的。

总结

通过写一个小的正则解析器demo可以理解DFA和NFA的原理和区别，NFA转换成DFA后状态机就不存在回溯了，所以DFA算法没有ReDos问题。

基于PCRE实现的正则基本都有配置选项限制回溯次数，所以出现ReDos的概率会小很多。

像CPython re模块这种自己实现NFA算法的，又没有控制回溯次数的，就很有可能出现ReDos问题。比如CVE-2020-8492、CVE-2018-1060/CVE-2018-1061

为了自动化检测ReDos问题，我们可以基于如rxxr2类似的工具开发。这些工具有没有一些漏报的情况，就需要另外研究了。