Software vulnerabilities are ubiquitous and costly. To detect vulnerabilities earlier during development, organizations deploy a set of static analyzers to locate and eventually fix these vulnerabilities before releasing their software. Due to the prohibitive cost of running all available analyzers, organizations must run only a subset of all possible analyzers on their codebases. Choosing this set deterministically leaves recognizable gaps of vulnerability coverage. To overcome these challenges, we present Randomized Best Response (RBR), a method that computes an optimal randomization over size-bounded sets of available static analyzers. RBR models the relationship between malicious users and organizations as a leader-follower Stackelberg security game. Our solution focuses on software vulnerabilities due to their security implications when exploited by malicious users. Using 8 static analyzers for C/C++ and 8 Common Weakness Enumeration (CWE) vulnerability types, we show that RBR outperforms a set of natural baselines by always picking analyzers that achieve a higher benefit to the defender. Through a case study of a large system at Oracle, we show how RBR may be used in a real-world scenario.

Recent methods for visualizing graphs have used a map metaphor: vertices are represented as regions in the plane, and proximity between regions represents edges between vertices.In many real world applications, the data changes over time, resulting in a dynamic map. This paper introduces new methods for representing dynamic graphs with map animation. More specifically, we present three different animation methods: MDSV (Multidimensional scaling - Voronoi), TV (Tutte - Voronoi) and TD (Tutte - dual). These methods support operations such as addition and deletion of vertices and edges. Each of our methods uses a kind of matrix interpolation.

In this paper, we propose a novel method for context-sensitive pointer analysis using the value flow graph (VFG) formulation. We achieve context-sensitivity by simultaneously applying function cloning and computing context-free language reachability (CFL-reachability) in a novel way. In contrast to existing clone-based and CFL-based approaches, flow-sensitivity is easily integrated in our approach by using a flow-sensitive VFG where each value flow edge is computed in a flow-sensitive manner. We apply context-sensitivity to both local variables and heap objects and propose a new approximation for heap cloning.

In this paper, we introduce Parfait, a static bug-checking tool for C/C++ applications. Parfait achieves precision and scalability at the same time by employing a layered program analysis framework. In Parfait, different analyses varying in precision and runtime expense can be invoked on demand to detect defects of a specific type, effectively achieving higher precision with smaller runtime overheads. Several production organizations within Oracle have started to integrate Parfait into their development process. Feedback from various production teams suggests that it is precise and scalable: the tool is able to analyze the OpenSolarisTM operating system and network consolidation (ON) with more than 6 million lines of code in 1 hour, and report thousands of defects with a false positive rate of close to 10%.

Points-to analysis is a fundamental static analysis technique which computes the set of memory objects that a pointer may point to. Many different applications, such as security-related program analyses, bug checking, and analyses of multi-threaded programs, require precise points-to information to be effective. Recent work has focused on improving the precision of points-to analysis through flow-sensitivity and great progress has been made. However, even with all recent progress, flow-sensitive points-to analysis can still be much slower than a flow-insensitive analysis.

Although buffer overflow detection has been studied for more than 20 years, it is still the most common source of security vulnerabilities in systems code. Different approaches using symbolic analysis have been proposed to detect this vulnerability. However, existing symbolic analysis techniques are either too complex to scale to millions of lines of code (MLOC), or too simple to effectively handle loops and complex program structures.

The goal of the Parfait project is to find bugs in C source code in a scalable and precise way. To this end, Parfait was designed as a framework with layers of sound program analyses, multiple layers per bug type, to identify bugs in a program more quickly and accurately.

Parfait is a bug checker of C code that has been designed to address developers' requirements of scalability (support millions of lines of code in a reasonable amount of time), precision (report few false positives) and reporting of bugs that may be exploitable from a security vulnerability point of view. For large code bases, performance is at stake if the bug checking tool is to be integrated into the software development process, and so is precision, as each false alarm (i.e., false positive) costs developer time to track down. Further, false negatives give a false sense of security to developers and testers, as it is not obvious or clear what other bugs were not reported by the tool. A common criticism of existing bug checking tools is the lack of reported metrics on the use of the tool. To a developer it is unclear how accurate the tool is, how many bugs it does not find, how many bugs get reported that are not actual bugs, whether the tool understands when a bug has been fixed, and what the performance is for the reported bugs. In this tool demonstration we show how Parfait fairs in the area of buffer overflow checking against the various requirements of scalability and precision.

Bug-checking tools have been used with some success in recent years to find bugs in software. For finding bugs that can cause security vulnerabilities, bug checking tools require a program analysis which determines whether a software bug can be controlled by user-input. In this paper we introduce a static program analysis for computing user-input dependencies. This analysis can be used as a pre-processing filter to a static bug checking tool for identifying bugs that can potentially be exploited as security vulnerabilities. In order for the analysis to be applicable to large commercial software in the millions of lines of code, runtime speed and scalability of the user-input dependence analysis is of key importance. Our user-input dependence analysis takes both data and control dependencies into account. We extend static single assignment (SSA) form by augmenting phi-nodes with control dependencies. A formal definition of user-input dependence is expressed in a dataflow analysis framework as a meet-over-all-paths (MOP) solution. We reduce the equation system to a sparse equation system exploiting the properties of SSA. The sparse equation system is solved as a reachability problem that results in a fast algorithm for computing user-input dependencies. We have implemented a call-insensitive and a call-sensitive analysis. The paper gives preliminary results on the comparison of their efficiency for various benchmarks.

The Squawk virtual machine is a small Java™ virtual machine (VM) written mostly in Java that runs without an operating system on a wireless sensor platform. Squawk translates standard class file into an internal pre-linked, position independent format that is compact and allows for efficient execution of bytecodes that have been placed into a read-only memory. In addition, Squawk implements an application isolation mechanism whereby applications are represented as object and are therefore treated as first class objects (i.e., they can be reified). Application isolation also enables Squawk to run multiple applications at once with all immutable state being shared between the applications. Mutable state is not shared. The combination of these features reduce the memory footprint of the VM, making it ideal for deployment on small devices.Squawk provides a wireless API that allows developers to write applications for wireless sensor networks (WSNs), this API is an extension of the generic connection framework (GCF). Authentication of deployed files on the wireless device and migration of applications between devices is also performed by the VM.This paper describes the design and implementation of the Squawk VM as applied to the Sun™ Small Programmable Object Technology (SPOT) wireless device; a device developed at Sun Microsystems Laboratories for experimentation with wireless sensor and actuator applications.

A binary translator examines binary code for a source machine and generates code for a target machine. Understanding what to do with delayed branches in binary code can involve tricky case analyses, for example, if there is a branch instruction in a delay slot. This article presents a disciplined method for deriving such case analyses. The method identifies problematic cases, shows the translations for the nonproblematic cases, and gives confidence that all cases are considered. The method supports such common architectures as SPARC, MIPS, and PA-RISC, and it should apply to any tool that analyzes machine instructions. We begin by writing a very simple interpreter for the source machine's code. We then transform the interpreter into an interpreter for a target machine without delayed branches. To maintain the semantics of the program being interpreted, we simultaneously transform the sequence of source-machine instructions into a sequence of target-machine instructions. The transformation of the instructions becomes our algorithm for binary translation.

Translation of assembly code to high-level language code is of importance in the maintenance of legacy code, as well as in the areas of program understanding, porting, and recovery of code. We present techniques used in the asm2c translator, a SPARC assembly to C translator. The techniques involve data and control flow analyses. The data flow analysis eliminates machine dependencies from the assembly code and recovers high-level language expressions. The control flow analysis recovers control structure statements. Simple data type recovery is also done. The presented techniques are extensions and improvements on previously developed CISC techniques. The choice of intermediate representation allows for both RISC and CISC assembly code to be supported by the analyses. We tested asm2c against SPEC95 SPARC assembly programs generated by a C compiler. Results using both unoptimized and optimized assembly code are presented.

Since the 1980s most countries worldwide have introduced laws which extend copyright protection to computer software.In the first Australian case to consider copyright in a shareware computer program distributed on the Internet, the court held that the Internet service provider OzEmail had infringed Trumpet Software's copyright in Trumpet Winsock 2.0B by arranging for the program and a set of altered data files to be distributed with other software on diskette as a give-away inserted in copies of computer magazines.The implications of this case for software developers, distributors, and users are presented.

Program slicing is a technique for determining the set of statements of a program that potentially affect the value of a variable at some point in the program. Intra and interprocedural slicing of high level languages has greatly been studied in the literature; both static and dynamic techniques have been used to aid in the debugging, maintenance, parallelization, program integration, and dataflow testing of programs. We explain how to apply conventional intraprocedural static analysis to binary executables for the purposes of static analysis of machine code and assembly code, such as debugging code and determining the instructions that affect an indexed jump or an indirect call on a register. This analysis is useful in the decoding of machine instructions phase of reverse engineering tools of binary executables, such as binary translators, disassemblers, binary profilers and binary debuggers

The porting of software to newer and faster machines using static binary translation techniques has proved successful to a large extent. Current binary translators are static in nature and require a runtime environment to successfully support the execution of the translated programs on the new machine. On the other hand, dynamic binary translation has not been considered as an alternative to static translation-the authors argue that these translators can achieve at least the same performance as static translators but will require a simpler runtime environment. The paper presents techniques used to migrate legacy software running on register-based machines of the last 10 to 15 years to modern RISC machines. They have developed a second-generation disassembler to aid in the construction of a retargetable binary translation front-end. Retargetability of binary translators is on issue that has nor been addressed in present translators.

We present the main recommendations of the Copyright Law Review Committee in its submission to the Australian Government in 1995 in relation to the protection of computer software in Australia and the intellectual property of software developers in this country. The implications of these recommendations to the academic and industry computer science community are presented, as well as comparisons with European and US legislation.

Reverse engineering of software systems has traditionally centered upon the generation of high level abstractions or specifications from high level code or databases. We report on a reverse engineering environment for low level executable code: a reverse compilation or decompilation environment that aids in the understanding of the underlying executable program. The reverse compilation process recovers high level code from executable programs at a higher representation level than that produced by disassemblers; in fact, disassembly is part of the first stage in this process. Several tools aid in the process of reverse compilation, these are: loaders, signature generators, library prototype generators, disassemblers, library bindings, and language to language translators. The integration of these tools in the whole process is presented in this paper. The results obtained by the prototype reverse compilation system dcc are encouraging: high level code is regenerated with correct use of expressions and control structures, and the complete elimination of registers and condition codes. An elimination rate of low level instructions of over 75% was reached, representing the overall improvement this decompiler system has made over previous decompilers and disassemblers (where the rate tends to be nil). A sample decompilation program is given.

Abstract The structure of a decompiler is presented, along with a thorough description of the different modules that form part of a decompiler, and the type of analyses that are performed on the machine code to regenerate high‐level language code. The phases of the decompiler have been grouped into three main modules: front‐end, universal decompiling machine, and back‐end. The front‐end is a machine‐dependent module that performs the loading, parsing and semantic analysis of the input program, as well as generating an intermediate representation of the program. The universal decompiling machine is a machine‐ and language‐independent module that performs data and control flow analysis of the program based on the intermediate representation, and the program's control flow graph. The back‐end is a language‐dependent module that deals with the details of the target high‐level language. In order to increase the readability of the generated programs, a decompiling system has been implemented which integrates a decompiler, dcc, and an automatic signature generator, dccSign. Signatures for libraries and compilers are stored in a database that is read by the decompiler; thus, the generated programs can make use of known library names, such as WriteLn() and printf(). dcc is a decompiler for the Intel 80286 architecture and the DOS operating system. dec takes as input binary programs from a DOS environment and generates C programs as output. Sample code produced by this decompiler is given.