In this thesis we establish a quantitative framework to measure and study the security of code obfuscation, an effective software protection method that defends software against malicious reverse engineering. Despite the recent positive result by Garg et al.[GGH+13] that shows the possibility of obfuscating using indistinguishability obfuscation definition, code obfuscation has two major challenges: firstly, the lack of theoretical foundation that is necessary to define and reason about code obfuscation security; secondly, it is an open problem whether there exists security metrics that measure and certify the current state-of-the-art of code obfuscation techniques. To address these challenges, we followed a research methodology that consists of the following main routes: a formal approach to build a theory that captures, defines and measures the security of code obfuscation, and an experimental approach that provides empirical evidence about the soundness and validity of the proposed theory and metrics. To this end, we propose Algorithmic Information Theory, known as Kolmogorov complexity, as a theoretical and practical model to define, study, and measure the security of code obfuscation.
We introduce the notion of unintelligibility, an intuitive way to define code obfuscation, and argue that it is not sufficient to capture the security of code obfuscation. We then present a more powerful security definition that is based on the algorithmic mutual information, and show that is able to effectively capture code obfuscation security. We apply our proposed definition to prove the possibility of obtaining security in code obfuscation under reasonable assumptions. We model adversaries with deobfuscation capabilities that explicitly realise the required properties for a successful deobfuscation attack.
We build a quantitative model that comprises a set of security metrics, which are derived from our proposed theory and based on lossless compression, aiming to measure the quality of code obfuscation security. We propose normalised information distance NID as a metric to measure code obfuscation resilience, and establish the relation between our security definition and the normalised information distance. We show that if the security conditions for code obfuscations are satisfied (the extreme case) then the NID tends to be close to one, which is the maximum value that can be achieved.
Finally, we provide an experimental evaluation to provide empirical validation for the proposed metrics. Our results show that the proposed measures are positively correlated with the degree of obfuscation resilience to an attacker using decompilers, i.e. the percentage of the clear code that was not recovered by an attacker, which indicates a positive relationship with the obfuscation resilience factor.