有没有办法将恶意代码放入正则表达式？

Question

我想在我的公共网页上添加正则表达式搜索功能.除了编码输出的HTML之外,我是否需要做任何事情来防止恶意用户输入？

谷歌搜索被解决逆向问题的人淹没 - 使用正则表达式来检测恶意输入 - 这是我不感兴趣的.在我的场景中,用户输入是一个正则表达式.

我将在.NET(C#)中使用Regex库.

Answer 1

拒绝服务问题

正则表达式最常见的问题是通过指数 - 甚至超指数 - 的病态模式的拒绝服务攻击! - 所以似乎需要永远解决.这些可能仅出现在特定的输入数据上,但通常可以创建一个无关紧要的输入数据.

这些中的哪些将取决于您正在使用的正则表达式编译器的智能程度,因为其中一些可以在编译期间被检测到.实现递归的正则表达式编译器通常具有内置的递归深度计数器,用于检查非进展.

Russ Cox 2007年关于正则表达式匹配的优秀论文可以简单快速(但在Java,Perl,PHP,Python,Ruby等方面很慢)谈论大多数现代NFA的方式,这些似乎都来自Henry Spencer的代码,遭受严重的性能下降,但汤普森风格的NFA没有这样的问题.

如果你只承认可以由DFA解决的模式,你可以这样编译它们,它们运行得更快,可能更快.但是,这需要时间.考克斯报告提到了这种方法及其伴随的问题.这一切都归结为经典的时空权衡.

使用DFA,您需要花费更多时间来构建它(并分配更多状态),而使用NFA则需要花费更多时间来执行它,因为它可以同时处于多个状态,并且回溯可以吃午餐 - 以及您的CPU.

解决这些模式的最合理的方法可能是在宇宙热死亡的竞赛中失败,用一个计时器包裹它们,有效地为执行它们留出了最多的时间.通常,这将远远大于大多数HTTP服务器提供的默认超时.

有各种方法可以实现这些,从alarm(N)C级简单到某种类型try {}阻止警报类型异常,一直产生一个新的线程,该线程是专门用内置的时序约束创建的.

在允许代码标注的正则表达式语言中,应该提供一些允许或禁止从您要编译的字符串中删除这些内容的机制.即使代码标注只是用你正在使用的语言编写代码,你也应该限制它们; 他们没有必要能够调用外部代码,但如果可以的话,你会遇到更大的问题.

例如,在Perl中,不能在字符串插值创建的正则表达式中使用代码调用(因为它们是在运行时编译的,因为它们在运行时编译),除非use re "eval";在当前作用域中激活了特殊的词法范围的编译指示.

这样,没有人可以潜入代码标注来运行系统程序rm -rf *,例如.由于代码标注对安全性非常敏感,因此默认情况下Perl会在所有插值字符串上禁用它们,并且您必须不再重新启用它们.

仍然与Unicode的样式属性一个更安全的敏感问题-像\pM,\p{Pd},\p{Pattern_Syntax},或者\p{Script=Greek}-这可能支持该符号在一些正则表达式的编译器存在.

问题在于,在其中一些中,可能的属性集是用户可扩展的.这意味着你可以拥有自定义属性,它们是某些特定名称空间中命名函数的实际代码标注,如\p{GoodChars}或\p{Class::Good_Characters}.您的语言如何处理这些可能值得一看.

在Perl中,通过Safe模块的沙盒隔离区可以控制名称空间可见性.其他语言提供类似的沙盒技术.如果此类设备可用,您可能需要查看它们,因为它们专门用于限制执行不受信任的代码.

Answer 2

添加到tchrist的优秀答案:编写"正则表达式"页面的同一个Russ Cox也发布了代码!re2是一个C++库,它保证O(length_of_regex)运行时和可配置的内存使用限制.它在Google中使用,因此您可以在谷歌代码搜索中键入正则表达式 - 这意味着它已经过战斗测试.

Answer 3

是.

Answer 4

你想读这篇论文:

不安全的上下文切换:为生存性接种正则表达式本文更多地讲述了正则表达式引擎(例如PCRE)可能出现的问题,但它可以帮助您理解您的反对意见.

Answer 5

您不仅要担心匹配本身,还要考虑如何进行匹配.例如,如果您的输入在前往正则表达式引擎的过程中经历某种类型的eval阶段或命令替换,则可能存在在模式内执行的代码.或者,如果您的正则表达式语法允许嵌入式命令,您也必须对此保持警惕.由于您未在问题中指定语言,因此很难确定所有安全含义是什么.