Еще одним видом сетей с учителем являются байесовские или вероятностные сети. Это сети, чей принцип действия основан на байесовской статистике. Обычная статистика по заданной модели говорит, какова будет вероятность того или иного исхода. Байесова статистика зеркально отражает вопрос: правильность модели оценивается по имеющимся достоверным данным. В более общем плане, байесова статистика дает возможность оценивать плотность вероятности распределений параметров модели по имеющимся данным. Вероятностная сеть представляет собой реализацию методов ядерной аппроксимации оценки плотности, оформленных в виде нейронной сети. В отличае от персептрона, вероятностная сеть на выходе дает не принадлежность примера к какому-либо классу, а вероятность принадлежности к каждому из классов. Применение байесовских сетей к задаче обнаружения плагиата не найдено.

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

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

2.8 Жадное строковое замощение

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

Пусть Р и Т - представления сравниваемых текстовых файлов.

Определения:

1. MinimumMatchLength - минимальная длина наибольшего общего префикса строк Рр и Tt, при которой он учитывается алгоритмом;

2. Длина самого большого из пока найденных на текущей итерации алгоритма общих префиксов строк Рр и Tt обозначается MaxMatch;

3. Набор тайлов будет обозначаться как Tiles.

4. Множество, содержащее кандидаты на попадание в набор тайлов, обозначется Mathes.

Алгоритм можно разделить на две фазы:

1. Ищутся наибольшие общие подстроки Р и Т, состоящие только из непомеченных элементов (вначале алгоритма все элементы непомечены). Для этого используются три вложенных цикла: первый пробегает по всем возможным Рр, второй по всем Tt, а третий находит наибольший общий префикс Рр и Tt. Далее существует три варианта в зависимости от соотношения величин MaxMatch и найденного префикса:

1.1. если MaxMatch меньше, то мы удаляем из списка общих подстрок Matches все до этого добавленные и помещаем туда найденный префикс;

1.2. если MaxMatch больше, то ничего не меняем;

1.3. если они равны, то добавляем наибольший общий префикс Рр и Tt к списку Matches.

2. Просматривается список. Если текущий элемент списка - подстрока, не содержащая помеченных элементов, то она помещается в выходной набор Tiles (теперь эту подстроку называют Tile -- отсюда и название алгоритма), маркируются все элементы рассматриваемой строки, входящие в Р и Т. Если длины строк в списке (MaxMatch) больше MinimumMatchLength, то соуществляется переход к первой фазе.

Достоинства:

1. Общие подстроки меньшей длины, чем MinimumMatchLength, игнорируются, поэтому алгоритм не принимает в расчет небольшие случайно совпавшие области текста;

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

3. Алгоритм нечувствителен к перестановкам больших фрагментов кода. Недостатки:

1. Возможноть совпадения представлений текстовых файлов, но отсутствия совпадения в самих текстах;

2. Разбиение совпадения на блоки вставкой или заменой на похожий, каждый длиной меньшие MinimumMatchLength, ведет к полному игнорированию совпадения;

3. Из-за эвристик, используемых в алгоритме, совпадения, длиной меньшей чем MinimumMatchLength, будут проигнорированы.

2.9 Метод идентификационных меток

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

abracadabra, (он состоит из 11 символов; т = 11)

k-граммом называются любые k символов стоящих подряд. Построим всевозможные k-граммы для нашего текста при, например, k = 3:

abr, bra, гак, ака, kad, ada, dab, abr, bra

Количество k-граммов, которые можно построить для текста длины т обозначим п,

п = (т - (k - 1)) (в примере = 9)

Хешируются все k-граммы. Получившийся набор хеш-значений (h1.. hn) характеризует исходный документ. Для рассмотренного текста могла получиться, например, такая последовательность хеш-значений:

12, 35, 18, 3, 26, 48, 55, 12, 35

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

Чтобы выбрать те хеш-значения, которые будут представлять документ, используют следующие подходы:

1. Наивный подход - выбрать каждое i-тое из п значений. Однако, такой способ не устойчив к вставке и удалению символов, изменению их порядка (действительно, если добавить в начало файла 1 символ, позиции всех k-граммов сдвинутся, ни одна из меток нового файла со старыми не совпадет). Поэтому опираться на позицию внутри документа нельзя.

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

3. Манбер предложил выбирать в качестве меток только те хеш-значения, для которых h = 0 mod р, так останется только п/р меток (объем идентификационного набора для разных файлов будет отличаться, сами метки будут зависеть от содержимого файла). Однако, в этом случае расстояние между последовательно выбранными хеш-значениями не ограничено и может быть велико. В этом случае совпадения, оказавшиеся между метками, не будут учтены.

4. Метод просеивания (winnowing) не имеет этого недостатка. Алгоритм гарантирует, что если в двух файлах есть хотя бы одна достаточно длинная общая подстрока, то как минимум одна метка в их наборах совпадет.

Алгоритм просеивания для построения меток

При поиске общей подстроки в файлах руководствуются следующими условиями:

1. если длина совпадающей подстроки больше или равна гарантированной длине (guarantee threshold) t,то совпадение будет обнаружено;

2. совпадения короче шумового порога (noise threshold) k, игнорируются. (Параметры t и k задают в зависимости от необходимой точности). Пункт 2 обеспечен выделением из текста k-граммов. Чем больше k, тем менее вероятно, что совпадения случайны. Но с ростом k падает устойчивость метода к перестановкам. В художественных текстах обычно за k принимают среднюю длину устойчивых выражений.

