Размещено на http://www.allbest.ru/

ПРАВИТЕЛЬСТВО РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

Факультет компьютерных наук

Департамент программной инженерии

Выпускная квалификационная работа

Программа автоматической проверки заданий по программированию

По направлению подготовки 09.03.04 «Программная инженерия»

Научный руководитель:

доцент департамента программной инженерии,

к.т.н. Р.З. Ахметсафина

Выполнил:

студент группы БПИ121

4 курса бакалавриата

образовательной программы «Программная инженерия»

А.А. Коренев

Москва 2016



Реферат

Работа посвящена автоматизации процессов проверки заданий по программированию.

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

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

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

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

Ключевые слова: автоматизация проверки, автоматическое оценивание заданий по программированию.

Abstract

Current work is dedicated to automation of processes of programming assignments assessment.

In this paper, we provide a list of criteria which can be used during the grading of assignments. We also observed various approaches of source code analysis and different approaches of testing of programs behavior, which includes software build from source code besides actual launching.

We designed an approach to automated checking of programming assignments, based on the examined approaches of software verification and software building and testing automation using continuous integration technique

The aim of the work is a program which provides an ability to support various criteria of assignment checking and also to perform assessment of such criteria. The program aims to reduce amount of time spent on manual assessment and to reduce the gap between submitting an assignment and its assessment.

The built solution uses a continuous integration tool called Jenkins and has a web-interface for interacting with a user.

Keywords: assessment automation, checking automation, software assignments checking, software assignments assessment.



Основные определения, термины и понятия

1. Компиляция - транслирование исходного кода программы в более низкоуровневый код (иногда машинный код).

2. Критерий проверки - оцениваемый аспект сданной студентом работы.

3. Непрерывная интеграция - методика, направленная на осуществление постоянной сборки изменяемого проекта с целью осуществления регрессионного и интеграционного тестирования.

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

5. Подправило оценивания - правило оценивания отдельного критерия проверки работы.

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

7. Преподаватель - участник оценивания, предоставляющий общие файлы для задания, тестирующие правила, а также составляющий правило оценивания задания.

8. Регрессионное тестирование - методика тестирования программного обеспечения для обнаружения ошибок в уже протестированном исходном коде.

9. Стандарт оформления кода (стиль программирования) - набор правил, соблюдаемых при написании программного кода.

10. Статический анализ кода - анализ программного обеспечения, осуществляемый без запуска программы.

11. Студент - участник оценивания, предоставляющий файлы для их оценки.

12. Юнит-тестирование (модульное тестирование) - методика осуществления тестирования программного обеспечения с помощью тестирования отдельных изолированных модулей программы.



Оглавление

Реферат

Основные определения, термины и понятия

Введение

1. Предметная область

1.1 Критерии проверки задания

1.2 Существующие решения

1.3 Обзор подходов и инструментов

1.3.1 Проверка исходного кода на плагиат

1.3.2 Проверка исходного кода на возможность компиляции и проверка синтаксиса на корректность

1.3.3 Проверка исходного кода на соответствие стандартам оформления

1.3.4 Компиляция исходного кода

1.3.5 Юнит тестирование

1.3.6 Взаимодействие с программой через командную строку и файлы

1.3.7 Ограничение используемых ресурсов

1.3.8 Инструменты непрерывной интеграции

2. Алгоритмы проверки заданий по программированию

2.1 Алгоритм работы статических анализаторов кода

2.2 Алгоритм поиска плагиата в наборе документов

2.2.1 Генерализация исходного кода

2.2.2 Алгоритм поиска и сравнения отпечатков

2.2.3 Поиск отпечатков

2.2.4 Сравнение отпечатков документов

2.2.5 Поиск совпавших областей в парах документов

2.2.6 Описание параметров алгоритма

2.3 Критерии оцениваемой работы

2.4 Роли

2.5 Файлы заданий

2.6 Результаты проверки

2.6.1 Результат проверки критерия

2.6.2 Разграничение доступа к результатам

2.6.3 Формирование итоговой оценки

2.7 Этапы выполнения проверки задания

3. Программная реализация

3.1 Модель данных

3.2 Архитектура приложения

3.3 Сервер оценки

3.3.1 REST интерфейс

3.3.2 Формат данных

3.3.3 База данных

3.3.4 Система учетных записей

