计算机工程

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

基于依赖图等价代换的SSDG构建算法

徐东,狄效国,孟宇龙,冯晓宁   

  1. (哈尔滨工程大学计算机科学与技术学院,哈尔滨 150001)
  • 收稿日期:2014-11-21 出版日期:2015-12-15 发布日期:2015-12-15
  • 作者简介:徐东(1969-),男,教授、博士,主研方向:计算机体系结构;狄效国,硕士研究生;孟宇龙,讲师、博士;冯晓宁,副教授。
  • 基金项目:
    国家自然科学基金资助项目(61100006,61272184);黑龙江省自然科学基金资助项目(F201129)。

SSDG Construction Algorithm Based on Dependency Graph Equivalent Substitution

XU Dong,DI Xiaoguo,MENG Yulong,FENG Xiaoning   

  1. (College of Computer Science and Technology,Harbin Engineering University,Harbin 150001,China)
  • Received:2014-11-21 Online:2015-12-15 Published:2015-12-15

摘要: 已有软件语义分析方法普遍存在时间复杂度高、准确率低的问题。为此,基于抽象语法树,提出一种根据控制依赖图构建程序控制流图的算法,并在对依赖图进行等价代换的基础上简化该算法。通过对目标程序进行等价代换,并使用程序依赖图替换程序系统依赖图,改进传统 系统依赖图的构建流程。实验结果表明,该算法可有效降低构建系统依赖图的复杂度,并能提高程序切片的速率。

关键词: 语义分析, 控制流图, 系统依赖图, 程序切片, 程序依赖, 数据依赖

Abstract: At present,the mainly method of software semantics analysis generally has the problem of high time complexity and inaccurate results.For the problems,a program Control Flow Graph(CFG) algorithm which is based on Control Dependency Graph (CDG) and abstract syntax tree is proposed in this paper.This algorithm uses object program equivalent substitution and procedure dependence graph to replace procedure System Dependency Graph(SDG) which breaks the building process on traditional SDG.Experimental results show that the algorithm reduces the complexity of constructional SDG effectively and increases the rate of program slicing.

Key words: semantics analysis, Control Flow Graph(CFG), System Dependency Graph(SDG), program slice, program dependence, data dependence

中图分类号: