Програмна система оцінки плагіату програмного коду

Програмна система оцінки плагіату програмного коду

плагіат проектування програма діаграма

Вступ

Основне завдання викладача під час викладання свого предмету — це дати студентові знання. Також у планах за курсом, крім прослуховування лекцій, студенти повинні виконати ряд лабораторних робіт і курсову роботу, якщо вона передбачена за планом. Але у зв’язку з бурхливим розвитком Інтернету та засобів комунікації, почали з’являтися готові бази з вирішеними завданнями. Також студенти мають друзів на старших курсах, які могли вже здати предмет до цього. Або ж один з кращих студентів здає роботу, і вона розходиться по всіх групі. У всіх випадках недобросовісні студенти беруть готову роботу, змінюють її трохи та видають за свою власну розробку. З цим можна боротися. Можна кожному студенту видавати унікальне завдання. Також можливо ретельно переглядати кожну роботу на наявність плагіату. Але напевно найкращим рішенням буде автоматизація перевірки на плагіат. Викладач зможе до початку прийому лабораторної або курсової роботи перевірити її на плагіат.

Для нас плагіат — це безпосереднє використання чужого коду у своєму. Частина однієї програми є плагіатом частини іншої програми, якщо вона була отримана з неї копіюванням з подальшою незначною зміною коду (випадкові вставки в код, перегрупування методів, перейменування змінних, рефакторинг коду)[1].

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

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

Найкращім рішенням для боротьби з плагіатом є створення системи для виявлення плагіату[2], в базі якої будуть зберігатися всі здані лабораторні роботи студентів за весь час існування навчального закладу. Коли викладач буде приймати роботу, він завантажить в програму по виявленню плагіату код студента, який перевіряється з усіма програмами вже зданими до нього. Якщо програма по виявленню плагіату знайде плагіат коду, вона покаже це в зручній формі, і викладач одразу зможе довести студенту, що в його роботі присутній плагіат.

На цей час в навчальних закладах, де є спеціальності зв’язані з програмуванням є гарна практика, розробляти свої детектори плагіату. Наприклад Стенфордський університет, математичний інститут ім. В. А. Стеклова РАН та інші, мають свої детектори плагіату, які перевіряють роботи студентів.

Об'єкт дослідження у даній роботі це алгоритми пошуку плагіату, тому що складніше вибрати або розробити алгоритм чим реалізувати його.

Методами дослідження є пошук алгоритмів в Інтернеті та вивчення існуючих систем по виявленню плагіату.

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

1. Аналіз предметної галузі та постановка задачі

1.1 Актуальність проблеми

На даний момент, під час широкого розвитку ІТ інтелектуальна власність стає все більш і більш цінною. В зв’язку з великою кількістю цього виду власності, виникла необхідність створення потужної системи захисту цієї власності. Для цих цілей краще всього підходить автоматична перевірка авторства або на плагіат.

Плагіат — умисне привласнення авторства чужого твору науки або мистецтва, чужих ідей або винаходів. Плагіат може бути порушенням авторсько-правового законодавства і патентного законодавства і в якості таких може спричинити за собою юридичну відповідальність. З іншого боку, плагіат можливий і в областях, на які не поширюється дія будь-яких видів інтелектуальної власності, наприклад, в математиці та інших фундаментальних наукових дисциплінах.

Найбільш часто плагіат виражається у публікації під своїм ім'ям чужого твору або чужих ідей, а також у запозиченні фрагментів чужих творів без зазначення джерела запозичення. Обов’язковою ознакою плагіату є присвоєння авторства, так неправомірне використання, опублікування, копіювання і т.п. творів, що охороняється авторським правом, саме по собі є не плагіатом, а іншим видом порушення авторського права, часто званим «піратством».

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

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

Обфускація або заплутування коду — приведення вихідного тексту або виконуваного коду програми до виду, зберігає її функціональність, але ускладнює аналіз, розуміння алгоритмів роботи і модифікацію при декомпіляції[3].

При здачі запозичених робіт, студенти технічних навчальних закладів, дуже часто застосовують обфускацію. Несумлінний студент бере у найкращого учня здану роботу (див. рис. 1.1). Потім він переставляє код, та міняє назву змінним (див. рис. 1.2). Якщо в програмі дуже багато коду, та студент дуже заплутав програму, виклад не завжди зможе улучити студента у плагіаті. Тому є необхідність автоматизувати перевірки, для економії сил та часу для викладача.

Рисунок 1.1 — Код оригіналу Рисунок 1.2 — Код плагіату Система розробляється в даній бакалаврській роботі, не пропускатиме заплутування коду і повідомлятиме про плагіат, якщо буде знайдено хоча б 40% чужої роботи.

Хоча в автоматизованих системах плагіату є недоліки, тому обов’язково у людини, яка буде робити перевірку на плагіат повинна бути можливість подивитися в частки коду, де детектор плагіату знайшов підозрілу частину на плагіат.

1.2 Огляд аналогів

На даний момент вже існують програми, які виявляють плагіат в кодах програм. Але деякі детектори плагіату пристосовані тільки до змін назв змінних, якість таких детекторів є, але треба, щоб детектор був ще пристосований до перестановку часток коду, або методів. До детекторів плагіату, які виконують дані умов входять JPlag[4], SID[5], MOSS[6]. Їх і будемо аналізувати.

Будь-яка програма має певну ієрархію структур, які можуть бути виявлені, виміряні і використані як характеристики програми. Стосовно до доведення факту запозичення ці характеристики повинні слабо змінюватися у випадку модифікації програми або включення фрагментів однієї програми в іншу. Імена процедур і змінних, текстові рядки і таке інше можуть бути легко змінені зловмисником і тому не повинні використовуватися для отримання характеристик. Для цієї мети краще підійде послідовність операторів програми, оскільки модифікація цієї послідовності вимагає глибокого розуміння логіки функціонування програми і є дуже трудомістким процесом. Процес перетворення початкового коду в послідовність операторів називається токенізірованням.

