220
一個由正則表達式引發的血案
今天為大家送上一篇很有意思的小文章，具有提神醒腦之功效。作者是來自阿裏巴巴LAZADA產品技術部的申徒童鞋。
近期我在為Lazada賣家中心做一個自助注冊的項目，其中的shop name校驗規則較為複雜，要求：
1. 英文字母大小寫
2. 數字
3. 越南文
4. 一些特殊字符，如“&”，“-”，“_”等
看到這個要求的時候，自然而然地想到了正則表達式。於是就有了下麵的表達式（寫的比較齪）：
^([A-Za-z0-9._()&'\- ]|[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])+$
在測試環境，這個表達式從功能上符合業務方的要求，就被發布到了馬來西亞的線上環境。結果上線之後，發現線上機器時有發生CPU飆到100%的情況，導致整個站點響應異常緩慢。通過dump線程trace，才發現線程全部卡在了這個正則表達式的校驗上：
一開始難以置信，一個正則表達式的匹配過程怎麼可能引發CPU飆高呢？抱著懷疑的態度去查了資料才發現小小的正則表達式裏麵竟然大有文章，平時寫起來都是淺嚐輒止，隻要能夠滿足功能需求，就認為達到目的了，完全忽略了它可能帶來的性能隱患。
引發這次血案的就是所謂的正則“回溯陷阱（Catastrophic Backtracking）”。下麵詳細介紹下這個問題，以避免重蹈覆轍。
說起回溯陷阱，要先從正則表達式的引擎說起。正則引擎主要可以分為基本不同的兩大類：一種是DFA（確定型有窮自動機），另一種是NFA（不確定型有窮自動機）。簡單來講，NFA 對應的是正則表達式主導的匹配，而 DFA 對應的是文本主導的匹配。
DFA從匹配文本入手，從左到右，每個字符不會匹配兩次，它的時間複雜度是多項式的，所以通常情況下，它的速度更快，但支持的特性很少，不支持捕獲組、各種引用等等；而NFA則是從正則表達式入手，不斷讀入字符，嚐試是否匹配當前正則，不匹配則吐出字符重新嚐試，通常它的速度比較慢，最優時間複雜度為多項式的，最差情況為指數級的。但NFA支持更多的特性，因而絕大多數編程場景下（包括java，js），我們麵對的是NFA。以下麵的表達式和文本為例，
text ＝ ‘after tonight’
regex ＝ ‘to(nite|nighta|night)’
在NFA匹配時候，是根據正則表達式來匹配文本的，從t開始匹配a，失敗，繼續，直到文本裏麵的第一個t，接著比較o和e，失敗，正則回退到 t，繼續，直到文本裏麵的第二個t，然後 o和文本裏麵的o也匹配，繼續，正則表達式後麵有三個可選條件，依次匹配，第一個失敗，接著二、三，直到匹配。
而在DFA匹配時候，采用的是用文本來匹配正則表達式的方式，從a開始匹配t，直到第一個t跟正則的t匹配，但e跟o匹配失敗，繼續，直到文本裏麵的第二個 t 匹配正則的t，接著o與o匹配，n的時候發現正則裏麵有三個可選匹配，開始並行匹配，直到文本中的g使得第一個可選條件不匹配，繼續，直到最後匹配。
可以看到，DFA匹配過程中文本中的字符每一個隻比較了一次，沒有吐出的操作，應該是快於NFA的。另外，不管正則表達式怎麼寫，對於DFA而言，文本的匹配過程是一致的，都是對文本的字符依次從左到右進行匹配，所以，DFA在匹配過程中是跟正則表達式無關的，而 NFA 對於不同但效果相同的正則表達式，匹配過程是完全不同的。
說完了引擎，我們再來看看到底什麼是回溯。對於下麵這個表達式，相信大家很清楚它的意圖，
ab{1,3}c
也就是說中間的b需要匹配1~3次。那麼對於文本“abbbc”，按照第1部分NFA引擎的匹配規則，其實是沒有發生回溯的，在表達式中的a匹配完成之後，b恰好和文本中的3個b完整匹配，之後是c發生匹配，一氣嗬成。如果我們把文本換成“abc”呢？無非就是少了一個字母b，卻發生了所謂的回溯。匹配過程如下圖所示（橙色為匹配，黃色為不匹配），
1~2步應該都好理解，但是為什麼在第3步開始，雖然已經文本中已經有一個b匹配了b{1,3}，後麵還會拉著字母c跟b{1,3}做比較呢？這個就是我們下麵將要提到的正則的貪婪特性，也就是說b{1,3}會竭盡所能的匹配最多的字符。在這個地方我們先知道它一直要匹配到撞上南牆為止。 在這種情況下，第3步發生不匹配之後，整個匹配流程並沒有走完，而是像棧一樣，將字符c吐出來，然後去用正則表達式中的c去和文本中的c進行匹配。這樣就發生了一次回溯。
我們再來看一下究竟什麼是貪婪模式。
下麵的幾個特殊字符相信大家都知道它們的用法：
i. ?: 告訴引擎匹配前導字符0次或一次。事實上是表示前導字符是可選的。
ii. +: 告訴引擎匹配前導字符1次或多次。
iii. *: 告訴引擎匹配前導字符0次或多次。
iv. {min, max}: 告訴引擎匹配前導字符min次到max次。min和max都是非負整數。如果有逗號而max被省略了，則表示max沒有限製；如果逗號和max都被省略了，則表示重複min次。
默認情況下，這個幾個特殊字符都是貪婪的，也就是說，它會根據前導字符去匹配盡可能多的內容。這也就解釋了為什麼在第3部分的例子中，第3步以後的事情會發生了。
在以上字符後加上一個問號（？）則可以開啟懶惰模式，在該模式下，正則引擎盡可能少的重複匹配字符，匹配成功之後它會繼續匹配剩餘的字符串。在上例中，如果將正則換為
ab{1,3}?c
則匹配過程變成了下麵這樣（橙色為匹配，黃色為不匹配），
由此可見，在非貪婪模式下，第2步正則中的b{1,3}?與文本b匹配之後，接著去用c與文本中的c進行匹配，而未發生回溯。
如果在以上四種表達式後加上一個加號（+），則會開啟獨占模式。同貪婪模式一樣，獨占模式一樣會匹配最長。不過在獨占模式下，正則表達式盡可能長地去匹配字符串，一旦匹配不成功就會結束匹配而不會回溯。我們以下麵的表達式為例，
ab{1,3}+bc
如果我們用文本"abbc"去匹配上麵的表達式，匹配的過程如下圖所示（橙色為匹配，黃色為不匹配），
可以發現，在第2和第3步，b{1,3}+會將文本中的2個字母b都匹配上，結果文本中隻剩下一個字母c。那麼在第4步時，正則中的b和文本中的c進行匹配，當無法匹配時，並不進行回溯，這時候整個文本就無法和正則表達式發生匹配。如果將正則表達式中的加號（+）去掉，那麼這個文本整體就是匹配的了。
把以上三種模式的表達式列出如下，
現在再回過頭看看文章開頭的那個很長的正則表達式，其實簡化之後，就是一個形如
^[允許字符集]+
的表達式。該字符集大小約為250，而+號表示至少出現一次。按照上麵說到的NFA引擎貪婪模式，在用戶輸入一個過長字符串進行匹配時，一旦發生回溯，計算量將是巨大的。後來采用了獨占模式，CPU 100%的問題也得到了解決。
因此，在自己寫正則表達式的時候，一定不能大意，在實現功能的情況下，還要仔細考慮是否會帶來性能隱患。
來源：阿裏技術
原文鏈接
最後更新：2017-08-25 10:32:39