Implémentations logicielle et matérielle de l'algorithme Aho-Corasick pour la détection d'intrusions

Ce travail propose des méthodes et architectures efficaces pour l'implémentation de l'algorithme Aho-Corasick. Cet algorithme peut être utilisé pour la recherche de chaînes de caractères dans un système de détection d'intrusion, tels que Snort, pour les réseaux informatiques. Deux versions sont proposées, une version logicielle et une version matérielle. La première version développe une implémentation logicielle pour des processeurs à usage général. Pour cela, de nouvelles implémentations de l'algorithme tenant compte des ressources mémoire et de l'exécution séquentielle des processeurs ont été proposées. La deuxième version développe de nouvelles architectures de processeurs particularisés pour FPGA. Elles tiennent compte des ressources de calcul disponibles, des ressources mémoire et du potentiel de parallélisation à grain fin offert par le FPGA. De plus, une comparaison avec une version logicielle modifiée est effectuée. Dans les deux cas, les performances et les compromis pour la sélection de différentes structures de données de nœuds en mémoire ont été analysés. Une sélection de paramètres est proposée afin de maximiser la fonction objective de performance qui combine le nombre de cycles, la consommation mémoire et la fréquence d'horloge du système. Les paramètres permettent de déterminer lequel des deux ou des trois types de structures de données de nœuds (selon la version) sera choisi pour chaque nœud d'une machine à états. Lors de la validation, des scénarios de test utilisant des données variées ont été utilisés afin de s'assurer du bon fonctionnement de l'algorithme. De plus, les contenus des règles de Snort 2.9.7 ont été utilisés. La machine à états a été construite avec environ 26×103 chaînes de caractères qui sont toutes extraites de ces règles. La machine à états contient environ 381×103 nœuds. La contribution générale de ce mémoire est de montrer qu'il est possible, à travers l'exploration d'architectures, de sélectionner des paramètres afin d'obtenir un produit mémoire × temps optimal. Pour ce qui est de la version logicielle, la consommation mémoire diminue de 407 Mo à 21 Mo, ce qui correspond à une diminution de mémoire d'environ 20× par rapport au pire cas avec seulement un type de nœud. Pour ce qui est de la version matérielle, la consommation mémoire diminue de 11 Mo à 4 Mo, ce qui résulte en une diminution de mémoire d'environ 3× par rapport à la version logicielle modifiée. Pour ce qui est du débit, il augmente de 300 Mbps pour la version logicielle modifiée à 400 Mbps pour la version matérielle.

Abstract

This work proposes effective methods and architectures for the implementation of the Aho-Corasick algorithm. This algorithm can be used for pattern matching in network-based intrusion detection systems such as Snort. Two versions are proposed, a software version and a hardware version. The first version develops a software implementation in C/C++ for general purpose processors. For this, new implementations of the algorithm, considering the memory resources and the processor's sequential execution, are proposed. The second version develops an architecture in VHDL for a specialized processor on FPGA. For this, new architectures of the algorithm, considering the available computing resources, the memory resources and the inherent parallelism of FPGAs, are proposed. Furthermore, a comparison with a modified software version is performed. For both cases, we analyze the performance and cost trade-off from selecting different data structures of nodes in memory. A selection of parameters is used in order to maximize de performance objective function that combines the cycles count, the memory usage and the system's frequency. The parameters determine which of two or three types of data structures of nodes (depending on the version) is selected for each node of the state machine. For the validation phase, test cases with diverse data are used in order to ensure that the algorithm operates properly. Furthermore, the Snort 2.9.7 rules are used. The state machine was built with around 26×103 patterns which are all extracted from these rules. The state machine is comprised of around 381×103 nodes. The main contribution of this work is to show that it is possible to choose parameters through architecture exploration, to obtain an optimal memory × time product. For the software version, the memory consumption is reduced from 407 MB to 21 MB, which results in a memory improvement of about 20× compared with the single node-type case. For the hardware version, the memory consumption is reduced from 11 MB to 4 MB, which results in a memory improvement of about 3× compared with the modified software version. For the throughput, it increases from 300 Mbps with the modified software version to 400 Mbps with the hardware version.