Отменить длительный матч с регулярным выражением?

Question

Скажем, у меня есть служба, где пользователи могут отправлять регулярные выражения для поиска по большому количеству данных. Если пользователь отправляет регулярное выражение очень медленно (т.е. Matcher.find() возвращает минуты), я хочу отменить это совпадение. Единственный способ, которым я могу думать об этом, - это иметь другой монитор потока, сколько времени занимает совпадение, и использовать Thread.stop(), чтобы отменить его, если это необходимо.

Переменные-члены:

long REGEX_TIMEOUT = 30000L;
Object lock = new Object();
boolean finished = false;
Thread matcherThread;

Сопоставление темы:

try {
    matcherThread = Thread.currentThread();

    // imagine code to start monitor thread is here

    try {
        matched = matcher.find();
    } finally {
        synchronized (lock) {
            finished = true;
            lock.notifyAll();
        }
    }
} catch (ThreadDeath td) {
    // send angry message to client
    // handle error without rethrowing td
}

Мониторинг потока:

synchronized (lock) {
    while (! finished) {
        try {
            lock.wait(REGEX_TIMEOUT);

            if (! finished) {
                matcherThread.stop();
            }
        } catch (InterruptedException ex) {
            // ignore, top level method in dedicated thread, etc..
        }
    }
}

Я прочитал java.sun.com/j2se/1.4.2/docs/guide/misc/threadPrimitiveDeprecation.html и думаю, что это использование безопасно, так как я контролирую, где ThreadDeath выбрасывается через синхронизацию, и обрабатываю его, и только поврежденный объекты могут быть моими экземплярами Pattern и Matcher, которые все равно будут отброшены. Я думаю, что это нарушает Thread.stop(), потому что я не выкидываю ошибку, но я не хочу, чтобы поток умирал, просто прервите метод find ().

До сих пор мне удавалось избегать использования этих устаревших компонентов API, но Matcher.find(), кажется, не прерываемый и может занять очень много времени, чтобы вернуться. Есть ли лучший способ сделать это?

Answer 1

