一个正则表达式导致CPU 利用率居高不下

前几天线上一个项目监控信息突然报告异常,上到机器上后查看相关资源的使用情况,发现 CPU 利用率将近 100%。通过 Java 自带的线程 Dump 工具,我们导出了出问题的堆栈信息。

藏在正则表达式里的陷阱,一个正则表达式导致CPU 利用率居高不下

我们可以看到所有的堆栈都指向了一个名为 validateUrl 的方法,这样的报错信息在堆栈中一共超过 100 处。通过排查代码,我们知道这个方法的主要功能是校验 URL 是否合法。

很奇怪,一个正则表达式怎么会导致 CPU 利用率居高不下。为了弄清楚复现问题,我们将其中的关键代码摘抄出来,做了个简单的单元测试。

public static void main(String[] args) {
 String badRegex = "^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\\/])+$";
 String bugUrl = "http://www.fapiao.com/dddp-web/pdf/download?request=6e7JGxxxxx4ILd-kExxxxxxxqJ4-CHLmqVnenXC692m74H38sdfdsazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf";
 if (bugUrl.matches(badRegex)) {
 System.out.println("match!!");
 } else {
 System.out.println("no match!!");
 }
}

当我们运行上面这个例子的时候,通过资源监视器可以看到有一个名为 java 的进程 CPU 利用率直接飙升到了 91.4% 。

藏在正则表达式里的陷阱,一个正则表达式导致CPU 利用率居高不下

看到这里,我们基本可以推断,这个正则表达式就是导致 CPU 利用率居高不下的凶手!

于是,我们将排错的重点放在了那个正则表达式上:

^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\/])+$

这个正则表达式看起来没什么问题,可以分为三个部分:

第一部分匹配 http 和 https 协议,第二部分匹配 www. 字符,第三部分匹配许多字符。我看着这个表达式发呆了许久,也没发现没有什么大的问题。

其实这里导致 CPU 使用率高的关键原因就是: Java 正则表达式使用的引擎实现是 NFA 自动机,这种正则表达式引擎在进行字符匹配时会发生回溯(backtracking)。 而一旦发生回溯,那其消耗的时间就会变得很长,有可能是几分钟,也有可能是几个小时,时间长短取决于回溯的次数和复杂度。

看到这里,可能大家还不是很清楚什么是回溯,还有点懵。没关系,我们一点点从正则表达式的原理开始讲起

正则表达式引擎

正则表达式是一个很方便的匹配符号,但要实现这么复杂,功能如此强大的匹配语法,就必须要有一套算法来实现,而实现这套算法的东西就叫做正则表达式引擎。简单地说,实现正则表达式引擎的有两种方式: DFA 自动机 (Deterministic Final Automata 确定型有穷自动机)和 NFA 自动机 (Non deterministic Finite Automaton 不确定型有穷自动机)。

对于这两种自动机,他们有各自的区别,这里并不打算深入将它们的原理。简单地说,DFA 自动机的时间复杂度是线性的,更加稳定,但是功能有限。而 NFA 的时间复杂度比较不稳定,有时候很好,有时候不怎么好,好不好取决于你写的正则表达式。但是胜在 NFA 的功能更加强大,所以包括 Java 、.NET、Perl、Python、Ruby、PHP 等语言都使用了 NFA 去实现其正则表达式。

那 NFA 自动机到底是怎么进行匹配的呢?我们以下面的字符和表达式来举例说明。

text="Today is a nice day."regex="day"

要记住一个很重要的点,即:NFA 是以正则表达式为基准去匹配的。也就是说,NFA 自动机会读取正则表达式的一个一个字符,然后拿去和目标字符串匹配,匹配成功就换正则表达式的下一个字符,否则继续和目标字符串的下一个字符比较。或许你们听不太懂,没事,接下来我们以上面的例子一步步解析。

  • 首先,拿到正则表达式的第一个匹配符:d。于是那去和字符串的字符进行比较,字符串的第一个字符是 T,不匹配,换下一个。第二个是 o,也不匹配,再换下一个。
  • 第三个是 d,匹配了,那么就读取正则表达式的第二个字符:a。 读取到正则表达式的第二个匹配符:a。那着继续和字符串的第四个字符 a 比较,又匹配了。那么接着读取正则表达式的第三个字符:y。
  • 读取到正则表达式的第三个匹配符:y。那着继续和字符串的第五个字符 y 比较,又匹配了。尝试读取正则表达式的下一个字符,发现没有了,那么匹配结束。

