In order to maintain its presence on an infected system, malware employs a variety of persistence techniques. Although persistence is a well-known tactic of modern malware, our community lacks a comprehensive understanding of the types and prevalence of techniques adopted by Windows malware.

Abstract This paper introduces several techniques that improve the scalability of the deductive verification of data-level parallel programs working on arrays and matrices. First of all, we introduce a technique to rewrite expressions with (nested) quantifiers, so suitable triggers can be generated for these expressions. We have proven this rewrite technique correct using a theorem prover. Second, we make reasoning about potentially overlapping arrays easier, by providing specification constructs to indicate and verify that two arrays are not aliases, or that they are immutable, so they can be modelled as mathematical sequences. All our techniques are implemented in the VerCors program verifier. We illustrate how the combination of our techniques improves scalability via a large number of experiments. Using our techniques on a set of typical GPU kernels, we achieve a reduction of verification time by, on average, a factor of 9, with outliers being up to 150 times faster. Additionally, applying these techniques to earlier experiments and an earlier case study of a radio telescope pipeline permitted to obtain verification results that were previously either unobtainable or only in a significantly longer verification time.

Abstract Software model checking and deductive software verification have complementary strengths and weaknesses: software model checkers are more straight-forward to use, as they analyze the program without user input; but they do not yet support complicated data structures and expressive specifications. In contrast, deductive verifiers can verify expressive specifications and complex data structures modularly, but they require the user to specify the program behavior in detail, which is a time-consuming process. Due to their differing nature, the two approaches usually remain separate. However, for industrial usage, one requires both: ease of use as well as expressiveness. Therefore, we present AutoSV-Annotator , a toolchain that integrates the two approaches for C programs. The toolchain allows a user to iteratively refine the deductive annotations in a C program, calling a model checker to supplement the annotations at each iteration, guided by the already existing annotations. We show that our tool is able to annotate and prove many tasks from the SV-Benchmarks set. Our results show that the two strategies can indeed benefit from each other.

Abstract GPU programs are widely used in industry. To obtain the best performance, a typical development process involves the manual or semi-automatic application of optimizations prior to compiling the code. Such optimizations can introduce errors. To avoid the introduction of errors, we can augment GPU programs with (pre- and postcondition-style) annotations to capture functional properties. However, keeping these annotations correct when optimizing GPU programs is labor-intensive and error-prone. This paper presents an approach to automatically apply optimizations to GPU programs while preserving provability by defining annotation-aware transformations . It applies frequently-used GPU optimizations, but besides transforming code, it also transforms the annotations. The approach has been implemented in the Alpinist tool and we evaluate Alpinist in combination with the VerCors program verifier, to automatically apply optimizations to a collection of verified programs and reverify them.

Embedded systems are used in many safety-critical domains, including in medicine, traffic, and critical infrastructure. Due to the strict timing requirements such systems usually have to fulfill, they often run on real-time operating systems (RTOS). As the RTOS influences the function and the timing behavior of the system, it becomes important to rigorously ensure the correctness and safety of applications running on them while taking into account the semantics of the operating system. Existing verification approaches are either limited to specific RTOS components or based on explicit state space exploration techniques such as model checking, which do not scale well for concurrent or timed applications. In this article, we propose a deductive approach to verify crucial safety properties about applications written for the widely-used RTOS FreeRTOS using the VerCors verifier. Our key ideas are threefold: (1) We provide a formalization of a wide variety of FreeRTOS features and an automatic encoding of FreeRTOS applications for verification with VerCors. (2) We adapt and enhance an existing approach for automatic invariant generation to largely automate the typically high-effort verification process. (3) We present a systematic technique to verify both functional and timing-related properties of cooperative RTOS applications. We demonstrate the applicability of our approach on a FreeRTOS demo application as well as an adaptive cruise control system.

Despite significant effort put into research and development of defense mechanisms, new malware is continuously developed rapidly, making it still one of the major threats on the Internet. For malware to be successful, it is in the developer’s best interest to evade detection as long as possible. One method in achieving this is using Code Injection, where malicious code is injected into another benign process, making it do something it was not intended to do. Automated detection and characterization of Code Injection is difficult. Many injection techniques depend solely on system calls that in isolation look benign and can easily be confused with other background system activity. There is therefore a need for models that can consider the context in which a single system event resides, such that relevant activity can be distinguished easily. In previous work, we conducted the first systematic study on code injection to gain more insights into the different techniques available to malware developers on the Windows platform. This paper extends this work by introducing and formalizing Behavior Nets: A novel, reusable, context-aware modeling language that expresses malicious software behavior in observable events and their general interdependence. This allows for matching on system calls, even if those system calls are typically used in a benign context. We evaluate Behavior Nets and experimentally confirm that introducing event context into behavioral signatures yields better results in characterizing malicious behavior than the state of the art. We conclude with valuable insights on how future malware research based on dynamic analysis should be conducted.

Abstract This paper gives an overview of the most recent developments on the VerCors verifier. VerCors is a deductive verifier for concurrent software, written in multiple programming languages, where the specifications are written in terms of pre-/postcondition contracts using permission-based separation logic. In essence, VerCors is a program transformation tool: it translates an annotated program into input for the Viper framework, which is then used as verification back-end. The paper discusses the different programming languages and features for which VerCors provides verification support. It also discusses how the tool internally has been reorganised to become easily extendible, and to improve the connection and interaction with Viper. In addition, we also introduce two tools built on top of VerCors, which support correctness-preserving transformations of verified programs. Finally, we discuss how the VerCors verifier has been used on a range of realistic case studies.

Abstract Over the last years, deductive program verifiers have substantially improved, and their applicability on non-trivial applications has been demonstrated. However, a major bottleneck is that for every new programming language, a new deductive verifier has to be built. This paper describes the first steps in a project that aims to address this problem, by language-agnostic support for deductive verification: Rather than building a deductive program verifier for every programming language, we develop deductive program verification technology for a widely-used intermediate representation language (LLVM IR), such that we eventually get verification support for any language that can be compiled into the LLVM IR format. Concretely, this paper describes the design of VCLLVM, a prototype tool that adds LLVM IR as a supported language to the VerCors verifier. We discuss the challenges that have to be addressed to develop verification support for such a low-level language. Moreover, we also sketch how we envisage to build verification support for any specified source program that can be compiled into LLVM IR on top of VCLLVM.

Abstract The HaliVer tool integrates deductive verification into the popular scheduling language Halide, used for image processing pipelines and array computations. HaliVer uses VerCors, a separation logic-based verifier, to verify the correctness of (1) the Halide algorithms and (2) the optimised parallel code produced by Halide when an optimisation schedule is applied to an algorithm. This allows proving complex, optimised code correct while reducing the effort to provide the required verification annotations. For both approaches, the same specification is used. We evaluated the tool on several optimised programs generated from characteristic Halide algorithms, using all but one of the essential scheduling directives available in Halide. Without annotation effort, HaliVer proves memory safety in almost all programs. With annotations HaliVer, additionally, proves functional correctness properties. We show that the approach is viable and reduces the manual annotation effort by an order of magnitude.

Deductive verifiers require intensive user interaction in the form of writing precise specifications, thereby limiting their use in practice. While many solutions have been proposed to generate specifications, their evaluations and comparisons to other tools are limited. As a result, it is unclear what the best approaches for specification inference are and how these impact the overall specification writing process. In this paper we take steps to address this problem by providing an overview of specification inference tools that can be used for deductive verification of Java programs. For each tool, we discuss its approach to specification inference and identify its advantages and disadvantages. Moreover, we identify the types of specifications that it infers and use this to estimate the impact of the tool on the overall specification writing process. Finally, we identify the ideal features of a specification generator and discuss important challenges for future research.

Abstract To stimulate the development and application of formal methods in industry, we need to promote research and development for the improvement of formal methods and tools for industrial applications, and we need to exchange experiences of the industrial usage of these methods and tools. This special issue of Software Tools for Technology Transfer presents various tools and experience reports that are targeting the use of formal methods in industry. The papers in this special issue are extended versions of selected conference papers from the proceedings of the 27th International Conference on Formal Methods for Industrial Critical Systems (FMICS 2022).

