La modélisation des événements et de leurs propriétés temporelles concerne des types variés d’utilisateurs et de communautés scientifiques. Nous nous plaçons dans le cadre du paradigme Objet et construisons un méta modèle opérationnel servant de représentation pivot, indépendante du métier pour représenter des événements composites avec leurs propriétés structurelles et temporelles. Le méta modèle PTOM (Periodic Temporal Occurrence Metamodel) prend en compte l’expression de contraintes structurelles sur les événements, ou géométriques, topologiques et relationnelles sur la temporalité de leurs occurrences. Il privilégie la représentation en intension (vs extension) des occurrences d’événements périodiques. PTOM étend la norme ISO 19108 et s’adapte aux standards EventsML G2 et iCalendar. Sur un plan théorique, nous étendons les algèbres d’intervalles d’ALLEN et de LIGOZAT, et proposons un système de relations topologiques entre intervalles non convexes (ALLEN*) dont nous étudions les propriétés. Ces résultats sont intégrés dans PTOM. La première application de PTOM est la spécification de la sémantique du calendrier grégorien. Les éléments calendaires sont réintroduits en tant qu’événements périodiques dans PTOM, ce qui renforce son pouvoir expressif. PTOM a été mis en œuvre lors d’un projet ANR sur des corpus d’événements journalistiques (agences de presse) concernant les loisirs et la culture. L’Ingénierie Dirigée par les Modèles a été utilisée pour la conception et l’exploitation de PTOM. Cela permet de gérer la complexité, d’assurer la maintenabilité et la cohérence de l’ensemble et enfin, de générer automatiquement des interfaces pour les pourvoyeurs ou utilisateurs de données. / Modelling events with their temporal properties concerns many users and scientific communities. We adopted the Object paradigm and designed an operational metamodel which stands as a pivot business independent representation for composite events accompanied with their structural and temporal properties. PTOM metamodel (Periodic Temporal Occurrence Metamodel) accounts for structural constraints upon events and geometric, topologic or relational constraints upon their temporal occurrences. It gives prominence to intensional representations of periodic events occurrences vs extensional ones. PTOM extends ISO 19108 standard and fits EventsML G2 and iCalendar. From a theoretical viewpoint, we extend ALLEN’s and LIGOZAT’s interval algebras and propose a special set of topological relations between non convexintervals (ALLEN*), and study its properties. These results are part of PTOM. The first application of PTOM results in a specification of the Gregorian calendar semantics. Calendar elements are reinserted as periodic events in PTOM thus enhancing its expressiveness. PTOM was also experimented upon a corpus of journalistic (press agencies) events dedicated to leisure and culture at the occasion of an ANR project. Model Driven Engineering was extensively used for PTOM design and use.It allows to manage complexity and to ensure maintainability, consistency and eventually can automatically generate data provider or end user interfaces as well.

La modélisation des événements et de leurs propriétés temporelles concerne des types variés d'utilisateurs et de communautés scientifiques. Nous nous plaçons dans le cadre du paradigme Objet et construisons un méta modèle opérationnel servant de représentation pivot, indépendante du métier pour représenter des événements composites avec leurs propriétés structurelles et temporelles. Le méta modèle PTOM (Periodic Temporal Occurrence Metamodel) prend en compte l'expression de contraintes structurelles sur les événements, ou géométriques, topologiques et relationnelles sur la temporalité de leurs occurrences. Il privilégie la représentation en intension (vs extension) des occurrences d'événements périodiques. PTOM étend la norme ISO 19108 et s'adapte aux standards EventsML G2 et iCalendar. Sur un plan théorique, nous étendons les algèbres d'intervalles d'ALLEN et de LIGOZAT, et proposons un système de relations topologiques entre intervalles non convexes (ALLEN*) dont nous étudions les propriétés. Ces résultats sont intégrés dans PTOM. La première application de PTOM est la spécification de la sémantique du calendrier grégorien. Les éléments calendaires sont réintroduits en tant qu'événements périodiques dans PTOM, ce qui renforce son pouvoir expressif. PTOM a été mis en œuvre lors d'un projet ANR sur des corpus d'événements journalistiques (agences de presse) concernant les loisirs et la culture. L'Ingénierie Dirigée par les Modèles a été utilisée pour la conception et l'exploitation de PTOM. Cela permet de gérer la complexité, d'assurer la maintenabilité et la cohérence de l'ensemble et enfin, de générer automatiquement des interfaces pour les pourvoyeurs ou utilisateurs de données.

