Оценка идентичности программного кода

от
Прочее   плагиат исходного кода, обнаружение плагиата

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


ВведениеПодход «Copy-and-Paste Programming» широко распространён при разработке программного обеспечения и применяется по целому ряду причин, основными из которых являются:
- обеспечение повторного использования кода, для сокращения времени разработки и/или тестирования программного обеспечения;
- повышение производительности ПО (подход актуален в случаях, когда используемый компилятор не реализует соответствующие оптимизации);
- недостатка времени на переработку исходного кода или недостаточным количеством знаний о разрабатываемой системе у программиста;
- намеренный плагиат и присвоение интеллектуальной собственности.
Подобное дублирование кода, вносимое безосновательно, может привести к различным негативным последствиям, самым очевидным из которых является увеличение объёма и уменьшение связности исходного кода, усложняющие его поддержку.
Не менее актуальной проблемой является применение «Copy-and-Paste Programming» при обучении программированию: неправильное применение этого подхода может привести к недостаточному пониманию предмета изучения, препятствовать развитию навыков разработки новых самостоятельных решений и имеет риск войти в привычку из-за простоты в применении; однако анализ студенческих работ по курсу разработки компиляторов, в течение трёх лет проводимый исследователями из Китая показал, что плагиату в той или иной мере подвержено до 82% проверяемого программного кода [21]. Проблема плагиата решений актуальна и при проведении соревнований по программированию – использование готовых фрагментов исходного кода на многих соревнованиях считается неспортивным и явно запрещается их правилами.
По этим причинам становится актуальной проблема определения идентичных или мало отличающихся участков программного кода в автоматическом режиме, что может производиться как часть процесса автоматической проверки решений системой тестирования (пример используемых сейчас систем тестирования можно найти, например, в [7, 8]). При этом как сам программный код, тестируемый такими системами, так и потребности организационного процесса контрольных или соревновательных мероприятий вносят свои изменения в поставку задачи поиска клонов и, следовательно, возможные подходы к её решению. Основными особенностями программ, проверяемых при проведении подобных мероприятий, является их простота (отсутствие внешних модулей, логики их синхронизации и взаимодействия) и малый объём; при этом на соревнованиях зачастую используется несколько языков (обычно Java и C++), мало различающихся с точки зрения написания решений для простых и средних задач, а следовательно, возникает потребность проверки идентичности решений, написанных на разных языках программирования.


1. Определение степени идентичности программного кода в литературеРазные авторы по-разному подходят к проблемам определения степени идентичности программного кода и используют несколько различную классификацию клонов исходного кода.

1.1. Классификация Bellon, 2007Классификация клонов исходного кода, приведённая в [2], описывает подход к выделению клонов без учёта форматирования программного кода и разделяет дубликаты на следующие типы:
- тип I, идентичные фрагменты программного кода:
  1. int gcd(int a, int b) { // non neg
  2.   if(b==0)
  3.       return a;
  4.   return gcd(b, a%b);
  5. }
  1. int gcd(int a, int b)
  2. {
  3. if (b == 0) { return a; }
  4. return gcd(b, a % b); }
- тип II, фрагменты программного кода типа I, также содержащие изменения имён, типов и значений переменных и констант:
  1. int gcd(int l, int r) { // non neg
  2.   if(r==0)
  3.       return l;
  4.   return gcd(r, l%r);
  5. }
  1. int gcd(long  a, long b)
  2. {
  3. if (b == 0L) { return a; }
  4. return gcd(b, a % b); }
- тип III, фрагменты программного кода типа II, имеющие небольшие различия, например, добавление или удаление отдельных операторов:
  1. int gcd(int l, int r) { // non neg
  2.   if(l==0) return r; // <- added
  3.   if(r==0) return l;
  4.   return gcd(r, l%r);
  5. }
  1. int gcd(long  a, long b)
  2. {
  3. if (b == 0L) { return a; }
  4. return gcd(b, a % b); }

1.2. Классификация Roy, 2009Одна из наиболее полных на данный момент классификаций приводится в [3, 4] и используется во многих других работах. Данная классификация основывается на типах 1-3 классификации Ballon, 2007, вводя для них общий надтип «синтаксической близости», а также четвёртый, семантический, тип клонов:
- синтаксически близкие фрагменты, типы I – III по классификации Ballon, 2007;
- семантически близкие фрагменты, тип IV: семантически эквивалентный код, представленный различными синтаксическими конструкциями:
  1. int gcd(int l, int r) { // non neg
  2.   while (b != 0) {
  3.     swap(a, b);
  4.     b %= a;
  5.   }
  6.   return a;
  7. }
  1. int gcd(long  a, long b)
  2. {
  3. if (b == 0L) { return a; }
  4. return gcd(b, a % b); }

