限制正则表达式执行时间

正则表达式是一种非常方便的工具，为了支持更强大的搜索功能，大部分正则表达式引擎在某些场景会进行回溯（backtracking）。

JDK 8

例如正则表达式 (a+)*b ，在 OpenJDK 8 上测试。

Pattern compile = Pattern.compile("(a+)*b");
String string = "aaaaaaaaaaaaaaaaaaaaaaaab";
System.out.println(compile.matcher(string).matches());

执行速度非常快，似乎也没什么问题。但如果把最后一个 b 修改成 c，执行时间就需要超过 1 秒了。

耗时是指数级增长的，也可以再增加几个 a 试试。

灾难性回溯（Catastrophic Backtracking）

为什么会出现上面的问题呢？简单来说，就是某个字符无法确认是否匹配时，就假设可以匹配然后继续，如果后续匹配失败了，就会退到之前的状态。

或者可以用走迷宫来类比，当走到一个岔路的时候，不知道应该走哪条路，就可以先记录一下当前位置，然后根据策略先选择一条，如果没匹配到，再回到当前位置。

一般来说也没有问题，但是可以通过特殊构造的正则表达式，让搜索的空间变得非常巨大，直接占满 CPU，严重的话会导致线上事故。

PCRE2

https://regex101.com/ 是一个正则表达式开发测试的网站，可以显示正则表达式匹配的具体过程，例如刚才的例子。

可以打开 Debug 工具。

可以发现 aaaaaaaaaac 这个长度的字符串居然需要匹配超过 6000 步，这个工具可以一步一步展示匹配的过程，基本上都在出错然后回溯。

JDK 17

JDK 的正则表达式引擎也在不断优化中，上述例子，在 OpenJDK 17 已经几乎不耗时了。但因为正则表达式的原理，无法从根本上避免这样的问题，例如这段代码。

Pattern compile = Pattern.compile("(\\w|_){1,64}@");
String string = "_________________________";
System.out.println(compile.matcher(string).matches());

运行时间也超过 1 秒，而且也是指数级增长的。

限制执行时间

既然无法从根本上解决正则表达式回溯的问题，尤其是在表达式本身是任意输入的情况下，如何限制正则表达式的运行时间呢？

matcher 方法的参数类型是 CharSequence，而 CharSequence 又是一个接口，只有 3 个需要实现的方法。

/**
 * Creates a matcher that will match the given input against this pattern.
 *
 * @param  input
 *         The character sequence to be matched
 *
 * @return  A new matcher for this pattern
 */
public Matcher matcher(CharSequence input) {
    // ...
}

简单看下正则匹配的代码，就是不断在调用 charAt 方法。可以统计一下在上述 OpenJDK 17 例子中，charAt 方法调用超过 1 亿次。那么可以通过代理 CharSequence 来限制正则表达式的执行时间，

基于时间的

public final class TimedCharSequence implements CharSequence {
    private final CharSequence sequence;
    private final long timestamp;

    public TimedCharSequence(CharSequence sequence, long milliseconds) {
        this.sequence = sequence;
        this.timestamp = System.currentTimeMillis() + milliseconds;
    }

    @Override
    public String toString() {return sequence.toString();}

    @Override
    public int length() {return sequence.length();}

    @Override
    public char charAt(int index) {
        if (timestamp < System.currentTimeMillis()) {
            throw new IllegalStateException("Regex match timeout");
        }
        return sequence.charAt(index);
    }

    @Override
    public CharSequence subSequence(int start, int end) {return sequence.subSequence(start, end);}
}

基于次数的

public class CountedCharSequence implements CharSequence {
    private final CharSequence sequence;
    private long count;

    public CountedCharSequence(CharSequence sequence, long maxCount) {
        this.sequence = sequence;
        this.count = maxCount;
    }

    @Override
    public String toString() {return sequence.toString();}

    @Override
    public int length() {return sequence.length();}

    @Override
    public char charAt(int index) {
        if (count <= 0) {
            throw new IllegalStateException("Regex match timeout");
        }
        count--;
        return sequence.charAt(index);
    }

    @Override
    public CharSequence subSequence(int start, int end) {return sequence.subSequence(start, end);}
}

示例

限制最多执行一百万次调用。

Pattern compile = Pattern.compile("(\\w|_){1,64}@");
String string = "_________________________";
System.out.println(compile.matcher(new CountedCharSequence(string, 1_000_000)).matches());

限制最多执行 100 ms。

Pattern compile = Pattern.compile("(\\w|_){1,64}@");
String string = "_________________________";
System.out.println(compile.matcher(new TimedCharSequence(string, 100)).matches());

最终都会报错

java.lang.IllegalStateException: Regex match timeout

如果是基于时间的的话，需要频繁调用 currentTimeMillis，所以实践中，可以考虑用次数来反应时间，额外开销将会非常小。也可以自定义异常类，并包含更多的上下文信息。