Software Similarity Measurement based on Dependency Graph using Harmony Search

Ho-Yeong Yun (윤호영); Yong-Joon Joe (조용준); Byung-Ok Jung (정병옥); Dong-Myung Shin (신동명); 방효근

Software Similarity Measurement based on Dependency Graph using Harmony Search

Journal of The Korea Society of Computer and Information
Abbr : JKSCI
2016, 21(12), pp.1-10
Publisher : The Korean Society Of Computer And Information
Research Area : Engineering > Computer Science

Ho-Yeong Yun ¹, Yong-Joon Joe ¹, Byung-Ok Jung ¹, Dong-Myung Shin ¹, 방효근 ²

¹엘에스웨어
²성균관대학교

Accredited

ABSTRACT

In this paper, we attempt to prevent certain cases by tracing a history and making genogram about open source software and its modification using similarity of source code. There are many areas which use open source software actively and widely, and open source software contributes their development. However, there are many unconscious cases like ignoring license or intellectual properties infringe which can lead litigation. To prevent such situation, we analyze source code similarity using program dependence graph which resembles subgraph isomorphism problem, a typical NP-complete problem. To solve subgraph isomorphism problem, we utilized harmony search of metaheuristic algorithm and compared its result with a genetic algorithm. For the future works, we represent open source software as program dependence graph and analyze their similarity.

KEYWORDS

Open Source Software, License, Subgraph Isomorphism Problem, Harmony Search

Citation status

* References for papers published after 2023 are currently being built.

[thesis] S. H. Kim / 2011 / Plagiarism Detection using Dependence Graph Analysis Specialized for Javascript / Master / Korea Advanced Institute of Science Technology

[journal] 지정훈 / 2008 / A Plagiarism Detection Technique for Java Program Using Bytecode Analysis / 정보과학회논문지 : 소프트웨어 및 응용 / 한국정보과학회 35(7) : 442~451

[journal] 김영철 / 2005 / A Program Similarity Evaluation Algorithm / 인터넷정보학회논문지 / 한국인터넷정보학회 6(1) : 53~66

[confproc] Koschke, R. / 2006 / Clone Detection Using Abstract Syntax Suffix Trees / Proceedings of the 13th Working Conference on Reverse Engineering / IEEE : 253~262

[confproc] Liu, C. / 2006 / GPLAG: Detection of Software Plagiarism by Program Dependence Graph Analysis / Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining : 872~881

[confproc] Y.E.Kim / 2016 / A Parallel Performance Comparison of Haskell Using a Plagiarism Detection Method / Korea Computer Congress : 1724~1726

[journal] Lutz Prechelt / 2002 / Finding Plagiarism among a Set of Programs with JPlag / Journal of Universal Computer Science 8(11) : 1016~1038

[journal] Gitchell, David / 1999 / Sim : a Utility for Detecting Similarity in Computer Programs / ACM SIGCSE Bulletin / ACM 31(1)

[journal] Wise, Michael J. / 1996 / YAP3 : Improved Detection of Similarities in Computer Program and Other Texts / ACM SIGCSE Bulletin 28(1) : 130~134

[book] Suresh G. Singh / 2010 / Graph Theory / PHI Learning

[confproc] J.E.Choi / 2012 / An efficient genetic algorithm for subgraph isomorphism / Proceedings of the 14th annual conference on Genetic and evolutionary computation : 361~368

[confproc] Farahani, M. M. / 2015 / A Genetic and Iterative Local Search Algorithm for Solving Subgraph Isomorphism Problem / Industrial Engineering and Operations Management (IEOM), International Conference on. IEEE : 1~6

[confproc] Li, Z. / 2016 / Solving the Subgraph Isomorphism Problem Using Simulated Annealing and Evolutionary Algorithms / Proceedings on the International Conference on Artificial Intelligence (ICAI). The Steering Committee of The World Congress in Computer Science, Computer Engineering and Applied Computing (WorldComp) : 293~299

[confproc] J.E.Choi / 2012 / An efficient genetic algorithm for subgraph isomorphism / Proceedings of the 14th annual conference on Genetic and evolutionary computation

[journal] 이혜련 / 2013 / Constructing Software Structure Graph through Progressive Execution / 한국컴퓨터정보학회논문지 / 한국컴퓨터정보학회 18(7) : 111~123

[journal] 김재협 / 2016 / Object Classification Method Using Dynamic Random Forests and Genetic Optimization / 한국컴퓨터정보학회논문지 / 한국컴퓨터정보학회 21(5) : 79~89

This paper was written with support from the National Research Foundation of Korea.

KJCKorea
Journal Central

Journal of The Korea Society of Computer and Information 2023 KCI Impact Factor : 0.65