Время прочтения: 4 мин.

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

Алгоритм шинглов – это алгоритм поиска дубликатов и копий текстов в web-документе. В основе алгоритма лежит использование шинглов – последовательностей слов, которые сравниваются друг с другом. Так как перед сравнением тексты необходимо подготовить, алгоритм содержит несколько этапов:

  • приведение текста к единому виду (канонизация);
  • разбиение на группы по несколько символов (шинглы);
  • для ускорения процесса сравнения приведение групп к числовому формату (вычисление хэшей);
  • сравнение хэшей, определение результата.

На этапе канонизации текста убираются все союзы, знаки препинания, теги и прочие «зашумляющие» слова, в том числе и прилагательные.

Рис. 1 Пример канонизации текста

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

Рис. 2 Формирование шингла

Для сравнения шинглов можно применять разные методы, в частности для нашей задачи мы проверяли вхождение символов одного шингла в другой:

Рис. 3 Алгоритм сравнения

Практическое применение данного алгоритма использовалось нами при анализе компрометации учётных записей (УЗ), когда один пользователь входит под чужими данными. С точки зрения информационной безопасности это недопустимо. Казалось бы, задача проста: в журнале операций сравнить логин входа в операционную систему (ОС) и логин входа в АС, но есть и «подводные камни». К таким камням относятся многочисленные случаи, когда у сотрудника логин в ОС – 12-Habarov-SB, а в АС – KhabarovSB. Сравнивая две УЗ простым SQL-запросом такие случаи попадут в отклонения как факт компрометации. Однако, применяя алгоритм шинглов, можно исключить большинство подобных случаев. Например, в одной из проверок указанные выше функции (Рис. 1-3) использовались следующим образом. На вход подавался список из пар логинов сотрудника, взятых из логов входа в АС. Затем в цикле вызывались функции канонизации, генерации и сравнения шинглов (Рис 4).

Рис. 4 Применение алгоритма

В результате функция сравнения выдаёт процент схожести (Рис. 5). При проведении данной проверки порог схожести опытным путём был установлен в 70%. Все случаи, где процент схожести был ниже порогового значения, расценивались как компрометация учётной записи. Далее эти случаи дополнительно проверялись по системам контроля доступа и табелям учёта рабочего времени, и большинство из них было подтверждено. Сотрудники в период своего отсутствия передавали данные своих УЗ коллегам, что категорически запрещено. Таким образом, алгоритм шинглов, используемый совершенно в другой области деятельности, помог провести достаточно успешную проверку.

Рис. 5 Результат алгоритма

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