Dissertations / Theses on the topic 'Reachability Analysi'
To see the other types of publications on this topic, follow the link: Reachability Analysi.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Reachability Analysi.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Jouda, Fatma, and Sagar Mehdi. "Safety Verification in Vehicle Test Applications : Using Reachability Analysis With the Focus on Reachability Tools." Thesis, Högskolan i Halmstad, Halmstad Embedded and Intelligent Systems Research (EIS), 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:hh:diva-38947.
Full text
2
Hui, Daniel Hang-Yan. "Protocol validation via reachability analysis : an implementation." Thesis, University of British Columbia, 1985. http://hdl.handle.net/2429/24689.
Full textAbstract:
Reachability analysis is one of the earliest and most common techniques for protocol validation. It is well suited to checking the protocol syntactic properties since they are a direct consequence of the structure of the reachability tree. However, validations of unbounded protocols via reachability analysis always lead to the "state explosion" problem. To overcome this, a new approach in reachability analysis has been proposed by Vuong et al [Vuong 82a, 83a]. While not loosing any information on protocol syntactic properties, the Teachability tree constructed by the new approach for all non-FIFO and for a particular set of FIFO protocols (called well-ordered protocols) will become finite. This thesis is concerned with the implementation of an integrated package called VALIRA (VALIdation via Reachability Analysis) which bases on both the proposed technique and the conventional technique. Details and implementation of the various approaches used in VALIRA are presented in order to provide an insight to the package. Various features of the package are demonstrated with examples on different types of protocols, such as the FIFO, the non-FIFO, and the priority protocols. The use of VALIRA was found to be practical in general, despite some limitations of the package. Further enhancements on the VALIRA are also suggested.Science, Faculty of
Computer Science, Department of
Graduate
3
Lång, Magnus. "Sound and Complete Reachability Analysis under PSO." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-213286.
Full textAbstract:
Modern multiprocessor systems use weak (relaxed) memory models in order to execute memory sharing multi-threaded code in an efficient manner, but are much harder for programmers to reason about than systems using the sequential consistency memory model. The SB abstraction and its implementation in the Memorax tool allows sound and complete checking of control state reachability under the TSO memory model, used in modern x86 processors. In this paper, I present a formalisation of the PSO memory model using the semantics of the Sun SPARC documentation and an alternate semantic, called Partial Write Serialisation, I conjecture to be equivalent with my formalisation under the control state reachability problem. PWS is proved to be a well-structured system which allows sound and complete reachability analysis. An implementation of PWS is presented as part of the Memorax tool and demonstrated experimentally to be capable of analysing reachability and inferring minimal fence sets on many non-trivial and real world examples in reasonable time and memory usage.
4
Ganesan, Sudakshin. "Real Time Reachability Analysis for Marine Vessels." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-247878.
Full textAbstract:
Safety verification of continuous dynamical systems require the computationof the reachable set. The reachable set comprises those states the systemcan reach at a specific point in time. The present work aims to compute thisreachable set for the marine vessel, in the presence of uncertainties in thedynamic modeling of the system and in the presence of external disturbancesin the form of wind, waves and currents. The reachable set can then be usedto check if the vessel collides with an obstacle. The dynamic model used isthat of a nonlinear maneuvering model for the marine vessel. The dynamicson the azipod actuators are also considered.Several methods are considered to solve the reachability problem for themarine vessel. The first method considered is that of the Hamilton JacobiReachability analysis, where a dynamic game between the control input andthe disturbance input is played. This results in a dynamic programmingproblem known as the Hamilton Jacobi Bellman Isaacs (HJBI) equation. Itis solved using the Level-Set method, but it suffers from the curse of dimensionality.The other method considered is the use of set-theoretic approach,where an over-approximation of the reachable set is computed, in the contextof safety verification. But on the downside, large sets of admissible controlyields highly over-approximated reachable sets, which cannot be usedIn order to overcome the disadvantages posed by the first two methods,emphasizing on the real-time computation, a third method is developed, wherea supervised classification algorithm is used to compute the reachable setboundary. The dataset required for the classification algorithm is computedby solving a 2 Point Boundary Value Optimal Control Problem for the marinevessel. The features for classification algorithm can be extended, so as toinclude the uncertainties and disturbances in the system. The computationtime is greatly reduced and the accuracy of the method is comparable to theexact reachable set computation.Säkerhetsverifiering av kontinuerliga dynamiska system kräver beräkningav mängden av tillstånd som kan nås vid en specifik tidpunkt, givet dess initialtillstånd.Detta arbete fokuserar påatt bestämma denna mängd av nåbaratillstånd för ett marint fartyg under modellosäkerheter och externa störningari form av vind, vågor och strömmar. Den nåbara mängden av tillstånd användssedan för att kontrollera om fartyget riskerar att kollidera med hinder.Den dynamiska modell som används i våra studier är en icke-linjär modelldär även dynamiken hos azipod-ställdonen betraktas.Arbetet studerar flera metoder för att lösa problemet: en klassisk Hamilton-Jacobi nåbarhetsanalys, en mängd-teoretisk teknik, samt en ny metod baseradpåmaskininlärning. Numeriska simuleringsstudier bekräftar att den föreslagnamaskininlärningsmetoden är snabbare än de tvåalternativen.
5
Hollingum, Nicholas. "On the Practice and Application of Context-Free Language Reachability." Thesis, The University of Sydney, 2017. http://hdl.handle.net/2123/17866.
Full textAbstract:
The Context-Free Language Reachability (CFL-R) formalism relates to some of the most important computational problems facing researchers and industry practitioners. CFL-R is a generalisation of graph reachability and language recognition, such that pairs in a labelled graph are reachable if and only if there is a path between them whose labels, joined together in the order they were encountered, spell a word in a given context-free language. The formalism finds particular use as a vehicle for phrasing and reasoning about program analysis, since complex relationships within the data, logic or structure of computer programs are easily expressed and discovered in CFL-R. Unfortunately, The potential of CFL-R can not be met by state of the art solvers. Current algorithms have scalability and expressibility issues that prevent them from being used on large graph instances or complex grammars. This work outlines our efforts in understanding the practical concerns surrounding CFL-R, and applying this knowledge to improve the performance of CFL-R applications. We examine the major difficulties with solving CFL-R-based analyses at-scale, via a case-study of points-to analysis as a CFL-R problem. Points-to analysis is fundamentally important to many modern research and industry efforts, and is relevant to optimisation, bug-checking and security technologies. Our understanding of the scalability challenge motivates work in developing practical CFL-R techniques. We present improved evaluation algorithms and declarative optimisation techniques for CFL-R, capitalising on the simplicity of CFL-R to creating fully automatic methodologies. The culmination of our work is a general-purpose and high-performance tool called Cauliflower, a solver-generator for CFL-R problems. We describe Cauliflower and evaluate its performance experimentally, showing significant improvement over alternative general techniques.
6
Ausmees, Kristiina. "Zone-Based Reachability Analysis of Dense-Timed Pushdown Automata." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-179802.
Full textAbstract:
Proving that programs behave correctly is a matter of both great theoretical interest as well as practical use. One way to do this is by analyzing a model of the system in question in order to determine if it meets a given specification. Real-time recursive systems can be modeled by dense-timed pushdown automata, a model which combines the behaviours of classical timed automata and pushdown automata. The problem of reachability has been proven to be decidable for this model. The algorithm that solves this problem relies on constructing a classical pushdown automaton that mimics the behaviour of a given timed pushdown automaton by means of an abstraction that uses regions as a symbolic representation of states. The drawback of this approach is that the untimed automaton produced generally contains a very large number of states. This report proposes a method of generalizing this abstraction by using zones instead of regions, in order to minimize the number of states in the untimed automaton.
7
Yan, Chao. "Projectagon-based reachability analysis for circuit-level formal verification." Thesis, University of British Columbia, 2011. http://hdl.handle.net/2429/37135.
Full textAbstract:
This dissertation presents a novel verification technique for analog and mixed signal circuits. Analog circuits are widely used in many applications include consumer electronics, telecommunications, medical electronics. Furthermore, in deep sub-micron design, physical effects might undermine common digital abstractions of circuit behavior. Therefore, it is necessary to develop systematic methodologies to formally verify hardware design using circuit-level models. We present a formal method for circuit-level verification. Our approach is based on translating verification problems to reachability analysis problems. It applies nonlinear ODEs to model circuit dynamics using modified nodal analysis. Forward reachable regions are computed from given initial states to explore all possible circuit behaviors. Analog properties are checked on all circuit states to ensure full correctness or find a design flaw. Our specification language extends LTL logic with continuous time and values and applies Brockett’s annuli to specify analog signals. We also introduced probability into the specification to support practical analog properties such as metastability behavior.
We developed and implemented a reachability analysis tool COHO for a simple class of moderate-dimensional hybrid systems with nonlinear ODE dynamics. COHO employs projectagons to represent and manipulate moderate-dimensional, non-convex reachable regions. COHO solves nonlinear ODEs by conservatively approximating ODEs as linear differential inclusions. COHO is robust and efficient. It uses arbitrary precision rational numbers to implement exact computation and trims projectagons to remove infeasible regions. To improve performance and reduce error, several techniques are developed, including a guess-verify strategy, hybrid computation, approximate algorithms, and so on.
The correctness and efficiency of our methods have been demonstrated by the success of verifying several circuits, including a toggle circuit, a flip-flop circuit, an arbiter circuit, and a ring-oscillator circuit proposed by researchers from Rambus Inc. Several important properties of these circuits have been verified and a design flaw was spotted during the toggle verification. During the reachability computation, we recognized new problems (e.g., stiffness) and proposed our solutions to these problems. We also developed new methods to analyze complex properties such as metastable behaviors. The combination of these methods and reachability analysis is capable of verifying practical circuits.
8
Lin, Yi-Tzer. "Modeling and analysis for message reachability in distributed manufacturing systems." Diss., Georgia Institute of Technology, 1994. http://hdl.handle.net/1853/24292.
Full text
9
Scott, Joseph Kirk. "Reachability analysis and deterministic global optimization of differential-algebraic systems." Thesis, Massachusetts Institute of Technology, 2012. http://hdl.handle.net/1721.1/76539.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Chemical Engineering, 2012.This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (p. 447-460).
Systems of differential-algebraic equations (DAEs) are used to model an incredible variety of dynamic phenomena. In the chemical process industry in particular, the numerical simulation of detailed DAE models has become a cornerstone of many core activities including, process development, economic optimization, control system design and safety analysis. In such applications, one is primarily interested in the behavior of the model solution with respect variations in the model inputs or uncertainties in the model itself. This thesis addresses two computational problems of general interest in this regard. In the first, we are interested in computing a guaranteed enclosure of all solutions of a given DAE model subject to a specified set of inputs. This analysis has natural applications in uncertainty quantification and process safety verification, and is used for many important tasks in process control. However, for nonlinear dynamic systems, this task is very difficult. Existing methods apply only to ordinary differential equation (ODE) models, and either provide very conservative enclosures or require excessive computational effort. Here, we present new methods for computing interval bounds on the solutions of ODEs and DAEs. For ODEs, the focus is on efficient methods for using physical information that is often available in applications to greatly reduce the conservatism of existing methods. These methods are then extended for the first time to the class of semi-explicit index-one DAEs. The latter portion of the thesis concerns the global solution of optimization problems constrained by DAEs. Such problems arise in optimal control of batch processes, determination of optimal start-up and shut-down procedures, and parameter estimation for dynamic models. In nearly all conceivable applications, there is significant economic and/or intellectual impetus to locate a globally optimal solution. Yet again, this problem has proven to be extremely difficult for nonlinear dynamic models. A small number of practical algorithms have been proposed, all of which are limited to ODE models and require significant computational effort. Here, we present improved lower-bounding procedures for ODE constrained problems and develop a complete deterministic algorithm for problems constrained by semi-explicit index-one DAEs for the first time.
by Joseph Kirk Scott.
Ph.D.
10
Chai, Xinwei. "Reachability Analysis and Revision of Dynamics of Biological Regulatory Networks." Thesis, Ecole centrale de Nantes, 2019. http://www.theses.fr/2019ECDN0014/document.
Full textAbstract:
Les systèmes concurrents sont un bon choix pour ajuster les données et analyser les mécanismes sous-jacents pour leur sémantique simple mais expressive. Cependant, l’apprentissage et l’analyse de tels systèmes concurrents sont difficiles pour ce qui concerne les calculs. Lorsqu’il s’agit de grands ensembles de données, les techniques les plus récentes semblent insuffisantes, que ce soit en termes d’efficacité ou de précision. Ici, nous proposons un cadre de modélisation raffiné ABAN (Asynchronous Binary Automata Network) et développons des outils pour analyser l’atteignabilité : PermReach (Reachability via Permutation search) et ASPReach (Reachability via Answer Set Programming). Nous proposons ensuite deux méthodes de construction et d’apprentissage des modèles: CRAC (Completion via Reachability And Correlations) et M2RIT (Model Revision via Reachability and Interpretation Transitions) en utilisant des données continues et discrètes pour s’ajuster au modèle et des propriétés d’accessibilité afin de contraindre les modèles en sortieConcurrent systems become a good choice to fit the data and analyze the underlying mechanics for their simple but expressive semantics. However, learning and analyzing such concurrent systems are computationally difficult. When dealing with big data sets, the state-of-the-art techniques appear to be insufficient, either in term of efficiency or in term of precision. In this thesis, we propose a refined modeling framework ABAN (Asynchronous Binary Automata Network) and develop reachability analysis techniques based on ABAN: PermReach (Reachability via Permutation search) and ASPReach (Reachability via Answer Set Programming). Then we propose two model learning/constructing methods: CRAC (Completion via Reachability And Correlations) and M2RIT (Model Revision via Reachability and Interpretation Transitions) using continuous and discrete data to fit the model and using reachability properties to constrain the output models
11
Agrawal, Akash. "Static Analysis to improve RTL Verification." Thesis, Virginia Tech, 2017. http://hdl.handle.net/10919/75293.
Full textAbstract:
Integrated circuits have traveled a long way from being a general purpose microprocessor to an application specific circuit. It has become an integral part of the modern era of technology that we live in. As the applications and their complexities are increasing rapidly every day, so are the sizes of these circuits. With the increase in the design size, the associated testing effort to verify these designs is also increased. The goal of this thesis is to leverage some of the static analysis techniques to reduce the effort of testing and verification at the register transfer level. Studying a design at register transfer level gives exposure to the relational information for the design which is inaccessible at the structural level.
In this thesis, we present a way to generate a Data Dependency Graph and a Control Flow Graph out of a register transfer level description of a circuit description. Next, the generated graphs are used to perform relation mining to improve the test generation process in terms of speed, branch coverage and number of test vectors generated. The generated control flow graph gives valuable information about the flow of information through the circuit design. We are using this information to create a framework to improve the branch reachability analysis mainly in terms of the speed. We show the efficiency of our methods by running them through a suite of ITC'99 benchmark circuits.Master of Science
12
McManus, Stephen C. "Predicting host level reachability via static analysis of routing protocol configuration." Thesis, Monterey, Calif. : Naval Postgraduate School, 2007. http://bosun.nps.edu/uhtbin/hyperion-image.exe/07Sep%5FMcManus.pdf.
Full textAbstract:
Thesis (M.S. in Computer Science)--Naval Postgraduate School, September 2007.Thesis Advisor(s): Xie, Geoffrey. "September 2007." Description based on title screen as viewed on October 24, 2007. Includes bibliographical references (p. 149). Also available in print.
13
Park, Jaeyong. "Safe Controller Design for Intelligent Transportation System Applications using Reachability Analysis." The Ohio State University, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=osu1366201401.
Full text
14
Karoui, Mohamed. "Surveillance des processus dynamiques évènementiels." Thesis, Grenoble, 2011. http://www.theses.fr/2011GRENT110/document.
Full textAbstract:
Dans le cadre de ce sujet de thèse, on s'intéresse à la surveillance des systèmes hybrides à forte dynamique événementielle. L'objectif est de détecter les défauts permanents et intermittents qui causent l'accélération et le ralentissement des tâches des systèmes. C'est dans ce contexte que se situent les principales contributions suivantes des travaux consignés dans la présente thèse : - Le développement d'une méthode de surveillance des processus basée sur les automates hybrides linéaires (AHL). Cette méthode consiste en premier lieu à l'établissement du modèle AHL du système dynamique en tenant compte des contraintes physiques et dynamiques de celui-ci. - La réalisation d'une analyse d'atteignabilité qui consiste à définir toutes les trajectoires pouvant amener le système à son objectif tout en respectant le cahier des charges qui lui est imposé. L'extension de l'approche en utilisant les automates hybrides rectangulaires. Cette sous-classe d'automates nous a permis de modéliser des systèmes plus complexes donc une modélisation hybride riche et a permis également une analyse formelle. Cette partie a été ponctuée par l'implémentation du système de surveillance qui consiste à déterminer les équations caractérisant chaque sommet de l'automate qui modélise le systèmeAs part of this thesis, we focus on the monitoring of hybrid systems with high dynamic event. The aim is to detect faults that cause permanent and intermittent acceleration and deceleration systems tasks. It is in this context that the following are the main contributions of the work reported in this thesis: - The development of a method for process monitoring based on linear hybrid automata (AHL). This method involves first the establishment of the AHL model the dynamic system taking into account the physical and dynamic one. - The realization of a reachability analysis of defining all paths that can cause the system to its target while respecting the specifications imposed on it. The extension of the approach using the rectangular hybrid automata. This class of controllers has allowed us to model more complex systems, therefore, a hybrid modeling rich and also allowed a formal analysis. This part was punctuated by the implementation of the monitoring system by determining equations characterizing each summit of the automaton that models the system
15
Kantz, Stephen M. "Static reachability analysis and validation regarding security policies implemented via packet filters." Thesis, Monterey, Calif. : Naval Postgraduate School, 2007. http://bosun.nps.edu/uhtbin/hyperion.exe/07Mar%5FKantz.pdf.
Full text
16
Lu, Kenneth K. (Kenneth Ke Wei) 1978. "Implementing a hazard elimination analysis tool for SpecTRM-RL using backwards reachability." Thesis, Massachusetts Institute of Technology, 2002. http://hdl.handle.net/1721.1/87253.
Full text
17
Roy, Tonmoy. "Reachability Analysis of RTL Circuits Using k-Induction Bounded Model Checking and Test Vector Compaction." Thesis, Virginia Tech, 2017. http://hdl.handle.net/10919/78801.
Full textAbstract:
In the first half of this thesis, a novel approach for k-induction bounded model checking using
signal domain constraints and property partitioning for proving unreachability of
branches in Verilog RTL code is presented. To do this, it approach
uses program slicing with
respect to the variables of the property under test to generate small-sized
SMT formulas that describe the change of variable values between
consecutive cycles. Variable substitution is then used on these
variables to generate the formula for the subsequent cycles without
traversing the abstract syntax tree of the entire design.
To reduce the approximation on the induction step, an addition of
signal domain constraints is proposed. Moreover, we present the technique for splitting up the
property in question to get a better model of the system.
The later half of the thesis is concerned with presenting a technique
for doing sequential vector compaction on test set generated during
simulation based ATPG. Starting with a compaction framework for storing
metadata and about the test vectors during generation, this work
presented to methods for findind the solution of this compaction problem.
The first of these two methods generate the optimum solution by converting
the problem appropriate for an optimization solver. The latter method
utilizes a heuristics based approach for solving the same problem which
generates a comparable but sub-optimal solution while having
magnitudes better time and computational efficiency.Master of Science
18
Heidenreich, Caroline. "Safe learning for control: Combining disturbance estimation, reachability analysis and reinforcement learning with systematic exploration." Thesis, KTH, Reglerteknik, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-214080.
Full textAbstract:
Learning to control an uncertain system is a problem with a plethora ofapplications in various engineering elds. In the majority of practical scenarios,one wishes that the learning process terminates quickly and does not violatesafety limits on key variables. It is particularly appealing to learn the controlpolicy directly from experiments, since this eliminates the need to rst derivean accurate physical model of the system. The main challenge when using suchan approach is to ensure safety constraints during the learning process.This thesis investigates an approach to safe learning that relies on a partlyknown state-space model of the system and regards the unknown dynamics asan additive bounded disturbance. Based on an initial conservative disturbanceestimate, a safe set and the corresponding safe control are calculated using aHamilton-Jacobi-Isaacs reachability analysis. Within the computed safe set avariant of the celebrated Q-learning algorithm, which systematically exploresthe uncertain areas of the state space, is employed to learn a control policy.Whenever the system state hits the boundary of the safe set, a safety-preservingcontrol is applied to bring the system back to safety. The initial disturbancerange is updated on-line using Gaussian Process regression based on the measureddata. This less conservative disturbance estimate is used to increase thesize of the safe set. To the best of our knowledge, this thesis provides the rstattempt towards combining these theoretical tools from reinforcement learningand reachability analysis to safe learning.We evaluate our approach on an inverted pendulum system. The proposedalgorithm manages to learn a policy that does not violate the pre-speciedsafety constraints. We observe that performance is signicantly improved whenwe incorporate systematic exploration to make sure that an optimal policy islearned everywhere in the safe set. Finally, we outline some promising directionsfor future research beyond the scope of this thesis.Maskininlärning för att uppnå en reglerstrategi för ett delvis okända systemär ett problem med en mångfald av tillämpningar i olika ingenjörvetenskapligaområden. I de esta praktiska scenarier vill man att inlärningsprocessen skaavsluta snabbt utan att bryta inte mot givna bivillkor. Särkild lockande är detatt lära in en reglerstrategi direkt från experiment eftersom man då kringgårnödvändigheten att härleda en exakt modell av systemet först. Den största utmaningenmed denna metod är att säkerställa att säkerhetsrelaterade bivillkorär uppfyllda under hela inlärningsprocessen.Detta examensarbete undersöker ett tillvägagångssätt att uppnå säker maskininlärning som bygger på en delvis känd modell av tillståndsrummet och betraktarde okända dynamikerna som en additiv begränsad störning. Baseratpå en initial konservativ uppskattning av störningen, beräknas en säker tillståndsmängd och en motsvarande reglerstragi genom använding av Hamilton-Jacobi-Isaacs nåbarhetsanalys. Inom den beräknade tillståndsmängden används en variant av Q-inlärning som systematiskt utforskar okända delar av tillståndsrummet för att lära in en reglerstrategi. När systemet stöter på gränsenav den säkra tillståndsmängden, tillämpas istället en säkerhetsbevarande reglerstrategiför att få systemet tillbaka till säkerhet. Den första uppskattningenav störningen uppdateras kontinuerligt genom Gaussprocessregression baseradpå uppmätt data. Nya, mindre konservativa uppskattningar används för attöka storleken på den säkra tillståndsmängden. Så vitt vi vet är detta examensarbetedet första försöket att kombinera dessa teoretiska metoder, frånförstärkningsinlärning och nåbarhetsanalys, för att uppnå säker inlärning.Vi utvärderar vår metod på ett inverterat pendelsystem. Den föreslagnaalgoritmen klarar av att lära in en reglerstrategi som inte bryter mot i förvägspecierade bivillkor. Vi iakttar att prestandan kan förbättras avsevärt om viintegrerar systematisk utforskning för att säkerställa att den optimala reglerstrateginlärs in överallt i den säkra tillståndsmängden. Slutligen diskuterar vinågra lovande inriktingar för framtida forskning utöver omfattningen av dettaarbete.
19
Lam, Huy Hong. "Discrete Transition System Model and Verification for Mitochondrially Mediated Apoptotic Signaling Pathways." Thesis, Virginia Tech, 2007. http://hdl.handle.net/10919/33802.
Full textAbstract:
Computational biology and bioinformatics for apoptosis have been gaining much momentum due to the advances in computational sciences. Both fields use extensive computational techniques and modeling to mimic real world behaviors. One problem of particular interest is on the study of reachability, in which the goal is to determine if a target state or protein concentration in the model is realizable for a signaling pathway. Another interesting problem is to examine faulty pathways and how a fault can make a previously unrealizable state possible, or vice versa. Such analysis can be extremely valuable to the understanding of apoptosis. However, these analyses can be costly or even impractical for some approaches, since they must simulate every aspect of the model.
Our approach introduces an abstracted model to represent a portion of the apoptosis signaling pathways as a finite state machine. This abstraction allows us to apply hardware testing and verification techniques and also study the behaviors of the system without full simulation. We proposed a framework that is tailor-built to implement these verification techniques for the discrete model. Through solving Boolean constraint satisfaction problems (SAT-based) and with guided stimulation (Genetic Algorithm), we can further extract the properties and behaviors of the system.
Furthermore, our model allows us to conduct cause-effect analysis of the apoptosis signaling pathways. By constructing single- and double-fault models, we are able to study what fault(s) can cause the model to malfunction and the reasons behind it. Unlike simulation, our abstraction approach allows us to study the system properties and system manipulations from a different perspective without fully relying on simulation. Using these observations as hypotheses, we aim to conduct laboratory experiments and further refine our model.Master of Science
20
Chen, Xin Verfasser], Erika [Akademischer Betreuer] [Ábrahám, and Sriram [Akademischer Betreuer] Sankaranarayanan. "Reachability analysis of non-linear hybrid systems using Taylor Models / Xin Chen ; Erika Ábrahám, Sriram Sankaranarayanan." Aachen : Universitätsbibliothek der RWTH Aachen, 2015. http://d-nb.info/1181107857/34.
Full text
21
Rocca, Alexandre. "Formal methods for modelling and validation of biological models." Thesis, Université Grenoble Alpes (ComUE), 2018. http://www.theses.fr/2018GREAM028/document.
Full textAbstract:
L’objectif de cette thèse est la modélisation et l’étude de systèmes biologiques par l’intermédiaire de méthodes formelles. Les systèmes biologiques démontrent des comportements continus mais sont aussi susceptibles de montrer des changements abrupts dans leur dynamiques. Les équations différentielles ordinaires, ainsi que les systèmes dynamiques hybrides, sont deux formalismes mathématiques utilisés pour modéliser clairement de tels comportements. Un point critique de la modélisation de systèmes biologiques est la recherche des valeurs des paramètres du modèle afin de reproduire de manière précise un ensemble de données expérimentales. Si aucun jeu de paramètres valides n’est trouvé, il est nécessaire de réviser le modèle. Une possibilité est alors de remplacer un paramètre, ou un ensemble de paramètres, définissant un processus biologique par une fonctiondépendante du temps.Dans le cadre de cette thèse, nous exposons tout d’abord une méthode pour la révision de modèles hybrides. Pour cela, nous proposons une approche gloutonne appliquée à une méthode de contrôle optimal utilisant les mesures d’occupations etla relaxation convexe. Ensuite, nous étudions comment analyser les propriétés dynamiques d’un modèle à temps discret en utilisant la simulation ensembliste. Dans cet objectif, nous proposons deux méthodes basées sur deux outils mathématiques.La première méthode, qui se repose sur les polynômes de Bernstein, est une extension aux systèmes dynamiques hybrides, de l’outil de calcul ensembliste Sapo [1]. La seconde méthode utilise les représentations de Krivine-Stengle [2] pour permettre l’analyse d’atteignaiblité de systèmes dynamiques polynomiaux. Enfin, nous proposons aussi une méthodologie pour générer des systèmes dynamiques hybrides modélisant des protocoles biologiques expérimentaux. Les méthodes précédemment proposées sont appliquées sur divers études biologiques. Nous étudions tout d’abord un modèle de la production d’hémoglobinedurant la différentiation des érythrocytes dans la moelle [3]. Pour permettre la construction de ce modèle, nous avons dans un premier temps généré un ensemble de jeux de paramètres valides à l’aide d’une méthode de type Monte-Carlo. Dans un second temps, nous avons appliqué la méthode de révision de modèle afin de reproduire plus précisément les données expérimentales [4]. Nous proposons aussi un modèle préliminaire des effets à faibles doses du Cadmium sur la réponse du métabolisme à différentes étapes de la vie d’un rat. Enfin, nous appliquons les techniques d’analyse ensembliste pour la validation d’hypothèses sur un modèle d’homéostasie du fer [6] dans le cas où des paramètres varient dans de larges intervalles.Dans cette thèse, nous montrons aussi que le protocole associé à l’étude de la production d’hémoglobine, ainsi que le protocole étudiant l’intégration du Cadmium durant la vie d’un rat, peuvent être formalisés comme des systèmes dynamiques hybrides, et servent ainsi de preuves de concepts pour notre méthode de modélisation de protocoles expérimentauxThe purpose of this thesis is the modelling and analysis of biological systems with mechanistic models (in opposition with black-box models).In particular we use two mathematical formalisms for mechanism modelling: hybrid dynamical systems and polynomial Ordinary Differential Equations (ODEs).Biological systems modelling give rise to numerous problem and in this work we address three of them.First, the parameters in the differential equations are often uncertain or unknown.Consequently, we aim at generating a subset of valid parameter sets such that the models satisfy constraints deducted from some experimental data.This problem is addressed in the literature under the denomination of parameter synthesis, parameter estimation, parameter fitting, or parameter identification following the context.Then, if no valid parameter is found, one solution is to revise the model. This can be done by substituting a law in place of a constant parameter.In the literature, models with uncertain parts are known as grey models, and their studies can be found under the term of model identification.Finally, it may be necessary to ensure the correctness of the built models using validation, or verification, methods for a continuous over-approximation of the determined valid parameters.In this thesis we study the parameter synthesis problem, in the Haemoglobin production model case study, using an adaptation of the classical method based on Monte-Carlo sampling, and numerical simulations.To perform model revision of hybrid dynamical systems we propose an iterative scheme of an optimal control method based on occupation measures, and convex relaxations.Finally, we assess the quality of a model using set-based simulations, and reachability analysis.For this purpose, we propose two methods: the first one, which relies on Bernstein expansion, is an extension for hybrid dynamical systems of the reachability tool sapo , while the other uses Krivine-Stengle representations to perform the reachability analysis of polynomial ODEs.We also provide a methodology to generate hybrid dynamical systems modelling biological experimental protocols.All of these proposed methods were applied in different case studies.We first propose a model of haemoglobin production during the differentiation of an erythrocyte in the bone marrow.To develop this model we first applied the Monte-Carlo based parameters synthesis, followed by the model revision to correctly fit to the experimental data.We also propose a hybrid model of Cadmium flux in rats in the context of an experimental protocol, as well as a preliminary study of the effect of low dose Cadmium on a Glucose response.Finally, we apply the reachability analysis techniques for the validation on large parameters set of the iron homoeostasis model developed by Nicolas Mobilia during his Phd.We note the haemoglobin production model, as well as the glucose reponse model can be formalised, in their experimental context, as hybrid dynamical systems. Thus, they serve as proof of concept for the methodology of biological experimental protocols modelling
22
Ben, Makhlouf Ibtissem [Verfasser]. "Comparative Evaluation and Improvement of Computational Approaches to Reachability Analysis of Linear Hybrid Systems / Ibtissem Ben Makhlouf." Aachen : Shaker, 2016. http://d-nb.info/1094396621/34.
Full text
23
Hanashi, Abdalla Musbah Omar. "Enhanced Probabilistic Broadcasting Scheme for Routing in MANETs. An investigation in the design analysis and performance evaluation of an enhanced probabilistic broadcasting scheme for on-demand routing protocols in mobile ad-hoc networks." Thesis, University of Bradford, 2009. http://hdl.handle.net/10454/4321.
Full textAbstract:
Broadcasting is an essential and effective data propagation mechanism with several important applications, such as route discovery, address resolution and many other network services. Though data broadcasting has many advantages, it can also cause a high degree of contention, collision and congestion, leading to what is known as 'broadcast storm problems'. Broadcasting has traditionally been based on the flooding protocol, which simply overflows the network with a high number of rebroadcast messages until these reach all the network nodes. A good probabilistic broadcast protocol can achieve high saved rebroadcast (SRB), low collision and a lower number of relays. When a node is in a sparse region of the network, rebroadcasting is relatively more important while the potential redundancy of rebroadcast is low because there are few neighbours which might rebroadcast the packet unnecessarily. Further, in such a situation, contention over the wireless medium resulting from Redundant broadcasts is not as serious as in scenarios with medium or high density node populations. This research proposes a dynamic probabilistic approach that dynamically fine-tunes the rebroadcast probability according to the number of neighbouring nodes distributed in the ad-hoc network for routing request packets (RREQs) without requiring the assistance of distance measurements or location-determination devices. The main goal of this approach is to reduce the number of rebroadcast packets and collisions in the network. The performance of the proposed approach is investigated and compared with simple AODV, fixed-probabilistic and adjusted-probabilistic flooding [1] schemes using the GloMoSim network simulator and a number of important MANET parameters, including node speed, traffic load and node density under a Random Waypoint (RWP) mobility model. Performance results reveal that the proposed approach is able to achieve higher SRB and less collision as well as a lower number of relays than fixed probabilistic, simple AODV and adjusted-probabilistic flooding. In this research, extensive simulation experiments have been conducted in order to study and analyse the proposed dynamic probabilistic approach under different mobility models. The mobility model is designed to describe the movement pattern of mobile customers, and how their position, velocity and acceleration change over time. In this study, a new enhanced dynamic probabilistic flooding scheme is presented. The rebroadcast probability p will be calculated dynamically and the rebroadcasting decision will be based on the average number of nodes in the ad-hoc networks. The performance of the new enhanced algorithm is evaluated and compared to the simple AODV, fixed-probabilistic, adjusted-probabilistic and dynamic-probabilistic flooding schemes. It is demonstrated that the new algorithm has superior performance characteristics in terms of collision, relays and SRB. Finally, the proposed schemes are tested and evaluated through a set of experiments under different mobility models to demonstrate the relative merits and capabilities of these schemes.
24
Hagemann, Willem [Verfasser], and Christoph [Akademischer Betreuer] Weidenbach. "Symbolic orthogonal projections : a new polyhedral representation for reachability analysis of hybrid systems / Willem Hagemann. Betreuer: Christoph Weidenbach." Saarbrücken : Saarländische Universitäts- und Landesbibliothek, 2015. http://d-nb.info/107952388X/34.
Full text
25
Pelletier, Vivien. "Sur-approximations non régulières et terminaison pour l’analyse d’accessibilité." Thesis, Orléans, 2017. http://www.theses.fr/2017ORLE2044/document.
Full textAbstract:
L’analyse d’accessibilité est une des composantes de l’analyse de modèles. Elle consiste à modéliser un système complexe par trois ensembles : le langage initial, le langage des configurations indésirables et un système de réécriture. Le langage initial et le langage des configurations indésirables sont des ensembles de termes. Un terme est un mot mais construit à partir de symboles d’arités supérieures à 1. Le système de réécriture représente la dynamique du système complexe. C’est un ensemble de règles qui permettent d’obtenir un nouveau terme à partir d’un terme original. Pour effectuer une analyse d’accessibilité à partir de cette modélisation, on peut calculer l’ensemble des configurations accessibles. Cet ensemble aussi appelé ensemble des descendants est obtenu en appliquant le système de réécriture sur le langage initial jusqu’à ne plus obtenir de nouveaux termes. Une fois l’ensemble des descendants calculé, il reste à faire l’intersection entre celui-ci et l’ensemble des configurations indésirables. Si cette intersection est vide, alors il n’y a pas de configuration indésirable accessible, sinon les configurations présentes dans cette intersection sont accessibles. Cependant, l’ensemble des descendants n’est pas calculable dans le cas général. Pour contourner ce problème, nous calculons une sur-approximation des descendants. Ainsi, si l’intersection est vide, cela signifie toujours qu’aucune configuration indésirable n’est accessible. A contrario, s’il existe un terme dans l’intersection, il n’est pas possible de déterminer s’il s’agit d’un faux positif ou d’une configuration indésirable accessible. La précision de la sur-approximation est alors déterminanteReachability analysis is part of model checking. It consists to model complex systems by three sets : initial language, unwanted configurations and rewrite system. The initial language and the unwanted configurations language are sets of terms. Terms are words which are construct with symbols that have an arity that can be greater than 1. The rewrite system represent the dynamic of the complex system. It is a set of rules that permit from a initial term to obtain a new term. One of the approaches to analyze reachability from this modelling is to compute the set of reachable configurations. This set which is called set of descendants is obtained by applying the rewrite system on the initial language until obtaining no more new terms. After the set of descendants is computed, we need to compute the intersection between this set and the unwanted configurations set. If this intersection is empty then there is no unwanted configuration reachable, else the configurations in this intersection are reachable. However, the set of descendants is not computable in the general case. To bypass this problem, we compute an over-approximation of descendants.Now, if the intersection is empty, we keep proving that no unwanted configuration is reachable. Nevertheless, if the intersection is not empty, it is not possible to know if it comes from false-positives or form unwanted reachable configurations. So, the precision of the over-approximation is decisive
26
Elguindy, Ahmed [Verfasser], Matthias [Akademischer Betreuer] Althoff, Matthias [Gutachter] Althoff, and Majid [Gutachter] Zamani. "Control and Stability of Power Systems using Reachability Analysis / Ahmed Elguindy ; Gutachter: Matthias Althoff, Majid Zamani ; Betreuer: Matthias Althoff." München : Universitätsbibliothek der TU München, 2017. http://d-nb.info/1160034672/34.
Full text
27
Schupp, Stefan [Verfasser], Erika [Akademischer Betreuer] Ábrahám, and Goran [Akademischer Betreuer] Frehse. "State set representations and their usage in the reachability analysis of hybrid systems / Stefan Schupp ; Erika Ábrahám, Goran Frehse." Aachen : Universitätsbibliothek der RWTH Aachen, 2019. http://d-nb.info/1220728993/34.
Full text
28
Basaran, Cuneyt. "Automated network protocol reachability analysis with supertrace algorithm and TESTGEN : automated generation of test sequence for a formal protocol specification." Thesis, Monterey, Calif. : Springfield, Va. : Naval Postgraduate School ; Available from National Technical Information Service, 1994. http://handle.dtic.mil/100.2/ADA280788.
Full text
29
Arslantas, Yunus Emre [Verfasser], Claus [Akademischer Betreuer] Braxmaier, Claus [Gutachter] Braxmaier, and Christof [Gutachter] Büskens. "Development of a Reachability Analysis Algorithm for Space Applications / Yunus Emre Arslantas ; Gutachter: Claus Braxmaier, Christof Büskens ; Betreuer: Claus Braxmaier." Bremen : Staats- und Universitätsbibliothek Bremen, 2017. http://d-nb.info/1149219939/34.
Full text
30
Ben, Makhlouf Ibtissem [Verfasser], Stefan [Akademischer Betreuer] Kowalewski, and Goran [Akademischer Betreuer] Frehse. "Comparative evaluation and improvement of computational approaches to reachability analysis of linear hybrid systems / Ibtissem Ben Makhlouf ; Stefan Kowalewski, Goran Frehse." Aachen : Universitätsbibliothek der RWTH Aachen, 2016. http://d-nb.info/1130326780/34.
Full text
31
Ben, Makhlouf Ibtissem Verfasser], Stefan [Akademischer Betreuer] Kowalewski, and Goran [Akademischer Betreuer] [Frehse. "Comparative evaluation and improvement of computational approaches to reachability analysis of linear hybrid systems / Ibtissem Ben Makhlouf ; Stefan Kowalewski, Goran Frehse." Aachen : Universitätsbibliothek der RWTH Aachen, 2016. http://d-nb.info/1130326780/34.
Full text
32
Bagri, Sharad. "Improving Branch Coverage in RTL Circuits with Signal Domain Analysis and Restrictive Symbolic Execution." Thesis, Virginia Tech, 2015. http://hdl.handle.net/10919/51625.
Full textAbstract:
Considerable research has been directed towards efficient test stimuli generation for Register Transfer Level (RTL) circuits. However, stimuli generation frameworks are still not capable of generating effective stimuli for all circuits. Some of the limiting factors are 1) It is hard to ascertain if a branch in the RTL code is reachable, and 2) Some hard-to-reach branches require intelligent algorithms to reach them.
Since unreachable branches cannot be reached by any test sequence, we propose a method to deduce unreachability of a branch by looking for the possible values which a signal can take in an RTL code without explicit unrolling of the design. To the best of our knowledge, this method has been able to identify more unreachable branches than any method published in this domain, while being computationally less expensive.
Moreover, some branches require very specific values on input signals in specific cycles to reach them. Conventional symbolic execution can generate those values but is computationally expensive. We propose a cycle-by-cycle restrictive symbolic execution that analyzes only a selected subset of program statements to reduce the computational cost. Our proposed method gathers information from an initial execution trace generated by any technique, to intelligently decide specific cycles where the application of this method will be helpful. This method can hybrid with simulation-based test stimuli generation methods to reduce the cost of formal verification. With this method, we were able to reach some previously unreached branches in ITC99 benchmark circuits.Master of Science
33
Zhang, Yingying. "Algorithms and Data Structures for Efficient Timing Analysis of Asynchronous Real-time Systems." Scholar Commons, 2013. http://scholarcommons.usf.edu/etd/4622.
Full textAbstract:
This thesis presents a framework to verify asynchronous real-time systems based on model checking. These systems are modeled by using a common modeling formalism named Labeled Petri-nets(LPNs).
In order to verify the real-time systems algorithmically, the zone-based timing analysis method is used for LPNs. It searches the state space with timing information (represented by zones). When there is a high degree of concurrency in the model, firing concurrent enabled transitions in different order may result in different zones, and these zones may be combined without affecting the verification result. Since the zone-based method could not deal with this problem efficiently, the POSET timing analysis method is adopted for LPNs. It separates concurrency from causality and generates an exactly one zone for a single state. But it needs to maintain an extra POSET matrix for each state. In order to save time and memory, an improved zone-based timing analysis method is introduced by integrating above two methods. It searches the state space with zones but eliminates the use of the POSET matrix, which generates the same result as with the POSET method. To illustrate these methods, a circuit example is used throughout the thesis.
Since the state space generated is usually very large, a graph data structure named multi-value decision diagrams (MDDs) is implemented to store the zones compactly. In order to share common clock value of dierent zones, two zone encoding methods are described: direct encoding and minimal constraint encoding. They ignore the unnecessary information in zones thus reduce the length of the integer tuples. The effectiveness of these two encoding methods is demonstrated by experimental result of the circuit example.
34
Al, Khatib Mohammad. "Analyse de stabilité, ordonnancement, et synthèse des systèmes cyber-physiques." Thesis, Université Grenoble Alpes (ComUE), 2017. http://www.theses.fr/2017GREAM041/document.
Full textAbstract:
Il s'agit d'une étude menée sur les systèmes cyber-physiques sur trois aspects principaux: la vérification de la stabilité, l'ordonnancement et la synthèse des paramètres. Les systèmes de contrôle embarqués (ECS) agissant dans le cadre de contrats temporels sont la classe considérée de systèmes cyber-physiques dans la thèse. ECS fait référence à des intégrations d'un dispositif informatique avec le système physique. En ce qui concerne les contrats temporels, ils sont des contraintes de temps sur les instants où se produisent certains événements tels que l'échantillonnage, l'actionnement et le calcul. Ces contrats sont utilisés pour modéliser les problèmes qui se posent dans les systèmes de contrôle modernes: incertitudes sur les retards d'actionnement, les périodes d'échantillonnage incertaines et l'interaction de plusieurs systèmes physiques avec des ressources informatiques partagées (CPUs). Maintenant, compte tenu d'un ECS et d'un contrat temporel, nous reformulons le système de manière impulsionnelle et vérifions la stabilité du système, sous toutes les incertitudes bornées et données par le contrat, en utilisant des techniques d'approximation convexe et de nouveaux résultats généralisés pour le problème sur une classe de systèmes modélisés dans le cadre des inclusions différentielles. Deuxièmement, compte tenu d'un ensemble de contrôleurs implémentés sur une plate-forme de calcul commune (CPUs), dont chacun est soumis à un contrat de synchronisation, et à son meilleur et son plus mauvais cas d'exécution dans chaque CPU, nous synthétisons une politique d’ordonnancement dynamique qui garantit que chaque contrat temporel est satisfait et que chacun des CPU partagés est attribué à au plus un contrôleur à tout moment. L'approche est basée sur une reformulation qui nous permet d'écrire le problème d’ordonnancement comme un jeu temporelle avec spécification de sureté. Ensuite, en utilisant l'outil UPPAAL-TIGA, une solution au jeu fournit une politique d’ordonnancement appropriée. En outre, nous fournissons une nouvelle condition nécessaire et suffisante pour l’ordonnancement des tâches de contrôle en fonction d’un jeu temporisé simplifiés. Enfin, nous résolvons un problème de synthèse de paramètres qui consiste à synthétiser une sous-approximation de l'ensemble des contrats de synchronisation qui garantissent en même temps l’ordonnancement et la stabilité des contrôleurs intégrés. La synthèse est basée sur un nouveau paramétrage du contrat temporel pour les rendre monotones, puis sur un échantillonnage à plusieurs reprises de l'espace des paramètres jusqu'à atteindre une précision d'approximation prédéfinieThis is a study conducted on cyber-physical systems on three main aspects: stability verification, scheduling, and parameter synthesis. Embedded control systems (ECS) acting under timing contracts are the considered class of cyber-physical systems in the thesis. ECS refers to integrations of a computing device with the physical system. As for timing contracts they are time constraints on the instants where some events happen such as sampling, actuation, and computation. These contracts are used to model issues that arise in modern embedded control systems: uncertain sampling to actuation delays, uncertain sampling periods, and interaction of several physical systems with shared computational resources (CPUs). Now given an ECS and a timing contract we reformulate the system into an impulsive one and verifies stability of the system, under all possible bounded uncertainties given by the contract, using safe convex approximation techniques and new generalized results for the problem on a class of systems modeled in the framework of difference inclusions. Second given a set of controllers implemented on a common computational platform (CPUs), each of which is subject to a timing contract, and best and worst case execution times on each CPU, we synthesize a dynamic scheduling policy, which guarantees that each timing contract is satisfied and that each of the shared CPUs are allocated to at most one embedded controller at any time. The approach is based on a timed game formulation that allows us to write the scheduling problem as a timed safety game. Then using the tool UPPAAL-TIGA, a solution to the safety game provides a suitable scheduling policy. In addition, we provide a novel necessary and sufficient condition for schedulability of the control tasks based on a simplified timed game automaton. Last, we solve a parameter synthesis problem which consists of synthesizing an under-approximation of the set of timing contracts that guarantee at the same time the schedulability and stability of the embedded controllers. The synthesis is based on a re-parameterization of the timing contract to make them monotonic, and then on a repeatedly sampling of the parameter space until reaching a predefined precision of approximation
35
Lalami, Abdelhalim. "Diagnostic et approches ensemblistes à base de zonotopes." Cergy-Pontoise, 2008. http://biblioweb.u-cergy.fr/theses/08CERG0377.pdf.
Full textAbstract:
Le diagnostic consiste à détecter, localiser et éventuellement identifier les défauts au sein d’un système. Un modèle ne représentant qu’imparfaitement la réalité, une prise en compte explicite des incertitudes est nécessaire pour mettre en oeuvre des techniques de redondance analytique conduisant à un diagnostic garanti. En s’appuyant sur une représentation déterministe des incertitudes (par des intervalles et, plus particulièrement, des zonotopes, une classe particulière de polytopes), l’objet de ce travail est double : proposer une spécification des modes de fonctionnement aussi proche que possible de la connaissance disponible, d’une part, assurer la correction logique entre la spécification des modes de fonctionnement et la décision fournie, d’autre part. En s’appuyant sur des algorithmes de calcul d’atteignabilité à base de zonotopes pour limiter les problèmes de dépendance et l’effet d’enveloppement, d’une part, sur des algorithmes de détection de collision, d’autre part, l’intérêt d’une re-formulation ensembliste de plusieurs techniques de génération de résidus (indicateurs de défauts) est mise en évidence non seulement pour la synthèse de tests implantés en ligne, mais aussi pour l’aide à la conception d’un système de diagnostic (choix de seuils, analyses de sensibilité). Les approches ensemblistes permettent d’introduire la notion de découplage dans les limites fixées par les bornes. Un nombre arbitrairement grand de perturbations peut ainsi être découplé parfaitement sans contrainte de rang. Les domaines calculés permettent de borner les incertitudes dans toutes les directions de l’espace et d’obtenir des sensibilités meilleures que celles résultant de techniques projectives ou d’élimination. Le travail effectué sur les calculs d’atteignabilité débouche quant à lui sur une ouverture vers la vérification de propriétés de sûreté dans les systèmes dynamiques hybridesFault diagnosis consists in detecting, isolating and possibly identifying the faults occurring in a system. As a model never perfectly represent the reality, the uncertainties have to be explicitly formalized in order to implement analytical redundancy approaches providing a guaranteed diagnosis. Based on a deterministic representation of uncertainties (by intervals and, more precisely, by zonotopes, a particular class of polytopes), this work follows two main objectives: proposing a specification of operating modes which is as close as possible to the available knowledge, and ensuring the logical soundness between the specification of the operating modes and the diagnosis decision. Using reachability algorithms based on zonotopes to control the dependency problem and the wrapping effect, on the one hand, using collision detection algorithms, on the other hand, the interest in a setmembership re-formulation of several residual generation methods is put into evidence not only to design on-line tests, but also to design and analyse the properties of a fault diagnosis system (adjustment of thresholds, sensitivity analysis). Set-membership approaches allow to introduce the notion of decoupling in the limits fixed by some bounds An arbitrary number of perturbations can then be perfectly decoupled without any rank constraint. The computed domains allow to bound the uncertainties in all the space directions and so obtain better sensitivities than those resulting from projective or elimination approaches. The work about reachability computations has lead to developments that are expected to be useful for the verification of safety properties of hybrid dynamical systems
36
Haziza, Frédéric. "Few is Just Enough! : Small Model Theorem for Parameterized Verification and Shape Analysis." Doctoral thesis, Uppsala universitet, Avdelningen för datorteknik, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-264171.
Full textAbstract:
This doctoral thesis considers the automatic verification of parameterized systems, i.e. systems with an arbitrary number of communicating components, such as mutual exclusion protocols, cache coherence protocols or heap manipulating programs. The components may be organized in various topologies such as words, multisets, rings, or trees. The task is to show correctness regardless of the size of the system and we consider two methods to prove safety:(i) a backward reachability analysis, using the well-quasi ordered framework and monotonic abstraction, and (ii) a forward analysis which only needs to inspect a small number of components in order to show correctness of the whole system. The latter relies on an abstraction function that views the system from the perspective of a fixed number of components. The abstraction is used during the verification procedure in order to dynamically detect cut-off points beyond which the search of the state-space need not continue. Our experimentation on a variety of benchmarks demonstrate that the method is highly efficient and that it works well even for classes of systems with undecidable property. It has been, for example, successfully applied to verify a fine-grained model of Szymanski's mutual exclusion protocol. Finally, we applied the methods to solve the complex problem of verifying highly concurrent data-structures, in a challenging setting: We do not a priori bound the number of threads, the size of the data-structure, the domain of the data to store nor do we require the presence of a garbage collector. We successfully verified the concurrent Treiber's stack and Michael & Scott's queue, in the aforementioned setting. To the best of our knowledge, these verification problems have been considered challenging in the parameterized verification community and could not be carried out automatically by other existing methods.
37
Otčeskich, Olga. "Paskirstytųjų sistemų agregatinių specifikacijų validavimas analizuojant būsenų pasiekiamumą." Master's thesis, Lithuanian Academic Libraries Network (LABT), 2005. http://vddb.library.lt/obj/LT-eLABa-0001:E.02~2005~D_20050517_183614-75526.
Full textAbstract:
The problem of analyzing concurrent systems has been investigated by many researchers, and several solutions have been proposed. Among the proposed techniques, reachability analysis—systematic enumeration of reachable states in a finite-state model—is attractive because it is conceptually simple and relatively straightforward to automate and can be used in conjunction with model-checking procedures to check for application-specific as well as general properties. The system validation problem considered here is the problem of verifying that the original specification is itself logically consistent. If, for instance, the specification has a design error, an implementation is expected to pass a conformance test if it contains the same error. A validation for the logical consistency of the system, however, must reveal the design error. An automated analysis of all reachable states in a distributed system can be used to trace obscure logical errors that would be very hard to find manually. This type of validation is traditionally performed by the symbolic execution of a finite state machine model of the system studied. The author presents an overview of the existing validation techniques and methods. Specified and analyzed systems are presented as reachable state graph. The implementation of the aggregate specifications validation system is also presented.
38
Ferreira, candido Renato markele. "Analyse d’atteignabilité de systèmes max-plus incertains." Thesis, Angers, 2017. http://www.theses.fr/2017ANGE0014.
Full textAbstract:
Les Systèmes à Evénements Discrets (SED) peuvent être définis comme des systèmes dans lesquels les variables d'état changent sous l'occurrence d'évènements au fil du temps. Les SED mettant en jeu des phénomènes de synchronisation peuvent être modélisés par des équations linéaires dans les algèbres de type (max,+). L'analyse d'atteignabilité est une problématique majeure pour les systèmes dynamiques. L'objectif est de calculer l'ensemble des états atteignables d'un système dynamique pour toutes les valeurs admissibles d'un ensemble d'états initiaux. Le problème de l'analyse d'atteignabilité pour les systèmes Max-Plus Linéaire (MPL) a été, proprement, résolu en décomposant le système MPL en une combinaison de systèmes affines par morceaux où les composantes affines du système sont représentées par des matrices de différences bornées (Difference Bound Matrix, DBM). La contribution principale de cette thèse est de présenter une procédure similaire pour résoudre le problème de l'atteignabilité pour des systèmes MPL incertains (uMPL), c'est-à-dire des systèmes MPL soumis à des bruits bornés, des perturbations et/ou des erreurs de modélisation. Tout d'abord, nous présentons une procédure permettant de partionner l'espace d'état d'un système uMPL en parties représentables par des DBM. Ensuite, nous étendons l'analyse d'atteignabilité des systèmes MPL aux systèmes uMPL. Enfin, les résultats sur l'analyse d'atteignabilité sont mis en oeuvre pour résoudre le problème d'atteignabilité conditionnelle, qui est étroitement lié au calcul du support de la densité de probabilité impliquée dans le problème de filtage stochastiqueDiscrete Event Dynamic Systems (DEDS) are discrete-state systems whose dynamics areentirely driven by the occurrence of asynchronous events over time. Linear equations in themax-plus algebra can be used to describe DEDS subjected to synchronization and time delayphenomena. The reachability analysis concerns the computation of all states that can bereached by a dynamical system from an initial set of states. The reachability analysis problemof Max Plus Linear (MPL) systems has been properly solved by characterizing the MPLsystems as a combination of Piece-Wise Affine (PWA) systems and then representing eachcomponent of the PWA system as Difference-Bound Matrices (DBM). The main contributionof this thesis is to present a similar procedure to solve the reachability analysis problemof MPL systems subjected to bounded noise, disturbances and/or modeling errors, calleduncertain MPL (uMPL) systems. First, we present a procedure to partition the state spaceof an uMPL system into components that can be completely represented by DBM. Then weextend the reachability analysis of MPL systems to uMPL systems. Moreover, the results onreachability analysis of uMPL systems are used to solve the conditional reachability problem,which is closely related to the support calculation of the probability density function involvedin the stochastic filtering problem
Os Sistemas a Eventos Discretos (SEDs) constituem uma classe de sistemas caracterizada por apresentar espaço de estados discreto e dinâmica dirigida única e exclusivamente pela ocorrência de eventos. SEDs sujeitos aos problemas de sincronização e de temporização podem ser descritos em termos de equações lineares usando a álgebra max-plus. A análise de alcançabilidade visa o cálculo do conjunto de todos os estados que podem ser alcançados a partir de um conjunto de estados iniciais através do modelo do sistema. A análise de alcançabilidade de sistemas Max Plus Lineares (MPL) pode ser tratada por meio da decomposição do sistema MPL em sistemas PWA (Piece-Wise Affine) e de sua correspondente representação por DBM (Difference-Bound Matrices). A principal contribuição desta tese é a proposta de uma metodologia similar para resolver o problema de análise de alcançabilidade em sistemas MPL sujeitos a ruídos limitados, chamados de sistemas MPL incertos ou sistemas uMPL (uncertain Max Plus Linear Systems). Primeiramente, apresentamos uma metodologia para particionar o espaço de estados de um sistema uMPL em componentes que podem ser completamente representados por DBM. Em seguida, estendemos a análise de alcançabilidade de sistemas MPL para sistemas uMPL. Além disso, a metodologia desenvolvida é usada para resolver o problema de análise de alcançabilidade condicional, o qual esta estritamente relacionado ao cálculo do suporte da função de probabilidade de densidade envolvida o problema de filtragem estocástica
39
Santos, Felipe Martins dos. "Soluções eficientes para processos de decisão markovianos baseadas em alcançabilidade e bissimulações estocásticas." Universidade de São Paulo, 2013. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-12022014-140538/.
Full textAbstract:
Planejamento em inteligência artificial é a tarefa de determinar ações que satisfaçam um dado objetivo. Nos problemas de planejamento sob incerteza, as ações podem ter efeitos probabilísticos. Esses problemas são modelados como Processos de Decisão Markovianos (Markov Decision Processes - MDPs), modelos que permitem o cálculo de soluções ótimas considerando o valor esperado de cada ação em cada estado. Contudo, resolver problemas grandes de planejamento probabilístico, i.e., com um grande número de estados e ações, é um enorme desafio. MDPs grandes podem ser reduzidos através da computação de bissimulações estocásticas, i.e., relações de equivalência sobre o conjunto de estados do MDP original. A partir das bissimulações estocásticas, que podem ser exatas ou aproximadas, é possível obter um modelo abstrato reduzido que pode ser mais fácil de resolver do que o MDP original. No entanto, para problemas de alguns domínios, a computação da bissimulação estocástica sobre todo o espaço de estados é inviável. Os algoritmos propostos neste trabalho estendem os algoritmos usados para a computação de bissimulações estocásticas para MDPs de forma que elas sejam computadas sobre o conjunto de estados alcançáveis a partir de um dado estado inicial, que pode ser muito menor do que o conjunto de estados completo. Os resultados experimentais mostram que é possível resolver problemas grandes de planejamento probabilístico com desempenho superior às técnicas conhecidas de bissimulação estocástica.Planning in artificial intelligence is the task of finding actions to reach a given goal. In planning under uncertainty, the actions can have probabilistic effects. This problems are modeled using Markov Decision Processes (MDPs), models that enable the computation of optimal solutions considering the expected value of each action when applied in each state. However, to solve big probabilistic planning problems, i.e., those with a large number of states and actions, is still a challenge. Large MDPs can be reduced by computing stochastic bisimulations, i.e., equivalence relations over the original MDP states. From the stochastic bisimulations, that can be exact or approximated, it is possible to get an abstract reduced model that can be easier to solve than the original MDP. But, for some problems, the stochastic bisimulation computation over the whole state space is unfeasible. The algorithms proposed in this work extend the algorithms that are used to compute stochastic bisimulations for MDPs in a way that they can be computed over the reachable set of states with a given initial state, which can be much smaller than the complete set of states. The empirical results show that it is possible to solve large probabilistic planning problems with better performance than the known techniques of stochastic bisimulation.
40
Meslem, Nacim. "Atteignabilité hybride des systèmes dynamiques continus par analyse par intervalles : application à l'estimation ensembliste." Phd thesis, Université Paris-Est, 2008. http://tel.archives-ouvertes.fr/tel-00461673.
Full textAbstract:
Cette thèse porte sur le calcul d'une sur-approximation conservative pour les solutions d'équations différentielles ordinaires en présence d'incertitudes et sur son application à l'estimation et l'analyse de systèmes dynamiques à temps continu. L'avantage principal des méthodes et des algorithmes de calculs présentés dans cette thèse est qu'ils apportent une preuve numérique de résultats. Cette thèse est organisée en deux parties. La première partie est consacrée aux outils mathématiques et aux méthodes d'intégration numérique garantie des équations diff érentielles incertaines. Ces méthodes permettent de caractériser de manière garantie l'ensemble des trajectoires d'état engendrées par un système dynamique incertain dont les incertitudes sont naturellement représentées par des intervalles bornés. Dans cette optique, nous avons développé une méthode d'intégration hybride qui donne de meilleurs résultats que les méthodes d'intégration basées sur les modèles de Taylor intervalles. La seconde partie aborde les problèmes de l'identification et de l'observation dans un contexte à erreurs bornées ainsi que le problème d'atteignabilité continue pour la véri cation de propriétés des systèmes dynamiques hybrides.
41
Konecny, Filip. "Vérification relationnelle pour des programmes avec des données entières." Phd thesis, Université de Grenoble, 2012. http://tel.archives-ouvertes.fr/tel-00805599.
Full textAbstract:
Les travaux présentés dans cette thèse sont lies aux problèmes de vérification de l'atteignabilité et de la terminaison de programmes qui manipulent des données entières non-bornées. On décrit une nouvelle méthode de vérification basée sur une technique d'accélération de boucle, qui calcule, de manière exacte, la clôture transitive d'une relation arithmétique. D'abord, on introduit un algorithme d'accélération de boucle qui peut calculer, en quelques secondes, des clôtures transitives pour des relations de l'ordre d'une centaine de variables. Ensuite, on présente une méthode d'analyse de l'atteignabilité, qui manipule des relations entre les variables entières d'un programme, et applique l'accélération pour le calcul des relations entrée-sortie des procédures, de façon modulaire. Une approche alternative pour l'analyse de l'atteignabilité, présentée également dans cette thèse, intègre l'accélération avec l'abstraction par prédicats, afin de traiter le problème de divergence de cette dernière. Ces deux méthodes ont été évaluées de manière pratique, sur un nombre important d'exemples, qui étaient, jusqu'a présent, hors de la portée des outils d'analyse existants. Dernièrement, on a étudié le problème de la terminaison pour certaines classes de boucles de programme, et on a montré la décidabilité pour les relations étudiées. Pour ces classes de relations arithmétiques, on présente un algorithme qui s'exécute en temps au plus polynomial, et qui calcule l'ensemble d'états qui peuvent générer une exécution infinie. Ensuite on a intégré cet algorithme dans une méthode d'analyse de la terminaison pour des programmes qui manipulent des données entières.
42
Cunha, Daniela Vieira. "Análise lógica de protocolos, proposta e avaliação de desempenho de um algoritmo de atribuição de rótulo baseado em SRLG em um ambiente GMPLS-WDM." Universidade de São Paulo, 2006. http://www.teses.usp.br/teses/disponiveis/3/3141/tde-04052006-155552/.
Full textAbstract:
Para satisfazer o explosivo aumento na demanda de tráfego de voz e dados, as redes ópticas baseadas em WDM e GMPLS estão sendo desenvolvidas. A suíte de protocolos GMPLS é atualmente considerada como um plano de controle para as redes ópticas e é composta por protocolos de sinalização e de roteamento, como também do protocolo de gerenciamento de enlace (LMP). O LMP é um importante protocolo que interfere na atribuição de rótulos (comprimentos de onda) e é necessário fazer sua análise lógica para verificar se o mesmo está livre de erros de progresso. Para esta finalidade, o método denominado alcançabilidade justa foi utilizado. Verificada a corretude do LMP, o estudo foca o subproblema de atribuição de comprimento de onda do RWA nas redes GMPLS-WDM por ser um dos principais problemas que causam o baixo desempenho destas redes. O cenário estudado é das redes GMPLS-WDM que operam em um ambiente RWA dinâmico com restrição de continuidade de comprimento de onda. O problema RWA é examinado bem como as várias heurísticas de atribuição de comprimento de onda apresentadas na literatura. Com o objetivo de melhorar o desempenho das redes GMPLS-WDM com restrição de continuidade de comprimento de onda, propõe-se um algoritmo de atribuição de rótulos que utiliza os conceitos conjunto de rótulos e SRLG já implementados pelo GMPLS. O algoritmo proposto melhora a eficiência no uso de recursos nas redes em questão. O desempenho é verificado através da métricas de probabilidade de bloqueio de conexão, desempenho este próximo do ótimo e demonstrado através de simulações.To satisfy the explosive increasing demands of voice and data traffic, optical networks based on WDM and GMPLS are being developed. The GMPLS´ suite of protocols is currently being considered as the control plane for optical networks and it is compounded of signaling and routing protocols, and also the link management protocol (LMP). The LMP is an important protocol that interferes with label (wavelength) assignment and it is necessary to logically analyse this protocol in order to verify if it is free from progress errors. For this purpose, the method called fair reachability has been used. Verified the LMP is correctable, the study focuses on the RWA wavelength assignment problem in GMPLS-WDM networks because it is one of the main problems which causes the low performance of these networks. The studied scene is GMPLS-WDM networks operating under a dynamic RWA environment with wavelength continuity constraint. The RWA problem is examined and also the various wavelength-assignment heuristics proposed in the literature. With the goal to improve the performance of the GMPLS-WDM networks with wavelength continuity constraint, it is proposed a label assignment algorithm, which uses the concepts of label set and SRLG, already implemented by GMPLS. The proposed algorithm provides an improvement in efficiency of resource use. The performance is verified by using the blocking probability metric, and it is very close to the optimum and demonstrated through simulations.
43
Konečný, Filip. "Relační verifikace programů s celočíselnými daty." Doctoral thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2012. http://www.nusl.cz/ntk/nusl-261262.
Full textAbstract:
Tato práce představuje nové metody pro verifikaci programů pracujících s neomezenými celočíslenými proměnnými, konkrétně metody pro analýzu dosažitelnosti a~konečnosti. Většina těchto metod je založena na akceleračních technikách, které počítají tranzitivní uzávěry cyklů programu. V práci je nejprve představen algoritmus pro akceleraci několika tříd celočíselných relací. Tento algoritmus je až o čtyři řády rychlejší než existující techniky. Z teoretického hlediska práce dokazuje, že uvažované třídy relací jsou periodické a~poskytuje tudíž jednotné řešení prolému akcelerace. Práce dále představuje semi-algoritmus pro analýzu dosažitelnosti celočíselných programů, který sleduje relace mezi proměnnými programu a~aplikuje akcelerační techniky za účelem modulárního výpočtu souhrnů procedur. Dále je v práci navržen alternativní algoritmus pro analýzu dosažitelnosti, který integruje predikátovou abstrakci s accelerací s cílem zvýšit pravděpodobnost konvergence výpočtu. Provedené experimenty ukazují, že oba algoritmy lze úspěšně aplikovat k verifikaci programů, na kterých předchozí metody selhávaly. Práce se rovněž zabývá problémem konečnosti běhu programů a~dokazuje, že tento problém je rozhodnutelný pro několik tříd celočíselných relací. Pro některé z těchto tříd relací je v práci navržen algoritmus, který v polynomiálním čase vypočítá množinu všech konfigurací programu, z nichž existuje nekonečný běh. Tento algoritmus je integrován do metody, která analyzuje konečnost běhů celočíselných programů. Efektivnost této metody je demonstrována na několika netriviálních celočíselných programech.
44
Lemattre, Thibault. "Allocation de fonctions de commande de systèmes critiques par recherche d'atteignabilité dans un réseau d'automates communicants." Phd thesis, École normale supérieure de Cachan - ENS Cachan, 2013. http://tel.archives-ouvertes.fr/tel-00916583.
Full textAbstract:
La conception d'architectures opérationnelles d'un système de contrôle-commande est une phase très importante lors de la conception de systèmes de production d'énergie. Cette phase consiste à projeter l'architecture fonctionnelle sur l'architecture organique tout en respectant des contraintes de capacité et de sûreté, c'est-à-dire à allouer les fonctions de commande à un ensemble de contrôleurs tout en respectant ces contraintes. Les travaux présentés dans cette thèse proposent : i)une formalisation des données et contraintes du problème d'allocation de fonctions - ii)une méthode d'allocation, par recherche d'atteignabilité, basée sur un mécanisme d'appel/réponse dans un réseau d'automates communicants à variables entières - iii)la comparaison de cette méthode à une méthode de résolution par programmation linéaire en nombres entiers. Les résultats de ces travaux ont été validés sur des exemples de taille réelle et ouvrent la voie à des couplages entre recherche d'atteignabilité et programmation linéaire en nombres entiers pour la résolution de problèmes de satisfaction de systèmes de contraintes non linéaires.
45
Santiago, Pinazo Sonia. "Advanced Features in Protocol Verification: Theory, Properties, and Efficiency in Maude-NPA." Doctoral thesis, Universitat Politècnica de València, 2015. http://hdl.handle.net/10251/48527.
Full textAbstract:
The area of formal analysis of cryptographic protocols has been an active
one since the mid 80’s. The idea is to verify communication protocols
that use encryption to guarantee secrecy and that use authentication of
data to ensure security. Formal methods are used in protocol analysis to
provide formal proofs of security, and to uncover bugs and security flaws
that in some cases had remained unknown long after the original protocol
publication, such as the case of the well known Needham-Schroeder
Public Key (NSPK) protocol. In this thesis we tackle problems regarding
the three main pillars of protocol verification: modelling capabilities,
verifiable properties, and efficiency.
This thesis is devoted to investigate advanced features in the analysis
of cryptographic protocols tailored to the Maude-NPA tool. This tool
is a model-checker for cryptographic protocol analysis that allows for
the incorporation of different equational theories and operates in the
unbounded session model without the use of data or control abstraction.
An important contribution of this thesis is relative to theoretical aspects
of protocol verification in Maude-NPA. First, we define a forwards
operational semantics, using rewriting logic as the theoretical framework
and the Maude programming language as tool support. This is the first
time that a forwards rewriting-based semantics is given for Maude-NPA.
Second, we also study the problem that arises in cryptographic protocol
analysis when it is necessary to guarantee that certain terms generated
during a state exploration are in normal form with respect to the protocol
equational theory.
We also study techniques to extend Maude-NPA capabilities to support
the verification of a wider class of protocols and security properties.
First, we present a framework to specify and verify sequential protocol
compositions in which one or more child protocols make use of information obtained from running a parent protocol. Second, we present a
theoretical framework to specify and verify protocol indistinguishability
in Maude-NPA. This kind of properties aim to verify that an attacker
cannot distinguish between two versions of a protocol: for example, one
using one secret and one using another, as it happens in electronic voting
protocols.
Finally, this thesis contributes to improve the efficiency of protocol
verification in Maude-NPA. We define several techniques which drastically
reduce the state space, and can often yield a finite state space,
so that whether the desired security property holds or not can in fact
be decided automatically, in spite of the general undecidability of such
problems.Santiago Pinazo, S. (2015). Advanced Features in Protocol Verification: Theory, Properties, and Efficiency in Maude-NPA [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/48527
TESIS
46
Ye, Xin. "Model checking self modifying code." Thesis, Université de Paris (2019-....), 2019. http://www.theses.fr/2019UNIP7010.
Full textAbstract:
Le code auto-modifiant est un code qui modifie ses propres instructions pendant le temps d'exécution. Il est aujourd'hui largement utilisé, notamment dans les logiciels malveillants pour rendre le code difficile à analyser et à été détecté par les anti-virus. Ainsi, l'analyse de tels programmes d'auto-modifiant est un grand défi. Pushdown System(PDSs) est un modèle naturel qui est largement utilisé pour l'analyse des programmes séquentiels car il permet de modéliser précisément les appels de procédures et de simuler la pile du programme. Dans cette thèse, nous proposons d'étendre le modèle du PDS avec des règles auto-modifiantes. Nous appelons le nouveau modèle Self-Modifying PushDown System (SM- PDS). Un SM-PDS est un PDS qui peut modifier l’ensemble des règles de transitions pendant l'exécution. Tout d'abord, nous montrons comment les SM-PDS peuvent être utilisés pour représenter des programmes auto- et nous fournissons des algorithmes efficaces pour calculer les configurations précédentes et suivantes des SM-PDS accessibles. Ensuite, nous résolvons les problèmes sur la vérification de propriétés LTL et CTL pour le code auto-modifiant. Nous implémentons nos techniques dans un outil appelé SMODIC. Nous avons obtenu des résultats encourageants. En particulier, notre outil est capable de détecter plusieurs logiciels malveillants auto-modifiants ; il peut même détecter plusieurs logiciels malveillants que les autres logiciels anti-virus bien connus comme McAfee, Norman, BitDefender, Kinsoft, Avira, eScan, Kaspersky, Qihoo-360, Avast et Symantec n'ont pas pu détecterA Self modifying code is code that modifies its own instructions during execution time. It is nowadays widely used, especially in malware to make the code hard to analyse and to detect by anti-viruses. Thus, the analysis of such self modifying programs is a big challenge. Pushdown Systems (PDSs) is a natural model that is extensively used for the analysis of sequential programs because it allows to accurately model procedure calls and mimic the program’s stack. In this thesis, we propose to extend the PushDown System model with self-modifying rules. We call the new model Self-Modifying PushDown System (SM-PDS). A SM-PDS is a PDS that can modify its own set of transitions during execution. First, we show how SM-PDSs can be used to naturally represent self-modifying programs and provide efficient algorithms to compute the backward and forward reachable configurations of SM-PDSs. Then, we consider the LTL model-checking problem of self-modifying code. We reduce this problem to the emptiness problem of Self-modifying Büchi Pushdown Systems (SM-BPDSs). We also consider the CTL model-checking problem of self-modifying code. We reduce this problem to the emptiness problem of Self-modifying Alternating Büchi Pushdown Systems (SM-ABPDSs). We implement our techniques in a tool called SMODIC. We obtained encouraging results. In particular, our tool was able to detect several self-modifying malwares; it could even detect several malwares that well-known anti-viruses such as McAfee, Norman, BitDefender, Kinsoft, Avira, eScan, Kaspersky, Qihoo-360, Avast and Symantec failed to detect
47
Ben, Abdallah Emna. "Étude de la dynamique des réseaux biologiques : apprentissage des modèles, intégration des données temporelles et analyse formelle des propriétés dynamiques." Thesis, Ecole centrale de Nantes, 2017. http://www.theses.fr/2017ECDN0041.
Full textAbstract:
Au cours des dernières décennies, l’émergence d’une large gamme de nouvelles technologies a permis de produire une quantité massive de données biologiques (génomique, protéomique...). Ainsi, une grande quantité de données de séries temporelles est maintenant élaborée tous les jours. Nouvellement produites, ces données peuvent nous fournir des nouvelles interprétations sur le comportement des Systèmes Biologiques (SB). Cela conduit alors à des développements considérables dans le domaine de la bioinformatique qui peuvent tirer profit de ces données. Ceci justifie notre motivation pour le développement de méthodes efficaces qui exploitent ces données pour l’apprentissage des Réseaux de Régulation Biologique (RRB) modélisant les SB. Nous introduisons alors, dans cette thèse, une nouvelle approche qui infère des RRB à partir des données de séries temporelles. Les RRB appris sont présentés avec un nouveau formalisme, introduit dans cette thèse, appelé " réseau d’automates avec le temps" (T-AN). Ce dernier assure le raffinement de la dynamique des RRB, modélisés avec le formalisme des réseaux d’automates (AN), grâce à l’intégration d’un paramètre temporel (délai) dans les transitions locales des automates. Cet enrichissement permet de paramétrer les transitions entre les états locaux des automates et aussi entre les états globaux du réseau. À posteriori de l’apprentissage des RRB, et dans le but d’avoir une meilleure compréhension de la nature du fonctionnement des SB, nous procédons à l’analyse formelle de la dynamique des RRB. Nous introduisons alors des méthodes logiques originales (développées en Answer Set Programming) pour déchiffrer l’énorme complexité de la dynamique des SB. Les propriétés dynamiques étudiées sont : l’identification des attracteurs (ensemble d’états globaux terminaux dont le réseau ne peut plus s’échapper) et la vérification de la propriété d’atteignabilité d’un objectif (un ensemble de composants) à partir d’un état global initial du réseauOver the last few decades, the emergence of a wide range of new technologies has produced a massive amount of biological data (genomics, proteomics...). Thus, a very large amount of time series data is now produced every day. The newly produced data can give us new ideas about the behavior of biological systems. This leads to considerable developments in the field of bioinformatics that could benefit from these enormous data. This justifies the motivation to develop efficient methods for learning Biological Regulatory Networks (BRN) modeling a biological system from its time series data. Then, in order to understand the nature of system functions, we study, in this thesis, the dynamics of their BRN models. Indeed, we focus on developing original and scalable logical methods (implemented in Answer Set Programming) to deciphering the emerging complexity of dynamics of biological systems. The main contributions of this thesis are enumerated in the following. (i) Refining the dynamics of the BRN, modeling with the automata Network (AN) formalism, by integrating a temporal parameter (delay) in the local transitions of the automata. We call the extended formalism a Timed Automata Network (T-AN). This integration allows the parametrization of the transitions between each automata local states as well as between the network global states. (ii) Learning BRNs modeling biological systems from their time series data. (iii) Model checking of discrete dynamical properties of BRN (modeling with AN and T-AN) by dynamical formal analysis : attractors identification (minimal trap domains from which the network cannot escape) and reachability verification of an objective from a network global initial state
48
Cochard, Thomas. "Contribution à la génération de séquences pour la conduite de systèmes complexes critiques." Thesis, Université de Lorraine, 2017. http://www.theses.fr/2017LORR0355/document.
Full textAbstract:
Les travaux présentés dans ce manuscrit portent sur la conduite de systèmes complexes critiques. Ils s'inscrivent dans le cadre du projet CONNEXION (Investissements d'Avenir, BGLE2) qui réunit les principaux acteurs de la filière nucléaire française autour de la conception des systèmes de contrôle-commande des centrales et de leur exploitation. Dans le domaine de la conduite, les actions développées par le projet concernent la phase d'ingénierie avec pour objectif d'intégrer le point de vue de l'exploitant au plus tôt dans la validation des architectures de contrôle de commande, et la phase d'exploitation avec pour objectif de fournir une aide à la préparation et à l'exécution des procédures de conduite. Dans ce contexte, la contribution présentée dans ce mémoire porte sur la génération et la vérification de séquences d'actions de conduite répondant à un objectif donné et pouvant être opérées en toute sécurité sur le procédé. L'approche proposée repose la vérification d'une propriété d'atteignabilité sur un réseau d'automates temporisés modélisant le comportement des architectures. L'originalité réside dans la définition d’un cadre formel de modélisation sous la forme de patrons favorisant la réutilisabilité des modèles ainsi que dans la proposition d'algorithmes d'abstraction et de recherche d'atteignabilité itératifs exploitant la hiérarchisation intrinsèque des architectures afin de permettre le passage à l'échelle de l'approche proposée. La contribution a été éprouvée sur la plate-forme d'expérimentation CISPI du CRAN puis sur un cas d'étude à échelle industrielle proposé dans le cadre du projet CONNEXIONThe works presented in this manuscript deals with critical complex systems operation. They are part of the CONNEXION project (Investissements d'Avenir, BGLE2), which involves the main actors in the French nuclear industry around the design of control systems for power plants and their operation. In the operation field, the actions developed by the project concern the engineering phase with the aim of integrating the operator's point of view as soon as possible in the validation of control architectures, and the operation phase with the aim of providing assistance in the preparation and execution of operation procedures. In this context, the contribution presented in this manuscript deals with the generation and verification of action sequences that meet a given objective and that can be safely operated on the process. The proposed approach relies on verifying a reachability property on a network of timed automata modelling the behavior of architectures. The originality is in the definition of a formal modelling framework using patterns promoting the reusability of models, as well as in the proposition of abstraction and reachability iterative analysis algorithms exploiting the intrinsic hierarchization of architectures in order to scale-up of the proposed approach. The contribution was evaluated on the CISPI experimental platform of the CRAN, and on an industrial scale case study proposed within the framework of the CONNEXION project
49
Gucik-Derigny, David. "CONTRIBUTION AU PRONOSTIC DES SYSTÈMES NON LINÉAIRES À BASE DE MODÈLES : THÉORIE ET APPLICATION." Thesis, Aix-Marseille 3, 2011. http://www.theses.fr/2011AIX30032.
Full textAbstract:
Cette thèse est une contribution au problème du pronostic des systèmes complexes. Plus précisément, elle concerne l'approche basée modèles et est composée de trois contributions principales. Tout d'abord, dans une première contribution une définition du concept de pronostic est proposée et est positionnée par rapport aux concepts de diagnostic et de diagnostic prédictif. Pour cela, une notion de contrainte temporelle a été introduite afin de donner toute pertinence à la prédiction réalisée. Il a également été montré comment le pronostic est lié à la notion d'accessibilité en temps fini.La deuxième contribution est dédiée à l'utilisation des observateurs à convergence en temps fini pour la problématique du pronostic. Une méthodologie de pronostic est présentée pour les systèmes non linéaires à échelle de temps multiple. Puis, une troisième contribution est introduite par l'utilisation des observateurs par intervalle pour le pronostic. Une méthodologie de pronostic est proposée pour les systèmes non linéaires incertains à échelle de temps multiple. Pour illustrer les différents résultats théoriques, des simulations ont été conduites sur un modèle de comportement d'un oscillateur électromécaniqueThis thesis is a contribution to the problem of a complex system prognosis. More precisely, it concerns the model-based prognosis approach and the thesis is divided into three main contributions. First of all, a definition of prognosis concept is proposed as a first contribution and is positionned in reference to the diagnosis and predictive diagnosis concepts. For that, a notion of temporal constraint is introduced to give all pertinence to the prediction achieved. It is also shown how prognosis is linked to the finite time reachability notion. The second contribution is dedicated to the use of finite time convergence observer for the prognosis problem. A prognosis methodology is presented for nonlinear multiple time scale systems. Then, a last contribution is introduced through the use of interval observer for the prognosis problem. A pronognosis methodology is proposed for nonlinear uncertain multiple time scale systems. To illustrate the theorical results, simulations are achieved based on a model of an electromechanical oscillator system
50
Tsai, Jung-Tai, and 蔡榮泰. "Reachability Analysis of Sequential Circuits." Thesis, 2007. http://ndltd.ncl.edu.tw/handle/58761696852409546372.
Full textAbstract:
碩士國立清華大學
資訊工程學系
95
Reachability analysis is a fundamental technique in the Synthesis and verification of VLSI circuits. This paper presents a novel semi-formal approach which combines the advantages of simulation and formal methods to traverse the state space of the FSMs. We conduct the experiments on a set of ISCAS’89 benchmarks. As compared with a previous work which relies on biased random technique, our approach reaches more states with less CPU time.