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

摘要

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 funtion 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.%精确的变量值范围分析对于编译器优化、静态分析和软件测试至关重要.在介绍抽象解释理论的基础上,扩展了经典的区间抽象,首次提出区间集的概念并定义了新的数值型区间集代数、布尔型和引用型区间代数,给出了统一的基于抽象解释的变量值范围分析方法RABAI,引入拓宽算子计算循环体变量范围,对过程参数定义了特殊的未定义取值(undefined),使用函数摘要来计算过程调用对程序上下文状态的影响.该方法能有效压缩变量取值空间,检测出程序中的矛盾语句节点和不可达路径,实验表明基于BABAI方法的缺陷检测工具DIS能有效降低误报率.