深度分析正則(pcre)最大回溯/遞歸限制

2020-01-20 22:17:18

字體：大中小

來源：轉載

供稿：網友

今天,Tank問了一個問題, 對于如下的正則:

復制代碼代碼如下:

/<script>.*?<//script>/i

當要匹配的字符串長度大于100014的時候, 就不會得出正確結果:

復制代碼代碼如下:

 
$reg = "/<script>.*?<//script>/is"; 
$str = "<script>********</script>"; //長度大于100014 
$ret = preg_replace($reg, "", $str); //返回NULL 

難道正則對匹配的串有長度限制?
不是, 當然不是, 原因是這樣的, 在PHP的pcre擴展中, 提供了倆個設置項.

復制代碼代碼如下:

 
pcre.backtrack_limit //最大回溯數 
pcre.recursion_limit //最大嵌套數 

默認的backtarck_limit是100000(10萬).
這個問題, 就和設置項backtrack_limit有關系. 現在要弄清這個問題的原因, 關鍵就是什么是”回溯”.
這個正則, 使用非貪婪模式, 非貪婪模式匹配原理簡單來說是, 在可配也可不配的情況下, 優先不匹配. 記錄備選狀態, 并將匹配控制交給正則表達式的下一個匹配字符, 當之后的匹配失敗的時候, 再溯, 進行匹配.
舉個例子:

復制代碼代碼如下:

 
源字符串: aaab 
正則: .*? 

匹配過程開始的時候, “.*?”首先取得匹配控制權, 因為是非貪婪模式, 所以優先不匹配, 將匹配控制交給下一個匹配字符”b”, “b”在源字符串位置1匹配失敗(“a”), 于是回溯, 將匹配控制交回給”.*?”, 這個時候, “.*?”匹配一個字符”a”, 并再次將控制權交給”b”, 如此反復, 最終得到匹配結果, 這個過程中一共發生了3次回溯.
現在我們來看看文章開頭的例子, 默認的backtrack_limit是100000, 而源字符串的開頭是9個字符, 一共是99997個字符.
另外, 因為match函數自身的邏輯, 在文章開頭的例子下, 會導致回溯計數增3(有興趣的可以參看pcrelib/pcre_exec.c中match函數邏輯部分), 所以在匹配到"“之前, pcre中的回溯計數剛好是100000,于是就正常匹配, 退出.
而, 只要在增加一個字符, 就會導致回溯計數大于100000, 從而導致匹配失敗退出.
在PHP 5.2以后, 提供了:

復制代碼代碼如下:

 
int preg_last_error ( void ) 
Returns the error code of the last PCRE regex execution. 

我們應該經常檢查這個函數的返回值, 當不為零的時候說明上一個正則函數出錯, 特別的對于文章的例子, 出錯返回(PREG_BACKTRACK_LIMIT_ERROR)
最后, 在順便說一句, 非貪婪模式導致太多回溯, 必然會有一些性能問題, 適當的該寫下正則, 是可以避免這個問題的. 比如將文章開頭例子中的正則修改為:

復制代碼代碼如下:

/<script>[^<]*<//script>/i

就不會導致這么多的回溯了~
而recursion_limit限制了最大的正則嵌套層數, 如果這個值, 設置的太大, 可能會造成耗盡?？臻g爆棧. 默認的100000似乎有點太大了…
就比如對于一個長度為10000的字符串, 如下這個看似”簡”的單正則:

復制代碼代碼如下:

 
//默認recursion_limit為100000 
$reg = /(.+?)+/is; 
$str = str_pad("laruence", 10000, "a"); //長度為1萬 
$ret = preg_repalce($reg, "", $str); 

會導致core, 這是因為嵌套太多, 導致爆棧.
當然, 你可以通過修改棧的大小來暫時的解決這個問題, 比如修改棧空間為20M以后, 上面的代碼就能正常運行, 但這肯定不是最完美的解法. 根本之道, 還是優化正則.
最后: 正則雖易, 用好卻難.. 尤其在做大數據量的文本處理的時候, 如果正則設計不慎, 很容易導致深度嵌套, 另外考慮到性能, 還是建議能用字符串處理盡量使用字符串處理代替.

上一篇：精確查找PHP WEBSHELL木馬修正版

下一篇：小議正則表達式效率貪婪、非貪婪與回溯