Чтобы удовлетворить пункту 1 необходимо (и достаточно), чтобы из каждых последовательно идущих (t - k + 1) хеш-значений хотя бы одно было выбрано в качестве метки.

Идея алгоритма такова. Продвигается окно размера w = (t - к + 1) вдоль последовательности h1.. hn, на каждом шаге окно перемещается на одну позицию вправо. Назначаем меткой минимальное hj в окне. Если в одном окне два элемента принимают минимальное значение, правый назначается меткой.

Пример для выше рассмотренного процесса.

Тексту abracadabra соответствует последовательность хеш-значений:

12, 35, 78, 3, 26, 48, 55, 12, 35

Пусть интересуют совпадения длины 4 и более, т.е. t = 4. Тогда w = (4 - 3 + 1)= 2, и окна получатся

(12,35), (35, 78), (78, 3), (3, 26), (26,48), (48, 55), (55, 12), (12, 35)

Жирным выделены значения, назначенные метками. Для данного текста итоговый набор меток будет следующим:

(12, 35, 3, 26, 48, 12)

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

Показателем эффективности алгоритма может служить плотность d -- доля хеш-значений, выбранных в качестве меток, среди всех хеш-значений документа. Можно показать, что при просеивании d = 2/(w+l).

Достоинством данного алгоритма является его линейная трудоемкость. Количество сравнений зависит от заданного пользователем уровня точности.

2.10 Алгоритм Хескела

Представим два текстовых файла в виде строк a и b соответственно. Одним из критериев сходства строк считается длина их наибольшей общей подпоследовательности. Всегда можно найти такой элемент строки аi, что НОП строк a' = a|a|a|a|-1…aia1…ai-1 и b будет значительно меньше (максимум в два раза), чем НОП(а, b) (если НОП(а, b) > 1). Чтобы избежать этого явления можно воспользоваться алгоритмом сравнения строк Хескела, он требует нескольких проходов, но работает за линейное время. Разобьем строки а и b на k-граммы (подстроки длины k). Найдем те k-граммы, которые встречаются в а и b только по одному разу. Для каждой такой пары проверим совпадают ли элементы строк, непосредственно лежащие над ними; если это так, то проведем ту же проверку и для них и так далее, пока несовпадение не будет найдено. Аналогично для строк, лежащих ниже соответствующих k-граммов. Получаем набор общих непересекающихся подстрок а и b. Их общая длина может служить мерой схожести программ соответвующих а и b.

Достоинства:

1.Линейная трудоемкость (количество сравнений) алгоритма.

Недостатки:

1. Небольшое количество уникальных k-граммов в больших текстовых областях, соответственно, многие совпадения, не содержащие в себе таких k-граммов, будут проигнорированы;

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

Существует ещё ряд методов таких как Conceptual graph или Abstract Syntax tree и поиск на XML представлении. Но их применение целесообразно только в случае обнаружения плагиата в программах, поскольку вся информация, проверяемая на сходство, представляется в виде дерева. Во втором алгоритме описание хранится в XML формате.

Заключение

Стандартный алгоритм и нейросетевые методы обладают рядом существенных недостатков, чтобы их использовать. Алгоритмы Кнута-Морриса-Пратта и Бойера-Мура уже реализованы. Реализация метода идентификационных меток существует в похожей с разрабатываемой библиотекой обнаружения утечки конфиденциальной информации. После оценки достоинств и недостатков следующих методов: Жадное строковое замощение и алгоритм Хескела, на рассмотрение к реализации выбран алгоритм Хескела.

3 Постановка задачи

3.1. Целью проекта является предотвращение несанкционированного распространения конфиденциальной информации посредством документов. Для достижения данной цели необходимо:

3.1.1. Реализовать алгоритм, выбранный на основании аналитического обзора существующих методов сравнения текстовых файлов, поиска плагиата в передаваемом документе на языке С++;

3.1.2. Разработать модуль обнаружения утечки конфиденциальной информации на основании алгоритма поиска плагиата. Модуль будет представлен в виде библиотеки;

3.1.3. Разработать рекомендации по использованию библиотеки;

3.1.4. Разработать руководство программиста.

3.2. В качестве исходных данных, используемых для выполнения проекта, будут определены конфиденциальные и не конфиденциальные документы, представленные в виде текстовых файлов. На вход библиотеки будут поступать проверяемые на предмет плагиата документы.

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

Глава 2 Разработка алгоритма сравнения текстовых файлов

1 Выбор и обоснование алгоритма

На основании проведённого анализа представляется использовать следующий алгоритм оценки сходства документов - алгоритм сравнения строк Хескела, что повышает эффективность обнаружения утечки конфиденциальной информации. Данный алгоритм уже реализован в двух программах обнаружения плагиата исходных кодов программ. Этими программами являются следующие детекторы: Plague, YAP, которые построены по модели токенов.

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

2 Разработка алгоритма