3.3.5 Аутентификация

3.3.6 Роли

3.3.7 Регистрация на курсе

3.3.8 Сохранение пароля пользователя

3.4 Оценка работы

3.4.1 Поддерживаемые критерии

3.4.2 Концепция оценщиков

3.4.3 Взаимодействие с Jenkins

3.4.4 Файловая структура

3.4.5 Безопасность выполнения стороннего кода

3.4.6 Оценщик для поиска плагиата

3.5 Хранение файлов

3.6 Веб интерфейс программы

3.6.1 Взаимодействие с сервером оценки

3.6.2 Система шаблонов

Заключение

Список источников

Введение

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

Зачастую на подобных дисциплинах работы студентов представляют собой исходный код или скомпилированные программы. «Ручная» проверка таких работ является рутинной и затратной по времени деятельностью.

Помимо временных затрат при «ручной» проверке возникает целый ряд проблем:

· Продолжительный период между сдачей работы и ее оцениванием может негативно сказаться на процессе обучения, так как обучающийся не получает своевременно обратную связь.

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

· Анализу программного кода зачастую уделяется намного меньше внимания, чем проверке работоспособности программы. Это может негативно сказываться на обучении написанию правильного и понятного исходного кода.

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

1. Изучить распространенные аспекты проверки заданий по программированию;

2. Провести анализ подходов к автоматизации проверки корректности работы программы;

3. Рассмотреть подходы к автоматизации анализа программного кода;

4. Рассмотреть подходы обнаружения плагиата в текстовых документах и программных кодах;

5. Выбрать подходы автоматизации проверки заданий по программированию на основе проведенного анализа;

6. Разработать архитектуру программы автоматизации проверки работ по программированию;

7. Разработать программу в соответствии с разработанной архитектурой;

8. Провести тестирование и отладку разработанной программы;

9. Разработать техническую документацию.

Работа структурирована следующим образом: в первой главе рассмотрены предметная область работы, а также рассмотрены возможные методики и алгоритмы для решения поставленных задач; вторая глава посвящена описанию выбранных подходов и алгоритмов для решения поставленных задач; в третьей главе описаны особенности реализации программы.



1. Предметная область

1.1 Критерии проверки задания

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

· В виде исходного кода программы. В случае компилируемого языка, для проверки работоспособности такой программы требуется провести этап компиляции исходного кода для получения запускаемого приложения. В случае же интерпретируемого языка программа уже может быть запущена в том виде, в котором и представлена.

· В виде скомпилированной программы, в случае использования компилируемого языка.

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

Под анализом исходного кода имеется в виду статический анализ кода (static code analysis), то есть анализ программного обеспечения без его исполнения. Перечислим возможные критерии анализа исходного кода заданий:

· Проверка исходного кода на плагиат. Данный пункт представляет собой выявление схожих участков кода между документов среди определенного набора файлов исходного кода.

· Проверка исходного кода на возможность компиляции (для компилируемых языков) и проверка синтаксиса на корректность. Данная проверка позволяет определить, соответствует ли код программы конструкциям языка программирования, на котором она была написана, и в следствие этого, может ли она быть скомпилирована и запущена.

· Проверка исходного кода на соответствие стандартам оформления кода. В данном пункте исходный код проверяется на удовлетворение определенным стандартам стиля программирования. Данные стандарты являются могут сильно отличаться от языка к языку. Примером такого стандарта для языка Java может являться Google Java Style [2].

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

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

· Проверка корректности работы программы с помощью юнит-тестирования (unit-testing) [3] представляет собой анализ работоспособности отдельных изолированных участков программы на предмет соответствия ими определенных критериев.

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

1.2 Существующие решения

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

Тем не менее, существует ряд инструментов, которые решают похожие задачи, среди которых можно выделить три наиболее подходящих и популярных инструмента: ejudge [4], Peach³ [5] и Web-CAT [6].

1. ejudge является системой проведения онлайн соревнований по программированию и представляет собой мощный инструмент, позволяющий компилировать и запускать программы на исходном коде большинства популярных языков программирования. ejudge также способен осуществлять проверку правильности программы, используя для ввода-вывода данных командную строку. Также существуют аналоги, такие как codeforces [7], Timus [8], предоставляющие схожий функционал проверки программного обеспечения.

