maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2012-6-69-78mais-140Research ArticleОригинальные статьиArticlesСлайсинг над деревьями: метод обнаружения разорванных и переплетенных клонов в исходном коде программного обеспеченияTree Slicing in Clone Detection: Syntactic Analysis Made (Semi)-SemanticАхинМарат ХалимовичAkhinMarat

аспирант

аспирант

akhin@kspt.ftk.spbstu.ruИцыксонВладимир МихайловичItsyksonVladimir

доцент

доцент

vlad@ftk.spbstu.ruСанкт-Петербургский государственный политехнический университетРоссияСанкт-Петербургский государственный политехнический университетRussian Federation2012120320151966978Copyright © Ахин М.Х., Ицыксон В.М., 20152015Ахин М.Х., Ицыксон В.М.Akhin M., Itsykson V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/140

В настоящее время практически любое программное обеспечение (ПО) содержит избыточный дублированный код (клоны), что приводит ко множественным проблемам на этапе поддержки такого ПО. За последние годы для решения проблемы дублирования было предложено множество различных подходов к обнаружению клонов, но большинство из них не рассматривают семантические свойства исходного кода ПО.

В данной работе предлагается усилить классический подход к обнаружению клонов на основе анализа абстрактных синтаксических деревьев (АСД) за счет использования дополнительной информации о слайсах АСД по переменным программы. Это позволяет эффективно обнаруживать разорванные (gapped) и переплетенные (intertwined) клоны – результаты предварительных экспериментов подтверждают применимость предложенного подхода на практике.

Nowadays most of software contains code duplication that leads to serious problems in software maintenance. A lot of different clone detection approaches have been proposed over the years to deal with this problem, but almost all of them do not consider semantic properties of the source code. We propose to reinforce traditional tree-based clone detection algorithms by using additional information about variable slices. This allows to find intertwined/gapped clones on variables; preliminary evaluation confirms applicability of our approach to real-world software.

обнаружение клоновслайсинг над деревьямишаблоны над деревьямиподдержка программного обеспеченияClone DetectionTree SlicingTree PatternsSoftware MaintenanceReferencesDeshpande A., Riehle D. The Total Growth of Open Source // Conference on Open Source Systems. Springer Verlag, 2008.Deshpande A., Riehle D. The Total Growth of Open Source // Conference on Open Source Systems. Springer Verlag, 2008.Roy C. K., Cordy J. R. A Survey on Software Clone Detection Research. TR 2007-541, School of Computing, Queen’s University, 2007.Roy C. K., Cordy J. R. A Survey on Software Clone Detection Research. TR 2007-541, School of Computing, Queen’s University, 2007.Ахин М.Х., Ицыксон В.М. Обнаружение клонов исходного кода: теория и практика // Системное программирование. 2010. 5. С. 145–163.Ахин М.Х., Ицыксон В.М. Обнаружение клонов исходного кода: теория и практика // Системное программирование. 2010. 5. С. 145–163.Li Z., Lu S., Myagmar S., Zhou Y. CP-Miner: a Tool for Finding Copy-Paste and Related Bugs in Operating System Code // Conference on Symposium on Opearting Systems Design & Implementation, USENIX Association, Berkeley, 2004. P. 20–20.Li Z., Lu S., Myagmar S., Zhou Y. CP-Miner: a Tool for Finding Copy-Paste and Related Bugs in Operating System Code // Conference on Symposium on Opearting Systems Design & Implementation, USENIX Association, Berkeley, 2004. P. 20–20.Kontogiannis K. Evaluation Experiments on the Detection of Programming Patterns Using Software Metrics // Working Conference on Reverse Engineering. IEEE Computer Society. Washington, DC, 1997. P. 44–44.Kontogiannis K. Evaluation Experiments on the Detection of Programming Patterns Using Software Metrics // Working Conference on Reverse Engineering. IEEE Computer Society. Washington, DC, 1997. P. 44–44.Koschke R., Falke R., Frenzel P. Clone Detection Using Abstract Syntax Suffix Trees // Working Conference on Reverse Engineering. IEEE Computer Society. Washington, DC, 2006. P. 253–262.Koschke R., Falke R., Frenzel P. Clone Detection Using Abstract Syntax Suffix Trees // Working Conference on Reverse Engineering. IEEE Computer Society. Washington, DC, 2006. P. 253–262.Hummel B., Juergens E., Heinemann L., Conradt M. Index-based Code Clone Detection: Incremental, Distributed, Scalable // International Conference on Software Maintenance. IEEE Computer Society. Washington, DC, 2010. P. 1–9.Hummel B., Juergens E., Heinemann L., Conradt M. Index-based Code Clone Detection: Incremental, Distributed, Scalable // International Conference on Software Maintenance. IEEE Computer Society. Washington, DC, 2010. P. 1–9.Gabel M., Jiang L., Su S. Scalable Detection of Semantic Clones // International Conference on Software Engineering. IEEE Computer Society, Washington, DC, 2008. P. 321–330.Gabel M., Jiang L., Su S. Scalable Detection of Semantic Clones // International Conference on Software Engineering. IEEE Computer Society, Washington, DC, 2008. P. 321–330.Krinke J. Identifying Similar Code with Program Dependence Graphs // Working Conference on Reverse Engineering. IEEE Computer Society. Washington, DC, 2001.Krinke J. Identifying Similar Code with Program Dependence Graphs // Working Conference on Reverse Engineering. IEEE Computer Society. Washington, DC, 2001.Jiang L., Misherghi G., Su S., Glondu S. DECKARD: Scalable and Accurate Treebased Detection of Code Clones // International Conference on Software Engineering. IEEE Computer Society. Washington, DC, 2007. P. 96–105.Jiang L., Misherghi G., Su S., Glondu S. DECKARD: Scalable and Accurate Treebased Detection of Code Clones // International Conference on Software Engineering. IEEE Computer Society. Washington, DC, 2007. P. 96–105.Andoni A., Indyk P. Near-optimal Hashing Algorithms for Approximate Nearest Neighbour in High Dimensions. Commun. // ACM. 2008. 51, 1. P. 117–122.Andoni A., Indyk P. Near-optimal Hashing Algorithms for Approximate Nearest Neighbour in High Dimensions. Commun. // ACM. 2008. 51, 1. P. 117–122.Evans W., Fraser C., Ma F. Clone Detection via Structural Abstraction // Software Quality Journal. 2009. 17, 4. P. 309–330.Evans W., Fraser C., Ma F. Clone Detection via Structural Abstraction // Software Quality Journal. 2009. 17, 4. P. 309–330.Bulychev P., Minea M. Duplicate Code Detection Using Anti-unification // Spring Young Researchers Colloquium on Software Engineering, 2008. P. 51–54.Bulychev P., Minea M. Duplicate Code Detection Using Anti-unification // Spring Young Researchers Colloquium on Software Engineering, 2008. P. 51–54.Kamiya T., Kusumoto S., Inoue K. CCFinder: Multilinguistic Token-based Code Clone Detection System for Large Scale Source Code // IEEE Trans. Softw. Eng. 2002. 28, 7. P. 654–670.Kamiya T., Kusumoto S., Inoue K. CCFinder: Multilinguistic Token-based Code Clone Detection System for Large Scale Source Code // IEEE Trans. Softw. Eng. 2002. 28, 7. P. 654–670.

The authors declare that there are no conflicts of interest present.