Skip to Main content Skip to Navigation

Reconnaissance de motifs dynamiques par automates temporisés à mémoire

Abstract : The globalized and increasing use of computers and the Internet have for consequences an always increasing quantity of data and online communications. Some examples of this data can be logs of social networks messages of Internet routers usages. Such communication logs are similar to dynamic graph formalized as link streams. The monitoring and analysis of this kind of systems are quite common, often looking for occurrences of specific communication patterns. For example, a common pattern in Security is the detection of concerted attacks toward a same target, such as a DDOS. One of the problems addressed in this thesis is the creation of a normalized specification language for such patterns in the networks. Not many similar languages exist because they are often specific to some kind of patterns due to performance issues. The other main issues applied during this thesis is the implementation of a prototype tool for the detection of this patterns in real life link streams.The chosen approach is to specify the pattern with a language inspired from the regular expressions : timed expressions with memory layer. This expressions are designed to specifie both timed constraints, to model the dynamism of the networks, and also data from an open environment. An open environment means that the entities specified in the pattern cannot be known in the first place and can also appear and disappear during the evolution of the network. For example, in intrusion detection, the indentities of the oppenents are hidden until the intrusion attempt. Following the example of regular expressions, the Automata theory offer tools to define a recognition principle for the different properties of this patterns. Timed automate is a classic and well studied automate model to specify and recognize timed systems and properties. Furthermore, the different class of memory automata formalizes some recognition principle for properties over infinite alphabets, used to represent patterns over open environment. We designed and formalized the Timed layered memory automate, integrating features of both memory and timed automata models. One of the specific feature of this model is the introduction of layered memory, offering more flexibility to define complex properties. We are proving the equivalence between the automata and specification language through a Kleene like theorem. Thus, we can easily define and compare the properties of our models to the ones from the literature. Our last contribution is the design and implementation of a generic pattern matching algorithm into a prototype tool. It gives us the opportunity to experiment on link streams from real world networks. We experimented by modeling and monitoring intrusion patterns and community detection in a social network.
Document type :
Complete list of metadata
Contributor : Abes Star :  Contact
Submitted on : Wednesday, March 17, 2021 - 6:38:07 PM
Last modification on : Wednesday, April 14, 2021 - 3:38:08 AM


Version validated by the jury (STAR)


  • HAL Id : tel-03172600, version 1


Clément Bertrand. Reconnaissance de motifs dynamiques par automates temporisés à mémoire. Traitement du signal et de l'image [eess.SP]. Université Paris-Saclay, 2020. Français. ⟨NNT : 2020UPASG034⟩. ⟨tel-03172600⟩



Record views


Files downloads