Java正则表达式易遭DOS攻击？求安全检测与规避方案

我在Intel Core i7机器上运行以下程序耗时1.5秒：

public static void main(String[] args) {
    String regex = ".*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*b.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*.*x";
    long start = System.nanoTime();
    boolean match = "aaabccc".matches(regex);
    long end = System.nanoTime();
    System.out.println((end - start) / 1e9);
}

该正则表达式由30个.*、一个b、再30个.*和最终的x组成。String.matches的返回耗时随.*数量呈指数级增长，时间复杂度为O(eⁿ)。若将30替换为50，运行耗时将超过一分钟。

我正计划搭建允许用户输入正则表达式的公共HTTP API，因此对此问题深感担忧：恶意用户可能输入此类正则表达式，导致服务器长时间高负载运行。

请问这是Java API中的已知问题吗？是否存在可行的解决方案，即一种可检测正则表达式是否具有危险性的方法？

1. 这是Java正则API的已知问题吗？ #

是，这属于正则表达式灾难性回溯问题，并非Java特有，所有基于传统NFA（非确定性有限自动机）实现的正则引擎都会出现该问题，Java的java.util.regex正是这类实现。

当正则表达式包含多个重叠的贪婪/惰性量词（比如多个.*）时，引擎会尝试所有可能的匹配组合寻找有效匹配；当目标字符串无法满足最终匹配条件（比如示例中目标字符串aaabccc不含x），引擎会进行大量回溯操作，时间复杂度呈指数级上升。

2. 可行的解决方案 #

• 使用限制回溯的正则引擎：Java 9及以上版本的java.util.regex支持Pattern.RESTRICTED标志，编译正则时指定该标志会限制可能引发灾难性回溯的模式，检测到危险模式时直接抛出PatternSyntaxException。示例代码：

  Pattern pattern = Pattern.compile(userProvidedRegex, Pattern.RESTRICTED);
  

• 提前检测危险正则模式：通过静态分析正则结构，识别高危特征：

  • 多个相邻的贪婪量词（如.*.*、\w+\w+）
  • 嵌套的量词结构（如(.*)*）
  • 重叠的可选分支且每个分支含量词
    可自行实现检测逻辑，或借助成熟的静态分析库扫描这些模式。

• 为正则匹配设置超时时间：通过线程池或FutureTask为匹配任务设置超时阈值，超时则终止任务，避免长期占用CPU。示例代码：

  ExecutorService executor = Executors.newSingleThreadExecutor();
  Future<Boolean> future = executor.submit(() -> {
      Pattern pattern = Pattern.compile(userProvidedRegex);
      return pattern.matcher(targetString).matches();
  });
  
  try {
      Boolean result = future.get(1, TimeUnit.SECONDS); // 设置1秒超时
      // 处理匹配结果
  } catch (TimeoutException e) {
      future.cancel(true);
      // 处理超时，返回错误提示
  } finally {
      executor.shutdown();
  }
  

• 规范用户的正则写法：引导用户使用高效写法，比如将多个.*合并为单个.*，或使用原子组(?>...)避免回溯，但这种方式依赖用户配合，对公共API来说可控性较低。

内容的提问来源于stack exchange，提问作者Klitos Kyriacou