上面这个匹配过程就是 NFA 自动机的匹配过程,但实际上的匹配过程会比这个复杂非常多,但其原理是不变的。

NFA自动机的回溯

了解了 NFA 是如何进行字符串匹配的,接下来我们就可以讲讲这篇文章的重点了:回溯。为了更好地解释回溯,我们同样以下面的例子来讲解。

text="abbc"regex="ab{1,3}c"

上面的这个例子的目的比较简单,匹配以 a 开头,以 c 结尾,中间有 1-3 个 b 字符的字符串。NFA 对其解析的过程是这样子的:

首先,读取正则表达式第一个匹配符 a 和 字符串第一个字符 a 比较,匹配了。于是读取正则表达式第二个字符。 读取正则表达式第二个匹配符 b{1,3} 和字符串的第二个字符 b 比较,匹配了。但因为 b{1,3} 表示 1-3 个 b 字符串,以及 NFA 自动机的贪婪特性(也就是说要尽可能多地匹配),所以此时并不会再去读取下一个正则表达式的匹配符,而是依旧使用 b{1,3} 和字符串的第三个字符 b 比较,发现还是匹配。于是继续使用 b{1,3} 和字符串的第四个字符 c 比较,发现不匹配了。此时就会发生回溯。 发生回溯是怎么操作呢?发生回溯后,我们已经读取的字符串第四个字符 c 将被吐出去,指针回到第三个字符串的位置。之后,程序读取正则表达式的下一个操作符 c,读取当前指针的下一个字符 c 进行对比,发现匹配。于是读取下一个操作符,但这里已经结束了。 下面我们回过头来看看前面的那个校验 URL 的正则表达式:

^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\/])+$

出现问题的 URL 是:

http://www.fapiao.com/dzfp-web/pdf/download?request=6e7JGm38jfjghVrv4ILd-kEn64HcUX4qL4a4qJ4-CHLmqVnenXC692m74H5oxkjgdsYazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf

我们把这个正则表达式分为三个部分:

  • 第一部分:校验协议。^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)。
  • 第二部分:校验域名。(([A-Za-z0-9-~]+).)+。
  • 第三部分:校验参数。([A-Za-z0-9-~/])+$。

我们可以发现正则表达式校验协议 http:// 这部分是没有问题的,但是在校验 www.fapiao.com 的时候,其使用了 xxxx. 这种方式去校验。那么其实匹配过程是这样的:

  • 匹配到 www.
  • 匹配到 fapiao.
  • 匹配到 com/dzfp-web/pdf/download?request=6e7JGm38jf.....,你会发现因为贪婪匹配的原因,所以程序会一直读后面的字符串进行匹配,最后发现没有点号,于是就一个个字符回溯回去了。

这是这个正则表达式存在的第一个问题。

另外一个问题是在正则表达式的第三部分,我们发现出现问题的 URL 是有下划线(_)和百分号(%)的,但是对应第三部分的正则表达式里面却没有。这样就会导致前面匹配了一长串的字符之后,发现不匹配,最后回溯回去。

这是这个正则表达式存在的第二个问题。

解决方案

明白了回溯是导致问题的原因之后,其实就是减少这种回溯,你会发现如果我在第三部分加上下划线和百分号之后,程序就正常了。

public static void main(String[] args) {
 String badRegex = "^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~_%\\/])+$";
 String bugUrl = "http://www.fapiao.com/dddp-web/pdf/download?request=6e7JGxxxxx4ILd-kExxxxxxxqJ4-CHLmqVnenXC692m74H38sdfdsazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf";
 if (bugUrl.matches(badRegex)) {
 System.out.println("match!!");
 } else {
 System.out.println("no match!!");
 }
}

