One problem with computers is that the operating system automatically trusts any externallyconnected peripheral. This can result in abuse when a peripheral technically can violate the security model because the peripheral is trusted. Because of that the security is an important issue to look at.The aim of our project is to see in which cases hardware peripherals can be trusted. We built amodel of the universal asynchronous transmitter/receiver (UART), a model of the main memory(RAM) and a model of a DMA controller. We analysed interaction between hardware peripherals,user processes and the main memory.One of our results is that connections with hardware peripherals are secure if the hardware is properly configured. A threat scenario could be an eavesdropper or man-in-the-middle trying to steal data or change a cryptographic key.We consider the use-cases of DMA and protecting a cryptographic key. We prove the well-behavior of the algorithm. Some error-traces resulted from incorrect modelling that was resolved by adjusting the models. Benchmarks were done for different memory sizes.The result is that a peripheral can be trusted provided a configuration is done. Our models consist of finite state machines and their corresponding SMV modules. The models represent computer hardware with DMA. We verified the SMV models using the model checkers NuSMV and nuXmv. / Målet med vårt projekt är att verifiera olika specifikationer av externa enheter som ansluts till datorn. Vi utför formell verifikation av sådan datorutrustning och virtuellt minne. Verifikation med temporal logik, LTL, utförs. Specifikt verifierar vi 4 olika use-case och 9 formler för seriell datakommunikation, DMA och virtuellt minne. Slutsatsen är att anslutning av extern hårdvara är säker om den är ordentligt konfigurerad.Vi gör jämförelser mellan olika minnesstorlekar och mätte tidsåtgången för att verifiera olika system. Vi ser att tidsåtgången för verifikation är långsammare än linjärt beroende och att relativt små system tar relativt lång tid att verifiera.

Linear Temporal Logic (LTL), as one of the temporal logic, can generate a fully automated correct-by-design controller synthesis approach for single or multiple autonomous vehicles, under much more complex missions than the traditional point-to-point navigation.In this master thesis, a framework which combines model- checking-based robot motion planning with action planning is proposed based on LTL for-mulas. The specifications implicitly require both sequential regions for multi-agent to visit and the desired actions to perform at these regions while avoid-ing collision with each other and fixed obstacles. The high level motion and task planning and low level navigation function based collision avoidance controller are verified by nontrivial simulation and implementation on real quadcopter in Smart Mobility Lab.

While autonomous robot systems are becoming increasingly common, their usage is still mostly limited to rather simple tasks. This primarily results from the need for manually programming the execution plans of the robots. Instead, as shown in this thesis, their behavior can be automatically generated from a given goal specification. This forms the basis for providing formal guarantees regarding optimality and satisfaction of the mission goal specification and creates the opportunity to deploy these robots in increasingly sophisticated scenarios. Well-defined robot capabilities of comparably low complexity can be developed independently from a specific high-level goal and then, using a behavior planner, be automatically composed to achieve complex goals in a verifiably correct way. Considering multiple robots introduces significant additional planning complexity. Not only actions need to be planned, but also allocation of parts of the mission to the individual robots needs to be considered. Classically, either are planning and allocation seen as two independent problems which requires to solve an exponential number of planning problems, or the formulation of a joint team model leads to a product state space between the robots. The resulting exponential complexity prevents most existing approaches from being practically useful in more complex and realistic scenarios. In this thesis, an approach is presented to utilize the interplay of allocation and planning, which avoids the exponential complexity for independently executable parts of the mission specification. Furthermore, an approach is presented to identify these independent parts automatically when only being given a single goal specification for the team. This bears the potential of improving the efficiency to find an optimal solution and is a significant step towards the application of formal multi-robot behavior planning to real-world problems. The effectiveness of the proposed methods is therefore illustrated in experiments based on an existing office environment and in realistic scenarios. / Även om autonoma robotsystem blir allt vanligare är deras användning fortfarande mestadels begränsad till ganska enkla uppgifter. Detta beror främst på att manuell programmering av robotarnas exekveringsplaner behövs. Istället, som det visas i denna avhandling, kan deras beteende genereras automatiskt från en given målspecifikation. Detta utgör fundamentet för att ge en formell garanti att det resulterande beteendet är optimalt och uppdragsmålspecifikationen är uppfylld. Därför skapar det möjlighet att använda dessa robotar i alltmer sofistikerade scenarier. Väldefinierade robotkompetenser med relativt låg komplexitet kan utvecklas oberoende av ett specifikt mål på hög nivå och sedan sammansättas automatiskt med hjälp av en beteendeplanerare för att uppnå komplexa mål på ett verifierbar korrekt sätt. Om det handlar om flera robotar så introduceras ytterligare planeringskomplexitet som är betydande. Inte bara åtgärder behöver planeras, men även fördelning av uppdragets olika delar till de enskilda robotarna måste hanteras. Traditionellt anses planering och allokering som två oberoende problem som kräver att man löser ett exponentiellt antal planeringsproblem, eller så leder formuleringen av en gemensam modell för hela gruppen till ett produkttillståndsutrymme mellan robotarna. Den resulterande exponentiella komplexiteten förhindrar att de flesta befintliga metoderna är praktiskt användbara i mer komplexa och realistiska scenarier. I denna avhandling presenteras ett tillvägagångssätt för att utnyttja samspelet mellan allokering och planering, som undviker exponentiell komplexitet för oberoende exekverbara delar av uppdragsspecifikationen. Dessutom presenteras ett tillvägagångssätt för att automatiskt identifiera dessa oberoende delar när endast en enda målspecifikation ges för arbetslaget. Detta har potential att förbättra effektiviteten för att hitta en optimal lösning och är ett viktigt steg mot tillämpningen av formell multi-robot-beteendeplanering för realistiska problem. Effektiviteten av de föreslagna metoderna illustreras därför i experiment baserade på en befintlig kontorsmiljö och i realistiska scenarier. / <p>QC 20170928</p>