Использовать алгоритм сравнения строк Хескела в разрабатываемом модуле обнаружения утечки информации в документах возможно по 2 двум различным схемам. Но их объединяют одинаковые типы данных, поступающих на вход библиотеки. К ним относятся 3 типа текстовых файлов: с конфиденциальной, не конфиденциальной и проверяемой информацией. Эти файлы представляются в виде строк. Рассмотрим две из них, например с конфиденциальной и не конфиденциальной информацией. Обозначим их a и b соответственно. В строках a и b из всех имеющихся символов сохраняются только буквы, пробелы и знаки препинания удаляются. Далее а и b разбиваются на подстроки длиной k (k-граммы). Целесообразно, чтобы минимальное количество символов в k-граммах было равно 3.

В качестве объяснения получения k-грамм рассмотрим текст: конфиденциальный, (он состоит из 16 символов; m = 16). K-граммой называются любые k символов стоящих подряд. Всевозможные k-граммы для рассматриваемого текста при, например, k = 5, строятся следующим образом: конфи, онфид, нфиде, фиден, иденц, денци, енциа, нциал, циаль, иальн, альны, льный. Количество k-граммов, которые можно построить для текста длиной m обозначаются n, n = (m - (k - 1)) (в примере n = 12). Чем больше, тем менее вероятно, что совпадения случайны. Но с ростом k-граммы падает устойчивость метода к перестановкам. В художественных текстах обычно за длину k-граммы принимают среднюю длину устойчивых выражений.

Возможно, что и в а, и в b, будут присутствовать дублирующиеся части, поэтому удаляются повторяющиеся наборы k-грамм в каждой строке. Сравнение строк a и b проводится следующим образом. Выполняется поиск пар уникальных k-грамм, т.е. тех которые встречаются в a и b только по одному разу. Для каждой пары проверяется, совпадают ли символы в k-граммах, которые располагаются над ними, затем сравнивается сама пара. Далее проводится проверка для k-грамм, лежащих ниже соответствующей пары. И так до тех пор, пока совпадение не будет найдено. В результате получается набор общих непересекающихся подстрок в a и b. Общие - т.е. присутствует сходство подстрок между a и b. Непересекающиеся - т.е. отсутствует сходство между подстроками каждой строки: a и b. Как раз для получения непересекающихся подстрок и проводилось удаление повторяющихся наборов k-грамм в каждой строке. Набор общих непересекающихся подстрок формируется для каждой строки: a и b. Их общая длина может служить мерой сходства документов соответствующих a и b.

Вторая схема вначале работает по тому же принципу, что и первая. Файлы также представляются в виде строк. Из всех имеющихся символов удаляются пробелы и знаки препинания, остаются только буквы. Проводится разбиение на k-граммы. Если присутствуют дублирующиеся части, то удаляются повторяющиеся наборы k-грамм в каждой строке. Далее алгоритм Хескела дополняется соответствующим образом. С использованием хеш-функции формируются списки сигнатур a и b, которые записываются в базу данных. С помощью такой функции происходит преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Хеш-функция также называется функцией свёртки, а ее результаты называют хешем, хеш-кодом или дайджестом сообщения. В разрабатываемом алгоритме хеши будут присваиваться каждой k-грамме. Хеш-коды не являются уникальными, поэтому если есть повторяющиеся k-граммы, то и хеши тоже совпадают. Одной из характеристик множества алгоритмов хеширования является разрядность. Рассмотрим следующие хеш-функции:

1. На выходе CRC-16 (контрольной суммы) - хеш-код, максимальный размер которого равен 16 бит или 2 байта, об этом свидетельствует имя хеш-функции;

2. На выходе MD5 - хеш-код, максимальный размер которого равен 128 бит или 16 байт;

3. На выходе SHA-1 - хеш-код, максимальный размер которого равен 160 бит или 20 байт.

Размер одного символа составляет 1 байт. Если длина k-граммы варьируется в диапазоне от 3 до 16 символов, то объему k-граммы соответствует диапазон от 3 до 16 байт. Выбор той или иной хеш-функции определяется спецификой решаемой задачи. Но в общем случае однозначного соответствия между исходными данными и хеш-кодом нет. Поэтому существует множество массивов данных, дающих одинаковые хеш-коды -- так называемые коллизии. Вероятность возникновения коллизий играет немаловажную роль в оценке «качества» хеш-функций. В связи с этим можно выбрать хеш-функцию с наименьшим объемом хеш-кода. В данном случае это контрольная сумма CRC-16. Каждой k-грамме будет присваиваться двухбайтовый хеш-код, будет происходить хеширование k-граммы по хеш-функции CRC-16.

CRC-16 или контрольная сумма - несложный, крайне быстрый и легко реализуемый алгоритм. Может использоваться в качестве защиты от непреднамеренных искажений. Платой за столь высокую скорость является легкая возможность подогнать сообщение под заранее известную сумму. Обычно разрядность контрольных сумм (типичное число: 32 бита) ниже, чем у таких хеш-функций как MD5 или SHA (типичные числа: 128, 160 и 256 бит), что означает возможность возникновения непреднамеренных коллизий. Простейшим случаем такого алгоритма является деление сообщения на 32- или 16-битные слова и их суммирование. Как правило, к такому алгоритму предъявляются требования отслеживания типичных ошибок, таких, как несколько подряд идущих ошибочных бит до заданной длины. Семейство алгоритмов т. н. «циклических избыточных кодов» удовлетворяет этим требованиям. К ним относится, например, CRC32.

В качестве применения хеширования можно использовать:

1. Сверку данных. В общем случае это применение можно описать, как проверка некоторой информации на идентичность оригиналу, без использования оригинала. Для сверки используется хеш-код проверяемой информации. Различают два основных направления этого применения:

