Dissertations / Theses on the topic 'Model and Program 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 'Model and Program 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.
Beyene, Tewodros Awgichew. "Constraint-based verification of imperative programs." Master's thesis, Faculdade de Ciências e Tecnologia, 2011. http://hdl.handle.net/10362/7965.
The continuous reduction in the cost of computing ever since the first days of computers has resulted in the ubiquity of computing systems today; there is no any sphere of life in the daily routine of human beings that is not directly or indirectly influenced by computer systems anymore. But this high reliance on computers has not come without a risk to the society or a challenge to computer scientists. As many computer systems of today are safety critical, it is crucial for computer scientists to make sure that computer systems, both the hardware and software components, behave correctly under all circumstances. In this study, we are interested in techniques of program verification that are aimed at ensuring the correctness of the software component. In this work, constraint programming techniques are used to device a program verification framework where constraint solvers play the role of typical verification tools. The programs considered are written in some subset of Java, and their specifications are written in some subset of Java Modeling Language(JML). In our framework, the program verification process has two principal steps: constraint generation and constraint solving. A program together with its specification is first parsed into a system of constraints. And then, the system of constraints is processed using constraint solvers so that the correctness of the original program is proved to hold, or not, based on the outcome of the constraint solving. The performance of our framework is compared with other well-known program verification tools using standard benchmarks, and our framework has performed quite well for most of the cases.
Kaiser, Alexander. "Monotonicity in shared-memory program verification." Thesis, University of Oxford, 2013. http://ora.ox.ac.uk/objects/uuid:1d16b4b5-524a-40db-b7bf-062374f8679c.
Bezuidenhout, Johannes Abraham. "Automated program generation : bridging the gap between model and implementation." Thesis, Stellenbosch : Stellenbosch University, 2012. http://hdl.handle.net/10019.1/19584.
ENGLISH ABSTRACT: The general goal of this thesis is the investigation of a technique that allows model checking to be directly integrated into the software development process, preserving the benefits of model checking while addressing some of its limitations. A technique was developed that allows a complete executable implementation to be generated from an enhanced model specification. This included the development of a program, the Generator, that completely automates the generation process. In addition, it is illustrated how structuring the specification as a transitions system formally separates the control flow from the details of manipulating data. This simplifies the verification process which is focused on checking control flow in detail. By combining this structuring approach with automated implementation generation we ensure that the verified system behaviour is preserved in the actual implementation. An additional benefit is that data manipulation, which is generally not suited to model checking, is restricted to separate, independent code fragments that can be verified using verification techniques for sequential programs. These data manipulation code segments can also be optimised for the implementation without affecting the verification of the control structure. This technique was used to develop a reactive system, an FTP server, and this experiment illustrated that efficient code can be automatically generated while preserving the benefits of model checking.
AFRIKAANSE OPSOMMING: Hierdie tesis ondersoek ’n tegniek wat modeltoetsing laat deel uitmaak van die sagtewareontwikkelingsproses, en sodoende betroubaarheid verbeter terwyl sekere tekorkominge van die tradisionele modeltoetsing proses aangespreek word. Die tegniek wat ontwikkel is maak dit moontlik om ’n volledige uitvoerbare implementasie vanaf ’n gespesialiseerde model spesifikasie te genereer. Om die implementasie-generasie stap ten volle te outomatiseer is ’n program, die Generator, ontwikkel. Daarby word dit ook gewys hoe die kontrolevloei op ’n formele manier geskei kan word van data-manipulasie deur gebruik te maak van ’n staatoorgangsstelsel struktureringsbenadering. Dit vereenvoudig die verifikasie proses, wat fokus op kontrolevloei. Deur di´e struktureringsbenadering te kombineer met outomatiese implementasie-generasie, word verseker dat die geverifieerde stelsel se gedrag behou word in die finale implementasie. ’n Bykomende voordeel is dat data-manipulasie, wat gewoonlik nie geskik is vir modeltoetsing nie, beperk word tot aparte, onafhanklike kode segmente wat geverifieer kan word deur gebruik te maak van verifikasie tegnieke vir sekwensi¨eele programme. Hierdie data-manipulasie kode segmente kan ook geoptimeer word vir die implementasie sonder om die verifikasie van die kontrole struktuur te be¨ınvloed. Hierdie tegniek word gebruik om ’n reaktiewe stelsel, ’n FTP bediener, te ontwikkel, en di´e eksperiment wys dat doeltreffende kode outomaties gegenereer kan word terwyl die voordele van modeltoetsing behou word.
Wardana, Awang Noor Indra. "Development of automatic program verification for continuous function chart based on model checking /." Kassel : Kassel Univ. Press, 2009. http://d-nb.info/998980234/04.
de, Carvalho Gomes Pedro. "Automatic Extraction of Program Models for Formal Software Verification." Doctoral thesis, KTH, Teoretisk datalogi, TCS, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-176286.
Den här avhandlingen studerar automatisk konstruktion av abstrakta modeller för formell verifikation av program skrivna i verkliga programmeringsspråk. Avhandlingen består av tre delar som involverar olika typer av program, programmeringsspråk, verifikationsscenarier, programmodeller och egenskaper.Del ett presenterar en algoritm för generation av flödesgrafer från sekventiella program i Java bytekod. Graferna är skräddarsydda för en kompositionell teknik för verifikationen av temporala kontrollflödens säkerhetsegenskaper. Vi visar att de extraherade modellerna sunt överapproximerar programbeteenden med avseende på sekvenser av metodanrop och -undantag. Således gäller egenskaperna som kan fastställas genom kompositionstekniken över kontrollflöden även för programmen. Vi implementerar dessutom algoritmen i form av verktyget ConFlEx och utvärderar verktyget på ett antal testfall.Del två presenterar en teknik för att generera modeller av ofullständiga program. Det vill säga, program där implementationen av åtminstone en komponent inte är tillgänglig. Vi definierar ett ramverk för att representera ofullständiga Java bytekodsprogram och utökar algoritmen från del ett till att hantera ofullständig kod. Därefter presenterar vi raffineringsregler - villkor för att instansiera den saknade koden - och bevisar att reglerna bevarar relevanta egenskaper av kontrollflödesgrafer. Vi har dessutom utökat ConFlEx till att stödja de nya definitionerna och har omvärderat verktyget på testfall av ofullständiga program.Del tre angriper verifikation av multitrådade program. Vi presenterar en teknik för att bevisa följande egenskap för synkronisering med vilkorsvariabler: "Om varje trådsynkronisering under samma villkor så småningom stiger in i sitt synkroniseringsblock så kommer varje tråd också till slut lämna synkroniseringen". För att stödja verifikationen så introducerar vi först SyncTask - ett enkelt mellanliggande språk för att specificera synkronisering av parallella beräkningar. Därefter presenterar vi ett annoteringsspråk för Java som tillåter automatisk extrahering av SyncTask-program och visar att egenskapen gäller om och endast om motsvarande SyncTask-program terminerar. Vi reducerar termineringsproblemet till ett nåbarhetsproblem på färgade Petrinät samt definierar en algoritm som skapar Petrinät från SyncTask-program där programmet terminerar om och endast om nätet alltid når en särskild mängd av döda konfigurationer. Extraktionen av SyncTask-program och deras motsvarande Petrinät är implementerade i form av verktyget STaVe. Slutligen utvärderar vi verktyget genom att mata annoterade.
QC 20151101
He, Nannan. "Exploring Abstraction Techniques for Scalable Bit-Precise Verification of Embedded Software." Diss., Virginia Tech, 2009. http://hdl.handle.net/10919/27683.
Ph. D.
Mahtab, Tazeen 1981. "Automated verification of model-based programs under uncertainty." Thesis, Massachusetts Institute of Technology, 2004. http://hdl.handle.net/1721.1/28453.
Includes bibliographical references (p. 89-91).
Highly robust embedded systems have been enabled through software executives that have the ability to reason about their environment. Those that employ the model-based autonomy paradigm automatically diagnose and plan future actions, based on models of themselves and their environment. This includes autonomous systems that must operate in harsh and dynamic environments, like, deep space. Such systems must be robust to a large space of possible failure scenarios. This large state space poses difficulties for traditional scenario-based testing, leading to a need for new approaches to verification and validation. We propose a novel verification approach that generates an analysis of the most likely failure scenarios for a model-based program. By finding only the lost likely failures, we increase the relevance and reduce the quantity of information the developer must examine. First, we provide the ability to verify a stochastic system that encodes both off-nominal and nominal scenarios. We incorporate uncertainty into the verification process by acknowledging that all such programs may fail, but in different ways, with different likelihoods. The verification process is one of finding the most likely executions that fail the specification. Second, we provide a capability for verifying executable specifications that are fault-aware. We generalize offline plant model verification to the verification of model-based programs, which consist of both a plant model that captures the physical plant's nominal and off-nominal states and a control program that specifies its desired behavior. Third, we verify these specifications through execution of the RMPL executive itself. We therefore circumvent the difficulty of formalizing the behavior of complex
(cont.) software executives. We present the RMPL Verifier, a tool for verification of model-based programs written in the Reactive Model-based Programming Language (RMPL) for the Titan execution kernel. Using greedy forward-directed search, this tool finds as counterexamples to the program's goal specification the most likely executions that do not achieve the goal within a given time bound.
by Tazeen Mahtab.
M.Eng.and S.B.
Newcomb, Tom C. "Model checking data-independent systems with arrays." Thesis, University of Oxford, 2003. http://ora.ox.ac.uk/objects/uuid:7fc75da9-e653-4578-b061-8a1cc30ba609.
Rezine, Othmane. "Verification of networks of communicating processes : Reachability problems and decidability issues." Doctoral thesis, Uppsala universitet, Avdelningen för datorteknik, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-334788.
de, Carvalho Gomes Pedro. "Sound Modular Extraction of Control Flow Graphs from Java Bytecode." Licentiate thesis, KTH, Teoretisk datalogi, TCS, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-105275.
QC 20121122
de, Carvalho Gomes Pedro, and Attilio Picoco. "Sound Extraction of Control-Flow Graphs from open Java Bytecode Systems." KTH, Teoretisk datalogi, TCS, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-104076.
QC 20121029
Verification of Control-Flow Properties of Programs with Procedures(CVPP)
Fourie, Jean Francois. "Reducing communication in distributed model checking." Thesis, Stellenbosch : University of Stellenbosch, 2009. http://hdl.handle.net/10019.1/2176.
ENGLISH ABSTRACT: Model checkers are programs that automatically verify, without human assistance, that certain user-specified properties hold in concurrent software systems. Since these programs often have expensive time and memory requirements, an active area of research is the development of distributed model checkers that run on clusters. Of particular interest is how the communication between the machines can be reduced to speed up their running time. In this thesis the design decisions involved in an on-the-fly distributed model checker are identified and discussed. Furthermore, the implementation of such a program is described. The central idea behind the algorithm is the generation and distribution of data throughout the nodes of the cluster. We introduce several techniques to reduce the communication among the nodes, and study their effectiveness by means of a set of models.
AFRIKAANSE OPSOMMING: Modeltoetsers is programme wat outomaties bevestig, sonder enige hulp van die gebruiker, dat gelopende sagteware aan sekere gespesifiseerde eienskappe voldoen. Die feit dat hierdie programme dikwels lang looptye en groot geheues benodig, het daartoe aanleiding gegee dat modeltoetsers wat verspreid oor ’n groep rekenaars hardloop, aktief nagevors word. Dit is veral belangrik om vas te stel hoe die kommunikasie tussen rekenaars verminder kan word om sodoende die looptyd te verkort. Hierdie tesis identifiseer en bespreek die ontwerpsbesluite betrokke in die ontwikkeling van ’n verspreide modeltoetser. Verder word die implementasie van so ’n program beskryf. Die kernidee is die generasie en verspreiding van data na al die rekenaars in die groep wat aan die probleem werk. Ons stel verskeie tegnieke voor om die kommunikasie tussen die rekenaar te verminder en bestudeer die effektiwiteit van hierdie tegnieke aan die hand van ’n lys modelle.
Wardana, Awang Noor Indra [Verfasser]. "Development of Automatic Program Verification for Continuous Function Chart based on Model Checking / Awang Noor Indra Wardana." Kassel : Kassel University Press, 2009. http://d-nb.info/1011715880/34.
Nakade, Radha Vi. "Verification of Task Parallel Programs Using Predictive Analysis." BYU ScholarsArchive, 2016. https://scholarsarchive.byu.edu/etd/6176.
Berglund, Lasse. "Executive Summaries in Software Model Checking." Thesis, KTH, Teoretisk datalogi, TCS, 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-231433.
Model checking, eller modellkontroll, är en välkänd teknik inom programverifikation som används för att verifiera att en modell, ofta av ett program, uppfyller en given specifikation genom att undersöka alla nåbara tillstånd i modellen. Det är en välutvecklad teknik som lider av några brister, en av de viktigaste är det så kallade state space explosion-problemet. Modellerna kan bestå av så många olika tillstånd att \textit{model checking} inte går att använda. I den här rapporten undersöker vi om vi kan tillämpa så kallade procedur-sammanfattningar för att förbättra prestandan av model checking. Procedur-sammanfattningar är representationer av delar av program, till exempel metoder eller funktioner. Vi presenterar en design och implementation av dynamiskt genererade sammanfattningar i form av ett tillägg till Java PathFinder, en virtuell maskin som exekverar Java bytecode som kan utföra model checking genom att backa körningar för att till exempel utforska olika schemaläggningar. Våra procedur-sammanfattningar har i många fall en negativ effekt på körtid, men visar på lovande resultat i vissa fall, i synnerhet när så kallad stateless model checking används. Vi presenterar också resultat kopplat till fall när våra sammanfattningar är applicerbara som kan leda vägen för fortsatt arbete inom området.
Haziza, Frédéric. "Few is Just Enough! : Small Model Theorem for Parameterized Verification and Shape Analysis." Doctoral thesis, Uppsala universitet, Avdelningen för datorteknik, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-264171.
Prestero, Timothy (Timothy Jason) 1970. "Verification of a six-degree of freedom simulation model for the REMUS autonomous underwater vehicle." Thesis, Massachusetts Institute of Technology, 2001. http://hdl.handle.net/1721.1/65068.
Includes bibliographical references (p. 125-127).
mproving the performance of modular, low-cost autonomous underwater vehicles (AUVs) in such applications as long-range oceanographic survey, autonomous docking, and shallow-water mine countermeasures requires improving the vehicles' maneuvering precision and battery life. These goals can be achieved through the improvement of the vehicle control system. A vehicle dynamics model based on a combination of theory and empirical data would provide an efficient platform for vehicle control system development, and an alternative to the typical trial-and-error method of vehicle control system field tuning. As there exists no standard procedure for vehicle modeling in industry, the simulation of each vehicle system represents a new challenge. Developed by von Alt and associates at the Woods Hole Oceanographic Institute, the REMUS AUV is a small, low-cost platform serving in a range of oceanographic applications. This thesis describes the development and verification of a six degree of freedom, non-linear simulation model for the REMUS vehicle, the first such model for this platform. In this model, the external forces and moments resulting from hydrostatics, hydrodynamic lift and drag, added mass, and the control inputs of the vehicle propeller and fins are all defined in terms of vehicle coefficients. This thesis describes the derivation of these coefficients in detail. The equations determining the coefficients, as well as those describing the vehicle rigid-body dynamics, are left in non-linear form to better simulate the inherently non-linear behavior of the vehicle. Simulation of the vehicle motion is achieved through numeric integration of the equations of motion. The simulator output is then checked against vehicle dynamics data collected in experiments performed at sea. The simulator is shown to accurately model the motion of the vehicle.
by Timothy Prestero.
S.M.
Faitelson, David. "Program synthesis from domain specific object models." Thesis, University of Oxford, 2008. http://ora.ox.ac.uk/objects/uuid:0c5a992e-dad4-435c-a576-e3ed504bcdbd.
Cyriac, Aiswarya. "Verification of communicating recursive programs via split-width." Thesis, Cachan, Ecole normale supérieure, 2014. http://www.theses.fr/2014DENS0004/document.
This thesis investigates automata-theoretic techniques for the verification of physically distributed machines communicating via unbounded reliable channels. Each of these machines may run several recursive programs (multi-threading). A recursive program may also use several unbounded stack and queue data-structures for its local-computation needs. Such real-world systems are so powerful that all verification problems become undecidable. We introduce and study a new parameter called split-width for the under-approximate analysis of such systems. Split-width is the minimum number of splits required in the behaviour graphs to obtain disjoint parts which can be reasoned about independently. Thus it provides a divide-and-conquer approach for their analysis. With the parameter split-width, we obtain optimal decision procedures for various verification problems on these systems like reachability, inclusion, etc. and also for satisfiability and model checking against various logical formalisms such as monadic second-order logic, propositional dynamic logic and temporal logics. It is shown that behaviours of a system have bounded split-width if and only if they have bounded clique-width. Thus, by Courcelle's results on uniformly bounded-degree graphs, split-width is not only sufficient but also necessary to get decidability for MSO satisfiability checking. We then study the feasibility of distributed controllers for our generic distributed systems. We propose several controllers, some finite state and some deterministic, which ensure that the behaviours of the system have bounded split-width. Such a distributedly controlled system yields decidability for the various verification problems by inheriting the optimal decision procedures for split-width. These also extend or complement many known decidable subclasses of systems studied previously
Shaner, Steve M. "Modular verification of higher-order methods with mandatory calls specified by model programs." [Ames, Iowa : Iowa State University], 2008.
Bart, Anicet. "Constraint modelling and solving of some verification problems." Thesis, Ecole nationale supérieure Mines-Télécom Atlantique Bretagne Pays de la Loire, 2017. http://www.theses.fr/2017IMTA0031/document.
Constraint programming offers efficient languages andtools for solving combinatorial and computationally hard problems such as the ones proposed in program verification. In this thesis, we tackle two families of program verification problems using constraint programming.In both contexts, we first propose a formal evaluation of our contributions before realizing some experiments.The first contribution is about a synchronous reactive language, represented by a block-diagram algebra. Such programs operate on infinite streams and model real-time processes. We propose a constraint model together with a new global constraint. Our new filtering algorithm is inspired from Abstract Interpretation. It computes over-approximations of the infinite stream values computed by the block-diagrams. We evaluated our verification process on the FAUST language (a language for processing real-time audio streams) and we tested it on examples from the FAUST standard library. The second contribution considers probabilistic processes represented by Parametric Interval Markov Chains, a specification formalism that extends Markov Chains. We propose constraint models for checking qualitative and quantitative reachability properties. Our models for the qualitative case improve the state of the art models, while for the quantitative case our models are the first ones. We implemented and evaluated our verification constraint models as mixed integer linear programs and satisfiability modulo theory programs. Experiments have been realized on a PRISM based benchmark
Gerber, Erick D. B. "A model checker for the LF system." Thesis, Stellenbosch : Stellenbosch University, 2007. http://hdl.handle.net/10019.1/19597.
ENGLISH ABSTRACT: Computer aided veri cation techniques, such as model checking, can be used to improve the reliability of software. Model checking is an algorithmic approach to illustrate the correctness of temporal logic speci cations in the formal description of hardware and software systems. In contrast to traditional testing tools, model checking relies on an exhaustive search of all the possible con gurations that these systems may exhibit. Traditionally model checking is applied to abstract or high level designs of software. However, often interpreting or translating these abstract designs to implementations introduce subtle errors. In recent years one trend in model checking has been to apply the model checking algorithm directly to the implementations instead. This thesis is concerned with building an e cient model checker for a small concurrent langauge developed at the University of Stellenbosch. This special purpose langauge, LF, is aimed at developement of small embedded systems. The design of the language was carefully considered to promote safe programming practices. Furthermore, the language and its runtime support system was designed to allow directly model checking LF programs. To achieve this, the model checker extends the existing runtime support infrastructure to generate the state space of an executing LF program.
AFRIKAANSE OPSOMMING: Rekenaar gebaseerde program toetsing, soos modeltoetsing, kan gebruik word om die betroubaarheid van sagteware te verbeter. Model toetsing is 'n algoritmiese benadering om die korrektheid van temporale logika spesi kasies in die beskrywing van harde- of sagteware te bewys. Anders as met tradisionlee program toetsing, benodig modeltoetsing 'n volledige ondersoek van al die moontlike toestande waarin so 'n beskrywing homself kan bevind. Model toetsing word meestal op abstrakte modelle van sagteware of die ontwerp toegepas. Indien die ontwerp of model aan al die spesi kasies voldoen word die abstrakte model gewoontlik vertaal na 'n implementasie. Die vertalings proses word gewoontlik met die hand gedoen en laat ruimte om nuwe foute, en selfs foute wat uitgeskakel in die model of ontwerp is te veroorsaak. Deesdae, is 'n gewilde benadering tot modeltoetsing om di e tegnieke direk op die implementasie toe te pas, en sodoende die ekstra moeite van model konstruksie en vertaling uit te skakel. Hierdie tesis handel oor die ontwerp, implementasie en toetsing van 'n e ektiewe modeltoetser vir 'n klein gelyklopende taal, LF, wat by die Universiteit van Stellenbosch ontwikkel is. Die enkeldoelige taal, LF, is gemik op die veilige ontwikkeling van ingebedde sagteware. Die taal is ontwerp om veilige programmerings praktyke aan te moedig. Verder is die taal en die onderliggende bedryfstelsel so ontwerp om 'n model toetser te akkomodeer. Om die LF programme direk te kan toets, is die model toetser 'n integrale deel van die bedryfstelsel sodat dit die program kan aandryf om alle moontlike toestande te besoek.
Cyriac, Aiswarya, and Aiswarya Cyriac. "Verification of communicating recursive programs via split-width." Phd thesis, École normale supérieure de Cachan - ENS Cachan, 2014. http://tel.archives-ouvertes.fr/tel-01015561.
Weitz, Noah. "Analysis of Verification and Validation Techniques for Educational CubeSat Programs." DigitalCommons@CalPoly, 2018. https://digitalcommons.calpoly.edu/theses/1854.
Palikareva, Hristina. "Techniques and tools for the verification of concurrent systems." Thesis, University of Oxford, 2012. http://ora.ox.ac.uk/objects/uuid:fc2028e1-2a45-459a-afdd-70001893f3d8.
Tuch, Harvey Computer Science & Engineering Faculty of Engineering UNSW. "Formal memory models for verifying C systems code." Publisher:University of New South Wales. Computer Science & Engineering, 2008. http://handle.unsw.edu.au/1959.4/41233.
De, Oliveira Steven. "Finding constancy in linear routines." Thesis, Université Paris-Saclay (ComUE), 2018. http://www.theses.fr/2018SACLS207/document.
The 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
Zeng, Reng. "Methods for Modeling and Analyzing Concurrent Software." FIU Digital Commons, 2013. http://digitalcommons.fiu.edu/etd/931.
Wichers, Sacha. "Verification of numerical models for hydrothermal plume water through field measurements at TAG." Thesis, Massachusetts Institute of Technology, 2005. http://hdl.handle.net/1721.1/39173.
Includes bibliographical references (p. 63-65).
Hydrothermal vents discharge superheated, mineral rich water into our oceans, thereby providing a habitat for exotic chemosynthetic biological communities. Hydrothermal fluids are convected upwards until they cool and reach density equilibrium, at which point they advect laterally with the current. The neutrally buoyant plume layer can have length scales on the order of several kilometers, and it therefore provides the best means to detect the presence of vent fields on the seafloor, which typically have length scales on the order of a few meters. This thesis uses field measurements of the velocity, temperature and particulate anomalies associated with the TAG hydrothermal plume to demonstrate that tidal currents exert a strong impact on the plume shape, and to provide new constraints on the thermal power of the TAG hydrothermal system. The results show that the power output of the TAG system is on the order of 6000 MW, which is up to two orders of magnitude greater than previous estimates, and that there is considerably more entrainment than had previously been assumed.
by Sacha Wichers.
S.M.
Kerbrat, Alain. "Méthodes symboliques pour la vérification de processus communicants : étude et mise en oeuvre." Université Joseph Fourier (Grenoble), 1994. http://tel.archives-ouvertes.fr/tel-00005100.
Bull, J. J. D. "A comparison of two different model checking techniques." Thesis, Stellenbosch : Stellenbosch University, 2003. http://hdl.handle.net/10019.1/53235.
ENGLISH ABSTRACT: Model checking is a computer-aided verification technique that is used to verify properties about the formal description of a system automatically. This technique has been applied successfully to detect subtle errors in reactive systems. Such errors are extremely difficult to detect by using traditional testing techniques. The conventional method of applying model checking is to construct a model manually either before or after the implementation of a system. Constructing such a model requires time, skill and experience. An alternative method is to derive a model from an implementation automatically. In this thesis two techniques of applying model checking to reactive systems are compared, both of which have problems as well as advantages. Two specific strategies are compared in the area of protocol development: 1. Structuring a protocol as a transition system, modelling the system, and then deriving an implementation from the model. 2. Automatically translating implementation code to a verifiable model. Structuring a reactive system as a transition system makes it possible to verify the control flow of the system at implementation level-as opposed to verifying the control flow at abstract level. The result is a closer correspondence between implementation and specification (model). At the same time testing, which is restricted to small, independent code fragments that manipulate data, is simplified significantly. The construction of a model often takes too long; therefore, verification results may no longer be applicable when they become available. To address this problem, the technique of automated model extraction was suggested. This technique aims to reduce the time required to construct a model by minimising manual input during model construction. A transition system is a low-level formalism and direct execution through interpretation is feasible. However, the overhead of interpretation is the major disadvantage of this technique. With automated model extraction there are disadvantages too. For example, differences between the implementation and specification languages-such as constructs present in the implementation language that cannot be expressed in the modelling language-make the development of an automated model extraction tool extremely difficult. In conclusion, the two techniques are compared against a set of software development considerations. Since a specific technique is not always preferable, guidelines are proposed to help select the best approach in different circumstances.
AFRIKAANSE OPSOMMING: Modeltoetsing is 'n rekenaargebaseerde verifikasietegniek wat gebruik word om eienskappe rakende 'n formele spesifikasie van 'n stelsel te verifieer. Die tegniek is al suksesvol toegepas om subtiele foute in reaktiewe stelsels op te spoor. Sulke foute word uiters moeilik opgespoor as tradisionele toetsings tegnieke gebruik word. Tradisioneel word modeltoetsing toegepas deur 'n model te bou voor of na die implementasie van 'n stelsel. Om'n model te bou verg tyd, vernuf en ervaring. 'n Alternatiewe metode is om outomaties 'n model van 'n implementasie af te lei. In hierdie tesis word twee toepassingstegnieke van modeltoetsing vergelyk, waar beide tegnieke beskik oor voordele sowel as nadele. Twee strategieë word vergelyk in die gebied van protokol ontwikkeling: 1. Om 'n protokol as 'n oorgangsstelsel te struktureer, dit te moduleer en dan 'n implementasie van die model af te lei. 2. Om outomaties 'n verifieerbare model van 'n implementasie af te lei. Om 'n reaktiewe stelsel as 'n oorgangsstelsel te struktureer maak dit moontlik om die kontrolevloei op implementasie vlak te verifieer-in teenstelling met verifikasie van kontrolevloei op 'n abstrakte vlak. Die resultaat is 'n nouer band wat bestaan tussen die implementasie en die spesifikasie. Terselfdetyd word toetsing, wat beperk word tot klein, onafhanklike kodesegmente wat data manupileer, beduidend vereenvoudig. Die konstruksie van 'n model neem soms te lank; gevolglik, wanneer die verifikasieresultate beskikbaar word, is dit dalk nie meer toepaslik op die huidige weergawe van 'n implementasie nie. Om die probleem aan te spreek is 'n tegniek om modelle outomaties van implementasies af te lei, voorgestel. Die doel van die tegniek is om die tyd wat dit neem om 'n model te bou te verminder deur handtoevoer tot 'n minimum te beperk. 'n Oorgangsstelsel is 'n laevlak formalisme en direkte uitvoering deur interpretasie is wesenlik. Die oorhoofse koste van die interpreteerder is egter die grootste nadeel van die tegniek. Daar is ook nadele wat oorweeg moet word rakende die tegniek om outomaties modelle van implementasies af te lei. Byvoorbeeld, verskille tussen die implementasietaal en spesifikasietaal=-soos byvoorbleed konstrukte wat in die implementasietaal gebruik word wat nie in die modeleringstaal voorgestel kan word nie-vrnaak die ontwikkeling van 'n modelafieier uiters moeilik. As gevolg word die twee tegnieke vergelyk teen 'n stel van programatuurontwikkelingsoorwegings. Omdat 'n spesifieke tegniek nie altyd voorkeur kan geniet nie, word riglyne voorgestel om te help met die keuse om die beste tegniek te kies in verskillende omstandighede.
Ben, Henda Noomene. "Infinite-state Stochastic and Parameterized Systems." Doctoral thesis, Uppsala University, Department of Information Technology, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-8915.
A major current challenge consists in extending formal methods in order to handle infinite-state systems. Infiniteness stems from the fact that the system operates on unbounded data structure such as stacks, queues, clocks, integers; as well as parameterization.
Systems with unbounded data structure are natural models for reasoning about communication protocols, concurrent programs, real-time systems, etc. While parameterized systems are more suitable if the system consists of an arbitrary number of identical processes which is the case for cache coherence protocols, distributed algorithms and so forth.
In this thesis, we consider model checking problems for certain fundamental classes of probabilistic infinite-state systems, as well as the verification of safety properties in parameterized systems. First, we consider probabilistic systems with unbounded data structures. In particular, we study probabilistic extensions of Lossy Channel Systems (PLCS), Vector addition Systems with States (PVASS) and Noisy Turing Machine (PNTM). We show how we can describe the semantics of such models by infinite-state Markov chains; and then define certain abstract properties, which allow model checking several qualitative and quantitative problems.
Then, we consider parameterized systems and provide a method which allows checking safety for several classes that differ in the topologies (linear or tree) and the semantics (atomic or non-atomic). The method is based on deriving an over-approximation which allows the use of a symbolic backward reachability scheme. For each class, the over-approximation we define guarantees monotonicity of the induced approximate transition system with respect to an appropriate order. This property is convenient in the sense that it preserves upward closedness when computing sets of predecessors.
Padoan, Tommaso. "Tableaux, automata and games for true concurrency properties." Doctoral thesis, Università degli studi di Padova, 2019. http://hdl.handle.net/11577/3425438.
Bekkouche, Mohammed. "Combinaison des techniques de Bounded Model Checking et de programmation par contraintes pour l'aide à la localisation d'erreurs : exploration des capacités des CSP pour la localisation d'erreurs." Thesis, Nice, 2015. http://www.theses.fr/2015NICE4096/document.
A model checker can produce a trace of counter-example for erroneous program, which is often difficult to exploit to locate errors in source code. In my thesis, we proposed an error localization algorithm from counter-examples, named LocFaults, combining approaches of Bounded Model-Checking (BMC) with constraint satisfaction problem (CSP). This algorithm analyzes the paths of CFG (Control Flow Graph) of the erroneous program to calculate the subsets of suspicious instructions to correct the program. Indeed, we generate a system of constraints for paths of control flow graph for which at most k conditional statements can be wrong. Then we calculate the MCSs (Minimal Correction Sets) of limited size on each of these paths. Removal of one of these sets of constraints gives a maximal satisfiable subset, in other words, a maximal subset of constraints satisfying the postcondition. To calculate the MCSs, we extend the generic algorithm proposed by Liffiton and Sakallah in order to deal with programs with numerical instructions more efficiently. This approach has been experimentally evaluated on a set of academic and realistic programs
Djoudi, Adel. "Binary level static analysis." Thesis, Université Paris-Saclay (ComUE), 2016. http://www.theses.fr/2016SACLX093.
Automatic software verification methods have seen increasing success since the early 2000s, thanks to several industrial successes (Microsoft, Airbus, etc.).Static program analysis aims to automatically infer verified properties of programs, based on their descriptions. The standard static analysis techniques apply on the software source code, written for instance in C or Java. However, access to source code is not possible for many safety-related applications, whether the source code is not available (mobile code, computer virus), or the developer does not disclose it (shelf components, third party certification).We are interested in this dissertation in design and development of a static binary analysis platform for safety analysis. Our contributions are made at three levels: semantics, implementation and static analysis.First, the semantics of analyzed binary programs is based on a generic, simple and concise formalism called DBA. It is extended with some specification and abstraction mechanisms in this dissertation. A well defined semantics of binary programs requires also an adequate memory model. We propose a new memory model adapted to binary level requirements and inspired from recent work on low-level C. This new model allows to enjoy the abstraction of the region-based memory model while keeping the expressiveness of the flat model.Second, our binary code analysis platform BinSec offers three basic services:disassembly, simulation and static analysis. Each machine instruction is translated into a block of semantically equivalent DBA instructions. The platform handles a large part of x86 instructions. A simplification step eliminates useless intermediate calculations in order to ease further analyses. Our simplifications especially allow to eliminate up to 75% of flag updates.Finally, we developed a static analysis engine for binary programs based on abstract interpretation. Besides abstract domains specifically adapted to binary analysis, we focused on the user control of trade offs between accuracy/correctness and efficiency. In addition, we offer an original approach for high-level conditions recovery from low-level conditions in order to enhance analysis precision. The approach is sound, efficient, platform-independent and it achieves very high ratio of recovery
Boulgakov, Alexandre. "Improving scalability of exploratory model checking." Thesis, University of Oxford, 2016. https://ora.ox.ac.uk/objects/uuid:76acb8bf-52e7-4078-ab4f-65f3ea07ba3d.
Šimáček, Jiří. "Verifikace Programů se složitými datovými strukturami." Doctoral thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2012. http://www.nusl.cz/ntk/nusl-261270.
Fruth, Matthias. "Formal methods for the analysis of wireless network protocols." Thesis, University of Oxford, 2011. http://ora.ox.ac.uk/objects/uuid:df2c08f4-001c-42d3-a2f4-9922f081fb49.
Ferrarezi, Rodrigo César. "Framework para modelagem e verificação formal de programas de controle de sistemas instrumentados de segurança." Universidade de São Paulo, 2014. http://www.teses.usp.br/teses/disponiveis/3/3152/tde-31122015-112539/.
Due to the high complexity of the actual Productive Systems, the design of suitable control systems according to the applicable industrial standards, and the possible negative impacts on the human being, on the environment and on equipment, the development of control solutions that are be both secure and stable as some systems have to operate nonstop is much demanded. One approach for the development systems with such requirements is the use of Safety Instrumented Systems complying with the standards IEC 61508 and IEC 61511. However, as on the development of any kind of software, SIS control programs are also prone to specification and design errors, even when the control programs are developed according to the applicable standards. Besides design errors, must be taken into consideration the fact that the SIS prevention and mitigation layers, as prescribed on the standards, can be developed individually and thus presenting unanticipated or undesirable behaviors when operating together. One way to improve the reliability of these control programs, which is also required by the safety standards IEC 61508 and IEC 61511 as part of the SIS development cycle, is the application of formal verification techniques on the control software models. Another way is to use a unified approach for modeling these control systems, and thus having the opportunity to understand their interactions better. Currently, one of the most prominent techniques for the verification of systems is the Model Checking. Such technique performs an exhaustive search in the space state of an event driven system, verifying the properties specified as established propositions in temporal logic. On this work, the TCTL logic is used due its ability to express properties in the dense time domain. As computational tool will be used GHENeSys environment, as it provides a unified environment for modeling, simulating and the verification of systems, which enjoys the benefits of modelling through Petri Nets and Model Checking techniques for formal verification.
Kotoun, Michal. "Symbolické automaty v analýze programů s řetězci." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2020. http://www.nusl.cz/ntk/nusl-433553.
Bobot, François. "Logique de séparation et vérification déductive." Phd thesis, Université Paris Sud - Paris XI, 2011. http://tel.archives-ouvertes.fr/tel-00652508.
Latham, J. T. "Abstraction in program verification." Thesis, University of Manchester, 1985. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.372026.
Nutz, Alexander [Verfasser], and Andreas [Akademischer Betreuer] Podelski. "Data flow in program verification." Freiburg : Universität, 2019. http://d-nb.info/1209878453/34.
Gonzalez, Perez Carlos Alberto. "Pragmatic model verification." Thesis, Nantes, Ecole des Mines, 2014. http://www.theses.fr/2014EMNA0189/document.
Model-Driven Engineering (MDE) is a popular approach to the development of software which promotes the use of models as first-Class citizens in the software development process. In a MDE-Based software development process, software is developed by creating models to be successively transformed into another models and eventually into the software source code. When MDE is applied to the development of complex software systems, the complexity of models and model transformations increase, thus risking both, the reliability of the software development process and the soundness of the resulting software. Traditionally, ensuring software correctness and absence of errors has been addressed by means of software verification approaches, based on the utilization of formal analysis techniques, and software testing approaches. In order to ensure the reliability of MDE-Based software development processes, these techniques have some how been adapted to try to ensure correctness of models and model transformations. The objective of this thesis is to provide new mechanisms to improve the landscape of approaches devoted to the verification of static models, and analyze how these static model verification approaches can be of assistance at the time of testing model transformations
Fan, Yang, Hidehiko Masuhara, Tomoyuki Aotani, Flemming Nielson, and Hanne Riis Nielson. "AspectKE*: Security aspects with program analysis for distributed systems." Universität Potsdam, 2010. http://opus.kobv.de/ubp/volltexte/2010/4136/.
Clouet, Myriam. "Langage de spécification et outil de vérification pour le consentement et la nécessité des données fondés sur une classification relative au respect de la vie privée." Electronic Thesis or Diss., université Paris-Saclay, 2024. http://www.theses.fr/2024UPASG023.
Privacy is a fundamental right implemented in many laws around the world. Therefore, verifying that a system complies with privacy is crucial. However, privacy is also a complex notion. Besides, ensuring compliance of a software system with respect to privacy requires to verify that the expected privacy properties hold during the whole system lifecycle. It usually involves different abstraction levels, which complicates the verification process. Many different solutions have been proposed to enhance privacy. It is often quite hard to precisely identify whether they target the same problem.This thesis addresses these issues by proposing a way to classify privacy papers and an approach to verify privacy properties at two different development stages. It proposes GePyR, a new generic and specializable representation, and an instantiable ontology, PyCO, that models key privacy elements and their relationships. This classification is evaluated on the literature, by using a Systematic Mapping Study. This thesis also formalizes two privacy properties, purpose compliance and necessity compliance. It proposes a new specification language, named CSpeL, that allows engineers to formally specify key system elements with regards to these properties, and introduces a new tool, CASTT, to verify the aforementioned properties on execution traces, on a model or on a program. This approach is applied on two use cases, both at two abstraction levels (model and code), in order to evaluate its correctness, its efficiency and its usefulness
Axelsson, Roland. "Verification of Non-Regular Program Properties." Diss., lmu, 2010. http://nbn-resolving.de/urn:nbn:de:bvb:19-116775.
Durand-Gasselin, Antoine. "Automata based logics for program verification." Paris 7, 2013. http://www.theses.fr/2013PA077238.
Formal software verification consists in a rigorous analysis of programs using mathematical logic, in order to demonstrat they meet their specification, and ensure with strong confidence in the absence of bugs. The choice of the logical framework to perform the analysis is crucial, and must address two issues: not only must the logic be expressive enough to express the specification and reflect the action of each instruction, but also the logic formalism must be simple enough in order to automate efficiently as much as possible the verification process. In this thesis we will study two logical frameworks and show how to manipulate those. First we will focus on first-order logics over automatic structures, such as Presburger Arithmetics which allows to express properties about integers. We will show that formulas can be effectively represented as automata, and we will detail a generic automata-based algorithn that allow to decide such first-order logics, whose complexity closely matches the hardness of those logics. Then we will present streaming string transducers, which are automata with a finite number of write-only registers and we will inspect their expressiveness. We will present this elegant extension of finite state automata to define string transformations as an intuitive computational model and we will establish their expressive power is precisely express transformations definable by monadic second-order logics
Pace, Kyongsuk P. "FNMOC model verification system." Thesis, Monterey, Calif. : Springfield, Va. : Naval Postgraduate School ; Available from National Technical Information Service, 1998. http://handle.dtic.mil/100.2/ADA349774.
Taghdiri, Mana 1979. "Automating modular program verification by refining specifications." Thesis, Massachusetts Institute of Technology, 2008. http://hdl.handle.net/1721.1/43055.
Includes bibliographical references (p. 205-211).
Modular analyses of software systems rely on the specifications of the analyzed modules. In many analysis techniques (e.g. ESC/Java), the specifications have to be provided by users. This puts a considerable burden on users and thus limits the applicability of such techniques. To avoid this problem, some modular analysis techniques automatically extract module summaries that capture specific aspects of the modules' behaviors. However, such summaries are only useful in checking a restricted class of properties. We describe a static modular analysis that automatically extracts procedure specifications in order to check heap-manipulating programs against rich data structure properties. Extracted specifications are context-dependent; their precision depends on both the property being checked, and the calling context in which they are used. Starting from a rough over-approximation of the behavior of each call site, our analysis computes an abstraction of the procedure being analyzed and checks it against the property. Specifications are further refined, as needed, in response to spurious counterexamples. The analysis terminates when either the property has been validated (with respect to a finite domain), or a non-spurious counterexample has been found. Furthermore, we describe a lightweight static technique to extract specifications of heap-manipulating procedures. These specifications neither are context-dependent, nor require any domain finitizations. They summarize the general behavior of procedures in terms of their effect on program state. They bound the values of all variables and fields in the post-state of the procedure by relational expressions in terms of their values in the pre-state. The analysis maintains both upper and lower bounds so that in some cases an exact result can be obtained.
by Mana Taghdiri.
Ph.D.