[1]戚晓芳,周晓宇,徐晓晶,等.一种组合式基于调用栈的程序切片方法[J].东南大学学报(自然科学版),2011,41(6):1171-1176.[doi:10.3969/j.issn.1001-0505.2011.06.009]
 Qi Xiaofang,Zhou Xiaoyu,Xu Xiaojin,et al.A combinational program slicing approach based on call stacks[J].Journal of Southeast University (Natural Science Edition),2011,41(6):1171-1176.[doi:10.3969/j.issn.1001-0505.2011.06.009]
点击复制

一种组合式基于调用栈的程序切片方法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
41
期数:
2011年第6期
页码:
1171-1176
栏目:
计算机科学与工程
出版日期:
2011-11-20

文章信息/Info

Title:
A combinational program slicing approach based on call stacks
作者:
戚晓芳1周晓宇1徐晓晶1张迎周2
(1东南大学计算机科学与工程学院,南京 210096)
(2南京邮电大学计算机学院,南京 210003)
Author(s):
Qi Xiaofang1Zhou Xiaoyu1Xu Xiaojin1Zhang Yingzhou2
(1School of Computer Science and Engineering, Southeast University, Nanjing 210096, China)
(2School of Computer Science and Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210003, China)
关键词:
程序调试 程序切片 调用栈
Keywords:
program debugging program slicing call stack
分类号:
TP311
DOI:
10.3969/j.issn.1001-0505.2011.06.009
摘要:
通过调用栈提取当前调用上文信息,对传统的静态程序切片约简,可获得基于调用栈的程序切片,进行有效的程序调试.针对目前该切片计算需构造系统依赖图(SDG)而造成大程序分析效率较低等问题,提出相关子程序分析算法,通过仅分析程序中部分与切片标准相关的子程序,而不是所有子程序来提高分析效率,同时提出一种组合式基于调用栈的程序切片方法进行切片计算.组合式程序切片方法以子程序为依赖性分析单位,程序依赖图由相互独立的子程序依赖图组合而成,子程序对外接口由参数间依赖关系实现,通过实参和形参之间的映射实现子程序间的分析.对3个不同规模的程序进行实验,相关子程序平均数为总子程序数的0.03%~17.1%,表明该方法可有效减少分析时间,提高调试响应速度.
Abstract:
Slicing based on call stacks reduces the size of static slice by leveraging the information of call stacks and then extracting current calling context. It is an effective technique to debug programs. In the traditional slicing method, system dependence graph is required to be constructed, which leads to high time overhead, especially for large programs. To enhance analysis efficiency, it is proposed that only partial procedures relevant to slicing criteria, instead of all procedures, are analyzed. An algorithm for identifying procedures related to slicing criteria is first presented and then a combinational slicing approach based on call stacks. During the slicing process, procedure is basic unit for dependence analysis and program dependence graph is a combination of dependence graphs for all independent procedures. Interfaces between procedures are realized by dependences among parameters and inter-procedure analysis is obtained by mapping actual to formal parameters or vice versa. This approach was applied to three programs with different size. Average ratio of the number of relevant procedures to that of the total is 0. 03% to 17. 1%. It shows that our approach is beneficial for reducing analysis time and hence improved debugging response effectively.

参考文献/References:

[1] Weiser M. Program slicing[J]. IEEE Transactions on Software and Engineering, 1984, 10(5): 498-509.
[2] Xu B, Qian J. A brief survey of program slicing[J]. ACM SIGSOFT Software Engineering Notes, 2005, 30(2): 1-36.
[3] Binkley D, Gold N, Harman M. An empirical study of static program slice size[J]. ACM Transactions on Software Engineering and Methodology, 2007, 16(2):1-30.
[4] Harman M, Binkley D, Gallagher K, et al. Dependence clusters in source code[J]. ACM Transactions on Programming Languages and Systems, 2009, 32(1):1-33.
[5] 戚晓芳, 徐宝文, 周晓宇. 一种基于程序可达图的并发程依赖性分析方法[J]. 电子学报, 2007, 35(2): 287-291.
  Qi Xiaofang, Xu Baowen, Zhou Xiaoyu. An approach to analyzing dependence of concurrent programs based on program reachability graph[J]. Acta Electronica Sinica, 2007, 35(2): 287-291. (in Chinese)
[6] 徐宝文, 陈振强, 周晓宇. 基于依赖性分析的面向对象Ada95程序切片[J]. 软件学报, 2001, 12(增刊): 208-213.
  Xu Baowen, Chen Zhenqiang, Zhou Xiaoyu. Slicing object-oriented Ada95 programs based on dependence analysis[J]. Journal of Software, 2001, 12(supp), 208-213. (in Chinese)
[7] Horwitz S, Liblit B, Polishchuk M. Better debugging via output tracing and callstack-sensitive slicing[J]. IEEE Transaction on Software Engineering, 2010, 36(1): 7-19.
[8] Krinke J. Effects of context on program slicing[J]. Journal of System and Software, 2006, 79(9): 1249-1260.
[9] Horwitz S, Reps T, Binkley D. Inter-procedural slicing using dependence graphs[J]. ACM Transactions on Programming Languages and Systems, 1990, 12(1): 26-60.
[10] Gramma Tech. Codesurfer2.1[EB/OL]. (2007-05-30)[2011-05-25]. http://www.grammatech.com/products/codesurfer/overview.html.
[11] Gailly J, Adler M. Zlib1.2.3[EB/OL]. (2005-07-18)[2011-05-25]. http://gnuwin32.sourceforge.net/packages/zlib.htm.
[12] Hogan T. BNBT easytracker beta7.7[EB/OL]. (2003-09-05)[2011-05-25]. http://sourceforge.net/projects/bnbteasytracker/.
[13] Dai W. Crypto++5.2.1[EB/OL]. (2004-07-21)[2011-05-25]. http://www.cryptopp.com/.

备注/Memo

备注/Memo:
作者简介: 戚晓芳(1972— ),女,博士,副教授,xfqi@seu.edu.cn.
基金项目: 国家自然科学基金资助项目(60873049, 60703086, 60903026).
引文格式: 戚晓芳,周晓宇,徐晓晶,等.一种组合式基于调用栈的程序切片方法[J].东南大学学报:自然科学版,2011,41(6):1171-1176. [doi:10.3969/j.issn.1001-0505.2011.06.009]
更新日期/Last Update: 2011-11-20