Аннотация:
Разработка программируемых и ресурсоэффективных аппаратных ускорителей для поиска по регулярным выражениям представляет собой актуальное направление в области сетевой безопасности, где критически важны высокая пропускная способность потоковой обработки данных и устойчивость к атакам типа ReDoS (Regular Expression Denial of Service). В настоящей работе представлен компилятор HOREC, применяемый в цикле высокоуровневого проектирования программируемого аппаратного ускорителя. В HOREC используется новое расширение детерминированного конечного автомата, позволяющее компактно описывать интервальные квантификаторы с большим числом повторений, типичные для правил в системах обнаружения вторжений. Рассмотрены алгоритмы, сокращающие число переходов в командах и уменьшающие общее число команд. Представлена программная модель ускорителя на основе интерпретатора сопоставления с скомпилированным образцом и задан набор параметров для поиска в пространстве архитектурных вариантов аппаратного ускорителя, в том числе: объем доступной памяти, формат команд и режимы сопоставления символов. Экспериментальное исследование проведено для 7234 регулярных выражений, извлеченных из правил ET OPEN. Результаты оценки демонстрируют высокую ресурсоэффективность предлагаемого решения: в память объемом 64K команд удалось разместить до 7000 выражений. При этом в 60% случаев число переходов на команду не превышает 4, а наличие глобальной таблицы множеств символов для 256 часто встречающихся элементов позволяет ограничить объем памяти локальной таблицы всего 10 множествами символов на программу.
Представленные результаты подтверждают применимость HOREC для аппаратной реализации поиска по РВ в задачах сетевой безопасности и показывают перспективность предложенного подхода для высокоуровневого проектирования ускорителей с низкими аппаратными затратами.
Полный текст:
PDF файл (1447 kB)