如何中断正则的执行

如果你在工作经常使用正则表达式的话，你可能对灾难性回溯（catastrophic backtracking）这个概念并不陌生，这说明你在强迫正则引擎去进行指数级的排列运算。比如说，点击这里运行下这个用例来看看它得花多长时间（大概是5到10秒）：

public class LongRunningRegexExample
{
   public static void main(String[] args) throws InterruptedException
   {
      final Pattern pattern = Pattern.compile("(0*)*A");
      final String input = "00000000000000000000000000";

      long startTime = System.currentTimeMillis();
      Matcher matcher = pattern.matcher(input);
      matcher.find(); // runs for a long time!
      System.out.println("Regex took:" + (System.currentTimeMillis() - startTime) + "ms");
   }
}

然而只需一个很小的改动就能让它马上返回。为什么？引用 Dzone的Andreas Haufler在他的_如何使用正则表达式杀掉Java程序_一文中的一句话，这个简洁的示例程序也是来自这篇文章的：


乍一看它像是一个无限循环，这其实是一个灾难性回溯。这说明匹配器在输入结尾处没有找到'A'字符。因此外部检测器会后退一步，而内部的则前进一步，但仍然没有发现。

因此匹配器会不断地回退，尝试完所有的组合，来看一下是否存在一个匹配的字符串。它最终仍会返回（没有匹配上），但时间复杂度却是指数级的（增加一个字符运行时间会翻倍）。


那么我们该如何做才能避免这样的影响，有没有可能会遇到这么一个场景，要让Java进程运行好几天，甚至好几年的？

如果你不嫌麻烦的话，你可以在自己的正则模式中注意去避免这样的情况。但是如果你部署了一个应用，它接受一个输入作为正则表达式的话——比如说一个在线的Java正则校验器，那么你需要防止这种情况，否则就可能会遭受拒绝服务攻击。

答案非常简单，不过你需要引入一个线程，下面是我在stackoverflow上找到的一个特殊的字符序列的实现。

public class InterruptibleRegexExample
{
   public static void main(String[] args) throws InterruptedException
   {
      final Pattern pattern = Pattern.compile("(0*)*A");
      final String input = "00000000000000000000000000";

      Runnable runnable = new Runnable() {
         @Override
         public void run()
         {
            long startTime = System.currentTimeMillis();
            Matcher interruptableMatcher = pattern.matcher(new InterruptibleCharSequence(input));
            interruptableMatcher.find(); // runs for a long time!
            System.out.println("Regex took:" + (System.currentTimeMillis() - startTime) + "ms");
         }
      };

      Thread thread = new Thread(runnable);
      thread.start();

      Thread.sleep(500);
      thread.interrupt();
   }
}

这样这个正则就非常棒了，它是可中断的。

Exception in thread "Thread-2" java.lang.RuntimeException: Die! ... Why won't you DIE!
at org.ocpsoft.tutorial.regex.server.InterruptRegex$InterruptibleCharSequence.charAt(InterruptRegex.java:72)
at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3366)
at java.util.regex.Pattern$Curly.match0(Pattern.java:3760)
at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)

当然了你需要用到InterruptibleCharSequence，这多少会影响到程序的性能，不过总比干等一年要好得多：

/**
 * {@link CharSequence} that notices {@link Thread} interrupts
 * 
 * @author gojomo - http://stackoverflow.com/questions/910740/cancelling-a-long-running-regex-match
 */
private static class InterruptibleCharSequence implements CharSequence {
   CharSequence inner;

   public InterruptibleCharSequence(CharSequence inner) {
      super();
      this.inner = inner;
   }

   @Override
   public char charAt(int index) {
      if (Thread.currentThread().isInterrupted()) {
         throw new RuntimeException("Interrupted!");
      }
      return inner.charAt(index);
   }

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

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

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

原创文章转载请注明出处：http://it.deepinmind.com


英文原文链接

评论

1 楼 QuarterLifeForJava 2014-06-18  

(任意字符)*  应该是匹配一切吧？

然后如果改为((0*)*)*A  这个就不知道要匹配多久了。。。
给我感觉多加一个*就多加个n次方，像上面这个感觉就是n的n次方的n次方