Новости
09.05.2023
с Днём Победы!
07.03.2023
Поздравляем с Международным женским днем!
23.02.2023
Поздравляем с Днем защитника Отечества!
Оплата онлайн
При оплате онлайн будет
удержана комиссия 3,5-5,5%








Способ оплаты:

С банковской карты (3,5%)
Сбербанк онлайн (3,5%)
Со счета в Яндекс.Деньгах (5,5%)
Наличными через терминал (3,5%)

ПОИСК ЗАИМСТВОВАННЫХ ФРАГМЕНТОВ В ИСХОДНОМ ПРОГРАММНОМ КОДЕ

Авторы:
Город:
Рыбинск
ВУЗ:
Дата:
15 апреля 2017г.

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

Свободный доступ к огромному количеству программных продуктов с открытым исходным кодом приводит к тому, что наблюдается большое количество случаев заимствования фрагментов кода в ходе разработки нового ПО. Копирование фрагментов кода приводит к дублированию, что влечет за собой проблемы:

•              увеличение размера программного кода;

•              ухудшение читаемости программного кода;

•              возможность возникновения семантических ошибок;

•              многократное исправление одной и той же ошибки;

•              усложнение сопровождения ПО;

•              увеличение стоимости поддержки ПО.

Для устранения данных проблем необходимо находить клоны в программном коде. В поиске повторяющихся фрагментов исходного программного кода заключается одна из главных задач, которая возникает при разработке огромных проектов с большой программной базой.

Исходные коды программ в силу своей сложности и вариативности невозможно сравнить, как обычный текст. Причем очень часто приходится сталкиваться с тем, что заимствование заключается лишь в каких-либо отдельных фрагментах.

На данный момент существуют различные приложения и Интернет-сервисы, позволяющие выявлять случаи заимствования в исходных программных кодах (Software Similarity Tester, JPlag, Measure Of Software Similarity и другие). Однако следует отметить, что их применение имеет ряд ограничений, как технических, так и лицензионных [1, 2, 3]:

•              коммерческая основа;

•              ограниченность БД, в которой происходит поиск клонов;

•              возможность  сравнивать  работы  только  в  web-контенте  или  только  определенного  языка программирования;

•              низкая скорость обработки данных;

•              маленькая точность обработки данных;

•              возможность сбоев при сравнении, так как проверка требует некоторого времени и происходит через интернет;

•              требуется ручная проверка результатов поиска клонов.

Фрагмент программного кода, который очень похож на другой фрагмент кода, называют клоном в программном обеспечении. Выделяют следующие основные типы клонов исходного программного кода [4, 5]:

•              I тип – фрагменты кода отличаются только пробелами и комментариями;

•              II тип – фрагменты кода отличаются пробелами, комментариями, именами переменных, типами переменных или их значениями;

•              III тип – фрагменты кода отличаются пробелами, комментариями, именами переменных, типами переменных или их значениями, а так же если произошло добавление или удаление некоторых строк.

Для поиска  клонов в  программном коде используется пять подходов: текстовый, лексический, синтаксический, семантический и метрический [5].

Текстовый подход. При таком подходе программный код программы рассматривается как

последовательность строк. В таком случае поиск клонов происходит за счет построчного сравнения или сравнения с использованием языка TXL. Алгоритмы, основанные на текстовом подходе, могут находить клоны только I и II типа [6, 7].

Лексический подход. Данный  подход заключается в преобразовании  программного кода в последовательность токенов (лексем), при помощи лексического анализатора, и поиске совпадающих последовательностей токенов. Алгоритмы, основанные на текстовом подходе, могут находить с высокой точностью клоны I и II типа [6, 7].

Метрический подход. При таком подходе для программного кода вычисляются метрики, и затем получившиеся векторы метрик сравниваются между собой. Обычно метрики вычисляются для абстрактного синтаксического дерева или графа зависимостей программы некоторого фрагмента кода. Алгоритмы, основанные на метрическом подходе, могут находить клоны всех трех типов (причем клоны I и II типа находят лучше, чем III типа). Они имеют высокую производительность и хорошо масштабируемы, но при этом достаточно низкая точность [6, 7].