1. Проверка на наличие ошибок. Например, контрольная сумма может быть передана по каналу связи вместе с основным текстом. На приёмном конце, контрольная сумма может быть рассчитана заново и её можно сравнить с переданным значением. Если будет обнаружено расхождение, то это значит, что при передаче возникли искажения и можно запросить повтор. Бытовым аналогом хеширования в данном случае может служить приём, когда при переездах в памяти держат количество мест багажа. Тогда для проверки не нужно вспоминать про каждую кладь, а достаточно их посчитать. Совпадение будет означать, что ни одна кладь не потеряна. То есть, количество мест багажа является его хеш-кодом;

2. Проверка парольной фразы. В большинстве случаев парольные фразы не хранятся на целевых объектах, хранятся лишь их хеш-коды. Хранить парольные фразы нецелесообразно, так как в случае несанкционированного доступа к файлу с фразами злоумышленник узнает все парольные фразы и сразу сможет ими воспользоваться, а при хранении хешей он узнает лишь хеши, которые не обратимы в исходные данные, в данном случае в парольную фразу. В ходе процедуры аутентификации вычисляется хеш-значение введённой парольной фразы, и сравнивается с сохранённым. Примером в данном случае могут служить ОС GNU/Linux и Microsoft Windows XP. В них хранятся лишь хеш-значения парольных фраз из учётных записей пользователей.

2. Ускорение поиска данных. Например, при записи текстовых полей в базе данных может рассчитываться их хеш-код и данные могут помещаться в раздел, соответствующий этому хеш-коду. Тогда при поиске данных надо будет сначала вычислить хеш-код текста и сразу станет известно, в каком разделе их надо искать, то есть, искать надо будет не по всей базе, а только по одному её разделу (это сильно ускоряет поиск). Бытовым аналогом хеширования в данном случае может служить помещение слов в словаре по алфавиту. Первая буква слова является его хеш-кодом, и при поиске просматривается не весь словарь, а только нужная буква.

После преобразования строк в сигнатуры проводится их сравнение следующим образом. Каждое хеш-значение строки a сравнивается с хеш-значением строки b. Количество совпавших комбинаций является мерой схожести документов. Для того, чтобы проверяемый файл был признан конфиденциальным и соответственно запрещенным к передаче, устанавливается пороговое значение количества схожих сравнений.

утечка информация конфиденциальный документ

2.1 Схема алгоритма

Схема 1



Схема 2

К шагу “Выполнение соответствующего действия” может относиться следующее:

1. Удаление сигнатур не конфиденциальных файлов из базы сигнатур конфиденциальных файлов. Процесс удаления будет подробно описан в главе 3, пункте 1;

2. Оповещение о конфиденциальности документа, которое сопровождается записью в журнал безопасности.

3 Выбор методики верификации

В качестве методики верификации экспериментальной системы обнаружения утечки информации было выбрано тестирование, результатом которого будет построение ROC-кривой.

ROC-кривая (Receiver Operator Characteristic - функциональные характеристики приемника) - кривая, которая наиболее часто используется для представления результатов бинарной классификации в машинном обучении. Название пришло из систем обработки сигналов. Поскольку классов два, один из них называется классом с положительными исходами, второй - с отрицательными исходами. ROC-кривая показывает зависимость количества верно классифицированных положительных примеров от количества неверно классифицированных отрицательных примеров. В терминологии ROC-анализа первые называются истинно положительным, вторые - ложно отрицательным множеством. При этом предполагается, что у классификатора имеется некоторый параметр, варьируя который, будет получаться то или иное разбиение на два класса. Этот параметр часто называют порогом, или точкой отсечения (cut-off value). В зависимости от него будут получаться различные величины ошибок I и II рода.

В логистической регрессии порог отсечения изменяется от 0 до 1 - это и есть расчетное значение уравнения регрессии. Будем называть его рейтингом.

Для понимания сути ошибок I и II рода рассмотрим четырехпольную таблицу сопряженности (confusion matrix), которая строится на основе результатов классификации моделью и фактической (объективной) принадлежностью примеров к классам.

Таблица 3.1 - Четырехпольная таблица сопряженности

Примеры маркируются как положительный (p), так и отрицательный (n). На выходе сопряженности возможны четыре случая:

1. Положительные примеры (р) (так называемые истинно положительные случаи) верно классифицированы (TP - True Positives);

2. Положительные примеры (р) классифицированы как отрицательные (ошибка I рода). Это так называемый "ложный пропуск" - когда интересующее нас событие ошибочно не обнаруживается (ложно отрицательные примеры) (FN - False Negatives);

3. Отрицательные примеры (n) (так называемые истинно отрицательные случаи) верно классифицированны (TN - True Negatives);

4. Отрицательные примеры (n) классифицированы как положительные (ошибка II рода). Это ложное обнаружение, т.к. при отсутствии события ошибочно выносится решение о его присутствии (ложно положительные случаи) (FP - False Positives).

Что является положительным событием, а что - отрицательным, зависит от конкретной задачи. В качестве примера можно продемонстрировать диагностический тест, который определяет наличие у человека болезни. В этом случае ложный пропуск происходит, когда по результатам теста человек здоров, но фактически болезнь есть (ошибка I рода). Ложное обнаружение происходит, когда у человека определяется болезнь, но фактически ее нет (ошибка II рода).

