МЕТОД ПОИСКА КЛОНОВ В ПРОГРАММНОМ КОДЕ

Осадчая А.О., Исаев И.В. Метод поиска клонов в программном коде // Научно-технический вестник информационных технологий, механики и оптики. 2020. Т. 20. № 5. С. 714–721. doi: 10.17586/2226-1494-2020-20-5-714-721

Предмет исследования. Исследованы существующие подходы и методы поиска клонов в программном коде. В результате исследования разработан метод, реализующий семантический подход поиска дублированных фрагментов, направленный на поиск клонов всех типов. Метод. Разработанный метод основан на анализе построенного по файлам исходного кода графа зависимостей программы. Для обнаружения дублированных фрагментов для каждого файла исходного кода генерируются графы зависимостей программы, узлы которых хешируются на основе свойств их содержимого. Пара узлов выбирается из каждого класса эквивалентности. Два изоморфных подграфа, которые включают в себя пару узлов, идентифицируются. Если пара клонов включена в другую пару, она удаляется из набора обнаруженных пар дублированных фрагментов. Набор клонов генерируется из пар дублированных фрагментов, совместно использующих те же изоморфные подграфы. Таким образом, происходит расширение пар клонов. Основные результаты. Для оценки эффективности работы разработанного метода поиска клонов проведено сравнение файлов для определения типов клонов, которые обнаруживает система, использующая данный метод, и тестирование работы на компонентах реальной системы. Выполнено сравнение результатов работы разработанной системы с реально существующими. Практическая значимость. Предложенный метод позволяет автоматизировать анализ исходных файлов. Поиск клонов в программном коде является приоритетным направлением в анализе кода. Обнаружение дублированных фрагментов позволяет бороться с недобросовестным копированием программного кода.

1. Deshpande A., Riehle D. The total growth of open source // IFIP International Federation for Information Processing. 2008. V. 275. P. 197–209. doi: 10.1007/978-0-387-09684-1_16

2. Kapser C., Godfrey M.W. Toward a taxonomy of clones in source code: A case study // Proc. of the Workshop Evolution of Large-scale Industrial Software Applications (ELISA). 2003. P. 67–78.

3. Саргсян С.С. Методы поиска клонов кода и семантических ошибок на основе семантического анализа программы: диссертация на соискание ученой степени кандидата физико-математических наук. Москва: Институт системного программирования Российской академии наук, 2016. С. 10–22.

4. Карпов Ю.Г. Model Checking. Верификация параллельных и распределенных программных систем. СПб.: БХВ-Петербург, 2010. 552 c.

5. Bacon D.F., Graham S.L., Sharp O.J. Compiler transformations for high-performance computing // ACM Computing Surveys. 1994. V. 26. N 4. P. 345–420. doi: 10.1145/197405.197406

6. Glass R.L. Frequently forgotten fundamental facts about software engineering // IEEE Software. 2001. V. 18. N 3. P. 110–112. doi: 10.1109/MS.2001.922739

7. Ахин М.Х., Ицыксон В.М. Обнаружение клонов исходного кода: теория и практика // Системное программирование. 2010. Т. 5. № 1. С. 145–163.

8. Hunt A., Thomas D. The Pragmatic Programmer: From Journeyman to Master. Addison-Wesley Professional, 1999. 352 p.

9. Fowler M., Beck K., Brant J., Opdyke W., Roberts D. Refactoring: Improving the Design of Existing Code. Addison-Wesley Professional, 1999. 464 p.

10. Miller G.A. The magical number seven, plus or minus two: some limits on our capacity for processing information // Psycological Review. 1956. V. 63. N 2. P. 81–97. doi: 10.1037/h0043158

11. Ducasse S., Rieger M., Demeyer S. A language independent approach for detecting duplicated code // Proc. 15th International Conference on Software Maintenance (ICSM). 1999. P. 109–118. doi: 10.1109/ICSM.1999.792593

12. Cordy J.R. The TXL source transformation language // Science of Computer Programming. 2006. V. 61. N 3. P. 190–210. doi: 10.1016/j.scico.2006.04.002

13. Wettel R., Marinescu R. Archeology of code duplication: Recovering duplication chains from small duplication fragments // Proc. 7th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC 2005). 2005. P. 63¬70. doi: 10.1109/SYNASC.2005.20

14. Livieri S., Higo Y., Matsushita M., Inoue K. Very-large scale code clone analysis and visualization of open source programs using distributed CCFinder: D-CCFinder // Proc. 29th International Conference on Software Engineering (ICSE). 2007. P. 106–115. doi: 10.1109/ICSE.2007.97

15. Jiang L., Misherghi G., Su Z., Glondu S. DECKARD: Scalable and accurate tree-based detection of code clones // Proc. 29th International Conference on Software Engineering (ICSE). 2007. P. 96–105. doi: 10.1109/ICSE.2007.30

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License