运行上面的程序,立刻就会打印出match!!。

但这是不够的,如果以后还有其他 URL 包含了乱七八糟的字符呢,我们难不成还再修改一遍。肯定不现实嘛!

其实在正则表达式中有这么三种模式: 贪婪模式、懒惰模式、独占模式。

在关于数量的匹配中,有 + ? * {min,max} 四种两次,如果只是单独使用,那么它们就是贪婪模式。

如果在他们之后加多一个 ? 符号,那么原先的贪婪模式就会变成懒惰模式,即尽可能少地匹配。但是懒惰模式还是会发生回溯现象的。例如下面这个例子:

text="abbc"regex="ab{1,3}?c"

正则表达式的第一个操作符 a 与 字符串第一个字符 a 匹配,匹配成功。于是正则表达式的第二个操作符 b{1,3}? 和 字符串第二个字符 b 匹配,匹配成功。因为最小匹配原则,所以拿正则表达式第三个操作符 c 与字符串第三个字符 b 匹配,发现不匹配。于是回溯回去,拿正则表达式第二个操作符 b{1,3}? 和字符串第三个字符 b 匹配,匹配成功。于是再拿正则表达式第三个操作符 c 与字符串第四个字符 c 匹配,匹配成功。于是结束。

如果在他们之后加多一个 + 符号,那么原先的贪婪模式就会变成独占模式,即尽可能多地匹配,但是不回溯。

于是乎,如果要彻底解决问题,就要在保证功能的同时确保不发生回溯。我将上面校验 URL 的正则表达式的第二部分后面加多了个 + 号,即变成这样:

^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)
(([A-Za-z0-9-~]+).)++ --->>> (这里加了个+号)
([A-Za-z0-9-~_%\/])+$

这样之后,运行原有的程序就没有问题了。

最后推荐一个网站,这个网站可以检查你写的正则表达式和对应的字符串匹配时会不会有问题。

Online regex tester and debugger: PHP, PCRE, Python, Golang and JavaScript

例如我本文中存在问题的那个 URL 使用该网站检查后会提示:catastrophic backgracking(灾难性回溯)。

藏在正则表达式里的陷阱,一个正则表达式导致CPU 利用率居高不下

当你点击左下角的「regex debugger」时,它会告诉你一共经过多少步检查完毕,并且会将所有步骤都列出来,并标明发生回溯的位置。

藏在正则表达式里的陷阱,一个正则表达式导致CPU 利用率居高不下

本文中的这个正则表达式在进行了 11 万步尝试之后,自动停止了。这说明这个正则表达式确实存在问题,需要改进。

但是当我用我们修改过的正则表达式进行测试,即下面这个正则表达式。

^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([A-Za-z0-9-~]+).)++([A-Za-z0-9-~\/])+$

工具提示只用了 58 步就完成了检查。

总结

以上所述是小编给大家介绍的一个正则表达式导致CPU 利用率居高不下,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对我们网站的支持!
如果你觉得本文对你有帮助,欢迎转载,烦请注明出处,谢谢!

(0)

