|本期目录/Table of Contents|

[1]吴军华,王佳利.基于依赖图的程序克隆分析及近似解求解方法[J].南京工业大学学报(自然科学版),2013,35(05):52-56.[doi:10.3969/j.issn.1671-7627.2013.05.010]
 WU Junhua,WANG Jiali.Program clone analysis and approximate solution method based on program dependence graph[J].Journal of NANJING TECH UNIVERSITY(NATURAL SCIENCE EDITION),2013,35(05):52-56.[doi:10.3969/j.issn.1671-7627.2013.05.010]
点击复制

基于依赖图的程序克隆分析及近似解求解方法()
分享到:

《南京工业大学学报(自然科学版)》[ISSN:1671-7627/CN:32-1670/N]

卷:
35
期数:
2013年05期
页码:
52-56
栏目:
出版日期:
2013-09-20

文章信息/Info

Title:
Program clone analysis and approximate solution method based on program dependence graph
文章编号:
1671-7627(2013)05-0052-05
作者:
吴军华王佳利
南京工业大学 电子与信息工程学院,江苏 南京 210009
Author(s):
WU Junhua WANG Jiali
College of Information Science and Engineering, Nanjing University of Technology, Nanjing 210009, China
关键词:
程序缺陷 克隆代码 程序依赖图 克隆分析 软件演化
Keywords:
program fault clone code program dependence graph(PDG) clone analysis software evolution
分类号:
TP311
DOI:
10.3969/j.issn.1671-7627.2013.05.010
文献标志码:
A
摘要:
大型软件系统中的代码复制和修改现象可能导致程序缺陷的扩大以及无用代码的存在,克隆代码检测分析则有助于抽取可复用的软件组件和模式,在软件重构和软件演化中起重要的作用。在给出了一种基于子图同构进行克隆代码检测的方法基础上,加入依赖边类型约束求近似解的算法,以改善算法的时间复杂性。
Abstract:
A code duplication in a large software system resulted in error extending and some dead codes. The analysis of clone code was helpful to extract reused software components and patterns. So it played an important role in software restructuring and evolving. An algorithm for the clone code detection was presented based on the subgraph isomorphism. Constraints of dependent edge types were used in the approximate solution method to improve the time complexity of the algorithm.

参考文献/References:

[1] Kumar Roy C,Cordy J R.An empirical study of function clones in open source software[C]//The 15th working conference on Reverse Engineering(WCRE’08).Belgium:[s.n.],2008:81-90.
[2] Kumar Roy C,Cordy J R,Koschke R.Comparison and evaluation of code clone detection techniques and tools:a qualitative approach[J].Science of Computer Programming,2009,74(7):470-495.
[3] Koschke R.Survey of research on software clones[C]//Duplication,Redundancy,and Similarity in Software.Dagstuhl:[s.n.],2006.
[4] Ducasse S,Rieger M,Demeyer S.A language independent approach for detecting duplicated code[C]//International Workshop on Empirical Studies of Software Maintenance-WESS’99.Oxford:[s.n.],1999.
[5] Johnson J.Identifying redundancy in source code using fingerprints[C]//IBM Centre for Advanced Studies Conference,Software Engineering.Toronto:IBM Press,1993:171-183.
[6] Kamiya T,Kusumoto S,Katsuro I.CCFinder:a multilinguistic token-based code clone detection system for large scale source code[J].Transactions on Software Engineering,2002,28(7):654- 670.
[7] Baxter I,Yahin A,Moura L,et al.Clone detection using abstract syntax trees[C]//The 14th International Conference on Software Maintenance(ICSM’98).Bethesda:[s.n.],1998:368-377.
[8] Krink J.Identifying similar code with program dependence graph[C]//The 8th Working Conference on Reverse Engineering(WCRE’01).Stuttgart:[s.n.],2001:301-309.
[9] 李必信.程序切片技术及其应用[M].北京:科学出版社,2006.
[10] 徐宝文,张挺,陈振强.递归子程序的依赖性分析及其应用[J].计算机学报,2001,24(11):1278-1284.
[11] Baker B S.A theory of parameterized pattern matching:algorithms and applications[C]//The 25th ACM Symposium on Theory of Computing.New York:[s.n.],1993:71-80.
[12] McCreight E M.A space-economical suffix tree construction algorithm[J].JACM,1976,23(2):262-272.
[13] Cordella L P,Foggia P,Sansone C,et al.An improved algorithm for matching large graphs[C]//The 3rd IAPR TC-15 Workshop on Graph based Representations in Pattern Recognition.Ischia:[s.n.],2001:149-159.
[14] 邹潇湘,戴琼.图同构中的一类顶点细分方法[J].软件学报,2007,18(2):213-219.
[15] Ullmann J R.An Algorithm for subgraph isomorphism[J].Journal of the Association for Computing Machinery,1976,23:31-42.
[16] Schmidt D C,Druffel L E.A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices[J].Journal of the ACM,1976,23(3):433-445.
[17] Cordella L P,Foggia P,Sansone C,et al.Subgraph transformations for the inexact matching of attributed relational graphs[J].Computing,1998,12(Suppl.):43-52.
[18] Hopcroft J,Wong J.Linear time algorithm for isomorphism of planar graphs[C]//The 6th Annual ACM Symposium,Theory of Computing.Washington:[s.n.],1974:172-184.
[19] 吴军华,汪婷婷.一种获取Web结构切片的方法及其应用[J].南京工业大学学报:自然科学版,2008(4):79-83.

备注/Memo

备注/Memo:
收稿日期:2012-12-17
基金项目:国家自然科学基金(61272080)
作者简介:吴军华(1965—),女,江西进贤人,副教授,主要研究方向为软件工程,E-mail:wujh@njut.edu.cn..
更新日期/Last Update: 2013-09-07