Count Min Sketch (CMS, Muthukrishnan)

L'algorithme Count Min Sketch a été mis au point par Cormode et Muthukrishnan en 2004. Il est simple, ce qui rend possible son implémentation lors de la prise en main du FPGA.

Il prend en compte un flux d'éléments avec une marque donnée, et un identifiant donné, et donne une évaluation probabiliste de la somme des marques d'éléments reçus d'un même identifiant. Dans le cas de la détection de Syn Flooding, les éléments du flux sont les paquets TCP de type SYN, et l'identifiant pourrait être simplement l'adresse IP destination. La marque serait toujours 1.

Pour faire fonctionner l'algorithme, on choisit une précision ε et une probabilité d'échec δ. On prend alors w = e/ε et d=ln(1/δ).

Les identifiants sont dans l'ensemble {1,2,...,N}. On prends alors w fonctions de hashage aléatoires, uniformes au deuxième ordre et indépendantes qui vont de {1,2,...,N} dans {1,2,...,w}.

On utilise alors un tableau de taille d x w. C'est l'espace mémoire nécessaire pour faire fonctionner l'algorithme. Pour que l'utilisation de cet algorithme ait un sens, il faut que d x w << N. C'est ce qui contraint le choix de ε et δ.

A chaque paquet reçu, on applique chaque fonction de hashage à l'identifiant, et on ajoute dans la case désignée par le couple {numéro de la fonction de hashage, valeur obtenue par hashage de l'identifiant} la marque du paquet.

L'estimation de la somme des marques pour un identifiant donné à un moment donné est la valeur minimum trouvée dans les cases désignées par les couples {numéro de la fonction de hashage, valeur obtenue par hashage de l'identifiant} pour toutes les fonctions de hashage.

Les complexités en temps de cette algorithme, pour l'ajout d'un paquet ou pour l'estimation du poids d'un identifiant, sont en O(ln(1/δ)). La complexité en mémoire est deO(ln(1/δ)/ε).

Il est ensuite possible d'appliquer cet algorithme à la recherche d'objets massifs. Dans notre cas, les objets massifs sont les attaques probables. On considère alors tous les identifiants dans l'estimation du poids à l'instant t est supérieure à une constante multipliée par la somme des poids de tous les identifiants au même instant (la constante est strictement inférieure à 1, elle définit le seuil à partir duquel une alerte est lancée).

La complexité de la recherche d'objets massifs est comparable au simple algorithme CMS. On fait une évaluation du poids total de l'identifiant à la réception de chaque paquet, et on maintient une liste des paquets massifs et la somme totale des marques.

Cet algorithme (recherche d'objets massifs incluse) a été implémenté en C par S. Muthu Muthukrishnan en 743 lignes. Nous ne connaissons pas d'implémentations en Verilog/VHDL.

Le problème de l'inversion du hashage

L'algorithme CMP pose un problème soulevé dans les recherches : est-il possible d'inverser le hashage opéré sur les adresses IP : nous pouvons évaluer le poids d'une adresse IP donnée, mais pouvons-nous par exemple a posteriori chercher dans la table les poids les plus fort, et retrouver leurs adresses IP ?

La réponse est clairement non si nous choisissons les fonctions de hashage au hasard. Cependant des chercheurs dirigés par Robert Schweller [SLC09] ont implémenté sur FPGA un algorithme qui permet cette inversion, en choisissant intelligemment les fonction de hashage et les identifiants (une fonction de l'IP au lieu de l'IP directement) utilisés.

Ceci permet des analyses a posteriori au lieu des analyses incrémentales comme la recherche d'objets massifs. On peut ainsi faire des détections plus poussées, et utiliser moins de mémoire (il n'est plus nécessaire de stocker la liste des objets massifs potentiels à chaque instant par exemple).

Cela nous donne une piste d'amélioration de l'algorithme, même si ce n'est pas nécessaire pour une première implémentation de la détection d'attaques par SYN flooding.

Sources

• Slides de présentation de l'algorithme CMS
•  Code source implémentant l'algoritme

[SLC09]

Robert Schweller, Zhichun Li, Yan Chen, Yan Gao, Ashish Gupta, Yin Zhang, Peter A. Dinda, Ming-Yang Kao, Gokhan Memik. Reversible Sketches: Enabling Monitoring and Analysis Over High-Speed Data Streams. IEEE. 2009.