相关推荐

  • Python 正则表达式匹配字符串中的http链接方法

    利用Python正则表达式匹配字符串中的http链接.主要难点是用正则表示出http 链接的模式. import re pattern = re.compile(r'http[s]?://(?:[a-zA-Z]|[0-9]|[$-_@.&+]|[!*\(\),]|(?:%[0-9a-fA-F][0-9a-fA-F]))+') # 匹配模式 string = 'Its after 12 noon, do you know where your rooftops are? http://tinyur

  • python 使用正则表达式按照多个空格分割字符的实例

    程序代码如下 import os import re os.system("nmap -sP 192.168.3.0/24") //扫描IP mac = os.popen("cat /proc/net/arp ").readlines() //按行读取 length = len(mac) for i in range(1,length): b= re.split(r" +",mac[i]) //按照多个空格分割 if(b[2]=='0x2'):

  • 在Django中URL正则表达式匹配的方法

    Django框架中的URL分发采用正则表达式匹配来进行,以下是正则表达式的基本规则: 官方演示代码: from django.conf.urls import url from . import views urlpatterns = [ url(r'^articles/2003/$', views.special_case_2003), url(r'^articles/([0-9]{4})/$', views.year_archive), url(r'^articles/([0-9]{4})/

  • Java使用正则表达式验证手机号和电话号码的方法

    一个朋友需要,所以写了这两个,话不多说,看代码 中国电信号段 133.149.153.173.177.180.181.189.199 中国联通号段 130.131.132.145.155.156.166.175.176.185.186 中国移动号段 134(0-8).135.136.137.138.139.147.150.151.152.157.158.159.178.182.183.184.187.188.198 其他号段 14号段以前为上网卡专属号段,如中国联通的是145,中国移动的是147

  • 史上最全正则表达式合集(马上收藏)

    前言 正则表达式,新手见它的感觉就是"这都什么玩意,乱七八糟的,完全不知所云",但学会它就会体验那种一行代码抵数十上百行,效率飞起的感觉,简直不要太爽.今天小肆先把我自己收藏的一些正则表达式写法分享给大家,当然想深入学习如何写正则表达式,可以去w3c看看教程. 干货 一.校验数字 数字:^[0-9]*$ n位的数字:^\d{n}$ 至少n位的数字:^\d{n,}$ m-n位的数字:^\d{m,n}$ 零和非零开头的数字:^(0|[1-9][0-9]*)$ 非零开头的最多带两位小数的数字

  • python正则表达式去除两个特殊字符间的内容方法

    以去掉去掉<!--和-->为例进行说明: def clearContentWithSpecialCharacter(content): # 先将<!--替换成,普通字符l content = content.replace("<!--","l") # 再将-->替换成,普通字符l content = content.replace("-->","l") # 分组标定,替换, pattern

  • 使用正则表达式实现网页爬虫的思路详解

    网页爬虫:就是一个程序用于在互联网中获取指定规则的数据. 思路: 1.为模拟网页爬虫,我们可以现在我们的tomcat服务器端部署一个1.html网页.(部署的步骤:在tomcat目录的webapps目录的ROOTS目录下新建一个1.html.使用notepad++进行编辑,编辑内容为: ) 2.使用URL与网页建立联系 3.获取输入流,用于读取网页中的内容 4.建立正则规则,因为这里我们是爬去网页中的邮箱信息,所以建立匹配 邮箱的正则表达式:String regex="\w+@\w+(\.\w+

  • 一个正则表达式导致CPU 利用率居高不下

    前几天线上一个项目监控信息突然报告异常,上到机器上后查看相关资源的使用情况,发现 CPU 利用率将近 100%.通过 Java 自带的线程 Dump 工具,我们导出了出问题的堆栈信息. 藏在正则表达式里的陷阱,一个正则表达式导致CPU 利用率居高不下 我们可以看到所有的堆栈都指向了一个名为 validateUrl 的方法,这样的报错信息在堆栈中一共超过 100 处.通过排查代码,我们知道这个方法的主要功能是校验 URL 是否合法. 很奇怪,一个正则表达式怎么会导致 CPU 利用率居高不下.为了弄

  • MongoDb CPU利用率过高问题如何解决

    在公司的项目中,突然出现过一个情况,mongodb 的CPU利用率到达100%,导致服务器这边卡死了,请求了半天无响应,提示请求超时. 因为,当时APP用户可能会在某一个时间段集中的使用,所以,请求量一下子就飙上去了,刚好APP打开请求的时候,有一个mongodb的请求. 当时因为Mongodb的服务器不在我们这边,所以一下子没反应过来,不过最后还是给排除出,并解决了.这里就来记录下排查和解决的全过程. 问题分析: 1.根据代码,定位到了是Mongodb的报错. 2.进入Mongodb 服务器的

  • python和bash统计CPU利用率的方法

    本文实例讲述了python和bash统计CPU利用率的方法.分享给大家供大家参考.具体如下: 开始的时候写了一个 bash 的实现: 因为最近也在学习 python ,所以就尝试着用 python 再实现一回: 支援 python2 环境: 请各位给予下建议,有什么改良的地方可以提一下,不甚感激: Python代码如下: #!/usr/bin/python # -*- coding:utf8 -*- __author__ = 'chenwx' def cpu_rate(): import tim

  • Java多线程导致CPU占用100%解决及线程池正确关闭方式

    简介 情景:1000万表数据导入内存数据库,按分页大小10000查询,多线程,15条线程跑. 使用了ExecutorService executor = Executors.newFixedThreadPool(15) 本地跑了一段时间后,发现电脑CPU逐渐升高,最后CPU占用100%卡死,内存使用也高达80%. 排查问题 Debug 发现虽然创建了定长15的线程池,但是因为数据量大,在For中循环分页查询的List会持续加入LinkedBlockingQueue() 队列中每一个等待的任务,又

  • 服务器大量php-cgi.exe进程导致CPU占用100%的解决方法

    windows 2003+IIS6中优化fastcgi配置文件fcgiext.ini,减少php-cgi.exe进程数量和所占内存大小 本来听说fastcgi比isapi好就在服务器中装上了,配置环境为windows 2003+IIS6+fastcgi(FCGI)+PHP5.2.17,经过与很长一段时间观察,发现工作在FastCGI模式下的PHP会占用越来越多的内存,访问量稍微多点php-cgi进程就多了N个,同样情况下能比原来用isapi模式的时候多出几百M,我的服务器内存只有2G伤不起啊.

  • php preg_filter执行一个正则表达式搜索和替换

    preg_filter (PHP 5 >= 5.3.0) preg_filter - 执行一个正则表达式搜索和替换 mixed preg_filter ( mixed $pattern , mixed $replacement , mixed $subject [, int $limit = -1 [, int &$count ]] ) preg_filter()等价于preg_replace() 除了它仅仅返回(可能经过转化)与目标匹配的结果. 这个函数怎样工作的更详细信息请阅读 preg

  • IOS 实现一个死锁导致 UI 假死的例子

    IOS 实现一个死锁导致 UI 假死的例子 现象 当 APP 启动一段时间后(约半小时左右),经常会发现 App 界面出现"冻死"的现象.同时后台输出: [CocoaGoPush]WorkThreadProc end 这时 App 呈现"假死"状态,点击屏幕任何地方没有反应,iPhone 除了开屏关屏无任何响应(包括按 Home 键),当然也无法解锁(但可以重启).如果用 Xcode 终止应用程序,则 iPhone 又恢复正常. 注:App 使用了 CocoaGoP

  • 一个js导致的jquery失效问题的解决方法

    搞网站开发,最头疼的是js问题,倒不是php程序开发,前端的页面,js真是太让人折腾了,特别是js,你根本不知道哪里就会出问题,各种兼容也要兼顾,不像写程序,你只关心功能如何实现,逻辑怎么写.js文件一个出问题,就影响其他js的运行,今天就遇到一个很纠结的东西,一个js导致的莫名其妙的问题. 这个js是一个增强页面效果的功能,但是用了它,jquery在有的页面可以用,有的页面就失效了,用firefox的firebug调试,发现在有的页面会报错,获取分页的位置的地方会出错.后来发现确实只要没有分页

  • python统计cpu利用率的方法

    本文实例讲述了python统计cpu利用率的方法.分享给大家供大家参考.具体实现方法如下: #-*-coding=utf-8-*- import win32pdh import time # Counter paths PROCESSOR_PERCENT = r'\Processor(_Total)\% Processor Time' MEMORY_PERCENT = r'\Memory\% Committed Bytes In Use' MEMORY_COMMITTED = r'\Memory

  • 如何使用shell获取进程名的内存以及CPU利用率

    目录 原理: 在ubuntu18.04和centos7.9测试: 使用方法: 总结 原理: 1)使用ps得到进程名的所有进程pid ps -C process_name -o pid= 2) 使用 /proc/$pid/status获得内存的占用,并循环求和: 3)使用top获取相关pid的cpu列表,并过滤第10列,求和. 在ubuntu18.04和centos7.9测试: # !/bin/bash # author:robin # usage: bash proc.sh openresty

随机推荐