SOURCE ARCHIVE
EXTRACTED CONTENT
78,161 charsStructured Random Differential Testing of Instruction Decoders
Nathan Jay Barton P. Miller
Computer Sciences Department Computer Sciences Department University of Wisconsin University of Wisconsin Madison, WI 53706 USA Madison, WI 53706 USA nholcomb@wisc.edu bart@cs.wisc.edu
Abstract—Decoding binary executable files is a critical facility bottlenecks can be obscured, and sandboxing untrusted code for software analysis, including debugging, performance monitor- can be faulty. Consider the output of Intel’s decoder for the ing, malware detection, cyber forensics, and sandboxing, among x86 architecture, XED [12] (version 6.26.0) for the bytes CA other techniques. As a foundational capability, binary decoding 48 0C. These bytes should correspond to instruction lretl must be consistently correct for the techniques that rely on it to be viable. Unfortunately, modern instruction sets are huge and 0xc48 (a function return instruction), but XED produces the encodings are complex, so as a result, modern binary decoders lcallq 0xc48 (a function call instruction). These outputs are buggy. In this paper, we present a testing methodology that have different implications for control flow, and this error will automatically infers structural information for an instruction set result in an incorrect control flow graph. Thorough testing of and uses the inferred structure to efficiently generate structured- random test cases independent of the instruction set being tested. instruction decoders is essential to understanding binary code. Our testing methodology includes automatic output verification High accuracy of an instruction decoder is difficult to using differential analysis and reassembly to generate error achieve due to the enormous complexity of modern instruction reports. This testing methodology requires little instruction- sets. Although manuals detailing early x86 processors are as set-specific knowledge, allowing rapid testing of decoders for short as 200 pages, modern manuals for x86 are thousands of new architectures and extensions to existing ones. We have implemented our testing procedure in a tool name Fleece and pages long [11]. Even manuals for RISC ISAs like PowerPC used it to test multiple binary decoders (Intel XED, libopcodes, and ARM exceed a thousand pages [3], [10]. These pages LLVM, Dyninst and Capstone) on multiple architectures (x86, detail hundreds of opcodes, many addressing modes, and a ARM and PowerPC). Our testing efficiently covered thousands myriad of restrictions on instruction fields or combinations of of instruction format variations for each instruction set and fields. Just determining which bits contribute to the opcode of uncovered decoding bugs in every decoder we tested. an instruction is challenging because many bits not explicitly I. INTRODUCTION included in the opcode of an instruction can still change it, or even invalidate the instruction. Many PowerPC and ARM Instruction decoding is the process taking the binary repre- instructions have reserved fields whose bits are specific to the sentation of a machine instruction and decomposing it into its opcode. Changing these fields invalidates the instruction or basic fields. As part of this decomposition, a decoder needs alters the opcode. The operation of x86 instructions depend to identify the opcode, the operands and their types, qualifiers not only on the 1-3 byte opcode, but also on prefixes and to the opcode and operands, and any address calculations that even fields within prefixes, as with EVEX instructions. Our might be used for the operands. While instruction decoding automated testing framework is able to detect which subsets of is essentially a syntactic operation, it provides information the bits in an instruction encode the operation of an instruction; necessary to support control- and data-flow of the code, and we found that hundreds of different sets encode the operation to understand instruction semantics. of PowerPC and ARM instructions, and thousands of sets of Instruction decoding is the first step for any tool that bits encode the operation of x86 instructions. operates on binary code, so represents a critical feature needed The complexity of modern instruction sets has resulted for these tools. Tools that operate on binary code include disas- in numerous errors in the decoding tools for x86, PowerPC semblers [2], [4], [12], [14], [21], reverse engineering tools [5], and ARM, highlighting the need for comprehensive testing. [9], [16], binary rewriters [4], [18], dynamic instrumentors [4], Unfortunately, comprehensive testing of instruction decoders [13], [22], performance profiling tools [1], [4], and security is challenging for two reasons. First, test inputs must be analysis tools [7], [20]. selected from the input space that maximize the number of Accurate instruction decoding of an instruction is essential errors found while minimizing the number of inputs that to the correct operation of the tools that are built on top of must be tested. ARMv8 and PowerPC both use 4-byte, fixed- the decoder. Incorrect decoding can cause these tools to be length instructions, so their decoders must correctly decode useless or even dangerous. For example, in the presence of more than 4 billion inputs. Decoders for x86 need to decode decoding errors, control flow can be misleading, performance variable-length instructions up to 15 bytes long, resulting in
978-1-5386-4969-5/18 c 84 SANER 2018, Campobasso, Italy
© 2018 IEEE Technical Research Papers
Accepted for publication by IEEE. ©c 2018 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
2120 possible inputs. A brute force approach to comprehensive II. RELATED WORK
testing is impractical and requires careful consideration of test instructions. Second, the assembly language output of each Several testing techniques provide a foundation for our decoder needs to be verified for every input. Given the size of work, including structured random input generation for fuzz the input space, this verification requires an automated method testing [8], [19] and differential testing of instruction decoders with ground-truth decoding for all input bytes. [17]. Existing work has recognized the complexity of modern While fuzz testing has been effective at finding bugs using ISAs and challenges in testing instruction decoders, seeking unstructured, pseudorandom input [15], using structured input to quantify issues with instruction decoder accuracy through has been used to provide greater coverage in a short period of differential testing. In 2010, Paleari et al [17] compared the time for certain tools [8]. outputs of eight x86 decoders when used to decode a mixture of random and known-valid inputs. Paleari’s work introduced Model-based input generation has been applied to x86 random differential testing for instruction decoders; however, instructions because instructions contain multiple distinct com- it was specific to x86 and leveraged detailed knowledge of ponents that can be used in combination, including prefixes, the ISA to generate known-valid test cases. Additionally, this opcodes, and modifier bits. This was explored by Seidel [19], work required extensive normalization functions to compare modeling instructions as graphs, with each node representing the output of different decoders. While the work by Paleari a byte of the instruction. In their technique, instructions start used mostly random inputs, results from other testing domains as an empty string of bytes and new bytes are appended as have shown that information about input structure can be used the graph is traversed with edges leading from the current byte to generate inputs that improve code coverage [8], [23]. of the instruction to each valid following byte, according to In this paper, we introduce a framework that provides a configurable probability. This approach can generate valid several benefits over existing tests: instructions with a specified distribution of instruction set • Inferred Input Structure: We automatically infer encoding features like prefixes and modifiers. However, this approach information using only knowledge of the register sets but requires extensive knowledge of the instruction set, and is only not a model of the ISA, significantly reducing the expert applicable to ISAs where instruction set features correspond knowledge required to test decoders. to contiguous bits (or bytes) that can be concatenated to create • Error Verification: Our framework uses reassembly to a valid instruction. In many RISC architectures like Arm and verify that differences in decoder output correspond to PowerPC, instructions are all 4 bytes whose individual bytes errors in decoding. This process vastly reduces the effort do not specify independent parts of the instruction, and whose required to analyze output and identify underlying issues parts are not all contiguous. in the decoders we test. Paleari et al introduced CPU execution as a way to generate • ISA Agnostic Testing: Our framework makes few assump- valid inputs for instruction decoders [17]. Their approach, tions about the structure of instructions, allowing us to again specific to x86, takes advantage of the structure of test decoders for x86, PowerPC and ARM (and others instructions to test all possible 1-3 byte opcodes. The authors in the future) within a single framework. Other testing executed one instruction for each possible value of the first methods make assumptions that restrict them to a single three bytes to obtain a list of valid 1-3 byte opcodes. Then, ISA, or even a specific version of an ISA. using a list of valid prefixes, they created test instructions We applied our testing methodology and tools to a wide by prepending prefixes to each of the valid opcodes. This variety of decoders, including Capstone [2], Dyninst [4], method produced valid instructions with a variety of opcodes libopcodes [21], LLVM [14], and XED [12], on a variety of to provide better coverage of the tested instruction set than architectures including x86 (32 and 64 bit), PowerPC (32 and a purely random approach. Unfortunately, this approach is 64 bit), and ARM (64 bit). Our experience has shown these specific to x86, and it assumes that the list of valid prefixes is tools (including those from the processor manufacturer and straightforward for a programmer to enumerate. New EVEX those from our own project) to be disturbingly buggy. Across instructions in x86 violate this assumption with complex 3- all decoders, testing encountered dozens of errors that varied byte prefixes that contain information about registers and in- significantly including segmentation faults, incorrect opcodes, struction operation. This method requires the tool to explicitly incorrect number of operands, invalid operand sizes, invalid define features of the instruction set (in the form of valid use of restricted registers and missing opcodes. We reported prefixes) and relies on 1-3 byte opcodes whose validity is all of the decoding errors we identified to the developers of independent of any prefixes. these tools and many have been confirmed and fixed. Unlike methods of that require knowledge of the instruction In Section 2, we provide background on existing instruction set to create test cases, grammar-based input generation can decoder testing. Section 3 describes the complexity of modern use symbolic execution and a pre-defined grammar to construct ISAs, Section 4 presents the testing procedure, Section 5 valid inputs [8]. This approach increases code coverage when presents an evaluation of Fleece, our tool that implements our compared to purely random approach, but also requires knowl- structured random testing procedure, testing several popular edge of the structure of inputs (in the form of a grammar) to instruction decoders. We conclude in Section 6. generate test cases.
85
In addition to detecting failures, our work also seeks to set of bits used to encode the opcode, each ISA has many verify the test results. Unfortunately, the specification of encoding variations that differ from their common opcode instruction decoding requires lengthy manuals with thousands encoding. Every PowerPC instruction uses at least the first of pages [3], [10], [11]. Verifying a single output by hand 6 bits to encode the opcode; many x86 instructions have requires lookups in several tables detailing the meaning of common encodings based on the prefixes present; and, ARM different bits, and sometimes referencing multiple manuals, a instructions often use bits 1-6 for the opcode. Despite common process that can introduce errors. Differential testing provides opcode-encoding bits in each ISA, a scattering of extra opcode a way to detect likely errors by comparing the output of several bits, reserved bits and fields that affect the opcode cause the instruction decoders and only producing error reports where total number of opcode-encoding subsets to explode. In total, the outputs differ. This technique was used by Paleari et al to we identified 279 different subsets of bits that encode ARMv8 quantify the number of errors in existing instruction decoders opcodes, 124 subsets that encode PowerPC opcodes and 2900 [17]. In their work, the authors use eight x86 decoders in subsets for x86 opcodes. Each ISA has characteristics that conjunction with execution on a CPU to identify cases where contribute to this complexity. For example, both ARM and the decoders differ, signifying a probable error. PowerPC contain opcodes that are valid only when certain Ideally, this differential testing would yield no false posi- values are supplied for operands, adding those operand bits to tives: every difference in the output of decoders would corre- the subset that affects the opcode, and the use of prefixes in spond to an error in at least one of the decoders. Unfortunately, x86 can shift and modify which bits encode the opcode. instruction decoders do not produce a single, uniform output. Multi-purpose operand values: Once the bits encoding an Even when configured to produce the same syntax, outputs operand are identified, the operand may have several meanings from different instruction decoders can vary significantly. based on other parts of the instruction. For example, x86 Paleari et al used nearly 100 functions to normalize the outputs instructions accessing a register encoded by the value ”001” of all decoders into one standard representation. Still, they might be accessing one of 10 different registers, where the found that some instructions marked as errors actually corre- register accessed is determined by prefixes, operand size, sponded to trivial formatting differences between instruction and other modifier bits scattered throughout the instruction. decoders, rather than an error. Our approach to normalization ARMv8 instructions also use multi-purpose operand encodings uses an assembler to detect equivalent decodings, significantly where the meaning of an operand encoding depends on the reducing the number of normalization functions. opcode. The DERIVE system [6] introduced the use of assemblers Undefined and illegal instructions: Determining whether an combined with a list of opcodes, registers and special in- instruction is valid and defined is difficult even if the opcode struction format strings to derive the encoding of instructions. is known because many factors can cause an instruction to be DERIVE’s instruction format strings specified which field in undefined or illegal. These factors include prefixes, addressing assembly language is the opcode, which are registers, and modes, interacting operand values and even unallocated bits. which are immediates. They then created assembly language For example, x86 instructions are illegal if they contain a instructions with permutations of opcodes, fields and imme- lock prefix but do not contain a memory operand. Both ARM diates, assembling each instruction. Using a series of con- and PowerPC have instructions that may be invalid because straint solvers, they determined which bits of the instruction of a combination of separate fields, like SIMD register loads correspond to which fields, as well as appropriate decoding whose range of destination registers cannot contain the source procedure. Unfortunately, modern ISAs violate several of the register. In these cases, only a synthesis of information from assumptions of this work, including: multiple binary instruc- different fields of the instruction can determine whether it will tions decode to the same assembly instruction, immediates be valid and defined. are not always represented in assembly as they appear in the binary, instruction fields are not always independent, and Instruction Set Churn: Since its creation, x86 has had not all immediate operands are contiguous. Conversely, our at least 13 extensions (depending on how you count) and approach modifies the binary encoding of instructions and now contains hundreds of opcodes, most of which were not uses decoders to derive similar structural information about present initially [11]. Likewise, both ARM and PowerPC have instructions without any outside information other than the undergone significant revisions since their creation [3], [10]. maximum length of instructions. Each revision or extension requires an updated decoder. Addi- tionally, extensions can produce new interactions between op- III. INSTRUCTION SET COMPLEXITY codes and operands that might affect existing instructions. The As introduced in Section 1, modern instruction sets are result is noticeable in differential testing: the GNU decoder complex, and the challenges of implementing correct instruc- incompletely deprecated 3DNow!, and Dyninst maintained old tion decoders are a direct reflection of this complexity. In this versions of PowerPC decodings from POWER 2 that conflict section, we try to quantify instruction set complexity. with a more recent vector extension. Complex opcode encoding: Opcodes can depend on many These instruction set complexities have resulted in numer- parts of an instruction, and even determining which bits encode ous errors in the decoding tools for x86, PowerPC and ARM, the opcode is difficult. While an ISA often has a common highlighting the need for comprehensive testing.
86
IV. TESTING PROCEDURE 1011010011011111: movb 0xdf, %ah
The complexity of instruction sets makes thorough testing 0011010011011111: xorb 0xdf, %al
of instruction decoders difficult. It is challenging to generate 1111010011011111: hlt
input that includes all interesting test cases, and to verify the 1001010011011111: xchgl %eax, %esp
results of the decoding. Given a set of instruction decoders and 1010010011011111: movsbb (%rsi), (%rdi)
an assembler, we generate a variety of test instructions that 1011110011011111: movb 0x65d5f5, (%esp)
provide good instruction set coverage and verify the output Fig. 2. Changes made to any of the first 5 bits of the top movb of each decoder through differential testing and reassembly. instruction produce an instruction that differs in a non-trivial way. When the output of decoders differ, and the reassembly process indicates a likely error, we produce labelled output indicating which decoder appears to be at fault. These tasks are broken The top of Figure 1 shows an overview of the input into two main components: input generation (Section IV-A) generation procedure. Given sequences of random seed bytes, and output verification (Section IV-B), shown in Figure 1. each of which is likely to contain a valid instruction (about 75% for x86 [17]), we detect structural information about these Testing Procedure instructions (Section IV-A1). Using this structural information, Seed Byte Strings we mutate the original instruction to create new test cases that efficiently cover the ISA being tested (Section IV-A2). This Detect Instruction Filter for New process continues iteratively by detecting the structure of each Structure Inputs new test case and mutating these instructions to produce new inputs (Section IV-A3). Mutate Instruction 1) Inferring Structure: We start our testing process by generating several random byte sequences, each as long as the Differential Testing maximum instruction length for the ISA being tested (four bytes for ARMv8 and PowerPC, 15 bytes for x86). For each Reassembly sequence of bytes that forms a valid instruction, we detect the structure of the instruction by repeatedly altering the sequence Error Reporting of bytes and decoding the result with each decoder. During this process, we give each bit a label that will be used during Fig. 1. Overview of testing procedure. mutation to decide which bits of the instruction should be changed to produce new inputs. Our labelling process has three steps: detecting instruction length, assigning preliminary labels A. Input Generation to each bit, and refining the label of certain bits. Our approach to input generation is based on the observation First, we determine the length of each instruction. Given a that, even though billions of byte strings decode to valid sequence of N bytes, we use a decoder to decode only the first instructions in an instruction set, most are similar. If two byte. If the result of decoding the first byte is identical to the instructions differ by only a single immediate or register result of decoding all N bytes, then the instruction is one byte operand, testing both instructions is probably unnecessary. long. We attempt decoding up to a maximum of N times. The Consider the x86 instruction at the top of Figure 2. While this fewest bytes that produces the exact same output as decoding instruction is 16 bits long, the last 8 bits contain an immediate all N bytes is considered to be the instruction length. The step operand, so changing these bits will produce an instruction that only has practical significance for variable length architectures differs only by that immediate. The same goes for bits 6-8, like x86, and it allows our process to function independently of which encode only a register operand. On the other hand, bits the explicitly returned instruction length provided by decoders. 1-5 encode the opcode. If we change any of these bits, we Next, we flip each bit of the instruction and assign a will produce a significantly different instruction, as shown in label based on the decoding of the resulting instruction. For the bottom five rows of Figure 2. Our goal is to identify the now, we assume that flipping each bit alone is sufficient to bits that can be changed to produce new and interesting test determine which parts of the instruction each bit encodes. This cases so we can vary them to generate input with a variety of is equivalent to assuming that all bits independently encode opcodes, prefixes and addressing modes. fields, i.e., flipping one bit will not affect the result of flipping To identify bits that encode parts of the instruction that another. This is not always true, so we relax this assumption we want to vary is to simply flip bits and determine the later to refine our inferred structures. Bits are assigned one of new decoding. We observe that, in most of the cases that four labels: field, reserved, unused or structural. we consider interesting (new opcodes, prefixes or addressing Field bit: A bit is a field bit if it encodes only a single modes), two or more operands are changed with a single bit field of the decoded instruction. These bits are marked with a flip. We use this observation as the starting point for inferring number indicating which field they encode. Often, these bits instruction structure and generating test cases. encode only a single immediate or register operand. In cases
87
Output Verification Input Generation
where the opcode of the instruction can be changed without alters the instruction when changed in combination with the modifying any other fields, a field bit can also be a part of the field bits. We refine our preliminary labels by relaxing the opcode. During mutation, field bits will be grouped into the assumption that all bits operate independently. Now, we flip fields that they changed, and each field will be given random two bits at a time to determine if any bits encode structural and special values intended to generate special instruction information conditioned on the values of other bits. We forms that depend on the operands. perform this two-bit test only for field bits and unused bits Reserved bit: A bit is a reserved bit if modifying it causes because structural bits are already known to encode structural the instruction to change from a valid instruction to an invalid information and changing reserved bits results in errors. We instruction. Because we focus on testing valid inputs, we do test two bits flipped at a time by modifying each field one bit not modify reserved bits during mutation. at a time and recomputing the preliminary map (which flips Unused bit: A bit is an unused bit if modifying the bit has every bit once, giving us combinations of two bits flipped at no effect on the decoded instruction. As they have no effect on a time). If the new map is different from the original, then the decoding, unused bits are not modified during mutation. the flipped bit encodes some structural information, so we Structural bit: A bit is structural if modifying it changes refine the preliminary label from field or unused to structural. more than one field of the decoded instruction, the number of Figure 4 illustrates this case with a more complex example fields in the instruction, or the preliminary labels of other bits. adc instruction that contains a REX prefix (the first 8 bits). These bits frequently encode the opcode, addressing mode or Several bits in the REX prefix are given a preliminary field operand size. Because we want to test these characteristics label because they encode only a single field of the assembly of instructions, we modify structural bits in multiple ways to language. However, these bits do not match the concept of generate new inputs. a field that we intended because they also encode instruction The preliminary label given to each bit is determined by structure. Bit 3 was given the label field 2 because it appeared comparing the decoding of the the instruction with that of the to encode field 2, but changing this bit alters the REX prefix instruction with the bit flipped. Figure 3 gives an example of to a data16 prefix. Both of these prefixes modify field 2, but generating the sequence of bit-flipped instructions from the they have different structures, so we revise the preliminary original movb with the resulting labels given to each bit. label of this bit to be structural. We try only combinations of two bits flipped at a time, so we cannot identify structure 1011010011011111: movb 0xdf, %ah Label: bits depend on two or more other bits. We chose this value 0011010011011111: xorb 0xdf, %al STRUCT. empirically because using three bits provided only marginal 1111010011011111: hlt STRUCT. benefits at a high cost. 1001010011011111: xchgl %eax, %esp STRUCT. Not all fields are encoded such that any value can be sup- 1010010011011111: movsbb (%rsi), (%rdi) STRUCT. 1011110011011111: movb 0x65d5f5, (%esp) STRUCT. plied while affecting only that field. Some have special values 1011010011011111: movb 0xdf, %al FIELD 2 that cannot be used with certain opcodes, and other fields 1011010011011111: movb 0xdf, %dh FIELD 2 determine which alias of an instruction should be produced. 1011010011011111: movb 0xdf, %ch FIELD 2 1011010011011111: movb 0x5f, %ah FIELD 1 In these cases, changing a bit that encodes a single operand 1011010011011111: movb 0x9f, %ah FIELD 1 may change multiple fields or the validity of the instruction, 1011010011011111: movb 0xff, %ah FIELD 1 so the labelling process may not give these bits field labels. 1011010011011111: movb 0xcf, %ah FIELD 1 1011010011011111: movb 0xd7, %ah FIELD 1 We do not consider this a significant limitation because these 1011010011011111: movb 0xdb, %ah FIELD 1 field bits are often given the structural label, which is used 1011010011011111: movb 0xdd, %ah FIELD 1 more rigorously to generate new inputs. 1011010011011111: movb 0xde, %ah FIELD 1 While the process of flipping each bit and re-decoding Preliminary Labels an instruction allows us to label every bit, it requires the 2 2 2 1 1 1 1 1 1 1 1 instruction to be decoded many times to infer its structure. The Structural Field 2: Field 1: final labelling process is an O(N 2) process with respect to the %ah 0xdf number of bits because it repeatedly determines all preliminary labels to identify structural bits like the one highlighted in Fig. 3. Example of flipping each bit in the example movb instruction Figure 4. For a 16 bit instruction, this could mean that and assigning labels. Grayed spaces in the final instruction are hundreds of decodings are used to infer structure. To reduce structural or reserved bits. Others are given a number corresponding the total number of decodings required, we introduce an opti- to the field that they encode. Note that changes made to any of the mization based on an observation used in DERIVE [6]: many first 5 bits of the top instruction produce an instruction that is different in a non-trivial way, while changes to the remaining bits produce an immediates are contiguous and printed in assembly exactly as instruction that differs only by an immediate or register. they appear in the bytes of the instruction. For example, movb $0xdf, %ah has two bytes: b4 df. The second byte encodes We originally assumed that all bits were independent, so the immediate, and its value is used directly in the assembly flipping each bit alone was sufficient to identify what those language representation of the instruction. Once we detect bits encoded. This is not always true; for example when a the first bit of an immediate field through decoding, we then bit encodes a field-modifying x86 prefix that significantly directly compare the value decoded with the adjoining bits. If
88
Legend: Modified bit Differs from input Structural/Reserved 1 Field # Unused
Input Instruction
010001100001001100110001: adc (%rcx), %r14d 2 2 2 1 0 0 0 2 2 2 2 1 1
Modified Instructions
Prelim. Bit
Instruction Bits Decoding Label Preliminary Structure Final Label
011001100001001100110001: adc (%rcx), %si FIELD 2 2 0 0 0 2 2 2 2 1 1 STRUCT. 010011100001001100110001: adc (%rcx), %r14 FIELD 2 2 2 1 0 0 0 2 2 2 2 1 1 STRUCT. 010000100001001100110001: adc (%rcx), %esi FIELD 2 2 2 1 0 0 0 2 2 2 2 1 1 STRUCT. 010001000001001100110001: adc (%rcx), %r14d UNUSED 2 2 1 0 0 0 2 2 2 2 1 1 STRUCT. 010001110001001100110001: adc (%r9), %r14d FIELD 1 2 2 1 0 0 0 2 2 2 2 1 1 STRUCT. 010001100011001100110001: xor (%rcx), %r14d FIELD 0 2 2 2 1 0 0 0 2 2 2 2 1 1 FIELD 0 010001100000001100110001: add (%rcx), %r14d FIELD 0 2 2 2 1 0 0 0 2 2 2 2 1 1 FIELD 0 010001100001101100110001: sbb (%rcx), %r14d FIELD 0 2 2 2 1 0 0 0 2 2 2 2 1 1 FIELD 0 010001100001101000110001: adc (%rcx), %r14b FIELD 2 2 1 0 0 0 2 2 2 2 1 1 STRUCT. 010001100001101100010001: adc (%rcx), %r10d FIELD 2 2 2 2 1 0 0 0 2 2 2 2 1 1 FIELD 2 010001100001101100100001: sbb (%rcx), %r12d FIELD 2 2 2 2 1 0 0 0 2 2 2 2 1 1 FIELD 2 010001100001101100111001: adc (%rcx), %r15d FIELD 2 2 2 2 1 0 0 0 2 2 2 2 1 1 FIELD 2 010001100001101100010011: adc (%rbx), %r14d FIELD 1 2 2 2 1 0 0 0 2 2 2 2 1 1 STRUCT. 010001100001101100100000: adc (%rax), %r14d FIELD 1 2 2 2 1 0 0 0 2 2 2 2 1 1 FIELD 1
Final Instruction
010001100001001100110001: adc (%rcx), %r14d 0 0 0 2 2 2 1
Fig. 4. An example of refining the preliminary map for an adc instruction. The first byte of this instruction is an x86 REX prefix, so the bits of this prefix
encode more than just operand 2, they also encode structural information. When each field bit is flipped, the preliminary labels are recomputed as shown on
the right side of the figure. Each bit whose change results in different (highlighted) preliminary labels is given the structural label in the final labels.
they match, we infer that all these bits encode an immediate, choosing a random value for each field, we try to create
without the need for additional decoding. Immediate bytes that new inputs that do not contain special operand values.
are labelled this way do not need to be checked for structural • Setting Special Operand Values: We also set each operand
properties because they are used in exactly one field. This to all zeros and all ones because these values are com-
optimization reduces the number of times the sample movb monly signify a special operation of an instruction. For
instruction must be decoded to infer structure from 192 (nearly example, register operands with the value ”11111” in
the number of bits squared) to 36 decodings. ARMv8 can (but not always) signify the stack pointer.
2) Mutating Instructions: Once each bit of the input in- By generating inputs with these common special values,
struction has been labelled, we use these labels in a mutation we try to test variations of instructions with special
process that generates new input instructions through four operations based on their operands.
different types of modifications of the original instruction: These mutations create new instructions that are likely to
differ in multiple fields and number of fields. While we are
• Pairwise Structural Bit Flips: Each pair of structural not limited to two structural bit flips at once, we observed bits are flipped while all other bits are held constant. a significantly reduced rate of new, valid instructions when Structural bits often correspond to opcode, addressing changing three or more structural bits. When mutating x86 mode or operand size, so changing a combination of these instructions, which can vary in length, the newly-created bits should create inputs with new variations of those instructions may be longer than the input instruction, up to characteristics. the x86 maximum size of 15 bytes. • Single Structural Bit Flips: Each structural bit is flipped 3) Filtering For New Inputs: While mutating the input individually while the other bits are held constant (this instruction creates new inputs to test, it can also create process is equivalent to simply passing the single struc- instructions that are redundant with other inputs. For example, tural bit-flipped instructions from Section IV-A1 to the the first output from mutating movb 0xdf, %ah is je 0xe1. filtering phase). When the je instruction is mutated, it will recreate the original • Field Randomization: We choose a single random value movb instruction, which would again be tested and mutated. To for each operand field. Special operand values (like all ensure that we do not loop through the same instructions, we zeros, all ones, or the same register used for source create a format string for each instruction we test. This string and destination) often signify a distinct operation of is a modified version of the assembly language representation, the instruction and may have a distinct decoding. By where the immediate operands are replaced with a generic
89
symbol and the register operands are replaced with a generic then attempts to reassemble the resulting assembly language
name indicating to which register set they belong. Instructions representations of the instruction to compare representations
are only tested and used to generate new input if no other (Section IV-B2). We produce an error report when it appears
instruction with the same format string has already been tested. that one or more decoders produced incorrect assembly lan-
This process requires information about the register sets of an guage for the input bytes (Section IV-B3).
ISA, but this is a small subset of the knowledge required by 1) Differential Decoding: We begin output verification with
other methods. Figure 5 shows the format string for the movb differential decoding: each instruction is decoded with all
instruction previously discussed. decoders, and the results are normalized and compared. Our
rationale for decoding each instruction with all decoders is
Original: movb 0xdf,%ah that if all decoders produce the same output, it is likely to
Format Str: movb IMM, %reg1 be correct, so no further testing of this input is needed. We
Fig. 5. The format string of a movb instruction. differ from Paleari et. al [17], who require 75% of decoders
to be correct. We require that all decodings match to be
We place one final restriction on new test inputs: they cannot considered correct, as we have found cases where only one
have more than two optional bytes. Bytes are considered decoder produces a correct decoding.
optional if they can be removed from the instruction while Ideally, there is one assembly language representation of
removing a subset of fields in the instruction, but without each instruction, so a simple string comparison could identify
altering any remaining fields of the instruction. In practice, the errors. Unfortunately, the decoder output can differ in minor
only bytes with this characteristic are the x86 legacy prefixes ways, like different register name formats, and complex ways,
and unused REX prefixes. Consider an x86 instruction (the like aliases of an opcode with a different number of operands.
movb from previous examples) with three optional bytes, each We address these differences by applying normalization rules.
of which is a prefix: When the assembly language from different decoders are
(data16 addr32 data16) movb 0xdf, %ah almost identical, except for spacing or minor formatting,
This instruction can have up to 13 prefix bytes, each of normalization can produce the same output from each de- which can have 11 different values (repetition of some prefixes coder, obviating the need for reassembly. In cases where is allowed). Using only permutations of the prefixes, we there are significant differences in decoder output, we use could create more than 30 trillion versions of this instruction, normalization to ensure that the assembly language produced making exhaustive testing prohibitive. To limit the number of by each decoder conforms to the input expected by the instructions that differ only by permutations of optional bytes, assembler. (Decoders frequently produce assembly language we filter out inputs with three or more optional bytes. Complex that cannot be reassembled.) Figure 6 shows a case where an x86 prefixes that affect the opcode or operands like the REX, ARM instruction produced different decodings with different VEX and EVEX prefixes are not counted toward optional bytes decoders. because removing them alters other fields of the instruction. In this case, there are a few trivial differences, like spac- While it may seem reasonable to save the generated inputs ing between operand and register name capitalization, but in the form of a model that can be used in future testing, the outputs of the decoders differ in other, more significant the resulting model will depend on the versions of the tested ways including opcode, operands and even validity. While decoders. If a decoder is updated to support new instructions or differences in decoding often indicate an error in at least one remove incorrect decodings, the old model may not correctly decoder, this may not always be the case. Reassembly of the capture these changes. As a result, we chose to re-run input instruction provides a tool to make this determination. generation each time we test decoders, requiring only a few 2) Reassembly: Consider the output of LLVM and libop- minutes for most ISAs. For 64-bit x86, this means testing codes in Figure 6. While the opcodes appear to differ, the mov about 8 hours. We feel that this is an acceptable cost for a opcode is actually an alias of ins. Explicitly programming all thorough test. Of course, users can re-test specific instructions such aliases as normalization rules would require substantial by running the decoders on a binary with only those instruc- expert knowledge of the ISA being tested, and may introduce tions. errors in the testing process. By using an assembler that B. Output Verification accepts different assembly language representations of an instruction, we can determine whether two different assembly Our approach to output verification uses differential testing language strings encode the same instruction. combined with reassembly to avoid the error-prone process If the output of a decoder assembles to the input bytes, of decoding instructions by hand and referencing the ISA we believe that the decoding is correct. For all other cases, manuals. When verifying the output of decoders, we use the we record whether the assembler produced an error and what assembly language representation because it is a common bytes were produced by assembling the instruction. We use this form of output available from all the instruction decoders information during error reporting to determine which decoder that we tested (and because the assembly language decoding outputs appear to be incorrect. can be verified using an assembler). Our approach first uses 3) Error Reporting: Once we have discovered that the out- each decoder to decode an instruction (Section IV-B1), and put of instruction decoders differs, and the difference cannot
90
Decoder Output Normalized Reassembled
libopcodes mov v0.d[0], v7.d[1] mov v0.d[0], v7.d[1] 0x630844e0
Capstone invalid invalid N/A
Dyninst ins Q0, Q7 ins q0, q7 Error
LLVM ins v0.d[0], v7.d[1] ins v0.d[0], v7.d[1] 0x630844e0
Fig. 6. A single ARM instruction decoded by each decoder.
be resolved through reassembly, we suspect that the difference one valid instruction in our input). We allowed the testing
indicates an error in one or more of the decoders. We define procedure to run until it exhausted the list of inputs that it
three ways that our testing procedure can identify errors in could discover using our mutation process. Table II provides
decoders: data summarizing the testing of each ISA.
Output of decoder results in an error when reassembled:
These errors often signify that the input instruction is invalid TABLE II
or that an instruction is not supported by the assembler. These TESTING RESULTS FROM APPLYING FLEECE TO SEVERAL DECODERS. X86
errors are always reported. TESTING GENERATED ABOUT 100X AS MANY INPUTS AS ARM AND
Decoder reports ”invalid”: If a decoder reports an input to POWERPC TESTING.
be invalid, and the other decoders report the same input to Arch Inputs Differences Time (mins:secs)
be valid, we check the reassembly of the valid decodings. If x86 482,711 480,034 508:00
any valid decodings can be reassembled without error, then ARM 6,051 4,337 3:09
we report the invalid decoding as an error. PowerPC 3,629 3,067 1:02
Output of decoder does not reassemble to the same input To our initial surprise, the vast majority of inputs resulted
bytes: This often indicates that the decoder has produced a in differences. However, because we independently vary fields valid but incorrect decoding for the input bytes. However, of an instruction, an error in the decoding of a single type of not all reassembly differences are the result of errors. Some operand or addressing mode will result in many differences. differences occur when the assembler produces an equivalent As a concrete example, few x86 instructions are valid with instruction encoded by different bytes. We detect this case a lock prefix, but our testing procedure tests many different by comparing the reassembled bytes of all valid decodings. If all valid decodings reassemble to the same bytes, then the opcodes and addressing modes with a lock prefix, resulting in decodings are equivalent and not reported as errors. more than 120,000 test cases with lock prefixes, most of which For each decoder with an error, we produce a report that result in differences because only libopcodes decoded them contains the input bytes, the output of every decoder, and any as valid. Similar issues with x86 prefixes exist for multiple error messages produced by the assembler. We organize these decoders, resulting in almost every test case differing among reports into files based on the reassembly error. For example, the five decoders. all x86 decodings that produced the error ”expecting lockable We handle this large number of differences in two ways. instruction after lock prefix” are placed in the same file. First, as mentioned in Section IV, output is placed into files This grouping simplifies the task of condensing many similar based on any assembler errors produced, so all 128,331 test reports. Ideally, we would like to automatically condense these cases with lock instructions that were decoded incorrectly reports for the developers of each decoder. Unfortunately, the by libopcodes are in the same file whose name includes process of determining which errors are the result of the same ”expecting lockable instruction”. Second, we use shell scripts underlying issue in a decoder is challenging and requires a that search for a certain feature, like an instruction pointer reference manual and significant expert knowledge of the ISA. dereference (%eip) or (%rip) in x86), and we compare the correct outputs to any incorrect outputs. If they differ V. EVALUATION by which instruction pointer was used, then we know this We implemented our testing procedure in a tool named decoding error contributed to the report. If the decodings are Fleece and used it to evaluate popular instruction decoders for different, but neither produced an assembler error, then we three architectures: x86-64, ARMv8.0 and PowerPC version refer to the ISA manual to determine which decoder is correct. 3.0. We tested libopcodes (2.26), LLVM (3.9), Dyninst (9.2) We check several such decodings before using a shell script and Capstone (3.0.4) for all three architectures, and Intel XED to automatically categorize the rest. For example, LLVM and (6.26) for only x86-64. We also compared the efficiency of Capstone correctly decoded all instruction pointer dereferences Fleece with random input generation for each of the architec- (their outputs reassemble to the input bytes without error), but tures, and demonstrated that Fleece produces instructions with Dyninst, libopcodes and XED did not. To identify all errors a substantially greater variety of formats. of this type, we use a single shell script that selects all reports A. Decoder Evaluation involving instruction pointer dereferences and outputs those where a decoder deviates from the known-correct decoders. For each ISA, we configured our tool to use the GNU While many of the differences that we report are the result assembler (version 2.26) and began our testing procedure with of an error in at least one decoder, other differences are the re- ten seed byte sequences (enough to frequently have at least sult of different ISA support. For example, libopcodes version
91
TABLE I
EXAMPLES OF ERRORS FOUND FOR EACH DECODER AND EACH ARCHITECTURE.
Decoder Input Output Correct
x86-64 XED & LLVM 67 00 05 00 00 00 00 addb %al, (%rip) addb %al, (%eip)
libopcodes c4 02 51 90 51 19 vpgatherdd %xmm5, vpgatherdd %xmm5,
51 19 0x19(%r9), %xmm10 0x19(%r8, %xmm8, 1), %xmm10
Dyninst de 6c 50 6e fisubr 0x6e(%rsp) fisubr 0x6e(%rax, %rdx, 2)
Capstone 66 3e 97 xchgl %di, %eax xchg %ax, %di
ARMv8 libopcodes e8 13 5a 2a mov w8, w26 orr w8, wzr, w26, lsr #4
LLVM f8 e3 4f 08 invalid ldaxrb w24, [sp]
Dyninst a9 1c 20 6e eor q9, q5, q0 eor v9.16b, v5.16b, v0.16b
Capstone 6a 2d 1e 6e invalid mov v10.h[7], v11.h[2]
PowerPC libopcodes: 7c 00 12 6e lhzux r0, 0, r2 invalid
LLVM 41 80 80 00 bt 0, .+32768 bt 0, .-32768
Dyninst 43 77 dc 23 bdzla- 0xffffdc20 bcla+ 26, 4*cr5+so, 0xffffdc20
Capstone 43 77 dc 23 bdzla+ 0xffffdc20 bcla+ 26, 4*cr5+so, 0xffffdc20
2.26 supports ARMv8.1, so it decoded 727 instructions that is computed using the wrong addressing mode and registers. are only valid in ARMv8.1, while the other decoders viewed Given the bytes 66 3e 97, Capstone produces an incorrect these as invalid inputs. In our x86 testing, there were also xchg instruction whose operands are different sizes (%di is a 129 differences in x86 output due to imperfect normalization. 16-bit register while %eax is 32 bits) because it incorrectly Most (79) of these instructions are variants of mov for which applies the data16 prefix (0x66) to only one of the two the correct representation is not always clear because the as- operands. Although operand order is swapped by Capstone, sembler error is generic (”unsupported instruction ’mov’”) and this has no effect for xchg instructions. the assembler will not accept instruction suffixes in some cases Decoders can also terminate unexpectedly due to invalid while requiring suffixes in other cases of the same opcode. inputs. LLVM will terminate with an ”unreachable” message The difference in syntax requirements of the assembler could when used to decode an EVEX instruction with opcode byte not be resolved even when considering opcode and addressing 0xc2, and libopcodes will terminate unexpectedly for some mode together. Normalization rules intended to address this EVEX instructions with opcode byte 0x02. issue reached too far and altered correct output, so they were ARM Summary: ARMv8 decoders had the fewest errors, but removed. In all other outputs, there was at least one incorrect each decoder had at least one. LLVM was the most reliable decoder or difference in support for an assembly feature. decoder, which is not surprising, because it receives commits Table III shows the number of real errors reported for each from ARM employees and is recommended as the authoritative decoder and architecture. ARM decoder. The most common error in ARM decoding is TABLE III the example provided for LLVM in Table I, a load instruction NUMBER OF ERRORS REPORTED FOR EACH TOOL. X86 DECODERS HAD used for transaction-based computation. LLVM decodes this FAR MORE ERRORS ON AVERAGE THAN OTHER DECODERS, WHILE ARM instruction as invalid because unused operands have values DECODERS TENDED TO HAVE THE FEWEST ERRORS. other than the typical compiler-generated values (all 1s) for Arch XED libopcodes LLVM Dyninst Capstone this instruction. In the error shown for libopcodes, the decoder x86 3 13 8 18 12 produced an incorrect alias. While the correct orr instruction ARM n/a 2 1 7 3 PowerPC n/a 7 4 6 7 includes a shift of 4 bits, the mov instruction given by The most common type of error discovered was invalid libopcodes incorrectly omits this shift. The Dyninst error is a instructions being decoded as valid. Decoders also had errors decoding in which registers of the wrong type (general purpose decoding control flow targets and memory access locations. instead of vector) are produced by the decoder. The incorrect x86-64 Summary: We found the most errors in x86 decoders, Capstone output shows a case where the decoder fails to the majority of which (44 of the 54 issues) involved instruc- recognize a valid instruction (this instruction was supposedly tions with at least one prefix. This finding agrees with the supported by the decoder). Compared to the errors identified in work of Paleari et. al, who also observed that x86 instructions x86-64 decoders, the errors we discovered in ARM decoders with prefixes were frequently decoded differently by a variety are more related to aliasing and correctly identifying valid of decoders [17]. While decoders agreed on many general- instructions and less related to operands and addressing modes, purpose instructions, instructions from recent extensions were likely because ARM instructions have distinct forms of each often decoded incorrectly by at least one decoder, particularly opcode that describe the types of operands used, while x86-64 when prepended with a legacy prefix. Table I gives an example instructions have a variety of different operands and operand- error reported for each of the decoders. In the example given modifying prefixes that can be used for any given opcode. for XED and LLVM, the first byte, 67 specifies that a 32-bit PowerPC Summary: For each decoder, PowerPC had fewer address should be used to determine the memory operand. errors than x86-64, and for all but Dyninst, they had more Both XED and LLVM ignore this byte when the register errors than ARM. The majority of these errors are cases where specified is the instruction pointer (%rip). The examples given an invalid instruction is decoded as valid. Table I shows an for both libopcodes and Dyninst show cases where an address example of a difference found for each decoder. libopcodes
92
TABLE IV For ARM random testing, most decodings were exact string
COMPARISON OF TESTING RESULTS USING RANDOM INPUTS AND matches, which do not require reassembly, allowing random
FLEECE-GENERATED INPUTS. RANDOM TESTING WAS RUN FOR AS LONG inputs to be tested more quickly. Despite this speed, ARM
AS FLEECE FOR X86, AND 10 MINUTES FOR ARM AND PPC. FOR EACH
ARCHITECTURE, FLEECE DISCOVERS MORE UNIQUE DIFFERENCES IN testing still tested instructions with about 1/10th of the format
LESS TIME. string variety discovered by Fleece. While the random ap-
Fleece Random proach discovered a greater total number of differences, most
Arch. Inputs Unique Time Inputs Unique Time of these differences are redundant, covering instructions with
x86 482,711 Diffs. (mins:secs) Diffs. (mins:secs) similar opcodes, addressing modes and register sizes.
480,034 508:42 2,679,254 9,494 508:00
ARM 6,051 4,337 3:09 1,706,422 600 10:00 Fleece discovered unique differences much more quickly
PPC 3,629 3,067 1:02 64,360 1,100 10:00 because it varied instruction features using inferred structure,
only testing instructions with new structure. For example, a
decodes an invalid lhzux instruction as valid. This atomic single x86-64 instruction with a data16 and EVEX prefix update lhzux instruction cannot use r0 as the first operand, will be produced at a rate of about one in 65,000 at random but the bits for this instruction encode r0, so it is invalid. (because it must contain 67 and 62 as prefixes), yet one in five The example error given for LLVM shows a case where it of the Fleece-generated input contained these prefixes because incorrectly decodes the offset of a branch instruction. Both they produce instructions with unique opcode-addressing mode Capstone and Dyninst incorrectly decode branch instructions combinations. For both ARM and PowerPC, the difference be- for PowerPC. In the case shown in the table, Dyninst and tween Fleece and the random input generation is less dramatic, Capstone both give a version of the branch mnemonic with yet it persists because instructions with 15 bits devoted to the fewer operands, but the alias is incorrect. The correct version opcode or reserved are still fairly rare in random inputs (1 in is a branch based on the overflow bit (so) of condition register 32768), but are frequently generated by Fleece. 5 (cr5), as indicated by the second operand. The incorrect For all architectures, Fleece was able to use inferred in- version produced by Dyninst and Capstone implicitly branches struction structure to generate inputs with a variety of features based on the less-than bit of cr0. much more efficiently than a random approach. The decoding errors we discovered have implications for a VI. CONCLUSION variety of higher-level analysis techniques that rely on accurate decoding. Decoding errors make debugging more difficult, and Binary decoders play a critical role in analyzing executable many of the errors also have implications for analysis tools. files, a task fundamental to numerous applications in pro- Decodings with incorrect addressing information will produce gram performance, security analysis and debugging. Decoders errors when tracing memory accesses for data flow. Incorrect provide instruction-set-specific knowledge that allows higher decodings of branch instructions, including conditions and levels of analysis to work with abstractions about control- destinations can result in incorrect control flow analysis and and data-flow. Unfortunately, the ISA-specific knowledge con- incomplete or incorrect code discovery as a result. Decoders tained in decoders can be inaccurate, leading to inaccurate that fail to decode instructions that do not contain typical conclusions from higher level analyses. We designed and compiler-generated instructions risk failure when given hand- implemented a method of input generation, differential testing, written executables, allowing malicious programmers to ob- and reassembly that can be used with very little ISA-specific fuscate code and defeat higher-level tools. knowledge to discover decoding errors. We demonstrated the effectiveness of our method by testing a variety of instruction B. Fleece Evaluation decoders for a variety of architectures and reporting errors Input generation is a critical part of our testing procedure, for each. In addition, we showed that our testing procedure but there are few good benchmarks against which we can can use inferred structural information to substantially im- evaluate our input generation. While Paleari et al. [17] used prove the variety of instruction formats tested during ran- input generation that was more sophisticated than a purely dom testing. The code used in this paper can be found at: random approach, they chose most of their input bytes at https://github.com/dyninst/tools. random. Additionally, their testing for x86 occurred before the A introduction of complex EVEX prefixes, so we compare Fleece CKNOWLEDGEMENTS to a random approach given the same, or greater period of We are grateful to the efforts of Xiaozhu Meng, Bill testing time. To evaluate the usefulness of Fleece, we compare Williams and Ben Welton in the preparation of this paper, the number of unique differences found (meaning no duplicate and the technical support of John Detter and the rest of the prefix-opcode-operand type instructions). Paradyn Project team. Table IV gives an overview of the inputs generated and This work is supported in part by Department of Energy differences discovered by testing random input compared to grant DE-AC05-00OR22725, National Science Foundation testing Fleece-generated input. Cyber Infrastructure grants ACI-1547272 and ACI-1449918, Random testing requires very little time to generate inputs, Lawrence Livermore National Lab grant B617863, a grant so the primary bottleneck for this approach was reassembly. from Cray Inc., and a grant from Intel Corp.
93
REFERENCES [13] Intel. Pin - A Dynamic Binary Instrumentation Tool,
[1] L. Adhianto, S. Banerjee, M. Fagan, M. Krentel, G. Marin, J. Mellor- https://software.intel.com/en-us/articles/pin-a-dynamic-binary- Crummey, and N. R. Tallent. HPCTOOLKIT: Tools for Performance [14] instrumentation-tool. Analysis of Optimized Parallel Programs. Concurrency and Computa- C. Lattner and V. Adve. LLVM: A Compilation Framework for Lifelong tion: Practice and Experience, 22(6):685–701, Apr. 2010. Program Analysis and Transformation. In CGO ’04 Proceedings of [2] Anh Quynh, Nguyen. Captstone: The Ultimate Disassembly Framework, the international symposium on Code generation and optimization: http://www.capstone-engine.org/. feedback-directed and runtime optimization, Palo Alto, California, USA, [3] ARM. ARM Architecture Reference Manual. [15] Mar. 2004. [4] A. R. Bernat and B. P. Miller. Anywhere, Any Time Binary Instrumen- B. P. Miller, L. Fredricksen, and B. So. An Empirical Study of the tation. In ACM SIGPLAN-SIGSOFT workshop on Program Analysis for Reliability of UNIX Systems. Communications of the ACM, 33(12), Software Tools and Engineering (PASTE), Szeged, Hungary, Sept. 2011. [16] Dec. 1990. [5] J. Caballero, N. M. Johnson, S. McCamant, and D. Song. Binary [17] Oleh Yuschuk. OllyDbg, http://ollydbg.de/. Code Extraction and Interface Identification for Security Applications. R. Paleari, L. Martigononi, G. Roglia, and D. Bruschi. N-Version Disas- Technical Report UCB/EECS-2009-133, EECS Department, University sembly: Differential Testing of X86 Disassemblers. In 19th international of California, Berkeley, Oct 2009. symposium on Software testing and analysis (ISSTA), Trento, Italy, July [6] D. R. Engler and W. C. Hsieh. DERIVE: A Tool that Automatically [18] 2010. Reverse-Engineers Instruction Encodings. In Proceedings of the ACM T. Romer, G. Voelker, D. Lee, A. Wolman, W. Wong, H. Levy, B. Ber- SIGPLAN workshop on Dynamic and adaptive compilation and opti- shad, and B. Chen. Instrumentation and Optimization of Win32/Intel mization, Boston, Massachusets, USA, Jan. 2000. Executables Using Etch. In Proceedings of the USENIX Windows NT [7] W. Fang, B. P. Miller, and J. A. Kupsch. Automated Tracing and [19] Workshop, Seattle, Washington, Aug. 1997. Visualization of Software Security Structure and Properties. In 9th P.-M. Seidel. Directed Test Case Generation for x86 Instruction Internation Symposium on Visualization for Cyber Security (VizSec), Decoding. In 15th International Microprocessor Test and Verification Seattle, Washintgon, USA, Oct. 2012. [20] Workshop (MTV), Austin, Texas, USA, Dec. 2014. [8] P. Godefroid, A. Kiezun, and M. Y. Levin. Grammar-based Whitebox D. Song, D. Brumley, H. Yin, J. Caballero, I. Jager, M. G. Kang, Fuzzing. In Proceedings of the 29th ACM SIGPLAN Conference on Z. Liang, J. Newsome, P. PoosanKam, and P. Saxena. BitBlaze: A Programming Language Design and Implementation, Tucson, AZ, USA, New Approach to Computer Security via Binary Analysis. In 4th June 2008. International Conference on Information Systems Security, Hyderabad, [9] Hex-Rays. IDA, https://www.hex-rays.com/products/ida/. [21] India, Dec. 2008. [10] IBM. Power ISA. The GNU Project. GNU Binutils, [11] Intel. Intel 64 and IA-32 Architectures Software Developer’s Manual. [22] https://www.gnu.org/software/binutils/. [12] Intel. Intel X86 Encoder Decoder Software Library, [23] The Valgrind Developers. Valgrind, https://valgrind.org. https://software.intel.com/en-us/articles/xed-x86-encoder-decoder- D. Yang, Y. Zhang, and Q. Liu. BlendFuzz: A Model-Based Framework software-library. for Fuzz Testing Programs with Grammatical Inputs. In Proceedings of the 11th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom), Liverpool, UK, June 2012.
94