從一次CPU打滿到ReDos攻擊和防範

語言: CN / TW / HK

作者:京東物流 劉海茂

近期碰到一起值班報警事件,web應用伺服器CPU消耗打到99%,排查後發現是因為ReDoS導致了伺服器發生了資源被耗盡、訪問系統緩慢的問題,通過排查過程從而分享下ReDos攻擊的原理、常見場景以及防範和解決方案,如果有錯誤歡迎指正。

背景

值班的時候突然報警,web應用伺服器CPU消耗打到99%,同時現場反饋系統訪問緩慢

登入泰山平臺,檢視ump監控發現系統消耗CPU消耗突然被打滿

通過java自帶的dump工具,下載jstock檔案,發現有大量相同任務執行緒在執行,具體的堆疊資訊如下

仔細檢視這些執行緒的執行程式碼,發現都呼叫了UrlUtil.extractDomain這個方法

根據堆疊資訊檢視業務程式碼,發現是joybuy登入攔截器用正則表示式匹配訪問url解析主域的方法出現了阻塞,至此,可以判斷是因為ReDoS導致了伺服器發生了資源被耗盡、訪問系統緩慢的問題,那麼,什麼是ReDoS呢?

ReDos簡介

ReDoS攻擊(正則表示式拒絕服務攻擊(Regular Expression Denial of Service)),攻擊者可構造特殊的字串,導致正則表示式執行會消耗大量的記憶體和cpu導致伺服器資源被耗盡。無法繼續響應,那為何不確定的正則表示式會導致redos攻擊呢?這得從正則表示式的實現原理說起

原理

目前實現正則表示式引擎的方式有兩種

  • DFA自動機(Deterministic Finite Automaton,確定有限狀態自動機)
  • NFA自動機(Nondeterministic Finite Automaton,非確定有限狀態自動機)
  • DFA自動機的構造代價遠大於NFA自動機,但DFA自動機的執行效率高於NFA自動機
  • 假設一個字串的長度為n,如果採用DFA自動機作為正則表示式引擎,則匹配的時間複雜度為O(n)
  • 如果採用NFA自動機作為正則表示式引擎,NFA自動機在匹配過程中存在大量的分支和回溯,假設NFA的狀態數為s,
  • 則匹配的時間複雜度為O(ns)
  • NFA自動機的優勢是支援更多高階功能,但都是基於子表示式獨立進行匹配
  • 因此在程式語言裡,使用的正則表示式庫都是基於NFA自動機實現的

NFA的特性:

1.一個有限的狀態集合S

2.一個輸入符號集合sigma,空字元epsilon不屬於Sigma

3.狀態遷移函式F,對於特定的輸入字元和狀態,輸出對應的變更狀態集合

4.s0為初始狀態

5.S子集為結束狀態集

說明

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

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

常見ReDoS場景

以java為例,有以下幾種常見的ReDoS場景:

1、使用javax.validation.constraints.Pattern驗證入參是否合理的場景

/**
 * 客戶備註
 * */
@ExcelProperty(index = 14)
@Length(min = 11 , max = 11, message = "VAT號必須為11位")
@Pattern(regexp = "^(GB)\\d{9}", message = "VAT號必須以GB開頭,9位數字結尾")
private String vatNumber;

2、使用String.matches進行業務資料驗證的場景

//發票日期格式yyyy-MM-dd
String regExp = "^[1-9]\\d{3}-(0?[1-9]|1[0-2])-(0?[1-9]|[1-2][0-9]|3[0-1])$";
if (StringUtils.isNotBlank(outstockDto.getInvoiceDate()) && !outstockDto.getInvoiceDate().matches(regExp)){
    totalMsg.add(new ErrorMsgDTO(ResultCodeEnum.OUTSTOCK_INVOICE_DATE_FORMAT_ERROR.getCode()));
}

3、使用String.replaceAll做引數替換的場景

private String getParamName(String str) {
    if (PATTERN_START_END.matcher(str).matches()) {
        String newStr = str.replaceAll("#\\{", "").replaceAll("\\}", "");
        if (StringUtils.isEmpty(newStr)) {
            return "";
        } else if (newStr.contains(".")) {
            return StringUtils.substringAfterLast(newStr, ".");
        }
        return newStr;
    }
    return null;
}

4、配置檔案匹配引數的場景

# joybuy登入主域
joybuy.login.domain = .*fop\.joybuy\.com$
# 歐美B賬號登入主域
pulsar.login.domain = .*ifop\.jd\.com$

ReDoS檢測

1、RegexStaticAnalysis工具

測試方式如下:

使用maven package 打包後執行本地執行,輸入需要測試的正則表示式

2、線上測試地址:https://regex101.com/

測試方式:

直接在輸入框輸入正則表示式和需要測試的字串,既可以看到對飲匹配的步數和結果

在dubugger模式下可以檢視匹配的詳細過程和步數

防範手段

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

  • 降低正則表示式的複雜度, 儘量少用分組
  • 嚴格限制使用者輸入的字串長度
  • 使用單元測試、fuzzing 測試保證安全
  • 使用靜態程式碼分析工具
  • 增加效能監控,如ump、pfinder等

解決方法

瞭解了ReDoS的原理和防範,針對本次CPU的報警程式碼進行了優化,採用判斷請求路徑和分割字串的方式獲取訪問的域,避免使用正則表示式導致的ReDoS問題

實際修復程式碼

public static String extractDomain(String url) {
    if(StringUtils.isBlank(url)) {
        return "";
    }
    int index = 0;
    if(url.startsWith(HTTP)) {
        index = HTTP.length();
    } else if(url.startsWith(HTTPS)) {
        index = HTTPS.length();
    } else {
        return "";
    }
    String safeUrl = url.substring(index);
    index = safeUrl.indexOf('/');
    if(index > 0) {
        safeUrl = safeUrl.substring(0, index);
    }
    String[] array = safeUrl.split("\\.");
    if(array.length < 2) {
        return "";
    }
    String part1 = array[array.length - 2];
    String part2 = array[array.length - 1];


    if(StringUtils.isNotBlank(part1) && StringUtils.isNotBlank(part2)) {
        if(!isIn(part2, DOMAINS)) {
            return "";
        }
        return part1 + '.' + part2;
    }
    return "";
}