Все четыре случая: True Positives, False Negatives, True Negatives, False Positives - это количественные характеристики. Также рассчитываются относительные показатели - доли (rates):

1. Доля истинно положительных примеров среди всех положительных образцов (True Positives Rate), еще называется чувствительностью (Sensitivity): TPR=TP/(TP+FN);

2. Доля ложно положительных примеров среди всех отрицательных образцов (False Positives Rate): FPR=FP/(FP+TN), FPR=1-Sp, Sp - cпецифичность (или представительность -Specificity): Sp=TN/(TN+FP).

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

1. Чувствительный диагностический тест проявляется в гипердиагностике - максимальном предотвращении пропуска больных;

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

3.1 Построение ROC-кривой

ROC-кривая получается следующим образом:

1. Для каждого значения порога отсечения, которое меняется от 0 до 1 с шагом dx (например, 0.01) рассчитываются значения чувствительности Se и специфичности Sp. В качестве альтернативы порогом может являться каждое последующее значение примера в выборке;

2. По оси 0y откладывается чувствительность Se или TPR - доля истинно положительных примеров, по оси 0x - (1-представительность) (1-Sp) или FPR - доля ложно положительных случаев.

В результате получается некоторая кривая:

Рисунок 3.1 - ROC-кривая

График часто дополняют прямой f(x)=x. На рисунке 3.1 представлена ROC-кривая для идеального классификатора, так как график проходит через верхний левый угол, где доля истинно положительных случаев составляет 100% или 1.0 (идеальная чувствительность), а доля ложно положительных примеров равна нулю. Поэтому чем ближе кривая к верхнему левому углу, тем выше предсказательная способность модели. Чем меньше изгиб кривой и чем ближе она расположена к диагональной прямой, тем менее эффективна модель. Диагональная линия соответствует "бесполезному" классификатору, т.е. полной неразличимости двух классов.

Визуальный анализ ROC-кривой не всегда позволяет определить, насколько эффективна модель. Своеобразным методом такого определения является оценка площади под кривой. Теоретически она изменяется от 0 до 1.0, но, поскольку модель всегда характеризуются кривой, расположенной выше положительной диагонали, то обычно говорят об изменениях от 0.5 ("бесполезный" классификатор) до 1.0 ("идеальная" модель). Эта оценка может быть получена непосредственно вычислением площади под многогранником, ограниченным справа и снизу осями координат и слева вверху - экспериментально полученными точками (рисунок 3.3). Численный показатель площади под кривой называется AUC (Area Under Curve). Вычислить его можно, например, с помощью численного метода трапеций:



Рисунок 3.3 - Площадь под ROC-кривой

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

1. показатель AUC предназначен скорее для сравнительного анализа нескольких моделей;

2. AUC не содержит никакой информации о чувствительности и специфичности модели.

По следующей экспертной шкале для значений AUC можно судить о качестве модели:

Идеальная модель обладает 100% чувствительностью и специфичностью. Однако на практике добиться этого невозможно, более того, невозможно одновременно повысить и чувствительность, и специфичность модели. Компромисс находится с помощью порога отсечения, т.к. пороговое значение влияет на соотношение Se и Sp. Можно говорить о задаче нахождения оптимального порога отсечения (optimal cut-off value).

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

1. Требование минимальной величины чувствительности (специфичности) модели. Например, нужно обеспечить чувствительность теста не менее 80%. В этом случае оптимальным порогом будет максимальная специфичность (чувствительность), которая достигается при 80% (или значение, близкое к нему "справа" из-за дискретности ряда) чувствительности (специфичности);

2. Требование максимальной суммарной чувствительности и специфичности модели: Cut_offo=maxk(Sek+Spk);

3. Требование баланса между чувствительностью и специфичностью, в случае Se?Sp: Cut_offo=mink|Sek-Spk|.

Глава 3 Экспериментальное обоснование результатов исследования

1 Архитектура экспериментальной системы обнаружения утечки информации

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



Рисунок 3.1.1 - Архитектура экспериментальной системы

2 Технология проведения эксперимента

В основе проведения эксперимента над системой обнаружения утечки информации лежит технология построения ROC-кривой. Эта кривая будет построена по 14 точкам. Для расчета координат необходимы показатели, представленные в следующей таблице.

Таблица 3.2.1 - Четырехпольная таблица сопряженности

Это четырехпольная таблица сопряженности (confusion matrix), которая строится на основе результатов классификации моделью и фактической (объективной) принадлежностью примеров к классам.

Примеры классифицируются как положительный (p), так и отрицательный (n). На выходе сопряженности возможны четыре случая:

1. Положительные примеры (р) (так называемые истинно положительные случаи) верно классифицированы (TP - True Positives);

2. Положительные примеры (р) классифицированы как отрицательные (ошибка I рода). Это так называемый "ложный пропуск" - когда интересующее нас событие ошибочно не обнаруживается (ложно отрицательные примеры) (FN - False Negatives);

3. Отрицательные примеры (n) (так называемые истинно отрицательные случаи) верно классифицированны (TN - True Negatives);

4. Отрицательные примеры (n) классифицированы как положительные (ошибка II рода). Это ложное обнаружение, т.к. при отсутствии события ошибочно выносится решение о его присутствии (ложно положительные случаи) (FP - False Positives).

В этом случае положительным примером будут конфиденциальные файлы, а отрицательным - не конфиденциальные файлы. На базе фактических данных все показатели делятся на две группы:

