Тъй като в момента работя по софтуер за автоматизирано тестване на състезателни задачи на езика C#, ми дойде идеята да направя и модул, който да проверява за еднаквост на код в два C# файла, с което да мога да хващам преписвачите, които използват моята система. Разбира се, за да се хванат преписвачите, е необходимо решението на всеки да бъде сравнено с решението на всеки друг. Това е лесната част. Трудното е самото сравняване. Тук ще се опитам да опиша решенията, които открих и начина, по който намерих решение на проблема ;)
Най-сигурния начин за сравнение на еднаквост на алгоритми и на код е да се направи анализ на code-flow графа на програмата и да се търси чрез алгоритми за изоморфизъм на графи някакви съвпадения. Това най-просто казано е да се видят всички възможни изпълнения на програмата през кои инструкции от кода ще преминат и да се види дали за 2 програми тези възможни последователности от инструкции са еднакви. Анализа на code-flow-а на една програма обаче е сложна задача и изисква доста време. Има и по-лесни варианти, които изискват по-малко усилия и дават сравнително добри резултати.
Първият и най-лесен начин е да се сравнява просто текстът в кода за някаква еднаквост. Това означава, че ако има няколко реда с еднакъв код, програмата ще ги забележи и ще сметне кода за еднакъв. Това звучи лесно и удобно, обаче преписвачите са хитри. Те най-често ще сменят имена на променливи, или ще сменят последователността на изпълнението на кода, ще сменят константи, литерали, ще сменят реда на операторите и т.н. Затова просто сравнение на текст няма да хване преписвачите в големия процент от случаите.
Поразрових се в Интернет и открих няколко програмки, някои са създадени за проверка на еднаквост на текст, а други за проверка на еднаквост на код. Повечето добри от тях за съжаление са платени. От безплатните програми тази, която ми направи най-добро впечатление е Simian. Тя е безплатна за целите на безплатния софтуер и софтуера с отворен код. Справя се добре с проверката на еднакъв C# код, но има доста солидни пропуски, като например игнориране на имената на променливите в C# код. Допълнително Simian може да сравнява и чист текст.
Най-добрият начин за хващане на cheater-ите, който ми хрумна и който изглежда доста по-сигурен, е анализ на кода на приложението след като е преминало през компилатора. За целта първо всеки един от файловете за проверка се компилира с компилатора на C# (csc.exe). След като компилатора е произвел изпълним файл, този файл се декомпилира до IL код. Това става чрез програмата ILDASM (ildasm.exe), която е част от SDK-то на езика C#. Тази програма обръща всяко компилирано .NET асембли от изпълним файл в MSIL код. При компилация и след това декомпилация имената на private променливите се губят. Допълнително се губи смисъла на част от хитростите като смяна на последователността на някои оператори или смяна на for с while цикъл, добавяне на препроцесорни инструкции, добавяне на излишни коменатари и т.н. След като сме получили MSIL кода, вече можем да разчитаме че при сравнението му с друг MSIL код, шанса да хванем преписвачите е в пъти по-голям. Тук влиза в употреба и програмата Simian, само че пусната върху IL файловете, а не върху C# кода. Ето как изглежда резултатът от работата на програмта:
От тестовете, които направих, последния вариант (с анализа на IL кода) се оказа доста добър. В еднакъв код (със сменени имена на променливи и сменен цикъл while с неговия for аналог, сменени места на 1-2 оператора, с добавени коментари и излишни препроцесорни инструкции) Simian ми намери 142 еднакви реда от 176 анализирани, което е доста добре, имайки предвид усилията, които положих, за да направя кода различен. Разбира се може да се използва комбинация от анализ на C# кода и анализ на IL кода, но ми се струва, че анализа на IL кода дава достатъчно добри резултати. Скоростта на анализ е 0.227 секунди на добър процесор, а самото компилиране плюс декомпилиране също отнема известно време. Не е много бързо, но си заслужава.
If you have any questions, Google them with Bing :)