La décomposition modulaire apparait naturellement dans différents domaines de la combinatoire (et en particulier les graphes). Cette décomposition se révèle être un puissant outil de description d'objets discrets. Elle est aussi utilisée comme étape préliminaire à nombreux d'algorithmes.<br /><br />Dans ce mémoire, nous nous intéressons au calcul de la décomposition modulaire. Malgré la publication d'algorithmes linéaires au milieu des années 90, la recherche sur ce problème n'a pas cessée. Nous faisons le point sur les différentes avancées et techniques utilisées.

PIGA est un outil permettant de détecter les comportements malicieux par analyse de trace système. Pour cela, il utilise des signatures représentant les comportements violant une ou plusieurs propriétés de sécurité définies dans la politique. Les signatures sont générées à partir de graphes modélisant les opérations entre les différentes entités du système et sont stockées en mémoire pendant la détection d’intrusion. Cette base de signatures peut atteindre une taille de plusieurs Mo et ainsi réduire les performances du système lorsque la détection d’intrusion est active. Durant cette thèse, nous avons mis en place plusieurs méthodes pour réduire la mémoire nécessaire pour stocker les signatures, tout en préservant leur qualité. La première méthode présentée est basée sur la décomposition modulaire des graphes. Nous avons utilisé cet outil de la théorie des graphes pour réduire la taille du graphe et, ainsi, diminuer le nombre de signatures, ainsi que leur longueur. Appliquée à des propriétés de confidentialité sur un système servant de passerelle, cette méthode divise par 20 le nombre de signatures générées. La seconde méthode réduit directement la base de signatures en supprimant des signatures inutiles lorsque PIGA est en mode IPS. Appliquée sur les mêmes propriétés, cette méthode divise par 5 le nombre de signatures générées. En utilisant les deux méthodes, on divise le nombre de signatures par plus de 50. Ensuite, nous avons adapté le mécanisme de détection afin d’utiliser les nouvelles signatures générées. Les expérimentations que nous avons effectuées montrent que notre système est équivalent à l’ancien système. De plus, nous avons réduit le temps de réponse de PIGA. / PIGA is a tool for detecting malicious behaviour by analysing system activity. This tool uses signatures representing illegal behaviours that violate security properties defined in the policy. The signatures are generated from graphs modelling the operation between different system entities and stored in the memory during the intrusion detection. The signature base can take up several MB (Megabytes). This will reduce system performance when the intrusion detection is running. During this thesis, we set up two methods to reduce the memory used to store the signatures while also preserving their quality. The first method is based on the modular decomposition of graphs. We used this notion of graph theory to reduce the size of the graph and lower the number and length of signatures. Applied to confidentiality properties on a gateway system, this method divides by 20 the number of generated signature. The second method reduces directly the signature base by deleting useless signatures when PIGA is used as an IPS. Applied to the same properties, this method divides by 5 the number of generated signatures. Using both methods together, the number of signatures is divided by more than 50. Next, we adapted the detection mechanism to use the new generated signatures. The experiments show that the new mechanism detects the same illegal behaviours detected by the previous one. Furthermore, we reduced the response time of PIGA.