Computers and the software they run are pervasive, yet released software is often unreliable, which has many consequences. Loss of time and earnings can be caused by application software (such as word processors) behaving incorrectly or crashing. Serious disruption can occur as in the l4th August 2003 blackouts in North East USA and Canadal, or serious injury or death can be caused as in the Therac-25 overdose incidents. One way to improve the quality of software is to test it thoroughly. However, software testing is time consuming, the resources, capabilities and skills needed to carry it out are often not available and the time required is often curtailed because of pressures to meet delivery deadlines3. Automation should allow more thorough testing in the time available and improve the quality of delivered software, but there are some problems with automation that this research addresses. Firstly, it is difficult to determine ifthe system under test (SUT) has passed or failed a test. This is known as the oracle problem4 and is often ignored in software testing research. Secondly, many software development organisations use an iterative and incremental process, known as evolutionary development, to write software. Following release, software continues evolving as customers demand new features and improvements to existing ones5. This evolution means that automated test suites must be maintained throughout the life ofthe software. A contribution of this research is a methodology that addresses automatic generation of the test cases, execution of the test cases and evaluation of the outcomes from running each test. "Predecessor" software is used to solve the oracle problem. This is software that already exists, such as a previous version of evolving software, or software from a different vendor that solves the same, or similar, problems. However, the resulting oracle is assumed not be perfect, so rules are defined in an interface, which are used by the evaluator in the test evaluation stage to handle the expected differences. The interface also specifies functional inputs and outputs to the SUT. An algorithm has been developed that creates a Markov Chain Transition Matrix (MCTM) model of the SUT from the interface. Tests are then generated automatically by making a random walk of the MCTM. This means that instead of maintaining a large suite of tests, or a large model of the SUT, only the interface needs to be maintained.

Les systèmes-de-systèmes (Systems-of-Systems, SoS) interconnectent plusieurs systèmes indépendants qui travaillent ensemble pour exécuter une action conjointe dépassant leurs compétences individuelles. Par ailleurs, les descriptions architecturales sont des artefacts qui décrivent des architectures logicielles jouant dans le contexte SoS un rôle important dans la promotion de l’interaction des éléments constituants tout en favorisant la communication parmi les intéressés et en soutenant les activités d’inspection et d’analyse dès le début de leur cycle de vie. Le principal problème traité dans cette thèse est le manque de descriptions architecturales adéquates pour les SoS qui sont développés sans l’attention nécessaire à leur architecture logicielle. Puisque les systèmes constituants ne sont pas forcément connus pendant la conception du projet à cause du développement évolutionnaire des SoS, la description architecturale doit définir à la conception même du projet quelles coalitions entre les systèmes constituants seront possibles pendant son exécution. En outre, comme plusieurs de ces systèmes sont développés pour le domaine critique de sécurité, des mesures supplémentaires doivent être mises en place pour garantir l’exactitude et la complétude de la description architecturale. Afin de résoudre ce problème, nous nous servons du SosADL, un langage formel créé spécialement pour le domaine SoS et qui permet de décrire les architectures logicielles comme des associations dynamiques entre systèmes indépendants où les interactions doivent être coordonnées pour réaliser une action combinée. Notamment, une nouvelle méthode formelle, nommée Ark, est proposée pour systématiser les étapes nécessaires dans la synthèse d’architectures concrètes obéissant à cette description. Dans ce dessein, cette méthode crée un modèle formel intermédiaire, nommé TASoS, qui décrit l’architecture du SoS en tant que problème de satisfaisabilité de restrictions, rendant ainsi possible la vérification automatique d’un ensemble initial de propriétés. Le résultat obtenu par cette analyse peut s’utiliser en raffinements et révisions ultérieurs de la description architecturale. Un outil logiciel nommé SoSy a été aussi développé pour automatiser la génération de modèles intermédiaires et d’architectures concrètes, en cachant l’utilisation de solveurs de contraintes dans le projet de SoS. Particulièrement, cet outil intègre un environnement de développement plus important et complet pour le projet de SoS. Cette méthode et son outil ont été appliqués dans un modèle de SoS de surveillance de rivières urbaines où la faisabilité d’architectures abstraites a été étudiée. En formalisant et en automatisant les étapes requises pour la synthèse architecturale de SoS, Ark contribue à l’adoption de méthodes formelles dans le projet d’architectures SoS, ce qui est nécessaire pour atteindre des niveaux plus élevés de fiabilité. / Systems-of-Systems (SoS) encompass diverse and independent systems that must cooperate with each other for performing a combined action that is greater than their individual capabilities. In parallel, architecture descriptions, which are the main artifact expressing software architectures, play an important role in fostering interoperability among constituents by facilitating the communication among stakeholders and supporting the inspection and analysis of the SoS from an early stage of its life cycle. The main problem addressed in this thesis is the lack of adequate architectural descriptions for SoS that are often built without an adequate care to their software architecture. Since constituent systems are, in general, not known at design-time due to the evolving nature of SoS, the architecture description must specify at design-time which coalitions among constituent systems are feasible at run-time. Moreover, as many SoS are being developed for safety-critical domains, additional measures must be placed to ensure the correctness and completeness of architecture descriptions. To address this problem, this doctoral project employs SoSADL, a formal language tailored for the description of SoS that enables one to express software architectures as dynamic associations between independent constituent systems whose interactions are mediated for accomplishing a combined action. To synthesize concrete architectures that adhere to one such description, this thesis develops a formal method, named Ark, that systematizes the steps for producing such artifacts. The method creates an intermediate formal model, named TASoS, which expresses the SoS architecture in terms of a constraint satisfaction problem that can be automatically analyzed for an initial set of properties. The feedback obtained in this analysis can be used for subsequent refinements or revisions of the architecture description. A software tool named SoSy was also developed to support the Ark method as it automates the generation of intermediate models and concrete architectures, thus concealing the use of constraint solvers during SoS design and development. The method and its accompanying tool were applied to model a SoS for urban river monitoring in which the feasibility of candidate abstract architectures is investigated. By formalizing and automating the required steps for SoS architectural synthesis, Ark contributes for adopting formal methods in the design of SoS architectures, which is a necessary step for obtaining higher reliability levels.

Ce travail s'inscrit dans le cadre des recherches menées autour de l'analyse et la visualisation des logiciels, notamment les logiciels à objets, et en particulier Java. Très brièvement, on peut dire que le but de cette thèse revient à tenter de répondre à une question fondamentale: comment faire pour faciliter la compréhension du logiciel par ses développeurs et concepteurs ? Ce travail de recherche est basé en grande partie sur deux axes principaux. Le premier consiste à analyser l'exécution des programmes, non seulement au niveau de la méthode, mais bien au niveau du bloc de base, pour recueillir des données d'exécutions avec un maximum de précision comme par exemple les différents types d'instances sur les sites d'appels. Le second axe considère l'utilisation des informations apportées par notre analyse dynamique de l'exécution pour permettre la visualisation de ces données. En effet, ces informations offrent des détails intéressants sur le fonctionnement du programme et aident à expliquer le comportement du logiciel, aussi bien pour déceler les problèmes de performance que les problèmes de codages. Nous proposons une technique souple et efficace qui effectue une analyse dynamique de l'exécution de programmes Java. Nous introduisons ainsi une nouvelle technique et un nouvel outil permettant de recueillir des informations encore non proposées par d'autres analyseurs. Cette approche trace l'exécution précise des programmes tout en ayant une baisse des performances d'exécution acceptable, laissant le programme final utilisable. De plus, nous proposons et expérimentons une approche basé sur la visualisation des relations au sein d'une représentation du logiciel par une métaphore de ville. Nous introduisons une nouvelle technique de représentation des relations nommée "3D HierarchicalEdge Bundles" qui est basée sur une représentation 2D existante nommée "HierarchicalEdge Bundles". Cette approche conserve la puissance de visualisation du logiciel offerte par la métaphore de la ville tout en ajoutant la représentation des relations, et cela d'une façon lisible. Ces travaux sont validés entre autres par le développement d'un outil d'analyse nommé VITRAIL JBInsTrace et d'un outil de visualisation nommé VITRAIL Visualizer. Ces outils sont la base de nos recherche actuelles sur l'étude de l'exécution des programmes objets / This work falls within the scope of research pertaining to the analysis and the visualization of software systems, especially for object oriented languages, and more precisely Java. In a nutshell, it can be said the aim of this thesis is to try to answer a fundamental question: what can we do to ease the understanding of software by its designers and developers ? This research work is mainly based on two axes. The first axis consists in analyzing software runtime, not only at method level, but also at basic bloc level, so as to be able to get meaningful and precise information about the runtime. For instance, we can acquire the different types of instances on call sites at runtime. The second axis considers the use of information coming from our dynamic analyzer of software runtime and allowing the visualization of these data. Indeed, this kind of information offers important details about software functioning and provide a way to explain the behavior of software, so as to identify performance, coding and even design and architecture issues. We propose a technique that allows flexible and efficient dynamic analysis of the execution of Java programs. We thus introduce a new technique and tool for gathering information not yet offered by other analyzers. This approach precisely traces the execution of programs with acceptable performance penalty, that is while keeping the traced programs usable. In addition, we propose and experiment an approach based on visualizing relationships within a software city representation. We introduce a new technique for representing relationships in 3D named the "3D Hierarchical Edge Bundles" that is based on an existing 2D technique, the "Hierarchical Edge Bundles". This approach keeps the power of the software city metaphor while adding the representation of the relationships within the software, in a readable way. These works are validated by, among others things, the development of a tracer and analyzer tool called VITRAIL JBInsTrace and a visualization tool called VITRAIL Visualizer. These tools are used on our current researches which consist in studying runtime of object-oriented programs

