Abstract Well-designed data structures are fundamental to the construction of robust programs, particularly when their correctness can be established using formal methods. Currently, various successful deductive verification techniques exist but necessitate distinct and non-interoperable specifications and verification methods for data structure implementations. This paper presents a technique enabling cross-paradigm interoperable specification and verification of encapsulated data structures. The novel approach builds on the shared mathematical foundations of algebraic data types (ADTs) across these diverse methodologies. The technique enables the coherent integration of components that have been verified using different deductive program verification approaches within a single project, provided that a regime of encapsulation is followed, which is slightly stricter than those originally imposed by the verification techniques. We formally introduce and discuss the encapsulation principle using a simplified conceptual object-oriented language and subsequently instantiate it for the Java programming language. This integrates the approaches of KeY, VeriFast, and Universe Types, thereby enabling heterogeneous verification projects in Java that encompass Dynamic Frames, Separation Logic, and Ownership Types. We demonstrate the applicability of our approach by conducting a cooperative verification of a client with three different data structures, each of which is verified with one of the aforementioned techniques.

Main-stream type systems do not prevent errors such as null-pointer exceptions, security problems, and con-currency errors. Optional Properties (Opprop) or pluggable type systems provide frameworks where users can guarantee a particular property holds with the help of a customizable type checker. Type annotations are used to specify a property, e.g., whether a reference can be null or not, and custom type rules enforce that property. However, manually inserting these type annotations for new and existing large projects requires a lot of human effort. Inference systems provide a constraint-based whole-program inference framework. However, thoroughly understanding the underlying framework to develop such a system is time-consuming. Furthermore, these frameworks make expensive calls to SAT and SMT solvers, which increases the runtime overhead during inference. Type system developers write test cases to ensure their type checker covers all the necessary type rules and works as expected. Our core idea is to leverage these manually written test cases along with the type checker to create a Deep Learning model to learn the type rules implicitly using a data-driven approach to automatically infer annotations for programs. We present a novel model, OppropBERL, which takes as input a Java program to predict the appropriate type annotations for a given type system. The pre-trained Transformer model helps encode the code tokens without specifying the programming language's grammar, including the type rules. In the presence of a type checker, the model can be refined further using a reinforcement learning (RL) technique. With comprehensive ex-periments, we establish the efficacy of OppropBERL for null ness and ownership annotation prediction tasks by comparing against 8 different tools on publicly available Java projects with around 240K lines of code.

We address least-privilege in a particular context of public cloud computing: calls to Amazon Web Services (AWS) Application Programming Interfaces (APIs). AWS is, by far, the largest cloud provider, and therefore an important context in which to consider the fundamental security design principle of least-privilege, which states that a thread of execution should possess only those privileges it needs. There have been reports of over-privilege being a root cause of attacks against AWS cloud applications, and a least-privilege set for an API call is a necessary building-block in devising a least-privilege policy for a cloud application. We observe that accurate information on a least-privilege set for an invoker of a method to possess is simply not available for most such methods in AWS. We provide a meaningful characterization of least-privilege in this context. We then propose techniques to determine such sets, and discuss a black-box process we have devised and carried out to identify such sets for all 707 API methods we are able to invoke across five AWS services. We discuss a number of interesting discoveries we have made, some of which are surprising and some alarming, that we have reported to AWS. Our work has resulted in a database of least-privilege sets for API calls to AWS, which we make available publicly. Developers can consult our database when configuring security policies for their cloud applications, and we welcome contributors that augment our database. Also, we discuss example uses of our database via an assessment of two repositories and two full-fledged serverless applications that are available publicly and have policies published alongside. We observe that the vast majority of policies are over-privileged. Our work contributes constructively to securing cloud applications in the largest cloud provider.

Using cryptographic APIs to encrypt and decrypt data, calculate digital signatures, or compute hashes is error prone. Weak or unsupported cryptographic algorithms can cause information leakage and runtime exceptions, such as a NoSuchAlgorithmException in Java. Using the wrong cryptographic service provider can also lead to unsupported cryptographic algorithms. Moreover, for Android developers who want to store their key material in the Android Keystore, misused cryptographic algorithms and providers make the key material unsafe.

Type systems and modern type checkers can be used very successfully to obtain formal correctness guarantees with little specification overhead. However, type systems in practical scenarios have to trade precision for decidability and scalability. Tools for deductive verification, on the other hand, can prove general properties in more cases than a typical type checker can, but they do not scale well. We present a method to complement the scalability of expressive type systems with the precision of deductive program verification approaches. This is achieved by translating the type uses whose correctness the type checker cannot prove into assertions in a specification language, which can be dealt with by a deductive verification tool. Type uses whose correctness the type checker can prove are instead turned into assumptions to aid the verification tool in finding a proof.Our novel approach is introduced both conceptually for a simple imperative language, and practically by a concrete implementation for the Java programming language. The usefulness and power of our approach has been evaluated by discharging known false positives from a real-world program and by a small case study.

