在python的正则表达式中使用用户输入是否安全?

我研究过一个程序,它允许用户输入他们自己的regex,而你是对的-他们可以(并且确实)输入需要很长时间才能完成的regex-有时比宇宙的生命周期还要长。更糟糕的是,当处理一个regex python时,它会保留gil,因此它不仅会挂起运行regex的线程,还会挂起整个程序。

限制regex的长度将不起作用,因为问题是回溯。例如,匹配regex r"(\S+)+x" 在长度n不包含“x”的字符串上,将回溯2**n次。在我的系统中,这需要一秒钟的时间来匹配 "a"*21 每增加一个字符,时间就会加倍,因此一个100个字符的字符串大约需要19167393131891000年才能完成(这是一个估计,我没有对它进行计时)。

要了解更多信息,请阅读O'Reilly的书“掌握正则表达式”——这本书有几个关于性能的章节。

编辑 为了解决这个问题,我们编写了一个regex分析函数,试图捕获和拒绝一些更明显的退化情况,但不可能得到所有这些情况。

我们看到的另一件事是修补re模块,以在它回溯太多次时引发异常。这是可能的,但需要更改python c源代码并重新编译,因此不可移植。我们还提交了一个补丁,在与python字符串匹配时释放gil,但我不认为它被接受到核心中(python只保留gil,因为regex可以针对可变缓冲区运行)。

对于临时用户来说,给他们一个子集语言要简单得多。壳牌的全球化规则 fnmatch 例如。类似SQL的条件规则是另一个例子。

将用户的语言转换为适当的regex,以便在运行时执行。

编译正则表达式应该是相当安全的。虽然它编译成的并不是严格意义上的NFA(backreferences意味着它没有那么干净),但编译成它还是有点简单。

至于性能特性,这完全是另一个问题。由于回溯,即使是一个小的正则表达式也可能具有指数时间特性。最好定义一些特性的子集,并且只支持您自己翻译的非常有限的表达式。

如果您真的想支持一般的正则表达式,您要么必须信任您的用户(有时是一个选项),要么限制使用的空间和时间。我 相信 所使用的空间仅由正则表达式的长度决定。

编辑:正如Dave所指出的,显然全局解释器锁是在regex匹配过程中保持的,这将使设置超时更加困难。如果是这种情况,设置超时的唯一选项是在单独的进程中运行匹配。虽然不完全理想,但它是可行的。我完全忘记了 multiprocessing . 兴趣点是 this section 共享对象。如果您真的需要这些硬约束,那么单独的过程就是实现这一点的方法。

不需要使用compile(),除非需要重用许多不同的正则表达式。模块已缓存最后一个表达式。

如果允许用户输入任何正则表达式,那么第2点(在执行时)可能非常困难。你可以用很少的字符组成一个复杂的regexp,比如 (x+x+)+y 一个。我认为这是一个尚未得到普遍解决的问题。 解决方法可能会启动一个不同的线程并监视它,如果超过了允许的时间,则终止该线程并返回一个错误。

我真的认为不可能简单地通过将代码传递到re.compile来执行代码。按照我理解的方式,re.compile(或任何语言的regex系统)将regex字符串转换为 finite automaton (dfa或nfa),尽管有一个不祥的名字“compile”,但它与任何代码的执行无关。

技术上你不需要使用 re.compile() 对字符串执行正则表达式操作。事实上,如果您只执行一次操作,那么编译方法通常会变慢,因为与初始编译相关联的开销很大。

如果你担心“编译”这个词,那么一起避免它,只需将原始表达式传递给 match , search 等等,您最终可能会稍微提高代码的性能。