Cette thèse porte en premier lieu sur l'analyse et le désassemblage de programmes malveillants utilisant certaines techniques d'obscurcissement telles que l'auto-modification et le chevauchement de code. Les programmes malveillants trouvés dans la pratique utilisent massivement l'auto-modification pour cacher leur code utile à un analyste. Nous proposons une technique d'analyse hybride qui utilise une trace d'exécution déterminée par analyse dynamique. Cette analyse découpe le programme auto-modifiant en plusieurs sous-parties non auto-modifiantes que nous pouvons alors étudier par analyse statique en utilisant la trace comme guide. Cette seconde analyse contourne d'autres techniques de protection comme le chevauchement de code afin de reconstruire le graphe de flot de contrôle du binaire analysé. Nous étudions également un détecteur de programmes malveillants, fonctionnant par analyse morphologique : il compare les graphes de flot de contrôle d'un programme à analyser à ceux de programmes connus comme malveillants. Nous proposons une formalisation de ce problème de comparaison de graphes, des algorithmes permettant de le résoudre efficacement et détaillons des cas concrets d'application à la détection de similarités logicielles / This dissertation explores tactics for analysis and disassembly of malwares using some obfuscation techniques such as self-modification and code overlapping. Most malwares found in the wild use self-modification in order to hide their payload from an analyst. We propose an hybrid analysis which uses an execution trace derived from a dynamic analysis. This analysis cuts the self-modifying binary into several non self-modifying parts that we can examine through a static analysis using the trace as a guide. This second analysis circumvents more protection techniques such as code overlapping in order to recover the control flow graph of the studied binary. Moreover we review a morphological malware detector which compares the control flow graph of the studied binary against those of known malwares. We provide a formalization of this graph comparison problem along with efficient algorithms that solve it and a use case in the software similarity field

La réutilisation est l’un des principaux objectifs de l’ingénierie logicielle. De nombreux concepts et mécanismes associés ont été proposés pour promouvoir la réutilisation des fonctionnalités offertes par le logiciel. L’ingénierie logicielle à base de composants (CBSE) est l’une des plus importantes approches qui ont été proposées pour augmenter la réutilisation des logiciels.Ainsi, plusieurs travaux ont été réalisés afin de restructurer les systèmes existants en systèmes à base de composants. Néanmoins, presque toutes les approches proposées visent plus l’identification des composants que l’identification des parties ré-utilisables. Ainsi, elles sont limitées à identifier des composants, correspondant à des ensembles de classes, permettantl’extraction d’une vue architecturale de l’ancien système. Mais, les composants identifiés ne peuvent pas être implantés avec un modèle concret de composants.Dans cette thèse, nous proposons deux approches pour améliorer la réutilisation des composants extraits, mais aussi faciliter la compréhension de l’architecture sous-jacente. Ainsi, la première approche vise l’identification des interfaces du composant extrait en fonction de ses interactions avec les autres composants. La seconde a pour objectif de rendre possible l’implantation des composants extraits avec un modèle concret de composants. Ceci est fait en utilisant des instances de classes (objets) qui composent les composants extraits pour déduire des instances possibles de composant.L’évaluation des approches proposées par une étude empirique montre que i) l’ensemble des interfaces identifiées correspondent aux différents aspects fonctionnels des composants extraits. ii) et, qu’il est possible d’implanter, dans un modèle concret de composants, les composants extraits sans modifier le comportement de l’application. / Reuse is one of the main goals of software engineering. Many concepts and associated mechanisms were proposed to promote the reuse of features offered by the software. Component based software engineering (CBSE) is one of the important approaches which was proposed to increase the software reuse. Thus, several works were conducted in order to restructure legacy systems into component-based ones. Nevertheless, almost all proposed approaches are more targeted for component identification than for the identification of reusable parts. Thus, they are limited to identify components, corresponding to sets of classes, allowing an extraction of the architectural view of the legacy system. But, the identified components can not be easily implemented in a concrete component model.In this thesis, we propose two approaches to improve the reusability of the extracted components and by the way facilitate the comprehension of the underlying architecture. Thus, the first approach aims the identification of the extracted component’s interfaces according to its interactions with the other components. The second one aims to make extracted components implementable within a concrete component model. This is done by using class instances (objects) that compose the extracted components to infer possible component instances.The evaluation of the proposed approaches via an empirical study showed that i) overall the identified interfaces correspond to the different functional aspects of the extracted components. ii) and, that is possible to implement, within a concrete component model, the extracted components without altering the behavior of the application.

Établir des preuves de bon fonctionnement des programmes est délicat ; on a recours à des outils de preuve, qui doivent procéder par surapproximation (à cause du théorème de Rice). La complétion d'automate est un tel outil, qui surapproxime l'ensemble des termes accessibles lors de l'exécution d'un programme représenté par un système de réécriture. La stratégie d'évaluation donne l'ordre dans lequel les sous-termes d'un terme doivent être réécrits ; en tenir compte permet une meilleur précision de l'analyse. Notre thèse propose une adaptation de la complétion d'automate à la stratégie en profondeur, utilisée notamment par OCaml. Nous établissons la correction et la précision de notre méthode et montrons comment elle s'inscrit dans le cadre plus large de l'analyse de programmes fonctionnels (OCaml). / Proving that programs behave correctly is difficult; one uses proof tools, which must rely on overapproximation (because of Rice's theorem). Automaton completion is such a tool, which overapproximates the set of reachable terms during the execution of a program represented as a TRS. An evaluation strategy dictates which subterm of a term should be rewritten first; taking this into account allows for a better approximation. Our thesis sets forward an adaptation of automaton completion to the innermost strategy, which is used among others by OCaml. We prove the soundness and the precision of our adaptation and show how it is part of a greater framework for analysis of functional programms (OCaml).

This dissertation investigates current trends concerning exceptions. Exceptions influence the reliability of software systems. In order to develop software systems that are most robust, thus delivering higher availability at a lower development and operating cost, the occurence of exceptions needs to be reduced and the effects of the exceptions controlled. In order to do this, issues such as detection, identification, classification, propagation, handling, language implementation, software testing and reporting of exceptions must be attended to. Although some of these areas are well researched there are remaining problems. The quest is to establish if a unified exception-handling framework is possible and viable, which can address the issues and problems throughout the software development life cycle, and if so, the requirements for such a framework. / Computing / M.Sc. (Information Systems)

Des nombreuses applications de méthodes formelles se fondent sur les solveurs SMT pour valider automatiquement les conditions à vérifier et fournissent des certificats de leurs résultats. Nous visons à la fois à améliorer l'efficacité des solveurs SMT et à accroître leur fiabilité. Notre première contribution est un cadre uniforme pour le raisonnement avec des formules quantifiées dans les solveurs SMT, dans lequel généralement diverses techniques d'instanciation sont utilisées. Nous montrons que les principales techniques d'instanciation peuvent être jetées dans ce cadre. Le cadre repose sur le problème de l'E-ground (dis)unification. Nous présentons une procédure de décision pour résoudre ce problème en pratique: Fermeture de congruence avec variables libres (CCFV}). Nous mesurons l'impact de CCFV dans les solveurs SMT veriT et CVC4. Nous montrons que nos implémentations présentent des améliorations par rapport aux approches à la fine pointe de la technologie. Notre deuxième contribution est un cadre pour le traitement des formules tout en produisant des preuves détaillées. Les principaux composants de notre cadre de production de preuve sont un algorithme de récurrence contextuelle générique et un ensemble extensible de règles d'inférence. Avec des structures de données appropriées, la génération des preuves ne crée que des frais généraux linéaires et les vérifications peuvent être vérifiées en temps linéaire. Nous avons également mis en œuvre l'approche en veriT. Cela nous a permis de simplifier considérablement la base du code tout en augmentant le nombre de problèmes pour lesquels des preuves détaillées peuvent être produites / In many formal methods applications it is common to rely on SMT solvers to automatically discharge conditions that need to be checked and provide certificates of their results. In this thesis we aim both to improve their efficiency of and to increase their reliability. Our first contribution is a uniform framework for reasoning with quantified formulas in SMT solvers, in which generally various instantiation techniques are employed. We show that the major instantiation techniques can be all cast in this unifying framework. Its basis is the problem of E-ground (dis)unification, a variation of the classic rigid E-unification problem. We introduce a decision procedure to solve this problem in practice: Congruence Closure with Free Variables (CCFV). We measure the impact of optimizations and instantiation techniques based on CCFV in the SMT solvers veriT and CVC4, showing that our implementations exhibit improvements over state-of-the-art approaches in several benchmark libraries stemming from real world applications. Our second contribution is a framework for processing formulas while producing detailed proofs. The main components of our proof producing framework are a generic contextual recursion algorithm and an extensible set of inference rules. With suitable data structures, proof generation creates only a linear-time overhead, and proofs can be checked in linear time. We also implemented the approach in veriT. This allowed us to dramatically simplify the code base while increasing the number of problems for which detailed proofs can be produced