1.3. Классификация Зельцер, 2013Классификация, вводимая в [5], также не учитывает форматирование исходного кода, и выделяет такие типы клонов, как:
     • точные клоны, эквивалент типа I описанных выше классификаций;
     • клоны 2-го типа, в которых переменные (и, возможно, константы) в теле дубликата могут быть заменены на вычисляемые выражения;
     • клоны 3-го типа, в которых отдельные выражения в теле дубликата могут быть заменены на другие выражения.

1.4. Сопоставление классификаций
Bellon, 2007Roy, 2009Зельцер, 2013
Тип IТип IТочные клоны
Тип IIТип IIКлоны II типа
 
Тип IIIТип III
Клоны III типа
Тип IV
Как отмечается в [3], тип IV (семантические клоны) классификации Roy кардинально отличается от остальных трёх типов (и соответствующих им), как в плане используемых подходов, так и решаемых задач, и поэтому не принимается во внимание в большинстве работ по определению дублирования кода. Также в [3] можно найти сопоставление предлагаемой классификации Roy, 2009 с некоторыми другими.

1.5. Клоны в коде решений задач по программированиюИспользуя классификацию Roy, 2009, определим, какие типы клонов необходимо определять при проверке решений задач по программированию на предмет возможных заимствований:
- обнаружение клонов типов I и II в программном коде решения задач свидетельствуют о вероятном заимствовании;
- обнаружение клонов типа III в решениях вполне возможно и при отсутствии реальных зависимостей в случаях решения участниками достаточно типовых алгоритмических задач;
- обнаружение клонов типа IV лишь показывает, что выбранные программы решают одну и ту же задачу, что и так известно тестирующей системе и организатору; такие клоны нас не интересуют.


2. Подходы и инструменты поиска идентичного кода
2.1. Строковые алгоритмыПервая рассматриваемая группа алгоритмов поиска клонов в программном коде – строковые алгоритмы. Их принцип работы прост: из анализируемого кода исключаются лишние пробельные символы и комментарии, (например, регулярным выражением), после чего с помощью алгоритмов хеширования или суффиксного дерева ищутся повторяющиеся подстроки достаточной длины. Пример такого алгоритма описывается в [9]. Подобные алгоритмы способны найти только клоны типа I, и поэтому практически не используются на практике. В качестве плюса этого подхода можно выделить его независимость от языка анализируемой программы.

2.2. Алгоритмы с применением лексического анализаАлгоритмы поиска клонов на основе лексического анализа работают схоже со строковыми, но в них программный код перед поиском клонов преобразуется в последовательность токенов с учётом рассматриваемого языка программирования; при этом токены, отвечающие за различные идентификаторы и константы, могут как различаться (для поиска клонов типа I), так и совпадать (для поиска клонов типа II). Известными примерами анализаторов дублирования кода, работающих по таким принципам, являются Dup [10] и CCFinder [11]; также существует утилита JPlag, задачей которой является поиск заимствований между программами на языке Java [12].

2.3. Алгоритмы с применением синтаксических деревьевСуществует также подход к поиску клонов программного кода при помощи построения абстрактных синтаксических деревьев (AST, Abstract Syntax Tree) и поиска в них схожих поддеревьев. Этот подход и использующий его анализатор дублирования кода описывается в [1]. Описанный инструмент полезен при поиске дублирования кода, но может оказаться недостаточно эффективным при поиске намеренных заимствований в случае их видоизменений, например, при перестановке строк или операндов местами. Преимуществом подхода можно назвать его независимость от языка программирования на этапе работы с AST, что может позволить анализировать взаимную идентичность программ на разных языках.

2.4. Алгоритмы на основе графов зависимостейПодходы на основе статического анализа (графов потока управления и потока данных) и профилирования предоставляют сложный в реализации, но потенциально мощный инструмент для анализа дублирования кода. Применение этих инструментов для поиска клонов описывается в [13, 14, 20]. Инструменты, использующие профилирование, могут быть достаточно сложны в использовании в промышленных системах по причинам сложности самого программного обеспечения и необходимости ввода некоторых данных для его работы при профилировании; использование же таких инструментов при автоматической проверке решений задач по программированию в значительной мере упрощается по причине использования готовых входных данных для проверки корректности решений – таким образом, при интеграции в систему проверки решений анализатора уникальности кода, организаторам соревновательных и контрольных мероприятий не потребуется добавлять какие-либо дополнительные входные данные для проверки решений на уникальность. Необходимо отметить, что использование графов зависимостей для анализа заимствований напрямую может дать большое количество ложных срабатываний на простых и средних по сложности реализации алгоритмах, особенно классических и известных. Аналогично подходу с AST, на этапе анализа графов не зависит от языка программирования.

2.5. Алгоритмы на основе метрик  Также некоторые исследователи применяли задачу поиска дублирования программного кода путём подсчёта различных метрик исходного кода: количества строк, количества вызовов функций, количества уровней вложенности блоков, количества используемых аргументов функции и/или локальных переменных, и т.д. Пример такого анализа можно найти в [15, 16]; при этом описанный подход основывается на обработке отдельных функций, в то время, как в программном коде решений задач заимствованный фрагмент может располагаться в любом месте, быть поделен на части, и т.д., что сильно уменьшает количество верных распознаваний плагиата программного кода [21].

