Здравствуйте ! Я не совсем уверен в том, что эта тема должна быть здесь, но тем не менее...
Задача состоит в том, что на входе подаются два текста некоторых программ (например, написанных на Паскале). Нам необходимо проверить, являются ли предложенные листинги программ разными, или же одна списана с другой. То есть, иначе: Равшан написал некоторую программу, а Джумшут взял и списал ее, при этом изменив в ней некоторые части (например, изменил имена переменных, порядок следования неключевых операторов). Наша задача - написать такую программу, которая могла бы определить, списал ли Джумшут программу у Равшана или написал сам.
Вопросы, которые наиболее значимы в этой задаче, это:
1)Как организовать процесс распознования в листинге не отдельных слов (типа for, while, print - то есть каких-нибудь опреаторов языка), а целых структур, которые они организовывают (например, распознать не просто оператор for, а некоторую абстрактную структуру "цикл") для того, чтобы сравнивать две разные программы именно по частоте вхождения структур ?
2)Где хранить подобные структуры (в виде чего) ?
3)Как правильно определять порог "списанности" задачи ? То есть, как необходимо считать кол-во совпадений в двух программах для конечного ответа на вопрос "Списано или нет" ?

И еще, данная программа будет в последствии написана на С++. По возможности, надо учитывать особенности языка. Спасибо большое за уделенное внимание !!!

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

Но если по простому, то можно преобразовать каждый текст в другой - каждое слово (из 4х-8байт) - это контрольная сумма текста на участке длиной, пусть 50 байт, и дальше надо только сравнить количество совпадений в двух текстах , в процентном отношении, и определить какой процент совпадений считать плагиатом (может он только один раз 50 байтовый кусок переписал ... или случайно совпало) и подобрать оптимальную ширину подсчёта (может не 50 а 20 байт оценивать).
Для надёжности можно сделать оценку с разной разбивкой (10,20,40,80... байт) вывести средний коэффициент и т.д.

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

Прежде чем думать как решить. Надо определить формально критерий списанная программа. 

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

На самом деле никому неохота сидеть и вручную исправлять текст ... но я бы (если надо) написал небольшую прогу ... или ,ещё проще, заменил в редакторе пробелы (4шт)) на знаки табуляции или наоборот.
Но это можно ликвидировать, если заставить программу ,при подсчёте контрольных сумм, игнорировать пробелы и знаки табуляции.
А от перестановки кусков текста местами может нарушиться смысл текста ... и для этого я и предложил делать "плавающий" (10, 20 , 40 ... ,байтовый) анализ (а может даже 2, 4 , 8 !) - результат может быть довольно надёжный.
Причём, "замаскированный" текст в такой разбивке будет выглядеть как скачки в проценте совпадений по разным разбивкам - что-то типа спектра - и тогда можно будет обнаружить попытки маскировки плагиата.

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

Анализ кода вещь слишком сложная и если ее решить то можно добиться гораздо большего чем выявления нерадивых студентов...
А для вашей задачи лучше подобрать критерии, т.е. признаки которые создаются по ходу выполнения программы:
1) В программе вводятся переменные под которые выделяется память, можно проследить последовательность ввода памяти. Получается что то типа частотной характеристики, которую можно считать как последовательностью, так и структурой (в проге было выделено память под int -- 10*4, под char -- 20*1,  и т.д.)... Т.е. у одинаковых программ будут совпадающий участки последовательности например 30% участка впаолне хватит или структура на 80% совпадает

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

А не создать ли нам опенсорс-проект по реализации этого безобразия  

Вы бы прежде чем проект делать написали определение что есть списаная программа. - формальное определение.


Иначы всё это напоминает профанацию которая никуда не уедет с мертвой точки

Если конечными перестановками блоков, фраз  и заменой имен можно получить из кода А код Б. И коды А и Б имеют одинаковую функциональность*, то программы А и Б назовем подобными.

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

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

ЗЫ: Чет формализм мне не свойственен... но попытку оставлю

Это сообщение отредактировал(а) dereyly - 6.12.2007, 04:57

Да. Мысль интересная. Действительно, если программа просто поверхностно замаскирована, то использование памяти будет практически таким же (ну разве что, плагиатчик может увеличить константы, отвечающие за размер выделяемых буферв). Это хороший критерий. Но полностью определить работу программы с памятью только лишь по синтаксису очень сложно (или, скорее, невозможно), так как часть операций выделения/освобождения может происходить в STL-контейнерах или в других сущностях. Вместо анализа синтаксиса можно написать свой менеджер памяти, который будет давать статистику (хотя, может, быть это умеет делать дебагерный софт вроде библиотеки efence).


Это сообщение отредактировал(а) SaDFromSpb - 8.12.2007, 15:25

Я просто хотел сказать что не надо анализировать код, а выделить из него какие нибудь критерии. Критериев можно нагенерить достаточно много 