Синтаксический подход. Данный подход заключается в преобразовании программного кода в абстрактное синтаксическое дерево (АСД), при помощи синтаксического анализатора. Поиск клонов происходит за счет сравнения поддеревьев, суффиксных деревьев (строится для поддерева и состоит из вершин АСД) или векторов (строится для поддерева и состоит из инструкций). Алгоритмы, основанные на синтаксическом подходе, могут находить клоны всех трех типов. Они имеют высокую производительность, но клоны III типа находятся менее точно, по сравнению с семантическим подходом [6, 7].

Семантический подход. При таком подходе программный код представляется в виде графа зависимостей программы (ГЗП). ГЗП содержит информацию о потоке данных и о потоке управления, где вершины – операции, а ребра – тип зависимости (по данным или по управлению). Поиск осуществляется в подграфах в каждой паре ГЗП. Алгоритмы, основанные на семантическом подходе, могут находить клоны всех трех типов. Они имеют высокую точность, но имеют большую вычислительную сложность [6, 7].

Таким образом, для решения проблемы, связанной с поиском повторяющихся фрагментов исходного программного кода, представляется целесообразным использовать сочетание синтаксического и семантического подходов. Для сравнения большого количества данный эффективнее использовать синтаксический подход, а в случаях, когда требуется повышенная точность, семантический подход.

Одним из алгоритмов  синтаксического подхода  является  алгоритм поиска схожих деревьев  на основе линеаризации. Сначала необходимо выполнить анонимизацию всех идентификаторов. Для АСД извлекаются все кодовые фразы путем итераций по всем поддеревьям, всем последовательностям операторов и соответствующему им глобальному контексту. Для каждой кодовой фразы вычисляется индекс и добавляется в соответствующий список инвертированных индексов или создается новый список, если кодовой фразы нет в списке индексов. Список инвертированных индексов реализовывается в виде хэш- таблицы. Путем хэширования списка для каждой кодовой фразы вычисляется хэш-код, при помощи алгоритма линеаризации. Причем кодовые фразы хешируются с использованием той же функции, если узлы могут быть линеаризованы аналогично [8].

Одним из алгоритмов семантического подхода является алгоритм поиска схожих подграфов на основе слайсинга. Для каждой вершины первого графа выбирается максимально схожая с ней вершина из второго графа. После этого все пары вершин считаются схожими подграфами и расширяются путем добавления подходящих инцидентных вершин. Алгоритм возвращает самую большую пару подграфов, полученный при расширении, как максимально схожие [9].

Таким образом, при автоматическом сравнении сочетание алгоритма поиска схожих подграфов на основе слайсинга и алгоритм поиска схожих деревьев на основе линеаризации позволит сократить время и повысить точность нахождения клонов в исходном программном коде.



Список литературы

 

1.                   The     software     and     text     similarity      tester     SIM     [Электронный     ресурс]     –     URL:https://dickgrune.com/Programs/similarity_tester/

2.                   JPlag – Detecting Software Plagiarism [Электронный ресурс] – URL: http://jplag.ipd.kit.edu/

3.                   A System for Detecting Software Plagiarism [Электронный ресурс] – URL: http://theory.stanford.edu/~aiken/moss/

4.                   Bellon S., Koschke R., Antoniol G., Krinke J., Merlo E. Comparison and evaluation of clone detection tools // IEEE Transactions on Software Engineering. – 2007. – № 33. – С. 577–591.

5.                   Roy C. K., Cordy J. R., Koschke R. Comparison and Evaluation of Code Clone Detection Techniques and Tools: A Qualitative Approach // Science of Computer Programming. – 2009. – № 7. – С. 470–495.

6.                   Саргсян С., Курмангалеев Ш., Белеванцев А., Асланян А., Балоян А. Масштабируемый инструмент поиска клонов кода на основе семантического анализа программ. – 2015. – № 1(том 27). – С. 39–49.

7.                   Саргсян С. Поиск семантических ошибок, возникающих при некорректной адаптации скопированных участков кода. // Труды ИСП РАН. – 2015. – № 2(том 27). – С. 93–104.

8.                   Nguyen A., Piech C., Huang J., Guibas L. Codewebs: scalable homework search for massive open online programming courses. // International World Wide WebConferences Steering Committee. – 2014. – С. 491–502.

9.                   Komondoor R., Horwitz S. Using slicing to identify duplication in source code // 8th International Symposium on Static Analysis. – 2001. – С. 40–56.