作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 体系结构与软件技术 • 上一篇    下一篇

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

肖可君a,于海波a,陈雨亭b,钟浩b   

  1. (上海交通大学 a.软件学院; b.电子信息与电气工程学院,上海 200240)
  • 收稿日期:2015-11-27 出版日期:2016-11-15 发布日期:2016-11-15
  • 作者简介:肖可君(1990—),男,硕士研究生,主研方向为程序分析;于海波、陈雨亭,讲师、博士;钟浩,副教授、博士。
  • 基金资助:
    国家自然科学基金(61572312)。

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

XIAO Kejun  a,YU Haibo  a,CHEN Yuting  b,ZHONG Hao  b   

  1. (a.School of Software; b.School of Electronic Information and Electrical Engineering, Shanghai Jiaotong University,Shanghai 200240,China)
  • Received:2015-11-27 Online:2016-11-15 Published:2016-11-15

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

关键词: 指向分析, 需求驱动, 流敏感, 上下文无关语言, 静态分析

Abstract: 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.

Key words: points-to analysis, demand-driven, flow-sensitive, Context Free Language(CFL), static analysis

中图分类号: