Seeker:流敏感的需求驱动指向分析

Seeker: Flow-sensitive Demand-driven Points-to Analysis

需求驱动指向分析技术一般用于受到严格时间或内存限制的环境。提高需求驱动指向分析的流敏感度,可使一些变量得到准确的指向关系,但实践中存在具有较强流与数据依赖的大型软件系统,较难识别出对目标变量的指向关系产生贡献的程序语句。为此,提出一种流敏感的程序表示方法,通过定义一种上下文无关语言可达性的概念,搜索目标变量的流敏感指向关系。开发一种Seeker工具,能够为用户感兴趣的变量计算指向集合。实验结果表明,需求驱动的指向分析算法提高了流敏感上下文非敏感指向分析的效率。

Many demand-driven points-to analysis techniques are proposed to suit some environments bounded by strict limits of time and memory usage.Improving the demand-driven points-to analysis in a flow sensitive manner helps achieve precise points-to relations for some variables.Due to the existence of strong flow and data dependencies in the large-scale software systems,it is difficult in identifying effectively all the program statements contributing to the points-to relations of the objective variables.This paper proposes a flow-sensitive program representation approach and defines a notion of Context Free Language（CFL）reachability which helps explore all the flow-sensitive points-to relations for the objective variables.It also develops a Seeker tool,which can compute the points-to sets of the variables of interest. Experimental results show that the demand-driven points-to analysis algorithm improves the efficiency of the Flow Sensitive Context Insensitive（FSCI）points-to analysis.