De nombreux systèmes hétérogènes sont complexes et critiques. Ces systèmes intègrent du logiciel et des composants matériels avec des interactions fortes entre ces composants. Dans ce contexte, il est devenu absolument nécessaire de développer des méthodologies et des techniques pour spéciier et valider ces systèmes.Dans l'ingénierie des systèmes, les exigences sont l'expression des besoins qu'un produit spécifique ou un service doit réaliser. Elles sont définies formellement à de nombreuses occasions dans l'ingénierie des systèmes complexes. Dans ce type de système, deux catégories d'exigence sont présentes : les exigences non-fonctionnelles telles que la performance et la fiabilité, les exigences fonctionnelles telles que la vivacité. Pour valider ces exigences, un environnement permettant de simuler et vérifier ces propriétés est essentiel.Dans notre travail, nous proposons une méthodologie basée sur SysML et combinée avec SystemC et Promela/SPIN pour spéciier et valider des systèmes complexes. Cette approche est basée sur l'ingénierie dirigée par les modèles pour premièrement traduire des modèles SysML en SystemC afin de réaliser des simulations et deuxièmement traduire des diagrammes d'état SysML en Promela/SPINain de vérifier des propriétés temporelles extraites des exigences. Cette approche est expérimentée sur une étude de cas pour démontrer sa faisabilité. / Heterogeneous Systems are complex and become very critical. These systems integrate software andhardware components with intensive interaction between them. In this context, there is a strongnecessity to develop methodologies and techniques to specify and validate these systems.In engineering, the requirements are the expression of needs on what a particular product or a serviceshould be or to make. They are used most of the time in a formal sense in the systems engineering.In this kind of systems, several types of requirements are present: non-functional requirements suchas the performance and the reliability and functional requirements such as the liveliness. To validatethese requirements of a system, an environment to simulate and to check the properties is essential.In our work, we propose a methodology based on SysML combined with SystemC and Promela/SPINto specify and validate complex systems. This approach is based on Model Driven Engineeringtechniques to irstly translate SysML models to systemC with the aim of simulation and to mapSysML behavioral diagrams to Promela/SPIN in order to verify temporal properties extracted fromthe requirements. The approach is experimented on case studies to demonstrate its feasibility.

