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.

Notre objectif principal est de permettre l’utilisation de propriétés temporelles dans une politique d’adaptation en tenant compte des spécificités de la vérification à l’exécution.Pour y répondre, nous définissons un modèle de système à composants supportant les reconfigurations dynamiques. Nous introduisons les reconfigurations gardées qui nous permettent d’utiliser des opérations primitives en tant que “briques” pour construire des reconfigurations plus élaborées impliquant des constructions, non seulement, séquentielles, mais aussi alternatives ou répétitives, tout en garantissant la consistance des configurations du système.En outre, nous étendons (aux événements externes) la logique temporelle utilisée précédemment pour exprimer des contraintes architecturales sur des configurations. Avec une sémantique, dite progressive, nous pouvons, dans la plupart des cas, évaluer (de fac¸on centralisée ou décentralisée)une expression temporelle pour une configuration donnée `a partir d’ évaluations déjà réalisées à la seule configuration précédente. Nous utilisons cette logique dans des politiques d’adaptation permettant de guider et contrôler les reconfigurations de systèmes à composants à l’exécution.Enfin, l’implémentation de politiques d’adaptation a été expérimentée dans divers cas d’ études sur les plateformes Fractal et FraSCAti. Nous utilisons notamment le fuzzing comportemental afin de pouvoir tester des aspects spécifiques d’une politique d’adaptation. / Our main goal is to allow the usage of temporal properties within an adaptation policy while takinginto account runtime verification specificities.In order to reach it, we define a component-based system model that supports dynamicreconfigurations. We introduce guarded reconfigurations in order to use primitive operations as“building blocks” to craft more elaborated reconfigurations involving, not only sequential, but also,alternate and repetitive constructs while ensuring the system’s configurations consistency.Furthermore, we extend (to external events) the temporal logic previously used to expressarchitectural constraints on configurations. Using, so called, progressive semantics, we can, in mostof the cases, evaluate (in a centralised or decentralised fashion) a temporal expression for a givenconfiguration using evaluations performed only at the previous configuration. We use this logic withinadaptation policies enabling the steering and control of dynamic reconfigurations at runtime.Finally, we implemented such adaptation policies in various case studies using frameworks such asFractal and FraSCAti. We also use behavioural fuzzing to test various specific aspects of a givenadaptation policy.

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.

This thesis presents a fully automated technique for procedure-modular verification of control flow temporal safety properties. Procedure-modular verification is a natural instantiation of modular verification where modularity is achieved at the level of procedures. Here it is used for the verification of software systems in the presence of code evolution, multiple method implementations (as arising from software product lines), or even unknown method implementations (as in mobile code for open platforms). The technique is built on top of a previously developed modular verification framework based on maximal model construction. In the framework, program data is abstracted away completely to achieve algorithmic verification. This restricts the class of properties that can be verified. The technique is supported by a fully automated tool called ProMoVer which is described and evaluated on a number of real-life case studies. ProMoVer is quipped with a number of features, such as automatic specification extraction, to facilitate easy usage. Moreover, it provides a proof storage and reuse mechanism for efficiency. An application area which can significantly benefit from modular verification is software product line (SPL) design. In SPL engineering, products are generated from a set of well-defined commonalities and variabilities. The products of an SPL can be described by means of a hierarchical variability model specifying the commonalities and variabilities between the individual products. The number of products generated from a hierarchical model is exponential in the size of the hierarchical model. Therefore, scalable and efficient verification for SPL is only possible by exploiting modular verification techniques. In this thesis, we propose a hierarchical variability model for modeling product families. Then the modular verification technique and ProMoVer are adapted for the SPLs described with this hierarchical model. A natural extension of the modular verification technique is to include program data in a conservative fashion, by encoding data from a finite domain through control. By this, a wider class of properties can be supported. As a first step towards including program data, Boolean values are added to the program model, specification languages, maximal model construction and modular verification principles. / QC 20120507

Correct behavior of programs can be defined by their temporal properties. One of the options for formal specification of such properties is  linear temporal logic - LTL . This master's thesis describes design and implementation of a tool for automatic checking of temporal properties of programs, that are specified using Past-Time LTL formulae. The trace of a given program is analyzed in run-time and any violation of given formulae is reported in details to help to find the code location with a root cause of the bug.

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

<p>Laser beam control is important in many applications. Phase modulating spatial light modulators (SLMs) can be used to electronically alter the phase distribution of an optical wave-front and thus change the direction and shape of a laser beam. Physical constraints set limitations to the SLM and an ideal phase distribution can usually not be realised. In order to understand how such components can be used for non-mechanical beam control three nematic liquid crystal (NLC) SLMs have been thoroughly characterised and modelled.</p><p>The pixel structure and phase quantisation give a discrepancy between ideal and realised phase distributions. The impact on beam steering capability was examined by measurements and simulations of the intensity distribution in the far-field.</p><p>In two of the studied SLMs the pixel period was shorter than the thickness of the LC layer giving the optical phase shift. This results in a so-called “fringing field”, which was shown to degrade the phase modulation and couple light between polarisation modes. The deformation of the LC was simulated and a finite-difference time-domain (FDTD) algorithm was used to calculate how polarised light propagates through the optically anisotropic SLM.</p><p>Non-mechanical beam steering and tracking in an optical free-space communication link were demonstrated. Continual optimisation of the steering angle was achieved by feedback from a video camera.</p><p>The optical properties of the SLM in the time period right after a voltage update were studied. It was shown how light is redistributed between orders during the switching from one blazed grating to another. By appropriate choice of the blazed gratings the effects on the diffraction efficiency can be minimised.</p><p>The detailed knowledge of the SLM structure and its response to electronic control makes it possible to predict and optimise the device performance in future systems.</p>

Laser beam control is important in many applications. Phase modulating spatial light modulators (SLMs) can be used to electronically alter the phase distribution of an optical wave-front and thus change the direction and shape of a laser beam. Physical constraints set limitations to the SLM and an ideal phase distribution can usually not be realised. In order to understand how such components can be used for non-mechanical beam control three nematic liquid crystal (NLC) SLMs have been thoroughly characterised and modelled. The pixel structure and phase quantisation give a discrepancy between ideal and realised phase distributions. The impact on beam steering capability was examined by measurements and simulations of the intensity distribution in the far-field. In two of the studied SLMs the pixel period was shorter than the thickness of the LC layer giving the optical phase shift. This results in a so-called “fringing field”, which was shown to degrade the phase modulation and couple light between polarisation modes. The deformation of the LC was simulated and a finite-difference time-domain (FDTD) algorithm was used to calculate how polarised light propagates through the optically anisotropic SLM. Non-mechanical beam steering and tracking in an optical free-space communication link were demonstrated. Continual optimisation of the steering angle was achieved by feedback from a video camera. The optical properties of the SLM in the time period right after a voltage update were studied. It was shown how light is redistributed between orders during the switching from one blazed grating to another. By appropriate choice of the blazed gratings the effects on the diffraction efficiency can be minimised. The detailed knowledge of the SLM structure and its response to electronic control makes it possible to predict and optimise the device performance in future systems.

After over a decade of its discovery, the Electroretinogram (ERG) still remains the objective tool that is conventionally used in assessment of retinal function in health and disease. Although there is ongoing research in developing ERG- recording techniques, interpretation and clinical applications, there is still a limited understanding on how each photoreceptor class contribute to the ERG waveform and their role and/or susceptibilities in various retinal diseases still remains unclear. Another limitation with currently used conventional testing protocols in a clinical setting is the requirement of an adaptation period which is time-consuming. Furthermore, the ERG responses derived in this manner are recorded under different stimulus conditions, thus, making comparison of these signals difficult. To address these issues and develop a new testing method, we employed silent substitution paradigm in obtaining cone- and rod- isolating ERGs using sine- and square- wave temporal profiles. The ERGs achieved in this manner were shown to be photoreceptor-selective. Furthermore, these responses did not only provide the functional index of photoreceptors but their contributions to their successive postreceptoral pathways. We believe that the substitution stimuli used in this thesis could be a valuable tool in functional assessment of individual photoreceptor classes in normal and pathological conditions. Furthermore, we speculate that this method of cone/rod activity isolation could possibly be used in developing faster and efficient photoreceptor-selective testing protocols without the need of adaptation. / Bradford School of Optometry and Vision Sciences

In der formalen Verifikation digitaler Schaltkreise hat sich die Methodik der vollständigen Verifikation anhand spezieller Operationseigenschaften bewährt. Operationseigenschaften beschreiben das Verhalten einer Schaltung in einem festen Zeitintervall und können sequentiell miteinander verknüpft werden, um so das Gesamtverhalten zu spezifizieren. Zusätzlich beweist eine formale Vollständigkeitsprüfung, dass die Menge der Eigenschaften für jede Folge von Eingangssignalwerten die Ausgänge der zu verifizierenden Schaltung eindeutig und lückenlos determiniert. In dieser Arbeit wird untersucht, wie aus Operationseigenschaften, deren Vollständigkeit erfolgreich bewiesen wurde, automatisiert eine Schaltungsbeschreibung abgeleitet werden kann. Gegenüber der traditionellen Entwurfsmethodik auf Register-Transfer-Ebene (RTL) bietet dieses Verfahren zwei Vorteile. Zum einen vermeidet der Vollständigkeitsbeweis viele Arten von Entwurfsfehlern, zum anderen ähnelt eine Beschreibung mit Hilfe von Operationseigenschaften den in Spezifikationen häufig genutzten Zeitdiagrammen, sodass die Entwurfsebene der Spezifikationsebene angenähert wird und Fehler durch manuelle Verfeinerungsschritte vermieden werden. Das Entwurfswerkzeug vhisyn führt die High-Level-Synthese (HLS) einer vollständigen Menge von Operationseigenschaften zu einer Beschreibung auf RTL durch. Die Ergebnisse zeigen, dass sowohl die verwendeten Synthesealgorithmen, als auch die erzeugten Schaltungen effizient sind und somit die Realisierung größerer Beispiele zulassen. Anhand zweier Fallstudien kann dies praktisch nachgewiesen werden. / The complete verification approach using special operation properties is an accepted methodology for the formal verification of digital circuits. Operation properties describe the behavior of a circuit during a certain time interval. They can be sequentially concatenated in order to specify the overall behavior. Additionally, a formal completeness check proves that the sequence of properties consistently determines the exact value of the output signals for every valid sequence of input signal values. This work examines how a circuit description can be automatically derived from a set of operation properties whose completeness has been proven. In contrast to the traditional design flow at register-transfer level (RTL), this method offers two advantages. First, the prove of completeness helps to avoid many design errors. Second, the design of operation properties resembles the design of timing diagrams often used in textual specifications. Therefore, the design level is closer to the specification level and errors caused by refinement steps are avoided. The design tool vhisyn performs the high-level synthesis from a complete set of operation properties to a description at RTL. The results show that both the synthesis algorithms and the generated circuit descriptions are efficient and allow the design of larger applications. This is demonstrated by means of two case studies.