Диссертации утверждена распоряжением по нгу № от 200 г (стр. 6 из 9)
Сложность метода PortRule::compute может быть оценена как
, где u — количество уникальных портов в данном множестве, а n — его мощность. В худшем случае это 
. Но такая сложность достигается, только если каждое соединение во множестве имеет уникальный порт. Это редкая ситуация. Поэтому в большинстве случаев метод выполняется гораздо быстрее. Правило масок (класс MaskRule) описывает свойство принадлежности IP-адреса соединения определенному диапазону (поэтому правильнее было бы назвать его правилом адресов; еще одно не слишком удачное, но прочно закрепившееся название). В зависимости от настройки оно может обрабатывать как адрес отправителя, так и адрес получателя, представляя собой, фактически, два правила. Но нет никакой разницы в алгоритме работы, поэтому в дальнейшем мы будем ссылаться просто на адреса. Адрес соединения является свойством протокола IP, и поскольку выход за рамки семейства протоколов TCP/IP [10] не планируется (во всяком случае, в обозримом будущем), то считается, что IP-адрес есть у любого соединения.
Правило масок может проводить деление соединений, только опираясь на заданные вручную диапазоны адресов. Генерация новых диапазонов не предусмотрена. Это решение требует пояснения. Нет сомнений, что правило масок должно уметь отличать внутренний трафик от внешнего, а значит, информация о диапазонах адресов внутри локальной сети в любом случае необходима. Однако почему бы в дополнение к этим диапазонам не генерировать новые? Возможны два варианта их создания: они либо будут никак не связаны с заданными вручную, либо будут их конкретизировать (сужать). Первый вариант означает попытку эвристически разделить внешнюю сеть на сегменты. Это представляется неразрешимой задачей. Глобальная сеть функционирует по сложным законам, и IP-адреса ее элементов с точки зрения пользователей локальной сети можно считать случайными, не имеющими никакой структуры. Деление их на сегменты приведет к появлению множества бесполезных ветвлений в дереве правил. Внешние IP-адреса могут меняться, что приведет к появлению ложных сообщений об аномальном трафике. К тому же, мощность перебора, необходимого для решения этой задачи, очень велика. Никакой выгоды извлечь не удастся, зато мы получим существенный проигрыш по основным параметрам наборов правил — их количеству и скорости обработки соединений. Поэтому было принято решение никак не обрабатывать адреса, не лежащие ни в одном из заданных вручную диапазонов. Правило масок отключается в вершинах, которым приписаны только соединения с внешними адресами (ниже этот момент будет рассмотрен подробнее). Внешний трафик разбирается только по портам и протоколам.
Попытка конкретизировать диапазоны, заданные администратором, также не кажется хорошей идеей. Если внутри какого-то диапазона нет структуры, то незачем ее искать — это опять же приведет к разбуханию набора правил из-за бесполезных ветвлений и генерации ложных сообщений об аномальном трафике. Если же структура внутри диапазона имеется, то администратор должен сам ее задать. Он может это сделать, ведь структура адресов в локальных сетях почти всегда привязана к их физическому устройству и хорошо известна.
Однако если правило масок встречает множество, у всех соединений которого одинаковый адрес (например, А), и А лежит в одном из заданных диапазонов, то делается естественная конкретизация — вместо этого диапазона используется непосредственно адрес А. Вот откуда появился точный адрес 193.124.208.85 в примере, рассмотренном в главе об общей архитектуре генератора.
Конфигурация правила масок.
Описание структуры адресов локальной сети загружается из файла только при создании корневых правил для адресов отправителя и получателя. В дальнейшем обращения к конфигурации не происходит. По умолчанию берется файл masks.conf в директории, из которой запускается генератор. С помощью ключей командной строки можно задать другой источник. Это текстовый файл, содержащий отдельное описание диапазонов адресов отправителя и получателя. Его формат описан в приложении Б.
Поиск порогового значения.
Перед началом поиска порогового значения в методе MaskRule::compute неявно вводится дополнительный фиктивный диапазон Others, который по определению аккумулирует все адреса, не удовлетворяющие другим диапазонам. Далее делается проход по всем соединениям, и для каждого диапазона адресов (включая фиктивный) подсчитывается суммарный вес соединений, лежащих в нем. Следующим шагом из списка диапазонов удаляются те, вес которых равен нулю. Таким диапазонам не соответствует ни одного соединения, и они должны быть удалены, чтобы не тормозить работу правила.
Если после удаления нулевых диапазонов не осталось ничего, кроме Others — это признак того, что мы попали в вершину с чисто внешним трафиком, о которой говорилось выше. В этом случае правило масок отключается. Флаг отключения распространяется на клоны правила, т.е. идет дальше в поддереве, которое начинается в текущей вершине. Метод compute отключенного правила масок ничего не делает и всегда сообщает, что все пакеты прошли правило успешно, но деления найдено не было. Следует обратить внимание также на то, что правила масок для адресов отправителей и получателей — различные правила. Одно из них может быть отключено, а другое — продолжать функционировать. Благодаря этому успешно разбираются соединения с одним из адресов из внешней сети, а другим — из внутренней.
После того, как исключены все вырожденные случаи, происходит поиск деления. Фактически, имеется массив натуральных чисел (весов диапазонов), и нужно разделить его на две части, как можно меньше отличающиеся друг от друга по сумме. Задача при первом рассмотрении кажется эквивалентной задаче о суммах подмножеств, которая является NP-полной [14]. Но это не так. В нашем случае накладывается дополнительное ограничение, существенно упрощающее решение: одно из подмножеств, образованных в результате деления, должно целиком состоять из элемента(ов) с максимальным значением. Если это не выполняется, то средневзвешенное время прохождения пакетов через дерево правил не будет минимальным, ведь при делении в вершинах редкие соединения будут соседствовать с частыми. Но совсем упростить задачу — брать только один диапазон максимального веса, если таких больше трех — нельзя, потому что тогда соединения с равной частотой будут обрабатываться с применением существенно различного количества проверок.
Деление построено следующим образом. Ищется максимальное значение веса диапазона. В качестве ЭВ для деления используется выражение
. Если диапазон максимального веса всего один, то он является единственным элементом 
. Если таких диапазонов несколько, то в 
добавляется каждый второй из них. Дополнительно нужно проверить фиктивный диапазон Others. Он не может быть задан явно, а только методом исключения. Поэтому он не может быть частью порогового значения. Если диапазонов с максимальным весом несколько, и Others — лишь один из них, то мы просто не включаем его в 
, а включаем другие. Если же Others — единственный диапазон с максимальным весом, то составляется из всех остальных диапазонов, кроме него. Таким образом, мы как бы меняем ЭВ и его дополнение местами.Сложность метода MaskRule::compute оценивается как
, где n — это мощность множества соединений, а m — количество диапазонов (т.к. присутствует цикл по всем соединениям с вложенным циклом по всем диапазонам — когда мы вычисляем их вес). Можно считать, что 
. Это может не выполняться для некоторых вершин дерева, близких к листьям (когда осталось уже немного соединений), но для большинства вершин это однозначно верно, причем m во много раз меньше n. Таким образом, сложность правила масок, как и сложность правила портов не превышает (на самом деле, она гораздо меньше). Это подтверждает то, что общая сложность построения дерева правил не превышает 
. Необходимо сказать несколько слов о возможностях будущего улучшения алгоритма. Представляется разумным сравнивать вес диапазонов не точно, а допуская некоторую погрешность. Если мы имеем один диапазон максимальным весом 60 и несколько штук весом 59, то это, фактически, одна и та же частота. Уместно считать 60 и 59 равными весами. Однако точная величина допустимой погрешности неясна. Необходимо провести теоретические и практические исследования, чтобы понять, до какого момента выгодно закрывать глаза на разницу в весе диапазонов.