计算机科学 ›› 2017, Vol. 44 ›› Issue (4): 144-147.doi: 10.11896/j.issn.1002-137X.2017.04.031

• NASAC 2015 • 上一篇    下一篇

基于形式概念分析的依赖簇检测方法研究

尚颖,程克,李征   

  1. 北京化工大学信息科学与技术学院 北京100029,北京化工大学信息科学与技术学院 北京100029,北京化工大学信息科学与技术学院 北京100029
  • 出版日期:2018-11-13 发布日期:2018-11-13
  • 基金资助:
    本文受国家自然科学基金(61170082,61472025,5),教育部新世纪优秀人才计划(NCET-12-0757)资助

Research on FCA Based Dependence Cluster Detection

SHANG Ying, CHENG Ke and LI Zheng   

  • Online:2018-11-13 Published:2018-11-13

摘要: 依赖簇是相互依赖的程序组件的最大集合,大尺寸依赖簇已被证实在程序中普遍存在。依赖簇中任意一点产生变动都会引起其他组件的连锁反应,进而对整个系统造成潜在的影响,这将会阻碍软件理解、测试、维护等方面的工作。检测出依赖簇是消除不良影响的前提,目前通过单调切片尺寸图近似检测依赖簇的方法的准确度较低,会出现漏报和误报。提出了一种基于形式概念分析的依赖簇检测方法,通过概念包含度选取的大型概念来检测大尺寸依赖簇,并进一步提出轻量化策略以有针对性地选取大型概念,降低计算开销。在12个不同规模和领域的开源程序上,将所提方法与单调切片尺寸图法进行对比实验,结果表明所提方法及其轻量化策略能够有效地检测大尺寸依赖簇,可以提高依赖簇检测的准确度和效率。

关键词: 形式概念分析,概念格,依赖簇

Abstract: Dependence cluster is a maximal set of program components that all depend upon each other.The current view is that large dependence cluster is extremely universal,which widely exists in all kinds of program source code.The existence of large dependence cluster may lead to the significant ripple effect,i.e.,a change to a certain point of the cluster will cause potential adverse effects on the rest of the cluster,which might affect the whole system.It has a negative impact on many different software engineering activities,including comprehension,testing and maintenance.Dependence cluster detection is a prerequisite for solving adverse effects caused by large dependence cluster.Previous researchers have proposed monotonic slice-size graph (MSG) based method to detect the same slice size of dependence cluster.However,the proposed method is of conservative approximation,which will cause false positives and false negatives.This paper proposed a technique to detect dependence clusters using formal concept analysis (FCA),in which concept inclusiveness is defined to select large concepts.Furthermore,a light-weight computing strategy for FCA was proposed to compute large concept to decrease the computation cost significantly.Based on 12 open source subjects,the empirical comparison showes that the proposed technique can increase the detection accuracy of large dependence clusters with higher efficiency.

Key words: Formal concept analysis,Concept lattice,Dependence cluster

[1] BINKLEY D,HARMAN M.Locating dependence clusters and dependence pollution[C]∥Proceedings of the 21st IEEE International Conference on Software Maintenance,2005(ICSM’05).IEEE,2005:177-186.
[2] ACHARYA M,ROBINSON B.Practical change impact analysis based on static program slicing for industrial software systems[C]∥Proceedings of the 33rd International Conference on Software Engineering.ACM,2011:746-755.
[3] BESZDES A,GERGELY T,JSZ J,et al.Computation of ta-tic execute after relation with applications to software maintenance[C]∥IEEE International Conference on Software Maintenance,2007(ICSM 2007).IEEE,2007:295-304.
[4] SZEGEDI A,GERGELY T,B ESZEDES A,et al.Verifying the concept of union slices on Java programs[C]∥11th European Conference on Software Maintenance and Reengineering,2007(CSMR’07).IEEE,2007:233-242.
[5] HAJNAL A,FORGCS I.A demand-driven approach to slicing legacy COBOL systems[J].Journal of Software:Evolution and Process,2012,24(1):67-82.
[6] BINKLEY D,GOLD N,HARMAN M,et al.Dependence antipatterns[C]∥23rd IEEE/ACM International Conference on Automated Software Engineering.IEEE,2008:25-34.
[7] ACHARYA M,ROBINSON B.Practical change impact analysis based on static program slicing for industrial software systems[C]∥Proceedings of the 33rd International Conference on Software Engineering.ACM,2011:746-755.
[8] BINKLEY D,HARMAN M.Identifying’ Linchpin Vertices’ That Cause Large Dependence Clusters[C]∥Ninth IEEE International Working Conference on Source Code Analysis and Manipulation,2009(SCAM’09).IEEE,2009:89-98.
[9] BINKLEY D,HARMAN M,HASSOUN Y,et al.Assessing the impact of global variables on program dependence and depen-dence clusters[J].Journal of Systems and Software,2010,83(1):96-107.
[10] HARMAN M,BINKLEY D,GALLAGHER K,et al.Depen-dence clusters in source code[J].ACM Transactions on Programming Languages and Systems (TOPLAS),2009,32(1):1-33.
[11] BLACK S,COUNSELL S,HALL T,et al.Fault analysis in OSS based on program slicing metrics[C]∥35th Euromicro Conference on Software Engineering and Advanced Applications,2009(SEAA’09) .IEEE,2009:3-10.
[12] BLACK S,COUNSELL S,HALL T,et al.Using program slicing to identify faults in software[M]∥ Dagstuhl,Seminar N°.2005.
[13] ISIAM S S,KRINKE J,BINKLEY D.Dependence cluster visua-lization[C]∥Proceedings of the 5th International Symposium on Software Visualization.ACM,2010:93-102.
[14] WILLE R.Restructuring Lattice Theory:An Approach Based on Hierarchies of Concepts[M]∥Ordered Sets.Springer Netherlands,1982:445-470.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!