使用Python的正则表达式的用户输入是否安全？

Question

我想让我的用户使用正则表达式来实现某些功能.我很好奇将用户输入传递给re.compile()的含义是什么.我假设用户没有办法给我一个可以让他们执行任意代码的字符串.我想到的危险是:

1. 用户可以传递引发异常的输入.
   • 用户可以传递导致正则表达式引擎花费很长时间的输入,或者使用大量内存.

1.解决方案很简单:捕获异常.我不确定是否有一个很好的解决方案2.也许只是限制正则表达式的长度会起作用.

还有什么我需要担心的吗？

Answer 1

我已经开发了一个程序,允许用户输入他们自己的正则表达式,你是对的 - 他们可以(并且确实)输入可能需要很长时间才能完成的正则表达式 - 有时长于宇宙的生命周期.更糟糕的是,虽然处理正则表达式Python持有GIL,所以它不仅会挂起运行正则表达式的线程,而且会挂起整个程序.

限制正则​​表达式的长度是行不通的,因为问题是回溯.例如,r"(\S+)+x"在不包含"x"的长度为N的字符串上匹配正则表达式将回溯2**N次.在我的系统上,这需要大约一秒钟来匹配,"a"*21并且每个附加字符的时间加倍,所以一个100个字符的字符串将花费大约19167393131891000年来完成(这是一个估计,我还没有计时).

有关更多信息,请阅读O'Reilly的书"掌握正则表达式" - 这里有几章关于性能的章节.

编辑 为了解决这个问题,我们编写了一个正则表达式分析函数,试图捕获并拒绝一些更明显的退化情况,但是不可能得到所有这些.

我们看到的另一件事是修补re模块,如果它回溯太多次,就会引发异常.这是可能的,但需要更改Python C源代码并重新编译,因此不可移植.我们还提交了一个补丁,以便在匹配python字符串时释放GIL,但我不认为它被接受到核心(python只保存GIL,因为正则表达式可以针对可变缓冲区运行).

Answer 2

对于临时用户来说,为他们提供子集语言要简单得多.例如,shell在fnmatch中的globbing规则.SQL LIKE条件规则是另一个例子.

将用户的语言转换为正确的正则表达式,以便在运行时执行.