Алгоритм, архитектура и реализация потокового фильтра дубликатов IP пакетов в системах сбора и обработки IP статистики

Алгоритм, архитектура и реализация потокового фильтра дубликатов 1Р пакетов в системах сбора и обработки 1Р

статистики.

Коноплев В.В., Назиров Р.Р., Боярский М.Н.

Институт Космических Исследований РАН

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

Данная работа выполнена при финансировании Российским Фондом Фундаментальных Исследований.

1. Введение

Необходимость учета детализированной статистики IP трафика обладает первостепенной важностью при мониторинге и планировании телекоммуникационной сети. Для реализации данной функции производители телекоммуникационного оборудования предлагают разнообразные сервисы, интегрированные в сетевые устройства. Примером могут быть функции "IP accounting" и "Netflow switching", реализованные в операционных системах маршрутизаторов фирмы "Cisco Systems".

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

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

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

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

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

разработчиков. Типичный пример: сервис "IP accounting" маршрутизаторов "Cisco Systems" не дает информации о портах сетевых соединений.

Ряд вышеизложенных причин приводит к необходимости самостоятельной разработки подсистем сбора "сырой статистики". Наиболее просто это реализуется в средах множественного доступа Ethernet/FastEthernet, где нет необходимости физически врезаться в соединение. В данном случае сетевой интерфейс вводится в режим приема всех пакетов (promiscuous mode) на сегменте, и специальная программа считывает, обрабатывает и агрегирует заголовки принимаемых пакетов.

Операционная система UNIX, как платформа, выбранная для реализации предлагаемого фильтра, имеет широкие возможности по перехвату и анализу трафика на сетевых интерфейсах. Программная компонента, собирающая пакетные заголовки с интерфейсов, как правило, реализуется в виде драйвера устройства и называется пакетным фильтром. Пакетный фильтр производит первичную фильтрацию пакетов (в случае если интересует только некоторая часть трафика) и передачу их на уровень пользователя анализирующему приложению. Для различных клонов системы UNIX разработаны свои версии пакетных фильтров. Сюда входят: NIT для SunOS, "Ultrix Packet Filter" для ОС Ultrix, Snoop для ОС IRIX. Следует особо отметить фильтр BPF, разработанный в институте Беркли [1], который по результатам тестирования значительно превосходит свои аналоги в производительности.

Что касается анализирующего приложения, то здесь можно выделить пакет NeTraMet&NeMaC [3],[4], опирающийся на стандартизованную архитектуру сбора подсчета сетевого трафика по потокам (RFC2063 и RFC2123) и имеющий гибкие возможности по его обработке и агрегированию.

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

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

Попробуем оценить вычислительные затраты на данную операцию. Пусть мы имеем дело с одним сегментом Ethernet. Если предполагаемая частота поступления пакетов ~1000 Pckt/sec, то при вероятном времени получения дубликата 5 секунд размер буфера оценивается в 1000 Pckt/s * 5 sec = 5000 pckts. Операция поиска дубликата в данном буфере должна производится с частотой 1000 раз в секунду. Легко представить себе вычислительные затраты на данную операцию даже при таких скромных требованиях как один сегмент Ethernet.

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

2. Описание работы фильтра.

Для описания алгоритма работы фильтра введем понятие точки перехвата пакетов. Это некоторая абстракция идентифицирующая место, откуда поступают данные. Понятие точки перехвата несколько шире чем просто номер интерфейса, считывающего заголовки пакетов. В данном случае к номеру интерфейса добавляются еще MAC адреса источника и получателя. Таким образом, наборы с одинаковым значением номера интерфейса, но разными парами MAC адресов будут относиться к разным точкам перехвата. Рассмотрим конфигурацию измерительной системы как показано на рисунке 1. В данном случае маршруту пакета с некоторыми IP адресами источника и получателя будут соответствовать четыре точки перехвата, показанные стрелками: 1, 2, 3 и 4. При этом точки перехвата 2 и 3 принадлежат одному сегменту и соответствуют случаю перенаправления между маршрутизаторами.

При обрабокте четрырех дубликатов, на выходе фильра, вместо четырех копий пакета будет одна комбинированая. В ней в качестве MAC адреса источника используется адрес из первой точки, MAC адрес получателя заменен на MAC адрес из последней точки, а номер интерфейса заменяется побитно закодированой парой интефейсов первой и поледней точек. Таким образом, маршрут 1-2-3-4 заменяется на эффективный 5.

N Packet Head

Рисунок 1. Пояснение работы фильтра.

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

Фильтр в ходе работы агрегирует трафик в сетевые потоки по парам IP аресов (источник и получатель) и для каждого такого потока хранит последовательность упорядоченых точек перехвата, в которых встретились принадлежащие потоку пакеты.

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

