前一個主題說明了 災難性回溯，並提供實際範例，說明某人試圖讓正則表達式在自己的電腦上運作並執行良好的觀點。在閱讀這個主題之前，您應該先了解這些範例。

當災難性回溯發生在您的電腦上時，會令人感到困擾。但當它發生在具有多個同時使用者的伺服器應用程式中時，後果可能真的會很嚴重。太多使用者執行會出現災難性回溯的正規表示式會導致整個伺服器當機。而「太多」可能只需要伺服器中 CPU 核心數量的一小部分。

如果伺服器接受使用者的正規表示式，那麼使用者可以輕鬆地提供一個在任何主旨上會出現災難性回溯的正規表示式。如果伺服器接受使用者的主旨資料，那麼使用者可能會提供會觸發伺服器使用的正規表示式中災難性回溯的主旨，如果這些正規表示式容易發生災難性回溯的話。當使用者可以執行上述任何一項操作時，伺服器就會容易受到正則表達式拒絕服務 (ReDoS) 的影響。當足夠多的使用者（或一名偽裝成多名使用者的行為者）提供惡意的正規表示式和/或主旨進行比對時，伺服器將會花費幾乎所有 CPU 週期來嘗試比對這些正規表示式。

處理使用者提供的正規表示式

如果您的應用程式允許使用者提供自己的正規表示式，那麼您唯一真正的防禦措施就是使用 文字導向正規表示式引擎。這些引擎不會回溯。它們的效能取決於主旨字串的長度，而不是正則表達式的複雜度。但它們也不支援 反向參照 等依賴於回溯且許多使用者預期的功能。

如果您的應用程式使用具有使用者提供正規表示式的回溯引擎，那麼您只能減輕災難性回溯的後果。而且您真的需要這麼做。對於正規表示式技能有限的人來說，很容易意外地製作出會退化成災難性回溯的正規表示式。

您需要使用一個正規表達式引擎，當發生災難性回溯時，會中止比對嘗試，而不是執行到腳本崩潰或作業系統將其終止。您可以輕鬆地測試這一點。當正規表達式 (x\w{1,10})+y 在不斷增加的 x 字串上進行嘗試時，正規表達式引擎放棄的時間應該有一個合理的限制。理想情況下，您的引擎將允許您根據您的目的設定此限制。例如，.NET 引擎允許您將逾時傳遞給 Regex() 建構函式。PCRE 引擎允許您設定遞迴限制。您的限制越低，對抗 ReDoS 的防護就越好，但中止會找到有效比對的合法正規表達式的風險就越高，即使多給一點時間。低遞迴限制可能會阻止長正規表達式比對。低逾時可能會過早中止搜尋大型檔案。

如果您的正規表達式引擎沒有這些功能，您可以實作您自己的逾時。產生一個獨立執行緒來執行正規表達式。使用逾時等待執行緒。如果執行緒在等待逾時之前完成，處理其結果。否則，終止執行緒並告訴使用者正規表達式太過複雜。safe_regexp 套件為 Ruby 實作此功能。

檢閱應用程式中的正規表達式

如果伺服器只使用應用程式中硬編碼的正規表達式，則您可以完全防止基於正規表達式的阻斷服務攻擊。您需要確保您的正規表達式不會表現出災難性回溯，無論它們用於哪些主體。對於對正規表達式有紮實理解的人來說，這並不容易。但它確實需要小心和注意。僅測試正規表達式是否與有效主體相符是不夠的。您需要透過獨立於任何主體資料查看正規表達式來確保同一正規表達式的多個排列組合不可能相符同一事物。

當您讓正規表達式進行選擇時，就會發生排列組合。您可以使用 交替 和 量詞 來執行此操作。因此，這些是您需要檢查的正規表達式代碼。佔有 量詞除外，因為它們從不回溯。

交替

選項必須互斥。如果多個選項可以相符同一文字，則如果正規表達式的剩餘部分失敗，引擎將嘗試兩者。如果選項在重複的群組中，您就會有災難性回溯。

一個經典的範例是 (.|\s)*，用來在 regex 風格中沒有「點號比對換行」模式時，比對任意數量的任何文字。如果這是較長 regex 的一部分，那麼主旨字串中足夠長的一連串空白字元會中斷 regex。引擎會嘗試由 . 或 \s 比對的空白字元的所有可能組合。例如，3 個空白字元可以比對成 ...、..\s、.\s.、.\s\s、\s..、\s.\s、\s\s. 或 \s\s\s。那是 2^N 個排列組合。解決方法是使用 (.|\n)*，讓這些選項互斥。更棒的方法是更明確地指出哪些字元真正被允許，例如 [\r\n\t\x20-\x7E]*，代表 ASCII 可列印字元、跳格鍵和換行字元。