Так же можно написать парсер, который упрощает структуру. Принцип парсера будет подобен простенькому компилятору (интерпретатору). Т.е. после анализа кода выдается последовательность
int,int;
char;
char;
int[];
new int[]:
Такую штуку можно попробовать сделать начиная от тривиальной замены переменной на ее тип. Можно с попутной интерпритаций, тогда можно проследить динамические переменные и связи.
Так же с помощью замены можно представить код как 
цикл{
int=int+const;
CString=conststring;
}

Хотя не так стройно получается

• 1 Спасибо большое всем отписавшимся за интересные идеи и мнения !
• 2 Формальный критерий списанности программы на данный момент:
  Программа считается списанной с другой программы в том случае, когда количество сходных частей в них превосходит некоторое заранее определенное число.
  примечания:
      - сходными частями называются некоторые ключевые слова (лексемы) в том случае, когда их количество и порядок следования в программе совпадает с количеством и порядком следования в исходной программе.
      - заранее определенное число задает пользователь программы, сопоставляющей две программы на предмет нахождения в них закономерностей (большее число обуславливает большее необходимое количество найденных сходных частей);
      - прошу заметить, что этот критерий определен только на данный момент (для формализации задачи) для того, чтобы его было легче поправить в правильном направлении, т.е. очевидно, что программа-сопоставитель в последствии должна уметь находить, например, некоторые особенности исходного автора на предмет нахождения аналогичных признаков в подозрительном листинге.
• 3 Отдельное спасибо dereyly за интересное предложение по мониторингу вводимой в область действия алгоритма памяти, хотя если честно, пока что не знаю какими именно средствами реализовывать подобный механизм. А вообще, прошу обратить внимание, что не смотря на то, что программа будет реализована на С++, но анализировать будет скорее всего не С++ листинги (советую сейчас просто абстрагироваться от конкретностей языков), а просто некоторого процедурного языка. Хотя не думаю, что это ключевое замечание в данном случае, но все же позволю себе сейчас маленькое ворчливое замечание, сказав, что принципиальные конструкции подобных языков программирования имеют одинаковую структуру пользования. Что, думаю, является вполне логичным заключением.
  4)Дабы избавить себе от роли исключительно ворчливого профонатора приведу здесь примерный алгоритм программы-сопоставителя лексических закономерностей в листингах двух программ.

определение библиотеки Лексем - ключевых слов
Создаем список, в который будем вносить по мере надобности те ключевые слова, которые мы будем считать ключевыми.
При этом в списке мы постараемся струкуризировать ключевые слова по принципу схожести выполнения операция (как например, операторы цикла - for и while) для того, чтобы в последствии мы могли присваивать одинаковый маркер подобным оператором.
Парсер
Создаем синтаксический анализатор.
Поочередно реализуем лексический анализатор (разбор строк на символы), а затем проводим грамматический анализ (выявление ключевых слов). 
Примечание: вообще говоря, обозначив всю эту функцию как парсер, мы обязались строить дерево разбора после грамматиеского анализа. Однако, пока что, я лично остановился на том, что программа создает выходную цепочку в виде списка кодовых замен лексем (ключевых слов). То есть различные знаки препенания и константы с переменными (идентификаторы) отсеиваются как мусор. 
Эвристика вхождений ключевых слов
Данная эвристика просто проверяет количество вхождений схожих частей в оба листинга и возвращает количество совпадений.
Очевидно, что это один из самых 'слабых' вариантов проверки списанности. Однако, для уточнения, я пока включили в программу и его. Вообще говоря, поскольку каждой эвристике можно задвать 'вес' ее значимости - этой я отвожу 20-ти процентную значимость от общего чилса эвристик (а данный момент их всего две).
Эвристика порядка следования
Эта проверка позволяет определить количество одинаковых вхождений двух подряд идущих ключевых операторов.
Вторая эвристика является более точной на мой взгляд на данный момент. Проверка идет не только по количеству лексем, но и по структурам связи (двоичным).
Главная функция - инициализатор
Функция, вызывающая основные компоненты работы и впоследствии дающая конечный результат - списана ли программа.
Как говорилось выше, в формальном определении списанности. Конкретное число будет влиять на критрей точности того, что мы называем списанной программой.

Спасибо за внимание !

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

P.S.
Списанность программ само по себе определение не точно. Приведу пример - на областную олимпиаду от школы отправили меня с другом из класса, задания естественно были одинаковы и после олимпиады было разрешено забрать свои исходники. Так вот, мы очень удивились, что одну и ту же задачу решили совершенно одинаково, т.е названия переменных естественно были другие, но последовательность обработки данных, алгоритм был как будто списан, но уверяю на 100% что списать было невозможно, нас даже рассадили в разные кабинеты (по фамилиям). Объяснение очень простое - у нас был один преподаватель