Cette thèse introduit différentes méthodes de vérification (ou model-checking) sur des modèles de systèmes à pile. En effet, les systèmes à pile (pushdown systems) modélisent naturellement les programmes séquentiels grâce à une pile infinie qui peut simuler la pile d'appel du logiciel. La première partie de cette thèse se concentre sur la vérification sur des systèmes à pile de la logique HyperLTL, qui enrichit la logique temporelle LTL de quantificateurs universels et existentiels sur des variables de chemin. Il a été prouvé que le problème de la vérification de la logique HyperLTL sur des systèmes d'états finis est décidable ; nous montrons que ce problème est en revanche indécidable pour les systèmes à pile ainsi que pour la sous-classe des systèmes à pile visibles (visibly pushdown systems). Nous introduisons donc des algorithmes d'approximation de ce problème, que nous appliquons ensuite à la vérification de politiques de sécurité. Dans la seconde partie de cette thèse, dans la mesure où la représentation de la pile d'appel par les systèmes à pile est approximative, nous introduisons les systèmes à surpile (pushdown systems with an upper stack) ; dans ce modèle, les symboles retirés de la pile d'appel persistent dans la zone mémoire au dessus du pointeur de pile, et peuvent être plus tard écrasés par des appels sur la pile. Nous montrons que les ensembles de successeurs post* et de prédécesseurs pre* d'un ensemble régulier de configurations ne sont pas réguliers pour ce modèle, mais que post* est toutefois contextuel (context-sensitive), et que l'on peut ainsi décider de l'accessibilité d'une configuration. Nous introduisons donc des algorithmes de sur-approximation de post* et de sous-approximation de pre*, que nous appliquons à la détection de débordements de pile et de manipulations nuisibles du pointeur de pile. Enfin, dans le but d'analyser des programmes avec plusieurs fils d'exécution, nous introduisons le modèle des réseaux à piles dynamiques synchronisés (synchronized dynamic pushdown networks), que l'on peut voir comme un réseau de systèmes à pile capables d'effectuer des changements d'états synchronisés, de créer de nouveaux systèmes à piles, et d'effectuer des actions internes sur leur pile. Le problème de l'accessibilité étant naturellement indécidable pour un tel modèle, nous calculons une abstraction des chemins d'exécutions entre deux ensembles réguliers de configurations. Nous appliquons ensuite cette méthode à un processus itératif de raffinement des abstractions. / In this thesis, we propose different model-checking techniques for pushdown system models. Pushdown systems (PDSs) are indeed known to be a natural model for sequential programs, as they feature an unbounded stack that can simulate the assembly stack of an actual program. Our first contribution consists in model-checking the logic HyperLTL that adds existential and universal quantifiers on path variables to LTL against pushdown systems (PDSs). The model-checking problem of HyperLTL has been shown to be decidable for finite state systems. We prove that this result does not hold for pushdown systems nor for the subclass of visibly pushdown systems. Therefore, we introduce approximation algorithms for the model-checking problem, and show how these can be used to check security policies. In the second part of this thesis, as pushdown systems can fail to accurately represent the way an assembly stack actually operates, we introduce pushdown systems with an upper stack (UPDSs), a model where symbols popped from the stack are not destroyed but instead remain just above its top, and may be overwritten by later push rules. We prove that the sets of successors post* and predecessors pre* of a regular set of configurations of such a system are not always regular, but that post* is context-sensitive, hence, we can decide whether a single configuration is forward reachable or not. We then present methods to overapproximate post* and under-approximate pre*. Finally, we show how these approximations can be used to detect stack overflows and stack pointer manipulations with malicious intent. Finally, in order to analyse multi-threaded programs, we introduce in this thesis a model called synchronized dynamic pushdown networks (SDPNs) that can be seen as a network of pushdown processes executing synchronized transitions, spawning new pushdown processes, and performing internal pushdown actions. The reachability problem for this model is obviously undecidable. Therefore, we compute an abstraction of the execution paths between two regular sets of configurations. We then apply this abstraction framework to a iterative abstraction refinement scheme.