兩個選項部分比對相同文字是可以接受的。 [0-9]*\.[0-9]+|[0-9]+ 完全可以比對一個浮點數，其中整數部分和分數部分都是可選的。儘管只包含數字的主旨一開始會由 [0-9]* 比對，並且在 \. 失敗時會造成一些回溯，但這個回溯永遠不會變成災難。即使你將它放在較長 regex 中的群組內，群組也只會執行最少的回溯。（但群組不能有量詞，否則會違反巢狀量詞的規則。）

量詞順序

順序中的量化標記必須彼此互斥，或與它們之間的內容互斥。否則，兩個量詞都可以比對相同的文字，並且當 regex 的其餘部分無法比對時，會嘗試這兩個量詞的所有組合。群組內有交替選項的標記仍然與群組前後的任何標記順序相同。

一個經典的範例是 a.*?b.*?c，用來比對 3 個東西，中間有「任何東西」。當 c 無法比對時，第一個 .*? 會逐字擴充到行或檔案的結尾。對於每個擴充，第二個 .*? 會逐字擴充來比對行或檔案的剩餘部分。解決方法是體認到它們之間不能有「任何東西」。第一次執行需要在 b 停止，第二次執行需要在 c 停止。對於單一字元，a[^b]*b[^c]*c 是個簡單的解決方案。否定字元類別保證重複會在分隔符號停止。如果你的正規表示法風格支援 獨佔量詞，那麼你可以使用 a[^b]*+b[^c]*+c 進一步提升效能。

對於更複雜的範例和解決方案，請參閱前一個主題中的 比對一個完整的 HTML 檔案。這說明了如何在更複雜的情況下使用原子群組來防止回溯。

巢狀量詞

包含有量詞的代碼塊的群組，除非群組內部被量化的代碼塊只能與它互斥的其他東西比對，否則群組本身不能有量詞。這確保了外層量詞的較少次反覆與內層量詞的較多次反覆，不可能與外層量詞的較多次反覆與內層量詞的較少次反覆比對相同的文字。

正規表示法 (x\w{1,10})+y 比對一個或多個以 x 開頭的代碼，後面接著 1 到 10 個字元字元，最後接著 y。只要可以比對 y，一切都很好。當 y 遺失時，就會發生回溯。如果字串沒有太多 x，那麼回溯會很快發生。只有當主旨包含一個長序列的 x 時，事情才會變成災難。 x 和 x 不是互斥的。因此，重複的群組可以在一次反覆中比對 xxxx，例如 x\w\w\w，或在兩次反覆中比對 x\wx\w。

若要解決此問題，您首先需要考慮是否允許 x 和 y 出現在其後的 1 至 10 個字元中。排除 x 可消除大部分回溯。剩下的部分不會造成災難性的後果。您可以使用 字元類別減法 來排除它，例如 (x[\w-[x]]{1,10})+y，或使用 字元類別交集，例如 (x[\w&&[^x]]{1,10})+y。如果您沒有這些功能，則需要拼出您要允許的字元：(x[a-wyz0-9_]{1,10})+y。

如果允許 x，則唯一的解決方案是同樣不允許 y。然後，您可以讓群組成為原子群組或讓量詞成為獨佔量詞，以消除回溯。

如果允許 x 和 y 出現在 1 至 10 個字元的序列中，則沒有僅使用正規表示式的解決方案。您無法讓群組成為原子群組或讓量詞成為獨佔量詞，因為這樣 \w{1,10} 會與最後一個 y 匹配，這會導致 y 失敗。

其他防禦技術

除了防止如上所述的災難性回溯之外，您應該讓您的正規表示式盡可能嚴格。正規表示式越嚴格，它執行的回溯就越少，因此效能越好。即使您無法衡量效能差異，因為正規表示式不常在短字串上使用，但正確的技術是一種習慣。它還能降低較缺乏經驗的開發人員在稍後擴充您的正規表示式時引入災難性回溯的機率。

盡可能將包含選項的群組設為原子。使用 \b(?>one|two|three)\b 來比對字詞清單。

盡可能將量詞設為所有格。如果重複的記號與其後內容互斥，請使用所有格量詞強制執行。

使用 (否定) 字元類別，而非句點。您真正想要允許「任何內容」的情況很少見。例如，雙引號字串無法包含「任何內容」。它無法包含未跳脫的雙引號。因此，請使用 "[^"\n]*+"，而非 ".*?"。雖然兩者在單獨使用時找到的比對結果完全相同，但後者在貼到較長的正規表示式中時會導致災難性回溯。前者永遠不會回溯，無論正規表示式需要比對其他任何內容。

為什麼要使用正規表示式？

有些人肯定會爭辯說，上述內容只顯示正規表示式很危險，不應該使用。然後，他們會強迫開發人員使用程序碼來完成這項工作。用於比對非平凡模式的程序碼很快就會變得冗長且複雜，這會增加錯誤的機率，並提高開發和維護程式碼的成本。許多模式比對問題都可以透過遞迴自然地解決。當無法比對大型主旨字串時，失控的遞迴會導致堆疊溢位，使應用程式當機。

開發人員需要學習正確使用他們的工具。這對正規表示式來說與其他任何事物並無不同。