ПРОЦЕССОР С ПАРАМЕТРИЗОВАННОЙ VLIW-АРХИТЕКТУРОЙ ДЛЯ СОПОСТАВЛЕНИЯ С РЕГУЛЯРНЫМИ ВЫРАЖЕНИЯМИ

Петр Н. Советов

Аннотация


Цель работы заключается в проектировании специализированной процессорной архитектуры для высокопроизводительного сопоставления регулярных выражений (РВ) в составе систем обнаружения вторжений. Исследование базируется на методике совместного проектирования программных и аппаратных средств. Разработка выполнена на основе архитектуры с командным словом сверхбольшой длины, параметры которой согласованы с физической организацией блочной памяти современных программируемых логических интегральных схем. Применяемый подход обеспечивает обработку одного байта входного потока за один такт системной частоты. Реализованы специализированные алгоритмы генерации машинного кода: декомпозиция линейных путей и декомпозиция счетчиков циклов. Данные алгоритмы позволяют транслировать сложные РВ с интервальными квантификаторами в компактные последовательности инструкций, ограниченные параметрами аппаратного обеспечения. Проведен многокритериальный анализ пространства конфигураций системы команд для поиска парето-оптимальных решений по числу параллельных переходов, разрядности счетчиков циклов и объему памяти программ. Тестирование на наборе правил Emerging Threats Open (ET Open), содержащем 7235 сигнатур, подтвердило эффективность архитектуры. Применение предложенных оптимизаций обеспечило сокращение объема памяти программ в 2.3 раза при одновременном увеличении количества успешно скомпилированных РВ на 163 единицы по сравнению с базовым компилятором. Выявлено, что конфигурация с шириной ветвления 5 является предпочтительной для заданного набора правил при использовании 64 слов памяти. Результаты работы могут быть применены в системах обнаружения вторжений. Архитектура HOREC-DSA обеспечивает детерминированную обработку трафика и защиту от атак типа «отказ в обслуживании на регулярных выражениях».

Ключевые слова


системы обнаружения вторжений, регулярные выражения, ПЛИС, VLIW, спецпроцессор, архитектура системы команды

Полный текст:

PDF

Литература


1. Boukebous A.A.E., Fettache M.I., Bendiab G., Shiaeles S. A Comparative Analysis of Snort 3 and Suricata. 2023 IEEE IAS Global Conference on Emerging Technologies (GlobConET), London, United Kingdom. 2023, pp. 1-6. DOI: https://doi.org/10.1109/globconet56651.2023.10150141.

2. Waleed A., Jamali A.F., Masood A. Which open-source ids? Snort, suricata or zeek. Computer Networks. Elsevier. 2022, v. 213, pp. 109-116. DOI: https://doi.org/10.1016/j.comnet.2022.109116.

3. Siddiq M. L., Zhang J., Santos J. C. D. S. 2024. Understanding Regular Expression Denial of Service (ReDoS): Insights from LLM-Generated Regexes and Developer Forums. In Proceedings of the 32nd IEEE/ACM International Conference on Program Comprehension (ICPC '24). Association for Computing Machinery, New York, NY, USA, 190-201. DOI: https://doi.org/10.1145/3643916.3644424.

4. Carloni F., Conficconi D., Moschetto I., Santambrogio M.D. YARB: a Methodology to Characterize Regular Expression Matching on Heterogeneous Systems. 2023 IEEE International Symposium on Circuits and Systems (ISCAS), Monterey, CA, USA. 2023, pp. 1-5. DOI: https://doi.org/10.1109/iscas46773.2023.10181547.

5. Rahimi R., Sadredini E., Stan M., Skadron K. Grapefruit: An Open-Source, Full-Stack, and Customizable Automata Processing on FPGAs. 2020 IEEE 28th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), Fayetteville, AR, USA, 2020, pp. 138-147. DOI: https://doi.org/10.1109/fccm48280.2020.00027.

6. Zhong J., Chen S., Han B. FPGA-CPU architecture accelerated regular expression matching with fast preprocessing. The Computer Journal. Oxford University Press. 2023, v. 66, no. 12, pp. 2928-2947. DOI: https://doi.org/10.1093/comjnl/bxac138.

7. Gong L., Wang C., Xia H., Chen X., Li X., Zhou X. Enabling Fast and Memory-Efficient Acceleration for Pattern Matching Workloads: The Lightweight Automata Processing Engine. IEEE Transactions on Computers, v. 72, no. 4, pp. 1011-1025, 1 April 2023. DOI: https://doi.org/10.1109/tc.2022.3187338.

8. Wen Z., Kong L., Le Glaunec A., Mamouras K., Yang K. 2024. BVAP: Energy and Memory Efficient Automata Processing for Regular Expressions with Bounded Repetitions. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2 (ASPLOS '24), Vol. 2. Association for Computing Machinery, New York, NY, USA, 151-166. DOI: https://doi.org/10.1145/3620665.3640412.

9. Zhong J., Chen S., Yu C. Xav: A High-Performance Regular Expression Matching Engine for Packet Processing. Elsevier BV, 2024. DOI: https://doi.org/10.2139/ssrn.4760269.

10. Lin Z., Zhang X., Liu Q., Cui J. Design of a heterogeneous-based network intrusion detection system and compiler. Applied Sciences. MDPI. 2025, v. 15, no. 9, p. 5012. DOI: https://doi.org/10.3390/app15095012.

11. Carloni F., Conficconi D., Santambrogio M. D. 2024. ALVEARE: a Domain-Specific Framework for Regular Expressions. In Proceedings of the 61st ACM/IEEE Design Automation Conference (DAC '24). Association for Computing Machinery, New York, NY, USA, Article 155, 1-6. DOI: https://doi.org/10.1145/3649329.3657378.

12. Somaini A., Carloni F., Agosta G., Santambrogio M. D., Conficconi D. Combining MLIR dialects with domain-specific architecture for efficient regular expression matching. Proceedings of the 23rd ACM/IEEE international symposium on code generation and optimization. ACM, 2025. Pp. 255-270. DOI: https://doi.org/10.1145/3696443.3708916.

13. Советов, П.Н. HOREC: компилятор специализированных регулярных выражений для проектирования программируемой и ресурсоэффективной аппаратной архитектуры. Труды Института системного программирования РАН. 2025, т. 37, № 4-1, с. 79-96. DOI: https://doi.org/10.15514/ISPRAS-2025-37(4)-5. EDN: JYEGTE.
Sovietov P.N. HOREC: a specialized regular expression compiler for designing programmable and resource-efficient hardware architecture. Proceedings of ISP RAS, 37:4(1) (2025), pp. 79-96. DOI: https://doi.org/10.15514/ISPRAS-2025-37(4)-5. EDN: JYEGTE (in Russian).

14. Sovetov P. N. Development of DSL Compilers for Specialized Processors. Program Comput Soft 47, 541-554 (2021). DOI: https://doi.org/10.1134/s0361768821070082.

15. Proofpoint Emerging Threats Rules. URL:
https://rules.emergingthreats.net/ (accessed: 20.12.2025).




DOI: http://dx.doi.org/10.26583/bit.2026.2.14

Ссылки

  • На текущий момент ссылки отсутствуют.


Лицензия Creative Commons
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.