关于cpu:从一次CPU打满到ReDos攻击和防范

作者：京东物流刘海茂

近期碰到一起值班报警事件，web 应用服务器 CPU 耗费打到 99%，排查后发现是因为 ReDoS 导致了服务器产生了资源被耗尽、拜访零碎迟缓的问题，通过排查过程从而分享下 ReDos 攻打的原理、常见场景以及防备和解决方案，如果有谬误欢送斧正。

值班的时候忽然报警，web 应用服务器 CPU 耗费打到 99%，同时现场反馈系统拜访迟缓

登录泰山平台，查看 ump 监控发现零碎耗费 CPU 耗费忽然被打满

通过 java 自带的 dump 工具，下载 jstock 文件，发现有大量雷同工作线程在运行，具体的堆栈信息如下

认真查看这些线程的执行代码，发现都调用了 UrlUtil.extractDomain 这个办法

依据堆栈信息查看业务代码，发现是 joybuy 登录拦截器用正则表达式匹配拜访 url 解析主域的办法呈现了阻塞，至此，能够判断是因为 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 的个性：

一个无限的状态汇合 S
一个输出符号汇合 sigma，空字符 epsilon 不属于 Sigma
状态迁徙函数 F，对于特定的输出字符和状态，输入对应的变更状态汇合

4.s0 为初始状态

5.S 子集为完结状态集

定义一个正则表达式 ^(a+)+$ 来对字符串 aaaaX 匹配。应用 NFA 的正则引擎，必须经验 2^4=16 次尝试失败后能力否定这个匹配。

同理字符串为 aaaaaaaaaaX 就要经验 2^10=1024 次尝试。如果咱们持续减少 a 的个数为 20 个、30 个或者更多，那么这里的匹配会变成指数增长

以 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$

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 "";
}

关于cpu:从一次CPU打满到ReDos攻击和防范

背景

ReDos 简介

阐明

常见 ReDoS 场景

ReDoS 检测

防备伎俩

解决办法