1. Доля ложных обнаружений - характеризует ошибку II рода и означает, что не конфиденциальные файлы определились как конфиденциальные. Рассчитывается по формуле: FPR=FP/(FP+TN). При построении ROC-кривой является координатой точки по оси 0х;

2. Доля истинных обнаружений - означает, что конфиденциальные файлы определились как конфиденциальные, т.е. произошло правильное срабатывание. Рассчитывается по формуле: TPR=TP/(TP+FN). При построении ROC-кривой является координатой точки по оси 0y.

Возникновение ошибок I и II рода зависят от следующих критериев:

1. Особенность работы алгоритма - если разбивать строки на подстроки как можно большей длины (минимальная длина равна 3-м символам), то уменьшается вероятность ложного пропуска (конфиденциальные файлы определяются как не конфиденциальные), что является ошибкой I рода;

2. Особенность работы системы - в случае обновления базы конфиденциальных файлов информацией как конфиденциальной, так и не конфиденциальной, необходимо обновить и базу не конфиденциальных файлов, иначе возрастает вероятность ложного обнаружения. Т.е. не конфиденциальные файлы будут определяться как конфиденциальные. Это ошибка II рода.

Проверяемые файлы будут относится к двум классам - конфиденциальный и не конфиденциальный. В каждом классе будут по 150 файлов. Для меньшей вероятности возникновения ошибок I рода в алгоритме будет задаваться параметр разбиения на подстроки различной длины, начальное значение k=3 (подстрока из 3-х символов). В ходе проведения тестирования использовалась эмуляция ложных обнаружений. Для большей вероятности возникновения ошибок II рода - из базы не конфиденциальных файлов будет постепенно удаляться информация, в то время как в базе конфиденциальных файлов эта информация сохраняется.

3 Результаты тестирования

Изменение параметров выше рассмотренных критериев будет приводить к получению координат каждой из 14 точек.

1-я точка. Первоначальная длина k-граммы равна 3 символам. В базе не конфиденциальных файлов присутствует вся информация. После запуска программы была получена информация о подозреваемых документах, сохранившаяся в журнале безопасности (файл с расширением txt), на основе которой приведен следующий результат проверки:

1. Ни одного правильно обнаруженного конфиденциального файла, TP=0;

2. Абсолютный ложный пропуск, FN=150;

3. Все 150 не конфиденциальных файла правильно определились как не конфиденциальные, TN=150;

4. Ни одного ложно обнаруженного конфиденциального файла, FP=0.

Итак, все проверяемые файлы, фактически являющиеся конфиденциальными, определились как не конфиденциальные. Появилась ошибка I рода. В реальной системе проверяемый файл был бы разрешен к передаче. Все проверяемые файлы, фактически являющиеся не конфиденциальными, определились как не конфиденциальные.

TPR=0/150=0, Se=TPR=0, FPR=0/150=0, Sp=1-FPR=1

2-я точка. Длина k-граммы равна 4 символам. Из базы не конфиденциальных файлов удален 1 абзац.

Результат проверки документов:

1. 4 правильно обнаруженных конфиденциальных файла, TP=4;

2. 146 конфиденциальных файла определились как не конфиденциальные, FN=146;

3. 149 не конфиденциальных файла определились как не конфиденциальные, TN=149;

4. 1 ложно обнаруженный конфиденциальный файл, FP=1.

TPR=4/150=0,03, Se=TPR=0,03, FPR=1/150=0,01, Sp=1-FPR=0,99

3-я точка. Длина k-граммы равна 5 символам. Из базы не конфиденциальных файлов удалены 2 абзаца.

Результат проверки документов:

1. 11 правильно обнаруженных конфиденциальных файла, TP=11;

2. 139 конфиденциальных файла определились как не конфиденциальные, FN=139;

3. 147 не конфиденциальных файла определились как не конфиденциальные, TN=147;

4. 3 ложно обнаруженных конфиденциальных файла, FP=3.

TPR=11/150=0,07, Se=TPR=0,07, FPR=3/150=0,02, Sp=1-FPR=0,98

4-я точка. Длина k-граммы равна 6 символам. Из базы не конфиденциальных файлов удалены 4 абзаца.

Результат проверки документов:

1. 21 правильно обнаруженных конфиденциальных файла, TP=21;

2. 129 конфиденциальных файла определились как не конфиденциальные, FN=129;

3. 144 не конфиденциальных файла определились как не конфиденциальные, TN=144;

4. 6 ложно обнаруженных конфиденциальных файла, FP=6.

TPR=21/150=0,14, Se=TPR=0,14, FPR=6/150=0,04, Sp=1-FPR=0,96

5-я точка. Длина k-граммы равна 7 символам. Из базы не конфиденциальных файлов удалены 6 абзацев.

Результат проверки документов:

1. 36 правильно обнаруженных конфиденциальных файла, TP=36;

2. 114 конфиденциальных файла определились как не конфиденциальные, FN=114;

3. 140 не конфиденциальных файла определились как не конфиденциальные, TN=140;

4. 10 ложно обнаруженных конфиденциальных файла, FP=10.

TPR=36/150=0,24, Se=TPR=0,24, FPR=10/150=0,07, Sp=1-FPR=0,93

6-я точка. Длина k-граммы равна 8 символам. Из базы не конфиденциальных файлов удалены 8 абзацев.