2.6. Комбинированные подходыРассмотренные выше подходы часто комбинируются, например, как описывается в [17-19]; так, многие алгоритмы совмещают в себе этапы лексического анализа или построения графовой модели и подсчёта метрик. Одним из относительно новых подходов к финальной обработке полученных описанными выше алгоритмами данных является применение нейронных сетей: в [18] блоки исходного кода обрабатывались с помощью нейронной сети с целью поиска повторяющихся шаблонов; в [22] было применено обучение нейронной сети распознаванию автора кода по его «стилю программирования» и дальнейшая проверка авторства программного кода этой нейронной сетью; но такой подход может быть слабо применим к классическим олимпиадам по программированию и контролю задач по коротким учебным курсам, при контроле которых у организатора скорее всего не будет достаточного количества данных для обучения нейросети.


Литература1. Baxter I. D. et al. Clone detection using abstract syntax trees // Software Maintenance, 1998. Proceedings., International Conference on. – IEEE, 1998. – С. 368-377.
2. Bellon S. et al. Comparison and evaluation of clone detection tools // IEEE Transactions on software engineering. – 2007. – Т. 33. – №. 9.
3. Roy C. K., Cordy J. R. survey on software clone detection research // Queen’s School of Computing TR. – 2007. – Т. 541. – №. 115.
4. 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. – Т. 74. – №. 7. – С. 470-495.
5. Зельцер Н. Г. Поиск повторяющихся фрагментов исходного кода при автоматическом рефакторинге // Труды Института системного программирования РАН. – 2013. – Т. 25.
6. Ахин М. Х., Ицыксон В. М. Слайсинг над деревьями: метод обнаружения разорванных и переплетенных клонов в исходном коде программного обеспечения // Моделирование и анализ информационных систем. – 2015. – Т. 19. – №. 6. – С. 69-78.
7. Корнеев Г. А., Елизаров Р. А. Автоматическое тестирование решений на соревнованиях по программированию // Телекоммуникации и информатизация образования. – 2003. – №. 1. – С. 61-73.
8. Станкевич А. С. Методология и технические решения для проведения олимпиад по информатике и программированию // Парфенов-СПб. – 2011.
9. Johnson J. H. Identifying redundancy in source code using fingerprints // Proceedings of the 1993 conference of the Centre for Advanced Studies on Collaborative research: software engineering-Volume 1. – IBM Press, 1993. – С. 171-183.
10. Baker B. S. On finding duplication and near-duplication in large software systems // Reverse Engineering, 1995., Proceedings of 2nd Working Conference on. – IEEE, 1995. – С. 86-95.
11. Kamiya T., Kusumoto S., Inoue K. CCFinder: a multilinguistic token-based code clone detection system for large scale source code // IEEE Transactions on Software Engineering. – 2002. – Т. 28. – №. 7. – С. 654-670.
12. Prechelt L., Malpohl G., Philippsen M. Finding plagiarisms among a set of programs with JPlag // J. UCS. – 2002. – Т. 8. – №. 11. – С. 1016.
13. Komondoor R., Horwitz S. Using slicing to identify duplication in source code // International static analysis symposium. – Springer, Berlin, Heidelberg, 2001. – С. 40-56.
14. Ахин М. Х., Ицыксон В. М. Слайсинг над деревьями: метод обнаружения разорванных и переплетенных клонов в исходном коде программного обеспечения // Моделирование и анализ информационных систем. – 2015. – Т. 19. – №. 6. – С. 69-78
15. Mayrand J., Leblanc C., Merlo E. Experiment on the Automatic Detection of Function Clones in a Software System Using Metrics // icsm. – 1996. – Т. 96. – С. 244.
16. Kontogiannis K. A. et al. Pattern matching for clone and concept detection // Automated Software Engineering. – 1996. – Т. 3. – №. 1-2. – С. 77-108.
17. Balazinska M. et al. Measuring clone based reengineering opportunities // Software Metrics Symposium, 1999. Proceedings. Sixth International. – IEEE, 1999. – С. 292-303.
18. Davey N. et al. The development of a software clone detector // International Journal of Applied Software Technology. – 1995.
19. Малышев Е. В., Смелов В. В. Алгоритм распознавания плагиатов кодов программ // Труды БГТУ – 2018 – № 1 – С. 135-138.
20. Prado B., Bispo K. A., Andrade R. X9: An Obfuscation Resilient Approach for Source Code Plagiarism Detection in Virtual Learning Environments // ICEIS (1). – 2018. – С. 517-524.
21. Jiang Y., Xu C. Needle: Detecting Code Plagiarism on Student Submissions // TURC 2018 – 2018.
22. Bandara U., Wijayarathna G. A machine learning based tool for source code plagiarism detection // International Journal of Machine Learning and Computing. – 2011. – Т. 1. – №. 4. – С. 337.
+4   4   0
403