Research On Dynamic Program Analysis Technique For Software Security

To mitigate ever-growing malware and network attacks, software security drawsmore and more attentions. This dissertation mainly focuses on two directions ofsoftware security: automated software testcase generation and automated softwarevulnerability discovery. This dissertation involves two major techniques: dynamicsymbolic execution and dynamic taint analysis. Both of them belong to the domain ofdynamic program analysis. The content of this dissertation includes five aspects.Fist, this dissertation investigates the background, developments, challenges andsolutions systematically. Then this dissertation compares twelve existing dynamicsymbolic execution software. Research shows that dynamic symbolic execution is aresearch hot spot and it has gained great achievements. However, the wide applicationof the technique is obstructed by a number of challenges, such as path explosion,floating-point computations, non-linear computations, symbolic pointers and so on. Theinvestigation provides theoretical fundamentals and important references for subsequentresearches.Second, this dissertation researches automated software testcase generation basedon dynamic symbolic execution. This dissertation designs and implements dynamicsymbolic execution software, termed by SMAFE for Windows executables. SMAFE isable to analyze binary code directly without the presence of the source code. SMAFEhas four contributions. The first one is that SMAFE executes native x86instructionssymbolically without any intermediate representations, thus the efficiency of SMAFE isimproved. Then SMAFE designs a constraint intermediate language, so that itsportability is increased. Afterwards, this dissertation proposes several heuristics toaddress overlapping symbols, so that the accuracy of dynamic symbolic execution isboosted. Last, SMAFE utilizes a lightweight method for constraint generation, so as toreduce runtime overhead. Experiments show that SMAFE can achieve satisfactory codecoverage with reasonable time and space cost.Based on the previous research topic, this dissertation continues to researchautomated software vulnerability discovery. This dissertation designs and implementssoftware which is able to find vulnerabilities embedded in Windows binaries, named SEVE. SEVE is developed on top of SMAFE, so its key technique is also dynamicsymbolic execution. To facilitate vulnerability discovery, this dissertation proposes fourimprovements. The first one is active vulnerability discovery which injects vulnerabilityconstraints into path conditions actively. So the method can find more vulnerabilitiesthan passive alternatives. Besides, SEVE is actually a system for vulnerability discovery.In other words, SEVE can be enhanced by developing new plugins. Furthermore, toimprove the accuracy of dynamic symbolic execution without increasing runtimeoverhead, SEVE proposes function models. Finally, SEVE introduces an optimized pathexploration algorithm, thus the efficiency of vulnerability discovery is raised.Next, this dissertation presents the research on software vulnerability discoverybased on dynamic taint analysis. Essentially, dynamic taint analysis is a kind ofsingle-path analysis technique, so it is able to handle software with much larger sizesthan dynamic symbolic execution. Then this dissertation designs and implements TVMwhich has four advantage points. The first one is that TVM introduces a high efficientdatastructure to store taints, so the overall efficiency is increased. Besides, TVM designsa fast method to track taint propagation which is complete and uniform. It is able toboost the efficiency of taint analysis and reduce the development complexity of TVM.After that, TVM is able to track taint propagation incurred by tainted pointers, thus theaccuracy is increased and false negatives are reduced. The last one is the design ofhigh-level vulnerability detection policies, so TVM can find the bugs of memoryfunctions.The last research topic involves the future development of dynamic symbolicexecution. This dissertation suggests five research directions. First, path explosionrequires thorough research because so far it is the major obstacle preventing the wideapplication of dynamic symbolic execution. Second, the research on solvers would be ahot spot since dynamic symbolic execution relies on solvers. So the boost of solvers iscritical to dynamic symbolic execution. Third, the specialization of dynamic symbolicexecution software should be considered in future. Since the analyzed software and thedemands of users vary a lot, specialization would be a practical method. Fourth, highefficient and easy-to-manage summary databases should be introduced in futuredynamic symbolic execution software. Summaries are essential to address pathexplosion. Furthermore, summaries are easy to reuse. So good summary databases canbenefit dynamic symbolic execution to a great extent. Last, the parallelization of dynamic symbolic execution would be an important research topic in future. Byutilizing exiting parallel infrastructures, such as multi-cores CPU, multi-cores GPU,clusters, grids and cloud computing, one can parallelize the processes of pathexploration, constraint solving and so on. Parallelization can indeed promote theefficiency of dynamic symbolic execution greatly.