Dans ce mémoire, nous présentons l’utilisation de techniques de model-checking pour l’inférence de paramètres de réseaux de régulation génétique (GRN) et l’analyse formelle d’une voie de signalisation. Le coeur du mémoire est décrit dans la première partie, dans laquelle nous proposons une approche pour inférer les paramètres biologiques régissant les dynamiques de modèles discrets de GRN. Les GRN sont encodés sous la forme d’un méta-modèle, appelé GRN paramétré, de telle façon qu’une instance de paramètres définit un modèle discret du GRN initial. Sous réserve que les propriétés biologiques d’intérêt s’expriment sous la forme de formules LTL, les techniques de model-checking LTL sont combinées à celles d’exécution symbolique et de résolution de contraintes afin de sélectionner les modèles satisfaisant ces propriétés. L’enjeu est de contourner l’explosion combinatoire en terme de taille et de nombre de modèles discrets. Nous avons implémenté notre méthode en Java, dans un outil appelé SPuTNIk. La seconde partie décrit une collaboration avec des neuropédiatres, qui ont pour objectif de comprendre l’apparition du phénotype protecteur ou toxique des microglies (un type de macrophage du cerveau) chez les prématurés. Cette partie exploite un autre versant du model-checking, celui du modelchecking statistique, afin d’étudier un type de réseau biologique particulier : la voie de signalisation Wnt/β-caténine, qui permet la transmission d’un signal de l’extérieur à l’intérieur des cellules via une cascade de réactions biochimiques. Nous présentons ici l’apport du model-checker stochastique COSMOS, utilisant la logique stochastique à automate hybride (HASL), un formalisme très expressif nous permettant une analyse formelle sophistiquée des dynamiques de la voie Wnt/β-caténine, modélisée sous la forme d’un processus stochastique à événements discrets. / In this thesis, we present the use of model checking techniques for inference of parameters of Gene Regulatory Networks (GRNs) and formal analysis of a signalling pathway. In the first and main part, we provide an approach to infer biological parameters governing the dynamics of discrete models of GRNs. GRNs are encoded in the form of a meta-model, called Parametric GRN, such that a parameter instance defines a discrete model of the original GRN. Provided that targeted biological properties are expressed in the form of LTL formulas, LTL model-checking techniques are combined with symbolic execution and constraint solving techniques to select discrete models satisfying these properties. The challenge is to prevent combinatorial explosion in terms of size and number of discrete models. Our method is implemented in Java, in a tool called SPuTNIk. The second part describes a work performed in collaboration with child neurologists, who aim to understand the occurrence of toxic or protective phenotype of microglia (a type of macrophage in the brain) in the case of preemies. We use an other type of model-checking, the statistical model-checking, to study a particular type of biological network: the Wnt/β- catenin pathway that transmits an external signal into the cells via a cascade of biochemical reactions. Here we present the benefit of the stochastic model checker COSMOS, using the Hybrid Automata Stochastic Logic (HASL), that is an very expressive formalism allowing a sophisticated formal analysis of the dynamics of the Wnt/β-catenin pathway, modelled as a discrete event stochastic process.