Всі алгоритми які розглядалися в аналізі реалізовані з використанням токенізірованного представлення коду.

У таблиці 1.1 наведені характеристики аналізованих детекторів плагіату. На цій таблиці ми маємо змогу побачити, які моделі подання початкових даних використовує кожна система перевірки на плагіат, та який алгоритм був реалізований. Також ми бачимо, які мови програмування вони використовують. З цієї таблиці видно, що детектор плагіату MOSS, підтримує найбільшу кількість мов програмування.

Таблиця 1.1 — Алгоритми та мови аналізованих алгоритмів

1.2.1 Детектор плагіату JPlag

Детектор плагіату JPlag був розроблений на мові програмування Java[7]. В ньому присутня можливість перевірки коду на мовах програмування С/C++, C#, Java та Scheme. В цьому детекторі використовується алгоритм жадібного строкового замощення, цей алгоритм відноситься до структурних методів пошуку плагіату.

Для отримання доступу до детектору потрібно надіслати електронний лист розробникам, в якому вказати свої данні та описати мету для якої буде використовуватися даний детектор. Після подачі листа, адміністратор системи виносить рішення стосовно доступу до системі.

Розглянемо евристичний алгоритм отримання жадібного строкового замощення. Алгоритм отримує на вхід два рядки символів над певним алфавітом (безліч допустимих токенів), а на виході дає набір їх загальних непересічних підрядків близький до оптимального. Підрядок, що входить у цей набір, будемо називати тайл (tile). Нехай P і T — токенізірованне подання порівнюваних програм.

— minimumMatchLength — мінімальна довжина найбільшого загального префікса рядків Pp і Tt, при якій він враховується алгоритмом;

— maxmatch — довжина найбільшого з поки знайдених на поточної ітерації алгоритму загальних префіксів рядків Pp і Tt;

— tiles — набір тайлів;

— mathes — безліч, що містить кандидатів на потрапляння в набір тайлів.

Алгоритм можна розділити на дві фази:

а) шукаються найбільші загальні підрядки P і T, які містять тільки непозначені елементи (спочатку алгоритму всі елементи непозначені). Для цього використовуються три вкладених циклу: перший пробігає по всіх можливих Pp, другий за всім Tt, а третій знаходить найбільший спільний префікс Pp і Tt. Далі існує три варіанти в залежності від співвідношення величин maxmatch і знайденого префікса;

1) якщо maxmatch менше, то ми видаляємо зі списку загальних підрядків matches все, що було до цього додано і поміщаємо туди знайдений префікс;

2) якщо maxmatch більше, то нічого не міняємо;

3) якщо вони рівні, то додаємо найбільший спільний префікс Pp і Tt до списку matches;

б) проходимо за списком, якщо поточний елемент списку — підрядок, що не містить помічених елементів, тоді поміщаємо його у вихідний набір tiles (тепер цей підрядок називатимемо tile — звідси і назва алгоритму), позначаємо всі елементи аналізованої рядки, що входять в P і T. Якщо довжини рядків у списку більше MinimumMatchLength, то переходимо до першої фази.

Переваги алгоритму:

— переваги токенізірованного подання;

— загальні підрядки меншої довжини, ніж MinimumMatchLength ігноруються, тому алгоритм не бере в розрахунок невеликі випадково збігли ділянки коду;

— при розбитті ділянки коду на дві і більше частини вставкою одного-кількох блоків або одиночних операторів, а також перестановкою невеликої кількості незалежних операторів, функція схожості слабо змінюється;

— алгоритм нечутливий до перестановок великих фрагментів коду.

Недоліки алгоритму:

— можливість збігу токенізірованного представлення програм, але відсутності збігу у вихідних кодах програм;

— розбиття збіги на блоки вставкою або заміною оператора на схожий (наприклад, for на while), кожен довжиною менше MinimumMatchLength, веде до повного ігнорування збігу;

— через евристик, що використовуються в алгоритмі, збіги, довжиною меншою ніж MinimumMatchLength, будуть проігноровані.

1.2.2 Детектор плагіату MOSS

В детекторі плагіату MOSS використовується алгоритм, який базується на методі відбитків, цей метод відноситься до сигнатурних методів виявлення плагіату[8]. Розглянемо цей алгоритм.

Метод відбитків:

— хешіруемо всі підрядки токенізірованної програми P фіксованої довжини;

— виділяємо деяку підмножину їх хеш-значень, що добре характеризує P;

— проробляємо ті ж кроки для токенізірованих програм T1, T2 … Tn і поміщаємо вибрані хеш-значення в базу;

— за допомогою хеш-таблиці (бази) отримуємо набір ділянок рядка P, підозрілих на плагіат;

— аналізуємо результат і робимо висновки.

1.2.3 Детектор плагіату SID

В детекторі плагіату SID використовується алгоритм обчислення метрики на основі Колмогоровской складності, цей алгоритм відноситься до складу структурних методів виявлення плагіату. Розглянемо цей алгоритм:

— проводиться токенізація;

— запускається алгоритм cтиснення токенів, заснований на алгоритмі стиснення LZ.

1) першим ділом він знаходить довжелезний неточно повторюваний підрядок, що закінчується в поточному символі;

2) кодує її покажчиком на попереднє розміщення;

3) зберігає інформацію про внесені поправки.

