Search

A capability machine is a type of CPU allowing fine-grained privilege separation using capabilities, machine words that represent certain kinds of authority. We present a mathematical model and accompanying proof methods that can be used for formal verification of functional correctness of programs running on a capability machine, even when they invoke and are invoked by unknown (and possibly malicious) code. We use a program logic called Cerise for reasoning about known code, and an associated logical relation, for reasoning about unknown code. The logical relation formally captures the capability safety guarantees provided by the capability machine. The Cerise program logic, logical relation, and all the examples considered in the paper have been mechanized using the Iris program logic framework in the Coq proof assistant. The methodology we present underlies recent work of the authors on formal reasoning about capability machines [Georges et al. 2021; Skorstengaard et al. 2019a; Van Strydonck et al. 2022], but was left somewhat implicit in those publications. In this paper we present a pedagogical introduction to the methodology, in a simpler setting (no exotic capabilities), and starting from minimal examples. We work our way up to new results about a heap-based calling convention and implementations of sophisticated object-capability patterns of the kind previously studied for high-level languages with object-capabilities, demonstrating that the methodology scales to such reasoning. [ABSTRACT FROM AUTHOR]

Many foundational program verification tools have been developed to build machine-checked program correctness proofs, a majority of which are based on Hoare logic. Their program logics, their assertion languages, and their underlying programming languages can be formalized by either a shallow embedding or a deep embedding. Tools like early versions of Verified Software Toolchain (before 2018) choose different shallow embeddings to formalize their program logic. But the pros and cons of these different embeddings were not yet well studied. Therefore, we want to study the impact of the program logic’s embedding on logic’s proof rules in this paper. This paper considers a set of useful extended proof rules, which aided the proof automation in VST, and four different logic embeddings: one deep embedding and three common shallow embeddings. We prove the validity of these extended rules under these embeddings and discuss their main challenges. Furthermore, we propose a method to lift existing shallowly embedded logics to deeply embedded ones to greatly simplify proofs of extended rules in VST. We implemented our theory in VST by lifting the originally shallowly embedded VST to our deeply embedded VST and establishing these extended rules. [ABSTRACT FROM AUTHOR]

We apply program verification technology to the problem of specifying and verifying automatic differentiation (AD) algorithms. We focus on define-by-run, a style of AD where the program that must be differentiated is executed and monitored by the automatic differentiation algorithm. We begin by asking, "what is an implementation of AD?" and "what does it mean for an implementation of AD to be correct?" We answer these questions both at an informal level, in precise English prose, and at a formal level, using types and logical assertions. After answering these broad questions, we focus on a specific implementation of AD, which involves a number of subtle programming-language features, including dynamically allocated mutable state, first-class functions, and effect handlers. We present a machine-checked proof, expressed in a modern variant of Separation Logic, of its correctness. We view this result as an advanced exercise in program verification, with potential future applications to the verification of more realistic automatic differentiation systems and of other software components that exploit delimited-control effects. [ABSTRACT FROM AUTHOR]

A proof procedure, in the spirit of the sequent calculus, is proposed to check the validity of entailments between Separation Logic formulas combining inductively defined predicates denoting structures of bounded tree width and theory reasoning. The calculus is sound and complete, in the sense that a sequent is valid iff it admits a (possibly infinite) proof tree. We also show that the procedure terminates in the two following cases: (i) When the inductive rules that define the predicates occurring on the left-hand side of the entailment terminate, in which case the proof tree is always finite. (ii) When the theory is empty, in which case every valid sequent admits a rational proof tree, where the total number of pairwise distinct sequents occurring in the proof tree is doubly exponential w.r.t. the size of the end-sequent. [ABSTRACT FROM AUTHOR]

We study the expressivity and complexity of two modal logics interpreted on finite forests and equipped with standard modalities to reason on submodels. The logic ML(|) extends the modal logic K with the composition operator from ambient logicwhereasML(*) features the separating conjunction * from separation logic. Both operators are second-order in nature. We show that ML(|) is as expressive as the graded modal logic GML (on trees) whereas ML(*) is strictly less expressive than GML. Moreover, we establish that the satisfiability problem is Tower-complete for ML(*), whereas it is (only) AExpPol-complete for ML(|), a result that is surprising given their relative expressivity. As by-products, we solve open problems related to sister logics such as static ambient logic and modal separation logic. [ABSTRACT FROM AUTHOR]

In this paper we present an extension of (bunched) separation logic, Boolean BI, with epistemic and dynamic epistemic modalities. This logic, called action model separation logic (AMSL ), can be seen as a generalization of public announcement separation logic in which we replace public announcements with action models. Then we not only model public information change (public announcements) but also non-public forms of information change, such as private announcements. In this context the semantics for the connectives ∗ and - ∗ from separation logic are epistemic versions of their usual semantics. This is because formulas are interpreted in states, not in resources, and agents may be uncertain between different states representing the same resource. We present the logic AMSL and its semantics, with a detailed case study that highlights its interest for modeling. We also prove the elimination of the dynamics modalities and discuss some alternative epistemic semantics for the separation connectives. [ABSTRACT FROM AUTHOR]

