Каков наилучший подход для обработки большого количества пользовательских регулярных выражений

Question

У меня есть система, которая анализирует поток данных и на основе подписки многих пользователей ей необходимо ее отфильтровать. Однако эти фильтры могут содержать регулярные выражения, и мне нужно сделать их достаточно безопасными, чтобы злоумышленники не могли вставлять регулярные выражения, которые целенаправленно дорогостоящие CPU, чтобы уничтожить службу.

Я интересно, что лучший подход должен быть,

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

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

Есть ли лучший способ справиться с этим? Должен ли я тестировать регулярные выражения с использованием некоторых тестовых данных после создания подписки? Или, может быть, использовать отдельную очередь для каждого пользователя, который разбирается в другом потоке?

Кроме того, подходит другой подход, который приходит мне на голову, собирает статистику о том, сколько процессорного времени занимает каждый фильтр, и отключите их, которые слишком много едят, но на самом деле не справляются с «очень плохими» регулярными выражениями, которые могут нужно минут процессорного времени, чтобы закончить

Если кто-то интересно, я пишу это в C#, но этот вопрос является довольно общим и может применяться к любому языку

Answer 1

Поскольку вы используете C#, вам не нужно откручивать новый поток. Конструктор Regex имеет overload, что позволяет установить тайм-аут . Если регулярное выражение занимает слишком много времени, оно прерывается и бросает RegexMatchTimeoutException.

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

Другое дело, что было бы полезно сделать, если регулярные выражения больше, чем одноразовые использования, равны компиляции регулярных выражений. Регулярные выражения в C# поддерживают предварительную компиляцию для ускорения будущих матчей.

Answer 2

Если вы готовы реализовать свой собственный движок регулярных выражений (или найти библиотеку), используйте метод построения NFA Томпсона и ограничьте количество состояний в каждом автомате (или, для лучшего понимания пользователем, длину регулярного выражения, которое сильно коррелировано). Производительность алгоритмов сопоставления гораздо более предсказуема, чем алгоритмы обратного отслеживания.

Answer 3

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

• Пользователь хочет добавить фильтр X с регулярным выражением.
• Приложение должно запускать этот фильтр по предопределенному набору данных.
• Если этот пробег занимает более Y миллисекунд, не позволяйте его добавлять.
• Пользователям с более высоким рейтингом (платный сервис, лояльным пользователям, ...) могут быть разрешены более агрессивные фильтры (более миллисекунды обработки).

Answer 4

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

Таким образом, у вас нет накладных расходов на запуск новых потоков все время, но они все равно могут убивать те, которые занимают слишком много времени.