Реалізація відрізняється від класичного LZ-стиснення деякими особливостями, пов’язаними зі специфікою завдання: класичний алгоритм сімейства LZ з обмеженим буфером може пропустити деякі довгі повторювані підрядки через обмеження на розмір словника під час кодування. Це не страшно для кодування звичайних текстів, де потрібно перш за все економити пам’ять і зменшувати час виконання, адже втрати якості стискування будуть вкрай малі. Але в силу специфіки нашої задачі і вибраного алгоритму її рішення, використовує неточні збіги, втрата навіть невеликої кількості довгих повторюваних підрядків неприйнятна.

Переваги алгоритму:

— перевага токенізірованного подання;

— використовується евристичне наближення метрики, такий що, якщо дві програми, близькі щодо будь-якої іншої функції відстані, будуть близькими щодо даної;

— загальні підрядки, менше порогової довжини ігноруються, тому алгоритм не бере в розрахунок малі випадково збігли ділянки;

— при розбитті співпала ділянки коду на дві і більше частини вставкою одного-кількох блоків або одиночних операторів, функція схожості слабо змінюється;

— вкрай висока стійкість до вставки операторів;

— алгоритм нечутливий до перестановок великих фрагментів коду.

Недоліки алгоритму:

— можливість збігу токенізірованного представлення програм, але відсутності збігу у вихідних кодах програм.

1.2.4 Висновки огляду аналогів

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

Для якості знаходження плагіату було вирішено зробити 3 перевірки:

— перевірка коду ніяк не зв’язаного між собою;

— перевірка коду з частками коду іншої програми та перестановкою методів;

— перевірка коду з зміною тільки назв змінних.

Після аналізу було виявлено, що усі детектори гідно справляються з поставленим завданням. Детектори JPlag та MOSS показали приблизно однакові результати, детектор SID гірше за всіх впорався. Результати перевірки можемо переглянути на таблиці 1.2.

Таблиця 1.1 — Результати перевірки якості алгоритмів

1.3 Опис існуючих алгоритмів виявлення плагіату

Окрім алгоритмів які, були описані раніше, існує ще декілька непоганих алгоритмів. Існують структурні методи пошуку плагіату та атрібутні.

Атрібутні методи з’явилися раніше структурних. Основна їх ідея полягає в чисельному виразу якихось ознак програми та порівняння цих ознак з іншими програмами. Програми з близькими чисельними характеристиками вважаються потенційно схожими.

Структурний метод є більш нових підходом, він базується на порівнянні програм з урахуванням їхньої структури. Ця процедура більш складна ніж порівняння ознак програми. Структурні методи досліджують властивості програми не ізольовано, а як би в контексті, встановлюють взаємозв'язок різних характеристик, їх спільну поведінку. Для розібраним структурних методів потрібно відкидати зайву інформацію, для подальшій перевірки.

Недоліком структурних методів є їх обчислювальна трудомісткість. Також в більшості випадків структурні методи спираються на синтаксисі конкретної мови програмування.

Атрібутні методи не дуже якісні, їх можна використовувати тільки для попереднього аналізу, після якого буде проводитися перевірка структурними методами. Саме тому в даній роботі будуть розглянуті тільки структурні методи.

1.3.1 Концептуальний граф

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

Абстрактне синтаксичне дерево — в інформатиці це скінченна множина, позначене і орієнтоване дерево, в якому внутрішні вершини співставленні з відповідними операторами мови програмування, а листя з відповідними операндами[9]. Таким чином листя є порожніми операторами і являють собою тільки змінні і константи. Синтаксичні дерева використовуються в парсерах для проміжного представлення програми між деревом розбору і структурою даних яка потім використовується в якості внутрішнього представлення компілятора або інтерпретатора комп’ютерної програми для оптимізації і генерації коду.

Представлення програми у виді абстрактного синтаксичного дерева гарантую, що будь яка перестановка коду, не має ніякого значення.

Робота алгоритму:

На вхід подається абстрактне синтаксичне дерево. Ми розглядаємо усі пари піддерев, вони усі перевіряються в міру схожості (1.1). Та порівнюємо знайдено міру схожості з деякою константою (вводиться користувачем). Якщо міра схожості більше ніж константа, кажемо, що частки коду схожі.

де S, L та R — це кількість вузлів, які зустрічаються у обох, лівому та правом піддереві відповідно

1.3.2 Алгоритм Хескела

Для початку роботи алгоритму потрібно розбити коди програм на токенізованне представлення, а та b. Розіб'ємо рядки a і b на k-грами (підрядки довжини k). Знайдемо ті k-грами, які зустрічаються в a і b тільки по одному разу. Для кожної такої пари перевіримо чи збігаються елементи рядків, безпосередньо що лежать над ними, якщо це так, то проведемо ту ж перевірку і для них і так далі, поки розбіжність не буде знайдено. Аналогічно для рядків, що лежать нижче відповідних k-грам. Отримуємо набір загальних непересічних підрядків a і b. Їх загальна довжина може служити мірою схожості програм відповідно a і b.

Недоліки алгоритму:

— можливість збіги токенізірованного представлення програм, але відсутності збігу у вихідних кодах програм;

— невелика кількість унікальних k-грамів у великих програмах, відповідно багато збігу, якій не містять в собі такі k-грами буде проігнорований;

— вставка в знайдений блок або зміна на семантично еквівалентний оператор в багатьох випадках буде призводити до ігнорування тієї частини блоку, в якій не міститься унікальний k-грам.

1.3.3 Алгоритм просівання для побудови міток

При пошуку спільних підрядків в файлах ми керуємося наступними умовами:

— Якщо довжина збігається підрядку, більше або дорівнює гарантованої довжині t, то збіг буде виявлено;

— Збігу коротше шумового порога k, ігноруються.

Пункт 2 забезпечений виділенням з тексту k-грамів. Чим більше k, тим менш імовірно, що збіги випадкові. Але із зростанням k падає стійкість методу до перестановок. У художніх текстах зазвичай за k беруть середню довжину стійких виразів.

Щоб задовольнити пункту 1 необхідно (і достатньо), щоб з кожних послідовно що йдуть (t — k + 1) хеш-значень хоча б одне було обрано в якості позначки. Ідея алгоритму наступна: просуваємо вікно розміру w = (t — k + 1) вздовж послідовності h1... hn, на кожному кроці вікно переміщається на одну позицію вправо. Призначаємо міткою мінімальне hj у вікні. Якщо в одному вікні два елементи приймають мінімальне значення, правий призначається UA. Проілюструємо цей процес для розглянутого вище прикладу для тексту abrakadabra, якому відповідає наступна послідовність хеш значень 12, 35, 78, 3, 26, 48, 55, 12, 35. Нехай нас цікавлять збіги довжини 4 і більше, тобто t = 4. Тоді w = (4 — 3 + 1) = 2, і вікна вийдуть: (12, 35), (35, 78), (78, 3), (3, 26), (26, 48), (48, 55), (55, 12), (12, 35). Для даного тексту підсумковий набір міток буде наступним: (12, 35, 3, 26, 48, 12). Як видно, вибір мітки визначається тільки вмістом вікна, такий алгоритм називається локальним. Будь-який локальний алгоритм вибору міток коректний. Дійсно, якщо в двох файлах є достатньо великий загальний підрядок, то будуть і однакові вікна, а значить, будуть призначені однакові позначки. За ним визначимо, що у файлах є збіги.

Показником ефективності алгоритму може служити щільність d — частка хеш-значень, вибраних як міток, серед всіх хеш-значень документа. Це можна показати, просіюванні d = 2 / (w +1).

Для файлів обчислюються набори міток. Будується загального покажчик, де кожній мітці співставлений файл і місто, де вона зустрічається. Звіривши мітки перевіряємого файлу з покажчиком, вибираємо файли, з якими виявлено найбільше число збігів. Інформацію про них видаємо.

Трудомісткість (кількість порівнянь) залежить від заданого користувачем рівня точності.

1.4 Постановка задачі

Метою цієї роботи є написання системи, яка б дозволяла автоматизувати виявленню плагіату в програмному коді. Система повинна бути легко масштабована та мати можливість перевіряти на плагіат на різних мовах програмування. На цей час в навчальних закладах найбільш поширені мови програмування Java, C# та С++. Також ці мови користуються попитом в фірмах, які розробляють програмні продукти. Тому було прийнято рішення зробити перевірку на плагіат саме на цих мовах програмування.

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

Програма буде включати наступну функціональність:

— реалізувати видалення коментарів в кодах програм;

— реалізувати функціональність перетворення кодів програм в токенезіроване представлення цього коду;

— розробити xml-документ в якому будуть зберігатися оператори різних мов програмування;

— реалізувати алгоритм жадного строкового замощення;

— реалізувати алгоритм порівняння операторів;

— розробити можливість перевірки з накопиченою базою студентських робіт за весь час навчання;

— зробити висновок результату у зручній формі, результат повинен бути в html файлі.

2. Проектування та реалізація

2.1 Відомості про середовище розробки

Дана система була написана на мові програмування Java. На даний момент існує 3 найбільш стабільні середовища розробки на Java. Це Intellij Idea[10], Eclipse[11] та NetBeans[12]. Intellij Idea є хорошим середовищем розробки, але її недолік у тому, що вона платна. Eclipse і NetBeans приблизно однакової якості, і вибір між ними лежить вже на симпатіях розробника, хоча у Eclipse є невелика перевага у тому, що в неї більше плагінів. Плагін — незалежно компільований програмний модуль, що динамічно підключається до основної програми, призначений для розширення або використання її можливостей. Також може перекладатися як «модуль». Плагіни зазвичай виконуються у вигляді динамічних бібліотек.

У даній бакалаврській роботі вибір був зупинений на інтегрованому середовищі розробки Eclipse. Eclipse — вільне інтегроване середовище розробки модульних кроссплатформенних додатків. Розвивається і підтримується Eclipse Foundation. Найбільш відомі програми на основі Eclipse Platform — різні «Eclipse IDE» для розробки ПЗ на багатьох мовах (наприклад, найбільш популярний «Java IDE», підтримувався з самого початку, не покладається на будь-які закриті розширення, використовує стандартний відкритий API для доступу до Eclipse Platform).

Мова програмування Java була обрана з ряду причин. На Java можна писати кросплатформені додатки. Кросплатформені додатки — це додатки які працють більш ніж на одній апаратній платформі і / або операційній системі. На Java пишеться і підтримується велика кількість безкоштовних бібліотек. За допомогою цих бібліотек розробникам не потрібно придумувати свої рішення і витрачати на це час та сили, а можна відразу використовувати готове рішення написане професіоналами.

Java — об'єктно-орієнтована мова програмування, випущена компанією Sun Microsystems у 1995 році як основний компонент платформи Java. Синтаксис мови багато в чому походить від C та C++. У офіційній реалізації, Java програми компілюються у байткод, який при виконанні інтерпретується віртуальною машиною для конкретної платформи[13].

2.2 Побудова uml-діаграм

Для аналізу потоку подій в різних варіантах використання використовується діаграма діяльності[14]. Коли варіанти використання взаємодіють один з одним, на діаграмі діяльності зручно представити і проаналізувати їх потоки подій. Розробимо цю діаграму (див. рис. 2.1).

Рисунок 2.1 — Діаграма діяльності

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

