Representing binary code as a circuit

A high level intermediate representation of a binary is generated. Circuit nodes from the high level intermediate representation are built, wherein a circuit node represents an operation in the high level intermediate representation. The circuit nodes are connecting using a flow analysis of the binary to build a circuit that represents the binary.

BACKGROUND

There are many representations for program analysis or verification at the source code level. However, binary code also needs analysis. Binary analysis may determine the integrity of the binary and look for malicious code. Also, many developers only ship binaries and do not make their source code available to others. However, recipients of such binaries still may wish to verify the integrity of the binary code.

SUMMARY

Embodiments of the invention are directed to representing binary code as a circuit. In one example, a binary is extracted to an Intermediate Representation (IR) level and then to a High level Intermediate Representation (HIR). A circuit representation of the binary may then be built from the HIR.

DETAILED DESCRIPTION

The detailed description provided below in connection with the appended drawings is intended as a description of the present examples and is not intended to represent the only forms in which the present examples may be constructed or utilized. The description sets forth the functions of the examples and the sequence of steps for constructing and operating the examples. However, the same or equivalent functions and sequences may be accomplished by different examples.

FIG. 1shows a system100for building a circuit representation of a binary in accordance with an embodiment of the invention. System100includes a binary analysis tool104, a High level Intermediate Representation (HIR) tool106, and a circuit generator108. One or more components of system100may be implemented in a “code as a circuit” application using computer readable instructions executed by one or more computing devices. Embodiments of a computing device are discussed below in conjunction withFIG. 13.

Binary analysis tool104receives a binary102for analysis. A binary includes machine executable code. In one embodiment, binary102is compatible with x86 or x64 processor architectures. Binary analysis tool104lifts binary102to an Intermediate Representation (IR) and performs flow analysis of binary102. The IR may resemble assembly-like code. In one embodiment, binary analysis tool104includes a Microsoft® Vulcan binary analysis tool.

The IR and flow analysis from tool104is passed to HIR tool106. Tool106raises the IR to a HIR and performs further flow analysis. HIR tool106may remove replace register calls with variables and convert the instruction sequence to a Directed Acyclic Graphical (DAG)-like format.

Circuit generator108uses the HIR and enhanced flow analysis from HIR tool106to build circuit nodes. The resulting circuit may be presented to a user in a code as circuit User Interface (UI)110. An example code as a circuit UI is described below in connection withFIG. 12. System100may include a graph-walk application112to enable a user to walk through the circuit to gather detailed information about the circuit and to perform binary verification, such as backtracking for root cause analysis (discussed below).

Turning toFIG. 2, an embodiment of a circuit node200is shown. A circuit node may represent one or more operations in the HIR. As will be discussed further below, a circuit node may represent a program function (i.e., a set of operations). Circuit node200includes a gate204having one or more inputs202and one or more outputs206. Output206may be inputted into another circuit node as part of a circuit. Circuit node200may include predicate208which is a control condition that enables or disables gate204. A gate may represent a simple operation, such as ADD, or may represent a defined abstraction whose semantics are known. For example, a gate may represent a C language function “strcat” (string concatenate) that appends two strings together.

Turning toFIG. 3, an embodiment of representing binary code as a circuit is shown. A binary (shown in source code form at302) has been analyzed by binary analysis tool104. The resulting Intermediate Representation is shown at303. It will be appreciated that IR303appears as assembly-like code (e.g., IR303references machine registers). Analysis of IR303by HIR tool106results in a High-level Intermediate Representation304. It will be appreciated that HIR304is a high level abstraction of the binary that is machine independent and in a directed acyclic like format. HIR304shows a compare statement where if Z does not equal zero, then variable C takes on the sum of variables A and B.

HIR304may be expressed using circuit node306. In circuit node306, the inputs A and B are provided to a gate308that performs an addition operation. The predicate of node306is the compare statement (“CMP Z, 0”) of HIR304. Thus, when Z is not equal zero, then the addition operation of gate308may be performed to add inputs A and B and output the sum as output C. In one embodiment, when multiple circuit nodes are connected to create a circuit, the circuit flow is read from left-to-right. As will be described below, the circuit may be traced backwards (i.e., read from right-to-left) to determine potential root causes of a flawed output.