2. Peach³ - система управления обучением, позволяющая компилировать и тестировать ПО на языке Java с помощью юнит-тестирования. Некоторые версии Peach³ предоставляют возможность проверки исходного кода на плагиат, однако такие версии продукта не являются свободно распространяемыми. Данная система предоставляет возможность проверки исходного кода на соответствие стилю программирования на языке Java.

3. Web-CAT предоставляет возможности автоматизированной системы оценивания исходного кода по критерию полноты тестирования этого кода. Одним из основных плюсов данного инструмента является его расширяемая архитектура. Тем не менее, активная разработка Web-CAT не ведется уже с 2012 года.

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

1.3 Обзор подходов и инструментов

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

1.3.1 Проверка исходного кода на плагиат

Чтобы провести анализ подходов поиска плагиата в наборе документов, необходимо выделить ряд изменений исходного текста программы, к которым должен быть устойчив эффективный алгоритм [9]:

1. изменение комментариев кода;

2. изменение количества переносов строк, пробелов и отступов;

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

4. переименование переменных и функций;

5. замена строковых и символьных констант;

6. перестановка блоков кода;

7. добавление «ненужных» блоков кода (т.е. таких, которые практически не влияют на исполнение программы).

Среди наиболее распространенных подходов обнаружения плагиата можно выделить следующие [10]:

· Анализ строковых представлений программного кода (поиск точных строковых совпадений между программными кодами). Алгоритмы такого рода, как правило, являются быстрыми, но не учитывают возможных изменений кода между работами в случае плагиата;

· Токенизирование строковых представлений программного кода и обработка полученных токенов (конвертация исходного кода в набор токенов и их анализ). Данный подход позволяет избавиться от проблем, которые связаны с простыми изменениями изначальных документов, например, изменение количества пробелов, комментариев и т.д.;

· Анализ синтаксических деревьев (создание структур данных в виде деревьев, которые отражают синтаксическую структуру кода, и их сравнительный анализ). Данный подход является эффективным для обнаружения участков кода, которые не изменяют своей структуры в различных файлах, что наблюдается довольно редко;

· Анализ графов вызовов (анализ поведения программного кода). Подход, позволяющий сравнивать функциональную составляющую написанных исходных кодов. Похож на анализ синтаксических деревьев;

· Атрибутные методы (подсчет различных метрик: количество операторов, операндов, цикломатическая сложность и др.). Метод является простым для реализации, но может содержать большое количество случайных совпадений, когда количественные значения метрик совпадают, но при этом функциональный смысл участков кода является совершенно разным.

Существует довольно много инструментов для поиска плагиата в работах на естественном языке, многие из которых являются бесплатными и доступны в сети Интернет. Более того, многие из таких инструментов ищут плагиат с помощью нахождения точных копий участков кода, что не всегда эффективно. Намного меньше инструментов, которые учитывают специфику программных кодов и многих описанных выше типов изменений. Наиболее популярными и близкими к выделенным критериям инструментами являются MOSS (Stanford University) [11] и JPlag (Karlsruhe Institute of Technology) [12]. Но эти инструменты не чувствительны к некоторым из перечисленных ранее типов изменений исходных работ, а именно изменениям типов (3) и (5).

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

1) высокая скорость работы;

2) устойчивость к перестановкам частей документа [15];

3) относительно простая реализация;

4) устойчивость к шумам (т.е. вставке дополнительных участков текста в исходный документ) [15].

Использование данного алгоритма, однако, не решает задачу обнаружения плагиата полностью, а решает только проблемы, связанные с изменениями типов (6) и (7) [15]. Алгоритм находит совпадающие части в парах документов, но чувствителен к изменениям типов (1) - (5).

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

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

1.3.2 Проверка исходного кода на возможность компиляции и проверка синтаксиса на корректность

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

Однако если речь идет об интерпретируемых языках, то ситуация обстоит несколько иначе. Существует возможность запустить программу, исходный код которой может использовать неверные конструкции данного языка. Более того, такая программа может отработать безошибочно, так как в некоторых случаях, она выдает ошибку только в случае попытки выполнения этого ошибочного кода.

Существует множество инструментов и онлайн сервисов для проверки интерпретируемого программного кода на корректность, среди которых можно выделить PEP 8 (Python) [16], PHP Code Checker [17], JSLint (JavaScript) [18] и многие другие.

