OBFUSCATION WITH TURING MACHINE

Abstract

Obfuscation is an important technique to protect software from adversary analysis. Control flow obfuscation effectively prevents attackers from understanding the program structure, hence impeding a broad set of reverse engineering activities. In this thesis, a novel control flow obfuscation method is proposed. It employs

Turing machines to simulate the computation of branch conditions. By weaving the original program with Turing machine components, program control flow graph and call graph would become more complex. Moreover, due to the computation complexity of a Turing machine, program execution flow would become much more complicated and resilient to advanced reverse engineering approaches through symbolic execution and concolic testing.

A prototype tool based on the proposed technique is implemented. Comparing with previous work, the proposed control flow obfuscation technique bears three distinct advantages. 1). Complexity: the complicated implementation of a Turing machine makes it hard for attackers to understand the program control flow structure. 2). Universality: theoretically, Turing machines can encode any computation. The obfuscation is built on top of the LLVM intermediate representation so the application scope is broadened to almost every language with an LLVM front-end compiler. 3). Resiliency: our obfuscation is shown to be very resilient to advanced analysis tools. We have evaluated the method in terms of functionality correctness, potency, resilience, stealth, and cost, respectively. The experimental results show that the proposed technique can obfuscate programs in stealth with good performance and robustness.

Chapter 1 |

Introduction

Obfuscation is an important technique for software protection. Attackers could take advantage of the state-of-the-art techniques [21–23] to recover program source or high-level code from executables, exploit software vulnerabilities, and steal algorithm implementations. Software obfuscation is mostly designed to impede such (malicious) reverse engineering process. It is also used by malware developers to hide their malicious intent.

Recently, software security has drawn more and more attention because of, for example, infamous ransomware attacks and severe vulnerabilities such as the “WannaCry” incidence [34] and the OpenSSL “Heartbleed” bug [33] . All of these malware programs exploit vulnerabilities inside a program. To launch such attacks, attackers usually need to recover the control flow structures of the victim programs first. Symbolic execution and concolic testing are widely-adopted techniques to cover execution paths and explore program structure [1,30–32] . Typical symbolic execution engines such as SAGE [17] and KLEE [19] could yield new input which leads to a new execution path by solving branch conditions with a constraint solver. After all execution paths are traversed, control flow graph of the program could be restored with the traversing information. Such tools have been proven to be very effective in analyzing program control flow structures [25] .

Hence, a lot of anti-reverse engineering research has focused on preventing adversaries from analyzing important path conditions in a program [5,7–9,20] . Control flow obfuscation is one of these cutting-edge techniques to combat these reverse engineering tools. Control flow obfuscation aims at hiding path conditions and complicating the execution flow within a program. By rewriting or adding extra control flow components, the program path conditions become difficult or even impossible to analyze. Existing research [2] have demonstrated the effectiveness of control flow obfuscation.

In this thesis, we propose a novel control flow obfuscation method which leverages

Turing machine to compute path conditions. The Church-Turing thesis [24] states that the power of Turing machines andλ-calculus is the same as algorithms, or the informal notion of effectively calculable functions. Formally, Turing computable, λ-computable, and general recursive functions are shown to be equivalent, and informally, the thesis states that they all capture the power of algorithms or effectively calculable functions. This means any functional component of software can be re-implemented as or transformed into a Turing machine; the replaced code component and its corresponding semantic equivalent Turing machine is called Turing Equivalent.

Our method is to simulate important branch condition statements in a program with semantically equivalent Turing machines. A Turing machine behaves as a state machine so it would bring in a large amount of extra control flow transfers and basic blocks to the overall program control flow graph. Moreover, a typical Turing machine leverages a transition table to guide the computation, and such transition table-based execution would introduce additional computations and make the overall execution flow much more complicated. We envision the proposed technique would largely complicate the protected program, and also bring in new challenges for reverse engineering tasks. Our method can also be used to obfuscate other computation as well.

To obfuscate a program through the proposed Turing machine obfuscation technique, we first translate the original program source code into a compiler intermediate representation. Our Turing machine obfuscator then selects branch condition statements for transformation; the transformed instructions will invoke its corresponding Turing machine component, which is semantically equivalent to the original branch condition. After finishing the execution in the Turing machine “black box”, the execution flow returns back to the original instruction, with a return value which determines the branch selection. Inspired by previous work [4] , we evaluate our obfuscator regarding five aspects which are functionality correctness, potency, resilience, cost, and stealth. Results indicate that Turing machine obfuscator could effectively obfuscate commonly-used software with acceptable cost and robustness.

This thesis is organized as follows. Section 2 discusses related works on obfuscation, especially control flow obfuscation. Section 3 presents the overall design of Turing machine obfuscator. Obfuscator implementation is discussed in Section 4. Section 5 presents the evaluation result of our proposed technique. We further present discussion in Section 6, and conclude the theis in Section 7.

In Turing machine obfuscator, we collect all comparison instructions for branch predicate instructions (e.g., icmp). Through use-def chain analysis, we also locate all instructions that determine the value of the conditional branch instruction, all these instructions are deemed as transformation candidates.

OBFUSCATION WITH TURING MACHINE