Dissertations / Theses on the topic 'Formal verification'
To see the other types of publications on this topic, follow the link: Formal 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 'Formal 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.
1
Tristan, Jean-Baptiste. "Formal verification of translation validators." Phd thesis, Université Paris-Diderot - Paris VII, 2009. http://tel.archives-ouvertes.fr/tel-00437582.
Full textAbstract:
Comme tout logiciel, les compilateurs, et tout particulièrement les compilateurs optimisant, peuvent être défectueux. Il est donc possible qu'ils changent la sémantique du programme compilé, et par conséquent ses propriétés. Dans le cadre de développement de logiciels critiques, où des méthodes formelles sont utilisées pour s'assurer qu'un programme satisfait certaines propriétés, et cela avant qu'il soit compilé, cela pose un problème de fond. Une solution à ce problème est de vérifier le compilateur en s'assurant qu'il préserve la sémantique des programmes compilés. Dans cette thèse, nous évaluons une méthode nouvelle pour développer des passes de compilations sûres: la vérification formelle de validateurs de traduction. D'une part, cette méthode utilise la vérification formelle à l'aide d'assistant de preuve afin d'offrir le maximum de garanties de sûreté sur le compilateur. D'autre part, elle repose sur l'utilisation de la validation de traduction, où chaque exécution du compilateur est validée a posteriori, une méthode de vérification plus pragmatique qui a permis de vérifier des optimisations avancées. Nous montrons que cette approche nouvelle du problème de la vérification de compilateur est viable, et même avantageuse dans certains cas, à travers quatre exemples d'optimisations réalistes et agressives: le list scheduling, le trace scheduling, le lazy code motion et enfin le software pipelining.
2
Trinh, Cong Quy. "Formal Verification of Skiplist Algorithms." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-160314.
Full text
3
Dragomir, Ciprian. "Formal verification of P systems." Thesis, University of Sheffield, 2016. http://etheses.whiterose.ac.uk/15452/.
Full textAbstract:
Membrane systems, also known as P systems, constitute an innovative computational paradigm inspired by the structure and dynamics of the living cell. A P system consists of a hierarchical arrangement of compartments and a finite set of multiset rewriting and communication rules, which operate in a maximally parallel manner. The organic vision of concurrent dynamics captured by membrane systems stands in antithesis with conventional formal modelling methods which focus on algebraic descriptions of distributed systems. As a consequence, verifying such models in a mathematically rigorous way is often elusive and indeed counter-intuitive when considering established approaches, which generally require sequential process representations or highly abstract theoretical frameworks. The prevalent investigations with this objective in the field of membrane computing are ambivalent and inconclusive in the wider application scope of P systems. In this thesis we directly address the formal verification of membrane systems by means of model checking. A fundamental distinction between the agnostic perspective on parallelism, advocated by process calculi, and P systems' emblematic maximally parallel execution strategy is identified. On this basis, we establish that an intuitional translation to traditional process models is inadequate for the purpose of formal verification, due to a state space growth disparity. The observation is essential for this research project: on one hand it implies the feasibility of model checking P systems, and on the other hand it underlines the suitability of this formal verification technique in the context of membrane computing. Model checking entails an exhaustive state space exploration and does not derive inferences based on the independent instructions comprising a state transition. In this respect, we define a new sequential modelling strategy which is optimal for membrane systems and targets the SPIN formal verification tool. We introduce elementary P systems, a distributed computational model which subsumes the feature diversity of the membrane computing paradigm and distils its functional vocabulary. A suite of supporting software tools which gravitate around this formalism has also been developed, comprising of 1. the eps modelling language for elementary P systems; 2. a parser for the eps specification; 3. a model simulator and 4. a translation tool which targets the Promela specification of the SPIN model checker. The formal verification approach proposed in this thesis is progressively demonstrated in four heterogeneous case studies, featuring 1. a parallel algorithm applicable to a structured model; 2. a linear time solution to an NP-complete problem; 3. an innovative implementation of the Dining Philosophers scenario (a synchronisation problem) using an elementary P system and 4. a quantitative analysis of a simple random process implemented without the support of a probabilistic model.
4
Hurd, J. "Formal verification of probabilistic algorithms." Thesis, University of Cambridge, 2001. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.604823.
Full textAbstract:
We begin with an extensive foundational development of probability, creating a higher-order logic formalization of mathematical measure theory. This allows the definition of the probability space we use to model a random bit generator, which informally is a stream of coin-flips, or technically an infinite sequence of IID Bernoulli( 1/2 ) random variables. Probabilistic programs are modified using the state-transformer monad familiar from functional programming, where the random bit generator is passed around in the computation. Functions remove random bits from the generator to perform their calculation, and then pass back the changed random bit generator with the result. Our probability space modelling the random bit generator allows us to give precise probabilistic specifications of such programs, and then verify them in the theorem prover. We also develop technical support designed to expedite verification: probabilistic quantifiers; a compositional property subsuming measurability and independence; a probabilistic while loop together with a formal concept of termination with probability 1. We also introduce a technique for reducing properties of a probabilistic while loop to properties of programs that are guaranteed to terminate: these can then be established using induction and standard methods of program correctness. We demonstrate the formal framework with some example probabilistic programs, samples algorithms for four probability distributions; some optimal procedures for generating dice rolls from coin flips; the symmetric simple random walk. In addition, we verify the Miller-Rabin primality test, a well-known and commercially used probabilistic algorithm. Our fundamental perspective allows us to define a version with strong properties, which we can execute in the logic to prove compositeness of numbers.
5
Botinčan, Matko. "Formal verification-driven parallelisation synthesis." Thesis, University of Cambridge, 2018. https://www.repository.cam.ac.uk/handle/1810/274136.
Full textAbstract:
Concurrency is often an optimisation, rather than intrinsic to the functional behaviour of a program, i.e., a concurrent program is often intended to achieve the same effect of a simpler sequential counterpart, just faster. Error-free concurrent programming remains a tricky problem, beyond the capabilities of most programmers. Consequently, an attractive alternative to manually developing a concurrent program is to automatically synthesise one. This dissertation presents two novel formal verification-based methods for safely transforming a sequential program into a concurrent one. The first method---an instance of proof-directed synthesis---takes as the input a sequential program and its safety proof, as well as annotations on where to parallelise, and produces a correctly-synchronised parallelised program, along with a proof of that program. The method uses the sequential proof to guide the insertion of synchronisation barriers to ensure that the parallelised program has the same behaviour as the original sequential version. The sequential proof, written in separation logic, need only represent shape properties, meaning we can parallelise complex heap-manipulating programs without verifying every aspect of their behaviour. The second method proposes specification-directed synthesis: given a sequential program, we extract a rich, stateful specification compactly summarising program behaviour, and use that specification for parallelisation. At the heart of the method is a learning algorithm which combines dynamic and static analysis. In particular, dynamic symbolic execution and the computational learning technique grammar induction are used to conjecture input-output specifications, and counterexample-guided abstraction refinement to confirm or refute the equivalence between the conjectured specification and the original program. Once equivalence checking succeeds, from the inferred specifications we synthesise code that executes speculatively in parallel---enabling automated parallelisation of irregular loops that are not necessary polyhedral, disjoint or with a static pipeline structure.
6
Jobredeaux, Romain J. "Formal verification of control software." Diss., Georgia Institute of Technology, 2015. http://hdl.handle.net/1853/53841.
Full textAbstract:
In a context of heightened requirements for safety-critical embedded systems and
ever-increasing costs of verification and validation, this research proposes to
advance the state of formal analysis for control software. Formal methods are a
field of computer science that uses mathematical techniques and formalisms to
rigorously analyze the behavior of programs. This research develops a framework
and tools to express and prove high level properties of control law
implementations. One goal is to bridge the gap between control theory and
computer science. An annotation language is extended with symbols and axioms to
describe control-related concepts at the code level. Libraries of theorems,
along with their proofs, are developed to enable an interactive proof assistant
to verify control-related properties. Through integration in a prototype tool,
the process of verification is made automatic, and applied to several example systems.In a context of heightened requirements for safety-critical embedded systems and
ever-increasing costs of verification and validation, this research proposes to
advance the state of formal analysis for control software. Formal methods are a
field of computer science that uses mathematical techniques and formalisms to
rigorously analyze the behavior of programs. This research develops a framework
and tools to express and prove high level properties of control law
implementations. One goal is to bridge the gap between control theory and
computer science. An annotation language is extended with symbols and axioms to
describe control-related concepts at the code level. Libraries of theorems,
along with their proofs, are developed to enable an interactive proof assistant
to verify control-related properties. Through integration in a prototype tool,
the process of verification is made automatic, and applied to several example systems.
7
Parikh, Ankur. "Abstraction Guided Semi-formal Verification." Thesis, Virginia Tech, 2007. http://hdl.handle.net/10919/33596.
Full textAbstract:
Abstraction-guided simulation is a promising semi-formal framework for design validation in which an abstract model of the design is used to guide a logic simulator towards a target property. However, key issues still need to be addressed before this framework can truly deliver on it's promise. Concretizing, or finding a real trace from an abstract trace, remains a hard problem. Abstract traces are often spurious, for which no corresponding real trace exits. This is a direct consequence of the abstraction being an over-approximation of the real design. Further, the way in which the abstract model is constructed is an open-ended problem which has a great impact on the performance of the simulator.
In this work, we propose a novel approaches to address these issues. First, we present a genetic algorithm to select sets of state variables directly from the gate-level net-list of the design, which are highly correlated to the target property. The sets of selected variables are used to build the Partition Navigation Tracks (PNTs). PNTs capture the behavior of expanded portions of the state space as they related to the target property. Moreover, the computation and storage costs of the PNTs is small, making them scale well to large designs.
Our experiments show that we are able to reach many more hard-to-reach states using our proposed techniques, compared to state-of-the-art methods.
Next, we propose a novel abstraction strengthening technique, where the abstract design is constrained to make it more closely resemble the concrete design. Abstraction strengthening greatly reduces the need to refine the abstract model for hard to reach properties. To achieve this, we efficiently identify sequentially unreachable partial sates in the concrete design via intelligent partitioning, resolution and cube enlargement. Then, these partial states are added as constraints in the abstract model. Our experiments show that the cost to compute these constraints is low and the abstract traces obtained from the strengthened abstract model are far easier to concretize.Master of Science
8
Bubel, Richard. "Formal verification of recursive predicates." [S.l. : s.n.], 2007. http://digbib.ubka.uni-karlsruhe.de/volltexte/1000008366.
Full text
9
Suresh, Amrita. "Formal Verification of Communicating Automata." Electronic Thesis or Diss., université Paris-Saclay, 2022. http://www.theses.fr/2022UPASG092.
Full textAbstract:
Les systèmes distribués concernent des processus qui s’exécutent indépendamment et communiquent de manière asynchrone. Bien qu’ils couvrent un large éventail de cas d’utilisation et soient donc omniprésents dans notre monde, il est particulièrement difficile de garantir leur exactitude. Dans cette thèse, nous modélisons de tels systèmes en utilisant une formulation mathématique et logique, et nousles vérifions algorithmiquement. En particulier, nous nous concentrons sur les automates FIFO (First In First Out), et plus précisément sur des systèmes à un ou plusieurs automates finis qui communiquent via des canaux FIFO fiables pouvant contenir des mots de longueur arbitrairement grande. Comme la plupart des problèmes de vérification sont connus pour être indécidables pour les automates FIFO, nous nous concentrons sur diverses sous-classes et approximations du modèle. Le premier modèle que nous considérons est celui des systèmes de transition bien structurés sur les branches d’états accessibles (branch-WSTS), une classe qui inclut strictement la classe des WSTS. Nous étudions les problèmes de finitude des canaux et de terminaison pour de tels systèmes, et nous en montrons quelques exemples. Nous définissons également une autre classe de systèmes où la condition de monotonie est relâchée et nous montrons qu’une variante du problème de couerture est décidable sous des conditions naturelles d’effectivité. Nous étudions ensuite la restriction de la limitation de l’entrée (input-boundedness) sur les canaux FIFO et nous montrons que l’accessibilité rationnelle et diverses autres propriétés sont décidables pour les automates FIFO. Ce faisant, nous répondons à une question ouverte concernant l’accessibilité des automates FIFO limités en entrée. Nous dérivons également certaines bornes de complexité en considérant le cas le plus simple, un automate FIFO avec un seul canal. Une autre restriction que nous étudions est la synchronisabilité dans les systèmes communicants. En particulier, nous étudions cette notion pour les MSCs (Message Sequence Charts), qui est un modèle pour représenter les exécutions d’un système communicant. Nous montrons que si un ensemble quelconque de MSC satisfait les deux propriétés suivantes, à savoir la définissabilité MSO (Monadic Second-order Logic) et la (spécial) largeur d’arbre (tree-width) bornée, alors la synchronisabilité est décidable. De plus, l’accessibilité et le model checking sont également décidables dans ce cadre. Nous unifions alors certaines classes de la littérature à l’aide de ce cadre, et pour certaines autres classes, nous montrons leur indécidabilitéDistributed systems involve processes that run independently and communicate asynchronously. While they capture a wide range of use cases and are hence, ubiquitous in our world, it is also particularly difficult to ensure their correctness. In this thesis, we model such systems using mathematical and logical formulation, and try to algorithmically verify them. In particular, we focus on FIFO (First In First Out) machines, with one or more finite-state machines communicating via unbounded reliable FIFO buffers.As most verification problems are known to be undecidable for FIFO machines, we focus on various subclasses and approximations of the model. The first model we consider are branch-well structured transition systems (branch-WSTS), a class which strictly includes the well-known class of WSTS. We study the problems of boundedness and termination for such systems, and demonstrate some examples of them. We also define another class of systems where the monotony condition is relaxed and show that a variant of the coverability problem is decidable under effectivity conditions.We then study the restriction of input-boundedness on FIFO machines, and show that rational reachability and various other properties are decidable for FIFO machines under the input-bounded restriction. In doing so, we answer a long standing open question regarding the reachability for input-bounded FIFO machines. We also derive some complexity bounds by considering the simplest case, a FIFO machine with a single channel.Another restriction that we study is synchronizability in communicating systems. In particular, we study this notion for MSCs (Message Sequence Charts), which is a model to represent executions of a communicating system. We show that if any set of MSCs can satisfy two properties, namely MSO (Monadic Second-order Logic) definability and bounded (special-)tree width, then synchronizability is decidable. Moreover, reachability and model-checking are also decidable within this framework. We also unify some classes from the literature using this framework, and for some other classes, show their undecidability
10
Wei, Jijie. "Formal verification of a digital PLL." Thesis, University of British Columbia, 2014. http://hdl.handle.net/2429/50048.
Full textAbstract:
Common AMS circuit are composed from blocks that can be modeled accurately using linear differential inclusions to enable verification of important properties using reachability analysis. This dissertation presents a formal verification of Digital Phase Locked Loop (PLL) using reachability techniques.
PLLs are ubiquitous in analog mixed signal (AMS) designs and are widely used in modern communication equipment, clock generation for CPUs in computers, clock-acquisition in high-speed links etc. The most important property of a PLL is convergence, which means starting from any possible initial conditions, the PLL will eventually lock to the desired equilibrium. We model the digital PLL as a set of Ordinary Differential equation (ODEs), and discretize the weakly non-linear ODEs to linear differential inclusions. The transformation not only provides us an over approximation of the verification problem but also provides the basis for a sound proof.
We present the verification of a digital PLL using real tools, SpaceEx and Coho. In particular, we show how each component of the digital PLL can be modelled as a hybrid automaton. Due to the large number of transitions caused by the model, the whole proof is established by several lemmas. Interesting problems such as a timing glitch in the Phase Frequency Detector (PFD) are discussed and triggering conditions are formally proved in the dissertation. Global convergence is demonstrated by both tools.
Based on the digital PLL circuit and the challenges that arose during our verification, the error bounds, limitations, implementation differences and usability of the two leading tools are carefully evaluated. SpaceEx provides a graphical user interface that makes it easy to get started with simple examples but requires extensive user interaction for larger problems. The interface to Coho is a MATLAB API. While this lacks the packaged-tool feel of SpaceEx, it provides a flexible way to break a large verification problem into smaller lemmas and allows the proof to be ''re-executed'' simply by re-executing the MATLAB script.Science, Faculty of
Computer Science, Department of
Graduate
11
Pike, Lee. "Formal verification of time-triggered systems." [Bloomington, Ind.] : Indiana University, 2006. http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:3215296.
Full textAbstract:
Thesis (Ph.D.)--Indiana University, Dept. of Computer Science, 2006.Source: Dissertation Abstracts International, Volume: 67-04, Section: B, page: 2086. Adviser: Steven D. Johnson. "Title from dissertation home page (viewed June 20, 2007)."
12
Brückner, Ingo. "Slicing integrated formal specifications for verification /." Oldenburg : Univ., Fak. II, Dep. für Informatik, 2008. http://bvbr.bib-bvb.de:8991/F?func=service&doc_library=BVB01&doc_number=016564256&line_number=0001&func_code=DB_RECORDS&service_type=MEDIA.
Full text
13
Arnaud, Mathilde. "Formal verification of secured routing protocols." Phd thesis, École normale supérieure de Cachan - ENS Cachan, 2011. http://tel.archives-ouvertes.fr/tel-00675509.
Full textAbstract:
With the development of digital networks, such as Internet, communication protocols are omnipresent. Digital devices have to interact with each other in order to perform the numerous and complex tasks we have come to expect as commonplace, such as using a mobile phone, sending or receiving electronic mail, making purchases online and so on. In such applications, security is important. For instance, in the case of an online purchase, the right amount of money has to be paid without leaking the buyer personal information to outside parties. Communication protocols are the rules that govern these interactions. In order to make sure that they guarantee a certainlevel of security, it is desirable to analyze them. Doing so manually or by testing them is not enough, as attacks can be quite subtle. Some protocols have been used for years before an attack was discovered. Because of their increasing ubiquity in many important applications, e.g. electronic commerce, a very important research challenge consists in developing methods and verification tools to increase our trust on security protocols, and so on the applications that rely on them. For example, more than 28 billion Euros were spent in France using Internet transactions, and the number is growing. Moreover, new types of protocols are continuously appearing in order to face new technological and societal challenges, e.g. electronic voting, electronic passport to name a few.
14
Compton, Michael James. "Formal verification of process algebra systems." Thesis, University of Cambridge, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.612067.
Full text
15
Myreen, Magnus Oskar. "Formal verification of machine-code programs." Thesis, University of Cambridge, 2009. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.611450.
Full text
16
Olthuis, Jorrit. "Verification of Formal Requirements through Tracing." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-289947.
Full textAbstract:
Software development in the railway application is governed by strict standards which aim to ensure safety. It is for example highly recommended to use formal methods when specifying requirements. Moreover, it is mandatory to have certain roles be fulfilled by different people. A common technique is developing software tests for the requirements. Making sure that software requirements are properly described, interpreted and implemented by different people is a major challenge. Tests fully depend on the tester to cover all scenarios. Having more methods that simplify requirement tracing and that depends less on thoroughness of the tester would provide many benefits. This thesis investigates whether and how software tracing can be used to validate formal requirements of software. The goal is to perform trace validation such that it can be used to complement more traditional verification techniques. By verifying formal requirements on traces, the detection of errors depends on the events in the traces. As a consequence, more traces provide a higher chance of detecting errors. Thereby eliminating risk of the tester missing important cases. The presented verification approach firstly specifies requirements in linear temporal logic and converts this specification to a non-deterministic Büchi automaton, or a finite state machine which is also evaluated. Secondly, the approach describes several alternatives for collecting traces and how to link those to the formal specification. Lastly, the verification approach proposes an algorithm which takes the Büchi automaton and a trace to detect violations of the requirement. The validation approach is implemented in form of multiple tools and its operation shown by means of a toy example. This example models a railway application such that its requirements can be verified using the tools. The results are then used to show how these tools can be used in an actual railway application. Using these research outcomes, and the stand-alone tool, an implementation in Trace Compass is created. This can, just like the stand-alone tool, decide for each pair of trace and requirement whether the trace violates the requirement.Programvaruutveckling i järnvägsapplikationen styrs av strikta standarder som syftar till att säkerställa säkerheten. Det rekommenderas till exempel starkt att använda formella metoder när krav anges. Dessutom är det obligatoriskt att vissa roller uppfylls av olika ingenjörer. En vanlig teknik är att utveckla programvarutest för kraven. Det är en stor utmaning att se till att programvarukrav beskrivs, tolkas och implementeras på rätt sätt av olika ingenjörer. Tester beror helt på testaren för att täcka alla scenarier. Att ha fler metoder som förenklar spårning av krav och som beror mindre på testarens noggrannhet skulle ge många fördelar. Denna avhandling undersöker om och hur spårning av programvara (software tracing) kan användas för att värdera formella krav på programvara. Målet är att utföra spårningsvalidering så att den kan användas för att komplettera mer traditionella verifieringstekniker. Genom att verifiera formella krav på spår (trace) beror upptäckten av fel på händelserna i spåren. Som en konsekvens ger fler spår större möjlighet för att detektera fel. Därmed elimineras risken för att testaren missar viktiga fall. Den presenterade verifieringsmetoden specificerar först kraven i linear temporal logic och omvandlar denna specifikation till en icke-deterministisk Büchi-automat, eller en ändlig tillståndsautomat som också utvärderas. För det andra beskriver tillvägagångssättet flera alternativ för att samla in spår och hur man länkar dem till den formella specifikationen. Slutligen föreslår verifieringsmetoden en algoritm som tar Büchi-automaten och ett spår för att upptäcka överträdelser av kravet. Valideringsmetoden implementeras i form av flera verktyg och dess funktion visas med hjälp av ett leksaksexempel. Detta exempel modellerar en järnvägsapplikation så att dess krav kan verifieras med verktygen. Resultaten används sedan för att visa hur dessa verktyg kan användas i en verklig järnvägsapplikation. Med hjälp av dessa forskningsresultat och det fristående verktyget skapas en implementering i Trace Compass. Detta kan, precis som det fristående verktyget, avgöra för varje par av spår och krav om spårningen bryter mot kravet.
17
Limaye, Chinmay Avinash. "Formal Verification Techniques for Reversible Circuits." Thesis, Virginia Tech, 2011. http://hdl.handle.net/10919/33406.
Full textAbstract:
As the number of transistors per unit chip area increases, the power dissipation of the chip becomes a bottleneck. New nano-technology materials have been proposed as viable alternatives to CMOS to tackle area and power issues. The power consumption can be minimized by the use of reversible logic instead of conventional combinational circuits. Theoretically, reversible circuits do not consume any power (or consume minimal power) when performing computations. This is achieved by avoiding information loss across the circuit. However, use of reversible circuits to implement digital logic requires development of new Electronic Design Automation techniques. Several approaches have been proposed and each method has its own pros and cons. This often results in multiple designs for the same function. Consequently, this demands research in efficient equivalence checking techniques for reversible circuits.
This thesis explores the optimization and equivalence checking of reversible circuits. Most of the existing synthesis techniques work in two steps â generate an original, often sub-optimal, implementation for the circuit followed optimization of this design. This work proposes the use of Binary Decision Diagrams for optimization of reversible circuits. The proposed technique identifies repeated gate (trivial) as well as non-contiguous redundancies in a reversible circuit. Construction of a BDD for a sub-circuit (obtained by sliding a window of fixed size over the circuit) identifies redundant gates based upon the redundant variables in the BDD. This method was unsuccessful in identifying any additional redundancies in benchmark circuits; however, hidden non-contiguous redundancies were consistently identified for a family of randomly generated reversible circuits. As of now, several research groups focus upon efficient synthesis of reversible circuits. However, little work has been done in identification of redundant gates in existing designs and the proposed peephole optimization method stands among the few known techniques. This method fails to identify redundancies in a few cases indicating the complexity of the problem and the need for further research in this area.
Even for simple logical functions, multiple circuit representations exist which exhibit a large variation in the total number of gates and circuit structure. It may be advantageous to have multiple implementations to provide flexibility in choice of implementation process but it is necessary to validate the functional equivalence of each such design. Equivalence checking for reversible circuits has been researched to some extent and a few pre-processing techniques have been proposed prior to this work. One such technique involves the use of Reversible Miter circuits followed by SAT-solvers to ascertain equivalence. The second half of this work focuses upon the application of the proposed reduction technique to Reversible Miter circuits as a pre-processing step to improve the efficiency of the subsequent SAT-based equivalence checking.Master of Science
18
Vimjam, Vishnu Chaithanya. "Strategies for SAT-Based Formal Verification." Diss., Virginia Tech, 2007. http://hdl.handle.net/10919/26078.
Full textAbstract:
Verification of digital hardware designs is becoming an increasingly complex task as the designs are incorporating more functionality, becoming complex and growing larger in size. Today, verification remains a bottleneck in meeting time-to-market requirements and consumes more than 70% of the overall design-costs. Traditionally, verification has been done using simulation-based approaches, where a set of appropriate test-stimuli is used by the designer. As the designs become more complex, however, simulation-based techniques often fail to capture corner-case errors. Furthermore, unless exhaustively tested, these approaches do not guarantee the correctness of a system with respect to its specifications. As a consequence, formal methods for design verification have been sought after. In formal verification, the conformance of a design to a given set of specifications is proven mathematically, thereby leaving no room for unexplored search spaces. Despite the exponential time/memory complexities often involved within the formal approaches, they have shown promise in capturing subtle bugs, which were missed otherwise.
In this dissertation, we focus on Boolean Satisfiability (SAT) based formal verification, which has gained tremendous importance in the recent past. Importantly, SAT-based approaches often alleviate the memory explosion problem, which had been a bottleneck of the traditional symbolic (Binary Decision Diagram based) approaches. In SAT-based techniques, the set of verification tasks are converted into a set of Boolean formulae, which are checked for satisfiability using a SAT solver. These problems are often NP-complete and are prone to an explosion in the required run-time. To overcome this, we propose novel strategies which utilize both structural and logical information of a sequential circuit. In particular, we devise techniques to extract non-trivial invariants of a design, strengthen properties such that they can be proven faster and interleave bounded reachability analysis with bounded model checking. We provide the necessary algorithms and implementation details in order to automate the proposed techniques. Experiments conducted on a variety of benchmark circuits show that orders of magnitude improvement in overall run-times can be achieved via our techniques compared to the existing state-of-the-art SAT-based approaches.Ph. D.
19
Lu, Tianxiang. "Formal verification of the Pastry protocol." Thesis, Université de Lorraine, 2013. http://www.theses.fr/2013LORR0179/document.
Full textAbstract:
Le protocole Pastry réalise une table de hachage distribué sur un réseau pair à pair organisé en un anneau virtuel de noeuds. Alors qu'il existe plusieurs implémentations de Pastry, il n'y a pas encore eu de travaux pour décrire formellement l'algorithme ou vérifier son bon fonctionnement. Intégrant des structures de données complexes et de la communication asynchrone entre des noeuds qui peuvent rejoindre ou quitter le réseau, ce protocole représente un intérêt certain pour la vérification formelle. La thèse se focalise sur le protocole Join de Pastry qui permet à un noeud de rejoindre le réseau. Les noeuds ayant intégré le réseau doivent avoir une vue du voisinage cohérente entre eux. La propriété principale de correction, appelée CorrectDelivery, assure qu'à tout moment il y a au plus un noeud capable de répondre à une requête pour une clé, et que ce noeud est le noeud le plus proche numériquement à ladite clé. Il n'est pas trivial de maintenir cette propriété en présence de churn. Ce travail nous a permis de découvrir des violations inattendues de la propriété dans les versions publiées de l'algorithme. Sur la base de cette analyse, le protocole IdealPastry est conçu et vérifié en utilisant l'assistant interactif à la preuve TLAPS pour TLA+. Le protocole LuPastry est obtenu en assouplissant certaines hypothèses de IdealPastry. Il est montré formellement que LuPastry vérifie CorrectDelivery sous l'hypothèse qu'aucun noeud ne quitte le réseau. Cette hypothèse ne peut être relâchée à cause du risque de perte de connexion du réseau dans le cas où plusieurs noeuds quittent le réseau en même tempsPastry is a structured P2P algorithm realizing a Distributed Hash Table over an underlying virtual ring of nodes. Several implementations of Pastry are available, but no attempt has so far been made to formally describe the algorithm or to verify its properties. Since Pastry combines complex data structures, asynchronous communication, and concurrency in the presence of spontaneous join and departure of nodes, it makes an interesting target for verification. This thesis focuses on the Join protocol of Pastry that integrates new nodes into the ring. All member nodes must have a consistent key mapping among each other. The main correctness property, named CorrectDelivery, states that there is always at most one node that can deliver an answer to a lookup request for a key and this node is the numerically closest member node to that key. This property is non-trivial to preserve in the presence of churn. In this thesis, unexpected violations of CorrectDelivery in the published versions of Pastry are discovered and analyzed using the TLA+ model checker TLC. Based on the analysis, the protocol IdealPastry is designed and verified using the interactive theorem prover TLAPS for TLA+. By relaxing certain hypotheses, IdealPastry is further improved to LuPastry, which is again formally proved correct under the assumption that no nodes leave the network. This hypothesis cannot be relaxed in general due to possible network separation when particular nodes simultaneously leave the network
20
Lu, Tianxiang. "Formal verification of the Pastry protocol." Electronic Thesis or Diss., Université de Lorraine, 2013. http://www.theses.fr/2013LORR0179.
Full textAbstract:
Le protocole Pastry réalise une table de hachage distribué sur un réseau pair à pair organisé en un anneau virtuel de noeuds. Alors qu'il existe plusieurs implémentations de Pastry, il n'y a pas encore eu de travaux pour décrire formellement l'algorithme ou vérifier son bon fonctionnement. Intégrant des structures de données complexes et de la communication asynchrone entre des noeuds qui peuvent rejoindre ou quitter le réseau, ce protocole représente un intérêt certain pour la vérification formelle. La thèse se focalise sur le protocole Join de Pastry qui permet à un noeud de rejoindre le réseau. Les noeuds ayant intégré le réseau doivent avoir une vue du voisinage cohérente entre eux. La propriété principale de correction, appelée CorrectDelivery, assure qu'à tout moment il y a au plus un noeud capable de répondre à une requête pour une clé, et que ce noeud est le noeud le plus proche numériquement à ladite clé. Il n'est pas trivial de maintenir cette propriété en présence de churn. Ce travail nous a permis de découvrir des violations inattendues de la propriété dans les versions publiées de l'algorithme. Sur la base de cette analyse, le protocole IdealPastry est conçu et vérifié en utilisant l'assistant interactif à la preuve TLAPS pour TLA+. Le protocole LuPastry est obtenu en assouplissant certaines hypothèses de IdealPastry. Il est montré formellement que LuPastry vérifie CorrectDelivery sous l'hypothèse qu'aucun noeud ne quitte le réseau. Cette hypothèse ne peut être relâchée à cause du risque de perte de connexion du réseau dans le cas où plusieurs noeuds quittent le réseau en même tempsPastry is a structured P2P algorithm realizing a Distributed Hash Table over an underlying virtual ring of nodes. Several implementations of Pastry are available, but no attempt has so far been made to formally describe the algorithm or to verify its properties. Since Pastry combines complex data structures, asynchronous communication, and concurrency in the presence of spontaneous join and departure of nodes, it makes an interesting target for verification. This thesis focuses on the Join protocol of Pastry that integrates new nodes into the ring. All member nodes must have a consistent key mapping among each other. The main correctness property, named CorrectDelivery, states that there is always at most one node that can deliver an answer to a lookup request for a key and this node is the numerically closest member node to that key. This property is non-trivial to preserve in the presence of churn. In this thesis, unexpected violations of CorrectDelivery in the published versions of Pastry are discovered and analyzed using the TLA+ model checker TLC. Based on the analysis, the protocol IdealPastry is designed and verified using the interactive theorem prover TLAPS for TLA+. By relaxing certain hypotheses, IdealPastry is further improved to LuPastry, which is again formally proved correct under the assumption that no nodes leave the network. This hypothesis cannot be relaxed in general due to possible network separation when particular nodes simultaneously leave the network
21
Powell, Daniel, and n/a. "Formal Methods For Verification Based Software Inspection." Griffith University. School of Computing and Information Technology, 2003. http://www4.gu.edu.au:8080/adt-root/public/adt-QGU20030925.154706.
Full textAbstract:
Useful processes, that are independently repeatable, are utilised in all branches of science and traditional engineering disciplines but seldom in software engineering. This is particularly so with processes used for detection and correction of defects in software systems. Code inspection, as introduced by Michael Fagan at IBM in the mid 1970's is widely recognised as an effective technique for finding defects in software. Despite its reputation, code inspection, as it is currently practiced, is not a strictly repeatable process. This is due to the problems faced by inspectors when they attempt to paraphrase the complicated semantics of a unit of computer code. Verification based software inspection, as advocated by the cleanroom software engineering community, requires that arguments of correctness be formulated with the code and its specification. These arguments rely on the reader being able to extract the semantics from the code. This thesis addresses the requirement for an independently repeatable, scalable and substantially automated method for yielding semantics from computer code in a complete, unambiguous and consistent manner in order to facilitate, and make repeatable, verification based code inspection. Current literature regarding the use of code inspection for verification of software is surveyed. Empirical studies are referenced, comparing inspection to software testing and program proof. Current uses of formal methods in software engineering will be discussed, with particular reference to formal method applications in verification. Forming the basis of the presented method is a systematic, and hence repeatable, approach to the derivation of program semantics. The theories and techniques proposed for deriving semantics from program code extend current algorithmic and heuristic techniques for deriving invariants. Additionally, the techniques introduced yield weaker forms of invariant information which are also useful for verification, defect detection and correction. Methods for using these weaker invariant forms, and tools to support these methods, are introduced. Algorithmic and heuristic techniques for investigating loop progress and termination are also introduced. Some of these techniques have been automated in supporting tools, and hence, the resulting defects can be repeatably identified. Throughout this thesis a strong emphasis is placed on describing implementable algorithms to realise the derivation techniques discussed. A number of these algorithms are implemented in a tool to support the application of the verification methods presented. The techniques and tools presented in this thesis are well suited, but not limited to, supporting rigorous methods of defect detection as well as formal and semi-formal reasoning of correctness. The automation of these techniques in tools to support practical, formal code reading and correctness argument will assist in addressing the needs of trusted component technologies and the general requirement for quality in software.
22
Pompeo, François. "A formal verification assistant for TROMLAB environment." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape7/PQDD_0003/MQ43667.pdf.
Full text
23
Lu, Jianping. "On the formal verification of ATM switches." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape8/PQDD_0001/MQ43654.pdf.
Full text
24
Zhang, Bairong. "Formal specification and verification of OSI protocols." Thesis, University of Bristol, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.337284.
Full text
25
Mancini, Loretta Ilaria. "Formal verification of privacy in pervasive systems." Thesis, University of Birmingham, 2015. http://etheses.bham.ac.uk//id/eprint/6105/.
Full textAbstract:
Pervasive systems enhance a user's everyday experience. However, the use of pervasive sensing and context aware devices can result very intrusive from a privacy perspective. A familiar pervasive device is a mobile phone. Mobile telephony equipment is daily carried everywhere. Avoiding linkability of subscribers by third parties, and protecting their privacy is one of the goals of mobile telecommunication protocols. We use experimental and formal methods to model and analyse the security properties of mobile telephony protocols. We expose novel threats to the user privacy, which make it possible to trace and identify mobile telephony subscribers, and for some of the attacks we demonstrate the feasibility of a low cost implementation. We propose fixes to these privacy issues. We prove that our privacy friendly fixes satisfy the desired unlinkability and anonymity properties. Finally, we develop the first extension of the Pro Verif tool for the automatic verification of equivalence based properties of stateful protocols. This work shows how to formally verity privacy properties of pervasive systems. Moreover, we develop an automatic verification tool for the verification of equivalence based properties of stateful protocols. Further work in this direction will eventually widen the class of security protocols and security properties verifiable using automatic verification tools.
26
Smith, Mark Anthony Shawn 1968. "Formal verification of TCP and T/TCP." Thesis, Massachusetts Institute of Technology, 1997. http://hdl.handle.net/1721.1/42779.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1997.Includes bibliographical references (p. 421-424).
by Mark Anthony Shawn Smith.
Ph.D.
27
Davidson, Timothy A. S. "Formal verification techniques using quantum process calculus." Thesis, University of Warwick, 2012. http://wrap.warwick.ac.uk/51368/.
Full textAbstract:
Quantum communication is a rapidly growing area of research and development. While the successful construction of a large-scale quantum computer may be some years away, there are already commercial implementations of secure communication using quantum cryptography. The application of formal methods to classical communication and cryptographic systems has been very successful, and is now widely used in industry by organisations such as Intel, Microsoft and NASA. There is reason to believe that similar benefits can be expected for the verification of quantum systems. In this thesis, we focus on the use of process calculus, specifically Communicating Quantum Processes (CQP), for the analysis of quantum protocols. Congruence relations are an important aspect of process calculus, since they provide the foundation for equational reasoning. Previous work on congruence relations for quantum processes excluded the classical information arising from measurements, and was therefore unable to analyse many of the interesting known quantum communication protocols. Developing a congruence relation for general quantum processes is difficult because of the interaction between measurement, entanglement and parallel composition. We define a labelled transition relation for CQP in order to describe external interactions. Based on this semantics, we define a notion of observational equivalence for CQP processes, namely probabilistic branching bisimilarity. We find that this relation is not preserved by parallel composition, however we are able to gain a deeper understanding of the link between probabilistic branching and measurement. Based on this newfound understanding, we present a novel semantics for quantum processes, combining mixed quantum states with probabilistic branching. With respect to this new semantic model, we define full probabilistic branching bisimilarity and prove that it is a congruence. We use this congruence relation to discuss an axiomatic approach to the verification of quantum processes. The quantum teleportation protocol is used as a primary example throughout, and we prove that it is congruent to a quantum channel. We define a translation from CQP to the Quantum Model Checker (QMC) in order to provide automated verification techniques using CQP specifications. We prove that this translation preserves the semantics of CQP processes, thereby enabling a multifaceted approach to formal verification by enhancing the manual techniques of process calculus with the benefits of model checking.
28
Fang, Lei. "Exploring Constraint Satisfiability Techniques in Formal Verification." Diss., Virginia Tech, 2008. http://hdl.handle.net/10919/27573.
Full textAbstract:
Due to the widespread demands for efficient Propositional Satisfiability (SAT) solvers and its derivatives in Electronic Design Automation applications, methods to boost the performance of the SAT solver are highly desired. This dissertation aims to enhance the performance of SAT and related SAT solving problems. A hybrid solution to boost SAT solver performance is proposed as an initial attack in this dissertation, via an integration of local and DPLL-based search approaches.
Next, a different hybrid strategy is attempted that takes advantage of the conflicts in the SAT search, which plays a critical role in modern SAT solvers. Usually a learned conflict-induced clause is added back to the clause database. Although conflict-induced clauses help to block a portion of the search space, they can also become a burden due to the added cost in memory consumption and Boolean Constraint Propagation (BCP). We thus propose a novel double-layer conflict-driven learning to store only those "primary" conflict clauses back into the clause database while keeping the other clauses as pseudo Boolean constraints. With this approach our experiments demonstrate that the approach can improve both in performance and memory consumption. This work opens the door on how to assess the usefulness of conflict induced clauses.
Besides the aforementioned works about enhancing SAT solver performance and reducing memory cost, this dissertation also proposed a contributing work on the extended SAT problem solving. The current SAT solvers can provide an assignment for a satisfiable propositional formula. However, the capability for a SAT solver to return an "optimal" solution for a given objective function is severely lacking. MIN-ONE SAT is an optimization problem which requires the satisfying assignment with the minimal number of Ones, and it can be easily extended to minimize an arbitrary linear objective function. While some research has been conducted on MIN-ONE SAT, the existing algorithms do not scale very well on large formulas. This dissertation presents a novel approximation algorithm (RelaxSAT) for MIN-ONE SAT. RelaxSAT generates a set of constraints from the objective function to guide the search. The constraints are gradually relaxed to eliminate the conflicts with the original Boolean SAT formula until a solution is found. The experiments demonstrate that RelaxSAT is able to handle very large instances which cannot be solved by existing MIN-ONE algorithms; furthermore, RelaxSAT is able to obtain a very tight bound on the solution with one to two orders of magnitude speedup.
Based on the proposed powerful MIN-ONE SAT algorithm, we built a MAX-SAT solver which achieved more than one order of magnitude speed up compared with the-state-of-art MAX-SAT solver. We also discuss a promising application of this MAX-SAT solver in formal verification.Ph. D.
29
Sawada, Jun. "Formal verification of an advanced pipelined machine /." Digital version accessible at:, 1999. http://wwwlib.umi.com/cr/utexas/main.
Full text
30
Kühne, Ulrich. "Advanced automation in formal verification of processors." Aachen Shaker, 2009. http://d-nb.info/998313092/04.
Full text
31
Miyazawa, Alvaro Heiji. "Formal verification of implementations of stateflow charts." Thesis, University of York, 2012. http://etheses.whiterose.ac.uk/2353/.
Full textAbstract:
Simulink diagrams are widely used in industry for specifying control systems, and a particular type of block used in them is a Stateflow chart. Often, the systems specified are safety-critical ones. Therefore, the issue of correctness of implementations of these systems is relevant. We are interested in the verification of implementations of Stateflow charts. In this thesis, we propose a formal model of Stateflow charts in the Circus notation. The proposed model makes a distinction between the general semantics of Stateflow charts and the specific aspects of each chart, and maintains the operational style used in the official informal description of the semantics of Stateflow. In this way, we support the comparison of our model to the informal description as an extra form of validation. Moreover, this separation allows us to obtain a translation from a Stateflow chart to a Circus model based mostly on the syntactic structure of the chart. We formalise in Z a translation strategy that supports the generation of the chart specific model which is composed with the model of the semantics of Stateflow charts to formalise the execution of the chart. The translation strategy is implemented in a tool that supports the automatic generation of the complete model of a chart. The style in which the translation strategy is specified supports a very direct implementation, thus, minimising this potential source of error. We identify an architecture of parallel implementations based on the sequential implementations automatically generated by a code generator, and propose a refinement strategy that applies the Circus refinement calculus to verify the correctness of the implementation with respect to the proposed formal model of Stateflow charts. The identification of the architecture allows us to specify the refinement strategy in a degree of detail that renders it suitable for formalisation in a tactical language, thus, potentially achieving a high degree of automation. Moreover, this strategy is a starting point for new strategies targeting different architectural patterns.
32
Powell, Daniel. "Formal Methods For Verification Based Software Inspection." Thesis, Griffith University, 2003. http://hdl.handle.net/10072/366466.
Full textAbstract:
Useful processes, that are independently repeatable, are utilised in all branches of science and traditional engineering disciplines but seldom in software engineering. This is particularly so with processes used for detection and correction of defects in software systems. Code inspection, as introduced by Michael Fagan at IBM in the mid 1970's is widely recognised as an effective technique for finding defects in software. Despite its reputation, code inspection, as it is currently practiced, is not a strictly repeatable process. This is due to the problems faced by inspectors when they attempt to paraphrase the complicated semantics of a unit of computer code. Verification based software inspection, as advocated by the cleanroom software engineering community, requires that arguments of correctness be formulated with the code and its specification. These arguments rely on the reader being able to extract the semantics from the code. This thesis addresses the requirement for an independently repeatable, scalable and substantially automated method for yielding semantics from computer code in a complete, unambiguous and consistent manner in order to facilitate, and make repeatable, verification based code inspection. Current literature regarding the use of code inspection for verification of software is surveyed. Empirical studies are referenced, comparing inspection to software testing and program proof. Current uses of formal methods in software engineering will be discussed, with particular reference to formal method applications in verification. Forming the basis of the presented method is a systematic, and hence repeatable, approach to the derivation of program semantics. The theories and techniques proposed for deriving semantics from program code extend current algorithmic and heuristic techniques for deriving invariants. Additionally, the techniques introduced yield weaker forms of invariant information which are also useful for verification, defect detection and correction. Methods for using these weaker invariant forms, and tools to support these methods, are introduced. Algorithmic and heuristic techniques for investigating loop progress and termination are also introduced. Some of these techniques have been automated in supporting tools, and hence, the resulting defects can be repeatably identified. Throughout this thesis a strong emphasis is placed on describing implementable algorithms to realise the derivation techniques discussed. A number of these algorithms are implemented in a tool to support the application of the verification methods presented. The techniques and tools presented in this thesis are well suited, but not limited to, supporting rigorous methods of defect detection as well as formal and semi-formal reasoning of correctness. The automation of these techniques in tools to support practical, formal code reading and correctness argument will assist in addressing the needs of trusted component technologies and the general requirement for quality in software.Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Computing and Information Technology
Full Text
33
Livadas, Carolos. "Formal verification of safety-critical hybrid systems." Thesis, Massachusetts Institute of Technology, 1997. http://hdl.handle.net/1721.1/42817.
Full textAbstract:
Thesis (M.Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1997.Includes bibliographical references (p. 181-185).
This thesis investigates how the formal modeling and verification techniques of computer science can be used for the analysis of hybrid systems [7,14,22,37] - systems involving both discrete and continuous behavior. The motivation behind such research lies in the inherent similarity of the hierarchical and decentralized control strategies of hybrid systems and the communication and operation protocols used for distributed systems in computer science. As a case study, the thesis focuses on the development of techniques that use hybrid I/O automata [29,30] to model and analyze automated vehicle transportation systems and, in particular, their various protection subsystems - control systems that are used to ensure that the physical plant at hand does not violate its various safety requirements. The thesis is split into two major parts. In the first part, we develop an abstract model of a physical plant and its various protection subsystems - also referred to as protectors. The specialization of this abstract model results in the specification of a particular automated transportation system. Moreover, the proof of correctness of the abstract model leads to simple correctness proofs of the protector implementations for particular specializations of the abstract model. In this framework, the composition of independent protectors is straightforward - their composition guarantees the conjunction of the safety properties guaranteed by the individual protectors. In fact, it is shown that under certain conditions composition holds for dependent protectors also. In the second part, we specialize the aforementioned abstract model to simplified versions of the personal rapid transit system (PRT 200TM) under development at Raytheon Corporation. We examine overspeed and collision protection for a set of vehicles traveling on straight tracks, on binary merges, and on a directed graph of tracks involving binary merges and diverges. In each case, the protectors sample the state of the physical plant and take protective actions to guarantee that the physical plant does not reach hazardous states. The proofs of correctness of such protectors involve specializing the abstract protector to the physical plant at hand and proving that the suggested protector implementations are correct. This is done by defining simulations among the states of the protector implementations and their abstract counterparts.
by Carolos Livadas.
M.Eng.
34
Griggio, Alberto. "An Effective SMT Engine for Formal Verification." Doctoral thesis, Università degli studi di Trento, 2009. https://hdl.handle.net/11572/368265.
Full textAbstract:
Formal methods are becoming increasingly important for debugging and verifying
hardware and software systems, whose current complexity makes the traditional
approaches based on testing increasingly-less adequate. One of the most
promising research directions in formal verification is based on the
exploitation of Satisfiability Modulo Theories (SMT) solvers. In this thesis,
we present MathSAT, a modern, efficient SMT solver that provides several
important functionalities, and can be used as a workhorse engine in formal
verification. We develop novel algorithms for two functionalities which are
very important in verification -- the extraction of unsatisfiable cores and
the generation of Craig interpolants in SMT -- that significantly advance the
state of the art, taking full advantage of modern SMT techniques. Moreover,
in order to demonstrate the usefulness and potential of SMT in verification,
we develop a novel technique for software model checking, that fully exploits
the power and functionalities of the SMT engine, showing that this leads to
significant improvements in performance.
35
Griggio, Alberto. "An Effective SMT Engine for Formal Verification." Doctoral thesis, University of Trento, 2009. http://eprints-phd.biblio.unitn.it/145/1/thesis.pdf.
Full textAbstract:
Formal methods are becoming increasingly important for debugging and verifying
hardware and software systems, whose current complexity makes the traditional
approaches based on testing increasingly-less adequate. One of the most
promising research directions in formal verification is based on the
exploitation of Satisfiability Modulo Theories (SMT) solvers. In this thesis,
we present MathSAT, a modern, efficient SMT solver that provides several
important functionalities, and can be used as a workhorse engine in formal
verification. We develop novel algorithms for two functionalities which are
very important in verification -- the extraction of unsatisfiable cores and
the generation of Craig interpolants in SMT -- that significantly advance the
state of the art, taking full advantage of modern SMT techniques. Moreover,
in order to demonstrate the usefulness and potential of SMT in verification,
we develop a novel technique for software model checking, that fully exploits
the power and functionalities of the SMT engine, showing that this leads to
significant improvements in performance.
36
Griggio, Alberto. "An Effective SMT Engine for Formal Verification." Doctoral thesis, Università degli studi di Trento, 2009. https://hdl.handle.net/11572/368765.
Full textAbstract:
Formal methods are becoming increasingly important for debugging and verifying hardware and software systems, whose current complexity makes the traditional
approaches based on testing increasingly-less adequate. One of the most promising research directions in formal verification is based on the exploitation of Satisfiability Modulo Theories (SMT) solvers. In this thesis,
we present MathSAT, a modern, efficient SMT solver that provides several important functionalities, and can be used as a workhorse engine in formal verification. We develop novel algorithms for two functionalities which are
very important in verification -- the extraction of unsatisfiable cores and the generation of Craig interpolants in SMT -- that significantly advance the
state of the art, taking full advantage of modern SMT techniques. Moreover, in order to demonstrate the usefulness and potential of SMT in verification,
we develop a novel technique for software model checking, that fully exploits the power and functionalities of the SMT engine, showing that this leads to significant improvements in performance.
37
Griggio, Alberto. "An Effective SMT Engine for Formal Verification." Doctoral thesis, University of Trento, 2009. http://eprints-phd.biblio.unitn.it/166/2/thesis.pdf.
Full textAbstract:
Formal methods are becoming increasingly important for debugging and verifying hardware and software systems, whose current complexity makes the traditional
approaches based on testing increasingly-less adequate. One of the most promising research directions in formal verification is based on the exploitation of Satisfiability Modulo Theories (SMT) solvers. In this thesis,
we present MathSAT, a modern, efficient SMT solver that provides several important functionalities, and can be used as a workhorse engine in formal verification. We develop novel algorithms for two functionalities which are
very important in verification -- the extraction of unsatisfiable cores and the generation of Craig interpolants in SMT -- that significantly advance the
state of the art, taking full advantage of modern SMT techniques. Moreover, in order to demonstrate the usefulness and potential of SMT in verification,
we develop a novel technique for software model checking, that fully exploits the power and functionalities of the SMT engine, showing that this leads to significant improvements in performance.
38
Ferrara, Andrea. "Formal verification: further complexity issues and applications." Doctoral thesis, La Sapienza, 2006. http://hdl.handle.net/11573/917050.
Full text
39
Kattenbelt, Mark Alex. "Automated quantitative software verification." Thesis, University of Oxford, 2010. http://ora.ox.ac.uk/objects/uuid:62430df4-7fdf-4c4f-b3cd-97ba8912c9f5.
Full textAbstract:
Many software systems exhibit probabilistic behaviour, either added explicitly, to improve performance or to break symmetry, or implicitly, through interaction with unreliable networks or faulty hardware. When employed in safety-critical applications, it is important to rigorously analyse the behaviour of these systems. This can be done with a formal verification technique called model checking, which establishes properties of systems by algorithmically considering all execution scenarios. In the presence of probabilistic behaviour, we consider quantitative properties such as "the worst-case probability that the airbag fails to deploy within 10ms", instead of qualitative properties such as "the airbag eventually deploys". Although many model checking techniques exist to verify qualitative properties of software, quantitative model checking techniques typically focus on manually derived models of systems and cannot directly verify software. In this thesis, we present two quantitative model checking techniques for probabilistic software. The first is a quantitative adaptation of a successful model checking technique called counter-example guided abstraction refinement which uses stochastic two-player games as abstractions of probabilistic software. We show how to achieve abstraction and refinement in a probabilistic setting and investigate theoretical extensions of stochastic two-player game abstractions. Our second technique instruments probabilistic software in such a way that existing, non-probabilistic software verification methods can be used to compute bounds on quantitative properties of the original, uninstrumented software. Our techniques are the first to target real, compilable software in a probabilistic setting. We present an experimental evaluation of both approaches on a large range of case studies and evaluate several extensions and heuristics. We demonstrate that, with our methods, we can successfully compute quantitative properties of real network clients comprising approximately 1,000 lines of complex ANSI-C code — the verification of such software is far beyond the capabilities of existing quantitative model checking techniques.
40
Eleftherakis, George. "Formal verification of X-machine models : towards formal development of computer-based systems." Thesis, University of Sheffield, 2003. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.400012.
Full text
41
Hossain, Mousam. "Formal Verification Methodology for Asynchronous Sleep Convention Logic Circuits Based on Equivalence Verification." Thesis, North Dakota State University, 2019. https://hdl.handle.net/10365/31574.
Full textAbstract:
Sleep Convention Logic (SCL) is an emerging ultra-low power Quasi-Delay Insensitive (QDI) asynchronous design paradigm with enormous potential for industrial applications. Design validation is a critical concern before commercialization. Unlike other QDI paradigms, such as NULL Convention Logic (NCL) and Pre-Charge Half Buffers (PCHB), there exists no formal verification methods for SCL. In this thesis, a unified formal verification scheme for combinational as well as sequential SCL circuits is proposed based on equivalence checking, which verifies both safety and liveness. The method is demonstrated using several multipliers, MACs, and ISCAS benchmarks.
42
Mohnke, Janett. "A signature-based approach to formal logic verification." [S.l. : s.n.], 1999. http://deposit.ddb.de/cgi-bin/dokserv?idn=960520406.
Full text
43
Traub, Johannes [Verfasser]. "Formal Verification of Concurrent Embedded Software / Johannes Traub." Kiel : Universitätsbibliothek Kiel, 2016. http://d-nb.info/1105472175/34.
Full text
44
Argote, Garcia Gonzalo. "Formal verification and testing of software architectural models." FIU Digital Commons, 2009. http://digitalcommons.fiu.edu/etd/1308.
Full textAbstract:
Ensuring the correctness of software has been the major motivation in software research, constituting a Grand Challenge. Due to its impact in the final implementation, one critical aspect of software is its architectural design. By guaranteeing a correct architectural design, major and costly flaws can be caught early on in the development cycle. Software architecture design has received a lot of attention in the past years, with several methods, techniques and tools developed. However, there is still more to be done, such as providing adequate formal analysis of software architectures. On these regards, a framework to ensure system dependability from design to implementation has been developed at FIU (Florida International University). This framework is based on SAM (Software Architecture Model), an ADL (Architecture Description Language), that allows hierarchical compositions of components and connectors, defines an architectural modeling language for the behavior of components and connectors, and provides a specification language for the behavioral properties. The behavioral model of a SAM model is expressed in the form of Petri nets and the properties in first order linear temporal logic.
This dissertation presents a formal verification and testing approach to guarantee the correctness of Software Architectures. The Software Architectures studied are expressed in SAM. For the formal verification approach, the technique applied was model checking and the model checker of choice was Spin. As part of the approach, a SAM model is formally translated to a model in the input language of Spin and verified for its correctness with respect to temporal properties. In terms of testing, a testing approach for SAM architectures was defined which includes the evaluation of test cases based on Petri net testing theory to be used in the testing process at the design level. Additionally, the information at the design level is used to derive test cases for the implementation level. Finally, a modeling and analysis tool (SAM tool) was implemented to help support the design and analysis of SAM models. The results show the applicability of the approach to testing and verification of SAM models with the aid of the SAM tool.
45
Yao, Håkansson Jonathan, and Niklas Rosencrantz. "Formal Verification of Hardware Peripheral with Security Property." Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-209807.
Full textAbstract:
One problem with computers is that the operating system automatically trusts any externallyconnected peripheral. This can result in abuse when a peripheral technically can violate the security model because the peripheral is trusted. Because of that the security is an important issue to look at.The aim of our project is to see in which cases hardware peripherals can be trusted. We built amodel of the universal asynchronous transmitter/receiver (UART), a model of the main memory(RAM) and a model of a DMA controller. We analysed interaction between hardware peripherals,user processes and the main memory.One of our results is that connections with hardware peripherals are secure if the hardware is properly configured. A threat scenario could be an eavesdropper or man-in-the-middle trying to steal data or change a cryptographic key.We consider the use-cases of DMA and protecting a cryptographic key. We prove the well-behavior of the algorithm. Some error-traces resulted from incorrect modelling that was resolved by adjusting the models. Benchmarks were done for different memory sizes.The result is that a peripheral can be trusted provided a configuration is done. Our models consist of finite state machines and their corresponding SMV modules. The models represent computer hardware with DMA. We verified the SMV models using the model checkers NuSMV and nuXmv.Målet med vårt projekt är att verifiera olika specifikationer av externa enheter som ansluts till datorn. Vi utför formell verifikation av sådan datorutrustning och virtuellt minne. Verifikation med temporal logik, LTL, utförs. Specifikt verifierar vi 4 olika use-case och 9 formler för seriell datakommunikation, DMA och virtuellt minne. Slutsatsen är att anslutning av extern hårdvara är säker om den är ordentligt konfigurerad.Vi gör jämförelser mellan olika minnesstorlekar och mätte tidsåtgången för att verifiera olika system. Vi ser att tidsåtgången för verifikation är långsammare än linjärt beroende och att relativt små system tar relativt lång tid att verifiera.
46
Mejri, Mohamed. "A formal automatic verification of authentication cryptographic protocols." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/mq26244.pdf.
Full text
47
Negulescu, Radu. "Process spaces and formal verification of asynchronous circuits." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp03/NQ32848.pdf.
Full text
48
Kong, Xiaohua 1974. "Formal verification of peephole optimization in asynchronous circuits." Thesis, McGill University, 2001. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=32962.
Full textAbstract:
This thesis proposes and applies novel techniques for formal verification of peephole optimizations in asynchronous circuits. Our task is to verify whether locally optimized modules can replace parts of an existing circuit under certain assumptions regarding the operation of the optimized modules in context. Two main difficulties in verifying peephole optimizations are state explosion in the implementation models and increased complexity of the interfaces of optimized modules. A novel technique is proposed for constructing in a modular manner specifications and functional models of pulse-mode circuits. A verification rule related to assume-guarantee and hierarchical verification is presented, using relative timing constraints as optimization assumptions. We present two case studies to illustrate the proposed techniques: verification of speed-optimizations in an asynchronous arbiter, and verification of one step of communication refinement in a globally asynchronous, locally synchronous (GALS) architecture.
49
Sarraf, Danny. "Optimizing assertions in semi-formal assertion- based verification." Thesis, McGill University, 2013. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=116927.
Full textAbstract:
Assertion-based verification (ABV) is a powerful verification approach that has been proven to help digital IC architects, designers, and verification engineers improve design quality and reduce time to market.Assertions are a very powerful, concise and precise mechanism to specify properties of logic design. They run in all verification environments: simulation, emulation/acceleration and formal. In addition, they can be used as checkers or alternatively as assumptions.Some of the major challenges of ABV are that assertions are time-consuming to debug, there's no good way to measure the quality of hand-generated assertions and it's unclear how many assertions one needs to write.This thesis is an attempt at providing new ideas on how to resolve such issues. Different methods of adding assertions to an existing set have been explored and the task of writing enough assertions will be broken down into smaller and more manageable chunks. In order to do so, various types of assertions have first been identified in terms of their usefulness from the designers' and verification engineers' points of view.Lastly, the implementation of logic synthesis techniques to optimize assertions has been explored. Many significant improvements in terms of minimizing the total number of assertions as well as producing more efficient assertions have been observed.La vérification basée sur l'assertion (Assertion-based Verification - ABV) est une approche de vérification puissante ayant été prouvée à aider les architectes numériques de circuits intégrés, les concepteurs et les ingénieurs de vérification à améliorer la qualité de conception et de réduire le temps de mise sur le marché. Les assertions sont un outil très puissant et précis pour définir les propriétés de la conception logique. Elles peuvent être employées dans tous les environnements de vérification: simulation, émulation ou formelle. Aussi important, elles peuvent être utilisées comme corrections ou encore comme hypothèses.Les inconvénients majeurs d'ABV sont que les assertions nécessitent beaucoup de temps a déboguer, qu'il n'y a pas de bonne facon de mesurer la qualité des assertions produites manuellement et qu'on ne sait pas comment déterminer combien d'assertions on a besoin d'écrire.Cette thèse tente d'apporter de nouvelles idées afin de résoudre ces questions. Différentes méthodes d'ajouter des assertions ont été explorées. La tache de la rédaction d'assez d'assertions a été décomposée en plus petits et plus gérables morceaux.Pour réaliser ceci, différents types d'assertions ont été d'abord identifiées en termes de leur utilité des points de vue des concepteurs et ingénieurs de vérification.Enfin, la mise en œuvre des techniques de synthèse logique pour optimiser les assertions ont été explorées. Des améliorations notables en termes de minimisation du nombre total d'assertions ainsi que la production d'assertions plus efficaces ont été observées.
50
Meedeniya, Dulani Apeksha. "Correct model-to-model transformation for formal verification." Thesis, University of St Andrews, 2013. http://hdl.handle.net/10023/3691.
Full textAbstract:
Modern software systems have increasingly higher expectations on their reliability, in particular if the systems are critical and real-time. The development of these complex software systems requires strong modelling and analysis methods including quantitative modelling and formal verification. Unified Modelling Language (UML) is a widely used and intuitive graphical modelling language to design complex systems, while formal models provide a theoretical support to verify system design models. However, UML models are not sufficient to guarantee correct system designs and formal models, on the other hand, are often restrictive and complex to use. It is believed that a combined approach comprising the advantages of both models can offer better designs for modern complex software development needs. This thesis focuses on the design and development of a rigorous framework based on Model Driven Development (MDD) that facilitates transformations of non-formal models into formal models for design verification. This thesis defines and describes the transformation from UML2 sequence diagrams to coloured Petri nets and proves syntactic and semantic correctness of the transformation. Additionally, we explore ways of adding information (time, probability, and hierarchy) to a design and how it can be added onto extensions of a target model. Correctness results are extended in this context. The approach in this thesis is novel and significant both in how to establish semantic and syntactic correctness of transformations, and how to explore semantic variability in the target model for formal analysis. Hence, the motivation of this thesis establishes: the UML behavioural models can be validated by correct transformation of them into formal models that can be formally analysed and verified.