Control Flow Graph And Call Graph Extraction System Based On Dynamic Symbolic Execution

With the improvement in living standards and the development of technique,our life and software have become more and more inseparable.Whether it is daily communication,listening to music,or our study and work,software is playing an important role in our lives.However,there are more and more insecure factors in the current software.For example,some software has vulnerabilities and some software is malware.Thus,it is important to analysis the program and find it’s potential threat,For binary program analysis,the extraction of control flow graphs and call graphs is a very important step,because control flow graphs and call graphs can show the basic structure and call relationships of a program.First,in order to build a system for control flow graph and call graph extraction,the thesis compares some techniques and draws their strengths and weaknesses.Finally the thesis chooses the dynamic symbolic execution technique,because dynamic symbolic execution technique can explore all paths in theory.Based on the current advanced Angr platform,the extraction system of control flow graph and call graph has been developed in this thesis.Besides,the current system can complete the conversion of intermediate languages,and extract control flow graph and call graph of the program.Then,in order to reduce the time consumption caused by the exponential growth of the path during dynamic symbolic execution,the thesis proposes a parallel exploration algorithm based on the multi-cores of CPU.With the use of all cores’ computing resources,it is easy to shorten the time for path exploration.At the same time,after detailed analysis,I discover that if the main process directly transfers the path information to the child process,there will be a lot of time and memory consumption.Therefore,the thesis proposes to encode the path information that needs to be transmitted,and while the child process is running,the decoding method is used to perform multi-process path exploration.Finally,the thesis finds that the dynamic symbolic execution tool the thesis developes has an advantage in path exploration.Subsequently,the thesis tests the effect of the multi-process parallel exploration algorithm.I discover that the current algorithm can explore the program path faster without increasing memory consumption.Thus,the currently proposed exploration algorithm is effective.