logo标签列表

Java: Matcher.find 使用高CPU利用率

javaregexperformance
5
我正在使用mod security规则https://github.com/SpiderLabs/owasp-modsecurity-crs来清理用户输入数据。我发现CPU飙升，匹配用户输入和mod security规则正则表达式有延迟。总体上，它包含500多个正则表达式，用于检查不同类型的攻击（如xss、badrobots、通用和sql）。对于每个请求，我都会通过所有参数，并检查所有这些500个正则表达式。我正在使用Matcher.find来检查参数。在这种情况下，一些参数会出现无限循环，我用以下技术解决了这个问题。

取消长时间运行的正则表达式匹配？.

清理用户请求大约需要~500毫秒，CPU％飙升。我使用test suite runner和visualvm.java.net进行了分析。

Cpu Profile 输出

enter image description here

请帮助我降低CPU使用率％和负载平均值？

5
根据截图显示，checkPattern总共被调用了212148825次，总计时间为6100774毫秒，每次调用平均耗时0.02毫秒。我认为这里没有性能问题，而且绝对没有每次调用500毫秒的证据。 - user330315
1
如果有特定的模式导致了较长的延迟，您应该识别它们并在问题中包含它们。 - Holger
@Holger 时间不是问题。我的关注点只在于负载和CPU使用率。我想要并行处理参数，但如果这样做，我的平均负载会超过4。我使用jstack -l获取了线程转储，并使用thread -H -b -p <process id>查找最大消耗线程，并将其ID转换为十六进制代码。高CPU（50％）的线程处于Matcher.find的可运行状态。 - kannanrbk
1
@bharathi：这仍然是同一种问题。很可能有很多模式是便宜的，但其中一些是昂贵的。您必须确定昂贵的模式，集中优化这些特定的模式。顺便说一下，Matcher.find调用其他方法，由于分析器的默认过滤规则而未显示。更改这些规则以允许查看JDK方法内部可以揭示大部分时间（意味着CPU负载）花费在匹配的哪个位置。 - Holger
6个回答
3
我已经在做这个了。预编译所有匹配模式并将其存储为模式列表。 - kannanrbk
3
我建议您查看这篇论文："Towards Faster String Matching for Intrusion Detection or Exceeding the Speed of Snort"。
有更好的方法来进行您所描述的匹配。基本上，您将要匹配的500个模式编译成单个后缀树，可以非常高效地一次性将输入与所有规则进行匹配。
这篇论文解释了这种方法被丹·古斯菲尔德（Dan Gusfield）称为“Boyer-Moore精确集合匹配方法”。
Boyer-Moore是一个著名的字符串匹配算法。该论文描述了一种针对集合匹配的Boyer-Moore变体。
3
我觉得这是你问题的根源，而不仅仅是正则表达式性能本身：

对于每个请求，我都会检查所有参数并与这500个正则表达式进行匹配。
无论你的正则表达式多么快，这仍然是很多工作。我不知道你有多少个参数，但即使只有几个，每个请求仍需检查数千个正则表达式。这会让你的CPU忙不过来。
除了明显的事情，如通过预编译和/或简化它们来提高正则表达式性能外，你还可以执行以下操作来减少正则表达式检查的数量：
  1. 基于参数类型对用户输入进行正向验证。例如，如果某个参数必须是一个简单的数字，请不要浪费时间检查它是否包含恶意XML脚本。只需检查它是否与[0-9]+（或类似简单的内容）匹配即可。如果匹配成功，则跳过检查所有500个正则表达式。
  2. 尝试找到简单的正则表达式，可以消除整个攻击类别 - 查找正则表达式中的共同点。例如，如果您有100个正则表达式检查特定HTML标记的存在，请首先检查内容是否包含至少一个HTML标记。如果没有，您将立即节省检查100个正则表达式的时间。
  3. 缓存结果。在Web应用程序中生成的许多参数会重复。不要反复检查相同的内容，而只需记住最终验证结果。请注意限制缓存的最大大小，以避免DOS攻击。
另外请注意，负向验证通常很容易被绕过。只需更改几个字符的恶意代码，你的正则表达式就无法匹配。为了保护自己免受新攻击的影响，您必须扩大自己的正则表达式“数据库”。正向验证（白名单）没有这个缺点，而且更加有效。
嗨，我完成了前两个步骤。现在，总执行时间比以前更好。节省了大约60毫秒。 - kannanrbk
2

避免使用以下表达式：

  • 多行表达式
  • 不区分大小写的表达式
  • 等等

考虑将正则表达式进行分组，根据用户输入应用给定组的正则表达式。

这是完全错误的。为什么不使用多行/不区分大小写？Java 中的正则表达式匹配基于 NFA+回溯，因此诸如大小写敏感性之类的事情并不会对性能产生太大影响。更重要的是要避免回溯，例如.*后跟选择项（a|b|c）。 - Piotr Kołaczkowski
正如你所说，大小写敏感和多行搜索并不会对性能产生太大影响。这也意味着它们确实会影响性能。根据性能要求，它可能是相关的或不相关的。如果需要性能，则不能使用回溯。绝对不行。 - pabloa98
1
这500个正则表达式中必定存在一些有问题的子集。也就是说，存在某个正则表达式。
    String s = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB";

    Pattern.compile("(A+)+").matcher(s).matches();

需要数年时间才能完成。

因此，在您的情况下，我建议记录所有有问题的正则表达式及其输入。一旦找到这些问题，您可以手动重写这些少量有问题的正则表达式，并将其与原始正则表达式进行测试。正则表达式总是可以使用更简单和更易读的Java函数进行重写。

另一个选择是，虽然它无法解决上述问题，但您也可以利用更快（在某些情况下为x20）且更有限的正则表达式库。它可以在Maven Central中获得。

1
如果你有大量的正则表达式，你可以使用trie算法（http://en.wikipedia.org/wiki/Trie）将它们分组（至少其中一些）。
想法是，如果你有例如像/abc[0-9-]/，/abde/，/another example/，/.something else/和/.I run out of ideas/这样的正则表达式，你可以将它们合并为单个正则表达式。
 /a(?:b(?:c[0-9-]|de)|nother example)|.(?:I run out of ideas|something else)/

以这种方式，匹配器只需要运行一次而不是四次，并且由于正则表达式中公共起始部分的编写方式，可以避免很多回溯。
嗨，Davide，我无法对其进行分组。因为我需要获取匹配的规则（mod安全规则，每个规则都有自己的属性）详细信息。 - kannanrbk
原则上，如果匹配的规则只是其中的一些，您可以准备正则表达式的包，使用上述过程为每个包制作一个大的正则表达式。当其中一个大的正则表达式找到匹配项时，您可以检查组成该包的原始规则。为使此方法有效，您应将更可能一起出现的规则聚类在一起。我希望这是可行的。 - davide
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接