Weekly Status

23/10/18

As per the weekly meeting, I decided to try investigating some ML techniques in order build up a tree of io_vecs in a more principled way. The initial thought was to use hierarchical clustering. However, that does not work, because even with fine-grained clusters, there needs to be some inputs to give the FUT. Choosing a test from the fine-grained clusters would not give us the performance we need, as in it would be O(n) where n is the number of functions we can identify. I decided to go with decision tree learning in the end.

sklearn has an implementation of the decision tree learning algorithm. I was able to write a simple python script to generate two decision trees using two different criteria for tan, sin, cos. My first attempt resulted in an over fit tree, but does provide a path towards what we want. Later, Sushant performed some transformation on the data I used, and came up with a much better tree. We will discuss this at the meeting.

17/10/18

Sources of inaccuracy in static analysis:

• 44 functions that take in a locale_t argument but is not used.
• 88 functions take in long double, and so are passed onto the stack.

I have added support for system calls, and I am now correctly handling floating point arguments. System calls are handled by passing in a map of which registers they use to pass arguments, and this map is consulted when needed. I store all potential values the system call can be by tracking write immediates to RAX, but it is often one singular value. Floating point arguments are passed in the XMM* registers, and they are used in the order that they are needed, so foo(int, int, double) will use XMM0 for the first double argument. The only thing that can be said if XMM0 is used is that the function has at least one argument, if XMM1 is used, then the function has at least two arguments, and so on. This is how I treat an XMM* use-def. Combining these two efforts, I have brought up my 70% accuracy to 85%. There is one final bug that I am aware of, and I think that with it fixed, we will get the >90% success rate we are looking for. I decided to start working on the Input/Output Vector generation for the second half of the week.

The system right now supports only primitive times, but any number of arguments. An input vector is the values given to a function, the output vector is the value of the return value of the function. Included with the input/output vector is the function name for which this tuple applies. My system currently organizes io vecs into a tree by checking for equality (currently if all input arguments and return value are of the same type and value). Based on the io vec equality, a new leaf is added to the tree. A different tree is generated for each function arity. Then for each unknown function, we deduce its argument count, and then traverse the generated tree. If the function produces the output value from the input values, then the system moves to the pass branch of the binary tree. Otherwise, it tries the input from the fail branch. Io vecs are tried until there is a definitive answer, or there are no more io vecs. In the latter case, we report we do not know the function is, but we can provide possible candidates. In my initial testing for tan, cos, and sin was able to distinguish between the three functions.

However, we need a better way of inserting io vecs into the binary tree in order to achieve a balance. I have an algorithm to discuss, but perhaps I am overthinking it and a red-black tree will satisfy my needs.

9/10/18

I tried to see how we do identifying signatures when the return value is taken into consideration. I tried the following heuristics:

• Return smallest signature that resulted in the most common return value
• Return smallest signature that resulted in different return value

None of these significantly improved on the results already reported. So, as per last week's meeting, I decided to implement a simple static analysis pass to infer the number of arguments a function takes. The algorithm is fairly straightforward:

Iterate over all instructions in a function, only following call and unconditional jump instructions. If there is a path to an instruction that writes to an argument-holding register before it is read, then that register cannot be used as an argument. If a register cannot be used as an argument, all subsequent registers in the ABI order cannot be used as an argument. Conversely, if a register is determined to be an argument carrier, registers used before in the ABI order must be argument carriers. Continue until there are no more instructions or when all registers have been determined as argument carriers.

This approach is much more successful. I am not quite done with the implementation, but I already have 70% accuracy. Indirect calls and syscall are not yet supported (they are just skipped for now), and I am not quite handling floating point correctly. These are the main sources of inaccuracy.

Due to the difficulty in establishing correct state for an unknown binary, I think that we should pursue generating input/output vectors on a per argument count basis.

2/10/18

As per last week's discussion, I added in support for loading shared libraries using dlsym instead of using mmap. This revealed some issues with my function argument inference code. The most obvious of which is that string or wide string functions, or functions that use those functions with pointers that I provide, fail. This is because I make sure that there are no null terminators in the memory area I allocate. I have changed this to add a null terminator at the end of the allocated buffer. However, removing that logic could allow me to infer which parameter is expected to be a string by getting the fault address and seeing if it is the one of the guard pages surrounding my allocated buffers.

The numbers for libc and libcrypto are the following:

libc

Total Functions : 1992

Identified Functions : 1775

Crashed Functions : 217

Full Match : 427

Match in possible set : 472

Incorrect Match : 876

---

libcrypto

Total Functions : 3545

Identified Functions : 1960

Crashed Functions : 1585

Full Match : 593

Match in possible set : 605

Incorrect Match : 762

---

These numbers are not great. Specifically, the incorrect matches are quite high. The main problem is that we do not know the number of arguments. So when we run the test for zero arguments, we set all the registers to 0xFFFFFFFFFFFFFFFF. The Function Under Test (FUT) might actually have a signature of < int >, and so might consider this value as -1 which might be interpreted as an invalid check. The FUT returns early, and we register that as a successful run. Since the < void > test runs successfully, we pick that as a the signature.

25/9/18

I finished the function argument inference code, and ran it against musl libc. The results are the following:

2796 identified functions 1082 unidentified functions

Unidentified functions are present because all inputs cause a signal to be issued. The reasons for this are the following:

• A function relies on global variables, such as mutex locks, which either are not mapped or uninitialized
  • srandom(unsigned), setpwent()