Ensuring computations are unit-wise consistent is an important task in software development. Numeric computations are usually performed with primitive types instead of abstract data types, which results in very weak static guarantees about correct usage and conversion of units. This paper presents PUnits, a pluggable type system for expressive units of measurement types and a precise, whole-program inference approach for these types. PUnits can be used in three modes: (1) modularly check the correctness of a program, (2) ensure a possible unit typing exists, and (3) annotate a program with units. Annotation mode allows human inspection and is essential since having a valid typing does not guarantee that the inferred specification expresses design intent. PUnits is the first units type system with this capability. Compared to prior work, PUnits strikes a novel balance between expressiveness, inference complexity, and annotation effort. We implement PUnits for Java and evaluate it by specifying the correct usage of frequently used JDK methods. We analyze 234k lines of code from eight open-source scientific computing projects with PUnits. We compare PUnits against an encapsulation-based units API (the javax.measure package) and discovered unit errors that the API failed to find. PUnits infers 90 scientific units for five of the projects and generates well-specified applications. The experiments show that PUnits is an effective, sound, and scalable alternative to using encapsulation-based units APIs, enabling Java developers to reap the performance benefits of using primitive types instead of abstract data types for unit-wise consistent scientific computations.

Implicit or indirect control flow is a transfer of control between procedures using some mechanism other than an explicit procedure call. Implicit control flow is a staple design pattern that adds flexibility to system design. However, it is challenging for a static analysis to compute or verify properties about a system that uses implicit control flow. This paper presents static analyses for two types of implicit control flow that frequently appear in Android apps: Java reflection and Android intents. Our analyses help to resolve where control flows and what data is passed. This information improves the precision of downstream analyses, which no longer need to make conservative assumptions about implicit control flow. We have implemented our techniques for Java. We enhanced an existing security analysis with a more precise treatment of reflection and intents. In a case study involving ten real-world Android apps that use both intents and reflection, the precision of the security analysis was increased on average by two orders of magnitude. The precision of two other downstream analyses was also improved.

Current app stores distribute some malware to unsuspecting users, even though the app approval process may be costly and time-consuming. High-integrity app stores must provide stronger guarantees that their apps are not malicious. We propose a verification model for use in such app stores to guarantee that the apps are free of malicious information flows. In our model, the software vendor and the app store auditor collaborate -- each does tasks that are easy for her/him, reducing overall verification cost. The software vendor provides a behavioral specification of information flow (at a finer granularity than used by current app stores) and source code annotated with information-flow type qualifiers. A flow-sensitive, context-sensitive information-flow type system checks the information flow type qualifiers in the source code and proves that only information flows in the specification can occur at run time. The app store auditor uses the vendor-provided source code to manually verify declassifications.

Program verification is the only way to be certain that a given piece of software is free of (certain types of) errors --- errors that could otherwise disrupt operations in the field. To date, formal verification has been done by specially-trained engineers. Labor costs have heretofore made formal verification too costly to apply beyond small, critical software components.

Regular expressions are used to match and extract text. It is easy for developers to make syntactic mistakes when writing regular expressions, because regular expressions are often complex and different across programming languages. Such errors result in exceptions at run time, and there is currently no static support for preventing them.

Reference immutability ensures that a reference is not used to modify the referenced object, and enables the safe sharing of object structures. A pure method does not cause side-effects on the objects that existed in the pre-state of the method execution. Checking and inference of reference immutability and method purity enables a variety of program analyses and optimizations. We present ReIm, a type system for reference immutability, and ReImInfer, a corresponding type inference analysis. The type system is concise and context-sensitive. The type inference analysis is precise and scalable, and requires no manual annotations. In addition, we present a novel application of the reference immutability type system: method purity inference.

This paper describes practical experience building and using pluggable type-checkers. A pluggable type-checker refines (strengthens) the built-in type system of a programming language. This permits programmers to detect and prevent, at compile time, defects that would otherwise have been manifested as run-time errors. The prevented defects may be generally applicable to all programs, such as null pointer dereferences. Or, an application-specific pluggable type system may be designed for a single application.

Energy is increasingly a first-order concern in computer systems. Exploiting energy-accuracy trade-offs is an attractive choice in applications that can tolerate inaccuracies. Recent work has explored exposing this trade-off in programming models. A key challenge, though, is how to isolate parts of the program that must be precise from those that can be approximated so that a program functions correctly even as quality of service degrades.

Ownership is a powerful concept to structure the object store and to control aliasing and modifications of objects. This article presents an ownership type system for a Java-like programming language with generic types. Like our earlier Universe type system, Generic Universe Types structure the heap hierarchically. In contrast to earlier work, we separate the enforcement of an ownership topology from an encapsulation system. The topological system uses an existential modifier to express that no ownership information is available statically. On top of the topological system, we build an encapsulation system that enforces the owner-as-modifier discipline. This discipline does not restrict aliasing, but requires modifications of an object to be initiated by its owner. This allows owner objects to control state changes of owned objects—for instance, to maintain invariants. Separating the topological system from the encapsulation system allows for a cleaner formalization, separation of concerns, and simpler reuse of the individual systems in different contexts.

We propose the use of random wavelet packet decompositions as a way to increase the security of watermarking systems against unauthorized removal attacks. Experimental attacks based on coefficient quantization show that using a secret key-dependent subband structure to hide the watermarking domain significantly increases the watermark correlation under an attack as compared to a classical pyramidal wavelet watermark.