Owing to the massive growth in the storage demands of big data, cloud storage systems emerge at a historic moment, among which block-based cloud storage systems (BCSSs) are typical. Compared with traditional storage systems, BCSSs have many advantages, such as higher capacity, lower cost, and better scalability. BCSSs are also much more complex and error prone than traditional systems, and therefore, their reliability is a significant concern. Correctness is the most basic requirement for reliability. Therefore, it is of great significance to study BCSS program correctness verification to establish the theoretical basis for cloud storage systems. In this paper, we propose a novel framework based on separation logic (SL) to verify the correctness of BCSS management programs. We first construct a two-tier heap structure as the formal model of the storage architecture for BCSSs and present a modelling language based on this structure to describe the program execution. We then define assertion pairs to describe the properties of the two-tier structure. The two components of an assertion pair affect each other, producing several interesting properties. Finally, we propose a Hoare-style proof system to reason about BCSS programs and establish its soundness. We also demonstrate our proof system's uniqueness, usability, and scalability by verifying several real-world BCSS sample programs. In summary, this work presents a systematic approach that can be used to effectively solve BCSS program verification problems, and provides an SL-based logical modelling strategy, specifically to build its consistency with the actual behaviour of BCSSs. • Two-tier heap structure as a formal model of a block-based cloud storage system. • Separation logic-based assertion language with several new operators and connectives. • Hoare-style proof system to reason about BCSS management programs and its soundness. • Methods for formulation of specification rules to make them concise and effective. [ABSTRACT FROM AUTHOR]

Modern separation logics allow one to prove rich properties of intricate code, e.g., functional correctness and linearizability of non-blocking concurrent code. However, this expressiveness leads to a complexity that makes these logics difficult to apply. Manual proofs or proofs in interactive theorem provers consist of a large number of steps, often with subtle side conditions. On the other hand, automation with dedicated verifiers typically requires sophisticated proof search algorithms that are specific to the given program logic, resulting in limited tool support that makes it difficult to experiment with program logics, e.g., when learning, improving, or comparing them. Proof outline checkers fill this gap. Their input is a program annotated with the most essential proof steps, just like the proof outlines typically presented in papers. The tool then checks automatically that this outline represents a valid proof in the program logic. In this paper, we systematically develop a proof outline checker for the TaDA logic, which reduces the checking to a simpler verification problem, for which automated tools exist. Our approach leads to proof outline checkers that provide substantially more automation than interactive provers, but are much simpler to develop than custom automatic verifiers. [ABSTRACT FROM AUTHOR]

Symbolic heaps, which are a restricted class of separation logic formulas, with inductive definitions are a suitable language in automated verification systems for memory-manipulating programs. In this context, some related problems, e.g., the entailment problem, have been studied theoretically. In addition, several solvers for the entailment problem based on the proof-search algorithm in cyclic-proof systems, which are proof systems in sequent calculus style with cyclic structure, have been proposed. However, the cut-elimination property generally does not hold for cyclic-proof systems of symbolic heaps with inductive definitions, which means that searching for a cut-free proof is insufficient. In other words, we hope to find a reasonable proof-search algorithm considering the cut rule or we give up on obtaining a complete proof-search procedure. This paper investigates this issue and demonstrates a limit to the challenge of the restrictions on the cut rule in a cyclic-proof system for symbolic heaps. We propose a restricted cut rule, referred to as the presumable cut, which is a relaxed variant of the analytic cut, in which the cut formula must be a subformula of the bottom sequent. This paper demonstrates that the provability of the cyclic-proof system for symbolic heaps becomes strictly weaker by restricting the cut rule to the presumable cut. [ABSTRACT FROM AUTHOR]

• We add CUDA verification support to the VerCors verifier. • We verify data race-freedom and functional correctness of CUDA implementations of two parallel prefix sum algorithms. • We verify data race-freedom and functional correctness of CUDA implementations of stream compaction algorithm. GPUs are an important part of any High Performance Computing (HPC) architecture. To make optimal use of the specifics of a GPU architecture, we need programming models that naturally support the parallel execution model of a GPU. CUDA and OpenCL are two widely used examples of such programming models. Furthermore, we also need to redesign algorithms such that they adhere to this parallel programming model, and we need to be able to prove the correctness of these redesigned algorithms. In this paper we study two examples of such parallelized algorithms, and we discuss how to prove their correctness (data race freedom and (partial) functional correctness) using the VerCors program verifier. First of all, we prove the correctness of two parallel algorithms solving the prefix sum problem. Second, we show how such a prefix sum algorithm is used as a basic block in a stream compaction algorithm, and we prove correctness of this stream compaction algorithm, taking advantage of the earlier correctness proof for the prefix sum algorithm. The proofs as described in this paper are developed over the CUDA implementations of these algorithms. In earlier work, we had already shown correctness of a more high-level version of the algorithm. This paper discusses how we add support to reason about CUDA programs in VerCors, and it then shows how we can redo the verification at the level of the CUDA code. We also discuss some practical challenges that we had to address to prove correctness of the actual CUDA-level verifications. [ABSTRACT FROM AUTHOR]

