正则表达式

一、前言 当探讨计算机科学中的模式匹配技术时，正则表达式（Regular Expressions，通常简称regexp）无疑是一项强大的工具。它广泛应用于文本处理的各个方面，如搜索、编辑或者操控字符串。正则表达式允许用户通过定义特定的字符组合来查找、替换以及操作文本，其应用范围从简单的数据校验到复杂的系统日志分析等不一而足。正则表达式使用广泛，如果使用不当，会带来一些安全问题。 本文主要讨论正则表达式引起的ReDoS拒绝服务，侧信道泄露，权限绕过，数据校验，回溯限制以及正则执行问题。 二、ReDoS 拒绝服务 正则表达式底层通常会使用NFA非确定性有限自动机来实现，将正则匹配转换为路径匹配。举几个例子： 表达式一a：消耗1个字符a，可以从起始0到达终态1实现match 表达式二a*：消耗0个或多个字符a，可以从起始0到达终态1实现match，图中ε表示空串 空字符串可以直接从0->1找到一条访问路径, aa形式的字符串可以0->2->3->4->2->3->4->1的方式找到一条访问路径实现match 到此时似乎一切都没什么问题？看接下来的一个表达式 表达式三(a*)*b：其NFA图如下： 可以看到现在的6-..>7之间的所有路径本质和表达式二一致，如果把它当作一个整体并从更高层次看0->4之间的所有路径像是一个更大的表达式二，11->12路径形式则与表达式一等同。即表达式三由两个表达式二的图以"父图和子图"的方式嵌套并添加一个表达式一构成。 现在考虑如下输入及测试： # 后续文中使用的search都是该函数 # 主要用于打印正则匹配消耗的时间，单位s def search(r,s): a=time.time() re.match(r,s) b=time.time() c=b-a print("use:"+str(c)) >>> search("(a*)*b","a"*22) use:0.24314594268798828 >>> search("(a*)*b","a"*23) use:0.4825863838195801 >>> search("(a*)*b","a"*24) use:1.0666351318359375 >>> search("(a*)*b","a"*25) use:2.1269423961639404 可以看到输入每增加一个a字符，那么正则表达式消耗时间约增加一倍。 回溯问题：正则表达式匹配的时候，先按照贪婪匹配所有的a，之后尝试匹配b的时候发现匹配失败，说明当前路径不匹配，那么会进行路径回退，然后尝试另一条路径，由于"表达式二"的重复嵌套，会造成回退的路径非常多，计算量非常大，最终造成了ReDoS拒绝服务。 对于满足如下几条性质的正则表达式，会存在指数回溯问题 【时间负载度为O(2^n)，n是字符的个数】 ReDos是一种算法复杂度攻击，通过提供最坏情况输入来利用算法的攻击。 将 +/* 应用到一个子正则表达式A 子正则表达式A可以多种方式重复匹配相同的输入，比如 a|a / a+ / a|aa 等就能重复匹配输入 在重复的表达式之后要存在一个无法与输入匹配的表达式B 【以便让匹配失败，从而路径回退】 因此之前的测试search("(a*)*b","a"*25)就满足上面的3个性质，下面看一些其它例子： 2.1 情形一：邮件格式匹配 正则表达式： ^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*(@) {1}[a-z0-9]+[.]{1}(([a-z]{2,3})|([a-z]{2,3}[.]{1}[a-z]{2,3}))$ 分析：表达式中片段(([\-.]|[_]+)?([a-zA-Z0-9]+))* ， 其中的+满足条件1，*满足条件2，条件3只要构造特定输入数据就能满足。 测试： >>> search("^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))* (@){1}[a-z0-9]+[.]{1}(([a-z]{2,3})|([a-z]{2,3}[.]{1}[a-z]{2,3}))$", "a"*25) use:2.2077696323394775 2....