Статьи

Как убить Java с помощью регулярного выражения

Январь 22, 2019

Недавно мы столкнулись с феноменом, о котором мы абсолютно не знали: вы можете уничтожить любую Java IDE, а также любой процесс Java с помощью простого регулярного выражения…

Еще в университете меня учили, что регулярные выражения, которые называются регулярными грамматиками или грамматиками типа 3, всегда оказываются конечным автоматом и поэтому могут обрабатываться за линейное время (длина ввода удваивается, время обработки удваивается). Однако это верно только для «здравомыслящих» выражений. Регулярное выражение также может привести к недетерминированному автомату конечных состояний, и все может быть очень плохо.

Рассмотрим выражение: (0 *) * A Это будет любое количество нулей, за которым следует заглавная буква A. Теперь, если вы используете Matcher.find () для этого выражения, все в порядке, если во входных данных есть совпадение , Однако, если вы вызовете это, указав «00000000000000000000» в качестве входных данных, ваша программа будет зависать (как и консоль регулярных выражений в Eclipse или IntelliJ и в каждой (основанной на Java) онлайн-службе регулярных выражений).

То, что на первый взгляд выглядит как бесконечный цикл, превращается в катастрофическое возвращение назад . Это в основном означает, что устройство сопоставления обнаруживает, что в конце ввода не было найдено A. Теперь внешний квантификатор переходит на шаг назад — внутренний вперед и снова — безрезультатно. Таким образом, устройство сопоставления шаг за шагом повторяет все комбинации, чтобы найти совпадение. В конечном итоге он вернется (без совпадения), но сложность (и, следовательно, время выполнения) этого является потенциальной (добавление одного символа к входу удваивает время выполнения). Подробное описание можно найти здесь: катастрофический откат

Вот некоторые показатели времени выполнения, которые я измерил (которые почти точно удваиваются для каждого добавленного символа):

01
02
03
04
05
06
07
08
09
10
11
12
13
14
0000000000: 0.1ms
00000000000: 0.2ms
000000000000: 0.7ms
0000000000000: 1.3ms
00000000000000: 1.7ms
000000000000000: 3.5ms
0000000000000000: 7.2ms
00000000000000000: 13.9ms
000000000000000000: 27.5ms
0000000000000000000: 55.5ms
00000000000000000000: 113.0ms
000000000000000000000: 226.4ms
0000000000000000000000: 439.1ms
00000000000000000000000: 886.0ms

Небольшое замечание: для таких микро-тестов вам всегда нужно «прогреть» JVM, так как JIT HotSpot в какой-то момент подключится и оптимизирует код. Поэтому первый запуск выглядит так:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
0000000000: 6.8ms
00000000000: 11.8ms
000000000000: 25.5ms
0000000000000: 39.5ms
00000000000000: 6.3ms   <- JIT jumped in and started to translate
000000000000000: 5.4ms     to native code.
0000000000000000: 7.1ms
00000000000000000: 14.2ms
000000000000000000: 26.8ms
0000000000000000000: 54.4ms
00000000000000000000: 109.6ms
000000000000000000000: 222.1ms
0000000000000000000000: 439.2ms
00000000000000000000000: 885.6ms

Итак, что здесь на вынос? Если вы используете серверное приложение или что-то критическое, используемое многими пользователями, не позволяйте им вводить регулярные выражения, если вы действительно им не доверяете. Существуют реализации регулярных выражений, которые обнаруживают эту проблему и отменяют ее, но Java (до JDK 8) этого не делает.

Примечание. Вы можете проверить это с помощью своей локальной среды IDE или небольшой Java-программы, но, пожалуйста, не начинайте выбивать все веб-сайты тестировщиков regex. Эти ребята предоставляют хороший инструмент бесплатно, так что это было бы совершенно несправедливо.

Вот крошечный тест, который я использовал:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Test {
    public static void main(String[] args) {
        for (int runs = 0; runs < 2; runs++) {
            Pattern pattern = Pattern.compile("(0*)*A");
            // Run from 5 to 25 characters
            for (int length = 5; length < 25; length++) {
                // Build input of specified length
                String input = "";
                for (int i = 0; i < length; i++) { input += "0"; }
                
                // Measure the average duration of two calls...
                long start = System.nanoTime();
                for (int i = 0; i < 2; i++) {
                    pattern.matcher(input).find();
                }
                System.out.println(input + ": "
                       + ((System.nanoTime() - start) / 2000000d)
                       + "ms");
            }
        }
    }
}

42
Share: