Disassembly is the first step of a variety of binary analysis and transformation techniques, such as reverse engineering, or binary rewriting. Recent disassembly approaches consist of three phases: an exploration phase, that overapproximates the binary's code; an analysis phase, that assigns weights to candidate instructions or basic blocks; and a conflict resolution phase, that downselects the final set of instructions. We present a disassembly algorithm that generalizes this pattern for a wide range of architectures, namely x86, x64, arm32, and aarch64. Our algorithm presents a novel conflict resolution method that reduces disassembly to weighted interval scheduling. Additionally, we present a weight assignment algorithm that allows us to learn optimal weights for the various disassembly heuristics in the analysis phase. Learned weights outperform manually tuned weights in most cases while reducing the number of necessary heuristics by 40% (by setting their weights to zero). Our implementation, built on top of Ddisasm, outperforms state-of-the-art disassemblers in several metrics and achieves the largest proportion of perfectly disassembled binaries by a wide margin in all evaluated datasets.

This article considers some known abstract domains for affine-relation analysis (ARA), along with several variants, and studies how they relate to each other. The various domains represent sets of points that satisfy affine relations over variables that hold machine integers and are based on an extension of linear algebra to modules over a ring (in particular, arithmetic performed modulo 2 w , for some machine-integer width w ). We show that the abstract domains of Müller-Olm/Seidl (MOS) and King/Søndergaard (KS) are, in general, incomparable. However, we give sound interconversion methods. In other words, we give an algorithm to convert a KS element v KS to an overapproximating MOS element v MOS —that is, γ ( v KS ) ⊆ γ ( v MOS —as well as an algorithm to convert an MOS element w MOS to an overapproximating KS element w KS —that is, γ ( w MOS ) ⊆ γ ( w KS ). The article provides insight on the range of options that one has for performing ARA in a program analyzer: —We describe how to perform a greedy, operator-by-operator abstraction method to obtain KS abstract transformers. —We also describe a more global approach to obtaining KS abstract transformers that considers the semantics of an entire instruction, basic block, or other loop-free program fragment. The latter method can yield best abstract transformers, and hence can be more precise than the former method. However, the latter method is more expensive. We also explain how to use the KS domain for interprocedural program analysis using a bit-precise concrete semantics, but without bit blasting.

This article describes the design and implementation of a system, called T SL (for Transformer Specification Language), that provides a systematic solution to the problem of creating retargetable tools for analyzing machine code. T SL is a tool generator---that is, a metatool---that automatically creates different abstract interpreters for machine-code instruction sets. The most challenging technical issue that we faced in designing T SL was how to automate the generation of the set of abstract transformers for a given abstract interpretation of a given instruction set. From a description of the concrete operational semantics of an instruction set, together with the datatypes and operations that define an abstract domain, T SL automatically creates the set of abstract transformers for the instructions of the instruction set. T SL advances the state-of-the-art in program analysis because it provides two dimensions of parameterizability: (i) a given analysis component can be retargeted to different instruction sets; (ii) multiple analysis components can be created automatically from a single specification of the concrete operational semantics of the language to be analyzed. T SL is an abstract-transformer-generator generator . The article describes the principles behind T SL , and discusses how one uses T SL to develop different abstract interpreters.

Multicore technology is making concurrent programs increasingly pervasive. Unfortunately, it is difficult to deliver reliable concurrent programs, because of the huge and nondeterministic interleaving space. In reality, without the resources to thoroughly check the interleaving space, critical concurrency bugs can slip into production versions and cause failures in the field. Approaches to making the best use of the limited resources and exposing severe concurrency bugs before software release would be desirable. Unlike previous work that focuses on bugs caused by specific interleavings (e.g., races and atomicity violations), this article targets concurrency bugs that result in one type of severe effect: program crashes. Our study of the error-propagation process of real-world concurrency bugs reveals a common pattern (50% in our nondeadlock concurrency bug set) that is highly correlated with program crashes. We call this pattern concurrency-memory bugs: buggy interleavings directly cause memory bugs (NULL-pointer-dereferences, dangling-pointers, buffer-overflows, uninitialized-reads) on shared memory objects. Guided by this study, we built ConMem to monitor program execution, analyze memory accesses and synchronizations, and predictively detect these common and severe concurrency-memory bugs. We also built a validator,ConMem-v, to automatically prune false positives by enforcing potential bug-triggering interleavings. We evaluated ConMem using 7 open-source programs with 10 real-world concurrency bugs. ConMem detects more tested bugs (9 out of 10 bugs) than a lock-set-based race detector and an unserializable-interleaving detector, which detect 4 and 6 bugs, respectively, with a false-positive rate about one tenth of the compared tools. ConMem-v further prunes out all the false positives. ConMem has reasonable overhead suitable for development usage.

Concurrency bugs are caused by non-deterministic interleavings between shared memory accesses. Their effects propagate through data and control dependences until they cause software to crash, hang, produce incorrect output, etc. The lifecycle of a bug thus consists of three phases: (1) triggering, (2) propagation, and (3) failure.

The goal of our work is to create tools that an analyst can use to understand the workings of COTS components, plugins, mobile code, and DLLs, as well as memory snapshots of worms and virus-infected code. This paper describes how static analysis provides techniques that can be used to recover intermediate representations that are similar to those that can be created for a program written in a high-level language.

In this paper, we propose a novel, application specific demand paging mechanism for low-end embedded systems with flash memory as secondary storage. These systems are not equipped with virtual memory. A small memory space called an execution buffer is allocated to page an application. An application-specific page manager manages the buffer. The manager is generated by a compiler post-pass and combined with the application image. Our compiler post-pass analyzes the ELF executable image of an application and transforms function call/return instructions into calls to the page manager. As a result, each function of the code can be loaded into memory on demand at run time. To minimize the overhead of demand paging, code clustering algorithms are also presented. We evaluate our techniques with five embedded applications. We show that our approach can reduce the code memory size by 33% on average with reasonable performance degradation (8-20%) and energy consumption (10% more on average) for low-end embedded systems.