主頁(yè) > 知識(shí)庫(kù) > Java正則表達(dá)式里隱藏的陷阱

Java正則表達(dá)式里隱藏的陷阱

熱門標(biāo)簽:怎么在高德地圖標(biāo)注行走軌跡 清遠(yuǎn)陽(yáng)山400電話號(hào)碼如何申請(qǐng) 個(gè)性化地圖標(biāo)注在線 深圳400電話辦理那家好 百度地圖標(biāo)注名編輯 襄陽(yáng)房產(chǎn)電銷機(jī)器人招商 百度地圖標(biāo)注飯店位置怎么 施工地圖標(biāo)注怎么做 安徽移動(dòng)外呼系統(tǒng)

前幾天線上一個(gè)項(xiàng)目監(jiān)控信息突然報(bào)告異常,上到機(jī)器上后查看相關(guān)資源的使用情況,發(fā)現(xiàn) CPU 利用率將近 100%。通過(guò) Java 自帶的線程 Dump 工具,我們導(dǎo)出了出問(wèn)題的堆棧信息。

我們可以看到所有的堆棧都指向了一個(gè)名為 validateUrl 的方法,這樣的報(bào)錯(cuò)信息在堆棧中一共超過(guò) 100 處。通過(guò)排查代碼,我們知道這個(gè)方法的主要功能是校驗(yàn) URL 是否合法。

很奇怪,一個(gè)正則表達(dá)式怎么會(huì)導(dǎo)致 CPU 利用率居高不下。為了弄清楚復(fù)現(xiàn)問(wèn)題,我們將其中的關(guān)鍵代碼摘抄出來(lái),做了個(gè)簡(jiǎn)單的單元測(cè)試。

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!!");
    }
}

當(dāng)我們運(yùn)行上面這個(gè)例子的時(shí)候,通過(guò)資源監(jiān)視器可以看到有一個(gè)名為 java 的進(jìn)程 CPU 利用率直接飆升到了 91.4% 。

看到這里,我們基本可以推斷,這個(gè)正則表達(dá)式就是導(dǎo)致 CPU 利用率居高不下的兇手!

于是,我們將排錯(cuò)的重點(diǎn)放在了那個(gè)正則表達(dá)式上:

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

這個(gè)正則表達(dá)式看起來(lái)沒(méi)什么問(wèn)題,可以分為三個(gè)部分:

第一部分匹配 http 和 https 協(xié)議,第二部分匹配 www. 字符,第三部分匹配許多字符。我看著這個(gè)表達(dá)式發(fā)呆了許久,也沒(méi)發(fā)現(xiàn)沒(méi)有什么大的問(wèn)題。

其實(shí)這里導(dǎo)致 CPU 使用率高的關(guān)鍵原因就是:Java 正則表達(dá)式使用的引擎實(shí)現(xiàn)是 NFA 自動(dòng)機(jī),這種正則表達(dá)式引擎在進(jìn)行字符匹配時(shí)會(huì)發(fā)生回溯(backtracking)。而一旦發(fā)生回溯,那其消耗的時(shí)間就會(huì)變得很長(zhǎng),有可能是幾分鐘,也有可能是幾個(gè)小時(shí),時(shí)間長(zhǎng)短取決于回溯的次數(shù)和復(fù)雜度。

看到這里,可能大家還不是很清楚什么是回溯,還有點(diǎn)懵。沒(méi)關(guān)系,我們一點(diǎn)點(diǎn)從正則表達(dá)式的原理開(kāi)始講起。

正則表達(dá)式引擎

正則表達(dá)式是一個(gè)很方便的匹配符號(hào),但要實(shí)現(xiàn)這么復(fù)雜,功能如此強(qiáng)大的匹配語(yǔ)法,就必須要有一套算法來(lái)實(shí)現(xiàn),而實(shí)現(xiàn)這套算法的東西就叫做正則表達(dá)式引擎。簡(jiǎn)單地說(shuō),實(shí)現(xiàn)正則表達(dá)式引擎的有兩種方式:DFA 自動(dòng)機(jī)(Deterministic Final Automata 確定型有窮自動(dòng)機(jī))和 NFA 自動(dòng)機(jī)(Non deterministic Finite Automaton 不確定型有窮自動(dòng)機(jī))。

對(duì)于這兩種自動(dòng)機(jī),他們有各自的區(qū)別,這里并不打算深入將它們的原理。簡(jiǎn)單地說(shuō),DFA 自動(dòng)機(jī)的時(shí)間復(fù)雜度是線性的,更加穩(wěn)定,但是功能有限。而 NFA 的時(shí)間復(fù)雜度比較不穩(wěn)定,有時(shí)候很好,有時(shí)候不怎么好,好不好取決于你寫的正則表達(dá)式。但是勝在 NFA 的功能更加強(qiáng)大,所以包括 Java 、.NET、Perl、Python、Ruby、PHP 等語(yǔ)言都使用了 NFA 去實(shí)現(xiàn)其正則表達(dá)式。

