正则表达式高CPU消耗

Question

正则表达式高CPU消耗

3

我们在生产环境中遇到了100%的CPU利用率问题，线程转储显示我们的"黑名单"实现卡在以下步骤。

[11/14/13 10:12:42:745 CST] 0000000d ThreadMonitor W   WSVR0605W: Thread "Thread-002" (0000003b) has been active for 604063 milliseconds and may be hung.  There is/are 1 thread(s) in total in the server that may be hung.
    at java.lang.Character.isLetterOrDigit(Character.java:3516)
    at java.util.regex.Pattern$Bound.check(Pattern.java:4820)
    at java.util.regex.Pattern$Bound.match(Pattern.java:4832)
    at java.util.regex.Pattern$Curly.match0(Pattern.java:3782)
    at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
    at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3366)
    at java.util.regex.Pattern$Curly.match0(Pattern.java:3782)
    at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
    at java.util.regex.Matcher.match(Matcher.java:1127)
    at java.util.regex.Matcher.matches(Matcher.java:502)

问题在于，这种情况并非总是发生，这意味着它是数据相关的，并且我们在黑名单实现中有以下正则表达式列表。

如果有人能够告诉我以下哪个正则表达式可能会导致100%的CPU占用（我猜测是由于回溯），我将不胜感激。

# zero/null bytes 
.*\x00.*

# javascript
.*\bjavascript\b.* &&! ^[\w.,;/*+= -]*\b(:?application/x-javascript|text/javascript)\b[\w.,;/*+= -]*$
# vbscript
.*\bvbscript\b.*

# <script or </script>
.*<\s*/?\s*script\b.*|.*\bscript\s*>.*
# <img or </img>
.*<\s*/?\s*img\b.*|.*\bimg\s*>.*
# <div or </div>
.*<\s*/?\s*div\b.*|.*\bdiv\s*>.*
# <html or </html>
.*<\s*/?\s*html\b.*|.*\bhtml\s*>.*
# <body or </body>
.*<\s*/?\s*body\b.*|.*\bbody\s*>.*
# <link or </link>
.*<\s*/?\s*link\b.*|.*\blink\s*>.* &&! ^<\?xml .*$
# <meta or </meta>
.*<\s*/?\s*meta\b.*|.*\bmeta\s*>.*
# <base or </base>
.*<\s*/?\s*base\b.*|.*\bbase\s*>.*
# <span or </span>
.*<\s*/?\s*span\b.*|.*\bspan\s*>.*
# <input or </input>
.*<\s*/?\s*input\b.*|.*\binput\s*>.*
# <style or </style>
.*<\s*/?\s*style\b.*|.*\bstyle\s*>.*
# <table or </table>
.*<\s*/?\s*table\b.*|.*\btable\s*>.*
# <embed or </embed>
.*<\s*/?\s*embed\b.*|.*\bembed\s*>.*
# <frame or </frame>
.*<\s*/?\s*frame\b.*|.*\bframe\s*>.*
# <iframe or </iframe>
.*<\s*/?\s*iframe\b.*|.*\biframe\s*>.*
# <object or </object>
.*<\s*/?\s*object\b.*|.*\bobject\s*>.*

# < onload= >
.*<.+\bonload\s*=.+>.*
# < onerror= >
.*<.+\bonerror\s*=.+>.*
# < onmouseover= >
.*<.+\bonmouseover\s*=.+>.*
# < src= >
.*<.+\bsrc\s*=.+>.*
# < href= >
.*<.+\bhref\s*=.+>.*
# < style= >
.*<.+\bstyle\s*=.+>.*
# < content= >
.*<.+\bcontent\s*=.+>.*

# document.
.*\bdocument\s*\..+
# element.
.*\belement\s*\..+

# url(
.*\burl\s*\(.+
# eval(
.*\beval\s*\(.+
# alert(
.*\balert\s*\(.+

# /* */
.*/\*.*\*/.*


# HTTP response splitting
.*\bHTTP/\d+\.\d+.+


# Path traversal
#.*\.\.[/\\].*
.*\.\.[/\\]\.\.[/\\].*


# SQL injection (probably not very useful)

# from HttpServletBase.java
.*select\s+\S*\s*from\s+\S+(?:\s+where\s+.+)?.*
.*insert\s+\S*\s*into\s+\S+(?:\s+values\s+.+)?.*
.*update\s+\S*\s*set\s+\S+(?:\s+where\s+.+)?.*
.*delete\s+\S*\s*from\s+\S+(?:\s+where\s+.+)?.*

- user3017924

你如何使用这些正则表达式？通过重复使用Pattern对象，您可以节省大量CPU。 - Cyrille Ka

是的，我们会预编译它们。问题似乎基于一些数据，当100%的CPU被使用时，它并不总是发生，因此寻求一些帮助来确定哪个正则表达式可能会引起问题，例如回溯等。 - user3017924

1

我的有关性能的论点是，你是唯一知道什么是慢的人 :) 找到几个展示问题的数据样本，将它们放入一种单元测试中，然后激活/禁用一些正则表达式，以查看哪些是有问题的。 - Cyrille Ka

我曾经遇到过相同的问题，当时我正在处理非常简单的表达式，以至于我可以对是什么导致了它变慢有假设。不幸的是，我现在记不起来了。我建议您尝试使用更简单但仍然棘手的表达式重现这个问题。 - Giulio Franco

两个词：灾难性回溯。此外，您未提及使用哪个Java正则表达式函数和正则表达式修饰符。 - ridgerunner

2个回答

0

我可能错了，但正则表达式不能保护你免受XSS攻击，因为它们可能非常棘手：XSS Filter Evasion Cheat Sheet。你可能想看看OWASP的HTML清洁器。

对于我的项目中类似的问题，我提出了一个解决方案，将JSoup用于解析HTML和正则表达式来匹配属性和文本中的字符串（当时我不知道这个OWASP工具）。

- Andrey Chaschev

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cyrille Ka · Accepted Answer

正如我在评论中所说，对数据进行适当的测试是真正了解哪个正则表达式有问题的唯一方法。但我认为有些东西可以指出，你可以研究一下。基本上，要小心点运算符。

看这里：

.*<.+\bonload\s*=.+>.*

我猜你想要找到包含"onload"的任何HTML标签。问题是，如果你的数据中有很多标签，而且没有一个包含"onload"，它会像这样进行：

找到第一个 <
在字符串的其余部分中查找"\bonload"
由于找不到任何内容，回溯并尝试使用字符串中的以下< 。

因此，对于字符串中的每个标记，这将重复进行，因此如果字符串很长，则第2步可能很耗费时间。您可以通过将.+替换为[^>]+（即除>之外的任何内容）来防止其超过标记末尾以进行优化。

因此，以下正则表达式应该更有效：

.*<[^>]+\bonload\s*=.+>.*

此外，遵循“最快的代码是不运行的代码”的一般原则，您可以在使用正则表达式之前使用简单的字符串搜索查找字符串是否包含字符串“onload”。