The Research Of Control Flow Obfuscation Algorithm Based On Nesting Complexity

The wide application of computer software greatly improves the social productivity, and also brings a lot of security problems. Especially in recent years, with the rapid development of mobile Internet, the use of Android smart phone and Java language is more and more popular. Because of the openness of Android operating system, a large number of Android applications are cracked and implanted with trojans and viruses, which not only brings huge losses to the legitimate rights and intellectual property of software authors, but also threats to personal privacy and data security of smart phone users. So it has great significance to research more effective software protection technology.Code obfuscation is the key technology of software protection which turns the program’s outline, data flow and control flow into a more elusive version and preserves the semantic information at the same time, and can effectively prevent the program from malicious cracking.This thesis introduces the present research situation and several code obfuscation algorithms, mainly analyzes the control flow obfuscation algorithm based on random insertion, discusses the assessment method of code obfuscation, studies the JVM instruction set and the Java bytecode file format.The control flow obfuscation algorithm based on random insertion strategy has an uncertain obfuscation potency and overhead. To solve the problem, a kind of control flow obfuscation algorithm based on nesting complexity (OB_NC) is proposed. The algorithm calculates the cost of instructions and the nesting depth of loop to quantify the overhead caused by obfuscation, measures the complexity of control flow with nesting complexity metric and selects the insertion point of garbage code based on the idea of group knapsack, which improves the obfuscation potency as much as possible within the cost threshold. Analysis and experimental results show that compared with the algorithm based on random insertion, the program obfuscated by OB_NC algorithm has more complex control flow, higher obfuscation potency and lower time overhead.At last, the structure of Android application is analyzed, and the principle and insufficiency of the current mainstream DEX plus shell technology is discussed. On this basis, the OB_NC algorithm is applied to the safety reinforcement of Android application, and its feasibility is verified.