Many source code analysis tools available today, including Coverity Prevent, GrammaTech CodeSonar, Klocwork K7, and The MathWorks PolySpace Verifier detect software defects and vulnerabilities. During the past few years, interest has grown in performing similar analyses on executable machine code. Three main factors are driving this interest in direct machine code analysis: the need to control COTS software reliability and security, the technical advantages over source code analysis, and the recent increases in its feasibility and utility, which have been substantiated by breakthroughs in the research community. David explores the advantages of machine code analysis and summarizes the current state of the art.

Taking back control of application reliability and security

Time-to-market and cost demands have increased developers’ use of COTS components in embedded software applications. While these components offer advantages, they come at the price of some well-established drawbacks. In particular, consumers usually must accept the software “as is” and trust that the producer has taken the necessary steps to ensure security and reliability. Unfortunately, experience has demonstrated this is not always the case.

How can consumers know if a COTS component has acceptable security and reliability for their needs? A few COTS components provide some information about the development and testing process that was followed. Examples include a few Real-Time Operating Systems (RTOSs) that offer documentation to assist avionics software developers with the DO-178B certification process. But even in these unusual cases, typically only a reduced-functionality version of the RTOS is well documented. For most third-party components, no information about the development and testing process is available.

For organizations developing security or high reliability applications, the inability to assess the quality of third-party components is a significant problem. It is not surprising that one of the earliest proponents of developing better technology for analyzing executables was the National Security Agency, which in 2004 publicly emphasized the importance of tools that analyze binaries[13]. Of particular concern is software used in the nation’s critical infrastructure, such as emergency preparedness communications and power plants.

Machine code analysis offers a way to assess third-party code, even when the source is unavailable. The ability to detect defects, vulnerabilities, and intentionally inserted malicious code allows users to regain some control in determining if a piece of software meets their acceptance criteria. Users need not blindly trust the software producer.

Technical advantages of machine code analysis

Source code is not usually provided for COTS software, thus the need for machine code analysis. In fact, even when source code is available, machine code analysis offers many advantages over other analysis techniques. This is because the source code is not executed; rather, it is compiled into a machine code program (the executable). Analyzing programs written in interpreted languages is a different matter, although there, too, the source code is not executed directly on the processor.

Differences may exist between the source code semantics and the compiled executable semantics for several reasons. This potential mismatch is called the “What You See Is Not What You eXecute” (WYSINWYX) effect[4]. WYSINWYX acknowledges that the semantics in the source code may be incomplete or imprecise in view of what is actually executed in the process.

The WYSINWYX effect can be caused by various factors, including compiler bugs and linking third-party libraries. Figure 1 illustrates how the meaning of the original program can change as modules are added prior to the final executable’s creation.

One example of a compiler bug that initiated the WYSINWYX effect was discovered during a 2002 security review at Microsoft[10]. In this case, code like the following appeared in the source for a log-in program:

memset(password,‘\0’, len);

free(password);

As indicated by its name, the buffer password was used to hold a user’s password. As a security precaution, the programmer desired to minimize the amount of time this sensitive information was kept in memory. Thus, before deallocating the buffer (line 2), the intent was to overwrite the sensitive password with zeros (line 1).

However, in this case, the Microsoft C++ compiler determined that the password zeroing statement was “useless” and removed it. In a technical sense, the compiler was correct: The zeros written by the memset are not supposed to be read by any other statement, and removing the memset does not affect the program’s results. Nevertheless, the optimization resulted in a security vulnerability that was invisible in the source code.

Every potential WYSINWYX effect underlines machine code analysis tools’ advantage over source code analysis tools. The prior section discussed the problem of not having access to a program’s source code. However, even developers who have the source rarely have source code for all the code eventually included in the executable. Usually, they link their source against third-party libraries that are only in binary form. Especially in the embedded software, source code may include inline assembly. In some cases, modifications are made to the executable after the source is compiled. Source tools usually target programs written in one language, but an executable may be compiled from source in many different languages.

One of the most prominent reasons for the WYSINWYX effect is that source language semantics are usually underspecified. For example, C and C++ do not specify the function call argument order of evaluation. (See the sidebar for an example of this from Effective C++ by Scott Meyers[14].) Technically, problems due to source language ambiguity are visible in the source code. However, analyzing all the possible behaviors of an ambiguous statement quickly becomes intractable. For this reason, source analysis tools (and often programmers) usually resolve ambiguity by arbitrarily picking one plausible interpretation. Since there is no guarantee that their choice will be the same as the compiler’s, language ambiguity is considered to be a major cause of the WYSINWYX effect.

The choices a compiler makes to resolve source language ambiguities can have an important effect on the presence of vulnerabilities. Security exploits frequently rely on details such as data object layout, order of variables on the stack, whether a value is stored in RAM or only in registers, and so on. In a language like C or C++, most of these details are left to the discretion of the compiler.

A source analysis tool cannot consider all the different options a compiler might choose, at least not without making vague approximations. Machine code analysis, however, has the advantage of seeing the exact decisions the compiler made. For this reason, machine code analysis has the potential to be more precise than source code analysis.

Recent advances in machine code analysis