Turning toFIG. 4, a flowchart400shows the logic and operations of representing binary code as a circuit in accordance with an embodiment of the invention. In one embodiment, at least a portion of the logic of flowchart400may be implemented by computer readable instructions executable by one or more computing devices.

Starting at block402, a binary is received. At block404, an IR is generated of the binary. Next, at block406, flow analysis of the binary is performed. In one embodiment, the logic of blocks404and406may be performed by a binary analysis tool such as Microsoft® Vulcan.

Proceeding to block408, a HIR is generated from the IR and the flow analysis. Generating the HIR raises the IR to a platform independent representation which is easier for code analysis. For example, register calls are replaced with temporary variables and global/stack variables as appropriate. Generating the HIR includes performing enhanced flow analysis that may investigate factors such as virtual functions, global references, field references, and the like. At least a portion of this enhanced flow analysis is performed using the IR. In one embodiment, Microsoft® Symval APIs may be used to raise the IR to an HIR. An embodiment of generating the HIR is discussed below in connection withFIG. 6.

Next, in block410, circuit nodes are built from the HIR. Each circuit node may be a simple operation (e.g., add, subtract, greater than comparison, etc.) or represent a function having several operations which semantics may be defined (e.g., a strcat function, a user-defined function, etc.). Continuing to block412, the circuit nodes are connected using the enhanced flow analysis to build the circuit. In one embodiment, the circuit may be built for a subset of operations or edges that are of interest.

Turning toFIG. 5, a flowchart500shows the logic and operations of representing binary code as a circuit in accordance with an embodiment of the invention. Flowchart500shows an embodiment of performing flow analysis of the binary, as in block406. In one embodiment, at least a portion of the logic of flowchart500may be implemented by computer readable instructions executable by one or more computing devices.

Starting in block502, data flow chains are built to abstract the flow of data in the binary. Proceeding to block504, a control flow graph is built that describes the paths that the binary execution may take. In one embodiment, the stream of instructions is divided into basic blocks (i.e., a portion of code without a jump). The basic blocks are connected according to the control flow to produce the control flow graph. Next, in block506, a dependence graph is built that abstracts how a set of instructions depend on a conditional (i.e., predicate) instruction for execution.

Next, in block508, a call graph is built. The call graph describes the calling interactions between basic blocks. In one embodiment, the call sites for direct calls are connected. These direct calls may be used later to connect circuit nodes. A call to an import is marked as a pseudo circuit node. An import is a call to a function in an external module which may be made using libraries (e.g., dynamic linking), Component Object Model (COM), etc., in which case these instructions (i.e., the external module) are not available for analysis. These calls may be simulated using a pseudo circuit node to represent the external module.

Turning toFIG. 6, a flowchart600shows the logic and operations of representing binary code as a circuit in accordance with an embodiment of the invention. Flowchart600shows an embodiment of generating an HIR, as in block408. Analysis performed in flowchart600may be performed using the IR. In one embodiment, at least a portion of the logic of flowchart600may be implemented by computer readable instructions executable by one or more computing devices.

Starting in block602, redundant intermediary instructions are removed from the call stack associated with the binary. Proceeding to block604, context insensitive flow analysis is used to add missing edges to the call graph. In context insensitive flow analysis, all possible calls between basic blocks are represented, while in context sensitive flow analysis, values of the variables are taken into account when connecting the basic blocks.

Next, in block606, virtual functions are added to the call graph using context insensitive flow analysis and relocation information. Relocation information is used to detect the virtual calls that are made through virtual function tables (vtables). Since vtables have a specific format embedded with relocations/fixups, the vtables can be used to determine the possible locations of a virtual call.

Proceeding to block608, alias chains are built with context insensitive flow analysis for alias variables in the binary. Flow insensitive alias analysis is used to connect HIR nodes to add more information to the data flow chains.

Continuing to block610, a global reference list and a field reference list are built for global variables and fields, respectively, in the binary. In object oriented programming, a field (also referred to as data member) is data within a class and is available to each instance of the class. Global variables and fields may be connected across call boundaries. This will help in tracking value flow through global variables and field members.

Next, in block612, a system dependency list is built for the binary. The system dependency list describes system variables (e.g., config file, registry, etc.) that the binary is dependent on. These system variables may be read from the platform on which the binary is to execute. The system variables in the dependency list may then by simulated by special circuit nodes and supplied with any value as desired. For example, reads or writes to system locations, like a registry store/file, may be marked as special circuit nodes which can be supplied any value in the circuit graph simulation. In another example, if a binary reads the registry to obtain the Internet Explorer® version, the registry on that machine can be read and passed to the code as a circuit application for simulation.

Embodiments of the invention may be used for analysis of a binary. Such analysis may include static debugging, code coverage analysis, root cause analysis, and runtime tracing.FIG. 7illustrates how embodiments of the invention may be used for improving code coverage testing. Code702is represented as a circuit704. Code702(and code inFIGS. 8,10, and11) is shown as pseudo code to aid in understanding, but it will be understood that circuit702is built from the binary code version of code702. Tracing circuit704backwards exposes the code coverage for testing the binary. Ranges for a variable that may result in uncovered code may be discovered. Testing may then be modified to ensure coverage of this previously uncovered variable range.

InFIG. 7, if variable c is greater than 18, then the “if” block of code702would not get covered. In circuit704, the “if” block is entered at node706and the Boolean output of node706serves as a predicate for node708. Node708corresponds to statement703in the “if” block of code702. Thus, by walking backwards through circuit704, a user may determine which values of variable c will result in the coverage of the code represented by node708.

FIG. 8shows another example of using embodiments of the invention for determining code coverage. In this example, a user wants to determine under what conditions a divide by zero error may occur. Code802is represented by circuit804. In this example, a user wants to determine under what conditions the statement “u/=d” would attempt to divide variable u by zero (i.e., determine when d is equal to zero). By walking backwards through circuit804, the user may determine that d will be zero when one of the inputs to circuit node806is zero (i.e., when b equals zero or x equals y).