От Heritrix: ( http://crawler.archive.org/)

/**
 * CharSequence that noticed thread interrupts -- as might be necessary 
 * to recover from a loose regex on unexpected challenging input. 
 * 
 * @author gojomo
 */
public class InterruptibleCharSequence implements CharSequence {
    CharSequence inner;
    // public long counter = 0; 

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

    public char charAt(int index) {
        if (Thread.interrupted()) { // clears flag if set
            throw new RuntimeException(new InterruptedException());
        }
        // counter++;
        return inner.charAt(index);
    }

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

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

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

Оберните ваш CharSequence этим, и прерывания Thread будут работать...

Answer 2

С небольшими изменениями можно избежать использования дополнительных потоков для этого:

public class RegularExpressionUtils {

    // demonstrates behavior for regular expression running into catastrophic backtracking for given input
    public static void main(String[] args) {
        Matcher matcher = createMatcherWithTimeout(
                "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx", "(x+x+)+y", 2000);
        System.out.println(matcher.matches());
    }

    public static Matcher createMatcherWithTimeout(String stringToMatch, String regularExpression, int timeoutMillis) {
        Pattern pattern = Pattern.compile(regularExpression);
        return createMatcherWithTimeout(stringToMatch, pattern, timeoutMillis);
    }

    public static Matcher createMatcherWithTimeout(String stringToMatch, Pattern regularExpressionPattern, int timeoutMillis) {
        CharSequence charSequence = new TimeoutRegexCharSequence(stringToMatch, timeoutMillis, stringToMatch,
                regularExpressionPattern.pattern());
        return regularExpressionPattern.matcher(charSequence);
    }

    private static class TimeoutRegexCharSequence implements CharSequence {

        private final CharSequence inner;

        private final int timeoutMillis;

        private final long timeoutTime;

        private final String stringToMatch;

        private final String regularExpression;

        public TimeoutRegexCharSequence(CharSequence inner, int timeoutMillis, String stringToMatch, String regularExpression) {
            super();
            this.inner = inner;
            this.timeoutMillis = timeoutMillis;
            this.stringToMatch = stringToMatch;
            this.regularExpression = regularExpression;
            timeoutTime = System.currentTimeMillis() + timeoutMillis;
        }

        public char charAt(int index) {
            if (System.currentTimeMillis() > timeoutTime) {
                throw new RuntimeException("Timeout occurred after " + timeoutMillis + "ms while processing regular expression '"
                                + regularExpression + "' on input '" + stringToMatch + "'!");
            }
            return inner.charAt(index);
        }

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

        public CharSequence subSequence(int start, int end) {
            return new TimeoutRegexCharSequence(inner.subSequence(start, end), timeoutMillis, stringToMatch, regularExpression);
        }

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

}

Большое спасибо Доусу за то, что он указал мне на это решение в ответ на ненужный сложный вопрос!

Answer 3

Длительный процесс сопоставления с образцом можно остановить с помощью описанного ниже метода.

• Создайте StateFulCharSequenceкласс, который управляет состоянием сопоставления с образцом. Когда это состояние изменяется, при следующем вызове кcharAt метод.
• Это изменение состояния можно запланировать с помощью ScheduledExecutorService с требуемым таймаутом.

• Здесь сопоставление с образцом происходит в основном потоке, и нет необходимости каждый раз проверять состояние прерывания потока.

  public class TimedPatternMatcher {
  public static void main(String[] args) {
      ScheduledExecutorService executorService = Executors.newScheduledThreadPool(1);
      Pattern pattern = Pattern.compile("some regex pattern");
      StateFulCharSequence stateFulCharSequence = new StateFulCharSequence("some character sequence");
      Matcher matcher = pattern.matcher(stateFulCharSequence);
      executorService.schedule(stateFulCharSequence, 10, TimeUnit.MILLISECONDS);
      try {
          boolean isMatched = matcher.find();
      }catch (Exception e) {
          e.printStackTrace();
      }
  
  }
  
  /*
  When this runnable is executed, it will set timeOut to true and pattern matching is stopped by throwing exception.
   */
  public static class StateFulCharSequence implements CharSequence, Runnable{
      private CharSequence inner;
  
      private boolean isTimedOut = false;
  
      public StateFulCharSequence(CharSequence inner) {
          super();
          this.inner = inner;
      }
  
      public char charAt(int index) {
          if (isTimedOut) {
              throw new RuntimeException(new TimeoutException("Pattern matching timeout occurs"));
          }
          return inner.charAt(index);
      }
  
      @Override
      public int length() {
          return inner.length();
      }
  
      @Override
      public CharSequence subSequence(int start, int end) {
          return new StateFulCharSequence(inner.subSequence(start, end));
      }
  
      @Override
      public String toString() {
          return inner.toString();
      }
  
      public void setTimedOut() {
          this.isTimedOut = true;
      }
  
      @Override
      public void run() {
          this.isTimedOut = true;
      }
  }}
  

Answer 4

Другой обходной путь - ограничить область соответствия, а затем вызвать find()повторяется до тех пор, пока нить не прервется или не будет найдено совпадение.

Answer 5

Может быть, вам нужна новая библиотека, которая реализует алгоритм NFA.

Алгоритм NFA в сотни раз быстрее алгоритма, который используется стандартной библиотекой Java.

И библиотека Java std lib чувствительна к регулярному выражению ввода, что может привести к возникновению вашей проблемы - некоторые входные данные заставляют процессор работать годами.

И время ожидания может быть установлено алгоритмом NFA через шаги, которые он использует. Это эффективнее, чем решение Thread. Поверьте мне, я использую таймаут потока для относительной проблемы, это ужасно для производительности. Я наконец-то решил проблему, изменив основной цикл моего алгоритма. Я вставляю некоторую контрольную точку в основной цикл, чтобы проверить время.

Подробности можно найти здесь: https://swtch.com/~rsc/regexp/regexp1.html.

Answer 6

Я включил счетчик, чтобы проверять каждые n чтений charAt, чтобы уменьшить накладные расходы.

Примечания:

Некоторые люди заявили, что в автомобиль нельзя звонить достаточно часто. Я просто добавил переменную foo, чтобы продемонстрировать, сколько вызывается charAt и что это достаточно часто. Если вы собираетесь использовать это в производственной среде, удалите этот счетчик, так как он снизит производительность и в конечном итоге приведет к переполнению при длительной работе на сервере. В этом примере charAt вызывается 30 миллионов раз каждые 0,8 секунды или около того (не тестировалось в надлежащих условиях микробенчмаркинга, это просто доказательство концепции). Вы можете установить более низкий checkInterval, если хотите более высокую точность за счет производительности (System.currentTimeMillis() > timeoutTime в долгосрочной перспективе дороже, чем предложение if.

import java.util.regex.Matcher;
import java.util.regex.Pattern;

import com.goikosoft.test.RegexpTimeoutException;

/**
 * Allows to create timeoutable regular expressions.
 *
 * Limitations: Can only throw RuntimeException. Decreases performance.
 *
 * Posted by Kris in stackru.
 *
 * Modified by dgoiko to  ejecute timeout check only every n chars.
 * Now timeout < 0 means no timeout.
 *
 * @author Kris https://stackru.com/a/910798/9465588
 *
 */
public class RegularExpressionUtils {

    public static long foo = 0;

    // demonstrates behavior for regular expression running into catastrophic backtracking for given input
    public static void main(String[] args) {
        long millis = System.currentTimeMillis();
        // This checkInterval produces a < 500 ms delay. Higher checkInterval will produce higher delays on timeout.
        Matcher matcher = createMatcherWithTimeout(
                "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx", "(x+x+)+y", 10000, 30000000);
        try {
            System.out.println(matcher.matches());
        } catch (RuntimeException e) {
            System.out.println("Operation timed out after " + (System.currentTimeMillis() - millis) + " milliseconds");
        }
        System.out.print(foo);
    }

    public static Matcher createMatcherWithTimeout(String stringToMatch, String regularExpression, long timeoutMillis,
                                                      int checkInterval) {
        Pattern pattern = Pattern.compile(regularExpression);
        return createMatcherWithTimeout(stringToMatch, pattern, timeoutMillis, checkInterval);
    }

    public static Matcher createMatcherWithTimeout(String stringToMatch, Pattern regularExpressionPattern,
                                                    long timeoutMillis, int checkInterval) {
        if (timeoutMillis < 0) {
            return regularExpressionPattern.matcher(stringToMatch);
        }
        CharSequence charSequence = new TimeoutRegexCharSequence(stringToMatch, timeoutMillis, stringToMatch,
                regularExpressionPattern.pattern(), checkInterval);
        return regularExpressionPattern.matcher(charSequence);
    }

    private static class TimeoutRegexCharSequence implements CharSequence {

        private final CharSequence inner;

        private final long timeoutMillis;

        private final long timeoutTime;

        private final String stringToMatch;

        private final String regularExpression;

        private int checkInterval;

        private int attemps;

        TimeoutRegexCharSequence(CharSequence inner, long timeoutMillis, String stringToMatch,
                                  String regularExpression, int checkInterval) {
            super();
            this.inner = inner;
            this.timeoutMillis = timeoutMillis;
            this.stringToMatch = stringToMatch;
            this.regularExpression = regularExpression;
            timeoutTime = System.currentTimeMillis() + timeoutMillis;
            this.checkInterval = checkInterval;
            this.attemps = 0;
        }

        public char charAt(int index) {
            if (this.attemps == this.checkInterval) {
                foo++;
                if (System.currentTimeMillis() > timeoutTime) {
                    throw new RegexpTimeoutException(regularExpression, stringToMatch, timeoutMillis);
                }
                this.attemps = 0;
            } else {
                this.attemps++;
            }

            return inner.charAt(index);
        }

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

        public CharSequence subSequence(int start, int end) {
            return new TimeoutRegexCharSequence(inner.subSequence(start, end), timeoutMillis, stringToMatch,
                                                regularExpression, checkInterval);
        }

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

}

И настраиваемое исключение, так что вы можете поймать только ЭТО исключение, чтобы избежать проглатывания другого RE Pattern / Matcher, который может вызвать.

public class RegexpTimeoutException extends RuntimeException {
    private static final long serialVersionUID = 6437153127902393756L;

    private final String regularExpression;

    private final String stringToMatch;

    private final long timeoutMillis;

    public RegexpTimeoutException() {
        super();
        regularExpression = null;
        stringToMatch = null;
        timeoutMillis = 0;
    }

    public RegexpTimeoutException(String message, Throwable cause) {
        super(message, cause);
        regularExpression = null;
        stringToMatch = null;
        timeoutMillis = 0;
    }

    public RegexpTimeoutException(String message) {
        super(message);
        regularExpression = null;
        stringToMatch = null;
        timeoutMillis = 0;
    }

    public RegexpTimeoutException(Throwable cause) {
        super(cause);
        regularExpression = null;
        stringToMatch = null;
        timeoutMillis = 0;
    }

    public RegexpTimeoutException(String regularExpression, String stringToMatch, long timeoutMillis) {
        super("Timeout occurred after " + timeoutMillis + "ms while processing regular expression '"
                + regularExpression + "' on input '" + stringToMatch + "'!");
        this.regularExpression = regularExpression;
        this.stringToMatch = stringToMatch;
        this.timeoutMillis = timeoutMillis;
    }

    public String getRegularExpression() {
        return regularExpression;
    }

    public String getStringToMatch() {
        return stringToMatch;
    }

    public long getTimeoutMillis() {
        return timeoutMillis;
    }

}

На основании ответа Андреаса. Главные заслуги должны быть отданы ему и его источнику.

Answer 7

Как насчет проверки отправленного пользователем регулярного выражения на наличие "злых" шаблонов перед выполнением с использованием одного или нескольких шаблонов регулярных выражений (это может быть в форме метода, вызываемого до условного выполнения регулярного выражения):

Это регулярное выражение:

\(.+\+\)[\+\*]

Подойдет:

(a+)+
(ab+)+
([a-zA-Z]+)*

Это регулярное выражение:

\((.+)\|(\1\?|\1{2,})\)\+

Подойдет:

(a|aa)+
(a|a?)+

Это регулярное выражение:

\(\.\*.\)\{\d{2,}\}

Подойдет:

(.*a){x} for x \> 10

Я могу быть немного наивным по отношению к Regex и Regex DoS, но я не могу не думать, что небольшая предварительная проверка известных "злых" шаблонов будет иметь большое значение для предотвращения проблем во время выполнения, особенно если рассматриваемое регулярное выражение ввод, предоставляемый конечным пользователем. Приведенные выше шаблоны, вероятно, недостаточно доработаны, поскольку я далек от эксперта по регулярным выражениям. Это просто пища для размышлений, поскольку все остальное, что я там обнаружил, похоже, указывает на то, что это невозможно сделать, и фокусируется либо на установке тайм-аута в движке регулярных выражений, либо на ограничении количества итераций, которые ему разрешено выполнять..