Scientific and analytical journal «Vestnik Saint-Petersburg university of State fire service of EMERCOM of Russia» Scientific and analytical journal «Vestnik Saint-Petersburg university of State fire service of EMERCOM of Russia» Научно-аналитический журнал "Вестник Санкт-Петербургского университета ГПС МЧС России" 2218-130X 65963 ИНФОРМАТИКА, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И УПРАВЛЕНИЕ INFORMATICS, COMPUTER ENGINEERING AND CONTROL ИНФОРМАТИКА, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И УПРАВЛЕНИЕ METHOD FOR DETECTING SOURCE CODE DUPLICATES BASED ON THE RANDOM WALK ALGORITHM МЕТОД ОБНАРУЖЕНИЯ ДУБЛИКАТОВ ИСХОДНОГО КОДА НА ОСНОВЕ АЛГОРИТМА СЛУЧАЙНОГО БЛУЖДАНИЯ Яковлев Артем Владимирович Yakovlev Artem V. 89062703467@mail.ru Таров Евгений Викторович Tarov Evgeny V. tarov25@mail.ru https://orcid.org/0000-0002-9412-5693 Израилов Константин Евгеньевич Izrailov Konstantin E. konstantin.izrailov@mail.ru

кандидат технических наук;

candidate of technical sciences;

 https://orcid.org/0000-0001-7056-6972 Чечулин Андрей Алексеевич Chechulin Andrey A. andreych@bk.ru

кандидат технических наук;

candidate of technical sciences;

 Санкт-Петербургский государственный университет телекоммуникаций имени проф. М. А. Бонч-Бруевича The Bonch-Bruevich Saint-Petersburg State University of Telecommunications Санкт-Петербургский Федеральный исследовательский центр Российской академии наук Россия Saint-Petersburg Federal research center of the Russian academy of sciences Russian Federation Российская академия наук Санкт-Петербург Россия Russian academy of sciences Saint-Petersburg Russian Federation 07 07 2023 07 07 2023 2023 2 134 146 21 04 2023 22 05 2023 https://journals.igps.ru/en/nauka/article/65963/view

Статья посвящена задаче обнаружения экземпляров исходного кода, дублирующего заданный. В интересах этого рассматриваются существующие подходы поиска клонов кода, основанные на текстовом, лексическом, синтаксическом, метрическом и семантическом анализе. Основываясь на их критериальном сравнении, предлагается новый метод поиска дубликатов, в основу которого положен алгоритм случайного блуждания. Суть метода заключается в построении графов двух исходных кодов (где узлами являются лексические единицы текста, а ребрами – связи между ними), на которых затем применяется указанный алгоритм; дается описание метода в виде псевдокода. Проводится эксперимент по оценке работоспособности метода с использованием следующих метрик: Жаккара, разниц количества ребер, вершин и средней кластеризации графов, кратчайшего пути между их вершинами, а также сходства между графами. Сценарии экспериментов состоят из вычисления метрик для комбинаций экземпляров двух исходных кодов, их объединения и доли одного из них. Делаются выводы касательно применимости как самого метода, так и каждой из метрик оценки.

The article is devoted to the problem of source code finding copies that duplicates the given one. In the interests of this, the existing approaches for searching for code clones based on textual, lexical, syntactic, metric and semantic analysis are considered. Based on their criterion comparison, a new method for searching for duplicates is proposed, which is based on the random walk algorithm. The essence of the method is to build graphs of two source codes (where the nodes are the tokens of the text, and the edges are the links between them), on which the specified algorithm is then applied; the description of the method is given in the form of pseudocode. An experiment is being carried out to evaluate the performance of the method using the following metrics: Jaccard, differences in the number of edges, vertices and average clustering of graphs, the shortest path between their vertices, as well as similarities between graphs. Experimental scenarios consist of calculating metrics for combinations of two source codes instances, their union and the proportion of one of them. Conclusions are drawn regarding the applicability of both the method itself and each of the evaluation metrics.

 информационная безопасность поиск дубликатов случайное блуждание исходный код information security duplicate search random walk source code

