基于抽象解释的变量值范围分析及应用  

A Method of Variable Range Analysis Based on Abstract Interpretation and Its Applications

作　　者：王雅文[1] 宫云战[1] 肖庆[1,2] 杨朝红[2] 

机构地区：[1]北京邮电大学网络与交换技术国家重点实验室,北京100876 [2]装甲兵工程学院信息工程系,北京100072

出　　处：《电子学报》2011年第2期296-303,共8页Acta Electronica Sinica

基　　金：国家863高技术研究发展计划重点项目(No.2007AA010302);国家863高技术研究发展计划(No.2009AA012404)

摘　　要：精确的变量值范围分析对于编译器优化、静态分析和软件测试至关重要.在介绍抽象解释理论的基础上,扩展了经典的区间抽象,首次提出区间集的概念并定义了新的数值型区间集代数、布尔型和引用型区间代数,给出了统一的基于抽象解释的变量值范围分析方法RABAI,引入拓宽算子计算循环体变量范围,对过程参数定义了特殊的未定义取值(undefined),使用函数摘要来计算过程调用对程序上下文状态的影响.该方法能有效压缩变量取值空间,检测出程序中的矛盾语句节点和不可达路径,实验表明基于RABAI方法的缺陷检测工具DTS能有效降低误报率.Variable range analysis is essential for compiler optimization,static analysis and software testing.This paper extends the classical interval abstraction,and defines the new numeric interval-set algebra,Boolean interval algebra and reference interval algebra.Then it presents a unified method of variable range analysis based on abstract interpretation（RABAI）.This method uses widening operator to compute variable range in loop,undefined value to describe procedure parameters,and applies function summary as a stand-in for the function.RABAI compresses variable value ranges,and can detect infeasible paths in program.Finally RABAI is applied in Java code analysis tool DTS,and DTS can reduce the false positive rate of bug checking result.

关 键 词：软件测试 静态分析 抽象解释 区间抽象 范围分析 不可达路径 

分 类 号：TP311.5[自动化与计算机技术—计算机软件与理论]