ReDoS 正規表達式阻斷服務攻擊
正規表達式
正規表達式(Regular Expression)是由字元(可為英文字母、數字、符號等)與元字元(特殊符號)組成的一種有特定規則的特殊字元串。通常被用於驗證身分證號、電子信箱、網址、手機號碼等。
正規表達式引擎分類
引擎主要可以分為兩大類:一種是DFA,一種是NFA
DFA對於字串裡的每一個字符只需掃描一次,比較快,但特性較少,使用DFA引擎的程式主要有:awk 、 egrep 、 flex 、 lex 、 MySQL 、 Procmail等
NFA匹配回溯算法,以指定順序測試正規表達式的所有可能的擴展並接受第一個匹配項 , 使用NFA引擎的程式主要有:GNU Emacs、Java 、 ergp 、 less 、 more 、 .NET 、 PCRE library 、 Perl 、 PHP 、 Python 、 Ruby 、 sed 、 vi
如何造成ReDoS
開發人員使用了正規表達式來對用戶輸入的數據進行有效性校驗 , 當程式存在缺陷或不嚴謹 , 可能會產生大量消耗運算資源的情況,因而使得系統無法處理其他的請求,造成伺服器服務停止或中斷。
實際範例
使用NFA 匹配回溯算法
範例1
正規表達式:^(a+)+$
輸入字串:aaaab
總共執行了53次步驟
範例2
正規表達式:^(a+)+$
輸入字串:aaaaaaaab
總共執行了778次步驟
範例2只比範例1多加了4個字元,卻多了14倍的步驟,造成伺服器大量使用資源 , 嚴重的話將造成伺服器停擺
如何預防
1.限制使用者輸入長度
2.避免使用複雜的正規表達式
3.單元測試
其它
.NET 4.5以上Regex可設置執行時間,若超過設置時間將拋出例外錯誤
參考網址:Regex
近期留言