На початкових етапах проектування потрібно визначити спільні кордони та контекст модельованої предметної області. Та треба сформулювати загальні вимоги до функціонального поведінки проектованої системи. Для цього використовують діаграму варіантів використання. Побудуємо діаграму варіантів використання (див. рис. 2.2).

Рисунок 2.2 — Діаграма варіантів використання Створювана система не потребує багатьох можливостей для варіантів використання, тому що основною метою розробки цієї системи є якість перевірки на плагіат. На діаграмі варіантів використання відображаються можливості актора «Teacher» в системі. На діаграмі ми можемо побачити, що складність використання системи не дужа важка, викладачу потрібно тільки вибрати мову програмування, файли для перевірки та визначити якими алгоритмами проводите перевірку, та він отримає результат.

2.3 Опис використовуваного підходу

Після огляду аналогів було виявлено, що кожна система написана з використанням всього 1 алгоритму. Цей підхід має недолік, при спробі обманути детектор плагіату, зловмисник може підлаштувати код програми під якийсь алгоритм. А якщо в системі буде декілька алгоритмів перевірки, то можливість обдурити таку систему, дуже мала.

В даній роботі булу вирішено використовувати алгоритм жадібного строкового замощення та алгоритм підрядкового порівняння.

Обидва алгоритму використовують приблизно однакову схему пошуку плагіату. Спочатку потрібно загрузити файли які перевіряються, потім потрібно позбавитися від коментарів в програмних кодах. Потім потрібно запустити парсер, щоб позбавитися від коду, який не впливає на роботу програми, цей процес називається токенізація. Потім токенізованне представлення проходить через алгоритм пошуку плагіату. У алгоритмів є коефіцієнт, якщо програми перевищуються цей коефіцієнт, то програма позначається плагіатом, та виводиться результат. Намалюємо цю схему (див. рис. 2.3).

Рисунок 2.3 — Схема пошуку плагіату

2.3.1 Видалення коментарів в коді

Для видалення коментарів в коді будемо використовувати регулярні вислови[16]. Регулярний вислів — це рядок що описує або збігається з множиною рядків, відповідно до набору спеціальних синтаксичних правил. Регулярні вислови використовуються в багатьох текстових редакторах та допоміжних інструментах для пошуку та зміни тексту на основі заданих шаблонів. Багато мов програмування підтримують регулярні вислови для роботи з рядками. Наприклад, Perl та Tcl мають потужний механізм для роботи з регулярними висловами, вбудований безпосередньо в їх синтаксис. Завдяки набору утиліт (включаючи редактор sed та фільтр grep), що входили до складу дистрибутивів Юнікс регулярні вислови стали відомими та поширеними[17]. В Java, C# та С++ для коментарів використовуються однакові коментарі. Це багаторядкові коментарі(див. рис. 2.4). Багаторядкові коментарі призначені для коментування 1 чи більш рядків.

Рисунок 2.4 — Приклад багаторядкового коментарю Також існують однорядкові коментарі. Які призначені для коментування тільки 1 рядка (див. рис. 2.5).

Рисунок 2.5 — Приклад однорядкового коментарю Для видалення напишемо 2 регулярних вислова. Для того, щоб регулярні вирази знаходили плагіат у всьому тексту, требо позначити, щоб використовувався режим dotall та global. У таблиці 2.1 наведені регулярні вирази для коментарів.

Таблиця 2.1 — Регулярні вирази для виділення коментарів в коді

2.3.2 Токенізація коду

Токенізація це подання програми у такому вигляді, щоб були проігноровані назви функцій, змінних, класів та інше. Тобто ми позбавляємо програму від частин коду, які ніяк не впливають на її функціональність. Але варто зауважити, що у кожної мови програмування своя лексика. Тому є необхідність для кожної мови програмування створювати свої набори операторів. Для збереження операторів найкраще підійде xml-документ. Для того щоб не було проблем з xml-документом створимо xsd-схему (див. рис. 2.6), яка буде перевіряти xml-документ на коректність. XML — мова розмітки, що фактично є звід загальних синтаксичних правил[18]. XML — текстовий формат, призначений для зберігання структурованих даних (замість існуючих файлів баз даних), для обміну інформацією між програмами, а також для створення на його основі більш спеціалізованих мов розмітки (наприклад, XHTML). XML є спрощеною підмножиною мови SGML.

Рисунок 2.6 — Xsd-схема На підставі xsd-схеми побудуємо xml-документ[19]. Фрагмент xml-документу наведен на рисунку 2.7. В цьому xml-документі коренем є «languages», який зберігає у себе всі оператори. В нього є дочірній елемент «language», в якому є атрибут «langname» який вказує мову, та в нього є дочірній елемент «operator» в якому зберігається назва оператору.

Рисунок 2.7 — Фрагмент xml-документу

2.3.3 Задіяні алгоритми

Алгоритм жадібного строкового замощення:

— на вхід приймається токенізірованне представлення двох програм;

— призначаємо всі токени в обох програмах непозначеними;

— вибираємо коефіцієнт мінімального збігу підрядків;

— знаходимо найбільший загальний підрядок в непозначених токенах програм;

— якщо найбільший знайдений підрядок більше або дорівнює мінімального збігу підрядків, то повертаємося до пункту 4 та робимо токени позначеними;

— алгоритм виконується до тих пір поки найбільший знайдений підрядок не буде менше мінімального коефіцієнта підрядків;

— на основі позначених токенів визначаємо процент збігу програм, якщо цей збіг більше ніж 40% то помічаємо файли на наявність плагіата.

Алгоритм порівняння операторів:

Перший токен однієї послідовності порівнюється з першим токеном іншої послідовності. Якщо токени однакові, то лічильник збігів збільшується на одиницю. Далі беруться другі токени, порівнюються, і при збігу лічильник знову збільшуються. Цей процес продовжується до тих пір, поки не будуть обрані всі токени. У тому випадку, коли довжини послідовностей різні, порівняння виконується по довжині більш короткої послідовності. Після того, як всі токени обрані, кількість збігів запам’ятовується, а потім проводиться повторне порівняння, але перед цим більш коротка послідовність зрушується так, що її перший токен порівнюється з другим токеном довшої, другий — з третім, і так далі. Коли буде отримано ще одне число, що характеризує кількість збігів, воно також запам’ятовується, одна з послідовностей знову зсувається, знову проводиться порівняння, і так до тих пір, поки більш коротка послідовність не зрушиться циклічно стільки разів, скільки токенів в більш довгої послідовності. Після повної перевірки рахується процент збігу програм.

2.3.4 Генерація звіту перевірки плагіату

Після роботи алгоритмів, ми маємо процент плагіату в кодах програм. Але тільки процент це дуже мало інформації, тому що жоден автоматизований алгоритм не гарантує, що в кодах програм точно присутній плагіат. В зв’язку з цим потрібно виводити на екран результат перевірки, так, щоб користувач мав змогу одразу побачити частки коду, де присутній плагіат.

Для розробки звіту, було прийнято рішення використовувати html формат. Тому що, в цьому форматі ми маємо змогу легко розробляти таблиці та проводити різні операції над шрифтом[20].

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

2.4 Опис архітектури

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

В даній системі було прийнято рішення використовувати сервіс-орієнтована архітектуру. Сервіс-орієнтована архітектура — це модульний підхід до розробки програмного забезпечення, заснований на використанні сервісів (служб) зі стандартизованими інтерфейсами. В основі сервіс-орієнтованої архітектуру лежать принципи багатократного використання функціональних елементів інформаційних технологій, ліквідації дублювання функціональності в ПЗ, уніфікації типових операційних процесів, забезпечення переведення операційної моделі компанії на централізовані процеси і функціональну організацію на основі промислової платформи інтеграції. Компоненти програми можуть бути розподілені по різних вузлах мережі, і пропонуються як незалежні, слабо пов’язані, замінні сервіси-додатки. Програмні комплекси, розроблені відповідно до сервіс-орієнтованої архітектури, часто реалізуються як набір веб-сервісів, інтегрованих за допомогою відомих стандартних протоколів

Інтерфейс компонентів сервіс-орієнтовананих програм надає інкапсуляцію деталей реалізації конкретного компонента від інших компонентів. Таким чином, сервіс-орієнтована архітектура надає гнучкий та елегантний спосіб комбінування і багаторазового використання компонентів для побудови складних розподілених програмних комплексів.

В системі, що розробляється передбачені модулі:

— модуль підготовки кодів програм;

— модель перевірки на плагіат;

— модуль побудови звіту.

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

2.4.1 Опис модуля підготовки кодів програм

Цей модуль призначений для підготовки до перевірки програм на плагіат. Його основна мета, це загрузити у пам’ять програму, по заданій користувачем адресою, видалити коментарі в програмних кодах та перетворити всі програмні коди у токенізованний вид. На виході маємо токенізованне представлення програми. Структуру класів роботи модулю приведено на рисунку 2.8.

Рисунок 2.8 — Структура класів модуля підготовки кодів програм

Клас Tokenization має наступні методи:

— readFile — читає програму з диску;

— deleteComment — видаляє коментарі в програмі;

— makeList — перетворює програму в зручну форму для токенізації, та призначає кожної стоці програми номер, для подальшої індексації;

— selectOperator — вибирає з програми тільки оператори, які впливають на її працездатність та видаляє назви змінних, класів та інше;

— isOperator — перевіряє чи є дане слово оператором.

Клас Language має наступні методи:

— getInstance — реалізація патерна проектування Singlton, якщо даний клас, ще жодного разу не використовувався, з XML файлу зчитуються оператори вибраної мови програмування. Патерн використовується для того, щоб кожного разу не створювати нове підключення к XML-документу.

— getOperators — повертає оператори вибраної мови програмування.

Клас LanguageAnalyzer має наступні методи:

— getOperators — безпосередній розбір XML-документу з використанням DOM парсера;

— getOperator — повертає дочірній елемент в XML-документі по вказаній мові програмування.

2.4.2 Опис модуля перевірки на плагіат

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

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

В цьому модулі є головний клас Check, який відповідає за перенаправлення наборів токенів, які поступили до класу, в алгоритми перевірки вибрані користувачем. Алгоритми перевірки мають всього по 1 методу, в якому виконуються перевірка та повертають результат перевірки. Для зберігання результатів перевірки були написанні спеціальні класи.

Структуру класів роботи модулю приведено на рисунку 2.9.

Рисунок 2.9 — Структура класів модуля перевірки на плагіат Клас Check має наступні методи:

— scanCompareToken — запуск перевірки на плагіат алгоритмом порівняння операторів;

— scanGST — запуск перевірки на плагіат алгоритмом жадібного строкового замощення;

— startCheck — перевіряє, які алгоритми були обрані для перевірки та запускає потрібний алгоритми;

— isFileNotEmpty — перевіряє файл на порожнечу;

— getArrayFiles — вибирає зі сховища набір файлів з якими потрібно перевірити.

Клас GreedyStringTiling реалізує інтерфейс AlgorithmCheck та має наступний метод:

— startCheck — перевіряє 2 послідовності токенов на наявність плагіату.

Клас ResultGST має наступні властивості:

— firstTokens — зберігає послідовність токенів першої програми;

