Dissertations / Theses on the topic 'Temporal verification'
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 'Temporal verification.'
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.
Chen, Jinjun, and n/a. "Towards effective and efficient temporal verification in grid workflow systems." Swinburne University of Technology, 2007. http://adt.lib.swin.edu.au./public/adt-VSWT20070424.112326.
Full textSoleimanifard, Siavash. "Procedure-Modular Verification of Temporal Safety Properties." Licentiate thesis, KTH, Teoretisk datalogi, TCS, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-93898.
Full textQC 20120507
Jin, S. "Temporal logic specification and verification of communication protocols." Thesis, University of Manchester, 1987. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.378819.
Full textBruns, Glen R. "Process abstraction in the verification of temporal properties." Thesis, University of Edinburgh, 1998. http://hdl.handle.net/1842/384.
Full textHarvey, Randall A. "Verification of concurrent system specifications using temporal logic." Thesis, University of Ottawa (Canada), 1989. http://hdl.handle.net/10393/5662.
Full textBolotov, Alexander. "Clausal resolution for branching-time temporal logic." Thesis, Manchester Metropolitan University, 2000. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.311209.
Full textBrochenin, Rémi. "Separation logic : expressiveness, complexity, temporal extension." Phd thesis, École normale supérieure de Cachan - ENS Cachan, 2013. http://tel.archives-ouvertes.fr/tel-00956587.
Full textKoleini, Masoud. "Verification of temporal-epistemic properties of access control systems." Thesis, University of Birmingham, 2012. http://etheses.bham.ac.uk//id/eprint/3706/.
Full textBouaziz, Hamida. "Adaptation of SysML Blocks and Verification of Temporal Properties." Thesis, Besançon, 2016. http://www.theses.fr/2016BESA2015/document.
Full textThe work presented in this thesis takes place in the component-based development domain, it is a contribution to the specification,adaptation and verification of component-based systems. The main purpose of this thesis is the proposition of a formal approach tobuild incrementally complex systems by assembling and adapting a set of components, where their structure and behaviour are modelledusing SysML diagrams. In the first stage, we have defined a meta-model driven approach which is based on meta-modelling and modelstransformation, to verify the compatibility of blocks having their interaction protocols modelled using SysML sequence diagrams. To verifytheir compatibility, we perform a transformation into interface automata (IAs), and we base on the optimistic approach defined on IAs. Thisapproach consider that two components are compatible if there is a suitable environment with which they can interact correctly. Afterthat, we have proposed to benefit from the hierarchy, that may be present in the interaction protocol models of the blocks, to alleviate theverification of blocks compatibility. In the next stage, we have taken into consideration the problem of names mismatches of type one2onebetween services of blocks. At this stage, an adapter is generated for a set of reused blocks which have their interaction protocols modelledformally by interface automata. The generation of the adapter is guided by the specification of the parent block which is made initiallyby the designer. Our approach is completed by a verification phase which allows us to verify SysML requirements, expressed formallyby temporal properties, on SySML blocks. In this phase, we have exploited only the generated adapters to verify the preservation of therequirements initially satisfied by the reused blocks. Thus, our approach intends to give more chance to avoid the state space explosionproblem during the verification. In the same context, where we have a set of reused blocks and the specification of their parent blocks, wehave proposed to use coloured Petri nets (CPNs) to model the blocks interactions and to generate adapters that solve more type of problems.In this case the adapter can solve the problem of livelock by enabling the reordering of services calls
Chen, Jinjun. "Towards effective and efficient temporal verification in grid workflow systems." Australasian Digital Thesis Program, 2007. http://adt.lib.swin.edu.au/public/adt-VSWT20070424.112326/index.html.
Full textA thesis to CITR - Centre for Information Technology Research, Faculty of Information and Communication Technologies, Swinburne University of Technology, for the degree of Doctor of Philosophy, 2007. Typescript. Bibliography p. 145-160.
Tsiknis, George. "Specification-verification of protocols : the significant event temporal logic technique." Thesis, University of British Columbia, 1985. http://hdl.handle.net/2429/25047.
Full textScience, Faculty of
Computer Science, Department of
Graduate
Zoubek, Bohumir. "Automatic verification of temporal and timed properties of control programs." Thesis, University of Birmingham, 2004. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.419737.
Full textHummelgren, Lars. "A contract language for modular specification and verification of temporal properties." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-280457.
Full textDeduktiv mjukvaruverifikation används för att bevisa korrekthet av program med avseende på kontrakt. Kontrakt uttrycks ofta på procedurer i ett program med användning av Hoare-logik. Sådana kontrakt består av ett förvillkor som specificerar ett villkor som måste gälla innan proceduren exekveras och ett eftervillkor som uttrycker vad som garanteras i gengäld. Ett kontrakt kan ses som en överenskommelse mellan användaren av en procedur och dess utvecklare. Det är viktigt att det på ett skalbart sätt går att verifiera att procedurer i ett program uppfyller deras respektive kontrakt. Skalbarhet kan uppnås genom att se till att verifikationen är procedur-modulär, vilket innebär att varje proceduranrop direkt ersätts med kontraktet som tillhör den anropade proceduren i stället för att proceduranropet utvärderas. Hoare-logikens axiom gör den till en bra grund för procedur-modulära resonemang. Men Hoare-logik är inte välanpassad för att resonera kring en procedurs beteende under en sekvens av tillstånd. Frågorna som ställs är hur ett kontraktspråk för att specificera sådana temporala egenskaper kan utformas samt hur en procedur kan verifieras att uppfylla kontrakt uttryckta i ett sådant kontraktspråk på ett procedur-modulärt sätt. För att besvara frågan presenteras först ett enkelt programmeringsspråk med procedurer. Syftet är att kontrakt uttrycks på program skrivna i detta programspråk. Två kontraktspråk presenteras. Det visas hur kontrakt kan formuleras i dessa språk för att specificera temporala egenskaper av procedurer samt hur procedurer kan verifieras att uppfylla sådana temporala kontrakt. Det första kontraktspråket är begränsat med avseende på dess uttrycksfullhet, men dess kontrakt kan automatiskt verifieras. Det andra språket kan användas för att uttrycka mer komplicerade egenskaper, men dess verifikationsproblem visar sig vara oavgörbart. Alternativa tillvägagångssätt för att hantera dess verifikationsproblem diskuteras.
Bradfield, Julian Charles. "Verifying temporal properties of systems with applications to petri nets." Thesis, University of Edinburgh, 1991. http://hdl.handle.net/1842/6565.
Full textSogokon, Andrew. "Direct methods for deductive verification of temporal properties in continuous dynamical systems." Thesis, University of Edinburgh, 2016. http://hdl.handle.net/1842/20952.
Full textNaik, Yogesh. "A temporal logic for the specification and verification of real-time systems." Thesis, University of Warwick, 1993. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.386831.
Full textLudwig, Michel. "Resolution-based methods for linear-time temporal logics : with applications to formal verification." Thesis, University of Liverpool, 2010. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.533985.
Full textBorges, Rafael. "A neural-symbolic system for temporal reasoning with application to model verification and learning." Thesis, City University London, 2012. http://openaccess.city.ac.uk/1303/.
Full textMuraleedharan, Nair Jayakrishnan. "Signature Verification Model: A Long Term Memory Approach." Ohio University / OhioLINK, 2015. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1427210243.
Full textBundala, Daniel. "Algorithmic verification problems in automata-theoretic settings." Thesis, University of Oxford, 2014. https://ora.ox.ac.uk/objects/uuid:60b2d507-153f-4119-a888-56ccd47c3752.
Full textMuhammad, Shahabuddin. "EXTENDING DISTRIBUTED TEMPORAL PROTOCOL LOGIC TO A PROOF BASED FRAMEWORK FOR AUTHENTICATION PROTOCOLS." Doctoral diss., University of Central Florida, 2007. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/3086.
Full textPh.D.
School of Electrical Engineering and Computer Science
Engineering and Computer Science
Computer Science PhD
Shafie, Emad. "Runtime detection and prevention for Structure Query Language injection attacks." Thesis, De Montfort University, 2013. http://hdl.handle.net/2086/10076.
Full textKumar, Rahul. "Using Live Sequence Chart Specifications for Formal Verification." BYU ScholarsArchive, 2008. https://scholarsarchive.byu.edu/etd/1500.
Full textEl-kustaban, Amin Mohammed Ahmed. "Studying and analysing transactional memory using interval temporal logic and AnaTempura." Thesis, De Montfort University, 2012. http://hdl.handle.net/2086/6900.
Full textUhl, Philip J. "A Spatio-Temporal Data Model for Zoning." BYU ScholarsArchive, 2002. https://scholarsarchive.byu.edu/etd/1.
Full textMokkedem, Abdelillah. "Verification et raffinement de programmes parallèles dans une logique temporelle compositionnelle : application au langage SDL." Vandoeuvre-les-Nancy, INPL, 1994. http://www.theses.fr/1994INPL051N.
Full textSamant, Gajanan Balkrishna. "Verification of the "Energy Accumulation in Waves Travelling through a Checkerboard Dielectric Material Structure in Space-time" Using Spice Simulations." Digital WPI, 2009. https://digitalcommons.wpi.edu/etd-theses/1210.
Full textMutňanský, Filip. "Ověřování parametrických vlastností nad záznamy běhů programů." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2020. http://www.nusl.cz/ntk/nusl-417229.
Full textKlüppelholz, Sascha. "Verification of Branching-Time and Alternating-Time Properties for Exogenous Coordination Models." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2012. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-86211.
Full textAlouffi, Bader. "Run time verifcation of hybrid systems." Thesis, De Montfort University, 2016. http://hdl.handle.net/2086/12490.
Full textUrban, Caterina. "Static analysis by abstract interpretation of functional temporal properties of programs." Thesis, Paris, Ecole normale supérieure, 2015. http://www.theses.fr/2015ENSU0017/document.
Full textThe overall aim of this thesis is the development of mathematically sound and practically efficient methods for automatically proving the correctness of computer software. More specifically, this thesis is grounded in the theory of abstract interpretation, a powerful mathematical framework for approximating the behavior of programs. In particular, this thesis focuses on provingprogram liveness properties, which represent requirements that must be eventually or repeatedly realized during program execution. Program termination is the most prominent liveness property. This thesis designs new program approximations, in order to automatically infer sufficient preconditions for program termination and synthesize so called piecewisedefined ranking functions, which provide upper bounds on the waiting time before termination. The approximations are parametric in the choice between the expressivity and the cost of the underlying approximations, which maintain information about the set of possible values of the program variables along with the possible numerical relationships between them. This thesis also contributes an abstract interpretation framework for proving liveness properties, which comes as a generalization of the framework proposedfor termination. In particular, the framework is dedicated to liveness properties expressed in temporal logic, which are used to ensure that some desirable event happens once or infinitely many times during program execution. As for program termination, piecewise-defined ranking functions are used to infer sufficient preconditions for these properties, and to provide upper boundson the waiting time before a desirable event. The results presented in this thesis have been implemented into a prototype analyzer. Experimental results show that it performs well on a wide variety of benchmarks, it is competitive with the state of the art, and is able to analyze programs that are out of the reach of existing methods
Olšák, Ondřej. "Verifikace za běhu systémů s vlastnostmi v MTL logice." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2021. http://www.nusl.cz/ntk/nusl-449176.
Full textSečkařová, Petra. "Ověřování temporálních vlastností konečných běhů programů." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2019. http://www.nusl.cz/ntk/nusl-403176.
Full textBeyene, Tewodros Awgichew [Verfasser], Andrey [Akademischer Betreuer] [Gutachter] Rybalchenko, Philipp [Gutachter] Rümmer, and Helmut [Gutachter] Seidl. "Temporal Program Verification and Synthesis as Horn Constraints Solving / Tewodros Awgichew Beyene. Betreuer: Andrey Rybalchenko. Gutachter: Philipp Rümmer ; Helmut Seidl ; Andrey Rybalchenko." München : Universitätsbibliothek der TU München, 2015. http://d-nb.info/1103658468/34.
Full textGonçalves, Monteiro Pedro Tiago. "Towards an integrative approach for the modeling and formal verification of biological regulatory networks." Thesis, Lyon 1, 2010. http://www.theses.fr/2010LYO10239/document.
Full textThe study of large models of biological networks by means of analysis and simulation tools leads to large amounts of predictions. This raises the question of how to identify interesting predictions of novel phenomena that can be confronted with experimental data. Formal verification techniques based on model-checking have recently been used to the analysis of these networks, providing a powerful technology to keep up with this increase in scale and complexity. The application of these techniques is hampered, however, by several key issues. First, the systems biology domain brought to the fore a few properties of the network dynamics like multistability and oscillations, that are not easily expressed using classical temporal logics. Second, the problem of posing relevant and interesting questions in temporal logic, is difficult for non-expert users. Finally, most of the existing modeling and simulation tools are not capable of applying model-checking techniques in a transparent way. The approaches developed in this work lower the obstacles to the use of formal verification in systems biology. They have been validated on the analysis and simulation of two real and complex biological models
O estudo de redes biológicas tem originado o desenvolvimento de modelos cada vez mais complexos e detalhados. O estudo de redes biológicas complexas utilizando ferramentas de análise e simulação origina grandes quantidades de previsões. Isto levanta a questão de como identificar previsões interessantes de novos fenómenos que possam ser comparados com dados experimentais. As técnicas de verificação formal baseadas em model-checking têm sido usadas na análise destas redes, fornecendo uma tecnologia poderosa para acompanhar o aumento de escala e complexidade do problema. A aplicação destas técnicas tem sido dificultada por um conjunto importante de factores. Em primeiro lugar, em biologia de sistemas têm sido tratadas diversas questões acerca da dinâmica da rede, como a multi-estabilidade e oscilações, que não são facilmente expressas usando lógicas temporais clássicas. Em segundo lugar, o problema de como elaborar perguntas relevantes em lógica temporal, é difícil para o utilizador comum. Por último, a maioria das ferramentas de modelação e simulação não estão preparadas para a aplicação de técnicas de model-checking de forma transparente. Os métodos desenvolvidos nesta tese aliviam os obstáculos no uso da verificação formal em biologia de sistemas. Estes métodos foram validados através da análise e simulação de dois modelos biológicos complexos
Hague, Matthew. "Saturation methods for global model-checking pushdown systems." Thesis, University of Oxford, 2009. http://ora.ox.ac.uk/objects/uuid:40263ddb-312d-4e18-b774-2caf4def0e76.
Full textGrimm, Tomás [Verfasser], Michael [Gutachter] Hübner, and Holger [Gutachter] Blume. "A hybrid methodology to enable the verification of temporal properties as system-level / Tomás Grimm ; Gutachter: Michael Hübner, Holger Blume ; Fakultät für Elektrotechnik und Informationstechnik." Bochum : Ruhr-Universität Bochum, 2019. http://d-nb.info/1180027841/34.
Full textJenkins, Mark Daniel. "Synthesis and alternating automata over real time." Thesis, University of Oxford, 2012. http://ora.ox.ac.uk/objects/uuid:f37ccc5f-8ed6-4b00-b9e3-28c4bb4ec60a.
Full textBenghabrit, Walid. "A formal model for accountability." Thesis, Ecole nationale supérieure Mines-Télécom Atlantique Bretagne Pays de la Loire, 2017. http://www.theses.fr/2017IMTA0043/document.
Full textNowadays we are witnessing the democratization ofcloud services. As a result, more and more end-users(individuals and businesses) are using these services intheir daily life. In such scenarios, personal data isgenerally flowed between several entities. End-usersneed to be aware of the management, processing,storage and retention of personal data, and to havenecessary means to hold service providers accountablefor the use of their data. In this thesis we present anaccountability framework called AccountabilityLaboratory (AccLab) that allows to consideraccountability from design time to implementation time ofa system. In order to reconcile the legal world and thecomputer science world, we developed a language calledAbstract Accountability Language (AAL) that allows towrite obligations and accountability policies. Thislanguage is based on a formal logic called First OrderLinear Temporal Logic (FOTL) which allows to check thecoherence of the accountability policies and thecompliance between two policies. These policies aretranslated into a temporal logic called FO-DTL 3, which isassociated with a monitoring technique based on formularewriting. Finally, we developed a monitoring tool calledAccountability Monitoring (AccMon) which providesmeans to monitor accountability policies in the context ofa real system. These policies are based on FO-DTL 3logic and the framework can act in both centralized anddistributed modes and can run into on-line and off-linemodes
De, Oliveira Steven. "Finding constancy in linear routines." Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLS207/document.
Full textThe criticality of programs constantly reaches new boundaries as they are relied on to take decisions in place of the user (autonomous cars, robot surgeon, etc.). This raised the need to develop safe programs and to verify the already existing ones.Anyone willing to formally prove the soundness of a program faces the two challenges of scalability and undecidability. Million of lines of code, complexity of the algorithm, concurrency, and even simple polynomial expressions are part of the issues formal verification have to deal with. In order to succeed, formal methods rely on state abstraction to analyze approximations of the behavior of the analyzed program.The analysis of loops is a full axis of formal verification, as this construction is still today not well understood. Though some of them can be easily handled when they perform simple operations, there still exist some seemingly basic loops whose behavior has not been solved yet (the Syracuse sequence for example is suspected to be undecidable).The most common approach for the treatment of loops is the use of loop invariants, i.e. relations on variables that are true at the beginning of the loop and after every step. In general, invariants are expected to use the same set of expressions used in the loop: if a loop manipulates the memory on a structure for example, invariants will naturally use expressions involving memory operations. However, there exist loops containing only linear instructions that admit only polynomial invariants (for example, the sum on integers $sumlimits_{i=0}^n i$ can be computed by a linear loop and is a degree 2 polynomial in n), hence using expressions that are syntacticallyabsent of the loop. Is the previous remark wrong then ?This thesis presents new insights on loops containing linear and polynomial instructions. It is already known that linear loops are polynomially expressive, in the sense that if a variable evolves linearly, then any monomial of this variable evolves linearly. The first contribution of this thesis is the extraction of a class of polynomial loops that is exactly as expressive as linear loops, in the sense that there exist a linear loop with the exact same behavior. Then, two new methods for generating invariants are presented.The first method is based on abstract interpretation and is focused on a specific kind of linear loops called linear filters. Linear filters play a role in many embedded systems (plane sensors for example) and require the use of floating point operations, that may be imprecise and lead to errors if they are badly handled. Also, the presence of non deterministic assignments makes their analysis even more complex.The second method treats of a more generic subject by finding a complete set of linear invariants of linear loops that is easily computable. This technique is based on the linear algebra concept of eigenspace. It is extended to deal with conditions, nested loops and non determinism in assignments.Generating invariants is an interesting topic, but it is not an end in itself, it must serve a purpose. This thesis investigates the expressivity of invariantsgenerated by the second method by generating counter examples for the Kannan-Lipton Orbit problem.It also presents the tool PILAT implementing this technique and compares its efficiency technique with other state-of-the-art invariant synthesizers. The effective usefulness of the invariants generated by PILAT is demonstrated by using the tool in concert with CaFE, a model-checker for C programs based on temporal logics
Déharbe, David. "Vérification formelle de propriétés temporelles : étude et application au langage VHDL." Université Joseph Fourier (Grenoble ; 1971-2015), 1996. http://www.theses.fr/1996GRE10229.
Full textGuthmuller, Marion. "Vérification dynamique formelle de propriétés temporelles sur des applications distribuées réelles." Thesis, Université de Lorraine, 2015. http://www.theses.fr/2015LORR0090/document.
Full textWhile computers have become ubiquitous in our current society, ensuring the software quality takes on an increasing importance. One of the requirements to enhance this quality is the system correctness. In this thesis, we are particularly interested in distributed systems implementing one or more programs executed on several machines which communicate with each other through a network. Ensuring the system correctness is more difficult in this context, due to their heterogeneity but also their common characteristics. Corresponding algorithms are sometimes complex and the prediction of their behavior may be difficult to realize without an advanced study. The work done during this thesis implement the dynamic formal verification of some temporal properties on legacy distributed applications. This approach consists of checking the real implementation of an application by its systematic execution. The challenge in this approach is how to apply the methods derived from Model checking in the context of the verification of legacy distributed applications (without access to source code) and no longer on abstract models. For that, we propose in a first step a dynamic semantic analysis of a system state permitting the detection of identical states. Then, we implement the dynamic formal verification of some temporal properties: liveness properties, specified with the LTL_X logic, and the communications determinism in MPI applications. These contributions are experimentaly validated and evaluated with different series of experiments
Bojan, Marinković. "Interconnection of Heterogeneous Overlay Networks: Definition, Formalization and Applications." Phd thesis, Univerzitet u Novom Sadu, Fakultet tehničkih nauka u Novom Sadu, 2014. http://www.cris.uns.ac.rs/record.jsf?recordId=89489&source=NDLTD&language=en.
Full textDoktorska disertacija se bavi temama vezanim za prekrivajuće mreže, njihovomdefinicijom, formalizacijom i primenama. Dati su opisi Chord i Synapse protokolakorišćenjem ASM formalizma, kao i dokaz korektnosti formalizacije Chord protokolana visokom nivou, kao i njegovo profinjenje. Izvršena je verovatnosna ocena uspešnosti pretrage pomoću Synapse protokola. Predstavljena je ažurirana verzija Predloga sheme meta podataka za pokretna kulturna dobra, kao i Predlog sheme meta podataka za opis kolekcija. Implementiran je Distribuirani katalog digitalizovanih kolekcija kulturne baštine Srbije zasnovan na Chord protokolu.
Graja, Zaineb. "Vérification formelle des systèmes multi-agents auto-adaptatifs." Thesis, Toulouse 3, 2015. http://www.theses.fr/2015TOU30105/document.
Full textA major challenge for the development of self-organizing MAS is to guarantee the convergence of the system to the overall function expected by an external observer and to ensure that agents are able to adapt to changes. In the literature, several works were based on simulation and model-checking to study self-organizing MAS. The simulation allows designers to experiment various settings and create some heuristics to facilitate the system design. Model checking provides support to discover deadlocks and properties violations. However, to cope with the complexity of self-organizing MAS, the designer also needs techniques that support not only verification, but also the development process itself. Moreover, such techniques should support disciplined development and facilitate reasoning about various aspects of the system behavior at different levels of abstraction. In this thesis, three essential contributions were made in the field of formal development and verification of self-organizing MAS: a formalization with the Event-B language of self-organizing MAS key concepts into three levels of abstraction, an experimentation of a top-down refinement strategy for the development of self-organizing MAS and the definition of a bottom-up refinement process based on refinement patterns
Baud-Berthier, Guillaume. "Encodage Efficace des Systèmes Critiques pour la Vérificaton Formelle par Model Checking à base de Solveurs SAT." Thesis, Bordeaux, 2018. http://www.theses.fr/2018BORD0147/document.
Full textThe design of electronic circuits and safety-critical software systems in railway or avionic domains for instance, is usually associated with a formal verification process. More precisely, test methods for which it is hard to show completeness are combined with approaches that are complete by definition. Model Checking is one of those approaches and is probably the most prevalent in industry. Reasons of its success are mainly due to two characteristics, namely: (i) its fully automatic aspect, and (ii) its ability to produce a short execution trace of undesired behaviors, which is very helpful for designers to fix the issues. However, the increasing complexity of systems to be verified is a real challenge for the scalability of existing techniques. To tackle this challenge, different model checking algorithms (e.g., symbolic model checking, interpolation), various complementary methods (e.g., abstraction, automatic generation of invariants) and multiple decision procedures (e.g., decision diagram, SMT solver) can be considered. In this thesis, we particularly focus on temporal induction. It is a model checking algorithm widely used in the industry to check safety-critical systems. This is also the core algorithm of the tool developed within SafeRiver, company in which this thesis was carried out. More precisely, temporal induction consists of a combination of BMC (Bounded Model Checking) and k-induction. BMC is a very efficient bugfinding method. While k-induction adds a termination criterion to BMC when the system does not admit bugs. These two techniques generate formulas for which it is necessary to determine their satisfiability. To this end, we use a SAT solver as a decision procedure to determine whether a propositional formula has a solution. The main contribution of this thesis aims to strengthen the collaboration between the SAT solver and the model checker. The improvements proposed mainly focus on increasing the interconnections of these two modules by exploiting the high-level structure of the problem.We have therefore defined several methods taking advantage of the symmetrical structure of the formulas. This structure emerges during the successive unfolding of the transition relation, and allows us to duplicate clauses or even unroll the transitions in different directions (i.e., forward or backward). We also established a communication between the solver and the model checker, which has for purpose to: (i) simplify the model checker representation using the information inferred by the solver, and (ii) assist the solver during resolution with simplifications performed on the high-level representation. Another important contribution of this thesis is the empirical evaluation of the proposed algorithms on well-established benchmarks. This is achieved concretely via the implementation of a model checker taking AIG (And-Inverter Graph) as input, from which we were able to evaluate the effectiveness of our algorithms
Nguyên, Duy-Tùng. "Vérification symbolique de modèles à l'aide de systèmes de ré-écriture dédiés." Phd thesis, Université d'Orléans, 2010. http://tel.archives-ouvertes.fr/tel-00579490.
Full textDernaïka, Farah. "A posteriori log analysis and security rules violation detection." Thesis, Ecole nationale supérieure Mines-Télécom Atlantique Bretagne Pays de la Loire, 2020. http://www.theses.fr/2020IMTA0210.
Full textIn certain sensitive environments, such as the healthcare domain, where users are generally trusted and where particular events may occur, such as emergencies, the implemented security controls in the corresponding information systems should not block certain decisions and actions of users. This could have serious consequences. Indeed, it is important to be able to identify and trace these actions and decisions in order to detect possible violations of the security policy put in place and fix responsibilities. These functions are ensured by the a posteriori access control that lies on a monitoring mechanism based on logs. In the literature, this type of access control hasbeen divided into three stages: log processing, log analysis, and accountability. In this thesis, we cover these three areas of the a posteriori access control by providing new solutions, and we introduce new aspects that have not been addressed before
Stamenkovich, Joseph Allan. "Enhancing Trust in Autonomous Systems without Verifying Software." Thesis, Virginia Tech, 2019. http://hdl.handle.net/10919/89950.
Full textMaster of Science
Autonomous systems are surprisingly vulnerable, not just from malicious hackers, but from design errors and oversights. The lines of code required can quickly climb into the millions, and the artificial decision algorithms can be inscrutable and fully dependent upon the information they are trained on. These factors cause the verification of the core software running our autonomous cars, drones, and everything else to be prohibitively difficult by traditional means. Independent safety monitors are implemented to provide internal oversight for these autonomous systems. A semi-automatic design process efficiently creates error-free monitors from safety rules drones need to follow. These monitors remain separate and isolated from the software typically controlling the system, but use the same sensor information. They are embedded in the circuitry and act as their own small, task-specific processors watching to make sure a particular rule is not violated; otherwise, they take control of the system and force corrective behavior. The monitors are added to a consumer off-the-shelf (COTS) drone to demonstrate their effectiveness. For every rule monitored, an override is triggered when they are violated. Their effectiveness depends on reliable sensor information as with any electronic component, and the completeness of the rules detailing these monitors.
Methni, Amira. "Méthode de conception de logiciel système critique couplée à une démarche de vérification formelle." Thesis, Paris, CNAM, 2016. http://www.theses.fr/2016CNAM1057/document.
Full textSoftware systems are critical and complex. In order to guarantee their correctness, the use of formal methodsis important. These methods can be defined as mathematically based techniques, languages and tools for specifying and reasoning about systems. But, the application of formal methods to software systems, implemented in C, is challenging due to the presence of pointers, pointer arithmetic andinteraction with hardware. Moreover, software systems are often concurrent, making the verification process infeasible. This work provides a methodology to specify and verify C software systems usingmodel-checking technique. The proposed methodology is based on translating the semantics of Cinto TLA+, a formal specification language for reasoning about concurrent and reactive systems. We define a memory and execution model for a sequential program and a set of translation rules from C to TLA+ that we developed in a tool called C2TLA+. Based on this model, we show that it can be extended to support concurrency, synchronization primitives and process scheduling. Although model-checking is an efficient and automatic technique, it faces the state explosion problem when the system becomes large. To overcome this problem, we propose a state-space reduction technique. The latter is based on agglomerating a set of C instructions during the generation phase of the TLA+ specification. This methodology has been applied to a concrete case study, a microkernel of an industrial real-time operating system, on which a set of functional properties has been verified. The application of the agglomeration technique to the case study shows the usefulness of the proposed technique in reducing the complexity of verification. The obtained results allow us to study the behavior of the system and to find errors undetectable using traditional testing techniques
Tacla, Saad Rodrigo. "Parallel model checking for multiprocessor architecture." Thesis, Toulouse, INSA, 2011. http://www.theses.fr/2011ISAT0028/document.
Full textIn this thesis, we propose and study new algorithms and data structures for model checking finite-state, concurrent systems. We focus on techniques that target shared memory, multi-cores architectures, that are a current trend in computer architectures.In this context, we present new algorithms and data structures for exhaustive parallel model checking that are as efficient as possible, but also ``friendly'' with respect to the work-sharing policies that are used for the state space generation (e.g. a work-stealing strategy): at no point do we impose a restriction on the way work is shared among the processors. This includes both the construction of the state space as the detection of cycles in parallel, which is is one of the key points of performance for the evaluation of more complex formulas.Alongside the definition of enumerative, model checking algorithms for many-cores architectures, we also study probabilistic verification algorithms. By the term probabilistic, we mean that, during the exploration of a system, any given reachable state has a high probability of being checked by the algorithm. Probabilistic verification trades savings at the level of memory usage for the probability of missing some states. Consequently, it becomes possible to analyze part of the state space of a system when there is not enough memory available to represent the entire state space in an exact manner