К основному контенту

Catastrophic backtracking в регулярных выражениях

Можно ли простой и вроде невинной регуляркой убить систему? Да, можно.

Например:

>>> r = '(a+)*b'

Просто — да. Невинно — вроде да. Конечно неумно, потому что скобки и звездочка лишние, но должно работать. Попробуем:

>>> re.findall('(a+)*b', 'aaaaaab')
['aaaaaa']

Круто, работает, пошли пить пиво.

А нет…

Если строка, в которой ищем, не будет содержать искомого паттерна, например просто 'aaaaaa', компилятор будет пробовать найти её следующим алгоритмом:

1. Вся стока удовлетворяет 'a+', но мы не находим 'b', шаг назад.
2. Теперь 'a+' удовлетворяет только 'aaaaa' (все, кроме последней), последняя удовлетворяет повтору '*', 'b' все равно не находим, шаг назад.
3. Первое 'a+' удовлетворяет только 'aaaa', последние два 'aa' удовлетворяют повтору '*', 'b' все равно не находим, шаг назад.
4. Первое 'a+' удовлетворяет 'aaaa', предпоследняя 'a' удовлетворяет одному повтору '*', следующая 'a' еще одному повтору '*', 'b' так и не находиться…

Ну Вы поняли — и так далее. Вплоть до полного перебора строки.

Немного статистики:
>>> timeit.timeit("import re; re.findall('(a+)*n', 'a'*20)", number=1)
0.24741506576538086
>>> timeit.timeit("import re; re.findall('(a+)*n', 'a'*22)", number=1)
0.99283289909362793
>>> timeit.timeit("import re; re.findall('(a+)*n', 'a'*24)", number=1)
3.9849259853363037

Как видим, время исполнения растет экспоненциально. Для бОльших строк Python 2.6 на FreeBSD своевременно выкидывает RuntimeError, но на Windows тот самый Python бодренько перебирает все комбинации. Строки больше 30 символов не рискнул тестировать :)

Оригинал статьи можно найти тут

Комментарии

Отправить комментарий

Популярные сообщения из этого блога

Dispose pattern to file reading in C#:

This is how to implement dispose pattern to file reading in C#: using System; using System.IO; class BaseResource: IDisposable { // Track whether Dispose has been called. private bool disposed = false; // The unmanaged resource wrapper object private FileStream file; // Class constructor public BaseResource(String fileName) { Console.WriteLine("BaseResource constructor allocates unmanaged resource wrapper"); file = new FileStream(fileName, FileMode.Open, FileAccess.Read, FileShare.Read); } // Implement IDisposable public void Dispose() { // Check to see if Dispose has already been called. if (!disposed) { Console.WriteLine("Dispose pattern releases unmanaged resource wrapper's resource"); file.Close(); disposed = true; } } public void Close() { Dispose(); } public void DoS...
Отправить комментарий
Далее...

10 Interviewing Rules

By Carole Martin, Monster Contributing Writer ----- In the current job market, you'd better have your act together, or you won't stand a chance against the competition. Check yourself on these 10 basic points before you go on that all-important interview. Look Sharp Before the interview, select your outfit. Depending on the industry and position, get out your best duds and check them over for spots and wrinkles. Even if the company has a casual environment, you don't want to look like you slept in your clothes. Above all, dress for confidence. If you feel good, others will respond to you accordingly. Be on Time Never arrive late to an interview. Allow extra time to arrive early in the vicinity, allowing for factors like getting lost. Enter the building 10 to 15 minutes before the interview. Do Your Research Researching the company before the interview and learning as much as possible about its services, products, customers and competition will give you an edge in understand...
Отправить комментарий
Далее...