Constructing deterministic finite automata by reconfigurable means for solving information security tasks

Ukrainian Information Security Research Journal

View Publication Info
 
 
Field Value
 
Title Constructing deterministic finite automata by reconfigurable means for solving information security tasks
Построение конечных автоматов реконфигурируемыми средствами для решения задач информационной безопасности
Побудова скінченних автоматів реконфігуровними засобами для вирішення задач інформаційної безпеки
 
Creator Гільгурт, Сергій Якович; Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
 
Subject Information Security
information security; multi-pattern string matching; FPGA; finite automaton; Aho-Corasick algorithm; efficiency
UDC 004.274:004.056
Информационная безопасность
защита информации; сигнатурный анализ; ПЛИС; конечный автомат; алгоритм Ахо-Корасик; эффективность
УДК 004.274:004.056
Інформаційна безпека
захист інформації; сигнатурний аналіз; ПЛІС; скінченний автомат; алгоритм Ахо-Корасік; ефективність
УДК 004.274:004.056
 
Description Computer security requires the implementation of different measures - organizational, technical, cryptographic, etc. Network intrusion detection systems, antiviruses and other similar tools of technical protection based on signatures should solve in real time the computationally complex multi-pattern string matching task, which is a specific type of string matching functionality performed in DPI systems to search an input stream for a set of patterns rather than a single pattern. Due to rising traffic rates, increasing number and sophistication of attacks and the collapse of Moore's law for sequential processing, traditional software solutions can no longer meet the high requirements of today’s security challenges. Therefore, hardware approaches are proposed to accelerate pattern matching. Combining the flexibility of software and the near-ASIC performance, reconfigurable hardware devices based on Field Programmable Gate Arrays (FPGA) have become increasingly popular for this purpose. There are three main approaches to fulfill the computation-intensive multi-pattern string matching task using FPGA. The techniques of these approaches are: content addressable memory, Bloom filter and Aho-Corasick Algorithm. Each approach has its advantages and disadvantages. Effective construction of more and more complex signature-based tools of technical secure protection is impossible without a comprehensive analysis of the properties and specific features of every approach. In this study, in order to improve the efficiency of information security tools created on the basis of the FPGA, the main features of the third of the listed approaches are analyzed. Based on the analysis of the stateof-the-art finite automata realizing Aho-Corasick algorithm, the specialty of their implementation on FPGAs, encountering problems and ways to solve them are also investigated.
Противодействие угрозам информационной безопасности требует осуществления мероприятий различного плана – организационных, технических, криптографических и др. Сетевые системы обнаружения вторжений, антивирусы и прочие подобные средства технической защиты, работа которых основана на использовании сигнатур, должны решать в реальном времени вычислительно сложную задачу множественного распознавания строк, которая в отличие от одиночного распознавания подразумевает одновременный поиск во входных данных большого количества образцов. Программные решения уже не справляются с этой проблемой в связи с устойчивым ростом объема сетевого трафика, количества и сложности атак. Поэтому все большее распространение получают аппаратные решения с использованием реконфигурируемых устройств на базе ПЛИС типа FPGA, которые сочетают в себе близкую к аппаратной производитель-ность с гибкостью программного обеспечения. На сегодня наиболее распространены три подхода к построению аппаратных схем множественного распознавания, работа которых основана на использовании: ассоциативной памяти, фильтра Блума и конечных автоматов. Каждый из подходов имеет свои преимущества и недостатки. Эффективное построение все более сложных сигнатурных средств технической защиты информации, которые бы отвечали требованиям оптимального функционирования в зависимости от внешних условий, невозможно без всестороннего анализа свойств и специфических черт каждого из подходов. В этом исследовании с целью повышения эффективности создаваемых на базе ПЛИС средств информационной безопасности проанализированы преимущества и недостатки третьего из перечисленных подходов. На основе анализа мирового опыта использования конечных автоматов также исследованы особенности их реализации на ПЛИС, возникающие проблемы и пути их решения.
Протидія загрозам інформаційної безпеки потребує вживання заходів різного плану – організаційних, технічних, криптографічних тощо. Мережеві системи виявлення вторгнень, антивіруси, та інші засоби технічного захисту, робота яких заснована на використанні сигнатур, мають вирішувати в реальному часі обчислювально складну задачу множинного розпізнавання рядків, яка на відміну від одиночного розпізнавання має метою одночасний пошук у вхідних даних великої кількості зразків. Програмні рішення вже не впорюються з цією проблемою через сталий зріст об’єму мережевого трафіку, кількості та складності атак. Тому все більшого поширення набувають апаратні рішення з використанням реконфігуровних пристроїв на базі ПЛІС типу FPGA, які поєднують в собі близьку до апаратної продуктивність із гнучкістю програмного забезпечення. На сьогодні найбільш поширеними є три підходи щодо побудови апаратних схем множинного розпізнавання, робота яких заснована на використанні: асоціативної пам’яті, фільтра Блума та скінченних автоматів. Кожен с підходів має свої власні переваги та вади. Ефективна побудова все більш складних сигнатурних засобів технічного захисту інформації, яки б відповідали вимогам оптимального функціонування в залежності від зовнішніх умов, неможлива без всебічному аналізу властивостей та специфічних рис кожного з підходів. У цьому дослідженні з метою підвищення ефективності створюваних на базі ПЛІС засобів захисту інформації проаналізовані переваги та недоліки третього з перелічених підходів. На основі аналізу світового досвіду використання скінченних автоматів також досліджені особливості їх реалізації на ПЛІС, проблеми, що виникають, та шляхи їх вирішення
 
Publisher National Aviation University
 
Contributor


 
Date 2019-06-27
 
Type


 
Format application/pdf
application/pdf
application/pdf
 
Identifier http://jrnl.nau.edu.ua/index.php/ZI/article/view/13768
10.18372/2410-7840.21.13768
 
Source Ukrainian Information Security Research Journal; Том 21, № 2 (2019); 111-120
Защита информации; Том 21, № 2 (2019); 111-120
Захист інформації; Том 21, № 2 (2019); 111-120
 
Language uk
 
Rights Authors who publish with this journal agree to the following terms: Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
Авторы, публикующие в данном журнале, соглашаются со следующим: Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным сохранением ссылок на авторов оригинальной работы и оригинальную публикацию в этом журнале.Авторы сохраняют право заключать отдельные контрактные договоронности, касающиеся не-эксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге), со ссылкой на ее оригинальную публикацию в этом журнале.Авторы имеют право размещать их работу в сети Интернет (например в институтском хранилище или персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу (См. The Effect of Open Access).
Автори, які публікуються у цьому журналі, погоджуються з наступними умовами: Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).
 

Contact Us

The PKP Index is an initiative of the Public Knowledge Project.

For PKP Publishing Services please use the PKP|PS contact form.

For support with PKP software we encourage users to consult our wiki for documentation and search our support forums.

For any other correspondence feel free to contact us using the PKP contact form.

Find Us

Twitter

Copyright © 2015-2018 Simon Fraser University Library