Witam.
Przede mną wybór pracy inżynierskiej którą ma być jakaś aplikacja/system.
Zainteresował mnie temat dotyczący aplikacji wyszukującej plagiaty w kodach źródłowych programów. Ot i cała treść jak i zarazem opis ;] Temat wydaje się ciekawy i dosyć łatwy...no właśnie "łatwy"...i dlatego piszę tutaj żeby poznać opinię osób które z programowaniem mają już pewne doświadczenie. Szczególnie interesuje mnie poziom trudności takiej aplikacji i ewentualne rzeczy na które trzeba zwrócić uwagę podczas jej tworzenia.
Z programowaniem większych problemów nie mam ale nie chciałbym spędzić kilku tygodni szukając w internecie czy w książkach informacji tylko po to żeby wiedzieć od czego zacząć...a i takie tematy się zdarzają ;]
Z góry dziękuję za wszelkie opinie ;]
Program ma wykrywać plagiaty we wszystkich językach? Czy jakimś konkretnym?
tak jak napisałem temat i jego opis jest dosyć krótki :P
wg mnie będą to języki c/c++ java/c# może to na inżyniera wystarczy :D
zacznij od tokenizera a pozniej drzewo AST
Temat raczej średnio łatwy - parsowanie + jakis algorytm klasyfikacji / klasteryzacji, a na koniec mozesz miec fatalne wyniki bo akurat wybrany przez Ciebie algorytm słabo sobie radzi z takimi danymi...
Algorytmy wykrywania plagiatów są stosowane na Olimpiadach Informatycznych. ZTCP opierają się na Łańcuchach Markowa, ale szczegółów nie znam. Podobno radzą sobie ze zmianami nazw zmiennych, formatowania, a może nawet i języka - to ostatnie to tylko podejrzewam.
@up - nie chce mi się wierzyć żeby takie coś naprawdę działało - przecież przy, np. 5000 zgłoszeniach, któreś będą prawie identyczne bo ile różnych sposobów zapisu algorytmu można wymyślić (bo i tak jest tylko jeden, rzadko dwa, odpowiednio wydajny algorytm na który trzeba wpaść)..?
Wibowit napisał(a)
Algorytmy wykrywania plagiatów są stosowane na Olimpiadach Informatycznych. ZTCP opierają się na Łańcuchach Markowa, ale szczegółów nie znam. Podobno radzą sobie ze zmianami nazw zmiennych, formatowania [...]
Ze zmianami nazw czy formowania to sobie głupi parser radzi, zastosowania dla łańcuchów Markowa (i na cholerę z wielkiej piszesz, to nie nazwa własna) raczej nie widzę.
No ja na OI słyszałem od organizatorów, że mają taki program i jest on oparty na łańcuchach Markowa. Stosują go i do etapu pierwszego, czyli dla każdego i do kolejnych etapów. Na kolejnych etapach, czyli wtedy gdy pilnują i nie da się ściągać, program nie zgłosił żadnego fałszywego alarmu (tzn w tych etapach nie zgłosił żadnego plagiatu), więc można przyjąć, że jest skuteczny.
Skoro łańcuchy Markowa nadają się do generowania tekstu: http://en.wikipedia.org/wiki/Markov_chain#Markov_text_generators , to można je przetrenować na kodach źródłowych, a potem zmierzyć ich podobieństwo.
MSM:
Im trudniejsze zadanie tym bardziej rozwiązania będą się różnić od siebie. Tu nie chodzi tylko i wyłącznie o samą ideę wykorzystaną w algorytmie, ale także o styl pisania czy stosowane triki.
Takie systemy są i działają, choćby na głupim spoju. Studenci jednak opracowali listę kroków, po wykonaniu których szansa na wykrycie plagiatu spada niemal do zera (no chyba że ktoś jeszcze wziął ten sam kod i wykonał te same kroki):
- wszystkie pętle for zamieniamy na while
- wszystkie pętle while zamieniamy na for
- wszystkie iteracje od 0 do n zamieniamy na iteracje od n do 0 i na odwrót
- wszystko co w funkcji wklejamy bezpośrednio do kodu
- wydzielamy dowolne (choćby bezsensowne) fragmenty kodu do funkcji
- do funkcji, których naprawdę nie za bardzo jest jak wkleić do głównej części kodu - dodajemy argumenty, z którymi możemy jakieś bezsensowne operacje sobie porobić, a te sensowne argumenty możemy np. wyrzucić i użyć zmiennej globalnej :>
Antyplagiator używany na spoju porównuje (ponoć) kod wykonywalny programów, dlatego potrafi wykryć również plagiaty z różnych języków. Dlatego też nie ma żadnego znaczenia, czy zmienisz nazwy zmiennych i funcji - ważne jest, jakie instrukcje, w jakiej kolejności są powtarzane, w szczególności pętle, bo są charakterystyczne.
Całe to info pochodzi z plotek międzystudenckich :) Tak naprawdę to się nie obeznaję w temacie.
aurel napisał(a)
Antyplagiator używany na spoju porównuje (ponoć) kod wykonywalny programów, dlatego potrafi wykryć również plagiaty z różnych języków. Dlatego też nie ma żadnego znaczenia, czy zmienisz nazwy zmiennych i funcji - ważne jest, jakie instrukcje, w jakiej kolejności są powtarzane, w szczególności pętle, bo są charakterystyczne.
Szczególnie, że na SPOJ-u można używać języków skryptowych i dynamicznie kompilowanych opartych o VM. Używane kompilatory języków natywnych mają włączoną optymalizację i spore różnice w generatorach kodu, nie ma szans na to, żeby kod maszynowy odzwierciedlał w wystarczającym stopniu detale algorytmu.