1.3.3 Проверка исходного кода на соответствие стандартам оформления

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

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

Можно выделить наиболее популярные инструменты: Intellij IDEA (Java) [19], PMD (Java) [20], Clang (C, C++, Objective-C) [21], PVS-Studio (C, C++, C++11, C#) [22] и многие другие.

1.3.4 Компиляция исходного кода

В случае, если программа представлена в виде исходного кода на компилируемом языке программирования, необходимо провести этап компиляции кода, чтобы протестировать ее работоспособность.

Сама по себе компиляция одного или несколько файлов исходного кода не представляется сложной задачей, так как подавляющее большинство компиляторов имеет простой и понятный интерфейс взаимодействия с помощью командной строки. Для примера можно взять взаимодействие с компилятором языка Java, который вызывается с помощью команды «javac»:

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

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

К сожалению, не существует единого инструмента, поддерживающего сборку проектов на всех возможных языках программирования, но можно рассмотреть наиболее популярные из них, осуществляющие поддержку распространенных языков программирования:

· Make [23] - одна из самых первых утилит для сборки проекта, появившаяся в 1977 году. Данный инструмент основан на чтении файлов «Makefile», в которых описаны так называемые правила, представляющие собой инструкции, применяемые при сборке.

· CMake [24] является кроссплатформенной системой автоматизации сборки программного обеспечения. Данная система, однако, не занимается непосредственно сборкой, а генерирует команды для других сборщиков на основе используемой операционной системы. Таким образом, Cmake, запущенный на операционной системе семейства Unix будет генерировать файлы «Makefile», а на операционной системе семейства Windows «.vcproj/.sln», использующиеся при сборке с помощью Visual C++. Данная система обычно используется для сборки проектов, написанных на языке C/C++.

· Apache Ant [25] - декларативный кроссплатформенный фреймворк для сборки проектов. Данный фреймворк является аналогом системы Make, но команды для сборки в данной системе конфигурируются в виде XML-файлов. До фреймворка Apache Maven данный инструмент был наиболее популярным для сборки проектов на Java.

· Apache Maven [26] является кроссплатформенным фреймворком для автоматизации сборки проектов, написанных на Java, Ruby, Scala, С#, Groovy и других языках. Данный фреймворк является одним из самых популярных на данный момент для сборки проектов на языке Java. Из достоинств фреймворка можно выделить богатый выбор плагинов, которые позволяют расширить возможности фреймворка.

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

1.3.5 Юнит тестирование

Одним из самых популярных подходов тестирования программного обеспечения является юнит-тестирование (модульное тестирование). Главной идеей юнит-тестирования является проверка корректности отдельных изолированных участков программы, что позволяет оценивать корректность части программного обеспечения без тестирования всей программы целиком.

Вследствие широкой распространенности было создано значительное количество инструментов для осуществления данного типа тестирования. Одним из примеров таких фреймворков является семейство xUnit [3], поддерживающее большинство популярных языков программирования. Помимо этого, юнит-тестирование является встроенным в качестве одного из этапов сборки проекта при использовании некоторых фреймворков автоматической сборки (например, Apache Maven). Тем не менее, инструменты тестирования позволяют запускать тесты и без использования подобных фреймворков сборки. Для юнит-тестирования иногда требуется исходный код программы. Так, например, для программ на языке C++ может понадобиться компиляция исходных кодов программы вместе с кодами модульных тестов, чтобы получить итоговую программу.

1.3.6 Взаимодействие с программой через командную строку и файлы

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

Несмотря на то, что способ взаимодействия программы через командную строку предназначен скорее для взаимодействия с человеком, нежели чем с другими программами, автоматизация данной проверки может быть осуществлена с помощью средств операционной системы.

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

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

1.3.7 Ограничение используемых ресурсов

Важным аспектом проверки работы программного обеспечения является уровень потребляемых ресурсов.

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

Однако при юнит-тестировании могут возникнуть некоторые проблемы:

· Сложно оценить количество памяти, выделенной для самой тестируемой программы, а не для инструмента модульного тестирования. В связи с этой проблемой, превышение установленных лимитов может происходить за счет кода, который не является объектом тестирования.

· Не все инструменты тестирования позволяют регулировать время работы отдельных тестов. Так, например, фреймворк для тестирования приложений на языке C++ Google Test не позволяет останавливать тесты, по окончании заданного времени. Тем не менее, возможно контролировать время работы всех интеграционных тестов вместе, но в то же время теряется гранулярность проверки отдельных блоков кода, которые могут иметь различные требования к потреблению ресурсов.

1.3.8 Инструменты непрерывной интеграции

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

Наиболее популярными инструментами непрерывной интеграции являются: Jenkins (Hudson) [27], TeamCity (JetBrains) [28], Bamboo (Atlassian) [29] и другие.

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



2. Алгоритмы проверки заданий по программированию

2.1 Алгоритм работы статических анализаторов кода

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

Как правило, статический анализ кода предполагает анализ исходного текста программы для построения определенной модели на его основе. Рассмотрим наиболее известные модели [30]:

· Абстрактное синтаксическое дерево представляет программный код с помощью древовидной структуры, где вершины дерева являются элементами конструкций языка программирования. Пример дерева представлен на рис. 1.

Рисунок 1. Визуализация абстрактного синтаксического дерева на примере программного кода

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

· Диаграмма классов - в объектно-ориентированных языках программирования, модель, отражающая отношения между классами, их атрибутами и методами.

· Граф потока управления - модель, представленная в виде графа, отражающая все возможные пути исполнения программы.

После извлечения модели, алгоритм начинает ее анализ на предмет выявления характеристик, не подходящих под ряд правил. В качестве примера можно рассмотреть анализ дерева разбора, чтобы проверить соответствие программного кода на соответствии стандартам стиля программирования.

2.2 Алгоритм поиска плагиата в наборе документов

2.2.1 Генерализация исходного кода

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

Шаги данного алгоритма выполняются строго в порядке их описания.

Для устранения различий между документами с различными комментариями (изменение (1)) все комментарии исключаются из документов.

Для устранения различий между документами с измененными типами возвращаемых значений функций или типов переменных (изменение (3)) все возвращаемые типы функций и типы переменных изменяются по следующим правилам:

1. Все названия целочисленных типов и их классов-оберток (таких как «int», «Integer», «long», «Long», «byte», «Byte», «char», «Character» и др.) меняются на «int».

2. Все названия типов чисел с плавающей точкой и их классов-оберток (такие как «double», «Double», «float», «Float») меняются на «flt».

3. Все остальные названия типов в Java меняются на «ref».

Для устранения различий между документами с измененными названиями переменных и функций (изменение (4)) все названия переменных и функций изменяются по следующим правилам:

1. Все имена функций при вызове и декларации изменяются на «fun».

2. Все объявления переменных с определенным типом изменяются на название этого типа. Пример: строка «int x = 0» на данном этапе изменится на «int = 0», а строка «flt y» изменится на «flt».

Для устранения различий между документами с различным количеством переносов строк, пробелов и отступов (изменение (2)) все переносы строк, пробелы и отступы исключаются из документов.

Для устранения различий между документами с различными строковыми и символьными константами (изменение (5)) проводится замена всех строковых констант на строку «str» и всех констант типа char на строку «chr».

Рисунок 2. Пример работы алгоритма генерализации исходного кода на участке кода -приведение похожих структур к одинаковым

2.2.2 Алгоритм поиска и сравнения отпечатков

Алгоритм поиска и сравнения отпечатков документов является одним из наиболее популярных алгоритмов для поиска плагиата. Он основан на выборе множества небольших участков документа в качестве отпечатка этого документа и сравнения этого отпечатка с другими [13,14]. В данной работе этот алгоритм применяется на генерализированных исходных кодах.

Алгоритм использует параметры и - положительные целочисленные значения, смысл которых станет понятен при описании алгоритма.

Введем определение функции , которая возвращает детерминированное (при одинаковых входных параметрах всегда возвращается одно и то же значение) целочисленное равномерно распределенное значение в определенном диапазоне значений, где - подстрока документа [15]. Результат данной функции мы будем называть хэшем.

Введем определение как последовательной подстроки документа длиной символов [15].

2.2.3 Поиск отпечатков

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

Чтобы сделать это с минимальными затратами по времени, используется алгоритм кольцевого хэша [15]. Этот метод позволяет вычислять за короткое время (алгоритмическая сложность ) хэш подстроки из символов из значения хэша для подстроки . Для этого применяется следующая формула:

,

где - целое простое неизменяемое в ходе алгоритма число.

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

Выбранный набор хэшей и является отпечатком документа.

Рисунок 3. Схематическое представление вычисления отпечатка на строковой последовательности “adorunrunrun”

2.2.4 Сравнение отпечатков документов

После отбора всех хэшей документа необходимо сравнить два набора хэшей друг с другом, чтобы определить степень присутствия одинаковых участков в обоих документах.

Назовем последовательности хэшей и отпечатками документов и соответственно. Определим значение как степень «присутствия» документа в документе по формуле [31]:

,

Далее можно определить значение максимального «присутствия» между документами и по формуле, которая выводится из предыдущей формулы для расчета :

,

Для расчета данного значения необходимо быстро вычислять значение пересечения двух наборов хэшей. Для этого можно отсортировать оба набора (алгоритмическая сложность ), где - количество сортируемых элементов) и затем, используя алгоритм соединения слиянием сортированных списков [32], вычислить повторяющиеся значения хэшей и их количество (алгоритмическая сложность , где и - размеры наборов хэшей).

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

