Среди обычных разговоров разработчиков 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. Я закончу статью рассмотрением того, как этот код может поменять положение дел, а также кратким рассказом о некоторых других обсуждаемых будущих изменениях.

Основы SACK

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

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

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

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

Сценарий атаки

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

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

Количество пакетов в очереди на повторную передачу в основном определяется значением произведения пропускной способности на задержку (bandwidth-delay product, BDP) для двух узлов. Пропускная способность ограничена физическими характеристиками сети — атакующая сторона не может повысить ее без получения дополнительных каналов. Однако злоумышленник может произвольно увеличивать задержку, высылая каждое подтверждение спустя небольшое время после приема пакета. Для эффективного использования пропускной способности такого соединения с большой задержкой серверу требуется, чтобы в пути было достаточно пакетов, так что их среднее время передачи равнялось бы времени, необходимому на получение подтверждения. Если этого не делать, то в определенные промежутки времени по сети пакеты передаваться не будут, и пропускная способность будет использована не полностью. Каналы с большой задержкой требуют большого числа пакетов в пути для эффективного использования сети, и отправители TCP могут активно пытаться заполнить это пространство до пределов, определяемых стандартами на загрузку сети.

Задержка подтверждений успешно увеличивает размер очереди на повторную передачу, что является необходимым условием атаки. Например, если в довольно медленном соединении 10 МБ/с использовать задержку в 1750 мс, то образуется окно из 12 000 пакетов. Более быстрые соединения образуют еще большие окна, но уязвимость отчасти происходит из того, что такой подход реализуем на обычных домашних широкополосных соединениях, с помощью простого добавления больших задержек.

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

Этот конкретный сценарий атаки (основной предмет обсуждения статьи) известен как «find-first attack», потому что заставляет стек TCP тратить избыточное количество времени на поиск первого байта, указанного опцией SACK.

Измерения для сценария атаки

Измерение должно быть безумным! Kode Vicious

Учитывая все сказанное, давайте посмотрим, является ли это серьезной проблемой. Это задача для незначительной оптимизации, полномасштабный кризис либо что-то среднее? Для ответа нам нужны реальные данные, чтобы оценить серьезность вопроса. Задача номер один — решить, какие данные собирать и как их оценивать.

Подготовка эксперимента

Самое важное — собрать данные о нагрузке на серверный процессор. Основную работу может выполнить Oprofile со стандартным счетчиком CLK_UNHALTED. Также интересно посчитать количество просмотренных пакетов при обработке ответов SACK, а также средний размер окна на повторную передачу. Я добавил в исходный код сервера счетчик просмотренных пакетов. Также я перезапустил тесты без этого счетчика, чтобы убедиться, что вижу те же результаты, какие проявлялись бы на обычном сервере.

Также интересно знать, какое количество пакетов находится в пути. Средний размер очереди на повторную передачу можно рассчитать, используя счетчик просмотренных пакетов, если на стороне клиента также отслеживать количество переданных опций SACK. Для тестов без SACK я использовал обычную длину очереди задержанных ACK, переданных клиентом, чтобы примерно определить нижнюю границу размера окна TCP отправителя.

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

Клиент начинает эксперимент с подключения к серверу и передачи простого HTTP-запроса на ISO-файл размером 700 МБ. Затем он принимает все данные, посланные в ответ сервером по обычной сети 100 Мбит/с. Каждый пакет от сервера подтверждается с задержкой 1750 мс. Сервер пытается заполнить все 1750 мс постепенным увеличением одновременно высылаемых пакетов до тех пор, пока они не будут подтверждены. Я наблюдал окна до 14 000 пакетов в пути.

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

Для осмысленного сравнения я собрал данные для трех различных случаев:

1. Исходный случай: в первом тесте я провел базовые измерения. Вместо использования специального клиента и стека TCP я задействовал стандартный TCP-стек Linux и консольный HTTP-клиент wget.
2. Специальный случай, без SACK: во время второго измерения использовался специальный клиент, вызывающий увеличение окна TCP, но вообще не использующий SACK. Эти данные позволяют отделить обычные эффекты, вызванные увеличением окна TCP, от тех, которые вызваны обработками злонамеренных передач опций SACK.
3. Специальный случай с SACK: последний набор данных собирался с клиентом, вызывающим увеличение окна TCP, а также добавляющим к каждому ACK по четыре опции SACK.

