To see the other types of publications on this topic, follow the link: Computer language verification.
Dissertations / Theses on the topic 'Computer language 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 'Computer language 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
Swart, Riaan. "A language to support verification of embedded software." Thesis, Stellenbosch : Stellenbosch University, 2004. http://hdl.handle.net/10019.1/49823.
Full textAbstract:
Thesis (MSc)--University of Stellenbosch, 2004.ENGLISH ABSTRACT: Embedded computer systems form part of larger systems such as aircraft or chemical processing facilities. Although testing and debugging of such systems are difficult, reliability is often essential. Development of embedded software can be simplified by an environment that limits opportunities for making errors and provides facilities for detection of errors. We implemented a language and compiler that can serve as basis for such an experimental environment. Both are designed to make verification of implementations feasible. Correctness and safety were given highest priority, but without sacrificing efficiency wherever possible. The language is concurrent and includes measures for protecting the address spaces of concurrently running processes. This eliminates the need for expensive run-time memory protection and will benefit resource-strapped embedded systems. The target hardware is assumed to provide no special support for concurrency. The language is designed to be small, simple and intuitive, and to promote compile-time detection of errors. Facilities for abstraction, such as modules and abstract data types support implementation and testing of bigger systems. We have opted for model checking as verification technique, so our implementation language is similar in design to a modelling language for a widely used model checker. Because of this, the implementation code can be used as input for a model checker. However, since the compiler can still contain errors, there might be discrepancies between the implementation code written in our language and the executable code produced by the compiler. Therefore we are attempting to make verification of executable code feasible. To achieve this, our compiler generates code in a special format, comprising a transition system of uninterruptible actions. The actions limit the scheduling points present in processes and reduce the different interleavings of process code possible in a concurrent system. Requirements that conventional hardware places on this form of code are discussed, as well as how the format influences efficiency and responsiveness.
AFRIKAANSE OPSOMMING: Ingebedde rekenaarstelsels maak deel uit van groter stelsels soos vliegtuie of chemiese prosesseerfasiliteite. Hoewel toetsing en ontfouting van sulke stelsels moeilik is, is betroubaarheid dikwels onontbeerlik. Ontwikkeling van ingebedde sagteware kan makliker gemaak word met 'n ontwikkelingsomgewing wat geleenthede vir foutmaak beperk en fasiliteite vir foutbespeuring verskaf. Ons het 'n programmeertaal en vertaler geïmplementeer wat as basis kan dien vir so 'n eksperimentele omgewing. Beide is ontwerp om verifikasie van implementasies haalbaar te maak. Korrektheid en veiligheid het die hoogste prioriteit geniet, maar sonder om effektiwiteit prys te gee, waar moontlik. Die taal is gelyklopend en bevat maatreëls om die adresruimtes van gelyklopende prosesse te beskerm. Dit maak duur looptyd-geheuebeskerming onnodig, tot voordeel van ingebedde stelsels met 'n tekort aan hulpbronne. Daar word aangeneem dat die teikenhardeware geen spesiale ondersteuning vir gelyklopendheid bevat nie. Die programmeertaal is ontwerp om klein, eenvoudig en intuïtief te wees, en om vertaaltyd-opsporing van foute te bevorder. Fasiliteite vir abstraksie, byvoorbeeld modules en abstrakte datatipes, ondersteun implementering en toetsing van groter stelsels. Ons het modeltoetsing as verifikasietegniek gekies, dus is die ontwerp van ons programmeertaal soortgelyk aan dié van 'n modelleertaal vir 'n modeltoetser wat algemeen gebruik word. As gevolg hiervan kan die implementasiekode as toevoer vir 'n modeltoetser gebruik word. Omdat die vertaler egter steeds foute kan bevat, mag daar teenstrydighede bestaan tussen die implementasie geskryf in ons implementasietaal, en die uitvoerbare masjienkode wat deur die vertaler gelewer word. Daarom poog ons om verifikasie van die uitvoerbare masjienkode haalbaar te maak. Om hierdie doelwit te bereik, is ons vertaler ontwerp om 'n spesiale formaat masjienkode te genereer bestaande uit 'n oorgangstelsel wat ononderbreekbare (atomiese) aksies bevat. Die aksies beperk die skeduleerpunte in prosesse en verminder sodoende die aantal interpaginasies van proseskode wat moontlik is in 'n gelyklopende stelsel. Die vereistes wat konvensionele hardeware aan dié spesifieke formaat kode stel, word bespreek, asook hoe die formaat effektiwiteit en reageerbaarheid van die stelsel beïnvloed.
2
Pappalardo, Giuseppe. "Specification and verification issues in a process language." Thesis, University of Newcastle Upon Tyne, 1996. http://hdl.handle.net/10443/2016.
Full textAbstract:
While specification formalisms for reactive concurrent systems are now reasonably well-understood theoretically, they have not yet entered common, widespread design practice. This motivates the attempt made in this work to enhance the applicability of an important and popular formal framework: the CSP language, endowed with a failure-based denotational semantics and a logic for describing failures of processes. The identification of behaviour with a set of failures is supported by a convincing intuitive reason: processes with different failures can be distinguished by easily realizable experiments. But, most importantly, many interesting systems can be described and studied in terms of their failures. The main technique employed for this purpose is a logic in which process expressions are required to satisfy an assertion with each failure of the behaviour they describe. The theory of complete partial orders, with its elegant treatment of recursion and fixpoint-based verification, can be applied to this framework. However, in spite of the advantages illustrated, the practical applicability of standard failure semantics is impaired by two weaknesses. The first is its inability to describe many important systems, constructed by connecting modules that can exchange values of an infinite set across ports invisible to the environment. This must often be assumed for design and verification purposes (e.g. for the many protocols relying upon sequence numbers to cope with out-of-sequence received messages). Such a deficiency is due to the definition of the hiding operator in standard failure semantics. This thesis puts forward a solution based on an interesting technical result about infinite sets of sequences. Another difficulty with standard failure semantics is its treatment of divergence, the phenomenon in which some components of a system interact by performing an infinite, uninterrupted sequence of externally invisible actions. Within failure semantics, divergence cannot be abstracted from on the basis of the implicit fairness assumption that, if there is a choice leading out of divergence, it will eventually be made. This 'fair abstraction' is essential for the verification of many important systems, including communication protocols. The solution proposed in this thesis is an extended failure semantics which records refused traces, rather than just actions. Not only is this approach compatible with fair abstraction, but it also permits, like ordinary failure semantics, verification in a compositional calculus with fixpoint induction. Rather interestingly, these results can be obtained outside traditional fixpoint theory, which cannot be applied in this case. The theory developed is based on the novel notion of 'trace-based' process functions. These can be shown to possess a particular fixpoint that, unlike the least fixpoint of traditional treatments, is compatible with fair abstraction. Moreover, they form a large class, sufficient to give a compositional denotational semantics to a useful eSP-like process language. Finally, a logic is proposed in which the properties of a process' extended failures can be expressed and analyzed; the methods developed are applied to the verification of two example communication protocols: a toy one and a large case study inspired by a real transport protocol.
3
Yessenov, Kuat T. "A lightweight specification language for bounded program verification." Thesis, Massachusetts Institute of Technology, 2009. http://hdl.handle.net/1721.1/53184.
Full textAbstract:
Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009.Cataloged from PDF version of thesis.
Includes bibliographical references (p. 63-64).
This thesis presents a new light-weight specification language called JForge Specification Language (JFSL) for object-oriented languages such as Java. The language is amenable to bounded verification analysis by a tool called JForge that interprets JFSL specifications, fully integrates with a mainstream development environment, and assists programmers in examining counter example traces and debugging specifications. JFSL attempts to address challenges of specification languages such as inheritance, frame conditions, dynamic dispatch, and method calls inside specifications in the context of bounded verification. A collection of verification tasks illustrates the expressiveness and conciseness of JForge specifications and demonstrates effectiveness of the bounded verification technique.
by Kuat T. Yessenov.
M.Eng.
4
Wilson, Thomas. "The Omnibus language and integrated verification approach." Thesis, University of Stirling, 2007. http://hdl.handle.net/1893/260.
Full textAbstract:
This thesis describes the Omnibus language and its supporting framework of tools. Omnibus is an object-oriented language which is superficially similar to the Java programming language but uses value semantics for objects and incorporates a behavioural interface specification language. Specifications are defined in terms of a subset of the query functions of the classes for which a frame-condition logic is provided. The language is well suited to the specification of modelling types and can also be used to write implementations. An overview of the language is presented and then specific aspects such as subtleties in the frame-condition logic, the implementation of value semantics and the role of equality are discussed. The challenges of reference semantics are also discussed. The Omnibus language is supported by an integrated verification tool which provides support for three assertion-based verification approaches: run-time assertion checking, extended static checking and full formal verification. The different approaches provide different balances between rigour and ease of use. The Omnibus tool allows these approaches to be used together in different parts of the same project. Guidelines are presented in order to help users avoid conflicts when using the approaches together. The use of the integrated verification approach to meet two key requirements of safe software component reuse, to have clear descriptions and some form of certification, are discussed along with the specialised facilities provided by the Omnibus tool to manage the distribution of components. The principles of the implementation of the tool are described, focussing on the integrated static verifier module that supports both extended static checking and full formal verification through the use of an intermediate logic. The different verification approaches are used to detect and correct a range of errors in a case study carried out using the Omnibus language. The case study is of a library system where copies of books, CDs and DVDs are loaned out to members. The implementation consists of 2278 lines of Omnibus code spread over 15 classes. To allow direct comparison of the different assertion-based verification approaches considered, run-time assertion checking, extended static checking and then full formal verification are applied to the application in its entirety. This directly illustrates the different balances between error coverage and ease-of-use which the approaches offer. Finally, the verification policy system is used to allow the approaches to be used together to verify different parts of the application.
5
Zaccai, Diego Sebastian. "A Balanced Verification Effort for the Java Language." The Ohio State University, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=osu1461243619.
Full text
6
Veselinov, Roman Nikolov. "Formalization and verification of rewriting-based security polices." Worcester, Mass. : Worcester Polytechnic Institute, 2008. http://www.wpi.edu/Pubs/ETD/Available/etd-043008-165615/.
Full text
7
Yao, Huan 1976. "Utterance verification in large vocabulary spoken language understanding system." Thesis, Massachusetts Institute of Technology, 1998. http://hdl.handle.net/1721.1/47633.
Full text
8
Hummelgren, Lars. "A contract language for modular specification and verification of temporal properties." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-280457.
Full textAbstract:
Deductive software verification is used to prove correctness of programs with respect to contracts. Contracts are commonly expressed on procedures of a program using Hoare logic. Such contracts consist of a precondition, specifying a condition that must hold before the procedure is executed, and a postcondition which specifies what is guaranteed in return. A contract can be considered an agreement between the user of a procedure and its developer. It is important that the process of verifying that the procedures of a program satisfy their respective contracts is scalable. Scalability can be achieved by making sure verification is procedure-modular, which means that every procedure call can be replaced by the contract of the called procedure directly instead of being evaluated. The axioms of Hoare logic makes it a good basis for procedure-modular reasoning. But Hoare logic is not well-suited for reasoning about a procedure’s behaviour over a sequence of states. The stated questions are how a contract language for specifying such temporal properties can be designed, and how a procedure can be verified to satisfy contracts expressed in such a contract language in a procedure-modular way. To answer the question, a simple programming language with procedures is presented first. The intent is that contracts are expressed on programs written in this programming language. Two contract languages are presented. It is shown how contracts can be formulated in these languages to specify temporal properties of procedures, and how procedures can be verified to satisfy such temporal contracts. The first contract language is limited in terms of its expressivity, but its contracts can be automatically verified. The second language can be used to express more complex properties, but its verification problem turns out to be undecidable. Alternative approaches to its verification problem are discussed.Deduktiv mjukvaruverifikation används för att bevisa korrekthet av program med avseende på kontrakt. Kontrakt uttrycks ofta på procedurer i ett program med användning av Hoare-logik. Sådana kontrakt består av ett förvillkor som specificerar ett villkor som måste gälla innan proceduren exekveras och ett eftervillkor som uttrycker vad som garanteras i gengäld. Ett kontrakt kan ses som en överenskommelse mellan användaren av en procedur och dess utvecklare. Det är viktigt att det på ett skalbart sätt går att verifiera att procedurer i ett program uppfyller deras respektive kontrakt. Skalbarhet kan uppnås genom att se till att verifikationen är procedur-modulär, vilket innebär att varje proceduranrop direkt ersätts med kontraktet som tillhör den anropade proceduren i stället för att proceduranropet utvärderas. Hoare-logikens axiom gör den till en bra grund för procedur-modulära resonemang. Men Hoare-logik är inte välanpassad för att resonera kring en procedurs beteende under en sekvens av tillstånd. Frågorna som ställs är hur ett kontraktspråk för att specificera sådana temporala egenskaper kan utformas samt hur en procedur kan verifieras att uppfylla kontrakt uttryckta i ett sådant kontraktspråk på ett procedur-modulärt sätt. För att besvara frågan presenteras först ett enkelt programmeringsspråk med procedurer. Syftet är att kontrakt uttrycks på program skrivna i detta programspråk. Två kontraktspråk presenteras. Det visas hur kontrakt kan formuleras i dessa språk för att specificera temporala egenskaper av procedurer samt hur procedurer kan verifieras att uppfylla sådana temporala kontrakt. Det första kontraktspråket är begränsat med avseende på dess uttrycksfullhet, men dess kontrakt kan automatiskt verifieras. Det andra språket kan användas för att uttrycka mer komplicerade egenskaper, men dess verifikationsproblem visar sig vara oavgörbart. Alternativa tillvägagångssätt för att hantera dess verifikationsproblem diskuteras.
9
Ardeishar, Raghu. "Automatic verification of VHDL models." Thesis, This resource online, 1990. http://scholar.lib.vt.edu/theses/available/etd-03032009-040338/.
Full text
10
Barrett, Geoff. "The semantics and implementation of occam." Thesis, University of Oxford, 1988. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.329014.
Full text
11
Gustavsson, Camilla, Linda Strindlund, and Emma Wiknertz. "Verification, Validation and Evaluation of the Virtual Human Markup Language (VHML)." Thesis, Linköping University, Department of Electrical Engineering, 2002. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-1137.
Full textAbstract:
Human communication is inherently multimodal. The information conveyed through body language, facial expression, gaze, intonation, speaking style etc. are all important components of everyday communication. An issue within computer science concerns how to provide multimodal agent based systems. Those are systems that interact with users through several channels. These systems can include Virtual Humans. A Virtual Human might for example be a complete creature, i.e. a creature with a whole body including head, arms, legs etc. but it might also be a creature with only a head, a Talking Head. The aim of the Virtual Human Markup Language (VHML) is to control Virtual Humans regarding speech, facial animation, facial gestures and body animation. These parts have previously been implemented and investigated separately, but VHML aims to combine them. In this thesis VHML is verified, validated and evaluated in order to reach that aim and thus VHML is made more solid, homogenous and complete. Further, a Virtual Human has to communicate with the user and even though VHML supports a number of other ways of communication, an important communication channel is speech. The Virtual Human has to be able to interact with the user, therefore a dialogue between the user and the Virtual Human has to be created. These dialogues tend to expand tremendously, hence the Dialogue Management Tool (DMT) was developed. Having a toolmakes it easier for programmers to create and maintain dialogues for the interaction. Finally, in order to demonstrate the work done in this thesis a Talking Head application, The Mystery at West Bay Hospital, has been developed and evaluated. This has shown the usefulness of the DMT when creating dialogues. The work that has been accomplished within this project has contributed to simplify the development of Talking Head applications.
12
Edelman, Joseph R. "Machine Code Verification Using The Bogor Framework." Diss., CLICK HERE for online access, 2008. http://contentdm.lib.byu.edu/ETD/image/etd2396.pdf.
Full text
13
Neal, Stephen. "A language for the dynamic verification of design patterns in distributed computing." Thesis, University of Kent, 2001. https://kar.kent.ac.uk/13532/.
Full text
14
Dailey, David M. "Integration of VHDL simulation and test verification into a Process Model Graph design environment." Thesis, This resource online, 1994. http://scholar.lib.vt.edu/theses/available/etd-11242009-020247/.
Full text
15
Luken, Jackson. "QED: A Fact Verification and Evidence Support System." The Ohio State University, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=osu1555074124008897.
Full text
16
Pamplin, Jason Andrew. "Formal Object Interaction Language: Modeling and Verification of Sequential and Concurrent Object-Oriented Software." unrestricted, 2007. http://etd.gsu.edu/theses/available/etd-04222007-205349/.
Full textAbstract:
Thesis (Ph. D.)--Georgia State University, 2007.Title from file title page. Ying Zhu, committee chair; Xiaolin Hu, Geoffrey Hubona, Roy Johnson, Rajshekhar Sunderraman, committee members. Electronic text (216 p. : ill. (some col.)) : digital, PDF file. Description based on contents viewed Nov. 29, 2007. Includes bibliographical references (p. 209-216).
17
Yin, Pei. "Segmental discriminative analysis for American Sign Language recognition and verification." Diss., Georgia Institute of Technology, 2010. http://hdl.handle.net/1853/33939.
Full textAbstract:
This dissertation presents segmental discriminative analysis techniques for American Sign Language (ASL) recognition and verification. ASL recognition is a sequence classification problem. One of the most successful techniques for recognizing ASL is the hidden Markov model (HMM) and its variants. This dissertation addresses two problems in sign recognition by HMMs. The first is discriminative feature selection for temporally-correlated data. Temporal correlation in sequences often causes difficulties in feature selection. To mitigate this problem, this dissertation proposes segmentally-boosted HMMs (SBHMMs), which construct the state-optimized features in a segmental and discriminative manner. The second problem is the decomposition of ASL signs for efficient and accurate recognition. For this problem, this dissertation proposes discriminative state-space clustering (DISC), a data-driven method of automatically extracting sub-sign units by state-tying from the results of feature selection. DISC and SBHMMs can jointly search for discriminative feature sets and representation units of ASL recognition.
ASL verification, which determines whether an input signing sequence matches a pre-defined phrase, shares similarities with ASL recognition, but it has more prior knowledge and a higher expectation of accuracy. Therefore, ASL verification requires additional discriminative analysis not only in utilizing prior knowledge but also in actively selecting a set of phrases that have a high expectation of verification accuracy in the service of improving the experience of users. This dissertation describes ASL verification using CopyCat, an ASL game that helps deaf children acquire language abilities at an early age. It then presents the "probe" technique which automatically searches for an optimal threshold for verification using prior knowledge and BIG, a bi-gram error-ranking predictor which efficiently selects/creates phrases that, based on the previous performance of existing verification systems, should have high verification accuracy.
This work demonstrates the utility of the described technologies in a series of experiments. SBHMMs are validated in ASL phrase recognition as well as various other applications such as lip reading and speech recognition. DISC-SBHMMs consistently produce fewer errors than traditional HMMs and SBHMMs in recognizing ASL phrases using an instrumented glove. Probe achieves verification efficacy comparable to the optimum obtained from manually exhaustive search. Finally, when verifying phrases in CopyCat, BIG predicts which CopyCat phrases, even unseen in training, will have the best verification accuracy with results comparable to much more computationally intensive methods.
18
Abid, Nouha. "Verification of real time properties in fiacre language." Phd thesis, INSA de Toulouse, 2012. http://tel.archives-ouvertes.fr/tel-00782554.
Full text
19
Crutchfield, David Allen. "VERIFICATION AND DEBUG TECHNIQUES FOR INTEGRATED CIRCUIT DESIGNS." UKnowledge, 2009. http://uknowledge.uky.edu/gradschool_theses/631.
Full textAbstract:
Verification and debug of integrated circuits for embedded applications has grown in importance as the complexity in function has increased dramatically over time. Various modeling and debugging techniques have been developed to overcome the overwhelming challenge. This thesis attempts to address verification and debug methods by presenting an accurate C model at the bit and algorithm level coupled with an implemented Hardware Description Language (HDL). Key concepts such as common signal and variable naming conventions are incorporated as well as a stepping function within the implemented HDL. Additionally, a common interface between low-level drivers and C models is presented for early firmware development and system debug. Finally, selfchecking verification is discussed for delivering multiple test cases along with testbench portability.
20
Ulu, Cemil. "Specification And Verification Of Confidentiality In Software Architectures." Phd thesis, METU, 2004. http://etd.lib.metu.edu.tr/upload/12604809/index.pdf.
Full textAbstract:
This dissertation addresses the confidentiality aspect of the information security problem from the viewpoint of the software architecture. It presents a new approach to secure system design in which the desired security properties, in particular, confidentiality, of the system are proven to hold at the architectural level. The architecture description language Wright is extended so that confidentiality authorizations can be specified. An architectural description in Wright/c, the extended language, assigns clearance to the ports of the components and treats security labels as a part of data type information. The security labels are declared along with clearance assignments in an access control lattice model, also expressed in Wright/c. This enables the static analysis of data flow over the architecture subject to confidentiality requirements as per Bell-LaPadula principles. An algorithm takes the Wright/c description and the lattice model as inputs, and checks if there is a potential violation of the Bell-LaPadula principles. The algorithm also detects excess privileges. A software tool, which features an XML-based front-end to the algorithm is constructed. Finally, the algorithm is analyzed for its soundness, completeness and computational complexity.
21
Ubah, Ifeanyi. "A Language-Recognition Approach to Unit Testing Message-Passing Systems." Thesis, KTH, Skolan för informations- och kommunikationsteknik (ICT), 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-215655.
Full textAbstract:
This thesis addresses the problem of unit testing components in message-passing systems. A message-passing system is one that comprises components communicating with each other solely via the exchange of messages. Testing aids developers in detecting and fixing potential errors and with unit testing in particular, the focus is on independently verifying the correctness of single components, such as functions and methods, in a system whose behavior is well understood. With the aid of unit testing frameworks such as those of the xUnit family, this process can not only be automated and done iteratively, but easily interleaved with the development process, facilitating rapid feedback and early detection of errors in the system. However, such frameworks work in an imperative manner and as such, are unsuitable for verifying message-passing systems where the behavior of a component is encoded in its stream of exchanged messages. In this work, we recognise that similar to streams of symbols in the field of formal languages and abstract machines, one can specify properties of a component’s message stream such that they form a language. Unit testing a component thus becomes the description of an automaton that recognizes such a specified language. We propose a platform-independent, language-recognition approach to creating unit testing frameworks for describing and verifying the behavior of message-passing components, and use this approach in creating a prototype implementation for the Kompics component model. We show that this approach can be used to perform both black box and white box testing of components, and that it is easy to work with while preventing common mistakes in practice.
22
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.
Full textAbstract:
Systems code is almost universally written in the C programming language or a variant. C has a very low level of type and memory abstraction and formal reasoning about C systems code requires a memory model that is able to capture the semantics of C pointers and types. At the same time, proof-based verification demands abstraction, in particular from the aliasing and frame problems. In this thesis, we study the mechanisation of a series of models, from semantic to separation logic, for achieving this abstraction when performing interactive theorem-prover based verification of C systems code in higher- order logic. We do not commit common oversimplifications, but correctly deal with C's model of programming language values and the heap, while developing the ability to reason abstractly and efficiently. We validate our work by demonstrating that the models are applicable to real, security- and safety-critical code by formally verifying the memory allocator of the L4 microkernel. All formalisations and proofs have been developed and machine-checked in the Isabelle/HOL theorem prover.
23
Jedryszek, Jakub. "A model-driven development and verification approach for medical devices." Thesis, Kansas State University, 2014. http://hdl.handle.net/2097/18222.
Full textAbstract:
Master of ScienceDepartment of Computing and Information Sciences
John Hatcliff
Medical devices are safety-critical systems whose failure may put human life in danger. They are becoming more advanced and thus more complex. This leads to bigger and more complicated code-bases that are hard to maintain and verify. Model-driven development provides high-level and abstract description of the system in the form of models that omit details, which are not relevant during the design phase. This allows for certain types of verification and hazard analysis to be performed on the models. These models can then be translated into code. However, errors that do not exist in the models may be introduced during the implementation phase. Automated translation from verified models to code may prevent to some extent. This thesis proposes approach for model-driven development and verification of medical devices. Models are created in AADL (Architecture Analysis & Design Language), a language for software and hardware architecture modeling. AADL models are translated to SPARK Ada, contract-based programming language, which is suitable for software verification. Generated code base is further extended by developers to implement internals of specific devices. Created programs can be verified using SPARK tools. A PCA (Patient Controlled Analgesia) pump medical device is used to illustrate the primary artifacts and process steps. The foundation for this work is "Integrated Clinical Environment Patient-Controlled Analgesia Infusion Pump System Requirements" document and AADL Models created by Brian Larson. In addition to proposed model-driven development approach, a PCA pump prototype was created using the BeagleBoard-xM device as a platform. Some components of PCA pump prototype were verified by SPARK tools and Bakar Kiasan.
24
Neumann, Stefan, and Holger Giese. "Scalable compatibility for embedded real-time components via language progressive timed automata." Universität Potsdam, 2013. http://opus.kobv.de/ubp/volltexte/2013/6385/.
Full textAbstract:
The proper composition of independently developed components of an embedded real- time system is complicated due to the fact that besides the functional behavior also the non-functional properties and in particular the timing have to be compatible. Nowadays related compatibility problems have to be addressed in a cumbersome integration and configuration phase at the end of the development process, that in the worst case may fail. Therefore, a number of formal approaches have been developed, which try to guide the upfront decomposition of the embedded real-time system into components such that integration problems related to timing properties can be excluded and that suitable configurations can be found. However, the proposed solutions require a number of strong assumptions that can be hardly fulfilled or the required analysis does not scale well. In this paper, we present an approach based on timed automata that can provide the required guarantees for the later integration without strong assumptions, which are difficult to match in practice. The approach provides a modular reasoning scheme that permits to establish the required guarantees for the integration employing only local checks, which therefore also scales. It is also possible to determine potential configuration settings by means of timed game synthesis.Die korrekte Komposition individuell entwickelter Komponenten von eingebetteten Realzeitsystemen ist eine Herausforderung, da neben funktionalen Eigenschaften auch nicht funktionale Eigenschaften berücksichtigt werden müssen. Ein Beispiel hierfür ist die Kompatibilität von Realzeiteigenschaften, welche eine entscheidende Rolle in eingebetteten Systemen spielen. Heutzutage wird die Kompatibilität derartiger Eigenschaften in einer aufwändigen Integrations- und Konfigurationstests am Ende des Entwicklungsprozesses geprüft, wobei diese Tests im schlechtesten Fall fehlschlagen. Aus diesem Grund wurde eine Zahl an formalen Verfahren Entwickelt, welche eine frühzeitige Analyse von Realzeiteigenschaften von Komponenten erlauben, sodass Inkompatibilitäten von Realzeiteigenschaften in späteren Phasen ausgeschlossen werden können. Existierenden Verfahren verlangen jedoch, dass eine Reihe von Bedingungen erfüllt sein muss, welche von realen Systemen nur schwer zu erfüllen sind, oder aber, die verwendeten Analyseverfahren skalieren nicht für größere Systeme. In dieser Arbeit wird ein Ansatz vorgestellt, welcher auf dem formalen Modell des Timed Automaton basiert und der keine Bedingungen verlangt, die von einem realen System nur schwer erfüllt werden können. Der in dieser Arbeit vorgestellte Ansatz enthält ein Framework, welches eine modulare Analyse erlaubt, bei der ausschließlich miteinender kommunizierende Komponenten paarweise überprüft werden müssen. Somit wird eine skalierbare Analyse von Realzeiteigenschaften ermöglicht, die keine Bedingungen verlangt, welche nur bedingt von realen Systemen erfüllt werden können.
25
Thiagarajan, Hariharan. "Dependence analysis for inferring information flow properties in Spark ADA programs." Thesis, Kansas State University, 2011. http://hdl.handle.net/2097/13187.
Full textAbstract:
Master of ScienceDepartment of Computing and Information Sciences
John Hatcliff
With the increase in development of safety and security critical systems, it is important to have more sophisticated methods for engineering such systems. It can be difficult to understand and verify critical properties of these systems because of their ever growing size and complexity. Even a small error in a complex system may result in casualty or significant monetary loss. Consequently, there is a rise in the demand for scalable and accurate techniques to enable faster development and verification of high assurance systems. This thesis focuses on discovering dependencies between various parts of a system and leveraging that knowledge to infer information flow properties and to verify security policies specified for the system. The primary contribution of this thesis is a technique to build dependence graphs for languages which feature abstraction and refinement. Inter-procedural slicing and inter-procedural chopping are the techniques used to analyze the properties of the system statically. The approach outlined in this thesis provides a domain-specific language to query the information flow properties and to specify security policies for a critical system. The spec- ified policies can then be verified using existing static analysis techniques. All the above contributions are integrated with a development environment used to develop the critical system. The resulting software development tool helps programmers develop, infer, and verify safety and security systems in a single unified environment.
26
Carman, Benjamin Andrew. "Translating LaTeX to Coq: A Recurrent Neural Network Approach to Formalizing Natural Language Proofs." Ohio University Honors Tutorial College / OhioLINK, 2021. http://rave.ohiolink.edu/etdc/view?acc_num=ouhonors161919616626269.
Full text
27
Decker, Gero. "Design and analysis of process choreographies." Phd thesis, Universität Potsdam, 2009. http://opus.kobv.de/ubp/volltexte/2010/4076/.
Full textAbstract:
With the rise of electronic integration between organizations, the need for a precise specification of interaction behavior increases. Information systems, replacing interaction previously carried out by humans via phone, faxes and emails, require a precise specification for handling all possible situations. Such interaction behavior is described in process choreographies. Choreographies enumerate the roles involved, the allowed interactions, the message contents and the behavioral dependencies between interactions. Choreographies serve as interaction contract and are the starting point for adapting existing business processes and systems or for implementing new software components.
As a thorough analysis and comparison of choreography modeling languages is missing in the literature, this thesis introduces a requirements framework for choreography languages and uses it for comparing current choreography languages. Language proposals for overcoming the limitations are given for choreography modeling on the conceptual and on the technical level.
Using an interconnection modeling style, behavioral dependencies are defined on a per-role basis and different roles are interconnected using message flow. This thesis reveals a number of modeling "anti-patterns" for interconnection modeling, motivating further investigations on choreography languages following the interaction modeling style. Here, interactions are seen as atomic building blocks and the behavioral dependencies between them are defined globally. Two novel language proposals are put forward for this modeling style which have already influenced industrial standardization initiatives.
While avoiding many of the pitfalls of interconnection modeling, new anomalies can arise in interaction models. A choreography might not be realizable, i.e. there does not exist a set of interacting roles that collectively realize the specified behavior. This thesis investigates different dimensions of realizability.Elektronische Integration zwischen Organisationen erfordert eine präzise Spezifikation des Interaktionsverhaltens: Informationssysteme, die Kommunikation per Telefon, Fax und Email ablösen, können nicht so flexibel und selbständig auf Ausnahmesituationen reagieren wie Menschen. Choreographien ermöglichen es, Interaktionsverhalten genau zu spezifizieren. Diese Modelle zählen die beteiligten Rollen, die erlaubten Interaktionen, Nachrichteninhalte und Verhaltensabhängigkeiten auf und dienen somit als Interaktionsvertrag zwischen den Organisationen. Auch als Ausgangspunkt für eine Anpassung existierender Prozesse und Systeme sowie für die Implementierung neuer Softwarekomponenten finden Choreographien Anwendung. Da ein Vergleich von Choreographiemodellierungssprachen in der Literatur bislang fehlt, präsentiert diese Arbeit einen Anforderungskatalog, der als Basis für eine Evaluierung existierender Sprachen angewandt wird. Im Kern führt diese Arbeit Spracherweiterungen ein, um die Schwächen existierender Sprachen zu überwinden. Die vorgestellten Erweiterungen adressieren dabei Modellierung auf konzeptioneller und auf technischer Ebene. Beim Verlinkungsmodellierungsstil werden Verhaltensabhängigkeiten innerhalb der beteiligten Rollen spezifiziert und das Interaktionsverhalten entsteht durch eine Verlinkung der Kommunikationsaktivitäten. Diese Arbeit stellt einige "Anti-Pattern" für die Verlinkungsmodellierung vor, welche wiederum Untersuchungen bzgl. Choreographiesprachen des Interaktionsmodellierungsstils motivieren. Hier werden Interaktionen als atomare Blöcke verstanden und Verhaltensabhängigkeiten werden global definiert. Diese Arbeit führt zwei neue Choreographiesprachen dieses zweiten Modellierungsstils ein, welche bereits in industrielle Standardisierungsinitiativen eingeflossen sind. Während auf der einen Seite zahlreiche Fallstricke der Verlinkungsmodellierung umgangen werden, können in Interaktionsmodellen allerdings neue Anomalien entstehen. Eine Choreographie kann z.B. "unrealisierbar" sein, d.h. es ist nicht möglich interagierende Rollen zu finden, die zusammen genommen das spezifizierte Verhalten abbilden. Dieses Phänomen wird in dieser Arbeit über verschiedene Dimensionen von Realisierbarkeit untersucht.
28
Istoan, Paul. "Methodology for the derivation of product behaviour in a Software Product Line." Phd thesis, Université Rennes 1, 2013. http://tel.archives-ouvertes.fr/tel-00925479.
Full textAbstract:
The major problem addressed in this thesis is the definition of a new SPLE methodology that covers both phases of the SPLE process and focuses on the derivation of behavioral models of SPL products. In Chapter 2 three research areas scope context of this thesis: Software Product Lines, Business Processes, and Model-Driven Engineering. Throughout Chapter 3, we propose a new SPLE methodology that focuses on the derivation of product behavior. We first describe the main flow of the methodology, and then detail the individual steps. In chapter 4 we propose a new domain specific language called CBPF created for modeling composable business process fragments. A model driven approach is followed for creating CBPF: definition of the abstract syntax, graphical concrete syntax and translational semantics. In Chapter 5 we propose several types of verifications that can be applied to business processfragments to determine their "correctness". For structural verification we definine a set of fragment consistency rules that should be valid for every business process fragment created with CBPF. To check behavioral correctness we first transform the business process fragment into an equivalent HCPN. We can then check generic properties but also define aset of fragment specific properties. In chapter 6 we exemplify the proposed SPL methodology by applying it to a case study from the crisis management system domain. We also propose a tool suite that supports our methodology. Chapter 7 describes possible improvements and extensions to the contributions of this thesis. We conclude the thesis in Chapter 8 and draw some conclusions.
29
Kaplan, Simon Mark. "Specification and verification of context conditions for programming languages." Doctoral thesis, University of Cape Town, 1986. http://hdl.handle.net/11427/15898.
Full textAbstract:
Bibliography: p. 204-211.Context conditions - also called static semantics - are the constraints on computer programs that cannot be reasonably expressed by a context-free grammar, but that can be statically checked without considering the execution properties - semantics - of the program. Such conditions tend to be arbitrary and complex. This thesis presents a new specification formalism called CFF/AML. This formalism is · designed to be both useful for the specification of programming languages to an environment generator and also simple to use. The driving insight behind CFF/AML is that a language specifier conceives of the context condition checks associated with a programming language syntax description in procedural terms. CFF/AML supports this view of context condition specification, thus simplifying the task of the language specifier. CFF/AML has been formally by constructing a temporal proof system for the metalanguage. This proof system can also be used to verify CFF/AML specifications. The construction of the temporal proof system for CFF/AML uncovered a deficiency in the existing theory, namely that there was no way to prove subprograms, especially recursive subprograms, correct. The theory was extended to handle recursive subprograms. The approach developed in this thesis allows recursive subprograms to be proven correct using the same approach as was used previously for iterative constructs. This thesis makes a number of contributions to Computer Science. An approach to language specification - CFF/AML - is developed that greatly reduces the problems associated with building a language specification for input to a programming language environment generator. The theory of temporal proof systems is extended to include a methodology for handling proofs of recursive subprograms. A formal description of the CFF/AML metalanguage has been developed using temporal logic as the framework for the description. This is the first attempt to use temporal logic for such a task. As CFF/AML constructs can be dynamically scoped, this development differs from that required for statically scoped languages. We have also used this temporal proof system formally to prove that context condition specifications are correct. These proofs are an advancement on earlier work in the field of formal reasoning about context condition specification as they allow formal proof of the correctness of evaluations, as well as proving termination.
30
Zhou, Yichao. "Lip password-based speaker verification system with unknown language alphabet." HKBU Institutional Repository, 2018. https://repository.hkbu.edu.hk/etd_oa/562.
Full textAbstract:
The traditional security systems that verify the identity of users based on password usually face the risk of leaking the password contents. To solve this problem, biometrics such as the face, iris, and fingerprint, begin to be widely used in verifying the identity of people. However, these biometrics cannot be changed if the database is hacked. What's more, verification systems based on the traditional biometrics might be cheated by fake fingerprint or the photo.;Liu and Cheung (Liu and Cheung 2014) have recently initiated the concept of lip password, which is composed of a password embedded in the lip movement and the underlying characteristics of lip motion [26]. Subsequently, a lip password-based system for visual speaker verification has been developed. Such a system is able to detect a target speaker saying the wrong password or an impostor who knows the correct password. That is, only a target user speaking correct password can be accepted by the system. Nevertheless, it recognizes the lip password based on a lip-reading algorithm, which needs to know the language alphabet of the password in advance, which may limit its applications.;To tackle this problem, in this thesis, we study the lip password-based visual speaker verification system with unknown language alphabet. First, we propose a method to verify the lip password based on the key frames of lip movement instead of recognizing the individual password elements, such that the lip password verification process can be made without knowing the password alphabet beforehand. To detect these key frames, we extract the lip contours and detect the interest intervals where the lip contours have significant variations. Moreover, in order to avoid accurate alignment of feature sequences or detection on mouth status which is computationally expensive, we design a novel overlapping subsequence matching approach to encode the information in lip passwords in the system. This technique works by sampling the feature sequences extracted from lip videos into overlapping subsequences and matching them individually. All the log-likelihood of each subsequence form the final feature of the sequence and are verified by the Euclidean distance to positive sample centers. We evaluate the proposed two methods on a database that contains totally 8 kinds of lip passwords including English digits and Chinese phrases. Experimental results show the superiority of the proposed methods for visual speaker verification.;Next, we propose a novel visual speaker verification approach based on diagonal-like pooling and pyramid structure of lips. We take advantage of the diagonal structure of sparse representation to preserve the temporal order of lip sequences by employ a diagonal-like mask in pooling stage and build a pyramid spatiotemporal features containing the structural characteristic under lip password. This approach eliminates the requirement of segmenting the lip-password into words or visemes. Consequently, the lip password with any language can be used for visual speaker verification. Experiments show the efficacy of the proposed approach compared with the state-of-the-art ones.;Additionally, to further evaluate the system, we also develop a prototype of the lip password-based visual speaker verification. The prototype has a Graphical User Interface (GUI) that make users easy to access.
31
Gerber, Erick D. B. "A model checker for the LF system." Thesis, Stellenbosch : Stellenbosch University, 2007. http://hdl.handle.net/10019.1/19597.
Full textAbstract:
Thesis (MSc)--University of Stellenbosch, 2007.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.
32
Pasupuleti, Venkata Sai Manoj. "Probabilistic approaches for verification of unlikely inserted errors in Hardware Description Languages." The Ohio State University, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=osu1452182260.
Full text
33
Matthews, John Robert. "Algebraic specification and verification of processor microarchitectures /." Full text open access at:, 2000. http://content.ohsu.edu/u?/etd,212.
Full text
34
Bronish, Derek. "Abstraction as the Key to Programming, with Issues for Software Verification in Functional Languages." The Ohio State University, 2012. http://rave.ohiolink.edu/etdc/view?acc_num=osu1338317549.
Full text
35
Nilsson, Daniel. "System for firmware verification." Thesis, University of Kalmar, School of Communication and Design, 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:hik:diva-2372.
Full textAbstract:
Software verification is an important part of software development and themost practical way to do this today is through dynamic testing. This reportexplains concepts connected to verification and testing and also presents thetesting-framework Trassel developed during the writing of this report.Constructing domain specific languages and tools by using an existinglanguage as a starting ground can be a good strategy for solving certainproblems, this was tried with Trassel where the description-language forwriting test-cases was written as a DSL using Python as the host-language.
36
Might, Matthew Brendon. "Environment Analysis of Higher-Order Languages." Diss., Georgia Institute of Technology, 2007. http://hdl.handle.net/1853/16289.
Full textAbstract:
Any analysis of higher-order languages must grapple with the
tri-facetted nature of lambda. In one construct, the fundamental
control, environment and data structures of a language meet and
intertwine. With the control facet tamed nearly two decades ago, this
work brings the environment facet to heel, defining the environment
problem and developing its solution: environment analysis. Environment
analysis allows a compiler to reason about the equivalence of
environments, i.e., name-to-value mappings, that arise during a
program's execution. In this dissertation, two different
techniques-abstract counting and abstract frame strings-make this
possible. A third technique, abstract garbage collection, makes both
of these techniques more precise and, counter to intuition, often
faster as well. An array of optimizations and even deeper analyses
which depend upon environment analysis provide motivation for this
work.
In an abstract interpretation, a single abstract entity represents a
set of concrete entities. When the entities under scrutiny are
bindings-single name-to-value mappings, the atoms of environment-then
determining when the equality of two abstract bindings infers the
equality of their concrete counterparts is the crux of environment
analysis. Abstract counting does this by tracking the size of
represented sets, looking for singletons, in order to apply the
following principle:
If {x} = {y}, then x = y.
Abstract frame strings enable environmental reasoning by statically
tracking the possible stack change between the births of two
environments; when this change is effectively empty, the environments
are equivalent. Abstract garbage collection improves precision by
intermittently removing unreachable environment structure during
abstract interpretation.
37
Huffman, Brian Charles. "HOLCF '11: A Definitional Domain Theory for Verifying Functional Programs." PDXScholar, 2011. https://pdxscholar.library.pdx.edu/open_access_etds/113.
Full textAbstract:
HOLCF is an interactive theorem proving system that uses the mathematics of domain theory to reason about programs written in functional programming languages. This thesis introduces HOLCF '11, a thoroughly revised and extended version of HOLCF that advances the state of the art in program verification: HOLCF '11 can reason about many program definitions that are beyond the scope of other formal proof tools, while providing a high degree of proof automation. The soundness of the system is ensured by adhering to a definitional approach: New constants and types are defined in terms of previous concepts, without introducing new axioms. Major features of HOLCF '11 include two high-level definition packages: the Fixrec package for defining recursive functions, and the Domain package for defining recursive datatypes. Each of these uses the domain-theoretic concept of least fixed points to translate user-supplied recursive specifications into safe low-level definitions. Together, these tools make it easy for users to translate a wide variety of functional programs into the formalism of HOLCF. Theorems generated by the tools also make it easy for users to reason about their programs, with a very high level of confidence in the soundness of the results. As a case study, we present a fully mechanized verification of a model of concurrency based on powerdomains. The formalization depends on many features unique to HOLCF '11, and is the first verification of such a model in a formal proof tool.
38
Schwoon, Stefan. "Efficient verification of sequential and concurrent systems." Habilitation à diriger des recherches, École normale supérieure de Cachan - ENS Cachan, 2013. http://tel.archives-ouvertes.fr/tel-00927066.
Full textAbstract:
Formal methods provide means for rigorously specifying the desired behaviour of a hardware or software system, making a precise model of its actual behaviour, and then verifying whether that actual behaviour corresponds to the specification.My habiliation thesis reports on various contributions to this realm, where my main interest has been on algorithmic aspects. This is motivated by the observation that asymptotic worst-case complexity, often used to characterize the difficulty of algorithmic problems, is only loosely related to the difficulty encountered in solving those problems in practice.
The two main types of system I have been working on are pushdown systems and Petri nets. Both are fundamental notions of computation, and both offer, in my opinion, particularly nice opportunities for combining theory and algorithmics.
Pushdown systems are finite automata equipped with a stack; since the height of the stack is not bounded, they represent a class of infinite-state systems that model programs with (recursive) procedure calls. Moreover, we shall see that specifying authorizations is another, particularly interesting application of pushdown systems.
While pushdown systems are primarily suited to express sequential systems, Petri nets model concurrent systems. My contributions in this area all concern unfoldings. In a nutshell, the unfolding of a net N is an acyclic version of N in which loops have been unrolled. Certain verification problems, such as reachability, have a lower complexity on unfoldings than on general Petri nets.
39
Stainer, Amélie. "Contribution à la vérification d'automates temporisés : déterminisation, vérification quantitative et accessibilité dans les réseaux d'automates." Thesis, Rennes 1, 2013. http://www.theses.fr/2013REN1S167/document.
Full textAbstract:
Cette thèse porte sur la vérification des automates temporisés, un modèle bien établi pour les systèmes temps-réels. La thèse est constituée de trois parties. La première est dédiée à la déterminisation des automates temporisés, problème qui n'a pas de solution en général. Nous proposons une méthode approchée (sur-approximation, sous-approximation, mélange des deux) fondée sur la construction d'un jeu de sûreté. Cette méthode améliore les approches existantes en combinant leurs avantages respectifs. Nous appliquons ensuite cette méthode de déterminisation à la génération automatique de tests de conformité. Dans la seconde partie, nous prenons en compte des aspects quantitatifs des systèmes temps-réel grâce à une notion de fréquence des états acceptants dans une exécution d'un automate temporisé. Plus précisément, la fréquence d'une exécution est la proportion de temps passée dans les états acceptants. Nous intéressons alors à l'ensemble des fréquences des exécutions d'un automate temporisé pour étudier, par exemple, le vide de langages seuils. Nous montrons ainsi que les bornes de l'ensemble des fréquences sont calculables pour deux classes d'automates temporisés. D'une part, les bornes peuvent être calculées en espace logarithmique par une procédure non-déterministe dans les automates temporisés à une horloge. D'autre part, elles peuvent être calculées en espace polynomial dans les automates temporisés à plusieurs horloges ne contenant pas de cycles forçant la convergence d'horloges. Finalement, nous étudions le problème de l'accessibilité des états acceptants dans des réseaux d'automates temporisés qui communiquent via des files FIFO. Nous considérons tout d'abord des automates temporisés à temps discret, et caractérisons les topologies de réseaux pour lesquelles l'accessibilité est décidable. Cette caractérisation est ensuite étendue aux automates temporisés à temps continuThis thesis is about verification of timed automata, a well-established model for real time systems. The document is structured in three parts. The first part is dedicated to the determinization of timed automata, a problem which has no solution in general. We propose an approximate (over-approximation/under-approximation/mix) method based on the construction of a safety game. This method improves both existing approaches by combining their respective advantages. Then, we apply this determinization approach to the generation of conformance tests. In the second part, we take into account quantitative aspects of real time systems thanks to a notion of frequency of accepting states along executions of timed automata. More precisely, the frequency of a run is the proportion of time elapsed in accepting states. Then, we study the set of frequencies of runs of a timed automaton in order to decide, for example, the emptiness of threshold languages. We thus prove that the bounds of the set of frequencies are computable for two classes of timed automata. On the one hand, we prove that bounds are computable in logarithmic space by a non-deterministic procedure in one-clock timed automata. On the other hand, they can be computed in polynomial space in timed automata with several clocks, but having no cycle that forces the convergence between clocks. Finally, we study the reachability problem in networks of timed automata communicating through FIFO channels. We first consider dicrete timed automata, and characterize topologies of networks for which reachability is decidable. Then, this characterization is extended to dense-time automata
40
Yang, Zhenkun. "Scalable Equivalence Checking for Behavioral Synthesis." PDXScholar, 2015. https://pdxscholar.library.pdx.edu/open_access_etds/2461.
Full textAbstract:
Behavioral synthesis is the process of compiling an Electronic System Level (ESL) design to a register-transfer level (RTL) implementation. ESL specifications define the design functionality at a high level of abstraction (e.g., with C/C++ or SystemC), and thus provide a promising approach to address the exacting demands to develop feature-rich, optimized, and complex hardware systems within aggressive time-to-market schedules. Behavioral synthesis entails application of complex and error-prone transformations during the compilation process. Therefore, the adoption of behavioral synthesis highly depends on our ability to ensure that the synthesized RTL conforms to the ESL description. This dissertation provides an end-to-end scalable equivalence checking support for behavioral synthesis. The major challenge of this research is to bridge the huge semantic gap between the ESL and RTL descriptions, which makes the direct comparison of designs in ESL and RTL difficult. Moreover, a large number and a wide variety of aggressive transformations from front-end to back-end require an end-to-end scalable checking framework.
This dissertation provides an end-to-end scalable equivalence checking support for behavioral synthesis. The major challenge of this research is to bridge the huge semantic gap between the ESL and RTL descriptions, which makes the direct comparison of designs in ESL and RTL difficult. Moreover, a large number and a wide variety of aggressive transformations from front-end to back-end require an end-to-end scalable checking framework.
A behavioral synthesis flow can be divided into three major phases, including 1) front-end : compiler transformations, 2) scheduling: assigning each operation a clock cycle and satisfying the user-specified constraints, and 3) back-end : local optimizations and RTL generation. In our end-to-end and incremental equivalence checking framework, we check each of the three phases one by one. Firstly, we check the front-end that consists of a sequence of compiler transformations by decomposing it into a series of checks, one for each transformation applied. We symbolically explore paths in the input and output programs of each transformation, and check whether the input and output programs have the same observable behavior under the same path condition. Secondly, we validate the scheduling transformation by checking the preservation of control and data dependencies, and the preservation of I/O timing in the user-specified scheduling mode. Thirdly, we symbolically simulate the scheduled design and the generated RTL cycle by cycle, and check the equivalence of each mapped variables. We also develop several key optimizations to make our back-end checker scale to real industrial-strength designs. In addition to the equivalence checking framework, we also present an approach to detecting deadlocks introduced by parallelization of RTL blocks that are connected by synthesized interfaces with handshaking protocols.
To demonstrate the efficiency and scalability of our framework, we evaluated it on transformations applied by a behavioral synthesis tool to designs from the C-based CHStone and SystemC-based S2CBench benchmarks. Based on the evaluation results, our front-end checker can efficiently validate more than 75 percent of the total of 1008 compiler transformations applied to designs from the CHStone benchmark, taking an average time of 1.5 seconds per transformation. Our scheduling checker can validate control-data dependencies and I/O timing of all designs from S2CBench benchmark. Our back-end checker can handle designs with more than 32K lines of synthesized RTL from the CHStone benchmark, which demonstrates the scalability of the checker. Furthermore, our checker found several bugs in a commercial tool, underlining both the importance of formal equivalence checking and the effectiveness of our approach.
41
Vroon, Daron. "Automatically Proving the Termination of Functional Programs." Diss., Georgia Institute of Technology, 2007. http://hdl.handle.net/1853/19734.
Full textAbstract:
Establishing the termination of programs is a fundamental problem in the field of software verification. For transformational programs, termination is used to extend partial correctness to total correctness. For reactive systems, termination reasoning is used to establish liveness properties. In the context of theorem proving, termination is used to establish the consistency of definitional axioms and to automate proofs by induction. Of course, termination is an undecidable problem, as Turing himself proved. However, the question remains: how automatic can a general termination analysis be in practice?
In this dissertation, we develop two new general frameworks for reasoning about termination and demonstrate their effectiveness in automating the task of proving termination in the domain of applicative first-order functional languages.
The foundation of the first framework is the development of the first known complete set of algorithms for ordinal arithmetic over an ordinal notation. We provide algorithms for ordinal ordering ($<$), addition, subtraction, multiplication, and exponentiation on the ordinals up to epsilon-naught. We prove correctness and complexity results for each algorithm. We also create a library for automating arithmetic reasoning over epsilon-naught in the ACL2 theorem proving system. This ordinal library enables new termination proofs that were previously not possible in previous versions of ACL2.
The foundation of the second framework is an algorithm for fully automating termination reasoning with no user assistance. This algorithm uses a combination of theorem proving and static analysis to create a Calling Context Graph (CCG), a novel abstraction that captures the looping behavior of the program. Calling Context Measures (CCMs) are then used to prove that no infinite path through the CCG can be an actual computation of the program. We implement this algorithm in the ACL2, and empirically evaluate its effectiveness on the regression suite, a collection of over 11,000 user-defined functions from a wide variety of applications.
42
Atzemoglou, George Philip. "Higher-order semantics for quantum programming languages with classical control." Thesis, University of Oxford, 2012. http://ora.ox.ac.uk/objects/uuid:9fdc4a26-cce3-48ed-bbab-d54c4917688f.
Full textAbstract:
This thesis studies the categorical formalisation of quantum computing, through the prism of type theory, in a three-tier process. The first stage of our investigation involves the creation of the dagger lambda calculus, a lambda calculus for dagger compact categories. Our second contribution lifts the expressive power of the dagger lambda calculus, to that of a quantum programming language, by adding classical control in the form of complementary classical structures and dualisers. Finally, our third contribution demonstrates how our lambda calculus can be applied to various well known problems in quantum computation: Quantum Key Distribution, the quantum Fourier transform, and the teleportation protocol.
43
King, Christopher T. "An axiomatic semantics for functional reactive programming." Worcester, Mass. : Worcester Polytechnic Institute, 2008. http://www.wpi.edu/Pubs/ETD/Available/etd-042908-133033/.
Full text
44
Hugot, Vincent. "Tree automata, approximations, and constraints for verification : Tree (Not quite) regular model-checking." Phd thesis, Université de Franche-Comté, 2013. http://tel.archives-ouvertes.fr/tel-00909608.
Full textAbstract:
Tree automata, and their applications to verification from the common thread of this thesis In the first part, we definie a complete model-cheking framework.[...] The second part focus on an important aspect of the automata involved: constraints.[...] Finaly, we also study the very different variety of tree-walking automata which have tight connections with navigational languages on semi-structured documents.
45
Khatchadourian, Raffi Takvor. "Techniques for Automated Software Evolution." The Ohio State University, 2011. http://rave.ohiolink.edu/etdc/view?acc_num=osu1304885155.
Full text
46
Rodríguez, César. "Verification based on unfoldings of Petri nets with read arcs." Phd thesis, École normale supérieure de Cachan - ENS Cachan, 2013. http://tel.archives-ouvertes.fr/tel-00927064.
Full textAbstract:
Humans make mistakes, especially when faced to complex tasks, such as the construction of modern hardware or software. This thesis focuses on machine-assisted techniques to guarantee that computers behave correctly. Modern computer systems are large and complex. Automated formal verification stands as an alternative to testing or simulation to ensuring their reliability. It essentially proposes to employ computers to exhaustively check the system behavior. Unfortunately, automated verification suffers from the state-space explosion problem: even relatively small systems can reach a huge number of states. Using the right representation for the system behavior seems to be a key step to tackle the inherent complexity of the problems that automated verification solves. The verification of concurrent systems poses additional issues, as their analysis requires to evaluate, conceptually, all possible execution orders of their concurrent actions. Petri net unfoldings are a well-established verification technique for concurrent systems. They represent behavior by partial orders, which not only is natural but also efficient for automatic verification. This dissertation focuses on the verification of concurrent systems, employing Petri nets to formalize them, and studies two prominent verification techniques: model checking and fault diagnosis. We investigate the unfoldings of Petri nets extended with read arcs. The unfoldings of these so-called contextual nets seem to be a better representation for systems exhibiting concurrent read access to shared resources: they can be exponentially smaller than conventional unfoldings on these cases. Theoretical and practical contributions are made. We first study the construction of contextual unfoldings, introducing algorithms and data structures that enable their efficient computation. We integrate contextual unfoldings with merged processes, another representation of concurrent behavior that alleviates the explosion caused by non-determinism. The resulting structure, called contextual merged processes, is often orders of magnitude smaller than unfoldings, as we experimentally demonstrate. Next, we develop verification techniques based on unfoldings. We define SAT encodings for the reachability problem in contextual unfoldings, thus solving the problem of detecting cycles of asymmetric conflict. Also, an unfolding-based decision procedure for fault diagnosis under fairness constraints is presented, in this case only for conventional unfoldings. Finally, we implement our verification algorithms, aiming at producing a competitive model checker intended to handle realistic benchmarks. We subsequently evaluate our methods over a standard set of benchmarks and compare them with existing unfolding-based techniques. The experiments demonstrate that reachability checking based on contextual unfoldings outperforms existing techniques on a wide number of cases. This suggests that contextual unfoldings, and asymmetric event structures in general, have a rightful place in research on concurrency, also from an efficiency point of view.
47
Ngô, Van Chan. "Formal verification of a synchronous data-flow compiler : from Signal to C." Phd thesis, Université Rennes 1, 2014. http://tel.archives-ouvertes.fr/tel-01067477.
Full textAbstract:
Synchronous languages such as Signal, Lustre and Esterel are dedicated to designing safety-critical systems. Their compilers are large and complicated programs that may be incorrect in some contexts, which might produce silently bad compiled code when compiling source programs. The bad compiled code can invalidate the safety properties that are guaranteed on the source programs by applying formal methods. Adopting the translation validation approach, this thesis aims at formally proving the correctness of the highly optimizing and industrial Signal compiler. The correctness proof represents both source program and compiled code in a common semantic framework, then formalizes a relation between the source program and its compiled code to express that the semantics of the source program are preserved in the compiled code.
48
Vassiliev, Pavel. "Développement et réalisation d'un simulateur de machines à états abstraits temps-réel et model-checking de formules d'une logique des prédicats temporisée du premier ordre." Phd thesis, Université Paris-Est, 2008. http://tel.archives-ouvertes.fr/tel-00462013.
Full textAbstract:
Dans cette thèse nous proposons un modèle temporel dans le cadre des machines à états abstraits (ASM). Une extension du langage de spécification ASM est développé qui correspond à ce modéle temporel pour le temps continu. L'extension du langage avec des constructions de temps permet de diminuer la taille de la spécification et donc de réduire la probabilité d'erreurs. La sémantique de l'extension du langage ASM est fournie et prend en compte les définitions des fonctions externes, les valeurs des délais et les choix de résolution des non-déterminismes. Un sous-système de vérification des propriétés exprimées en logique FOTL (FirstOrder Timed Logic) est développé. Un simulateur d'ASMs temporisées est développé et implémenté, il comprend un analyseur syntaxique, un interprète du langage, un sous-système de vérification des propriétés ainsi qu'une interface graphique
49
Jacquemard, Florent. "Modèles d'automates d'arbres étendus pour la vérification de systèmes infinis." Habilitation à diriger des recherches, École normale supérieure de Cachan - ENS Cachan, 2011. http://tel.archives-ouvertes.fr/tel-00643595.
Full textAbstract:
Ce document présente l'étude de plusieurs modèles de machines à états finis qui étendent tous le même formalisme: les automates d'arbres classiques, et leur application dans différentes tâches telles que l'analyse statique de programmes ou de systèmes, la typage, la vérification de la cohérence de spécifications, le model checking... Les arbres sont une structure naturelle de données, très répandue en informatique, par exemple pour la représentation des structures de données hiérarchiques ou imbriquées, pour des algorithmes spécifiques (arbres binaires de recherche, algorithmes distribués), comme modèle abstrait pour des données semi-structurées utilisées pour l'échange d'information dans le Web, pour une présentation algébrique de processus récursifs, comme les termes en logique... Lorsqu'il s'agit de raisonner sur des systèmes manipulant des arbres, ou modelisés par des arbres, il est crucial d'avoir une représentation finie d'ensembles infinis d'arbres. Les automates d'arbres sont des machines à états finis permettant une telle représentation. Ils ont fait la preuve de leur adéquation à des tâches de raisonnement: ils ont un modèle théorique bien établi, en étroite relation avec la logique, ils bénéficient de bonnes propriétés de composition et d'algorithmes de décision efficaces. En particulier, les automates d'arbres sont utilisées au coeur de systèmes de vérification formelle d'outils de déduction automatique. Toutefois, les automates d'arbres ont des limitations sévères en expressivité. Par exemple, ils sont incapables de faire du filtrage non-linéaire ou d'exprimer des contraintes d'intégrité tels que les clés dans les bases de données. Certaines extensions ont été proposées afin d'améliorer le modèle en essayant de conserver de bonnes propriétés. Nous présentons dans ce document de plusieurs de telles extensions, leurs propriétés et leur utilisation en vérification symbolique de systèmes et de programmes.
50
Tesson, Julien. "Environnement pour le développement et la preuve de correction systèmatiques de programmes parallèles fonctionnels." Phd thesis, Université d'Orléans, 2011. http://tel.archives-ouvertes.fr/tel-00660554.
Full textAbstract:
Concevoir et implanter des programmes parallèles est une tâche complexe, sujette aux erreurs. La vérification des programmes parallèles est également plus difficile que celle des programmes séquentiels. Pour permettre le développement et la preuve de correction de programmes parallèles, nous proposons de combiner le langage parallèle fonctionnel quasi-synchrone BSML, les squelettes algorithmiques - qui sont des fonctions d'ordre supérieur sur des structures de données réparties offrant une abstraction du parallélisme - et l'assistant de preuve Coq, dont le langage de spécification est suffisamment riche pour écrire des programmes fonctionnels purs et leurs propriétés. Nous proposons un plongement des primitives BSML dans la logique de Coq sous une forme modulaire adaptée à l'extraction de programmes. Ainsi, nous pouvons écrire dans Coq des programmes BSML, raisonner dessus, puis les extraire et les exécuter en parallèle. Pour faciliter le raisonnement sur ceux-ci, nous formalisons le lien entre programmes parallèles, manipulant des structures de données distribuées, et les spécifications, manipulant des structures séquentielles. Nous prouvons ainsi la correction d'une implantation du squelette algorithmique BH, un squelette adapté au traitement de listes réparties dans le modèle de parallélisme quasi synchrone. Pour un ensemble d'applications partant d'une spécification d'un problème sous forme d'un programme séquentiel simple, nous dérivons une instance de nos squelettes, puis nous extrayons un programme BSML avant de l'exécuter sur des machines parallèles.