作者：京东物流 刘海茂

近期碰到一起值班报警事件，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 "";
}