基于延后策略的动态多路径分析方法

Exploring Multiple Execution Paths Based on Dynamic Lazy Analysis

多路径分析是弥补传统动态分析方法的不足、对可执行程序全面分析的重要方法之一.现有多路径方法主要采用随机构造或者根据路径条件构造输入进行路径触发,这两者均存在路径分析不全面和缺乏针对性的问题.文中通过对路径条件分析,确定了检测条件的基本组成元素,提出了弱控制依赖和路径引用集的概念和计算规则,并以此为基础提出一种延后策略的多路径分析方法.在程序分析过程中,对特定的程序检测点和检测点条件,有针对性地进行路径筛选,从语义上进行路径表达式简化,在保证检测点可达和检测表达式具有相同构造形式的前提下,简化检测表达式,减少分析路径的数量.对7款恶意软件的分析实验结果表明,该方法提高了分析效率和准确性.

Exploring multiple execution paths is an important method to analyze executable files.Most researchers use randomly generated input or construct input by path conditions to explore program paths.These methods suffer from two flaws：they cannot analyze all the paths while there are too many useless paths to analyze.This paper introduces weak control dependence and path reference set to analyze path conditions.It also ensures three basic kinds of elements in checked conditions.Lazy analysis is proposed based on these definitions and theories to explore multiple execution paths.When analyzing a program,it can choose suitable branch conditions to explore paths according to a program check point.In this way,the number of path conditions can be decreased without missing any necessary conditions that guarantee the program to run to the check point and the checked condition to have the same structures.A prototype is implemented to make some experiments on seven malwares.Taint analysis is used to trace the input from outer space such as tainted files in the overall analysis process.Shadow memory is also exploited to increase the managing speed.The results show that the method decreases the number of path conditions and increases the efficiency when exploring multiple paths.