This thesis focuses on decision support for regional LTL carriers. The basic operating characteristics of regional LTL carriers are similar to those of national LTL carriers, i.e., they operate linehaul networks with satellites, breakbulks, and relays to consolidate freight so as to be able to cost-effectively serve their customers. However, there are also key differences. Most importantly, because the area covered by a regional carrier is smaller, a regional carrier handles less freight (sometimes significantly less) and therefore typically has fewer consolidation opportunities, which results in higher handling and transportation costs per unit of freight. Consequently, competing with national carriers on price is difficult. Therefore, to gain or maintain market share, regional carriers have to provide better service. To be able to provide better service, regional carriers have to be more dynamic, e.g., they have to be able to deviate from their load plan when appropriate, which creates challenges for decision makers. Regional carriers deliver about 60% of their shipments within a day and almost all of their shipments within two days. Furthermore, most drivers get back to their domicile at the end of each day. Therefore, the focus of the thesis is the development of effective and efficient decision models supporting daily operations of regional LTL carriers which provide excellent service at low cost. This thesis presents an effective solution approach based on two optimization models: a dynamic load planning model and a driver assignment model. The dynamic load planning model consists of two parts: an integer program to generate the best paths for daily origin-destination freight volumes and an integer program to pack freight into trailers and trailers into loads, and to determine dispatch times for these loads. Techniques to efficiently solve these integer program solution are discussed in detail. The driver assignment model is solved in multiple stages, each stage requiring the solution of a set packing models in which columns represent driver duties. Each stages determines admissible driver duties. The quality and efficiency of the solution approach are demonstrated through a computational study with real-life data from one of the largest regional LTL carriers in the country. An important "technique" for reducing driver requirements is the use of meet-and-turn operations. A basic meet-and-turn operation involves two drivers meeting at a location in between terminals and exchange trucks. A parking lot or a rest area suffices as a meet-and-turn location. This ensures that drivers return to the terminal where they started. More sophisticated meet-and-turn operations also exist, often called drop and hook operations. In this case, drivers do not exchange trucks, but one of their trailers. The motivation in this case is not to get drivers back to their domicile, but to reduce load- miles. The thesis presents analytical results quantifying the maximum benefits of using meet and turn operations and optimization techniques for identifying profitable meet-and-turn opportunities.

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-08-22T19:52:23Z No. of bitstreams: 1 ANA EMÍLIA VICTOR BARBOSA - DISSERTAÇÃO PPGCC 2007..pdf: 1669761 bytes, checksum: f47054507fe9200c8d1d56d2848ae276 (MD5) / Made available in DSpace on 2018-08-22T19:52:23Z (GMT). No. of bitstreams: 1 ANA EMÍLIA VICTOR BARBOSA - DISSERTAÇÃO PPGCC 2007..pdf: 1669761 bytes, checksum: f47054507fe9200c8d1d56d2848ae276 (MD5) Previous issue date: 2007-04-20 / Capes / Neste trabalho propomos uma técnica que visa detectar violações de propriedades comportamentais automaticamente durante a execução de sistema de software concorrentes. A técnica foi inspirada na metodologia de desenvolvimento Design by Contract (DbC). DbC permite que os desenvolvedores adicionem aos programas asserções para que sejam verificadas em tempo de execução. O uso de asserções para expressar propriedades de programas concorrentes (multithreaded)eparalelos, entretanto,não ésuficiente. Nesses sistemas,muitas das propriedades comportamentais de interesse, como vivacidade e segurança, não podem ser expressas apenas com asserções. Essas propriedades requerem o uso de operadores temporais. Neste trabalho, utilizamos Lógica Linear Temporal (Linear Time Logic - LTL) para expressar o comportamento desejado. Para dar suporte a checagem do comportamento dos programas em tempo de execução, propomos uma técnica baseada em Programação Orientada a Aspectos, que permite que o programa seja continuamente monitorado (o comportamento é checado através do uso de autômatos que permite a deteção de comportamentos inesperados). Associada a cada propriedade comportamental existe um conjunto de pontos de interesse do código-fonte que devem obedece-la. Esses pontos são então monitorados durante a execução do sistema através do uso de aspectos. Entre outros benefícios, a técnica permite que o sistema de software alvo seja instrumentado de maneira não intrusiva, sem alterar o código-fonte — particulamente, nenhum código do software alvo deve ser modificado para execução da monitoração. Para validar este trabalho, desenvolvemos como prova de conceitos um protótipo que implementa a técnica e permite a monitoração de programas Java multi-threaded, chamado DesignMonitor. Essa ferramenta é apresentada e discutida através de um estudo de caso para demonstrar a aplicação da técnica / In this work we propose and develop a technique that allows to detect the violation of behavior properties of concurrent systems. The technique was inspired by the Design by Contract (DbC) programming methodology, which proposes the use of assertions and their evaluation at runtime to check programs behavior. The use of simple assertions to express properties of concurrent and parallel programs, however, is not sufficient. Many of the relevant properties of those systems,s uch as liveness and security, can not be expressed with simple assertions. Thesepropertiesrequiretheuseof temporal operators. In our work, we used Linear Time Logic (LTL) to specify the expected behavior. To support the runtime checking of the program against the expected behavior, we propose a technique, based on Aspect-Oriented Programming, that allows the program to be continuously monitored (behavior is checked against automata that allows the detection of unexpected behaviors). Each property is mapped to a set of points of interest in the target program. Those points are then monitored during the system execution through aspects. Among other benefits, the technique allows the instrumentation of the target software to be performed automatically and in a non-intrusive way — in particular, no code must be changed toturn monitoring on or off. To validate the work, we developed a proof of concept prototype tool that implements the technique and allows the monitoring of multi-threaded Java programs, called DesignMonitor. The tool was used in case study that has allowed the evaluation and the discussion of practical issues related with the technique.

