Java Соответствие шаблону регулярного выражения занимает слишком много времени

Question

Функция сопоставления с образцом регулярного выражения java занимает слишком много времени, если образец и слова имеют что-то вроде

pattern = ".*.*.*.*.*.*.*.*.*.*1";
word = aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Для сопоставления указанного выше образца со словом требуется более 10 секунд. Верно, что этот шаблон не имеет смысла, но в моем случае шаблон берется как вводимый пользователем из формы GUI.

Я использовал следующий код.

        boolean matches = false;
        long startTime = System.nanoTime();
        try {
            matches = Pattern.compile(pattern).matcher(word.toLowerCase()).matches();
        } catch (Exception e) {
            e.printStackTrace();
        }
        long elapseTime = System.nanoTime() - startTime;
        elapseTime = elapseTime / 1000000000;
        System.out.println("Time taken for regex match " + elapseTime + " out put " + matches);

Answer 1

Это более или менее известная проблема безопасности с регулярными выражениями: вы можете банально отказать в обслуживании любому серверу, на котором вы можете вводить регулярные выражения. Вы можете создать регулярное выражение, которое требует бесконечного времени для работы с любым вводом. Ваш пример довольно плохой; Вы можете стать еще хуже.

Это, кстати, ВНУТРИ. Это регулярное выражение соответствует, если общая длина вашего ввода является простым числом, и не работает в противном случае: .?|(..+?)\\1+.

1. Найти простые числа сложно.
2. Выше является допустимым регулярным выражением.
3. Следовательно, регулярные выражения потенциально медленные и не могут быть сделаны быстрее. QED.

Таким образом, то, что вы хотите, невозможно, если мы не мыслим нестандартно. Есть два решения:

A. не сопоставляйте регулярные выражения, сопоставьте что-то еще. Что, если мы сопоставим почти регулярные выражения: регулярные выражения с удаленными некоторыми функциями exoti c. Это приведет вас к так называемому сопоставителю регулярных выражений Thompson NFA , который имеет некоторые незначительные ограничения (в первую очередь, без обратных ссылок, без извлечения группировки, не без дополнительных усилий - без обратных ссылок эта функция поиска простых чисел выше не может работать) . Возможно, вы найдете реализацию этого варианта регулярного выражения для java. На этом этапе вы можете просто посчитать размер ввода плюс размер регулярного выражения и сделать выводы о том, сколько времени потребуется для выполнения указанного регулярного выражения.

B. Вам нужно будет защитить любой поиск регулярных выражений с помощью потока таймера и прервать его или запретить пользователю вводить регулярные выражения. Запустите задание регулярного выражения в отдельном потоке только для этой цели, который был выделен (установлен низкий уровень приоритета) и охраняется потоком таймера, который его прерывает (), хотя вам нужно будет проверить, действительно ли код сопоставления останавливается в он отслеживает, если вы его прервете (держу пари, что не будет, в этот момент вы вообще не можете остановить бегущее регулярное выражение, и вам придется найти что-то не- java, или найти где-нибудь библиотеку регулярных выражений и поместить if (Thread.interrupted()) throw new InterruptedException(); где-то внутри одного из его циклов.

C. Предложите пользователю что-то, что не является регулярным выражением. Возможно, чтобы реализовать это, вы конвертируете ввод пользователя в регулярное выражение, а затем запускаете его в обычном режиме, но в рамках преобразования вы дважды проверяете определенные условия, чтобы гарантировать, что регулярное выражение не будет медленным.

NB: ваш пример регулярного выражения совместим с Thompson-NFA; регулярное выражение в стиле Thompson-NFA сделает это быстро. Однако, Регулярные выражения java не являются t-NFA.