223 research outputs found
Interactive and Automated Proofs in Modal Separation Logic (Invited Talk)
No full textIn program verification, it is common to embed a high-level object logic into the meta logic of a proof assistant to hide low-level aspects of the verification. To verify imperative and concurrent programs, separation logic hides explicit reasoning about heaps and pointer disjointness. To verify programs with cyclic features such as modules or higher-order state, modal logic provides modalities to hide explicit reasoning about step-indices that are used to stratify recursion.
The meta logic of proof assistants such as Coq is well suited to embed high-level object logics and prove their soundness. However, proof assistants such as Coq do not have native infrastructure to facilitate proofs in embedded logics - their proof contexts and built-in tactics for interactive and automated proofs are tailored to the connectives of the meta logic, and do not extend to those of the object logic. This results in proofs that are at a too low level of abstraction because they are cluttered with bookkeeping code related to manipulating the object logic.
In this talk I will describe our work in the Iris project to address this problem - first for interactive proofs, and then for semi-automated proofs. The Iris Proof Mode provides high-level tactics for interactive proofs in higher-order concurrent separation logic with modalities. Recent work on RefinedC and Diaframe have built on top of the Iris Proof Mode to obtain proof automation for low-level C programs and fine-grained concurrent programs
Modular Verification of Intrusive List and Tree Data Structures in Separation Logic
No full textIntrusive linked data structures are commonly used in low-level programming languages such as C for efficiency and to enable a form of generic types. Notably, intrusive versions of linked lists and search trees are used in the Linux kernel and the Boost C++ library. These data structures differ from ordinary data structures in the way that nodes contain only the meta data (i.e. pointers to other nodes), but not the data itself. Instead the programmer needs to embed nodes into the data, thereby avoiding pointer indirections, and allowing data to be part of several data structures.
In this paper we address the challenge of specifying and verifying intrusive data structures using separation logic. We aim for modular verification, where we first specify and verify the operations on the nodes (without the data) and then use these specifications to verify clients that attach data. We achieve this by employing a representation predicate that separates the data structure’s node structure from the data that is attached to it. We apply our methodology to singly-linked lists - from which we build cyclic and doubly-linked lists - and binary trees - from which we build binary search trees. All verifications are conducted using the Coq proof assistant, making use of the Iris framework for separation logic
Cryostat Control: Real time control for a cryogenic refrigerator
No full textIn order to measure the spectrum of radio emissions from galaxies and other deep space objects, a new superconducting spectrometer, working at very cold temperatures close to the absolute zero, is developed. An advanced cooling system called a cryostat is used to cool down the spectrometer. The cool down of the cryostat involves the control of multiple sensors and actuators connected to the cryostat to achieve a final temperature below 250 millikelvin. A software program is used for this purpose. As extra hardware components have been added to the cryostat, the existing program does no longer fulfill the requirements. For this reason a new software program, which can monitor temperatures of all components and start control processes, is developed. The developed program consists of a client server structure. The server handles the logic of the cryostat using several controllers. It can send data to a native client, which is the graphical user interface, or a REST API. The native client displays sensor readouts received from the server and allows full control of server, which means it can start the cool down process as well as manual control processes. The REST API allows the user to have full control over the server using a Python script to achieve measurements which cannot be done from the native client. The increased automation, improved control and ability to integrate with external Python scripts allow the user to focus on the essential parts of an experiment making the developed program an improvement over the previous program
Proving functional correctness of monadic programs using separation logic
No full textInteraction trees are an active development in representing effectful and impure pro- grams in the Coq proof assistant. Examples of programs they can represent are programs that use: mutable state, concurrency and general recursion. Besides representing these programs we also want to reason about and verify these programs using separation logic. That is the purpose of this thesis. More technically speaking interaction trees are new way to do shallow embeddings in the Coq proof assistant. They are a coinductive variant of the free monad and come with the usual constructions of events and event handlers. The aim of interaction trees is to represent impure programs and potentially non-terminating programs in their environment. Interaction trees are, in contrast to relational operational semantics, executable by interpretation or program extraction. Interaction trees come with a framework for reasoning about their behavior based on equivalency up to weak bisimulation. An open problem is to reason about interaction trees utilizing a separation logic rather than weak bisimulation. We developed Pothos as a solution to this problem. Pothos has an Iris based concurrent separation logic for interaction trees. We address the problem in a non-extensible setting, with mutable state, non-termination and concur- rency as our chosen effects. Pothos inherits all the executable properties from interaction trees and includes a novel relation of Iris’s step-index with coinductive types. We have proven our logic to be sound and include a case study of a spin lock library. The case study shows that our logic is both non-trivial and can utilize the standard Iris patterns for concurrency.Computer Scienc
A type system for dynamic instances
No full textSide-effect are ubiquitous in programming. Examples include mutable state, exceptions, non-determinism, and user input. Algebraic effects and handlers are an approach to programming that gives a structured way of programming with effects. Each effect in a system with algebraic effects is defined by a set of operations. These operations can then be called anywhere in a program. Using a handler we can give an interpretation for the operations used. Unfortunately we are unable to express dynamic effects using regular algebraic effects, such as the dynamic creation of mutable references. Extending algebraic effects with effect instances enables us to express dynamic effects. These effect instances can be dynamically created and operations called on them are distinct from the same operation called on a different instance. Without a type system effect instances may result in runtime errors, because operation calls may be left unhandled. Because of their dynamic nature it is hard to give a type system for effect instances. In this thesis we present a new language, Miro, which extends algebraic effects and handlers with a restricted form of effect instances. We introduce the notion of an effect scope which encapsulates the creation and usage of dynamically created effect instances. We give a formal description of the syntax and semantics of Miro. We also give a type system which ensures that all operation calls are handled, so that there will be no runtime errors because of unhandled operation calls. Because effect instances can still escape their effect scope, in computationally irrelevant parts, we encounter difficulties in proving type safety for Miro. We discuss these difficulties and give a possible approach to prove type safety in the future.Computer Scienc
The Interval Domain in Homotopy Type Theory
No full textEven though the real numbers are the cornerstone of many fields in mathematics, it is challenging to formalize them in a constructive setting, and in particular, homotopy type theory. Several approaches have been established to define the real numbers, and the most prominent of them are based on Dedekind cuts and on Cauchy sequences. In this paper, we study a different approach towards defining the real numbers. Our approach is based on domain theory, and in particular, the interval domain, and we build forth on recent work on domain theory in univalent foundations. All the results in this paper have been formalized in Coq as part of the UniMath library.</p
It’s All a Game:Apartness and Bisimilarity
No full textWe study the connection between apartness and bisimulation games. Strong apartness has been proposed as a relation for distinguishing states in a labelled transition system. Prior work has shown that there is a clear connection between Hennessy-Milner logic, strong bisimilarity and strong apartness. We show that in a bisimulation game, winning strategies for SPOILER can be obtained from apartness proofs, and, vice versa, apartness proofs can be produced from winning SPOILER strategies.</p
An Operational and Axiomatic Semantics for Non-determinism and Sequence Points in C
No full textContains fulltext :
126245.pdf (Author’s version preprint ) (Open Access
A Formal C Memory Model for Separation Logic
No full textContains fulltext :
161380.pdf (Publisher’s version ) (Open Access)
Contains fulltext :
161380.pdf (Author’s version preprint ) (Open Access
Minimal Depth Distinguishing Formulas Without Until for Branching Bisimulation
No full textIn [16] an algorithm for distinguishing formulas for branching bisimulation is proposed. This algorithm has two shortcomings. First, it uses a dedicated until operator, and second, the generated formulas are in no sense minimal. Here we propose a method that generates formulas fitting in the modal mu-calculus, or more precisely, in Hennessy-Milner logic with one regular modality. We provide a polynomial-time algorithm that generates a distinguishing formula that is guaranteed to have minimal depth. Our technical exposition heavily relies on branching apartness, the dual of branching bisimulation.</p
- …
