基于条件范围约束的越界访问检测方法

Detecting Out-of-Bounds Accesses with Conditional Range Constraint

程序执行时的越界访问将导致异常的行为,已有的越界检测方法存在效率低或精度不高的缺点.分两步检测程序中的越界访问语句在约束产生阶段,提出一个流敏感、过程间的约束状态产生算法,为每条语句建立一个范围约束集合和值约束集合;在约束求解阶段,利用线性规划计算程序访问的内存大小和偏移量,报告可能的越界访问漏洞.实验表明,检测效率明显高于路径敏感的范围分析方法,而平均检测精度高于80%.

Out-of-bounds accesses can lead to nondeterministic behaviors. Proposed in this paper is a novel detection method based on conditional range constraint. It divides the detection process into two phrases： the constraint generation phase and the constraint resolution phase. In the phase of constraint generation, a flow-sensitive, inter-procedure algorithm is proposed to propagate range constraints and value constraints respectively. In the constraint resolution phase, a linear programming solver is used to determine the bounds of abstract memory locations and the offset. The experiment results show that the method proposed is effective, and its precision is higher than 80 %.