2.2.5 Поиск совпавших областей в парах документов

После нахождения всех значений часть значений отсеиваются по определенному числовому порогу, чтобы исключить неверные совпадения, значение которого принадлежит отрезку [0.0, 1.0). Так как заданное на входе алгоритма значение k (длина строки, по которой вычисляется хэш) является длиной подстроки, которая при совпадении с большой долей вероятности является заимствованной из другого документа подстрокой [15], пороговое значение должно быть сравнительно небольшим. В данной программе значение равно , что показывает хорошие результаты в отношении отсеивания неверных совпадений.

После отсеивания всех неверных совпадений начинается поиск совпавших участков среди пар документов.

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

Позиции совпавших областей запоминаются и записываются в исходных документах.

2.2.6 Описание параметров алгоритма

Как было отмечено ранее, алгоритм поиска и сравнения отпечатков использует два параметра, k и h, которые задаются определенными константными значениями:

1) - длина подстроки, по которой высчитывается значение функции . Значение должно задавать длину строки, при которой множественное совпадение различных строк длины с другим документом будет считаться подозрительным [15]. Все обнаруженные совпадающие подстроки длиной меньше не будут расценены алгоритмом как плагиат. С учетом генерализации исходного кода, которая сводит анализируемый документ практически до взаимодействия трехсимвольных переменных с математическими операторами и другими конструкциями языка Java, берется значение равное . Это значение больше, чем наиболее длинные генерализированные конструкции, которые зачастую встречается в данном языке.

