Wykrywanie klastrów „podobnych” kodów źródłowych

10

Załóżmy, że mam 400 studentów (na dużym uniwersytecie), którzy muszą wykonać projekt informatyczny i że muszą pracować samodzielnie (bez grupy studentów). Przykładem projektu może być „wdrożenie algorytmu szybkiej transformacji Fouriera w fortranie” (wiem, że to nie brzmi seksownie, ale to upraszcza moje pytanie). Jestem korektorem i chcę wysyłać procedury, aby sprawdzić, czy istnieją grupy studentów, które zaproponowały wdrożenie, które są „zbyt podobne, aby można je było naprawdę samodzielnie napisać”.

Jest to bez nadzoru wyszukiwanie klastrów. Myślę, że pytanie dotyczy raczej tego, które atrybuty użyć, a nie jakiego algorytmu klastrowania użyć. Pierwszą rzeczą, którą bym zrobił, to histogram litera po literze. Idealnie, ponieważ oszuści są mądrzejsi, w końcu spróbuję dobrze dobranych losowych kombinacji liter, aby sprawdzić, czy istnieje dobre dopasowanie histogramu litery (z permutacją). Również, że nie badają struktury kodu, tylko marginesowy rozkład liter ... jakie masz rozwiązanie? czy istnieje oprogramowanie lub pakiety dedykowane temu problemowi? (właściwie w dawnych czasach nauczyciele informatyki twierdzili, że mają tego typu narzędzie, ale teraz podejrzewam, że mieli coś bardzo prostego)

Wydaje mi się, że prawnik zajmujący się opracowywaniem oprogramowania ma tego typu problemy (nie z 1000 studentów, ale z 2 dużymi kodami ... co utrudnia sprawę)?

hypothesis-testing clustering Robin Girard
źródło

Odpowiedzi:

4

Oczywistym krokiem wstępnego przetwarzania jest scalenie plików, które są naprawdę identyczne.

Po tym kluczem jest normalizacja . W pewnym momencie uczniowie zaczną refaktoryzować kod, zmieniać nazwy zmiennych i tym podobne. Lub przeredaguj komentarze. Zbyt duży wpływ na to ma histogram literowy (a ponadto uchwyci on wiele właściwości języka).

Powszechną techniką jest użycie parsera specyficznego dla języka i przekształcenie kodu źródłowego w abstrakcyjne drzewo składniowe. Następnie wyodrębnij z tego funkcje. I może przeanalizować komentarze osobno równolegle.

Potem jest podejście oparte na linii „najdłuższe wspólne podsekwencje”. Jeśli masz dość dobre podobieństwo do pojedynczych wierszy, możesz wyszukać najdłuższą wspólną podsekwencję dowolnych dwóch plików. Spowoduje to również szereg dopasowań.

Ma ZAKOŃCZENIE - Anony-Mus
źródło
Chciałem tylko dodać, że najdłuższe wspólne podsekwencje można skutecznie znaleźć za pomocą drzewek sufiksów lub tablic sufiksów.
sebp
Dzięki Anony, naprawdę podoba mi się duch twojej odpowiedzi (i głosowałem za nią). To brzmi jak prawdziwe statystyki wielowymiarowe z „przekształcaniem danych” i wyszukiwaniem ekstremalnych wzorców. Jaką odległość byś postawił na tych drzewach?
robin girard
Nie jestem ekspertem od podobieństwa reprezentacji AST. Uważam, że istnieje pojęcie „symulacji” w tym sensie, że jedno drzewo jest szczególnym rodzajem poddrzewa drugiego. Myślę, że aby porównać AST, trzeba je wyrównać i policzyć względne różnice. Być może nie bierze pod uwagę kolejności gałęzi, więc trywialne porządkowanie kodu nie zmienia wyników. Należy pamiętać, że można dostać się do punktu, gdzie można uzyskać fałszywych alarmów, ponieważ nie tylko są n sposoby rozwiązywania problemu sprawnie, a otrzymasz fałszywych alarmów tylko dlatego, że znaleźli właściwe rozwiązanie ...
zrezygnował - anony-Mousse
0

Ze świata antyplagiatowego wcześniej spotkałem się z pojęciem „Graph Isomorphism”. Może też na to spojrzysz.

LCS - Możliwa jest także najdłuższa wspólna sekwencja. Ale spróbuj porównać wszystkie te rozwiązania i zobacz, co jest najlepsze :)

Ismi Najmi
źródło
Witamy na tej stronie! Czy możesz podać kilka odniesień do wyżej wspomnianej pracy, a może więcej szczegółów, aby czytelnicy mogli lepiej zrozumieć, w jaki sposób izomorfizm grafów lub LCS może rozwiązać dany problem?
chl