Application de l'algorithme de Max-hashing pour le référencement de fichiers vidéo et la détection de contenus et de flux connus à haute vitesse sur GPU

Le nombre croissant d'utilisateurs d'Internet et le développement de la technologie des communications s'accompagnent par l'émergence de comportements illégaux sur le réseau. Notons par exemple le partage de fichiers protégés par le droit d'auteur, comme des films ou de la musique, mais aussi le trafic d'images et de films à contenu pédo-pornographique illégal lui aussi. Il se forme alors le besoin de pouvoir efficacement cibler et détecter le transfert de ces fichiers connus sur un lien réseau. Le fonctionnement des communications sur le réseau Internet présente de multiples problématiques. Les fichiers sont segmentés en paquets et ceux-ci empruntent des routes possiblement indépendantes pour atteindre la même destination. D'autre part, ces paquets suspicieux peuvent être noyés dans les flux de données (légaux) de millions d'autres utilisateurs rendant donc la reconstitution du fichier original depuis les paquets observés très improbable. Dans ce cas, on peut considérer que deux paquets successifs sont indépendants. Nous sommes donc contraints de travailler au niveau des paquets et, pris individuellement les uns des autres, il nous faudrait déterminer avec le maximum de certitude si ceux-ci contiennent un segment de fichier connu ou si ils appartiennent à un flux de paquets connu. Enfin, les grands réseaux utilisant des liens à 10, 40 voire 100 Gb/s, ces détections doivent pouvoir être appliquées sur des millions de paquets par seconde. On peut simplement déterminer le flux auquel appartient un paquet en se basant sur les données de son entête. Le processus se complique lorsque l'on cherche à analyser le contenu des paquets. On est alors face à une grande quantité de données, très segmentée, dans laquelle on cherche des correspondances à des schémas (ou règles) connu(e)s. Dans ce domaine particulier, les expressions régulières sont très utilisées notamment grâce à leur versatilité. On note en revanche que les performances de celles-ci se dégradent avec le nombre de règles qu'on leur soumet. Les fonctions de hachage n'ont généralement pas ce désavantage puisque le temps d'accès à un élément d'une table est constant quelque soit l'état de remplissage de cette dernière. Elles ont, d'autre part, l'avantage de générer des empreintes de taille fixe à partir desquelles on ne peut pas reconstituer le fichier original (injectivité). Nous avons choisis de baser notre système sur l'algorithme de max-Hashing du fait de sa capacité à pouvoir détecter des segments de fichiers. Cette caractéristique n'est, en effet, pas partagée par tous les algorithmes de hachage et est cruciale dans le contexte que nous visons : la détection de fragments de fichiers connus, préalablement référencés, contenus dans des paquets réseau. Le référencement de fichiers informatiques avec l'algorithme de max-Hashing natif, ou ``brut'', a tendance à générer des empreintes peu originales : celles-ci peuvent être retrouvées lors du référencement d'autres fichiers (différents) ou, pire, lors de l'analyse de paquets transportant des données inconnues. On parlera de redondances lors du référencement et de faux-positifs lors de la détection. Ces cas de figure sont particulièrement courants avec des fichiers de même format. Le formatage introduit en général des champs de données qui peuvent se retrouver très similairement voire identiquement d'un fichier à l'autre.