• An unbounded string function executes until it finds the null terminator, which will never happen in our void* inputs. This function hits the guard page surrounding the allocated pointer. I am currently not testing for char* although I have made support for it. A quick test shows that at least some of these unidentified functions can be found by adding char* to the list of supported types.
  • strlen(char*), mkstemp(char*)
• The function issues a trap instruction
  • __restore
• The function allocates memory using malloc
  • strdup(char*)

Sources of function signature inaccuracy:

• Failed check early in function does not exercise main functionality
  • malloc(unsigned int) is inferred to be malloc(void*)
• Unsupported function argument, i.e. the function signature takes a float
  • remainder(double, double) is inferred to be remainder({void, int, void*})
• Functional equivalency of a int and void*
  • We infer ffs(int) to be ffs({void, int, void*})

Of the 2796 functions, one of the detected signatures matches the actual function signature 918 times. We exactly match the function signature (meaning there is one deduced signature and it matches the actual signature) for 333 functions.

18/9/18

Based on last week's discussion, I started the development of the function argument inference code. The design follows a similar line as fosbin-flop, in that I map the binary to the application's address space and use a binary descriptor to list out the location of functions. Then for each function in the binary, I invoke it N times, once for a unique combination of {int, double, char*, void*} for up to 5 arguments, plus once for no arguments. As input to the functions, I use nominally good values: 1 for int, 2.0 for double, a malloced string of length 48 for char*, and a malloced region 1024 bytes long for void*. I have not yet programmed the logic that determines success, but the logic is simple: I select the set of function types that minimizes the argument count but also returns without fault and does not change errno.

Once that is implemented I need to start generating the input-output mappings for library functions, and organizing them according to input types.

Topics for discussion:

1. The number of type combinations is large. How to know which functions to actually test?
2. Is my success criteria good enough?

11/9/18

Fixed several bugs in the pass and runtime library, including how floating point numbers are handled. This required adding a new runtime function to handle floating types, because casting a double into a void* changed the bit layout and I was losing information. The python script (id-parser.py) that reads in the JSON output from the test runs is capable of generating C++ classes for functions that only use primitive types. This was an attempt to get some initial results. Using the libc-test repository which musl uses, I can compile and run all the tests, but I am focusing on the src/math/pow.c test for initial results.

The pow function is called over 11,000 times in the course of the test, so I had id-parser.py cap the tests at 10 for now. As of this writing, the pow identifier does not find pow in the statically linked pow unit test, and I am investigating why. UPDATE: pow uses the GOT, and we don't know where that is going to be in the binary.

On the evaluation front, I found in GitHub the source of many different malware, including Mirai. Mirai looks to be ideal for a case study; it is statically linked, runs on embedded devices, well-known, and recent. Additionally, Mathias contacted a researcher who is compiling a large corpus of malware, and I have been granted access to the repository. I have not looked through it yet, but I am sure that there will be other malware case studies we can include.

Something to address in the paper from my presentation at the weekly meeting: Function call sequences that must happen in order (e.g. open-write-close) are not supported yet.

4/9/18

Created LLVM pass and runtime library to capture the input and return values for function calls. The pass is simple right now. It simply finds all CallInst, inserts a new function call to the runtime library lof_precall, and 0 or more calls to another runtime function lof_record_arg. Finally, a function call to lof_postcall is added immediately after the CallInst to record the return value. All function calls and function arguments are stored in a simple stack implementation using a linked list implementation I wrote. In other words, each function is represented as a stack of arguments, and each function argument stack is pushed onto a global stack. All data is written to a file called lof-output.json and is obviously in an easily parseable JSON format.

The library functions have the following function signatures:

lof_precall(void* funcaddr)

lof_record_arg(Data value, TypeID typeId, size_t size)

lof_postcall(Data value, TypeID typeId, size_t size)

Data is a union of various primitive types, and TypeID is an enum provided by LLVM that indicates if the value is a float, int, void*, etc.

Questions for discussion:

1. How to handle void*? Currently I am just reading the first 4 bytes.
2. How to handle structs? I'd like to punt this down the road for now until primitive types are handled.

28/8/18

Evaluated memcpy, memmove, strcpy, strncpy against busybox and nginx. 100% accuracy. Go me. This shows that we can identify functions post-execution by controlling their inputs, at least for some functions. Those functions that require some initial state probably won't work, but maybe we can find a lot of other functions with more function identifiers. We need an automated way to generate them.

Evaluated approaches for automating the generation of function identifiers. Problems I am trying to solve:

1. A priori, I don't know how a valid function execution changes program state
2. I don't know how to get valid input to a function to measure program state change

Unit tests seem to solve these problems, because the programmer writing the test would know best good inputs to a function (theoretically), and any relevant state change would be tested for in the unit test.

Two approaches were discussed:

1. Modify the various existing testing frameworks libraries currently use to memory map the binary into the address space first, and then replace function unit test is testing with a function in the binary. If test passes with binary function, then binary function == unit test function.
2. Instrument testing framework to capture the function parameters and return values all unit tests use when executing a function we want to describe. We save all input and return values (including struct subfields and following pointers recursively), and automatically create a fbf::FunctionIdentifier subclass containing the input. We then use the currently existing framework to compare functions in the BUA. A successful identification would be if the return value of the BUA function (or the underlying data if a pointer is returned) is the same as the unit test function return value, and any change in the input data pre- and post-execution should be the same in the unit test function and the binary function.