淺析ReDoS的原理與實踐

*本文原創作者：MyKings，本文屬FreeBuf原創獎勵計劃，未經許可禁止轉載

ReDoS(Regular expression Denial of Service) 正則表達式拒絕服務攻擊。

開發人員使用了正則表達式來對用戶輸入的數據進行有效性校驗, 當編寫校驗的正則表達式存在缺陷或者不嚴謹時, 攻擊者可以構造特殊的字元串來大量消耗伺服器的系統資源，造成伺服器的服務中斷或停止。

1 常見術語

先讓我們來了解幾個概念:

1.1 Regex

正則表達式(Regular Expression, Regex)是由字元(可為英文字母、數字、符號等)與元字元(特殊符號)組成的一種有特定規則的特殊字元串。在模式匹配中，正則表達式通常被用於驗證郵箱、URL、手機號碼等。

常用元字元:

更多元字元請點擊閱讀原文。

1.2 DoS & DDoS

拒絕服務攻擊(Denial-of-Service Attack)亦稱洪水攻擊，是一種網路攻擊手法，其目的在於使目標電腦的網路或系統資源耗盡，使服務暫時中斷或停止，導致其正常用戶無法訪問。

分布式拒絕服務攻擊(Distributed Denial-of-Service Attack)，是使用網路上兩個或兩個以上被攻陷的電腦作為 「殭屍」 向特定的目標發動 「拒絕服務」 式攻擊。

DDoS攻擊可以具體分成兩種形式：

帶寬消耗型攻擊

• 
  

  洪水攻擊

  
  
  
  

  UDP、ICMP、ping of death



• 
  

  放大攻擊

  
  
  
  

  NTP、DNS




資源消耗型攻擊





• 
  

  SYN洪水、LAND attack、CC

1.3 FSM、DFA、 NFA

有限狀態自動機：

有限狀態自動機擁有有限數量的狀態，每個狀態可以遷移到零個或多個狀態，輸入字串決定執行哪個狀態的遷移。

有限狀態自動機還可以分成確定與非確定兩種, 非確定有限狀態自動機可以轉化為確定有限狀態自動機。

正則表達式引擎分成兩類：一類稱為DFA（確定性有限狀態自動機），另一類稱為NFA（非確定性有限狀態自動機）。兩類引擎要順利工作，都必須有一個正則式和一個文本串，一個捏在手裡，一個吃下去。

DFA捏著文本串去比較正則式，看到一個子正則式，就把可能的匹配串全標註出來，然後再看正則式的下一個部分，根據新的匹配結果更新標註。

而NFA是捏著正則式去比文本，吃掉一個字元，就把它跟正則式比較，匹配就記下來：「某年某月某日在某處匹配上了！」，然後接著往下干。

一旦不匹配，就把剛吃的這個字元吐出來，一個個的吐，直到回到上一次匹配的地方。

部分程序及其所使用的正則引擎:

2 ReDoS 原理

2.1 概述

DFA對於文本串里的每一個字元只需掃描一次，比較快，但特性較少；NFA要翻來覆去吃字元、吐字元，速度慢，但是特性(如:分組、替換、分割)豐富。

NFA支持 惰性(lazy)、回溯(backtracking)、反向引用(backreference)，NFA預設應用greedy模式，NFA可能會陷入遞歸險境導致性能極差。

2.2 說明

我們定義一個正則表達式^(a+)+$來對字元串aaaaX匹配。使用NFA的正則引擎，必須經歷2^4=16次嘗試失敗後才能否定這個匹配。

同理字元串為aaaaaaaaaaX就要經歷2^10=1024次嘗試。如果我們繼續增加a的個數為20個、30個或者更多，那麼這裡的匹配會變成指數增長。

下面我們以python語言為例子來進行代碼的演示:

#!/usr/bin/env python# coding: utf-8import reimport timedef exp(target_str):
"""
"""
s1 = time.time()
flaw_regex = re.compile("^(a+)+$")
flaw_regex.match(target_str)
s2 = time.time()
print("Consuming time: %.4f" % (s2-s1))if __name__ == "__main__":
str_list = ( "aaaaaaaaaaaaaaaaX", # 2^16
"aaaaaaaaaaaaaaaaaaX", # 2^18
"aaaaaaaaaaaaaaaaaaaaX", # 2^20
"aaaaaaaaaaaaaaaaaaaaaaX", # 2^22
"aaaaaaaaaaaaaaaaaaaaaaaaX", # 2^24
"aaaaaaaaaaaaaaaaaaaaaaaaaaX", # 2^26
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaX", # 2^36
) for evil_str in str_list:
print("Current: %s" % evil_str)
exp(evil_str)
print("--"*40)

把上面的代碼保存成redos.py文件並執行這個 py 腳本文件:

$ python redos.pyCurrent: aaaaaaaaaaaaaaaaX
Consuming time: 0.0043--------------------------------------------------------------------------------Current: aaaaaaaaaaaaaaaaaaX
Consuming time: 0.0175--------------------------------------------------------------------------------Current: aaaaaaaaaaaaaaaaaaaaX
Consuming time: 0.0678--------------------------------------------------------------------------------Current: aaaaaaaaaaaaaaaaaaaaaaX
Consuming time: 0.2370--------------------------------------------------------------------------------Current: aaaaaaaaaaaaaaaaaaaaaaaaX
Consuming time: 0.9842--------------------------------------------------------------------------------Current: aaaaaaaaaaaaaaaaaaaaaaaaaaX
Consuming time: 4.1069--------------------------------------------------------------------------------Current: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaX

輸出到最後一行貌似程序卡住了，我們來看下電腦的 CPU:

CPU利用率已經快接近100%了，我們在分別執行兩次(

電腦配置低的慎重操作

2.3 總結

每個惡意的正則表達式模式應該包含：

• 
  

  使用重複分組構造



• 
  

  在重複組內會出現





• 
  

  重複



• 
  

  交替重疊

有缺陷的正則表達式會包含如下部分：

• 
  

  (a+)+



• 
  

  ([a-zA-Z]+)*



• 
  

  (a|aa)+



• 
  

  (a|a?)+



• 
  

  (.*a){x} | for x > 10

注意: 這裡的a是個泛指

2.4 實例

下面我們來展示一些實際業務場景中會用到的缺陷正則。

• 英文的個人名字:





• 
  

  Re

  gex: ^[a-zA-Z]+(([",.-][a-zA-Z ])?[a-zA-Z]*)*$



• 
  

  Payload: aaaaaaaaaaaaaaaaaaaaaaaaaaaa!




• Java Classname





• 
  

  Regex: ^(([a-z])+.)+[A-Z]([a-z])+$



• 
  

  P

  ayload: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!




• Email格式驗證





• 
  

  Regex: ^([0-9a-zA-Z]([-.w]*[0-9a-zA-Z])*@(([0-9a-zA-Z])+([-w]*[0-9a-zA-Z])*.)+[a-zA-Z]{2,9})$



• 
  

  Payload: a@aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!




• 多個郵箱地址驗證





• 
  

  Regex: ^[a-zA-Z]+(([",.-][a-zA-Z ])?[a-zA-Z]*)*s+<

  (w[-._w]*w@w[-._w]*w.w{2,3})>$|^(w[-._w]*w@w[-._w]*w.w{2,3})$



• 
  

  Payload: aaaaaaaaaaaaaaaaaaaaaaaa!




• 複數驗證





• 
  

  Regex: ^d*[0-9](|.d*[0-9]|)*$



• 
  

  Payload: 1111111111111111111111111!




• 模式匹配





• 
  

  Regex: ^([a-z0-9]+([-a-z0-9]*[a-z0-9]+)?.){0,}([a-z0-9]+([-a-z0-9]*[a-z0-9]+)?){1,63}(.[a-z0-9]{2,7})+$



• 
  

  Payload: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!

使用python來進行測試有缺陷的正則示例:

$ python -c "import re;re.match("^[a-zA-Z]+(([",.-][a-zA-Z ])?[a-zA-Z]*)*$", "aaaaaaaaaaaaaaaaaaaaaaaaaaaa!")"

3 ReDoS 防範

哪裡會用到Regex, 幾乎在我們的網路程序與設備資源的任何位置都會用到。如: WAF、Web前端、Web後端、DB資料庫等。

3.1 常見位置

客戶端

• 
  

  瀏覽器



• 
  

  移動設備

伺服器端

3.2 防範手段

防範手段只是為了降低風險而不能百分百消除 ReDoS 這種威脅。當然為了避免這種威脅的最好手段是盡量減少正則在業務中的使用場景或者多做測試, 增加伺服器的性能監控等。

• 
  

  降低正則表達式的複雜度, 盡量少用分組



• 
  

  嚴格限制用戶輸入的字元串長度(特定情況下)



• 
  

  使用單元測試、fuzzing 測試保證安全



• 
  

  使用靜態代碼分析工具, 如: sonar



• 
  

  添加伺服器性能監控系統, 如: zabbix

2.5 參考鏈接

《精通正則表達式》

http://blog.csdn.net/c601097836/article/details/47040703

http://hooopo.iteye.com/blog/548087

http://www.guoziweb.com/archive/1160.html

https://swtch.com/~rsc/regexp/regexp1.html

https://www.owasp.org/index.php/Regular_expression_Denial_of_Service_-_ReDoS

https://en.wikipedia.org/wiki/ReDoS

https://www.checkmarx.com/wp-content/uploads/2015/03/ReDoS-Attacks.pdf

https://www.exploit-db.com/docs/38149.pdf

https://www.owasp.org/index.php/Regular_expression_Denial_of_Service_-_ReDoS

https://www.owasp.org/images/3/38/20091210_VAC-REGEX_DOS-Adar_Weidman.pdf

https://www.owasp.org/index.php/OWASP_Validation_Regex_Repository

*本文原創作者：MyKings，本文屬FreeBuf原創獎勵計劃，未經許可禁止轉載