Потери производительности при выборочном подтверждении TCP

Среди обычных разговоров разработчиков Linux® в Интернете в последние месяцы довольно много
обсуждается реализация TCP SACK (выборочного подтверждения TCP) в Linux. Комментарии в основном касаются
производительности стека TCP при обработке отдельных событий SACK, и некоторые указывают
на наличие прорехи в безопасности.

Я был заинтригован этим обсуждением, но мне показалось, что в нем отсутствует конкретная информация.
О каких особых условиях идет речь? Это мелочь с точки зрения производительности или
реальная возможность DoS-атаки на сервер?

Я собрал несколько цитат на эту тему (ссылки на источники см. в разделе «Ресурсы»:

Дэвид Миллер: «Этой проблеме подвержены практически все стеки TCP:
большие затраты процессорных ресурсов на обработку неправильных или созданных злонамеренно
блоков SACK».

Ильпо Ярвинен [1]: «Но пока в sacktag имеется зависимость от skb из fack_count,
будет оставаться определенная возможность атаки на обрабатывающий подтверждения процессор,
даже при использовании красно-черного дерева, потому что становится необходимым медленный обход».

Университет Северной Каролины: «В этом эксперименте мы показываем эффективность
обработки SACK. Поскольку мы наблюдали множество примеров, в которых TCP работал не лучшим образом с большим окном,
особенно при большом буфере».

CHC IT: «И, наконец, предупреждение для 2.4 и 2.6: для каналов с очень большим
значением произведения пропускной способности на задержку, где окно TCP превышает 20 МБ, вы скорее
всего столкнётесь с проблемой реализации SACK в Linux. Если в момент получения системой SACK в пути
будет слишком много пакетов, то потребуется слишком много времени на поиск указанного в SACK пакета,
вы получите тайм-аут TCP, и CWND вернется к 1 пакету».

Эта статья рассматривает реализацию SACK и ее производительность в неидеальных условиях, начиная
с Linux 2.6.22 — текущего стандартного ядра для Ubuntu 7.10. Сейчас этому ядру уже несколько месяцев, и после
его выхода разработчики не только обсуждали проблему, но и писали код. Текущее ядро ветви разработки — 2.6.25 — содержит
набор патчей от Ильпо Ярвинена, которые касаются производительности SACK. Я закончу статью рассмотрением того,
как этот код может поменять положение дел, а также кратким рассказом о некоторых других обсуждаемых будущих изменениях.

«Ресурсы»). Подтверждения в обычном TCP (без SACK) действуют
строго накопительно— — подтверждение N означает, что был принят N-й байт и все предыдущие.
Проблема, которую должен решить SACK — это «всё или ничего» простой накопительной схемы.

Например, даже если при передаче потерян только 2-й пакет (допустим, в последовательности
от 0 до 9), то получатель может получить подтверждение приема (ACK) только для 1-го пакета,
потому что это последний пакет, полученный без пропусков. Зато получатель с SACK может
передать ACK для 1-го пакета, а также дополнение SACK для пакетов с 3-го по 9-й. Эта
дополнительная информация помогает отправителю определить, что потери минимальны, и повторно
передать требуется лишь малую часть данных. Без этой дополнительной информации требовалось бы
передавать намного больше данных и замедлять скорость отправки для
приспособления к сети с большими потерями.

SACK особенно важен для эффективного использования всей доступной пропускной
способности в подключениях с большой задержкой. Часто из-за большой задержки в каждый
данный момент подтверждения ожидает множество «зависших» пакетов. В Linux эти пакеты стоят в очереди на
повторную передачу, пока не будет получено подтверждение их приёма и они больше не будут
нужны. Эти пакеты располагаются в порядке следования, но никак не пронумерованы. При
получении сообщения SACK, требующего обработки, стек TCP должен найти в очереди на
повторную передачу пакеты, которых касается это сообщение. Чем больше эта очередь,
тем сложнее найти необходимые данные.

В каждом пакете может присутствовать до четырех дополнений SACK.

«Как насчет более мощного сервера?»

Внимательный читатель также должен обратить внимание на то, что количество дискретных
тактов на переданный килобайт в 16 раз больше для кода, задействующего SACK, чем для
исходного случая, однако отношение показателей нагрузки на процессор более скромное — 2:3.
Объяснение дает другой показатель — время, которое занял тест. В исходном случае 22%
ресурсов процессора использовалось чуть более минуты, а клиент с SACK заставил процессор
загрузиться на 33% почти на 13 минут. К концу дня клиентом с SACK будет использовано
гораздо больше квантов вычислений, чтобы передать то же число данных.

На первый взгляд эти показатели не кажутся такими плохими. Хотя загрузка процессора во
время атаки и доходила до 33%, он не был загружен полностью. Полная загрузка процессора не
позволила бы выполнять другие задачи и привела бы к отказу в обслуживании.

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

Еще более глубокое рассмотрение показывает, что загрузка процессора на 33% обманчива. Эти
13 минут состоят из повторяющихся всплесков в несколько секунд, в течение которых весь сервер
занят на 100%. За вспышками следуют затухания в загрузке процессора, после чего цикл повторяется снова.
Средний результат — загрузка на 33%, но существуют продолжительные интервалы, когда процессор
полностью занят обработкой TCP, вызванной удаленным узлом.

Рассмотрим для всех трех случаев графики загрузки процессора в определенные моменты времени:

ресурсов );я сконцентрируюсь
на трех наиболее важных.

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

Ильпо Ярвинен [2]: «Думаю, мы не способны защититься от злоумышленников, изобретающих
обходы настроек и оптимизаций, которые могут использоваться для обычных, законных
случаев».