Результат проверки документов:

1. 56 правильно обнаруженных конфиденциальных файла, TP=56;

2. 94 конфиденциальных файла определились как не конфиденциальные, FN=94;

3. 134 не конфиденциальных файла определились как не конфиденциальные, TN=134;

4. 16 ложно обнаруженных конфиденциальных файла, FP=16.

TPR=56/150=0,37, Se=TPR=0,37, FPR=16/150=0,11, Sp=1-FPR=0,89

7-я точка. Длина k-граммы равна 9 символам. Из базы не конфиденциальных файлов удалены 12 абзацев.

Результат проверки документов:

1. 71 правильно обнаруженных конфиденциальных файла, TP=71;

2. 79 конфиденциальных файла определились как не конфиденциальные, FN=79;

3. 126 не конфиденциальных файла определились как не конфиденциальные, TN=126;

4. 24 ложно обнаруженных конфиденциальных файла, FP=24.

TPR=71/150=0,47, Se=TPR=0,47, FPR=24/150=0,16, Sp=1-FPR=0,84

8-я точка. Длина k-граммы равна 10 символам. Из базы не конфиденциальных файлов удалены 16 абзацев.

Результат проверки документов:

1. 82 правильно обнаруженных конфиденциальных файла, TP=82;

2. 68 конфиденциальных файла определились как не конфиденциальные, FN=68;

3. 119 не конфиденциальных файла определились как не конфиденциальные, TN=119;

4. 31 ложно обнаруженных конфиденциальных файла, FP=31.

TPR=82/150=0,55, Se=TPR=0,55, FPR=31/150=0,26, Sp=1-FPR=0,74

9-я точка. Длина k-граммы равна 11 символам. Из базы не конфиденциальных файлов удалены 20 абзацев.

Результат проверки документов:

1. 89 правильно обнаруженных конфиденциальных файла, TP=89;

2. 61 конфиденциальных файла определились как не конфиденциальные, FN=61;

3. 107 не конфиденциальных файла определились как не конфиденциальные, TN=107;

4. 43 ложно обнаруженных конфиденциальных файла, FP=43.

TPR=89/150=0,59, Se=TPR=0,59, FPR=43/150=0,29, Sp=1-FPR=0,71

10-я точка. Длина k-граммы равна 12 символам. Из базы не конфиденциальных файлов удалены 25 абзацев.

Результат проверки документов:

1. 96 правильно обнаруженных конфиденциальных файла, TP=96;

2. 54 конфиденциальных файла определились как не конфиденциальные, FN=54;

3. 99 не конфиденциальных файла определились как не конфиденциальные, TN=99;

4. 51 ложно обнаруженных конфиденциальных файла, FP=51.

TPR=96/150=0,64, Se=TPR=0,64, FPR=51/150=0,34, Sp=1-FPR=0,66

11-я точка. Длина k-граммы равна 13 символам. Из базы не конфиденциальных файлов удалены 27 абзацев.

Результат проверки документов:

1. 103 правильно обнаруженных конфиденциальных файла, TP=103;

2. 47 конфиденциальных файла определились как не конфиденциальные, FN=47;

3. 90 не конфиденциальных файла определились как не конфиденциальные, TN=90;

4. 60 ложно обнаруженных конфиденциальных файла, FP=60.

TPR=103/150=0,69, Se=TPR=0,69, FPR=60/150=0,4, Sp=1-FPR=0,6

12-я точка. Длина k-граммы равна 14 символам. Из базы не конфиденциальных файлов удалены 32 абзаца.

Результат проверки документов:

1. 121 правильно обнаруженных конфиденциальных файла, TP=121;

2. 29 конфиденциальных файла определились как не конфиденциальные, FN=29;

3. 82 не конфиденциальных файла определились как не конфиденциальные, TN=82;

4. 68 ложно обнаруженных конфиденциальных файла, FP=68.

TPR=121/150=0,8, Se=TPR=0,8, FPR=68/150=0,45, Sp=1-FPR=0,55

13-я точка. Длина k-граммы равна 15 символам. Из базы не конфиденциальных файлов удалены 54 абзаца.

Результат проверки документов:

1. 136 правильно обнаруженных конфиденциальных файла, TP=136;

2. 14 конфиденциальных файла определились как не конфиденциальные, FN=14;

3. 49 не конфиденциальных файла определились как не конфиденциальные, TN=49;

4. 101 ложно обнаруженных конфиденциальных файла, FP=101.

TPR=136/150=0,91, Se=TPR=0,91, FPR=101/150=0,67, Sp=1-FPR=0,33

14-я точка. Длина k-граммы равна 16 символам. Из базы не конфиденциальных файлов удалены 75 абзацев.

Результат проверки документов:

1. 148 правильно обнаруженных конфиденциальных файла, TP=148;

2. 2 конфиденциальных файла определились как не конфиденциальные, FN=2;

3. 10 не конфиденциальных файла определились как не конфиденциальные, TN=10;

4. 140 ложно обнаруженных конфиденциальных файла, FP=140.

Итак, все проверяемые файлы, фактически являющиеся конфиденциальными, определились как конфиденциальные. Все проверяемые файлы, фактически являющиеся не конфиденциальными, определились как конфиденциальные. Появилась ошибка II рода. В реальной системе проверяемый файл был бы запрещен к передаче.

