如何为正则表达式引擎生成最重的内容？

我想知道如何自动生成小而重的内容以匹配某个正则表达式。我的意思是，对于某种表情，我正在寻找最小和最重的有效载荷。形式上称heavy值是 H = regexp engine work time/content length 鉴于有一个最大内容长度如何为正则表达式引擎生成最重的内容？

例正规表达式([\w%]+=[\w%]*&){500}：这需要〜2500个步骤来检查内容相匹配

A=& ... (498 times) ... A=&

，它需要〜250倍更多步骤检查内容是否不匹配

A=& ... (498 times) ... A=

我的观察结果如下：

正则表达式开始用wildchar序列（前）/^\w+.../是最坏的正则表达式引擎
当它试图匹配正则表达式，直到内容结束即内容不应与一般引擎执行更多的计算正则表达式

构建这种有效载荷的线索是什么？

是否可以自动生成这样的有效载荷？

来源

2017-05-03 academica

and it takes ~250 times more steps to check that content doesn't match

但步骤不给性能的真正指标。

不确定您的意思是有效载荷。但在失败模式下测试
您的正则表达式总是一个好主意（即让它失败）。

问题是你的正则表达式包含一个固定范围，最小（500）量词。

即使您的表达式不包含
包含嵌套量词，它也会启动回溯机制。

既然你标记PCRE，它能够更好地在由{500}量化表达式中使用原路返回控制动词的一个
地方。
这将退出即组的返回机制。
并且在匹配(*SKIP)的字符串中，禁止引擎返回。

你可以得到这个应用程序RegexFormat为Windows
运行一些测试/基准场景。我有一个内置的基准测试工具。

时间来匹配：

Regex1: ([\w%]+=(?:[\w%]*&|(*SKIP)(*FAIL))){500} 
Completed iterations: 1/1  (x 1000) 
Matches found per iteration: 1 
Elapsed Time: 0.26 s, 256.59 ms, 256588 µs

的时间失败：

Regex1: ([\w%]+=(?:[\w%]*&|(*SKIP)(*FAIL))){500} 
Completed iterations: 1/1  (x 1000) 
Matches found per iteration: 0 
Elapsed Time: 0.27 s, 270.76 ms, 270765 µs

来源

2017-05-04 02:00:41 sln

嘿，谢谢。我的整个想法是关于是否有可能导致最差性能的正则表达式功能（当然是在失败模式下）？我将在自动或半自动模式下搜索这些正则表达式，并利用它们导致regexp引擎的拒绝服务。我在Linux上，所以有任何在线基准测试工具？ – academica

如何为正则表达式引擎生成最重的内容？

回答

相关问题