感性认识—误报和漏报难以平衡 尝试寻找有理证明 WAF自身安全 正则表达式 计算复杂度 正则表达式DDOS攻击 非Regex DOS WAF防御能力 正则表达式DDOS攻击 提出一种正则表达式的DDOS攻击： 正则表达式的最坏时间复杂度大于等 于?(?2 )，该正则表达式可被DDOS 攻击 输入长度 (K) PCRE/PHP(ms) JAVA(ms) 1 0.5 142 8 458 500 10 720 786 20 2910 2941 Regex DDOS与Regex DOS不同 • ?(?2 )，?(2?) • Regex DDOS目前普遍存在 • Regex DOS很难找到了 寻找能被DDOS的正则表达式 寻找最坏时间复杂度大于等于? ?? 的正则表达式 利用正则表达式匹配的回溯 正则表达式匹配原理：NFA 匹配算法需要尝试每一条路径，直到找到一条匹配路径。尝试所有路径失败则匹配失败。 • 尝试所有匹配路径 • 路径尝试失败，需要回溯 正则表达式DDOS原理 正则：A.*B 文 本：AAN 正则：A.*B 文本：AAN 可被DDOS的一种正则表达式模式 ??????? = (????)(????)∗(SubC)，其中???? ∈ ???? 例如