• A new Hoare-style proof system to analyze and verify cloud storage system management programs. • A formalization of modular local reasoning about program correctness verification. • A set of adaptation rules to adapt the condition of specifications to broader contexts. • The soundness and adaptation completeness of the proof system. The rapid growth of data presents a significant challenge to the capability of traditional storage technologies to collect and manage data. Cloud storage systems (CSSs) have been proposed as a method to improve storage capacity. To safely and effectively manage cloud storage data and improve data service quality, it is necessary to verify the correctness of CSS management programs. However, the complexity of these systems renders program verification difficult. In this paper, we propose a Hoare-style proof system, in conjunction with two languages, to analyze and verify CSS management programs. The first is a modeling language that describes the program execution. The second is an assertion language based on Separation Logic (SL), used to describe the properties of the CSS file-block-location storage structure. The proof system supports modular local reasoning for CSS programs by a set of adaptation rules, which enable the condition of specifications to be applied to broader contexts. A key question that arises is whether the proof system can meet adaptation completeness. If so, arbitrary satisfiable specifications can be adjusted using the adaptation rules. To this end, we developed local predicate transformers and used their domain to interpret all types of commands. By finding the smallest local predicate transformer, we established adaptation completeness. In summary, this work provides a formalization of automatic modular reasoning patterns and lays a theoretical foundation for the compositional program verification of CSSs. [ABSTRACT FROM AUTHOR]

SL-COMP is a competition bringing together researchers and users interested in automated reasoning methods for separation logic (SL). The competition provides a snapshot of the state of the art in the area through a set of problems that put forward the strengths and challenges of the existing solvers and a comparative and replicable evaluation of participating solvers. The third edition of SL-COMP took place in April 2019, as part of the TOOLympics event at TACAS 2019. It collected more than 1K satisfiability and entailment problems, had seen the adoption of the new input format based on SMT-LIB and had doubled the number of participant solvers compared with the first edition in 2014. This report relates the history and the context of SL-COMP competition and accounts of its third edition. It also discusses the issues related with its organization and the challenges for the next editions. [ABSTRACT FROM AUTHOR]

Static analyses aim at inferring semantic properties of programs. We distinguish two important classes of static analyses: state analyses and relational analyses. While state analyses aim at computing an over-approximation of reachable states of programs, relational analyses aim at computing functional properties over the input–output states of programs. Several advantages of relational analyses are their ability to analyze incomplete programs, such as libraries or classes, but also to make the analysis modular, using input–output relations as composable summaries for procedures. In the case of numerical programs, several analyses have been proposed that utilize relational numerical abstract domains to describe relations. On the other hand, designing abstractions for relations over input–output memory states and taking shapes into account is challenging. In this paper, we propose a set of novel logical connectives to describe such relations, which are inspired by separation logic. This logic can express that certain memory areas are unchanged, freshly allocated, or freed, or that only part of the memory was modified. Using these connectives, we build an abstract domain and design a static analysis that over-approximates relations over memory states containing inductive structures. We implement this analysis and report on the analysis of basic libraries of programs manipulating lists and trees. [ABSTRACT FROM AUTHOR]

We present a new version of ReLoC: a relational separation logic for proving refinements of programs with higher-order state, fine-grained concurrency, polymorphism and recursive types. The core of ReLoC is its refinement judgment e ≲ e' : τ, which states that a program e refines a program e' at type τ. ReLoC provides type-directed structural rules and symbolic execution rules in separation-logic style for manipulating the judgment, whereas in prior work on refinements for languages with higher-order state and concurrency, such proofs were carried out by unfolding the judgment into its definition in the model. ReLoC's abstract proof rules make it simpler to carry out refinement proofs, and enable us to generalize the notion of logically atomic specifications to the relational case, which we call logically atomic relational specifications. We build ReLoC on top of the Iris framework for separation logic in Coq, allowing us to leverage features of Iris to prove soundness of ReLoC, and to carry out refinement proofs in ReLoC. We implement tactics for interactive proofs in ReLoC, allowing us to mechanize several case studies in Coq, and thereby demonstrate the practicality of ReLoC. ReLoC Reloaded extends ReLoC (LICS'18) with various technical improvements, a new Coq mechanization, and support for Iris's prophecy variables. The latter allows us to carry out refinement proofs that involve reasoning about the program's future. We also expand ReLoC's notion of logically atomic relational specifications with a new flavor based on the HOCAP pattern by Svendsen et al. [ABSTRACT FROM AUTHOR]