Abstract We present “Verified JavaBIP”, a tool set for the verification of JavaBIP models. A JavaBIP model is a Java program where classes are considered as components, their behaviour described by finite state machine and synchronization annotations. While JavaBIP guarantees execution progresses according to the indicated state machines, it does not guarantee properties of the data exchanged between components. It also does not provide verification support to check whether the behaviour of the resulting concurrent program is as (safe as) expected. This paper addresses this by extending the JavaBIP engine with run-time verification support, and by extending the program verifier VerCors to verify JavaBIP models deductively. These two techniques complement each other: feedback from run-time verification allows quicker prototyping of contracts, and deductive verification can reduce the overhead of run-time verification. We demonstrate our approach on the “Solidity Casino” case study, known from the VerifyThis Collaborative Long Term Challenge.

Formal methods have been used in a wide range of domains, including software, cyber-physical systems, and integrated computer-based systems. In recent years, we have seen in particular the application of formal methods in a wide range of areas, such as systems-of-systems, security, artificial intelligence, human-computer interaction, manufacturing, sustainability, power, transport, smart cities, healthcare, and biology. Formal methods also get used more and more in industry. All of these developments are supported by the design and validation of various formal method tools.

Abstract This paper presents a case study where a concurrent module of a tunnel control system written in Java is verified for memory safety and data race freedom using VerCors, a software verification tool. This case study was carried out in close collaboration with our industrial partner Technolution, which is in charge of developing the tunnel control software. First, we describe the process of preparing the code for verification, and how we make use of the different capabilities of VerCors to successfully verify the module. The concurrent module has gone through a rigorous process of design, code reviewing and unit and integration testing. Despite this careful approach, VerCors found two memory related bugs. We describe these bugs, and show how VerCors could have found them during the development process. Second, we wanted to communicate back our results and verification process to the engineers of Technolution. We discuss how we prepared our presentation, and the explanation we settled on. Third, we present interesting feedback points from this presentation. We use this feedback to determine future work directions with the goal to improve our tool support, and to bridge the gap between formal methods and industry.

Abstract GPU programs are widely used in industry. To obtain the best performance, a typical development process involves the manual or semi-automatic application of optimizations prior to compiling the code. To avoid the introduction of errors, we can augment GPU programs with (pre- and postcondition-style) annotations to capture functional properties. However, keeping these annotations correct when optimizing GPU programs is labor-intensive and error-prone. This paper introduces Alpinist, an annotation-aware GPU program optimizer. It applies frequently-used GPU optimizations, but besides transforming code, it also transforms the annotations. We evaluate Alpinist, in combination with the VerCors program verifier, to automatically optimize a collection of verified programs and reverify them.

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.

Java code can be annotated with formal specifications using the Java Modelling Language (JML). Previous work has provided IDE plugins intended to help write JML, but mostly for the Eclipse IDE. We introduce IntelliJML, a JML plugin for IntelliJ IDEA, with a focus on ease of use and maintainability. Features such as syntax, semantic, and type checking, as well as syntax highlighting and code completion are integrated into the plugin. The plugin can also be extended in the future to add more features. The source code for the plugin can be found at https://gitlab.utwente.nl/fmt/intellijml.

Abstract Research competitions and challenges are a driving force in transferring theoretical results into working software tools that demonstrate the state of the art in the respective field of research. Regular comparative evaluations provide guidance to practitioners that have to select new technology and tools for their development process. In order to support competitions and challenges with an appropriate publication venue, a new theme of issues in the International Journal on Software Tools for Technology Transfer was created. This issue is the inaugural issue of the newly introduced theme on “Competitions and Challenges” (CoCha). Test-Comp, the International Competition on Software Testing, is an example of a tool competition, where the research teams submit tools for test-generation, and the competition evaluates the tools and assigns scores according to achieved coverage. Test-Comp 2019 was part of the TOOLympics event, which took place as part of the 25-year celebration of the conference TACAS. Thus, it is most natural to start the new STTT-CoCha theme with a special issue that describes the results and participating systems of Test-Comp 2019. There will be a second issue on TOOLympics with contributions from other competitions.

Abstract This is the second issue in the new “Competitions and Challenges” (CoCha) theme of the International Journal on Software Tools for Technology Transfer. The new theme was established to support competitions and challenges with an appropriate publication venue. The first issue presented the competition on software testing Test-Comp 2019, which was part of the TOOLympics 2019 event. In this second issue for TOOLympics, we present selected competition reports. The TOOLympics event took place as part of the 25-years celebration of the conference TACAS. The goal of the event was to provide an overview of competitions and challenges in the area of formal methods.