那 NFA 自動(dòng)機(jī)到底是怎么進(jìn)行匹配的呢?我們以下面的字符和表達(dá)式來(lái)舉例說(shuō)明。

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

要記住一個(gè)很重要的點(diǎn),即:NFA 是以正則表達(dá)式為基準(zhǔn)去匹配的。也就是說(shuō),NFA 自動(dòng)機(jī)會(huì)讀取正則表達(dá)式的一個(gè)一個(gè)字符,然后拿去和目標(biāo)字符串匹配,匹配成功就換正則表達(dá)式的下一個(gè)字符,否則繼續(xù)和目標(biāo)字符串的下一個(gè)字符比較。或許你們聽(tīng)不太懂,沒(méi)事,接下來(lái)我們以上面的例子一步步解析。

  • 首先,拿到正則表達(dá)式的第一個(gè)匹配符:d。于是那去和字符串的字符進(jìn)行比較,字符串的第一個(gè)字符是 T,不匹配,換下一個(gè)。第二個(gè)是 o,也不匹配,再換下一個(gè)。第三個(gè)是 d,匹配了,那么就讀取正則表達(dá)式的第二個(gè)字符:a。
  • 讀取到正則表達(dá)式的第二個(gè)匹配符:a。那著繼續(xù)和字符串的第四個(gè)字符 a 比較,又匹配了。那么接著讀取正則表達(dá)式的第三個(gè)字符:y。
  • 讀取到正則表達(dá)式的第三個(gè)匹配符:y。那著繼續(xù)和字符串的第五個(gè)字符 y 比較,又匹配了。嘗試讀取正則表達(dá)式的下一個(gè)字符,發(fā)現(xiàn)沒(méi)有了,那么匹配結(jié)束。

上面這個(gè)匹配過(guò)程就是 NFA 自動(dòng)機(jī)的匹配過(guò)程,但實(shí)際上的匹配過(guò)程會(huì)比這個(gè)復(fù)雜非常多,但其原理是不變的。

文章首發(fā)于【博客園-陳樹(shù)義】,點(diǎn)擊跳轉(zhuǎn)到原文《藏在正則表達(dá)式里的陷阱》

NFA自動(dòng)機(jī)的回溯

了解了 NFA 是如何進(jìn)行字符串匹配的,接下來(lái)我們就可以講講這篇文章的重點(diǎn)了:回溯。為了更好地解釋回溯,我們同樣以下面的例子來(lái)講解。

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

上面的這個(gè)例子的目的比較簡(jiǎn)單,匹配以 a 開(kāi)頭,以 c 結(jié)尾,中間有 1-3 個(gè) b 字符的字符串。NFA 對(duì)其解析的過(guò)程是這樣子的:

  • 首先,讀取正則表達(dá)式第一個(gè)匹配符 a 和 字符串第一個(gè)字符 a 比較,匹配了。于是讀取正則表達(dá)式第二個(gè)字符。
  • 讀取正則表達(dá)式第二個(gè)匹配符 b{1,3} 和字符串的第二個(gè)字符 b 比較,匹配了。但因?yàn)?b{1,3} 表示 1-3 個(gè) b 字符串,以及 NFA 自動(dòng)機(jī)的貪婪特性(也就是說(shuō)要盡可能多地匹配),所以此時(shí)并不會(huì)再去讀取下一個(gè)正則表達(dá)式的匹配符,而是依舊使用 b{1,3} 和字符串的第三個(gè)字符 b 比較,發(fā)現(xiàn)還是匹配。于是繼續(xù)使用 b{1,3} 和字符串的第四個(gè)字符 c 比較,發(fā)現(xiàn)不匹配了。此時(shí)就會(huì)發(fā)生回溯。
  • 發(fā)生回溯是怎么操作呢?發(fā)生回溯后,我們已經(jīng)讀取的字符串第四個(gè)字符 c 將被吐出去,指針回到第三個(gè)字符串的位置。之后,程序讀取正則表達(dá)式的下一個(gè)操作符 c,讀取當(dāng)前指針的下一個(gè)字符 c 進(jìn)行對(duì)比,發(fā)現(xiàn)匹配。于是讀取下一個(gè)操作符,但這里已經(jīng)結(jié)束了。