Цифровые технологии и проблемы информационной безопасности: монография / Т.И. Абдуллин [и др.]. СПб.: СПГЭУ, 2021. 163 с. Cifrovye tekhnologii i problemy informacionnoj bezopasnosti: monografiya / T.I. Abdullin [i dr.]. SPb.: SPGEU, 2021. 163 s. Защита информации в компьютерных системах: монография / М.В. Буйневич [и др.]. СПб.: СПГЭУ, 2017. 163 с. Zashchita informacii v komp'yuternyh sistemah: monografiya / M.V. Bujnevich [i dr.]. SPb.: SPGEU, 2017. 163 s. Израилов К.Е. Моделирование программы с уязвимостями с позиции эволюции ее представлений. Ч. 1. Схема жизненного цикла // Труды учебных заведений связи. 2023. Т. 9. № 1. С. 75-93. DOI: 10.31854/1813-324X-2023-9-1-75-93. Izrailov K.E. Modelirovanie programmy s uyazvimostyami s pozicii evolyucii ee predstavlenij. Ch. 1. Skhema zhiznennogo cikla // Trudy uchebnyh zavedenij svyazi. 2023. T. 9. № 1. S. 75-93. DOI: 10.31854/1813-324X-2023-9-1-75-93. Сойников М.А. Взыскание ущерба, причиненного преступлением против интеллектуальной собственности: процессуальные аспекты // Lex Russica (Русский закон). 2019. № 12 (157). С. 80-86. Sojnikov M.A. Vzyskanie ushcherba, prichinennogo prestupleniem protiv intellektual'noj sobstvennosti: processual'nye aspekty // Lex Russica (Russkij zakon). 2019. № 12 (157). S. 80-86. Слета В.Д. Поддержка повторного использования кода на основе онтологического подхода // Современные информационные технологии. 2010. № 11. С. 178-181. Sleta V.D. Podderzhka povtornogo ispol'zovaniya koda na osnove ontologicheskogo podhoda // Sovremennye informacionnye tekhnologii. 2010. № 11. S. 178-181. Романов Н.Е., Израилов К.Е., Покусов В.В. Система поддержки интеллектуального программирования: машинное обучение feat. Быстрая разработка безопасных программ // Информатизация и связь. 2021. № 5. С. 7-17. DOI: 10.34219/2078-8320-2021-12-5-7-16. Romanov N.E., Izrailov K.E., Pokusov V.V. Sistema podderzhki intellektual'nogo programmirovaniya: mashinnoe obuchenie feat. Bystraya razrabotka bezopasnyh programm // Informatizaciya i svyaz'. 2021. № 5. S. 7-17. DOI: 10.34219/2078-8320-2021-12-5-7-16. Шуваев Ф.Л., Татарка М.В. Анализ математических моделей случайных графов, применяемых в имитационном моделировании информационно-коммуникационных сетей // Науч.-аналит. журн. «Вестник С.-Петерб. ун-та ГПС МЧС России». 2020. № 2. С. 67-77. Shuvaev F.L., Tatarka M.V. Analiz matematicheskih modelej sluchajnyh grafov, primenyaemyh v imitacionnom modelirovanii informacionno-kommunikacionnyh setej // Nauch.-analit. zhurn. «Vestnik S.-Peterb. un-ta GPS MCHS Rossii». 2020. № 2. S. 67-77. Suttichaya V., Eakvorachai N., Lurkraisit T. Source Code Plagiarism Detection Based on Abstract Syntax Tree Fingerprintings // The proceedings of 17th International Joint Symposium on Artificial Intelligence and Natural Language Processing (Chiang Mai, Thailand, 5-7 November 2022). 2022. P. 1-6. DOI: 10.1109/iSAI-NLP56921.2022.9960266. Suttichaya V., Eakvorachai N., Lurkraisit T. Source Code Plagiarism Detection Based on Abstract Syntax Tree Fingerprintings // The proceedings of 17th International Joint Symposium on Artificial Intelligence and Natural Language Processing (Chiang Mai, Thailand, 5-7 November 2022). 2022. P. 1-6. DOI: 10.1109/iSAI-NLP56921.2022.9960266. Nishi M.A., Ciborowska A., Damevski K. Characterizing Duplicate Code Snippets between Stack Overflow and Tutorials // The proceedings of 16th International Conference on Mining Software Repositories (Montreal, QC, Canada, 25-31 May 2019). 2019. P. 240-244. DOI: 10.1109/MSR.2019.00048. Nishi M.A., Ciborowska A., Damevski K. Characterizing Duplicate Code Snippets between Stack Overflow and Tutorials // The proceedings of 16th International Conference on Mining Software Repositories (Montreal, QC, Canada, 25-31 May 2019). 2019. P. 240-244. DOI: 10.1109/MSR.2019.00048. Raheja K., Tekchandani R.K. An efficient code clone detection model on Java byte code using hybrid approach // The proceedings of Confluence 2013: The Next Generation Information Technology Summit (Noida, 26-27 September 2013). 2013. P. 16-21. DOI: 10.1049/cp.2013.2287. Raheja K., Tekchandani R.K. An efficient code clone detection model on Java byte code using hybrid approach // The proceedings of Confluence 2013: The Next Generation Information Technology Summit (Noida, 26-27 September 2013). 2013. P. 16-21. DOI: 10.1049/cp.2013.2287. Wang H., Zhong J., Zhang D. A Duplicate Code Checking Algorithm for the Programming Experiment // The proccedings of Second International Conference on Mathematics and Computers in Sciences and in Industry (Sliema, Malta, 17 August 2015). 2015. P. 39-42. DOI: 10.1109/MCSI.2015.12. Wang H., Zhong J., Zhang D. A Duplicate Code Checking Algorithm for the Programming Experiment // The proccedings of Second International Conference on Mathematics and Computers in Sciences and in Industry (Sliema, Malta, 17 August 2015). 2015. P. 39-42. DOI: 10.1109/MCSI.2015.12. Moshkin V., Kalachev V., Zarubin A. Automation of Program Code Analysis Using Machine Learning Methods // The proocedings of International Russian Automation Conference (Sochi, Russian Federation, 4-10 September 2022). 2022. P. 404-408. DOI: 10.1109/RusAutoCon54946.2022.9896360. Moshkin V., Kalachev V., Zarubin A. Automation of Program Code Analysis Using Machine Learning Methods // The proocedings of International Russian Automation Conference (Sochi, Russian Federation, 4-10 September 2022). 2022. P. 404-408. DOI: 10.1109/RusAutoCon54946.2022.9896360. Израилов К.Е., Гололобов Н.В., Краскин Г.А. Метод анализа вредоносного программного обеспечения на базе Fuzzy Hash // Информатизация и связь. 2019. № 2. С. 36-44. Izrailov K.E., Gololobov N.V., Kraskin G.A. Metod analiza vredonosnogo programmnogo obespecheniya na baze Fuzzy Hash // Informatizaciya i svyaz'. 2019. № 2. S. 36-44. Хилько В.О., Шаров И.А. Поиск дубликатов в исходных кодах программ // Региональная информатика и информационная безопасность. Вып. 4. 2017. С. 184-185. Hil'ko V.O., Sharov I.A. Poisk dublikatov v iskhodnyh kodah programm // Regional'naya informatika i informacionnaya bezopasnost'. Vyp. 4. 2017. S. 184-185. Лисс А.Р., Андрианов И.А. Анализ и разработка методов поиска дубликатов в программном коде // Известия СПбГЭТУ ЛЭТИ. 2010. № 7. С. 55-61. Liss A.R., Andrianov I.A. Analiz i razrabotka metodov poiska dublikatov v programmnom kode // Izvestiya SPbGETU LETI. 2010. № 7. S. 55-61. Вахрушев И.Н. Использование суффиксных деревьев для поиска дублирующихся фрагментов кода // Системы управления и информационные технологии. 2012. № 4 (50). С. 55-58. Vahrushev I.N. Ispol'zovanie suffiksnyh derev'ev dlya poiska dubliruyushchihsya fragmentov koda // Sistemy upravleniya i informacionnye tekhnologii. 2012. № 4 (50). S. 55-58. Бородащенко А.Ю. Анализ текстов на семантическое сходство на основе аппарата теории графов // Известия Орловского государственного технического университета. Сер.: Информационные системы и технологии. 2008. № 1-2. С. 46-52. Borodashchenko A.Yu. Analiz tekstov na semanticheskoe skhodstvo na osnove apparata teorii grafov // Izvestiya Orlovskogo gosudarstvennogo tekhnicheskogo universiteta. Ser.: Informacionnye sistemy i tekhnologii. 2008. № 1-2. S. 46-52. De J., Zhang X., Lin F., Cheng L. Transduction on Directed Graphs via Absorbing Random Walks // IEEE Transactions on Pattern Analysis and Machine Intelligence. Vol. 40. № 7. P. 1770-1784. DOI: 10.1109/TPAMI.2017.2730871. De J., Zhang X., Lin F., Cheng L. Transduction on Directed Graphs via Absorbing Random Walks // IEEE Transactions on Pattern Analysis and Machine Intelligence. Vol. 40. № 7. P. 1770-1784. DOI: 10.1109/TPAMI.2017.2730871. Gori M., Maggini M., Sarti L. Exact and approximate graph matching using random walks // IEEE Transactions on Pattern Analysis and Machine Intelligence. Vol. 27. № 7. P. 1100-1111. DOI: 10.1109/TPAMI.2005.138. Gori M., Maggini M., Sarti L. Exact and approximate graph matching using random walks // IEEE Transactions on Pattern Analysis and Machine Intelligence. Vol. 27. № 7. P. 1100-1111. DOI: 10.1109/TPAMI.2005.138. Lambiotte R., Delvenne J.-C., Barahona M. Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks // IEEE Transactions on Network Science and Engineering. Vol. 1. № 2. P. 76-90. DOI: 10.1109/TNSE.2015.2391998. Lambiotte R., Delvenne J.-C., Barahona M. Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks // IEEE Transactions on Network Science and Engineering. Vol. 1. № 2. P. 76-90. DOI: 10.1109/TNSE.2015.2391998. Котов Э.М. Методы анализа гиперссылок при информационном поиске в глобальной сети // Известия ЮФУ. Технические науки. 2012. № 4 (129). С. 233-237. Kotov E.M. Metody analiza giperssylok pri informacionnom poiske v global'noj seti // Izvestiya YUFU. Tekhnicheskie nauki. 2012. № 4 (129). S. 233-237. Гасников А.В., Дмитриев Д.Ю. Об эффективных рандомизированных алгоритмах поиска вектора PageRank // Журнал вычислительной математики и математической физики. 2015. Т. 55. № 3. С. 355. DOI: 10.7868/S0044466915030060. Gasnikov A.V., Dmitriev D.Yu. Ob effektivnyh randomizirovannyh algoritmah poiska vektora PageRank // Zhurnal vychislitel'noj matematiki i matematicheskoj fiziki. 2015. T. 55. № 3. S. 355. DOI: 10.7868/S0044466915030060. Кузьминова М.В. Периодические динамические графы. Задачи о случайных блужданиях и о кратчайших путях // Известия высших учебных заведений. Северо-Кавказский регион. Сер.: Естественные науки. 2008. № 2 (144). С. 16-21. Kuz'minova M.V. Periodicheskie dinamicheskie grafy. Zadachi o sluchajnyh bluzhdaniyah i o kratchajshih putyah // Izvestiya vysshih uchebnyh zavedenij. Severo-Kavkazskij region. Ser.: Estestvennye nauki. 2008. № 2 (144). S. 16-21. Немченко Д.С. Выявление общих черт пользователей для рекомендательной системы на примере коэффициента сходства Жаккара // Вестник магистратуры. 2023. № 3-1 (138). С. 14-15. Nemchenko D.S. Vyyavlenie obshchih chert pol'zovatelej dlya rekomendatel'noj sistemy na primere koefficienta skhodstva Zhakkara // Vestnik magistratury. 2023. № 3-1 (138). S. 14-15. Кайда А.Ю. Анализ сходства текстов на основе коэффициента Жаккара-Танимото // Математические методы и модели техники, технологий и экономики: материалы Всерос. студ. науч.-практ. конф. 2022. С. 115-118. Kajda A.Yu. Analiz skhodstva tekstov na osnove koefficienta Zhakkara-Tanimoto // Matematicheskie metody i modeli tekhniki, tekhnologij i ekonomiki: materialy Vseros. stud. nauch.-prakt. konf. 2022. S. 115-118. Samanthula B.K., Jiang W. Secure Multiset Intersection Cardinality and its Application to Jaccard Coefficient // IEEE Transactions on Dependable and Secure Computing. Vol. 13. № 5. P. 591-604. DOI: 10.1109/TDSC.2015.2415482. Samanthula B.K., Jiang W. Secure Multiset Intersection Cardinality and its Application to Jaccard Coefficient // IEEE Transactions on Dependable and Secure Computing. Vol. 13. № 5. P. 591-604. DOI: 10.1109/TDSC.2015.2415482. Самохин М.В. Вычисление сходства помеченных графов и их проекций // Научно-техническая информация. Сер. 2: Информационные процессы и системы. 2006. № 3. С. 1-12. Samohin M.V. Vychislenie skhodstva pomechennyh grafov i ih proekcij // Nauchno-tekhnicheskaya informaciya. Ser. 2: Informacionnye processy i sistemy. 2006. № 3. S. 1-12. Kotenko I., Izrailov K., Buinevich M. The Method and Software Tool for Identification of the Machine Code Architecture in Cyberphysical Devices // Journal of Sensor and Actuator Networks. 2023. Vol. 12. Iss. 1. P. 11. DOI: 10.3390/jsan12010011. Kotenko I., Izrailov K., Buinevich M. The Method and Software Tool for Identification of the Machine Code Architecture in Cyberphysical Devices // Journal of Sensor and Actuator Networks. 2023. Vol. 12. Iss. 1. P. 11. DOI: 10.3390/jsan12010011. Kotenko I., Izrailov K., Buinevich M. Analytical Modeling for Identification of the Machine Code Architecture of Cyberphysical Devices in Smart Homes // Sensors. 2022. Vol. 22. Iss. 3. P. 1017. DOI: 10.3390/s22031017. Kotenko I., Izrailov K., Buinevich M. Analytical Modeling for Identification of the Machine Code Architecture of Cyberphysical Devices in Smart Homes // Sensors. 2022. Vol. 22. Iss. 3. P. 1017. DOI: 10.3390/s22031017. Kotenko I., Izrailov K., Buinevich M. Static Analysis of Information Systems for IoT Cyber Security: A Survey of Machine Learning Approaches // Sensors. 2022. Vol. 22. Iss. 4. P. 1335. DOI: 10.3390/s22041335. Kotenko I., Izrailov K., Buinevich M. Static Analysis of Information Systems for IoT Cyber Security: A Survey of Machine Learning Approaches // Sensors. 2022. Vol. 22. Iss. 4. P. 1335. DOI: 10.3390/s22041335.