Как отключить backtracking в sed

Question

Мне интересно, как использовать регулярные выражения атомных групп (non-capturing group) в sed. Атомные группы очень полезны, чтобы избежать атак с отказами в обслуживании, поглощая память серверов, так называемое катастрофическое обратное отслеживание, а также массивные мусорные атомные группы очень полезны.

Обнаружили следующую ссылку, чтобы отключить обратный отсчет с помощью re2 engine.

Вы можете полностью отключить отключение с помощью двигателя re2 (двигатель без обратного слежения). Мой вопрос заключается в том, почему мы не можем использовать один и тот же подход в sed, если возможно, как мы можем определить группу атомов или группу без захвата в sed.

Thanks

Answer 1

Вы задаете несколько вопросов. Ответ на один: appeared before in SO. Несущие парсеры не предоставляются sed.

Чтобы ответить на другой вопрос, вам нужно только внимательно ознакомиться с документацией re2. Механизм, используемый разветвителями-ответвлениями, такими как sed (а также Perl, Python, Java и т. Д.), И матрицы с детерминированным конечным автоматом (DFA), такие как re2, по сути, различны. Операция cut не работает в распознавателе sed, который будет делать то, что вы хотите.

Сказав это, документация re2 опускает свои негативы. Компиляция DFA гораздо более эффективна, чем преобразование регулярного выражения в байт-код, используемый внутри, например, Perl. Таким образом, программы Perl не замедляются компиляцией регулярных выражений. На самом деле компилятор re2 может «взорваться» на некоторых коротких регулярных выражениях и производить DFA размера экспоненциального размера в регулярном выражении. Таким образом, компилятор занимает экспоненциальное время для запуска, а метод re2 перемещает плохое поведение из среды выполнения в компиляцию.

Я согласен с ребятами re2, что в целом гораздо лучше иметь неправильное поведение, зависящее от регулярного выражения, чем вход. Это был бы лучший, безопасный мир, если бы все встроенные распознаватели regex в языках программирования использовали подход re2.

И, наконец, ваши вопросы, похоже, ограничивают размер и время выполнения. DOS из распознавателя обратного отслеживания возникает, потому что некоторые короткие входы требуют экспоненциального времени во входной длине для распознавания (или отклонения). Поскольку регулярное выражение никогда не может захватывать больше (короткой) длины ввода, захват или отсутствие захвата не влияет.

Другой тип DOS, о котором вы можете подумать, - это пользователь, предоставляющий вход монстра, который распознаватель sed вынужден хранить внутри, потому что он имеет только группы без захвата, даже если захват никогда не используется. Это, безусловно, способ сделать проблему, по крайней мере, для некоторых реализаций sed (гипотетическая интеллектуальная реализация может определить, что захват не нужен и пропустить его, я не думаю, что это делает код GNU), но это происходит только тогда, когда вы допускаете огромные входы, которые обычно можно предотвратить другими способами. Почему в группе sed нет групп, не связанных с захватом? Это исторически очень старая программа, восходящая к некоторым из первых машин Unix. В те дни люди не беспокоились о DOS.

Answer 2

Вы можете избежать обратного отслеживания с помощью якорей и быть более многословным в почти всех двигателях регулярных выражений. Кроме того, группы захвата и не захвата имеют очень небольшую разницу в своих накладных расходах, все они просто сохраняют начальные и конечные смещения внутри ввода.Захватывающие группы имеют недостаток в загрязнении пространства имен back-reference.