Abstract A commonly used approach to develop deterministic parallel programs is to augment a sequential program with compiler directives that indicate which program blocks may potentially be executed in parallel. This paper develops a verification technique to reason about such compiler directives, in particular to show that they do not change the behaviour of the program. Moreover, the verification technique is tool-supported and can be combined with proving functional correctness of the program. To develop our verification technique, we propose a simple intermediate representation (syntax and semantics) that captures the main forms of deterministic parallel programs. This language distinguishes three kinds of basic blocks: parallel, vectorised and sequential blocks, which can be composed using three different composition operators: sequential, parallel and fusion composition. We show how a widely used subset of OpenMP can be encoded into this intermediate representation. Our verification technique builds on the notion of iteration contract to specify the behaviour of basic blocks; we show that if iteration contracts are manually specified for single blocks, then that is sufficient to automatically reason about data race freedom of the composed program. Moreover, we also show that it is sufficient to establish functional correctness on a linearised version of the original program to conclude functional correctness of the parallel program. Finally, we exemplify our approach on an example OpenMP program, and we discuss how tool support is provided.

Abstract VerifyThis is a series of program verification competitions that emphasize the human aspect: participants tackle the verification of detailed behavioral properties—something that lies beyond the capabilities of fully automatic verification and requires instead human expertise to suitably encode programs, specifications, and invariants. This paper describes the 8th edition of VerifyThis, which took place at ETAPS 2019 in Prague. Thirteen teams entered the competition, which consisted of three verification challenges and spanned 2 days of work. This report analyzes how the participating teams fared on these challenges, reflects on what makes a verification challenge more or less suitable for the typical VerifyThis participants, and outlines the difficulties of comparing the work of teams using wildly different verification approaches in a competition focused on the human aspect.

Techniques are required that support developers to produce GPU software that is both functionally correct and high-performing. We envision an integration of push-button formal verification techniques into a Model Driven Engineering workflow. In this paper, we present our vision on this topic, and how we plan to make steps in that direction in the coming five years.

String sanitizers are widely used functions for preventing injection attacks such as SQL injections and cross-site scripting (XSS). It is therefore crucial that the implementations of such string sanitizers are correct. We present a novel approach to reason about a sanitizer's correctness by automatically generating a model of the implementation and comparing it to a model of the expected behaviour. To automatically derive a model of the implementation of the sanitizer, this paper introduces a black-box learning algorithm that derives a Symbolic Finite Transducer (SFT). This black-box algorithm uses membership and equivalence oracles to derive such a model. In contrast to earlier research, SFTs not only describe the input or output language of a sanitizer but also how a sanitizer transforms the input into the output. As a result, we can reason about the transformations from input into output that are performed by the sanitizer. We have implemented this algorithm in an open-source tool of which we show that it can reason about the correctness of non-trivial sanitizers within a couple of minutes without any adjustments to the existing sanitizers. © Copyright 2020 by SCITEPRESS - Science and Technology Publications, Lda. All rights reserved.

Model checking algorithms are typically complex graph algorithms, whose correctness is crucial for the usability of a model checker. However, establishing the correctness of such algorithms can be challenging and is often done manually. Mechanising the verification process is crucially important, because model checking algorithms are often parallelised for efficiency reasons, which makes them even more error-prone. This paper shows how the VerCors concurrency verifier is used to mechanically verify the parallel nested depth-first search (NDFS) graph algorithm of Laarman et al. [ 25 ]. We also demonstrate how having a mechanised proof supports the easy verification of various optimisations of parallel NDFS. As far as we are aware, this is the first automated deductive verification of a multi-core model checking algorithm.