La criticité des programmes dépasse constamment de nouvelles frontières car ils sont de plus en plus utilisés dans la prise de décision (voitures autonomes, robots chirurgiens, etc.). Le besoin de développer des programmes sûrs et de vérifier les programmes existants émerge donc naturellement.Pour prouver formellement la correction d'un programme, il faut faire face aux défis de la mise à l'échelle et de la décidabilité. Programmes composés de millions de lignes de code, complexité de l'algorithme, concurrence, et même de simples expressions polynomiales font partis des problèmes que la vérification formelle doit savoir gérer. Pour y arriver, les méthodes formelles travaillent sur des abstractions des états des programmes étudiés afin d'analyser des approximations de leur comportement. L'analyse des boucles est un axe entier de la vérification formelle car elles sont encore aujourd'hui peu comprises. Bien que certaines d'entre elles peuvent facilement être traitées, il existe des exemples apparemment très simples mais dont le comportement n'a encore aujourd'hui pas été résolu (par exemple, on ne sait toujours pas pourquoi la suite de Syracuse, simple boucle linéaire, converge toujours vers 1).L'approche la plus commune pour gérer les boucles est l'utilisation d'invariants de boucle, c'est à dire de relations sur les variables manipulées par une boucle qui sont vraies à chaque fois que la boucle recommence. En général, les invariants utilisent les mêmes expressions que celles utilisées dans la boucle : si elle manipule explicitement la mémoire par exemple, on s'attend à utiliser des invariants portant sur la mémoire. Cependant, il existe des boucles contenant uniquement des affectations linéaires qui n'admettent pas d'invariants linéaires, mais polynomiaux.Les boucles linéaires sont elles plus expressives que ce qu'il paraîtrait ?Cette thèse présente de nouvelles propriétés sur les boucles linéaires et polynomiales. Il est déjà connu que les boucles linéaires sont polynomialement expressives, au sens ou si plusieurs variables évoluent linéairement dans une boucle, alors n'importe quel monôme de ces variables évolue linéairement. La première contribution de cette thèse est la caractérisation d'une sous classe de boucles polynomiales exactement aussi expressives que des boucles linéaires, au sens où il existe une boucle linéaire avec le même comportement. Ensuite, deux nouvelles méthodes de génération d'invariants sont présentées.La première méthode est basée sur l'interprétation abstraite et s'intéresse aux filtres linéaires convergents. Ces filtres jouent un rôle important dans de nombreux systèmes embarqués (dans l'avionique par exemple) et requièrent l'utilisation de flottants, un type de valeurs qui peut mener à des erreurs d'imprécision s'ils sont mal utilisés. Aussi, la présence d'affectations aléatoires dans ces filtres rend leur analyse encore plus complexe.La seconde méthode traite d'une approche différente basée sur la génération d'invariants pour n'importe quel type de boucles linéaires. Elle part d'un nouveau théorème présenté dans cette thèse qui caractérise les invariants comme étant les vecteurs propres de la transformation linéaire traitée. Cette méthode est généralisée pour prendre en compte les conditions, les boucles imbriquées et le non déterminisme dans les affectations.La génération d'invariants n'est pas un but en soi, mais un moyen. Cette thèse s'intéresse au genre de problèmes que peut résoudre les invariants générés par la seconde méthode. Le premier problème traité est problème de l'orbite (Kannan-Lipton Orbit problem), dont il est possible de générer des certificats de non accessibilité en utilisant les vecteurs propres de la transformation considerée. En outre, les vecteurs propres sont mis à l'épreuve en pratique par leur utilisation dans le model-checker CaFE basé sur la verification de propriétés temporelles sur des programmes C. / The criticality of programs constantly reaches new boundaries as they are relied on to take decisions in place of the user (autonomous cars, robot surgeon, etc.). This raised the need to develop safe programs and to verify the already existing ones.Anyone willing to formally prove the soundness of a program faces the two challenges of scalability and undecidability. Million of lines of code, complexity of the algorithm, concurrency, and even simple polynomial expressions are part of the issues formal verification have to deal with. In order to succeed, formal methods rely on state abstraction to analyze approximations of the behavior of the analyzed program.The analysis of loops is a full axis of formal verification, as this construction is still today not well understood. Though some of them can be easily handled when they perform simple operations, there still exist some seemingly basic loops whose behavior has not been solved yet (the Syracuse sequence for example is suspected to be undecidable).The most common approach for the treatment of loops is the use of loop invariants, i.e. relations on variables that are true at the beginning of the loop and after every step. In general, invariants are expected to use the same set of expressions used in the loop: if a loop manipulates the memory on a structure for example, invariants will naturally use expressions involving memory operations. However, there exist loops containing only linear instructions that admit only polynomial invariants (for example, the sum on integers $sumlimits_{i=0}^n i$ can be computed by a linear loop and is a degree 2 polynomial in n), hence using expressions that are syntacticallyabsent of the loop. Is the previous remark wrong then ?This thesis presents new insights on loops containing linear and polynomial instructions. It is already known that linear loops are polynomially expressive, in the sense that if a variable evolves linearly, then any monomial of this variable evolves linearly. The first contribution of this thesis is the extraction of a class of polynomial loops that is exactly as expressive as linear loops, in the sense that there exist a linear loop with the exact same behavior. Then, two new methods for generating invariants are presented.The first method is based on abstract interpretation and is focused on a specific kind of linear loops called linear filters. Linear filters play a role in many embedded systems (plane sensors for example) and require the use of floating point operations, that may be imprecise and lead to errors if they are badly handled. Also, the presence of non deterministic assignments makes their analysis even more complex.The second method treats of a more generic subject by finding a complete set of linear invariants of linear loops that is easily computable. This technique is based on the linear algebra concept of eigenspace. It is extended to deal with conditions, nested loops and non determinism in assignments.Generating invariants is an interesting topic, but it is not an end in itself, it must serve a purpose. This thesis investigates the expressivity of invariantsgenerated by the second method by generating counter examples for the Kannan-Lipton Orbit problem.It also presents the tool PILAT implementing this technique and compares its efficiency technique with other state-of-the-art invariant synthesizers. The effective usefulness of the invariants generated by PILAT is demonstrated by using the tool in concert with CaFE, a model-checker for C programs based on temporal logics.

La thèse rapportée dans ce manuscrit étudie l'impact de ces propriétés dans la composition de services Web. La considération de telles propriétés soulève plusieurs problèmes auxquels on a essayé d'apporter une solution. Le premier aspect consiste à définir un modèle qui tienne compte des abstractions nécessaires afin de pouvoir analyser et synthétiser une composition, à savoir les messages, les données, les contraintes de données, les propriétés temporelles et l'aspect asynchrone des communications des services. En se basant sur ce modèle, le deuxième problème consiste à proposer une approche d'analyse de compatibilité. Cette analyse vise à caractériser la compatibilité ou la non-compatibilité des services Web et ce en prenant en considération les abstractions précédemment citées. Nous étudions particulièrement l'impact des propriétés temporelles dans une chorégraphie dans laquelle les services Web supportent des communications asynchrones. Nous proposons une démarche basée sur le model checking qui permet de détecter les éventuels conflits temporisés qui peuvent surgir dans une chorégraphie. Finalement, le dernier problème auquel nous nous intéressons est celui de la construction d'une composition qui essaie de répondre au besoin du client et ce en prenant en compte les aspects temporels. L'approche que l'on propose est basée sur la génération d'un médiateur pour essayer, quand c'est possible, de contourner les incompatibilités temporisées et non-temporisées qui peuvent surgir lors d'une collaboration. Des mécanismes et des algorithmes ont été développés afin de mettre en oeuvre ces objectifs / Web services are based on standrards and Web technologies to interact by exchanging messages. Apart from the sequences of messages, other factors affect the interoperability of Web services, such as temporal constraints that specify the required delay to exchange messages. This thesis studies the impact of these properties in the composition of Web services. The consideration of such properties raises several problems that need several investigations. The first aspect is to define a formal model that takes into account the necessary abstractions in order to analyze and synthesize a composition. The abstractions we have considered are: messages, data, data constraints, temporal properties and the asynchronous nature of services communications. Based on this model, the second problem we handled is the compatibility analysis. This later aims at characterizing the compatibility or incompatibility of Web services by taking into account the abstractions mentioned above. We propose an approach based on model checking to detect the conflicts that may arise in timed choreography. Finally, the last problem we dealt with is the construction of a composition which attempts to satisfy the client need. The approach that we propose is based on the generation of a mediator to try, whenever possible, to resolve the incompatibilities that may arise during a collaboration. Mechanisms and algorithms have been developed to implement these primitives

Alors que l'informatique est devenue omniprésente dans notre société actuelle, assurer la qualité d'un logiciel revêt une importance grandissante. Pour accroître cette qualité, l'une des conditions à respecter est la correction du système. Dans cette thèse, nous nous intéressons plus particulièrement aux systèmes distribués mettant en œuvre un ou plusieurs programmes exécutés sur plusieurs machines qui communiquent entre elles à travers le réseau. Dans ce contexte, assurer leur correction est rendu plus difficile par leur hétérogénéité mais également par leurs spécificités communes. Les algorithmes correspondants sont parfois complexes et la prédiction de leur comportement difficilement réalisable sans une étude avancée. Les travaux réalisés au cours de cette thèse mettent en œuvre la vérification dynamique formelle de propriétés temporelles sur des applications distribuées. Cette approche consiste à vérifier l'implémentation réelle d'une application à travers son exécution. L'enjeu majeur est de réussir à appliquer les techniques associées au Model checking dans le cadre d'une vérification sur des implémentations réelles d'applications distribuées et non plus sur des modèles abstraits. Pour cela, nous proposons dans un premier temps une analyse sémantique dynamique par introspection mémoire d'un état système permettant de détecter des états sémantiquement identiques. Puis, nous mettons en œuvre la vérification dynamique formelle de certaines propriétés temporelles : les propriétés de vivacité, formulées à l'aide de la logique LTL_X, et le déterminisme des communications dans les applications MPI. Une évaluation de chacune de ces contributions est réalisée à travers plusieurs expériences / While computers have become ubiquitous in our current society, ensuring the software quality takes on an increasing importance. One of the requirements to enhance this quality is the system correctness. In this thesis, we are particularly interested in distributed systems implementing one or more programs executed on several machines which communicate with each other through a network. Ensuring the system correctness is more difficult in this context, due to their heterogeneity but also their common characteristics. Corresponding algorithms are sometimes complex and the prediction of their behavior may be difficult to realize without an advanced study. The work done during this thesis implement the dynamic formal verification of some temporal properties on legacy distributed applications. This approach consists of checking the real implementation of an application by its systematic execution. The challenge in this approach is how to apply the methods derived from Model checking in the context of the verification of legacy distributed applications (without access to source code) and no longer on abstract models. For that, we propose in a first step a dynamic semantic analysis of a system state permitting the detection of identical states. Then, we implement the dynamic formal verification of some temporal properties: liveness properties, specified with the LTL_X logic, and the communications determinism in MPI applications. These contributions are experimentaly validated and evaluated with different series of experiments