Использовался довольно старый сервер с процессором Athlon XP 1.2 ГГц.

Измерения

Обманчивые данные Некоторые удивительные на первый взгляд показатели легко объяснить. Заметьте, что количество ACK примерно вдвое больше для специального клиента, чем для исходного wget. Это связано с тем, что специальный клиент направлен на ухудшение поведения сервера. В результате он не выполняет объединенные подтверждения. Большинство стеков TCP объединяет два подтверждения в одно, если они отправляются вплотную одно за другим без каких-либо данных. У специального клиента есть возможность сделать это, но она не была включена для наших данных. Был проведен запуск с включенной опцией объединения подтверждений, но оказалось, что на деле это не влияет на результаты. Объяснения смотрите ниже в примечании «Как насчет более мощного сервера?» Внимательный читатель также должен обратить внимание на то, что количество дискретных тактов на переданный килобайт в 16 раз больше для кода, задействующего SACK, чем для исходного случая, однако отношение показателей нагрузки на процессор более скромное — 2:3. Объяснение дает другой показатель — время, которое занял тест. В исходном случае 22% ресурсов процессора использовалось чуть более минуты, а клиент с SACK заставил процессор загрузиться на 33% почти на 13 минут. К концу дня клиентом с SACK будет использовано гораздо больше квантов вычислений, чтобы передать то же число данных.

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

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

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

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

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

Специальный клиент, не использующий SACK, также дает приемлемый график загрузки. Дополнительная сложность управления большими окнами TCP и работы с постоянными потерями приводит к немного большей загрузке процессора, но сервер всегда остается доступным.

Просто удивительно, насколько больше синей краски разлито по графику загрузки с SACK. Хотя средняя загрузка — составляет 33%, график ясно показывает повторяющиеся всплески, отражающие полную загрузку сервера.

Похоже, что на графике постоянно отрисовывается функция y=x^2 до тех пор, пока y не достигает 100%. Это ясно показывает, что для поиска нужных данных каждая опция SACK требует просмотра полной очереди на повторную передачу. Когда окно перегрузки на стороне отправителя растет, оно эффективно фактически удваивает число пакетов в пути за то время, пока пакет отправляется и в ответ принимается подтверждение. Эта удвоенная очередь требует проверки по каждой полученной опции SACK. Обратите внимание на удивительное число просмотров пакетов при обработке SACK — 755 миллионов — всего на полмиллиона полученных ACK. Этот алгоритм атаки вызывает экспоненциальное поведение, заметное на графиках.

Как насчет более мощного сервера? Основные претензии к эксперименту касались задействования скромного Athlon 1,2 ГГц в качестве тестового сервера. Кажется, что это может занизить обрабатывающие способности серверной стороны. Однако проявившееся квадратичное поведение относится к эффектам, которые нельзя устранить, перейдя на более быстрый сервер, либо реализовав оптимизации вроде объединения двух ACK в одно. Такие изменения потребуют увеличить границы окна перегрузки за небольшое число пакетов в 3 200, проявившееся в наших измерениях, однако кривая загрузки серверного процессора растет таким образом, что наверняка достигнет предела до открытия окна на 10 000 и более, что необходимо для заполнения этой относительно быстрой сети Ethernet.

Последняя загадка: почему это не гибельно для сервера? Было бы разумно ожидать, что загрузка подскочит до 100%, после чего останется на этом уровне до конца передачи. Но вместо этого мы видим последовательность вспышек и спадов. Ситуация выглядит так, будто очередь на повторную передачу сокращается. Нет?

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

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

Разработки ядра

Что делают разработчики?

Разработчики сетевой части Linux уже работают над кодом. 15 ноября 2007 г. Ильпо Ярвинен отправил значительное исправление алгоритмов обработки SACK. Этот код был помещен в ветку Линуса pre-2.6.25 во время слияния патчей 28 января 2008 г. Полный набор включает 10 патчей (см. ссылки в разделе ресурсов );я сконцентрируюсь на трех наиболее важных.

Исправления были написаны для улучшения производительности 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 ветки разработки. Для удобства сравнения в таблицу включены результаты трех предыдущих измерений.

Вот график загрузки ЦПУ во время использования специального увеличивающего окна клиента со злонамеренными опциями 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. Это закладывает основу для последующих разработок, таких как индексирование списка пакетов и разбиения, которые в будущем помогут бороться с некоторыми типами атак.