如何中断一个长时间运行的“无限”Java正则表达式

如果你处理过大量的正则表达式,那么你对“catastrophic backtracking”的概念一定不陌生,这种情况下处理器被强迫执行指数倍的计算。例如,点击该示例,看看它需要多久完成(应该在5-10秒后超时)。

    LongRunningRegexExample.java
    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的文章《How to Kill Java with a Regular Expression》,其中提到了这个非常简洁的例子:

  • 第一眼看上去像是无限循环的东西会造成catastrophic backtracking

  • 意思是说匹配器在输入的末尾并没有检测到”A”。现在外侧的限定符后退一次,内存的则前进一次,如此重复,无法得到结果。

  • 因此,匹配器逐步回退,并尝试所有的组合以找出匹配符号。它最终将返回(没有匹配的结果),但是该过程的复杂性是指数型的(输入中添加一个字符加倍了运行时间)。

所以,我们究竟该采取何种方式避免这种破坏性的影响,我们是否会遇到Java程序运行数天甚至几年的情形?

在你的资源非常充足的情况下,你也许可以简单小心的在你的模式中避免这种情况。但是,如果你正在开发一个接受正则表达式作为输入的应用程序,例如一个在线Java可视化的正则表达式示例,那么你就应该避免这种情情况或是受到拒绝服务器攻击。

幸运的是,答案非常简单,但需要引入一个线程,以及一个非常特殊的字符串序列。我是在StackOverflow上找到该实现的。

    InterruptibleRegexExample.java
    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类,它在某种程度上也会影响性能,但是要比等上一年要好的多:

    InterruptibleCharSequence.java
    /**
     * {@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();
      }
    }

结论

我很开心能学习并撰写这些内容,这篇博客总结了正则表达式的无限运行及解决方案(Java中),希望它能帮到其他遇到该问题的人。愉快的过程!

原文链接: ocpsoft 翻译: ImportNew.com - 人晓
译文链接: http://www.importnew.com/11975.html
[ 转载请保留原文出处、译者和译文链接。]

关于作者: 人晓

(新浪微博:@人晓

查看人晓的更多文章 >>



相关文章

发表评论

Comment form

(*) 表示必填项

还没有评论。

跳到底部
返回顶部