Perfect pre-deployment test coverage is notoriously difficult to achieve for large applications. Given enough end users, however, many more test cases will be encountered during an application's deployment than during testing. The use of runtime verification after deployment would enable developers to detect unexpected situations. Unfortunately, the prohibitive performance cost of runtime monitors prevents their use in deployed code. In this work, we study the feasibility of collaborative runtime verification, a verification approach which can distribute the burden of runtime verification among multiple users and over multiple runs. Each user executes a partially instrumented program and therefore suffers only a fraction of the instrumentation overhead. We focus on runtime verification using tracematches. Tracematches are a specification formalism that allows users to specify runtime verification properties via regular expressions with free variables over the dynamic execution trace. We propose two techniques for soundly partitioning the instrumentation required for tracematches: spatial partitioning, where different copies of a program monitor different program points for violations, and temporal partitioning, where monitoring is switched on and off over time. We evaluate the relative impact of partitioning on a user's runtime overhead by applying each partitioning technique to a collection of benchmarks that would otherwise incur significant instrumentation overhead. Our results show that spatial partitioning almost completely eliminates runtime overhead (for any particular benchmark copy) on many of our test cases, and that temporal partitioning scales well and provides runtime verification on a ‘pay as you go’ basis.

Precise, flow-sensitive analyses of pointer relationships often represent each object using the set of local variables that point to it (the alias set), possibly augmented with additional predicates. Many such analyses are difficult to scale due to the size of the abstraction and due to flow sensitivity. The focus of this paper is on efficient representation and manipulation of the alias set. Taking advantage of certain properties of static single assignment (SSA) form, we propose an efficient data structure that allows much of the representations of sets at different points in the program to be shared. The transfer function for each statement, instead of creating an updated set, makes only local changes to the existing data structure representing the set. The key enabling properties of SSA form are that every point at which a variable is live is dominated by its definition, and that the definitions of any set of simultaneously live variables are totally ordered according to the dominance relation. We represent the variables pointing to an object using a list ordered consistently with the dominance relation. Thus, when a variable is newly defined to point to the object, it need only be added to the head of the list. A back edge at which some variables cease to be live requires only dropping variables from the head of the list. We prove that the analysis using the proposed data structure computes the same result as a set-based analysis. We empirically show that the proposed data structure is more efficient in both time and memory requirements than set implementations using hash tables and balanced trees.

This paper presents a static analysis of typestate-like temporal specifications of groups of interacting objects, which are expressed using tracematches. Whereas typestate expresses a temporal specification of one object, a tracematch state may change due to operations on any of a set of related objects bound by the tracematch. The paper proposes a lattice-based operational semantics equivalent to the original tracematch semantics but better suited to static analysis. The paper defines a static analysis that computes precise local points-to sets and tracks the flow of individual objects, thereby enabling strong updates of the tracematch state. The analysis has been proved sound with respect to the semantics. A context-sensitive version of the analysis has been implemented as instances of the IFDS and IDE algorithms. The analysis was evaluated on tracematches used in earlier work and found to be very precise. Remaining imprecisions could be eliminated with more precise modeling of references from the heap and of exceptional control flow.

Java developers often use decompilers to aid reverse engineering and obfuscators to prevent it. Decompilers translate low-level class files to Java source and can produce "good" output. Obfuscators transform class files into semantically-equivalent versions that are either: (1) difficult to decompile, or (2) decompilable, but result in "hard- to-understand" Java source. We present a set of metrics developed to quantify the effectiveness of decompilers and obfuscators. The metrics include some selective size and counting metrics and an expression complexity metric. We have applied these metrics to evaluate a collection of decompilers and obfuscators. By quantitatively comparing original Java source against decompiled and obfuscated code respectively, we show which decompilers produce "good" code and whether obfuscations result in "hard-to-understand" code.

Java decompilers convert Java class files to Java source. Java class files may be created by a number of different tools including standard Java compilers, compilers for other languages such as AspectJ, or other tools such as optimizers or obfuscators. There are two kinds of Java decompilers, Javac-specific decompilers that assume that the class file was created by a standard Javac compiler and tool-independent decompilers that can decompile arbitrary class files, independent of the tool that created the class files. Typically Javac-specific decompilers produce more readable code, but they fail to decompile many class files produced by other tools. This paper tackles the problem of how to make a tool-independent decompiler, Dava, produce Java source code that is programmer-friendly. In past work it has been shown that Dava can decompile arbitrary class files, but often the output, although correct, is very different from what a programmer would write and is hard to understand. Furthermore, tools like obfuscators intentionally confuse the class files and this also leads to confusing decompiled source files. Given that Dava already produces correct Java abstract syntax trees (ASTs) for arbitrary class files, we provide a new back-end for Dava. The back-end rewrites the ASTs to semantically equivalent ASTs that correspond to code that is easier for programmers to understand. Our new back-end includes a new AST traversal framework, a set of simple pattern-based transformations, a structure-based data flow analysis framework and a collection of more advanced AST transformations that use flow analysis information. We include several illustrative examples including the use of advanced transformations to clean up obfuscated code

Laboratory information systems (LIMS) are used in life science research to manage complex experiments. Since LIMS systems are often shared by different research groups, powerful access control is needed to allow different access rights to different records of the same table. Traditional access control models that define a permission as the right of a user/role to perform a specific operation on a specific object cannot handle the enormous amount of objects and user/roles. In this paper, we propose an enhancement to role-based access control by introducing conditions that can be added to the traditional concept of permissions in order to keep the number of permissions small. Furthermore, we present an implementation of our access control model at the application programming level. Although access control is performed for every single database access, our solution completely separates access control from the application logic by using aspect-oriented programming. With this, access control can be integrated into a legacy 3-tier information system without changing the application programs.