A Research On Key Technologies Of Dynamic Symbolic Execution

Program analysis is an important method in research fields of program optimization, security vulnerability detection and malicious code detection. There are three categories of program analysis:static program analysis, dynamic program analysis and hybrid program analysis. Code obfuscation, a program protection technology, brought great challenges for these program analysis methods. There are three main problems of existing program analysis methods:1. Code obfuscation makes it very difficult to conduct precise static analysis, and path coverage of dynamic analysis is not good enough to detect malicious behavior or security vulnerability.2. The number of infeasible path in obfuscated program is huge. Control-Flow-Obfuscation like opaque predicates prevents path feasibility analysis.3. Some obfuscated program relies on external resources which must be loaded and located correctly to excute.This article researches hybrid program analysis methods and obfuscated program analysis to solve the problems mentioned above. And on the basis of analyzing the inter-procedure call processing of dynamic symbolic execution, external function, path feasibility analysis of obfuscated program, and the emulator for dynamic execution, it proposes a new dynamic symbolic execution scheme which effectively solved all three problems. The following are the main contributions of this article:First, it greatly mitigates the possibility of path explosion caused by repeatedly expanding the inter-procedure call in dynamic symbolic execution. Traditional dynamic symbolic execution methods like DART will expand all inter-procedure call and analyze the expanded result as part of the execution path, which will lead to redundant analysis of the same inter-procedure call when it appears in different paths. When there are embedded inter-procedure calls, the redundancy will be aggravated and eventually result in path explosion. Because of the huge number of path in obfuscated program, path explosion will prevent traditional dynamic symbolic execution from finishing the analysis within a reasonable time. The function summary is proposed in this article avoids such redundancy completely. All inter-procedure calls can be divided into two categories:function summary has been generated and not generated. The function summaries is used for analysis for those have already been generated. For those calls without function summary, recursively dynamic symbolic execution and generating will be done. The experiments conducted on prototype system proves the effectivity in reducing analysis time of this method.Second, this article points out that extract implicit inputs and makes them symbolic will enhance the path coverage rate after examing how external function affects the path coverage rate of dynamic symbolic execution. The results of external functions such as temporal correlation functions will change as time varies. Polymorphic malicious code can trigger malicious behavior by time or hide malicious behavior by the output variables of external functions. The premise of dynamic symbolic execution path coverage is that once an input generated according to the constraint expression of a path, it can drive the program to execute the path specified by the constraint expression. However the outputs of external function are out of control with dynamic symbolic execution, the actual execution path maybe not the same one specified by the path constraint expression. In other words, dynamic symbolic execution cannot ensure that a new execution path is explorered every time, and thus brings negative influence to path coverage rate. To deal with this problem, the method proposed in this article adds detection for external functions into dynamic symbolic execution, extracts implicit inputs containing external functions, uses SMT solvers generating the new inputs of implicit symbolic variables, then making sure the output of external functions can meet the the path constraint expression with current input throught the emulator. Otherwise, dynamic symbolic execution cannot satisfy the path constraint expression within a threshold. Then the path is infeasible. In this way, the path coverage rate for programs containing external functions in dynamic symbolic execution will improve.Third, this article applies improved dynamic symbolic execution to the path feasibility analysis of obfuscated program and implements the detection and analysis of execution path tree of it. Obfuscated program contains a large amount of infeasible paths, and control flow obfuscation like opaque predicates can entirely transform the control flow, thus static analysis cannot perform path feasibility analysis. The method in this article analyzes obfuscated program by implicit dynamic symbolic execution. When dynamic symbolic execution cannot drive obfuscated program to execute some paths, the new method will dump binary code of these paths and static analysis them to get a Candidate Obfuscation Path Set. Then IDSE, Implicit Dynamic Symbolic Execution, executes the program slice containing these paths and judges the feasibility. The actual execution path of obfuscated program can be detect by the new dynamic symbolic execution, and further analyzing behavior of obfuscated program.Last, this article improved the emulator based on QEMU so that it can detect external funtions and modify the environment parameters of guest operating system. Furthermore, the emulator can automatically detecting the system API calls in the obfuscated program and load the external resources, providing execution environment for the obfuscated program. Meanwhile, this scheme utilizes the system API sequence and the frequency of calling key system API as the signature of polymorphic malicious code, in order to efficiently detect and classify polymorphic malicious code.