-
Notifications
You must be signed in to change notification settings - Fork 2
Home
Identifying functions within a binary is the first step to understanding a binary, and must be done whenever the source is unavailable --- an increasingly more common reality today. Unfortunately, function identification in stripped binaries is a time-consuming, tedious, and error prone task. Semantic information, such as variable names, types, and structure definitions, are replaced with register accesses or offsets from RBP, and functions and global data are referenced as offsets from RIP instead of human-readable names. However, in malware analysis and other reverse engineering tasks, the analyst must make sense of the binary under analysis despite its difficulty. Because applications are typically built using open-source libraries, ideally we would want to identify the library functions automatically, and leave the task of identifying application specific functionality to the analyst, saving a significant amount of time and money. Current state-of-the-art techniques for function identification involve a mixture of pattern matching and heuristics, and quickly fail in the presence of new compilers, optimizations, custom implementations, and defense mechanisms.
The problem is that even the best static analyses cannot capture the complete effect of execution on program state. When referring to program state here, we are referring to the set of register values and persistent memory (global and heap memory, but not the stack). In order to be useful, functions must modify the program state in a measurable way, and, assuming good programming practices, each function must modify the program state in a unique way. If a function does not modify the program state in a measurable way, the function is essentially dead code and the compiler will likely remove it at even the lowest optimization level. Architecture specific optimizations for common operations like memcpy aside, if two functions modify the program state in the exact same way, then the two functions perform the same task, and the programmer herself will likely remove the redundant code.
Therefore, I propose the following hypothesis: dynamic analysis of program state changes post-execution will significantly improve accuracy in function identification. Specifically, I want to answer the following research questions:
- Can an anonymous function's effect on memory post-execution be unique enough to identify it as a specific known function within a static library?
- Can an analyst perform an automated dynamic analysis to identify a significant number of functions within an unknown stripped binary providing nothing other than the location of functions within the binary (NB: finding the location of functions within a binary is orthogonal to this research)?
- What input is needed to uniquely identify known open-source library functions, and how sensitive is function identification tied to input?
To accomplish answering these research questions, I propose a dual phase approach. First, implement a system that takes in as input the binary under test (BUA) and locations of functions within the BUA. The BUA must be statically linked, otherwise functions could be trivially found via the PLT. This host system maps the binary into its address space, and then executes each function in the BUA with input provided by the host system. It then compares the resulting state with built-in function identifiers. These function identifiers will initially be for identifying memcpy, memmove, strcpy, strncpy, and md5sum. I plan to run this analysis on self-implemented micro benchmarks, as well as real-world embedded applications nginx, OpenWRT, Mozilla's Things Gateway, and busybox, and commonly used open-source libraries such as OpenSSL and libpng.
Once the initial proof-of-concept phase is complete, the second phase will build upon what was created during the first phase, and extend it to automatically create function identifiers. I plan on using the functional test suite that is included in many open-source projects to determine good inputs, and measure the effects on the memory address space post-execution using the data gathered from the tests. These measurements can then be used to create a fully-formed function identifier, with good known inputs and expected outputs for each input. The automatically generated function identifiers will then be evaluated against the real-world embedded application suite from phase one. The data can be gathered by creating an LLVM pass to instrument callsites to record input parameters and return values. This pass will be combined with a static runtime library which will be linked with any application compiled with the new pass. LLVM's SafeStack implementation performs similar actions to my proposal, so this is a feasible approach and can be done quickly.
Manually creating function identifiers quickly becomes infeasible when multiple, whole libraries are involved. It would be hard to understand all functions in a library well enough to effectively write a function identifier for all library functions. Therefore, I created a Python script to parse the results of unit tests, and generate unique FunctionIdentifier subclasses, which can be compiled with the hand-written classes. Each FunctionIdentifier subclass now returns the fraction of failed tests to total tests, and if that fraction is higher than a configurable threshold, we declare the function under analysis to be the function the identifier is looking for. Using this framework, I was able to generate a function identifier for __slowpow, an implementation for the pow function in the libm math library. The unit test for pow executed pow over 11,000 times, so the Python script limited the test cases to the first 10. A smarter way to determine which test results to use is likely needed.
Trying every function identifier for every function in a binary results in a state explosion. We need a way to trim down the possible testcases. One way to perform such pruning is to deduce number and type of function arguments for each function in the binary, and then only use identifiers that test for those function signatures.