Методы повышения показателей качества фильтрации dlp-систем на основе предметно-ориентированной морфологической модели естественного языка

Необходимость 
разработки 
быстрого 
метода 
идентификации 
защищаемых данных в передаваемых сообщениях 
Для вынесения вердикта v (2.1.1) о возможности дальнейшей передачи 
сообщения необходимо определить, содержит ли оно хотя-бы один защищаемый 
факт I. Выявление защищаемых фактов в передаваемом сообщении производится 
после семантического анализа. Результатом семантического анализа, как правило, 
является граф, описывающий семантические объекты и связи между ними. 
Таким образом, на этапе после семантического анализа в анализаторе DLP-
системы имеется два графа – G
1
– граф, описывающий защищаемые данные, и G
2
– граф, описывающий передаваемое сообщение. Тогда для выявления угрозы 
утечки защищаемой информации необходимо решить задачу поиска изоморфизма 
графа G
2 
в G
1
.
По-видимому, первый анализ проблемы изоморфизма графов возникает в 
статье Р. Рида и Д. Корнейла (1977), с примечательным названием "Graph 
isomorphism disease". Приведенная в ней библиография из 36 работ и 
последующая библиография из ещё 32 работ содержат ссылки на большое число 
алгоритмов, которые по предположению их авторов, распознают изоморфизм 
произвольных графов за полиномиальное время. Однако, все эти предположения 
оказались несостоятельными. Наилучший результат к настоящему времени 
получен Л. Бабаи, Ю. Лаксом и В. Кантором (1983) и опирается на 
классификацию конечных простых групп. 

---

63 
В решении проблемы изоморфизма графов получены следующие результаты: 
Изоморфизм n-вершинных графов распознаваем за время 
(√ ) . 
Наилучший алгоритм, не использующий теорию групп, был построен М. 
Годбергом (1983) и имеет сложность 
. Упомянем здесь также, что 
наиболее быстрый с практической точки зрения алгоритм проверки изоморфизма 
графов принадлежит Б. Маккею и его реализация доступна на его домашней 
странице [38]. 
Достаточно быстрый алгортм описан в работе [39]. Его сложность 
варьируется от 
в лучшем случае до в худшем случае.