下面我們回過(guò)頭來(lái)看看前面的那個(gè)校驗(yàn) URL 的正則表達(dá)式:

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

出現(xiàn)問(wèn)題的 URL 是:

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

我們把這個(gè)正則表達(dá)式分為三個(gè)部分:

  • 第一部分:校驗(yàn)協(xié)議。^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)。
  • 第二部分:校驗(yàn)域名。(([A-Za-z0-9-~]+).)+。
  • 第三部分:校驗(yàn)參數(shù)。([A-Za-z0-9-~\\/])+$。

我們可以發(fā)現(xiàn)正則表達(dá)式校驗(yàn)協(xié)議 http:// 這部分是沒(méi)有問(wèn)題的,但是在校驗(yàn) www.fapiao.com 的時(shí)候,其使用了 xxxx. 這種方式去校驗(yàn)。那么其實(shí)匹配過(guò)程是這樣的:

  • 匹配到 www.
  • 匹配到 fapiao.
  • 匹配到 com/dzfp-web/pdf/download?request=6e7JGm38jf.....,你會(huì)發(fā)現(xiàn)因?yàn)樨澙菲ヅ涞脑颍猿绦驎?huì)一直讀后面的字符串進(jìn)行匹配,最后發(fā)現(xiàn)沒(méi)有點(diǎn)號(hào),于是就一個(gè)個(gè)字符回溯回去了。

這是這個(gè)正則表達(dá)式存在的第一個(gè)問(wèn)題。

另外一個(gè)問(wèn)題是在正則表達(dá)式的第三部分,我們發(fā)現(xiàn)出現(xiàn)問(wèn)題的 URL 是有下劃線(_)和百分號(hào)(%)的,但是對(duì)應(yīng)第三部分的正則表達(dá)式里面卻沒(méi)有。這樣就會(huì)導(dǎo)致前面匹配了一長(zhǎng)串的字符之后,發(fā)現(xiàn)不匹配,最后回溯回去。

這是這個(gè)正則表達(dá)式存在的第二個(gè)問(wèn)題。

解決方案

明白了回溯是導(dǎo)致問(wèn)題的原因之后,其實(shí)就是減少這種回溯,你會(huì)發(fā)現(xiàn)如果我在第三部分加上下劃線和百分號(hào)之后,程序就正常了。

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!!");
    }
}

運(yùn)行上面的程序,立刻就會(huì)打印出match!!。

但這是不夠的,如果以后還有其他 URL 包含了亂七八糟的字符呢,我們難不成還再修改一遍??隙ú滑F(xiàn)實(shí)嘛!

其實(shí)在正則表達(dá)式中有這么三種模式:貪婪模式、懶惰模式、獨(dú)占模式。

在關(guān)于數(shù)量的匹配中,有 + ? * {min,max} 四種兩次,如果只是單獨(dú)使用,那么它們就是貪婪模式。

如果在他們之后加多一個(gè) ? 符號(hào),那么原先的貪婪模式就會(huì)變成懶惰模式,即盡可能少地匹配。但是懶惰模式還是會(huì)發(fā)生回溯現(xiàn)象的。例如下面這個(gè)例子:

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

正則表達(dá)式的第一個(gè)操作符 a 與 字符串第一個(gè)字符 a 匹配,匹配成功。于是正則表達(dá)式的第二個(gè)操作符 b{1,3}? 和 字符串第二個(gè)字符 b 匹配,匹配成功。因?yàn)樽钚∑ヅ湓瓌t,所以拿正則表達(dá)式第三個(gè)操作符 c 與字符串第三個(gè)字符 b 匹配,發(fā)現(xiàn)不匹配。于是回溯回去,拿正則表達(dá)式第二個(gè)操作符 b{1,3}? 和字符串第三個(gè)字符 b 匹配,匹配成功。于是再拿正則表達(dá)式第三個(gè)操作符 c 與字符串第四個(gè)字符 c 匹配,匹配成功。于是結(jié)束。

如果在他們之后加多一個(gè) + 符號(hào),那么原先的貪婪模式就會(huì)變成獨(dú)占模式,即盡可能多地匹配,但是不回溯。

于是乎,如果要徹底解決問(wèn)題,就要在保證功能的同時(shí)確保不發(fā)生回溯。我將上面校驗(yàn) URL 的正則表達(dá)式的第二部分后面加多了個(gè) + 號(hào),即變成這樣:

^([hH][tT]{2}[pP]:\/\/|[hH][tT]{2}[pP][sS]:\/\/)
(([A-Za-z0-9-~]+).)++    --->>> (這里加了個(gè)+號(hào))
([A-Za-z0-9-~_%\\\/])+$