TPR=148/150=0,99, Se=TPR=0,99, FPR=140/150=0,93, Sp=1-FPR=0,07

По полученным точкам построена следующая ROC-кривая:

Рисунок 3.3.1 - Оценка эффективности обнаружения утечки информации

Для идеального классификатора график ROC-кривой проходит через верхний левый угол, где доля истинно положительных случаев составляет 100% или 1.0 (идеальная чувствительность), т.е. модель устойчива к возникновению ошибок I рода (ложных пропусков), а доля ложно положительных примеров равна нулю, т.е. устойчива к ошибкам II рода (ложных обнаружений). Чем меньше изгиб кривой и чем ближе она расположена к диагональной прямой, тем менее эффективна модель. Диагональная линия соответствует "бесполезному" классификатору, т.е. полной неразличимости двух классов. Данный график проходит между идеальной кривой и кривой неразличимости двух классов, но все же ближе к идеальной.

На основании проведенного тестирования получен массив точек, представленный в таблице “Чувствительность (доля истинных обнаружений) - Представительность”.

Таблица 3.3.1 - Чувствительность (доля истинных обнаружений) - Представительность

Порог	Se, %	Sp, %	Se + Sp	|Se - Sp|
0,075	0	100	0	0
0,15	3	99	102	96
0,225	7	98	105	91
0,3	14	96	110	82
0,375	24	93	117	69
0,45	37	89	126	52
0,525	47	84	131	37
0,6	55	74	129	19
0,675	59	71	130	12
0,75	64	66	130	02
0,825	69	60	129	09
0,9	80	55	135	25
0,975	91	33	124	58
1	99	7	106	92

Из таблицы 3.1 следует, что оптимальным порогом классификации, обеспечивающим максимум чувствительности и специфичности теста (или минимум ошибок I и II рода), является точка 0,9. В ней чувствительность равна 80%, что означает: 80% конфиденциальных файлов будут правильно определены как конфиденциальные. Специфичность равна 55%, следовательно, 55% файлов, которые являются не конфиденциальными, будут определены как не конфиденциальные.

Точкой баланса, в которой чувствительность и специфичность примерно совпадают, является 0,75.

Рисунок 3.3.2 - Площадь под ROC-кривой

Так как численный показатель площади под кривой - AUC = 0,778 (рисунок 3.2), то предсказательную способность системы обнаружения утечки конфиденциальной информации на основании экспертной шкалы можно охарактеризовать как хорошую.

Итак, разработанный модуль обнаружения утечки конфиденциальной информации в документах можно считать работоспособной и применять как средство интеграции в общую систему, так как величина ложного пропуска равна 1,3% (допустимое значение в пределах 1%) при длине k-граммы равной 16 символов, а ложного обнаружения - 0,7%. Данная величина ложного обнаружения получается, если не добавлен в базу не конфиденциальных файлов один абзац текста, который присутствует в базе конфиденциальных файлов. Такая ситуация может произойти по не внимательности.

4. Разработка рекомендаций по использованию разработанного алгоритма

4.1 Назначение и условия применения программы

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

1. to_upper - перевод буквы в верхний регистр для win-кодировки;

2. make_file_list - составление списка файлов по заданному пути;

3. input_file - ввод данных из файла в строку и составление списка хэш-кодов;

4. remove_repeats - удаление повторяющихся k-грамм;

5. remove_allowed - удаление не конфиденциальной информации из конфиденциальных файлов;

6. cmp_strings - сравнение содержимого проверяемого файла с конфиденциальным;

7. cmp_hashes - сравнение информации проверяемого файла с конфиденциальным;

8. Crc16 - функция, возвращающая двухбайтовый код;

9. init_hl - инициализация сервиса шифрования;

10. close_hl - завершение сервиса шифрования;

11. get_hash - получение хеш-кода;

12. main - инициализация библиотеки.

Условия необходимые для выполнения библиотеки:

1. PC-совместимая система;

2. Объем оперативной памяти - 15МБ и больше;

3. НМЖД объемом 500 КБ и больше;

4. Процессоры семейства Intel x86, а также IA-64, AMD64, PowerPC, ARM;

5. От используемого исполняемого файла зависит выбор операционной системы:

4.1. Ms Windows 95/98/МЕ/2000/ХР;

4.2. Операционная система Linux с дистрибутивами Slackware, Debian, Red Hat, Fedora, Mandriva, SuSE, Gentoo, Ubuntu.

4.2 Характеристика программы

К основным характеристикам и особенностям программы относятся:

1. Временная характеристика - при объеме всей информации в файлах равной 15КБ время работы составляет 2-3 с. Время работы программы будет возрастать на 1 с, в том случае, если объем информации увеличивается больше чем на 15КБ. График зависимости количества данных от времени выполнения программы будет больше приближен к оси 0х, что говорит о достаточной скорости работы;

2. Режим работы. Программа разработана в виде библиотеки и может быть встроена в системы с почтовыми серверами, где не требуется работы в консольном или графическом режиме. Настоящая реализация программы предполагает запуск исполняемого файла и сохранение отчета в файл;

3. Правильность выполнения. Ошибка ложного пропуска файла составляет 1,3%, ложного обнаружения - 0,7%.

4.3 Обращение к программе

При запуске исполняемого файла происходит обращение к функции main(), инициализирующей работу программы.

4.4 Входные и выходные данные

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

4.5 Сообщения

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

...