2) - длина «окна» в рамках которого необходимо выбрать хэш, чтобы он вошел в отпечаток документа. Значение варьируется в зависимости от размера документа, но не может быть менее 15 и более 35. Наименьшее значение выбирается в случае, если документ имеет размер менее 8000 символов. Если документ больше, то можно увеличить значение , чтобы уменьшить размер получаемых отпечатков для ускорения работы алгоритма. Оценка верхней границы параметра получена экспериментально. При ее превышении в отпечаток документа не попадает значительная его часть, и плагиат может быть не выявлен.

2.3 Критерии оцениваемой работы

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

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



2.4 Роли

В контексте описания алгоритмов оценивания заданий по программированию важно определить понятие роли участника оценивания. Можно выделить следующие условные роли:

· Преподаватель - участник, составляющий критерии оценивания конкретного задания.

· Студент - участник, предоставляющий программы системе для проведения их оценки на основе правил, составленных преподавателем.

2.5 Файлы заданий

Необходимо определить ряд различных групп файлов, принимающих участие в процессе оценивания:

· Файлы, предоставленные преподавателем в качестве общих файлов задания (общие файлы или common files). Данные файлы должны предоставляться студенту для выполнения задания. Такие файлы непосредственно не участвуют в ходе оценивания и служат исключительно для помощи студенту при выполнении задания. Они могут содержать как структуру папок, так и другие файлы, в том числе и программные коды. Стандартным примером подобной группы файлов является базовая структура проекта, в рамках которой студенту необходимо разработать собственное решение.

· Файлы, предоставленные студентом в качестве оцениваемой работы (файлы студента или student files). Данные файлы представляют собой программы в виде исходных кодов или уже скомпилированных файлов.