這樣之后,運(yùn)行原有的程序就沒(méi)有問(wèn)題了。

最后推薦一個(gè)網(wǎng)站,這個(gè)網(wǎng)站可以檢查你寫的正則表達(dá)式和對(duì)應(yīng)的字符串匹配時(shí)會(huì)不會(huì)有問(wèn)題。

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

例如我本文中存在問(wèn)題的那個(gè) URL 使用該網(wǎng)站檢查后會(huì)提示:catastrophic backgracking(災(zāi)難性回溯)。

當(dāng)你點(diǎn)擊左下角的「regex debugger」時(shí),它會(huì)告訴你一共經(jīng)過(guò)多少步檢查完畢,并且會(huì)將所有步驟都列出來(lái),并標(biāo)明發(fā)生回溯的位置。

本文中的這個(gè)正則表達(dá)式在進(jìn)行了 11 萬(wàn)步嘗試之后,自動(dòng)停止了。這說(shuō)明這個(gè)正則表達(dá)式確實(shí)存在問(wèn)題,需要改進(jìn)。

但是當(dāng)我用我們修改過(guò)的正則表達(dá)式進(jìn)行測(cè)試,即下面這個(gè)正則表達(dá)式。

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

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

一個(gè)字符的差別,性能就差距了好幾萬(wàn)倍。

樹(shù)義有話說(shuō)

一個(gè)小小的正則表達(dá)式竟然能夠把 CPU 拖垮,也是很神奇了。這也給平時(shí)寫程序的我們一個(gè)警醒,遇到正則表達(dá)式的時(shí)候要注意貪婪模式和回溯問(wèn)題,否則我們每寫的一個(gè)表達(dá)式都是一個(gè)雷。

通過(guò)查閱網(wǎng)上資料,我發(fā)現(xiàn)深圳阿里中心 LAZADA 的同學(xué)也在 17 年遇到了這個(gè)問(wèn)題。他們同樣也是在測(cè)試環(huán)境沒(méi)有發(fā)現(xiàn)問(wèn)題,但是一到線上的時(shí)候就發(fā)生了 CPU 100% 的問(wèn)題,他們遇到的問(wèn)題幾乎跟我們的一模一樣。有興趣的朋友可以點(diǎn)擊閱讀python中使用正則表達(dá)式將所有符合條件的字段全部提取出來(lái)

雖然把這篇文章寫完了,但是關(guān)于 NFA 自動(dòng)機(jī)的原理方面,特別是關(guān)于懶惰模式、獨(dú)占模式的解釋方面還是沒(méi)有解釋得足夠深入。因?yàn)?NFA 自動(dòng)機(jī)確實(shí)不是那么容易理解,所以在這方面還需要不斷學(xué)習(xí)加強(qiáng)。歡迎有懂行的朋友來(lái)學(xué)習(xí)交流,互相促進(jìn)。

以上就是Java正則表達(dá)式里隱藏的陷阱的詳細(xì)內(nèi)容,更多關(guān)于Java正則表達(dá)式的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!

您可能感興趣的文章:
  • Java使用正則表達(dá)式驗(yàn)證用戶名和密碼的方法
  • Java常用正則表達(dá)式驗(yàn)證類完整實(shí)例【郵箱、URL、IP、電話、身份證等】
  • Java使用正則表達(dá)式驗(yàn)證手機(jī)號(hào)和電話號(hào)碼的方法
  • Java替換中使用正則表達(dá)式實(shí)現(xiàn)中間模糊匹配的方法
  • java 正則表達(dá)式獲取兩個(gè)字符中間的字符串方法
  • Java 使用正則表達(dá)式對(duì)象實(shí)現(xiàn)正則的獲取功能
  • JAVA正則表達(dá)式校驗(yàn)qq號(hào)碼的方法

標(biāo)簽:駐馬店 阜陽(yáng) 臨夏 黑河 延邊 中衛(wèi) 欽州 南昌

巨人網(wǎng)絡(luò)通訊聲明:本文標(biāo)題《Java正則表達(dá)式里隱藏的陷阱》,本文關(guān)鍵詞  Java,正則,表達(dá)式,里,隱藏,;如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問(wèn)題,煩請(qǐng)?zhí)峁┫嚓P(guān)信息告之我們,我們將及時(shí)溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò),涉及言論、版權(quán)與本站無(wú)關(guān)。
  • 相關(guān)文章
  • 下面列出與本文章《Java正則表達(dá)式里隱藏的陷阱》相關(guān)的同類信息!
  • 本頁(yè)收集關(guān)于Java正則表達(dá)式里隱藏的陷阱的相關(guān)信息資訊供網(wǎng)民參考!
  • 推薦文章