Researchers have made great strides in applying static analysis to machine code. Several groups have demonstrated the utility of machine code analysis for identifying malicious code[6,7,11,12], security vulnerabilities[8], and flaws that affect reliability[3,9].

One use of machine code analysis is to create an Intermediate Representation (IR) that captures a program’s semantics. Source analysis tools for finding bugs and security vulnerabilities often rely on information (such as types) readily available in source but not machine code. The goal of IR recovery is to fill that gap and allow developers to use source analysis techniques on machine code. Compared to developing specialized techniques or adopting source analysis techniques one at a time, IR recovery enables many techniques at once.

One advanced tool for IR recovery from executables is CodeSurfer/x86, which is the result of collaborative research between GrammaTech and the University of Wisconsin. CodeSurfer/x86 is a valuable tool for security analysts who need to understand the potential impact of a piece of malicious code. While the tool currently supports x86 machine code analysis, work on supporting other processor architectures, including PowerPC Architecture and ARM, is underway. Its purpose is to construct an IR similar to those that a compiler or source analysis tool uses. Specifically, the recovered IR represents the following information:

• A disassembly listing
• Control flow graphs, with indirect jumps resolved
• A call graph, with indirect calls resolved
• Information about the program‚Äôs variables
• Possible values of pointer variables
• Sets of used, killed, and possibly killed variables for each control flow graph node
• Data dependencies, including dependencies between instructions that involve memory access
• Type information (for example, base types, pointer types, and structs)

CodeSurfer/x86 performs IR recovery from an executable that runs on an Intel x86 processor. The IR can be used as the basis for building further analyses to find bugs and vulnerabilities or used to browse through a GUI interface. Figure 2 shows the recovered IR for a version of the infamous Nimda virus. The visualized IR components include the disassembly listing, possible data values at chosen program point, and call graph.

Many factors can complicate IR recovery. CodeSurfer/x86 does not rely on symbol table or source code information because such information is often stripped from COTS products. Even if this information was present, it would not be reliable in potentially malicious code. Recovering information about potential pointer values requires analyzing both pointers and numeric values simultaneously because address values and numeric values cannot be easily distinguished[1]. Type information must be inferred based on data access patterns because no structured data types are available[2].

Despite the difficulty in performing IR recovery, the technology has advanced far enough to start producing results. Balakrishnan and Reps recently demonstrated IR recovery use in a Windows device driver analysis[3]. They found that CodeSurfer’s IR recovery produces precise results on device drivers and demonstrated that by building on the recovered IR, they could adapt a technique for analyzing device driver source code to analyze machine code and replicate some of the same results[5]. Analyzing the machine code also can help address the WYSINWYX issues discussed earlier.

Meeting safety-critical needs

Machine code analysis is already playing a valuable role in identifying bugs and security vulnerabilities in software as well as helping users assess third-party code. Safety-critical software producers are expected to start using machine code analysis on their own software to account for the WYSINWYX effect. Both increasing need and increasing tool support and capabilities will continue to drive this growth in machine code analysis.

References

1. Balakrishnan, G. and T. Reps. Analyzing Memory Accesses in x86 Executables. International Conference on Compiler Construction. 2004. Barcelona, Spain: Springer Verlag. pp. 5-23.
2. Balakrishnan, G. and T. Reps, DIVINE: DIscovering Variables IN Executables. VMCAI. 2007. Nice, France.
3. Balakrishnan, G. and Reps, T., Analyzing stripped device-driver executables. TACAS, 2008.
4. Balakrishnan, G., T. Reps, D. Melski, and T. Teitelbaum. WYSINWYX: What You See Is Not What You eXecute. Proc. IFIP Working Conference on Verified Software: Theories, Tools, Experiments (to appear). 2005. Zurich, Switzerland.
5. Ball, T. and S.K. Rajamani. The Slam Project: Debugging System Software via Static Analysis.
6. Christodorescu, M., S. Jha, D. Maughan, D. Song, and C. Wang, eds. Malware Detection. Advances in Information Security, ed. S. Jajodia. Vol. 27. 2007, Springer.
7. Christodorescu, M., S. Jha, S.A. Seshia, D. Song, and R.E. Bryant. Semantics-Aware Malware Detection. IEEE Symp. on Security and Privacy. 2005. Oakland, CA.
8. Ganapathy, V., S.A. Seshia, S. Jha, T. Reps, and R.E. Bryant. Automatic discovery of API-level exploits. International Conference on Software Engineering. 2005.
9. Godefroid, P., M.Y. Levin, and D. Molnar. Automated Whitebox Fuzz Testing. 2007, Microsoft Research MSR-TR-2007-58.
10. Howard, M. Some Bad News and Some Good News.
11. Kinder, J., S. Ktzenbeisser, C. Schallhart, and H. Veith. Detecting Malicious Code by Model Checking. Conference on Detection of Intrusions and Malware and Vulnerability Assessment. 2005.
12. Kruegel, C., W. Robertson, and G. Vigna. Detecting Kernel-Level Rootkits Through Binary Analysis. Annual Computer Security Applications Conference. 2004.
13. Leveraging Cybersecurity – Interview with Daniel G. Wolf, Information Assurance Director, National Security Agency. Military Information Technology, Online Edition. February 9, 2004.
14. Meyers, S. Effective C++, Third Edition. 2005: Addison-Wesley.