La formulation des missions est le point de départ du développement de systèmes-de- systèmes, étant utilisée comme base pour la spécification, la vérification et la validation d’architectures de systèmes-de-systèmes. Élaborer des modèles d’architecture pour systèmes-de-systèmes est une activité complexe, cette complexité reposant spécialement sur les comportements émergents, c'est-à-dire, des comportements issus des interactions entre les parties constituantes d’un système-de-systèmes qui ne peuvent pas être prédits même si on connaît tous les comportements de tous les systèmes constituants. Cette thèse adresse le lien synergique entre mission et architecture dans le cadre des systèmes-de-systèmes à logiciel prépondérant, en accordant une attention particulière aux comportements émergents créés pour réaliser les missions formulées. Nous proposons ainsi une approche pour la conception d’architecture de systèmes-de-systèmes dirigée par le modèle de mission. Dans notre approche, le modèle de mission sert à dériver et à valider les architectures de systèmes-de-systèmes. Dans un premier temps, nous générons la structure de l’architecture à l’aide de transformations de modèles. Ensuite, lors que l’architecte spécifie les aspects comportementaux, la description de l’architecture résultante est validée à l’aide d’une démarche conjointe qui comprend à la fois la vérification des propriétés spécifiées et la validation par simulation des comportements émergents. La formalisation en termes de logique temporelle et la vérification statistique de modèles sont les fondements formels de l’approche. Un outil mettant en œuvre l’ensemble de l’approche a été également développé et expérimenté. / The formulation of missions is the starting point to the development of Systems-of-Systems (SoS), being used as a basis for the specification, verification and validation of SoS architectures. Specifying, verifying and validating architectural models for SoS are complex tasks compared to usual systems, the inner complexity of SoS relying specially on emergent behaviors, i.e. features that emerge from the interactions among constituent parts of the SoS which cannot be predicted even if all the behaviors of all parts are completely known. This thesis addresses the synergetic relationship between missions and architectures of software-intensive SoS, giving a special attention to emergent behaviors which are created for achieving formulated missions. We propose a design approach for the architectural modeling of SoS driven by the mission models. In our proposal, the mission model is used to both derive, verify and validate SoS architectures. As first step, we define a formalized mission model, then we generate the structure of the SoS architecture by applying model transformations. Later, when the architect specifies the behavioral aspects of the SoS, we generate concrete SoS architectures that will be verified and validated using simulation-based approaches, in particular regarding emergent behaviors. The verification uses statistical model checking to verify whether specified properties are satisfied, within a degree of confidence. The formalization in terms of a temporal logic and statistical model checking are the formal foundations of the developed approach. A toolset that implements the whole approach was also developed and experimented.

L’essor des périphériques mobiles (ex. tablettes, smartphones) ainsi que leurs applications pédagogiques et ludiques ont contribué à la naissance des Jeux Éducatifs Mobiles (JEM). De nombreux chercheurs ont prouvé les effets positifs de ces JEM sur la motivation des apprenants et même sur certains apprentissages. Cependant, l’utilisation de JEM en contexte scolaire reste très limitée. En effet, les JEM existants, parfois assez coûteux, sont souvent conçus pour un domaine très spécifique, et n’offrent donc pas de possibilités de réutilisation. De plus, les outils auteur existants sont, soit riches en fonctionnalités mais nécessitent un investissement important des enseignants pour être pris en main, soit simples à utiliser mais ne permettent pas de concevoir des JEM qui répondent aux besoins pédagogiques. Pour s’attaquer à ces problématiques, nous proposons JEM iNVENTOR, un outil auteur de JEM, fondé sur une approche de conception gigogne, destiné aux enseignants, conservateurs de musée, ou toute personne non-informaticienne, qui souhaitent scénariser leurs propres JEM et les déployer sur les systèmes mobiles.Le modèle de conception gigogne a été validé par une série d’expérimentations auprès d’une vingtaine d’enseignants ayant des niveaux d’expertises et des domaines d’enseignement très variés. Nous avons également mené des expérimentations de terrain, auprès d’environ 1500 étudiants et élèves, afin d’évaluer la qualité des JEM créés avec JEM iNVENTOR ainsi que leur impact sur les apprenants. / The rise of mobile devices (e.g. tablets, smartphones) and their educational and recreational applications have contributed to the emergence of Mobile Learning Games (MLGs). Indeed, MLGs show great potential for increasing engagement, creativity and authentic learning. Yet, despite their great potential for education, the use of MLGs by teachers, remains very limited. This is partly due to the fact that MLGs are often designed to match a specific learning context, and thus cannot be directly reusable for other contexts. In addition, existing authoring tools are either feature-rich but require a significant investment by teachers to be used, or simple to use but do not offer enough features for the design of MLGs that meet pedagogical needs. To tackle these problems, we propose JEM iNVENTOR, a MLG authoring tool, based on a nested design approach, intended for teachers, museum curators, or any person without computer skills, wishing to script their own MLG and deploy them on mobile systems.The nested design model was approved through a series of experimentations with some twenty teachers from a wide range of expertise levels and teaching fields. We also conducted field experimentations with about 1500 students and pupils in order to evaluate the quality of MLGs created with JEM iNVENTOR as well as their impact on learners.