the 24th International Conference on Tools and Algorithms for the Construction and Analysis of Systems took place in Thessaloniki, Greece on April 16-20, 2018, as part of the European Joint Conferences on Theory and Practice of Software (ETAPS).TACAS is a forum for researchers, developers, and users interested in rigorously based tools and algorithms for the construction and analysis of systems.The conference aims to bridge the gaps between different communities with this common interest and to support them in their quest to improve the utility, reliability, flexibility, and efficiency of tools and algorithms for building systems.This special issue of the Journal of Automated Reasoning contains revised and extended versions of seven papers selected out of 45 papers presented at the conference.The papers that were selected for this special issue all provide new theoretical contributions to the construction and analysis of systems.In addition to this special issue, a companion special issue for TACAS 2018 appears in the journal Software Tools for Technology Transfer (STTT), containing selected papers that report on advances in tools and tool sets in this area.All selected papers underwent a thorough reviewing process, with several iterations, where each paper was reviewed by several external domain experts.As a result of this selection process, this special issue contains the following papers.Kshitij Bansal, Eric Koskinen, and Omer Tripp propose an algorithm to reason automatically about commutativity (and non-commutativity) conditions for method pairs in a parallel context.They illustrate their approach by synthesizing commutativity conditions for several widely used data structures.Randal E. Bryant introduces chain reduction to enable reduced ordered binary decision diagrams (BDDs) and zero-suppressed binary decision diagrams (ZDDs) to each take advantage of the others' ability to symbolically represent Boolean functions in a compact form.He proposes extensions to the standard algorithms for operating on BDDs and ZDDs that enable them to operate on the chain-reduced versions.

Abstract In order to develop reliable software and systems, we depend on practical techniques for the construction and analysis of such software and systems. This special issue of Software Tools for Technology Transfer presents various tool-supported techniques that can help with the construction and analysis of such reliable software and systems. The papers in this special issue are extended versions of selected conference papers from the proceedings of the 24th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2018).

Evaluation of scientific contributions can be done in many different ways. For the various research communities working on the verification of systems (software, hardware, or the underlying involved mechanisms), it is important to bring together the community and to compare the state of the art, in order to identify progress of and new challenges in the research area. Competitions are a suitable way to do that. The first verification competition was created in 1992 (SAT competition), shortly followed by the CASC competition in 1996. Since the year 2000, the number of dedicated verification competitions is steadily increasing. Many of these events now happen regularly, gathering researchers that would like to understand how well their research prototypes work in practice. Scientific results have to be reproducible, and powerful computers are becoming cheaper and cheaper, thus, these competitions are becoming an important means for advancing research in verification technology. TOOLympics 2019 is an event to celebrate the achievements of the various competitions, and to understand their commonalities and differences. This volume is dedicated to the presentation of the 16 competitions that joined TOOLympics as part of the celebration of the $$25^{ th }$$ anniversary of the TACAS conference.

VerifyThis is a series of competitions that aims to evaluate the current state of deductive tools to prove functional correctness of programs. Such proofs typically require human creativity, and hence it is not possible to measure the performance of tools independently of the skills of its user. Similarly, solutions can be judged by humans only. In this paper, we discuss the role of the human in the competition setup and explore possible future changes to the current format. Regarding the impact of VerifyThis on deductive verification research, a survey conducted among the previous participants shows that the event is a key enabler for gaining insight into other approaches, and that it fosters collaboration and exchange.

Software quality assurance aims to ensure that the software product meets the quality standards expected by the customer. This special issue of Software Tools for Technology Transfer is concerned with the foundations on which software quality assurance is built. It introduces the papers that focus on this topic and that have been selected from the 20th International Conference on Fundamental Approaches to Software Engineering (FASE’17).

Software is omnipresent, and software failures can have tremendous costs for society and economy. Therefore, we need techniques to improve the quality of software, and to prevent software failures. Program verification can help to improve this situation, as it allows to check properties on all possible behaviours of a program. We focus in particular on the verification of concurrent software, which is even more error-prone, because of the possible interleavings between the different threads.

VerifyThis 2015 was a one-day program verification competition which took place on April 12th, 2015 in London, UK, as part of the European Joint Conferences on Theory and Practice of Software (ETAPS 2015). It was the fourth instalment in the VerifyThis competition series. This article provides an overview of the VerifyThis 2015 event, the challenges that were posed during the competition, and a high-level overview of the solutions to these challenges. It concludes with the results of the competition and some ideas and thoughts for future instalments of VerifyThis.

Existing concurrency control systems cannot execute transactions with overlapping updates concurrently. This is especially problematic for bulk updates, which usually overlap with all concurrent transactions. To solve this, we have developed a concurrency control mechanism based on lazy evaluation, which moves evaluation of operations from the writer to the reader. This allows readers to prioritize evaluation of those operations in which they are interested, without loss of atomicity of transactions. To handle bulk operations, we dynamically split large transactions into transactions on smaller parts of the data. In this paper we present an abstract lazy index structure for lazy transactions, and show how transactions can be encoded to effectively use this data structure. Moreover, we discuss evaluation strategies for lazy transactions, where trade-offs can be made between latency and throughput. To evaluate our approach, we have implemented a concurrent lazy trie, on which we performed a number of micro benchmarks.