Les systèmes logiciels sont devenus omniprésents se substituant à l'homme pour des tâches délicates, souvent critiques, mettant en jeu des coûts importants voire des vies humaines. Les conséquences des défaillances imposent la recherche de méthodes rigoureuses pour la validation. L'approche par automates du model-checking est la plus classique des approches de vérification automatique. Elle prend en entrée un modèle du système et une propriété, et permet de savoir si cette dernière est vérifiée. Pour cela un model-checker traduit la négation de la propriété en un automate et vérifie si le produit du système et de cet automate est vide. Hélas, bien qu'automatique, cette approche souffre d'une explosion combinatoire du nombre d'états du produit.Afin de combattre ce problème, en particulier lors de la vérification des propriétés insensibles au bégaiement, nous proposons la première évaluation d'automates testeur (TA) sur des modèles réalistes, une amélioration de l'algorithme de vérification pour ces automates et une méthode permettant de transformer un TA en un automate (STA) permettant une vérification en une seule passe.Nous proposons aussi une nouvelle classe d'automates: les TGTA. Ces automates permettent une vérification en une seule passe sans ajouter d'états artificiels. Cette classe combine les avantages des TA et des TGBA (automates de Büchi). Les TGTA permettent d'améliorer les approches explicite et symbolique de model-checking. Notamment, en combinant les TGTA avec la saturation, les performances de l'approche symbolique sont améliorées d'un ordre de grandeur par rapport aux TGBA. / Software systems have become ubiquitous in our everyday life. They replace humans for critical tasks that involve high costs and even human lives. The serious consequences caused by the failure of such systems make crucial the use of rigorous methods for system validation. One of the widely-used formal verification methods is the automata-theoretic approach to model checking. It takes as input a model of the system and a property, and answers if the model satisfies or not the property. To achieve this goal, it translates the negation of the property in an automaton and checks whether the product of the model and this automaton is empty. Although it is automatic, this approach suffers from the combinatorial explosion of the resulting product. To tackle this problem, especially when checking stutter-invariant LTL properties, we firstly improve the two-pass verification algorithm of Testing automata (TA), then we propose a transformation of TA into a normal form (STA) that only requires a single-pass verification algorithm.
 We also propose a new type of automata: the TGTA. These automata also enable a check in a single-pass and without adding artificial states : it combines the benefits of TA and generalized Büchi automata (TGBA). TGTA improve the explicit and symbolic model checking approaches. In particular, by combining TGTA with the saturation technique, the performances of the symbolic approach has been improved by an order of magnitude compared to TGBA. Used in hybrid approaches TGTA prove complementary to TGBA.
 All the contributions of this work have been implemented in SPOT and LTS-ITS, respectively, an explicit and a symbolic open source model-checking libraries.

Learning-based testing is a testing paradigm that combines model-based testing with machine learning algorithms to automate the modeling of the SUT, test case generation, test case execution and verdict construction. A tool that implements LBT been developed at the CSC school at KTH called LBTest. LBTest utilizes machine learning algorithms with off-the-shelf equivalence- and model-checkers, and the modeling of user requirements by propositional linear temporal logic. In this study, it is be investigated whether LBT may be suitable for testing a micro bus architecture within an embedded telecommunication device. Furthermore ideas to further automate the testing process by designing a data model to automate user requirement generation are explored. / Inlärningsbaserad testning är en testningsparadigm som kombinerar model-baserad testning med maskininlärningsalgoritmer för att automatisera systemmodellering, testfallsgenering, exekvering av tester och utfallsbedömning. Ett verktyg som är byggt på LBT är LBTest, utvecklat på CSC skolan på KTH. LBTest nyttjar maskininlärningsalgoritmer med färdiga ekvivalent- och model-checkers, och modellerar användarkrav med linjär temporal logik. I denna studie undersöks det om det är lämpat att använda LBT för att testa en mikrobus arkitektur inom inbyggda telekommunikationsenheter. Utöver det undersöks även hur testprocessen skulle kunna ytterligare automatiseras med hjälp av en data modell för att automatisera generering av användarkrav.