在sed中如何避免回溯

Question

我想知道如何在sed中使用正则表达式原子组(non-capturing组)。原子组对于通过占用服务器内存来避免任何拒绝服务攻击非常有用，所谓的灾难性回溯，以及性能明智的原子组都是非常有用的。

找到以下链接，请使用re2 engine关闭回溯。

您可以使用re2引擎(非回溯引擎)完全关闭回溯。我的问题是，为什么我们不能在sed中使用相同的方法，如果我们可以在sed中定义原子组或非捕获组的话。

谢谢

Answer 1

你问了几个问题。答案是appeared before in SO。sed不提供不匹配的父母。

要回答另一个问题，你只需仔细阅读re2的文档。sed's (以及Perl、Python、Java等)和确定性有限自动机(DFA)-based匹配器(如re2 )所使用的分支和绑定匹配器所使用的机制本质上是不同的。sed的识别器中没有一种cut操作可以满足您的需要。

话虽如此，re2文档忽略了它的负面影响。编译DFA要比将regex转换为例如Perl的匹配器内部使用的字节码要复杂得多。因此，Perl程序不会因为regex编译而减慢。实际上，re2编译器可以在某些短的正则表达式上“爆炸”，并生成大小为正则表达式的DFA。因此，编译器需要指数时间运行，而re2技术将不良行为从运行时转移到编译。

我同意re2的观点，一般来说，让坏的行为依赖于正则表达式比输入要好得多。如果编程语言中的所有嵌入式regex识别器都使用re2方法，将是一个更好、更安全的世界。

最后，您的问题似乎将大小和运行时间混为一谈。来自回溯识别器的DOS之所以出现，是因为某些短输入需要输入长度中的指数时间才能识别(或拒绝)。由于regex不能捕获超过(短)输入长度，捕获或缺少捕获没有任何影响。

您可能会想到的另一种DOS是用户提供了一个怪物输入，而sed识别器被迫在内部存储这些输入，因为它只有非捕获组，即使从未使用捕获。这当然是对至少一些sed实现造成问题的一种方法(假设智能实现可以确定不需要捕获并跳过捕获；我不认为GNU代码会这样做)，但只有在允许大量输入的情况下才会发生这种情况，通常可以通过其他方法来防止这种情况。为什么sed中没有非捕获组？从历史上看，它是一个非常古老的程序，可以追溯到一些最初的Unix机器。在那些日子里人们并不担心DOS。

Answer 2

您可以通过使用锚和在几乎所有regex引擎中变得更详细来避免回溯。另外，捕获组和非捕获组在管理费用上的差异很小，它们都只是将开始和结束偏移保持在输入范围内。捕获组有污染反向引用命名空间的缺点。