— secondTokens — зберігає послідовність токенов другої програми;

— startIndexFirst — індекс з якого починається збіг у першої послідовності програм;

— startIndexSecond — індекс з якого починається збіг у другої послідовності програм;

— count — кількість збігів у двох послідовностях.

Клас CompareToken реалізує інтерфейс AlgorithmCheck та має наступний метод:

— startCheck — перевіряє 2 послідовності токенов на наявність плагіату.

Клас ResultCompareToken має наступні властивості:

— firstIndex — індекс збігу у першої послідовності програм;

— secondIndex — індекс збігу у другої послідовності програм;

— operator — назва оператору який збігся.

2.4.3 Опис модуля побудови звіту

Модуль побудови звіту призначений для побудови звіту з перевірки в наочному вигляді, призначений для того щоб користувач системи міг одразу побачити частки коду, де передбачається наявність плагіату.

Структуру класів роботи модулю приведено на рисунку 2.10.

Рисунок 2.10 — Структура класів модуля побудови звіту Клас CreateHTML має наступні методи:

— createIndex — створює основну сторінку звіту;

— createAllCodeHTMLстворює сторінку звіту, де запозичений код виділяється червоним кольором;

— createBlockCodeHTML — створює сторінку звіту, де запозичений код розподілений по блокам;

— start — починаю побудову звіту.

Клас HTMLData має наступні властивості:

— blockView — зберігає текст, який призначений для блочного представлення;

— allCodeView — зберігає текст, який призначений для виводу усього коду;

— percent — зберігаю процент запозичення коду;

— firstFileName — зберігає им’я першого файлу;

— secondFileName — зберігаю им’я другого файлу.

3. Опис дослідної експлуатації

3.1 Загальні відомості

Даний програмний продукт був розроблений на мові Java, в інтегроване середовище розробки Eclipse.

Для запуску програми на комп’ютері повинна бути встановлена?? Java версії 1.5 або новіше. Для перегляду результатів, на комп’ютері повинен бути браузер.

3.2 Опис програмної реалізації

Інтерфейс розробленої програми не складний і інтуїтивно зрозумілий. Для перевірки на плагіат потрібно зайти в головне меню програми та обрати пункт «Plagiat detect». Після цього з’явиться вікно перевірки коду на плагіат (див. рис. 3.1).

В цьому вікні є всього 3 пункти яві потрібно заповнити:

— «Language» — в цьому видаючому списку потрібно обрати мову на якії потрібно перевіряти програму;

— «Path» — шляк до папки, де знаходяться файли для перевірки;

— «Algorithm» — треба вибрати алгоритм, за допомогою якого буде перевірятися код.

Рисунок 3.1 — Вибір мови програмування

Після того, як все буде заповнено потрібно натиснути на кнопку «start» почнеться перевірка та на головній формі з’явиться короткий результат з перевірки, та з’явиться кнопка «Report» для переходу в наочний аналіз знайденого плагіату (див. рис. 3.2). Детальний результат перевірки буде зберігатися у корені проекту у файлі «index.html».

Рисунок 3.2 — Вигляд основного ока після перевірки На головній формі, відображується кількість часу, яка була витрачена на пошук плагіату та час виконання пошуку. При натисканні на кнопку «Report» відкриється браузер по замовчуванням, в якому буде головна сторінка детального аналізу перевірки (див. рис. 3.3). На цій сторінці ми маємо змогу Рисунок 3.3 — Детальний результат перевірки На головній сторінці результатів, ми маємо змогу обрати один з 2 видів перегляду результатів. При натисканні на кнопку «go», яка знаходиться в стовпці «All code» відкриється нова сторінка на котрій буде детальна перевірка з виділенням коду червоним кольором (див. рис. 3.4).

Рисунок 3.4 — Перегляд місць плагіату Також ми маємо змогу вибрати перегляд плагіату в блочному режимі для цього потрібно натиснути кнопку «go» в стовпці «Block code». В цьому режимі ми бачимо тільки підозрі на плагіат частки коду (див рис. 3.5).

Рисунок 3.5 — Перегляд місць плагіату в блочному режимі

Висновки

В ході виконання бакалаврської роботи був проведений аналіз багатьох алгоритмів по виявленню плагіату в кодах програм. Також була розроблена система, яка має дуже простий інтерфейс, який легко зрозумілий при першому використані програми. Також система має архітектуру, яка дозволяє легко масштабувати та змінювати функціональність системи.

Розроблений програмний продукт не поступається іншим детекторам плагіату в якості та швидкості перевірки. Його перевага перед іншими детекторами плагіату у тому, що всі існуючи системи пошуку плагіату показуються тільки процент плагіату. Але дана модель не максимально ефективна, тому що є можливості випадкового збігу, тому потрібно давати користувачеві можливість наочно побачити, в якій ділянці коду присутній плагіат. Що було й зроблено в даній системі.

На цей час в навчальних закладах найбільша увага націлена на мови програмування Java, С# та С++. Тому в даній роботі була реалізована можливість перевірки саме на цих язиках, хоча додавання перевірки нової мої програмування дуже просте. Треба лише додати в XML-документ оператори мови програмування та ключеві слова, та програма одразу зможе перевіряти на новій мові.

В ході виконання проекту було реалізовано:

— видалення коментарів з коду;

— токенізація коду;

— перевірка коду алгоритмом жадного строкового замощення;

— перевірка коду алгоритмом порівняння операторів;

— xml-документ в якому зберігаються ключеві слова та оператори, кожної мови програмування для якої здійснюється перевірка.

— розроблена xsd-схема;

— генерація звіту в формі html в блочному виді та в виді виділення запозичених часток коду іншим кольором.