Turning toFIG. 9, a circuit900may be used in registry key analysis. Operation RegOpen902is used to open a registry key having the specified key name passed in as RString. Circuit node904performs a concatenation (shown by a ‘+’ symbol) on strings A and B to form RString. In analysis of the circuit graph, given RString, a user can chase back906to determine the input string. For example, RString may be built by performing:strcpy (RString,“HKEY_LOCAL_MACHINE\Software\Microsoft\Internet Explorer”);strcat(RString,“Version”); /* concatenation as in gate904Regopen(RString)

Using circuit900, given RString, the user can chase back to find the complete input string to RegOpen902is “HKEY_LOCAL_MACHINE\Software\Microsoft\Internet Explore\Version”.

In embodiments herein, circuit representations may be built per function (also referred to as a procedure) in a binary without having global and inter-functional edges or may be built for the binary as a whole. Turning toFIG. 10, an embodiment of the invention involving global variables is shown. Code1002, represented by circuit1004, has a global variable s. In code1002, a use of global variable s is shown at1010and a definition of global variable s is shown at1012. In circuit1004, global variable s is shown as a global line1006. Global line1006may serve as an input to a circuit node and be modified by a circuit node output. The “uses” and “definitions” of global variable s by nodes in circuit1004may simply be connected to global line1006. In circuit1004, node1014corresponds to global variable s use at1010and node1016corresponds to global variable s definition at1012.

Global line1006(also referred to as a global edge) may be carried across multiple procedure calls. In an alternative embodiment, an inter-functional edge may also be represented similarly as global line1006. An inter-functional edge may follow along the side of the circuit and will terminate at program exit points.

Turning toFIGS. 11 and 12,FIG. 12shows an embodiment of a code as a circuit UI1200for displaying a circuit representing code1100inFIG. 11. UI1200includes circuit section1202, assembly instructions1204, and circuit information section1206. UI1200also includes a button “Open Binary”1208to select a binary for circuit representation.

Circuit section1202shows a circuit that represents code1100. At the bottom of section1202is a key for the connections between nodes of the circuit. The key includes connections for local variables, temporary variables, Boolean variables, and immediate variables. Values for variables may be fed into the circuit and the circuit “executed” for evaluating the circuit logic.

Section1204shows an Intermediate Representation of the binary (labeled “Assembly instructions”). The user can view the IR of the binary that was used to construct the circuit. In one embodiment, the instructions shown in section1204include assembly instructions derived by Microsoft® Vulcan.

Section1206includes information about the circuit. A user may select portions of the circuit in section1202to display detailed information in section1206. For example, a user may select a gate to learn more information about that particular gate. InFIG. 12, the user has selected gate number 5 (the “greater than” gate). Section1206shows that the inputs to gate number 5 are temporary variable T0and local variable c. The output of gate number 5 is Boolean P1. Gate number 5 has a predicate of Boolean P0. P0is an always true predicate for a set of instructions that are not guarded by any condition (such as on entry to a function).

In one embodiment, graph-walk application112may be used to walk over the graphical representation of the circuit shown in UI1200. The graph-walk application may be used in root cause analysis of the binary code. For example, a user may use the circuit representation to find the set of variables that drive an output. If the output is faulty, then the circuit may be traced backwards from the output to find an input variable that may be a potential cause of the bad output. To obtain the set of instructions that might influence the output variable, the graph-walk application may traverse over the data and predicate edges backwards from the given output. Also, variables found on the edges (such as global variables) may be tracked as the circuit is traversed backwards.

Also, given the circuit representation, a user may see the independent flow paths that are available within a block of code, such as within a function. For example, multiple independent operations may be performed within a function like adding values to a list and then checking for the consistency of the list. These operations can be reviewed separately as independent operations by looking at the circuit graph in UI1200.

In one embodiment, the user may define a portion of the circuit as a “black box” and define the semantics for the black box. The semantics may include the inputs and resulting outputs. The black box may represent a function (e.g., user-defined, library call, etc.) where the circuit node inputs are parameters passed to the function and the circuit node outputs are return values of the function. For example, a portion of the circuit may include a strcat function. When the function strcat is encountered by the graph-walk application, a simulation of the function takes the two strings, concatenates them, and returns the output without walking over a circuit graph of the strcat function. This enables a user to focus the circuit on the section of code of interest.

Embodiments herein may be used for debugging code with runtime trace data. A trace of the code may be collected that includes the values involved at the predicates where a control transfer decision was made. A circuit representation of the code may be used to statically rerun and debug the code using the collected trace information. Information that is lost at join points during the flow analysis may be marked. For example, see the following code:

Imprecise static analysis may lose which specific location the value of x came from (i.e., case 1 or case 2). At runtime, since the specific path that is taken is known, the path can be tracked and recorded. In the above example, the user will then know which path (case 1 or case 2) was taken at runtime. The trace shows which path is taken during runtime and helps a user understand the root cause of a crash or other error. In some cases, call sites that cannot be resolved during static analysis may be resolved with runtime tracing.

Embodiments of the invention enable binary code to be represented as a circuit. Portions of the code may be represented by circuit nodes that are connected according to flow analysis of the binary code to produce a circuit representation. The circuit may help a user visualize the dependencies between variables and the flow of data. Embodiments of the invention may reduce code review time and aid in detection of code bugs. Also, embodiments herein may be used with dynamic tracing using data available at runtime.

FIG. 13and the following discussion are intended to provide a brief, general description of a suitable computing environment to implement embodiments of the invention. The operating environment ofFIG. 13is only one example of a suitable operating environment and is not intended to suggest any limitation as to the scope of use or functionality of the operating environment. Other well known computing devices, environments, and/or configurations that may be suitable for use with embodiments described herein include, but are not limited to, personal computers, server computers, hand-held or laptop devices, mobile devices (such as mobile phones, Personal Digital Assistants (PDAs), media players, and the like), multiprocessor systems, consumer electronics, mini computers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like.

FIG. 13shows an example of a computing device1300for implementing one or more embodiments of the invention. In one configuration, computing device1300includes at least one processing unit1302and memory1304. Depending on the exact configuration and type of computing device, memory1304may be volatile (such as RAM), non-volatile (such as ROM, flash memory, etc.) or some combination of the two. This configuration is illustrated inFIG. 13by dashed line1306.

In other embodiments, device1300may include additional features and/or functionality. For example, device1300may also include additional storage (e.g., removable and/or non-removable) including, but not limited to, magnetic storage, optical storage, and the like. Such additional storage is illustrated inFIG. 13by storage1308. In one embodiment, computer readable instructions to implement embodiments of the invention may be in storage1308. Storage1308may also store other computer readable instructions to implement an operating system, an application program, and the like.

Device1300may also include communication connection(s)1312that allow device1300to communicate with other devices. Communication connection(s)1312may include, but is not limited to, a modem, a Network Interface Card (NIC), an integrated network interface, a radio frequency transmitter/receiver, an infrared port, a USB connection, or other interfaces for connecting computing device1300to other computing devices. Communication connection(s)1312may include a wired connection or a wireless connection. Communication connection(s)1312may transmit and/or receive communication media.

The term “computer readable media” may include communication media. Communication media typically embodies computer readable instructions or other data in a “modulated data signal” such as a carrier wave or other transport mechanism and includes any information delivery media. The term “modulated data signal” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, radio frequency, infrared, Near Field Communication (NFC), and other wireless media.

Device1300may include input device(s)1314such as keyboard, mouse, pen, voice input device, touch input device, infrared cameras, video input devices, and/or any other input device. Output device(s)1316such as one or more displays, speakers, printers, and/or any other output device may also be included in device1300. Input device(s)1314and output device(s)1316may be connected to device1300via a wired connection, wireless connection, or any combination thereof. In one embodiment, an input device or an output device from another computing device may be used as input device(s)1314or output device(s)1316for computing device1300.

Components of computing device1300may be connected by various interconnects, such as a bus. Such interconnects may include a Peripheral Component Interconnect (PCI), such as PCI Express, a Universal Serial Bus (USB), firewire (IEEE1394), an optical bus structure, and the like. In another embodiment, components of computing device1300may be interconnected by a network. For example, memory1304may be comprised of multiple physical memory units located in different physical locations interconnected by a network.

In the description and claims, the term “coupled” and its derivatives may be used. “Coupled” may mean that two or more elements are in contact (physically, electrically, magnetically, optically, etc.). “Coupled” may also mean two or more elements are not in contact with each other, but still cooperate or interact with each other (for example, communicatively coupled).

Those skilled in the art will realize that storage devices utilized to store computer readable instructions may be distributed across a network. For example, a computing device1330accessible via network1320may store computer readable instructions to implement one or more embodiments of the invention. Computing device1300may access computing device1330and download a part or all of the computer readable instructions for execution. Alternatively, computing device1300may download pieces of the computer readable instructions, as needed, or some instructions may be executed at computing device1300and some at computing device1330. Those skilled in the art will also realize that all or a portion of the computer readable instructions may be carried out by a dedicated circuit, such as a Digital Signal Processor (DSP), programmable logic array, and the like.

Various operations of embodiments of the present invention are described herein. In one embodiment, one or more of the operations described may constitute computer readable instructions stored on one or more computer readable media, which if executed by a computing device, will cause the computing device to perform the operations described. The order in which some or all of the operations are described should not be construed as to imply that these operations are necessarily order dependent. Alternative ordering will be appreciated by one skilled in the art having the benefit of this description. Further, it will be understood that not all operations are necessarily present in each embodiment of the invention.

The above description of embodiments of the invention, including what is described in the Abstract, is not intended to be exhaustive or to limit the embodiments to the precise forms disclosed. While specific embodiments and examples of the invention are described herein for illustrative purposes, various equivalent modifications are possible, as those skilled in the relevant art will recognize in light of the above detailed description. The terms used in the following claims should not be construed to limit the invention to the specific embodiments disclosed in the specification. Rather, the following claims are to be construed in accordance with established doctrines of claim interpretation.