Тт >> Tp

Здесь: Тт - время жизни маршрута, а Tp - время ожидания дубликата.

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

Ограничения модели

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

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

Механизм упорядочения точек перехвата

Самый простой способ, упорядочивать точки по мере их создания, предполагая, что те точки, через которые пакеты проходят раньше, создаваться будут тоже раньше. Данное предположение неверно, поскольку фильтр может начать работу в произвольный момент времени. Если пакет идущий по маршруту 1-2-3-4 (рис. 1) мы застанем в данный момент в точке 3, то она окажется первой в списке. Кроме того, фильтр должен адаптироваться к изменениям маршрутов во времени.

В предлагаемой модели упорядочение точек перехвата производится на основании оценки значения веремени жизни пакетов TTL. Действительно, для каждого пакета оно будет уменьшаться от сегмента к сегменту. Оценка параметра TTL для каждой точки перехвата в потоке производится по формуле:

TTLk = K * (TTLk-1+TTL), где K ~ 0.9 % 0.99

3. Архитектура и алгоритм

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

Таблица потоков необходима для регистрации и упорядочения точек перехвата.

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

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

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

1 . Все четыре дубликата последовательно попадут в буфер и создадутся четыре точки перехвата.

2. При извлечении первого дубликата из буфера он поступит на выход фильтра с пересчитанными компонентами

3. Одновременно удалится первая точка перехвата, поскольку пакетов для нее в буфере уже не осталось.

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

5. Аналогично для дубликатов 3 и 4.

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

Работа фильтра представлена тремя основными операциями:

1. Запись пакета в буфер. При этом выполняются:

SrclpAddr

DstlpAddr

SrcMACAddr

DstMACAddr

LastTime

PktHead

Int

SrcInt DstInt TimeStamp

IP адрес источника

IP адрес получателя

MAC адрес источника

MAC адрес получателя

Время последнего прошедшего пакета.

Заголовок пакета со временем поступления в буфер.

Номер интерфейса

Интерфейс источника

Интерфейс получателя

Время перехвата пакета

• Поиск со вставкой соответствущего сетевого потока.

• Поиск со вставкой соответсвующей точки перехвата.

• Увеличение значения Childs для данной точки.

• Пересчет среднего времени TTL для данной точки.

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

2. Перемещение заголовка пакета из первой половины буфера во вторую.

• Поверяется, относится ли заголовок к первой точке перехвата.

• Если да, то он поступает на выход фильтра с пересчитанными эффективными компонентами.

3. Удаление заголовка пакета из второй половины буфера.

• Уменьшение значения Childs для данной точки.

• Удаление точки, если Childs = 0.

• Удаление потока, если удалена последняя точка.

Выбор параметров и оценка размеров буфера задержки

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

Тт >> Td >> Tp,

где Тт - время жизни маршрута, а Tp - время ожидания дубликата.

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

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

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

Рассамотрим случай, когда система имеет три точки подключения к ЛАН по FastEthernet. Частота передачи пакетов в одном сегменте FastEthernet при полной нагрузке порядка 1 0000 pckt/sec. Тогда частота поступления пакетов в буфер будет F = 3*10000 pckt/sec = 30000 pckt/sec. При длине заголовка пакета порядка L = 100 байт предполагаемый размер буфера будет:

S = F * L * Td = 30000 pckt/sec * 100 bytes/pckt * 2 * 5 sec = 30Mb.

Данная цифра является вполне приемлемой для текущих возможностей вычислительных систем.

Заголовок пакета

1пЪ SrcMACAddr DstMACAddr SrcIPAddr DstIPAddr ТТЬ

Обновление таблицы Запись в буфер

Рисунок 2. Блок-схема фильтра.

4. Реализация

Рассматриваемый фильтр реализован как модуль на языке C, для использования совместно с анализирующим программным пакетом "NeTraMe&NeMaC". В качестве платформы был была использована ОС LINUX.

Поиск потоков реализован с помощью хеш-таблицы с разрешением совпадений в последовательные саморганизующиеся цепочки [5].

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

• push - Поместить пакет в буфер задержки.

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

• proc - Переместить пакет из верхней очереди буфера в нижнюю и

обработать.

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

• delete - Удалить пакет из буфера задержки.

Для наглядной реализации работы данного фильтра он был вкомпилирован в популярную утилиту "tcpdump" [2].

В ходе эксперимента измерительная станция посылала icmp запросы на удаленный хост. Пакеты запросов перехватывались станцией в двух сегментах по пути следования (интерфейсы eth0 и eth1).

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