This paper discusses how several concurrent program verification techniques can be combined in a layered approach, where each layer is especially suited to verify one aspect of concurrent programs, thus making verification of concurrent programs practical. At the bottom layer, we use a combination of implicit dynamic frames and CSL-style resource invariants, to reason about data race freedom of programs. We illustrate this on the verification of a lock-free queue implementation. On top of this, layer 2 enables reasoning about resource invariants that express a relationship between thread-local and shared variables. This is illustrated by the verification of a reentrant lock implementation, where thread-locality is used to specify for a thread which locks it holds, while there is a global notion of ownership, expressing for a lock by which thread it is held. Finally, the top layer adds a notion of histories to reason about functional properties. We illustrate how this is used to prove that the lock-free queue preserves the order of elements, without having to reverify the aspects related to data race freedom.

This paper presents a benchmark for measuring the blocking behavior of schema transformations in relational database systems. As a basis for our benchmark, we have developed criteria for the functionality and performance of schema transformation mechanisms based on the characteristics of state of the art approaches. To address limitations of existing approaches, we assert that schema transformations must be composable while satisfying the ACID guarantees like regular database transactions. Additionally, we have identified important classes of basic and complex relational schema transformations that a schema transformation mechanism should be able to perform. Based on these transformations and our criteria, we have developed a benchmark that extends the standard TPC-C benchmark with schema transformations, which can be used to analyze the blocking behavior of schema transformations in database systems. The goal of the benchmark is not only to evaluate existing solutions for non-blocking schema transformations, but also to challenge the database community to find solutions that allow more complex transactional schema transformations.

Run-time assertion checking of multithreaded programs is challenging, as assertion evaluation should not interfere with the execution of other threads. This paper describes the prototype implementation of a run-time assertion checker that achieves this by evaluating assertions over snapshots of the state, instead of over the live state. Our prototype e-OpenJML, an extension to OpenJML, provides an easy to use, safe and interference-free evaluation of JML specifications in multithreaded programs. To achieve this, it integrates e-STROBE, our extension to the STROBE framework for asynchronous assertion evaluation. e-STROBE prevents all possible interferences between assertion evaluation and other program threads, which the original STROBE can not. It also simplifies evaluating assertions that relate the value of expressions in multiple states.

Permission accounting is fundamental to modular, thread-local reasoning about concurrent programs. This paper presents a new, symbolic system for permission accounting. In existing systems, permissions are numeric value-based and refer to the current thread only. Our system is based on symbolic expressions that provide a view of permissions for all relevant threads in the scope of the permission originator - current thread or a lock. This enables: (a) better understanding of permission tracking for the specifier, (b) more natural specification of complex permission transfer scenarios, and (c) more efficient reasoning for verification tools (in particular, no reasoning about rational numbers is required). Our system is based on symbolic permission slicing to divide permissions between multiple owners, and on tracking the history of permission transfers by means of "I-owe-you" chains of permission owners. We acclimatised our permission system in the KeY verifier as well as in PVS, and proved correct with both tools a list of vital properties about our permissions. KeY is an interactive verification tool for Java and our primary target to employ our permission system. First results with the verification of concurrent Java programs using our permission system in KeY are also reported.

This paper discusses static verification of programs that have been specified using separation logic with magic wands. Magic wands are used to specify incomplete resources in separation logic, i.e., if missing resources are provided, a magic wand allows one to exchange these for the completed resources. One of the applications of the magic wand operator is to describe loop invariants for algorithms that traverse a data structure, such as the imperative version of the tree delete problem (Challenge 3 from the VerifyThis@FM2012 Program Verification Competition), which is the motivating example for our work. Most separation logic-based static verification tools do not provide support for magic wands, possibly because validity of formulas containing the magic wand is, by itself, undecidable. To avoid this problem, in our approach the program annotator has to provide a witness for the magic wand, thus circumventing undecidability due to the use of magic wands. A witness is an object that encodes both instructions for the permission exchange that is specified by the magic wand and the extra resources needed during that exchange. We show how this witness information is used to encode a specification with magic wands as a specification without magic wands. Concretely, this approach is used in the VerCors tool set: annotated Java programs are encoded as Chalice programs. Chalice then further translates the program to BoogiePL, where appropriate proof obligations are generated. Besides our encoding of magic wands, we also discuss the encoding of other aspects of annotated Java programs into Chalice, and in particular, the encoding of abstract predicates with permission parameters. We illustrate our approach on the tree delete algorithm, and on the verification of an iterator of a linked list.