Первое изменение (см. в Ресурсах
«Abstract tp->highest_sack accessing &point to next skb») было сделано для
оптимизации схемы кэширования в исходном случае, когда опция SACK содержит только
информацию для данных с большими номерами в последовательности, для которых
уже производилось SACK. В целом это значит, что указанная ранее прореха при большом окне
остается, но для новых данных SACK будет производиться с ближней части окна. Это обычная
ситуация для нормальных действий. Патч оптимизирует этот случай, преобразуя
кэшированную ссылку из номера в последовательности в указатель на последний пакет
в очереди, для которого ранее производилось SACK. При помощи этой информации
другой патч (см. в Ресурсах «Rewrite SACK block processing &sack_recv_cache use»)
обрабатывает SACK, которые касаются данных только после кэшированного значения,
используя указатель кэша как отправную точку для просмотра списка — это устраняет
большинство затрат на проход по списку.

К сожалению, это не оптимизирует поведение в случае тестового клиента-злоумышленника.
Обычный ACK от такого клиента содержит опцию SACK для данных после тех, которые ранее просматривались,
но также содержит последовательность ссылок на непосредственно предшествующие пакеты. Чтобы
обнаружить эти данные, реализации 2.6.25 потребуется пройти с самого начала по очереди на
повторную передачу.

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

В прилагаемых к патчам комментариях отмечается, что в разработке находятся два
важных преобразования. Первое из них должно заменить текущий линейный список неподтвержденных
пакетов на структуру с указателем в виде красно-черного дерева. Это позволит проводить
логарифмический поиск пакетов, указанных в опциях SACK. Другое изменение, вводящее
некий указатель для доступа к произвольным элементам большой очереди на повторную передачу,
особенно важно для борьбы с атаками «find-first» на стек TCP.

Другое изменение в организации работы касается проблемы, которая здесь еще явно не
поднималась. Структура указателя даст хорошую производительность при просмотре отдельных
пакетов, но опция SACK может покрывать произвольные области байтов, включающие по
несколько пакетов. Ничто не остановит клиента-злоумышленника от отправки опций,
покрывающих практически все данные окна. Это отличается от атаки «find-first», на которой я
остановился в статье. Действительно, первый пакет может оказаться первым в списке, поэтому
его будет легко найти. Однако быстрый поиск требуемых пакетов не сильно поможет, если для
обработки опции SACK требуется линейно пройти по всей очереди. Изменения в коде должны
перестроить текущий список в два: один — с данными, для которых SACK производилось, а
другой — c данными, для которых SACK не производилось. Это может значительно помочь и
сузить пространство поиска только до тех данных, для которых не было SACK. Существует
ряд затруднений, касающихся связанной с этим спецификации DSACK (Duplicate SACK),
но поиски решения проблемы в этом направлении ведутся.

Последний интересующий нас патч (см. в Ресурсах «non-FACK SACK
follows conservative SACK loss recovery») — это изменение в семантике контроля за перегрузками,
внесенное для использования правил SACK из RFC 3517. Эти изменения позволяют ядру при
дополнительных условиях избежать полного восстановления, связанного с тайм-аутом. Восстановление
на основе тайм-аута предусматривает сокращения окна отправки до нуля и медленного обратного
наращивания до уровня, поддерживаемого текущим значением произведения пропускной способности
на задержку. Время восстановления обуславливает паузы между всплесками активности,
наблюдаемые в ходе теста.

Измерения для 2.6.25-pre

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

Таблица 2. Измерения нагрузки на сервер

Вот график загрузки ЦПУ во время использования специального увеличивающего окна клиента
со злонамеренными опциями SACK на ядре pre-2.6.25:

Рисунок 4. Специальный увеличивающий окно клиент
с SACK и ядро pre-2.6.25

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

Новый код заканчивает работу быстрее, но при этом очень сильно монополизирует процессор
на продолжительные промежутки времени и в среднем требует больше процессорного времени. Упущенное звено,
к которому можно привязать объяснение этих двух фактов, — это исключение в новом ядре вызовов
восстановления по TCP-таймаутам, что обусловлено изменениями, связанными с RFC 3517. Код 2.6.22
в среднем давал 17 тайм-аутов для каждого запуска тестового клиента. Для кода 2.6.25 в среднем
происходит всего 2. Результат на графике впечатляет: между тайм-аутами наблюдается гораздо
меньше бездействия процессора, поэтому мы получаем меньшее время простоя.

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

Однако эти большие окна также означают, что коду обработки SACK приходится
совершать намного больше работы для каждого входящего пакета, так как в просматриваемой
очереди содержится больше пакетов. Результаты в 2,7 миллиарда пакетов, просмотренных
за сеанс передачи файла (в четыре раза больше, чем в ядре предыдущей версии) и 10,07 дискретных
тактов на переданный килобайт наглядно показывают, что предстоит еще много работы.

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

Заключение

Влияние злонамеренно созданных опций SACK на производительность может быть очень
значительным, но сценарий не доходит до уровня простой в исполнении DoS-атаки.
Единственное спасение — в саморегуляции, связанной с периодическими тайм-аутами, но не так
сложно представить себе другой клиент, который может работать в режиме, при котором сервер
бы блокировался, но не доводился до точки тайм-аута.

Это не должно затронуть компьютеры, которые не отправляют большие блоки данных, так как
они никогда не заполнят большие окна, являющиеся основой уязвимости. Хотя выборочные
подтверждения необходимы для хорошей производительности на сетевых соединениях с
большим значением произведения трафика на задержку, они остаются необязательной
возможностью, которую можно отключить, не жертвуя способностью к взаимодействию. Для
отключения SACK в стеке TCP можно установить значение 0 для переменной
net.ipv4.tcp_sack из sysctl.

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