基于域敏感指向分析的区间运算在软件测试中的应用
Application of Interval Arithmetic in Software Testing Based on Field-Sensitive Point-to Analysis
-
摘要: 静态分析由于并不执行源代码,导致无法获取变量在实际运行中的取值,进而对一些和变量取值相关的缺陷检测带来了一定困难.利用符号执行和区间运算技术,虽然可以模拟程序实际执行时变量的可能取值范围,但对于结构体、数组等,由于不能对其成员进行独立描述,导致数据流无法支持域敏感分析,对和其成员变量相关的缺陷的检测难以实现,产生很多漏报.基于域敏感指向分析的区间运算模型,在域敏感指向分析模型的基础上对其进行了改进,将复杂数据类型拆分成独立的成员变量进行分析,并提出一种关联抽象取值集的类型系统,该系统可以保守的描述程序在动态执行时变量的可能取值.结合赋值语句的抽象语法定义,给出了该类型系统在数据流计算时的具体推导算法,并将其应用在缺陷检测系统(DTSGCC和DTSCPP)中.选用DTSCPP作为实验平台,对6个C++开源工程进行了测试,并对其数据进行了统计分析,结果表明该方法可以减少漏报,且测试效率与非域敏感版本相当.Abstract: Static analysis cannot obtain variable values in actual operation, because it does not execute source codes. It is difficult to detect defects which are related with variable values. Although the technique of symbolic execution and interval arithmetic can imitate the range of variable values in actual execution program, for structures, arrays, etc., their members cannot be described independently. It makes data flow analysis field-insensitive, and generates many false negative. The interval arithmetic model based on field-sensitive point-to analysis improves the classical model by splitting the complex data type into separate variables, and proposes a type system with a set of abstract values. This system can describe the range of variable values conservatively. When calculating the data flow, combined with the abstract syntax definition of assignment statements, we also propose a derivation algorithm to the type, and apply this type system in defect testing system (DTSGCC and DTSCPP). We choose DTSCPP as the experimental platform, six C++ open source projects as test objects. Experimental results prove that our method can efficiently lower the ratio of false negative in the condition of keeping the analysis time constant.