· Файлы, предоставленные преподавателем в качестве файлов, участвующих в проверке работ, которые не предоставляются студенту (файлы проверки или secret files). Данные файлы могут содержать программные коды, представляющие собой другие программы, участвующие при тестировании (например, файлы юнит-тестов), а также другие файлы конфигурации оценивания.

2.6 Результаты проверки

2.6.1 Результат проверки критерия

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

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

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

В качестве результата проверки конкретного критерия используются целочисленные метрики, отражающие количества неудач и удач (если таковые существуют), а также опциональный отчет в виде строкового представления, предназначенный для ознакомления непосредственно студентом или преподавателем.

2.6.2 Разграничение доступа к результатам

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

2.6.3 Формирование итоговой оценки

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

Правило оценивания определяется для всех участников задания и применяется для объединения результатов оценки работы программы в единый числовой вид.

Оценка за работу студента может принимать значение от 0 до 100 баллов. Формула вычисления оценки устанавливается преподавателем.

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

,

где - подправило с индексом , - множество индексов блокирующих правил, а - итоговая оценка.

Подправило же применяется для оценки одного конкретного критерия. Значение оценки подправила выражается в виде числа от 0 до 100. Возможные типы подправил, применяемых в различных случаях представлены в табл. 1.

Таблица 1 Типы подправил оценивания

Тип подправила	Правило составления оценки
Долевое	,
Долевое с порогом	,
Штрафное	,
Штрафное с порогом	,

2.7 Этапы выполнения проверки задания

Определим упорядоченный список этапов проверки заданий:

1. Работа загружена студентом;

2. Выполняется проверка правил задания, заданных преподавателем. Определяется набор проверок, необходимых для проведения тестирования;

3. Основываясь на определенных в шаге 2 проверок, начинается параллельная проверка статического анализа кода за исключением проверки на плагиат (даже если она была указана в качестве правил, заданных преподавателем), а также проверка исполнения программы;

3.1. Используя определенный в шаге 2 набор необходимых проверок исходного кода, начинается статический анализ кода. Проверки могут быть запущены параллельно по причине независимости их результатов. Для увеличения скорости проверки алгоритмы могут быть объединены, но это является частным случаем;

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

3.2.1. Загруженные файлы студентом (student files) и файлы, предоставленные преподавателем, для проведения тестирования (secret files) объединяются в один проект;

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

3.2.3. В случае, если необходимо провести юнит-тестирование проекта, программа запускается вместе с юнит-тестами, предоставленными в файлах проверки (secret files);

3.2.4. В случае, если необходимо провести тестирование с помощью проверки взаимодействия программы с командной строкой, программа запускается и в нее передаются данные, предоставленные в файлах проверки (secret files). Ожидаемый выход программы также представлен в файлах проверки, который используется для определения корректного поведения программы;

4. В случае завершения всех проверок (за исключением плагиата), определяется правило (набор подправил), формирующих оценку;

5. После определения правила оценивания, начинается формирование оценки - применение подправил к значениям метрик, полученным в ходе тестирования различных критериев;

6. После применения правила оценивания, полученная оценка запоминается. Далее генерируется три вида отчета, основанных на настройках доступа к отчету о проверке студентом: отчет для просмотра студентом до окончания приема работ, отчет для просмотра студентом после окончания приема работ, отчет для просмотра преподавателем.

Схематическое представление последовательности этапов проверки продемонстрировано на рис. 4.

Проверка заданий на плагиат осуществляется при наступлении окончания срока приема заданий на проверку или по запросу преподавателя.

Рисунок 4. Схематическое представление этапов проведения проверки задания по программированию

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

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



3. Программная реализация

3.1 Модель данных

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

1. Курс - сущность, используемая для группировки набора заданий. Данная сущность может быть ассоциирована с дисциплиной, которая содержит набор заданий.

2. Задание - сущность, используемая для представления задания по программированию. Задание может содержать в себе описание, предоставлять общие файлы (common files) и файлы для проведения оценки (secret files), а также иметь крайний срок приема работ на проверку. Задание должно содержать в себе набор подправил оценивания, по которому осуществляется формирование итоговой оценки.

3. Подправило оценивания - сущность, используемая для отображения определенного аспекта работы, которое возможно оценить. Правило оценивания содержит определенный вес, который отображает, насколько сильно данное правило влияет на формирование оценки.

...