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.

Abstract

The increasing number of Internet users and the development in communication technology are followed by the emergence of illegal behaviours on the network. For instance, we can mention the sharing of files that are protected by copyrights, such as films or music, and additionally the traffic of illegal images and video-clips related to child-pornography. There is, therefore, a need for a system that can efficiently detect the transfer of known illegal files over the Internet.Such a system is not trivial: the protocols used on the networks imply some difficulties. Files are fragmented into packets and these may follow different path through the network to eventually reach the same destination. Moreover, the suspicious packets may get mixed with legit data streams coming from millions of other users. Hence, the reconstruction of the original file from the packets we can capture from a node is very unlikely. In this case, we have to consider that two successive packets are independent. Focusing on each packet individually and yet with the maximum certainty, we must be able to determine whether or not this packet contains parts of a known file or belongs to a known packet flow. Finally, as the technology used in large networks, such as Internet Service Providers (ISP) or Internet backbones, reaches 10, 40 and 100 Gbps bandwidths, the ability for our system to treat such bandwidth is mandatory. One can simply determine the flow to which a packet belongs from the data embedded in its header. The process usually becomes much more complicated when trying to analyze the content of a packet. Then, we face large amount of data, very segmented, in which we try to locate the parts that match given patterns (or rules). Regular expressions are widely used for such problems thanks to their versatility but, on the other hand, their performances are bound to the number of patterns (rules) they try to locate: the more you add rules the less you can expect good performance from the system. Hashing methods usually do not have this disadvantage since the time to access an item in a hash-table is constant regardless of the its filling. Furthermore, they have the advantage of generating fixed size footprints from which we cannot reconstruct the original file (due to their injectivity property). We chose to base our system on the Max-Hashing algorithm due to its ability to detect segments of known files. This feature is not common to all hashing algorithms and is crucial for the purpose we seek: the detection of fragments of known files, previously referenced, contained in the payload of network packets. Basically referencing computer files with the max-Hashing algorithm leads to the generation of non-original fingerprints. These may be generated again while referencing other files (we call them redundancies) or, worse, while analyzing packet carrying unknown ones (we will call them false-positives). This kind of event can become particularly common when dealing with files that have the same format. Indeed, formatting introduces fields of data and flags that can be found in various files with little or no difference at all. By extension, some fields are more original : the kind of segment of data that is very unlikely to find in any other file. These segments give many information on the identity of the file from which they were extracted. We therefore call them ``high-entropy'' segments. Thus, we propose a method for the extraction of ``high-entropy'' segments in video files using the MP4 format and the H.264 encoder (the most used). Once located, we can focus on these zones in order to generate original fingerprints.