Диссертации утверждена распоряжением по нгу № от 200 г (стр. 5 из 9)

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

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

Перевод дерева в формат правил iptables.

Допустим, есть вершина N, и это не лист. Тогда одно из правил N является активным. Из-за того, что правила в вершине описывают состояние соединений именно в этой вершине, получить ЭВ, используемое для деления узла N можно так:

1. Найти, какое из правил активно в N;
2. Выписать значение этого правила для левого потомка N.

Условно обозначим данную операцию PrintSeparation(N). На втором шаге можно было бы использовать и правого потомка, это вопрос соглашения. В генераторе всегда используется левый. Хотя iptables не поддерживает древовидные структуры, есть возможность создавать пользовательские цепочки правил, с помощью чего деревья можно моделировать. Делается это следующим образом (на примере все того же узла N):

1. создается новая цепочка с уникальным именем C(N);
2. создается правило вида «если PrintSeparation(N), то перейти в цепочку C(N)».

Все соединения левого потомка N перейдут в цепочку C(N), а соединения правого потомка останутся в текущей цепочке — что и описывает деление вершины. Имя цепочки строится по шаблону «chain» + порядковый номер.

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

Приведем пример реального дерева правил и того, как оно переводится в набор команд iptables. Данные получены при обработке статистики, собранной на одном из сегментов локальной сети НГУ (подробнее см. главу о тестовых испытаниях системы).

Рисунок 1. Пример дерева.

На рисунке 1 изображено начало дерева. Смысл обозначений таков:

J₀: порт назначения меньше или равен 80;

J₁: получатель находится в любой из местных подсетей (внутренний адрес);

J₂: адрес отправителя равен 193.124.208.85.

А вот как выделенная жирным ветка дерева (J₀ → ¬J₁ → J₂) была переведена в команды iptables:

1: iptables -N chain1

2: iptables -A chain0 -p tcp --dport 1:80 -j chain1

3: iptables -N chain2

4: iptables -A chain1 -m set --set mset0 dst -j chain2

. . .

X: iptables -A chain1 -p tcp --dport 80 -s 193.124.208.85 -j chain_accept

. . .

Номера строк проставлены вручную для удобства, в настоящих командах их нет. Из фрагмента можно увидеть, во что преобразуются J₀, J₁ и J₂. J₀ описано в строке 2, J₁ — в строке 4. Как видно, все соединения, удовлетворяющие J₁, уходят в цепочку chain2 и там проходят дальнейшее деление. Соединения, не удовлетворяющие J₁, остаются в цепочке chain1. В строке X описано J₂, а также видно следствие того, что правило портов оказалось активным в листе. Было обнаружено, что все соединения в этом листе имеют порт назначения с номером 80, и этот факт отражен в командах iptables (хотя деления по данному параметру не было). О цепочке chain_accept будет рассказано в главе, посвященной структуре генерируемых правил. Сейчас важно лишь то, что в нее попадают все нормальные пакеты.

Далее мы разберем работу двух имеющихся на данный момент в системе правил, которые покрывают четыре свойства соединения: протокол, порт назначения, адреса отправителя и получателя. Станет понятно, почему в примере выше нигде нет проверок на порт отправителя, что скрывается за наименованием mset0, откуда берется адрес 192.124.208.85, и почему в строке X нет проверки на адрес назначения.

8 Правило портов и протоколов.

В некоторых протоколах портов нет, поэтому порты и протоколы в нашей системе реализованы в одном классе PortRule (больше подошло бы название ProtocolAndPortRule, но PortRule сложилось исторически). Проверка порта осуществляется только для порта назначения. В протоколе TCP порт отправления (порт на клиенте) задается случайным образом. Для UDP правила его задания оговариваются в спецификации протоколов прикладного уровня. В некоторых из них он также случаен. В других определяется, что клиент должен ждать ответа на том же порту, что и сервер, либо предлагаются более изощренные решения (например, системный сервис resolver протокола DNS или специальный сервис отображения портов в Sun RPC [10]). Общепринятого соглашения не существует, поэтому в текущей версии нашей системы UDP-порт на клиенте считается случайным (как и TCP-порт).

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

Работа метода PortRule::compute заключается в следующем. Устанавливается, скольким различным протоколам принадлежат переданные соединения. Если протоколов несколько, то деление проходит по ним. Для каждого протокола подсчитывается, каков суммарный вес соединений, соответствующих ему. В качестве ЭВ выступает выражение

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

Если протокол один, и он поддерживает порты (TCP или UDP), то деление происходит по портам. ЭВ тогда имеет вид

. Это не каноническая форма ЭВ, т.к. есть конъюнкция. Но она необходима, потому что в правиле iptables нельзя задать значение порта, не задав перед этим значение протокола (что логично). Для сокращения перебора в качестве кандидатов на выступают только те номера портов, которые встречаются во множестве. Это дает существенное ускорение работы, ведь пространство значений параметра велико (в худшем случае 2¹⁶ вариантов), в то же время почти всегда используется гораздо меньше различных портов. Для каждого кандидата запоминается, каков суммарный вес соединений, имеющих порты, меньше или равные ему. Наилучшее деление будет обеспечивать тот порт, у которого этот параметр максимален (иногда это — не единственное возможное решение, но всегда один из равноценных вариантов).

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

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