Code Correctness: Regular Expressions Denial of Service

ABSTRACT

不可信賴數據被傳遞至應用程序并作為正則表達式使用。這會導致線程過度使用 CPU 資源。

EXPLANATION

實現正則表達式評估程序及相關方法時存在漏洞，該漏洞會導致評估線程在處理嵌套和重復的正則表達式組的重復和交替重疊時掛起。這個缺陷可被攻擊者用于執行 DOS (Denial of Service) 攻擊。
例 1：如果在已知易受攻擊的代碼中使用以下正則表達式，則可能發生 denial of service 攻擊：

		(e+)+
		([a-zA-Z]+)*
		(e|ee)+
		

依賴具有缺陷的正則表達式的問題代碼示例如下：

NSString *regex = @"^(e+)+$";
NSPredicate *pred = [NSPRedicate predicateWithFormat:@"SELF MATCHES %@", regex];
if ([pred evaluateWithObject:mystring])
{
//do something
}

大多數正則表達式解析器在評估正則表達式時會構建 Nondeterministic Finite Automaton (NFA) 結構。在找到完全匹配之前，NFA 會嘗試所有可能的匹配。在上例中，如果攻擊者使用匹配字符串 "eeeeZ"，則正則表達式解析器必須進行 16 次內部評估來確定匹配。如果攻擊者使用 16 個 "e" ("eeeeeeeeeeeeeeeeZ") 作為匹配字符串，則正則表達式解析器必須進行 65536 (2^16) 次評估。通過增加連續的匹配字符數，攻擊者可以輕易地消耗計算資源。已知的正則表達式實現方法均無法避免這種攻擊。所有平臺和語言都容易受到這種攻擊。

REFERENCES

[1] Standards Mapping - OWASP Top 10 2004 - (OWASP 2004) A9 Application Denial of Service

[2] Standards Mapping - Security Technical Implementation Guide Version 3 - (STIG 3) APP6080 CAT II

[3] Standards Mapping - Security Technical Implementation Guide Version 3.4 - (STIG 3.4) APP6080 CAT II

[4] Standards Mapping - Common Weakness Enumeration - (CWE) CWE ID 185, CWE ID 730

[5] Standards Mapping - Web Application Security Consortium 24 + 2 - (WASC 24 + 2) Denial of Service

[6] Bryan Sullivan Regular Expression Denial of Service Attacks and Defenses

[7] Standards Mapping - Payment Card Industry Data Security Standard Version 1.1 - (PCI 1.1) Requirement 6.5.9

97av