Для краткости длинные MAC адреса заменены на псевдонимы: MAC1 , MAC2, MAC3, MAC4.

#./tcpdump -n -e -q src host 194.85.221.227 and host 193.232.212.31 14:43:37.712417 eth0: MAC1 MAC2 98: 194.85.221.227 > 193.232.212.31: icmp 14:43:38.712607 eth1: MAC3 MAC4 102: 194.85.221.227 > 193.232.212.31: icmp 14:43:39.712409 eth0: MAC1 MAC2 98: 194.85.221.227 > 193.232.212.31: icmp 14:43:40.712504 eth1: MAC3 MAC4 102: 194.85.221.227 > 193.232.212.31: icmp 14:43:41.712385 eth0: MAC1 MAC2 98: 194.85.221.227 > 193.232.212.31: icmp 14:43:42.712480 eth1: MAC3 MAC4 102: 194.85.221.227 > 193.232.212.31: icmp 14:43:43.712388 eth0: MAC1 MAC2 98: 194.85.221.227 > 193.232.212.31: icmp FILTER OUT: 14:43:37.712417 [eth0,eth1] MAC1 MAC4 194.85.221.227 > 193.232.212.31 FILTER OUT: 14:43:38.712607 >> DROP

FILTER OUT: 14:43:39.712409 [eth0,eth1] MAC1 MAC4 194.85.221.227 > 193.232.212.31 14:43:44.712514 eth1: MAC3 MAC4 102: 194.85.221.227 > 193.232.212.31: icmp 14:43:45.712384 eth0: MAC1 MAC2 98: 194.85.221.227 > 193.232.212.31: icmp FILTER OUT: 14:43:40.712504 >> DROP

FILTER OUT: 14:43:41.712385 [eth0,eth1] MAC1 MAC4 194.85.221.227 > 193.232.212.31 14:43:46.712522 eth1: MAC3 MAC4 102: 194.85.221.227 > 193.232.212.31: icmp 14:43:47.712531 eth0: MAC1 MAC2 98: 194.85.221.227 > 193.232.212.31: icmp FILTER OUT: 14:43:42.712480 >> DROP

FILTER OUT: 14:43:43.712388 [eth0,eth1] MAC1 MAC4 194.85.221.227 > 193.232.212.31 14:43:48.712567 eth1: MAC3 MAC4 102: 194.85.221.227 > 193.232.212.31: icmp

Запросы посылались с периодом 1 секунда. Время задержки в каждой очереди фильтра было установлено равным 3 секунды.

Как видно, после трех секунд работы фильтр начинает обрабатывать пакеты в буфере. Пакеты, которые были получены с интерфейса eth0 (первый по пути следования), поступают на выход фильтра с пересчитанными адресными компонентами:

• eth0 ^ ^^й^М]

• МАС1 МАС2 ^ МАС1 МАС4

Пакеты, полученые с интерфейса eth1, сбрасываются фильтром.

5. Вопросы безопасности

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

• Скрытие собственного трафика.

• Эмуляция трафика атакуемого.

Скрытие собственного трафика

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

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

Эмуляция трафика атакуемого

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

• Будет посчитан трафик только реального источника.

• Будет посчитан только фиктивный трафик.

• Будет посчитан суммарный трафик как атакующего хоста, так и атакуемого.

Обнаружение атак с подменой IP адреса

Особенностью данного фильтра является возможность детектирования атак, с подменой сетевого адреса. Идея здесь заключается в том, начальное значение TTL посылаемых пакетов задается в стеке протоколов TCP/IP и, как правило, не используется приложениями. Тогда значение параметра TTL в пакетах, относящихся к одному сетевому потоку и одной точке перехвата должно быть одинаковым. Если данное условие не выполняется на относительно большом проценте пакетов для рассматриваемой точки, значит есть вероятность атаки.

7. Список литературы

1. S. McCanne, V. Jacobson. "The BSD packet filter: A new architecture to usel-level network code" / Lawrence Berkeley laboratory, Berkeley, CA, December 1992.

2. V. Jacobson, C. Leres, S. McCanne. "The tcpdump manual page" / Lawrence Berkeley laboratory, Berkeley, CA, September 1992.

3. N. Brownlee, C. Mills, and G. Ruth, "Traffic Flow Measurement: Architecture" / RFC 2063, The University of Auckland, Bolt Beranek and Newman Inc., GTE Laboratories, Inc, January 1997.

4. N. Brownlee. "Traffic Flow Measurement: Experiences with NeTraMet" / RFC2123, The University of Auckland, March 1997.

5. Д. Кнут. "Искусство программирования для ЭВМ. Том 3. Сортировка и поиск" / Мир, Москва, 1978.