Specifying the functional behaviour of a concurrent program can often be quite troublesome: it is hard to provide a stable method contract that can not be invalidated by other threads. In this paper we propose a novel modular technique for specifying and verifying behavioural properties in concurrent programs. Our approach uses history-based specifications. A history is a process algebra term built of actions, where each action represents an update over a heap location. Instead of describing the object's precise state, a method contract may describe the method's behaviour in terms of actions recorded in the history. The client class can later use the history to reason about the concrete state of the object.

This paper discusses formal specification and verification of the synchronisation classes of the Java API. In many verification systems for concurrent programs, synchronisation is treated as a primitive operation. As a result, verification rules for synchronisation are hard-coded in the logic, and not verified. These rules describe the concrete semantics of the given synchronisation primitive, and manage how resources are protected by synchronisation. In contrast, this paper describes several synchronisation primitives at the specification level, by specifying the behaviour of synchronisation routines from the Java API at method level using permission-based Separation Logic. This gives a generalised, high-level, and easily extendable approach to formalisation of arbitrary synchronisation mechanisms, which allows for modular treatment of synchronisation in verification. Notably, our approach does not only apply to locks, but also to other synchronisation mechanisms such as semaphores and latches that we also discuss. Finally, we used the verification tool that we are developing and successfully verified (so far simplified) implementations of all presented synchronisers, the paper discusses the verification of one of them.

This paper studies how confidentiality properties of multi-threaded programs can be verified efficiently by a combination of newly developed and existing model checking algorithms. In particular, we study the verification of scheduler-specific observational determinism (SSOD), a property that chara cterizes secure information flow for multi-threaded programs under a given scheduler. Scheduler-specificness allows us to reason about refinement attacks, an important and tricky class of attacks that are notorious in practice. SSOD imposes two conditions: (SSOD-1) all individual public variables have to evolve deterministically, expressed by requiring stuttering equivalence between the traces of each individual public variable, and (SSOD-2) the relative order of updates of public variables is coincidental, i.e., there always exists a matching trace. We verify the first condition by reducing it to the question whether all traces of each public variable are stuttering equivalent. To verify the second condition, we show how the condition can be translated, via a series of steps, into a standard strong bisimulation problem. Our verification techniques can be easily adapted to verify other formalizations of similar information flow properties. We also exploit counter example generation techniques to synthesize attacks for insecure programs that fail either SSOD-1 or SSOD-2, i.e., showing how confidentiality of programs can be broken.

With the omnipresent usage of APIs in software development, it has become important to analyse how the routines and functionalities of APIs are actually used. This information is in particular useful for API developers, to make decisions about future updates of the API. However, also for developers of static analysis and verification tools this information is highly important, because it indicates where and how to put the most efficient effort in annotating APIs, to make them usable for the static analysis and verification tools. This paper presents an analysis of the usage of the routines and functionalities of the Java concurrency library java. util. concurrent. It discusses the Histogram tool that we developed for this purpose, i.e., to efficiently analyse a large collection of bytecode classes. The Histogram tool is used on a representative benchmark set, the Qualitas Corpus. The paper discusses the results of the analysis of this benchmark set in detail. This covers both an analysis of the important classes and methods used by the current releases of the benchmark collection, as well as an analysis of the time it took for the Java concurrency library to start being used in released software.

Design by Contract (DbC) is a technique for developing and improving functional software correctness through definition of "contracts" between client classes and their suppliers. Such contracts are enforced during runtime and if any of them is violated a runtime error should occur. Runtime assertions checkers (RACs) are a well-known technique that enforces such contracts. Although they are largely used to implement the DbC technique in contemporary languages, like Java, studies have shown that characteristics of contemporary exception handling mechanisms can discard contract violations detected by RACs. As a result, a contract violation may not be reflected in a runtime error, breaking the supporting hypothesis of DbC. This paper presents an error recovery technique for RACs that tackles such limitations. This technique relies on aspect-oriented programming in order to extend the functionalities of existing RACs stopping contract violations from being discarded. We applied the recovery technique on top of five Java-based contemporary RACs (i.e., JML/jml, JML/ajml, JContractor, CEAP, and Jose). Preliminary results have shown that the proposed technique could actually prevent the contract violations from being discarded regardless of the characteristics of the exception handling code of the target application.

