La mémoire Trie
Lors de la présentation du projet, Sylvain Gombault nous a présenté le projet VTHD++, qui avait pour but de faire du contrôle d'accès réseau en minimisant l'impact sur la QoS. En particulier tous les paquets devaient être traités avec le même délai, et le nombre de règles définies ne doit pas modifier ce délai.
Pour mettre en œuvre le contrôle d'accès, un ensemble de règles est appliqué consécutivement à chaque paquet en fonction du quadruplet {adresse IP source, port source, adresse IP destination, port destination}.
Pour rendre le temps de traitement indépendant du nombre de règles et du type de paquet, le principe de la mémoire trie (de l'Anglais reTRIEve, récupérer) a été utilisé : un arbre orienté est généré à partir des règles de sécurité, et l'orientation dans cet arbre se fait en lisant un à un chaque octet du quadruplet {adresse IP source, port source, adresse IP destination, port destination}. A chaque descente d'un cran, on arrive soit sur un noeud et on lit la suite, soit sur une feuille qui donne une action à faire (transmettre, jeter, sauvegarder le paquet).
Cet arbre orienté sert ensuite à générer une structure mémoire : il s'agit d'un tableau ayant en abscisses toutes les valeurs possibles d'un octet (les octets du quadruplet), et en ordonnées des numéros de règle. Ce tableau est en mémoire dans le FPGA qui le lit à chaque réception de paquet.
| Valeur de l'octet | 12 | 22 | 172 | 181 | 200 | 202 | 203 |
| Règle 1 | 1)→4 | →6 | |||||
| Règle 2 | →5 | ||||||
| Règle 3 | forward | →8 | |||||
| Règle 4 | 2)→7 | drop | |||||
| Règle 5 | →2 | store | |||||
| Règle 6 | forward | →1 | |||||
| Règle 7 | 3)drop | ||||||
| Règle 8 | →7 | store | |||||
Tableau 2: Exemple d'application de la mémoire trie sur l'IP 172.22.203.200
Prenons l'exemple de la mémoire trie ci-dessus et d'un paquet provenant de l'IP 172.22.203.200. On ne prend en compte dans cet exemple que l'IP source, et pas le quadruplet. La mémoire n'est pas complètement représentée pour ne pas surcharger le tableau :
- il commence à la règle 1 avec le premier octet 172 de l'adresse IP source, ce qui lui donne le numéro de règle suivant 4 ;
- il lit la règle 4 avec le second octet de l'adresse IP source 22, ce qui lui donne le numéro de règle suivant 7 ;
- il lit la règle 7 avec les troisième octet de l'adresse IP source 203, ce qui lui donne l'ordre « drop ». Il jette alors le paquet.
Le défaut de cette technique est l'espace mémoire nécessaire, qui est important. Lors du projet VTHD++, elle a cependant été implémentée sur un FPGA et pouvait fonctionner avec un débit allant jusqu'à 6,6Gb/s. Des améliorations sont possibles en traitant en parallèle plusieurs paquets par exemple.
La mémoire trie pourra nous être utile si nous cherchons à traiter les paquets par règles, car elle est très efficace à implémenter sur un FPGA et s'adapte bien à un filtrage par IP. Elle n'est pas nécessaire pour la simple détection d'attaques par SYN flooding, mais pourrait permettre de généraliser cette détection. Nous pourrions en effet créer un système générique de règles qui permettrait de compter certains types de paquets, puis de couper au-dessus d'un certain seuil. Une règle pourrait ainsi être écrite pour détecter le SYN flooding, et d'autres menaces pourraient être détectées de la même façon.
Liens
- Wikipédia. Trie. http://en.wikipedia.org/wiki/Trie