Розробка даного програмного продукту не буде припинена, тому що є ідеї поліпшення роботи програми. Потрібно оптимізувати швидкість роботи та додати ще алгоритми для більш якісного пошуку плагіату.

У подальших планах розвитку, передбачається перевірка, яка буде здійснюватися не з накопиченої університетською базою, а з сховищами, які знаходяться в Інтернеті.

При розробці даного програмного продукту була використана мова програмування Java, за допомогою Eclipse IDE.

Перелік посилань

1. Обзор автоматических детекторов плагиата в программах [Электронный ресурс] / С.-Петерб. гос. ун-т, информационных технологий, механики и оптики, фак. компьютерных технологий — Режим доступа: www/ URL: http://rain.ifmo.ru/cat/data/theory/unsorted/plagiarism-2006/article.pdf — 20.05.2011 г. — Загл. с экрана.

2. Методы выявления плагиата в программировании [Электронный ресурс] / С. Иванчегло — Режим доступа: www/ URL: http://www.kv.by/index2000491105.htm — 20.05.2011 г. — Загл. с экрана.

3. Мартин Р. Чистый код: создание, анализ и рефакторинг [Текст] / Р. Мартин. — СПб: Питер, 2010. — 464 с.

4. Официальный сайт MOSS [Электронный ресурс] / Stanford University — Режим доступа: www/ URL: http://theory.stanford.edu/~aiken/moss/ - 20.05.2011 г. — Загл. с экрана.

5. Официальный сайт JPlag [Электронный ресурс] / University of Karlsruhe — Режим доступа: www/ URL: https://www.ipd.uni-karlsruhe.de/jplag/ - 20.05.2011 г. — Загл. с экрана.

6. Официальный сайт SID [Электронный ресурс] / Computer Science Department — Режим доступа: www/ URL http://genome.math.uwaterloo.ca/SID/ - 20.05.2011 г. — Загл. с экрана.

7. Хорстманн К. С., Корнелл Г., Тонкости программирования [Текст] / К. С. Хорстманн, Г. Корнелл — М.: Издательский дом «Вильямс», 2008. — 1168 с.

8. Эккель Б. Философия Java [Текст] / Б. Эккель — СПб: Питер, 2009. — 638 с.

9. Стелтинг С., Маасен О. Применение шаблонов Java[Текст] / С. Стелтинг, О. Маасен. — М.: Издательский дом «Вильямс», 2002. — 576 с.

10. IntelliJ IDEA [Электронный ресурс] / JetBrainsРежим доступа: www / URL: http://www.jetbrains.com/idea/ -20.05.2011 г. — Загл. с экрана.

11. Eclipse IDE [Электронный ресурс] / Eclipse Foundation — Режим доступа: www / URL: http://www.eclipse.org/- 20.05.2011 г. — Загл. с экрана.

12. NetBeans IDE [Электронный ресурс] / NetBeans Community — Режим доступа: www/ URL: http://netbeans.org/- 20.05.2011 г. — Загл. с экрана.

13. Ноутон П. Шилдт Г., Java-2 [Текст] / П. Ноутон, Г. Шилдт — СПб: Питер, 2000. — 1034 с.

14. Буч Г. Язык UML. Руководство пользователя [Текст] /Г. Буч, Д. Рамбо, А. Джекобсон — ДМК Пресс: Питер, 2004. — 432 c.

15. Фаулер М., Кендалл С. UML. Основы [Текст] / М. Фаулер, С. Кендалл. — СПб: Символ-Плюс, 2002. — 192 с.

16. Фридл Д. Регулярные выражения [Текст]/ Д. Фридл. — СПб.: Питер, 2001. — 352 с.

17. Смит Б. Методы и алгоритмы вычислений на строках[Текст]/Б. Смит. — М.: «Вильямс», 2006. — 496 с.

18. Хабибулин И. Ш. Самоучитель XML [Текст] / И. Ш. Хабибулин — СПб: Питер, 2003. — 336 с.

19. XML Schema Tutorial [Электронный ресурс] / Refsnes Data — Режим доступа: www / URL: http://www.w3schools.com/schema/default.asp -20.05.2011 г. — Загл. с экрана.

20. Макконнелл С. Совершенный код [Текст] / С. Макконнелл Пер. — М.: Издательско торговый дом «Русская Редакция»; СПб. Питер, 2005. — 896 с.

Додаток А

VISION/SCOPE DOCUMENT FOR A «Plag detector»

Програмна система оцінки плагіату програмного коду Підготовлен для:

Харвківський Національний Університет Радіоелектроніки Випускна кваліфікаційна робота бакалавра Понеділок, 30 Травень 2011

Версія 0.94

Підготовлен:

Кононов Ілля ПІ-07−4

[email protected]

Автори:

Доц. Шатовська Т.Б.

Кононов І.О.

РЕЦЕНЗІЯ ТА ТАБЛИЦЯ ЗМІН Таблиця А.1 — Записи про зміни

Таблиця А.2 — Рецензенти

КОРОТКИЙ ЗМІСТ Основна мета проекту: створити систему оцінки плагіату коду з метою поліпшення праці викладачів вузів, тим, що перевірка на запозичення коду у інших студентів буде автоматизована.

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

Ця ситуація дуже погано впливає на розвиток освіти в вузі та в країні вчасності. Якщо так буде складатися надалі, то рівень освіти буде падати. З цим треба боротися. Тому є потреба в системі, яка буде робити автоматичний пошук плагіату в кодах студентів.

Програмний продукт розробляється для застосування в вузах. На перших стадіях, цей продукт буде тестуватися в ХНУРЕ. Якщо продукт покращить рівень знань у студентів, то ми будемо пропонувати його іншим вузам України.