This paper describes a novel technique for fully automated procedure-modular verification of Java programs equipped with method-local and global assertions that specify safety properties of sequences of method invocations. Modularity of verification is achieved by relativizing the correctness of global properties on the local properties rather than on the implementations of methods, and is based on the construction of maximal models. Tool support is provided by means of ProMoVer, a tool that is essentially a wrapper around a previously developed tool set for compositional verification of control flow safety properties, where program data is abstracted away completely. We evaluate the technique on a small but realistic case study.

This paper discusses how a subtle interaction between the semantics of Java and the implementation of the JML runtime checker can cause the latter to fail to report errors. This problem is due to the well-known capability of finally clauses to implicitly override exceptions. We give some simple examples of annotation violations that are not reported by the run-time checker because the errors are caught within the program text; even without any explicit reference to them. We explain this behaviour, based on the official Java Language Specification. We also discuss what are the consequences of this problem, and we sketch different solutions to the problem (by adapting the implementation of the JML run-time checker, or by adopting a slightly different semantics for Java).

This paper studies observational determinism, a generalisation of non-interference for multi-threaded programs. Standard notions of non-interference only consider input and output of programs, but to ensure the security of multithreaded programs, one has to consider execution traces. In earlier work, Zdancewic and Myers propose to consider a multi-threaded program secure when it behaves deterministic w.r.t. its public (or low) variables, i.e. traces of public variables should not depend on private (or high) variables. This property is called observational determinism. The original definition of observational determinism still allows to reveal private data; this paper corrects this. The main contribution of this paper is a rephrasing of the definition of observational determinism in terms of a temporal logic. This allows to use standard model checking techniques to verify observational determinism, which has the advantage that the verification is automatic and precise. Moreover in case the verification fails, model checking can produce a counterexample. We characterise observational determinism in CTL* and in the polyadic modal mu-calculus. For both logics, model checking algorithms exist

To support dynamic loading of applications on portable devices, one needs compositional reasoning techniques to ensure that newly loaded applications cannot break the overall security of a device. In earlier work, we developed an algorithmic verification technique for control flow based safety properties of smart card applications, which allows global system properties to be inferred from the properties of the components. Application of the technique requires knowledge of the names of all methods implemented by these components. In a truly compositional setting, however, one only knows the public interface of the new applet and does not have access to any implementation details. To compositionally verify interface properties of applets, one therefore has to combine our verification technique with an abstraction which preserves the interface behaviour and reduces the set of implemented methods to the set of public methods. In this paper, we develop such an abstraction technique: we formally define the notion of interface behaviour, and propose an inlining transformation which we prove to preserve the interface properties expressible in our specification language. In addition, we show on a concrete case study how the reduction in the number of methods resulting from the interface abstraction drastically improves the performance of the computationally most expensive step of the compositional verification technique.

We present an algorithmic compositional verification method for smart card applets and control flow based safety properties expressed in a modal logic with simultaneous greatest fixed points. Our method builds on a technique proposed by Grumberg and Long who use maximal models to reduce compositional verification of finite-state parallel processes to standard model checking. We adapt this technique to applets, a class of infinite-state sequential processes. This requires a refinement of the method, since for a given applet interface and behavioural formula a maximal applet does not always exist. We therefore propose a two-level approach, where local assumptions restrict the control flow structure of applets, while the global guarantee restricts the control flow behaviour of the system. We present a novel maximal model construction for our logic and then adapt it to applets. By separating the tasks of verifying global and local properties our method supports secure post-issuance loading of applets onto a smart card.

We present the first results of a project called LOOP, on formal methods for the object-oriented language Java. It aims at verification of program properties, with support of modern tools. We use our own front-end tool (which is still partly under construction) for translating Java classes into higher order logic, and a back-end theorem prover (namely PVS, developed at SRI) for reasoning. In several examples we demonstrate how non-trivial properties of Java programs and classes can be proven following this two-step approach.