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

Защита строится по подобию троттлинга, только наоборот и низкоуровневее: подключения рубятся, если слишком медленные. Скажем, пару сот бит в секунду. Естественно, лимит работает только на периоды активной передачи данных, в idle состоянии хули его трогать-то.

А вот в индиго такого нет, кстати.

Скролл времени в иос - это не цикл, а очень длинный список.

Боже, как же хорошо, что Хаффмана для хттп2 я сделал ещё полтора года назад. Если бы не тогдашний Павло, я бы обосрался, выгорел и ещё месяца два колупал его палкой.

В HTTP/2 мультиплексирование устроено за счёт стримов и фреймов. Фрейм - фиксированный заголовок из 9 октетов (24 бита длина, 8 бит тип, 8 бит флаги, 1 бит зарезервирован и 31 бит идентификатор стрима). Каждый стрим - это ровно один запрос и один ответ (за исключением стримов, инициированных сервером - которые PUSH_PROMISE). Когда мы хотим сделать запрос, мы просто шлём заголовки на стрим, ид которого ранее не использовался, неявно переводя его из состояния idle в reserved. Как только ответ полностью передан, стрим считается closed и больше не может быть заново использован.

Стримы, инициированные клиентом, обязаны быть нечётными, а инициированные сервером - чётными. Таким образом, пространство идентификаторов для запросов составляет 2^31 / 2 = 30 бит, миллиард с копейками. Когда истощается, следует открыть новое подключение.

(PUSH_PROMISE это, кстати, обещание отправить клиенту по указанному стриму ответ без предварительного запроса. По-умолчанию фича, правда, отключена, и клиент также может её со своей стороны отключить, и тогда сервер не имеет права её использовать.)

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

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

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

Хэшмапа как стартовая точка, но я пока не пробовал и не сильно уверен в её эффективности по памяти. По скорости, в принципе, должна быть около-оптимальной.

Принимая, что обычный LUT не подойдёт из-за пропусков (даже в нормальном случае, поскольку более новый стрим может завершиться раньше более старого), а обычная мапа принимается, как немного чересчур жирная - наиболее оптимальным решением, как мне кажется, является обычная хэшмапа с открытой адресацией, где вместо хэша - log(hmap_size) (он же log(max_streams)) нижних бит идентификатора стрима. Низлежащий индексируемый массив будет состоять из структуры, включающей в себя целый ид стрима, и непосредственно канал для связи с горутиной. Речь идёт о трёхзначных числах.

Интуитивно решается вопрос с зацикливанием - новые вхождения будут сами по себе постепенно переползать с конца мапы в начало. С пропуском всё тоже прекрасно решается, правда, разрешение коллизий линейной пробой может быть больноватым. Например, если у нас завершились два самых новых стрима, а все остальные всё ещё активны - мы обойдём весь массив прежде, чем найдётся свободный слот. Лукап будет не менее болезненным.

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

Ну, правда, и проблемой-то это назвать можно с натяжкой. Принимая за базовый случай 128 вхождений, перебор ~100 uint32 не так уж и дорого, как для worst case. Больновато, но это 30-150нс, если массив нормально в кэше лежит. Беря 8 байт на вхождение (uint32 идентификатор стрима + указатель на канал = 2 машинных слова, рассматриваем 64-разрядные системы), 1024 байт на таблицу выглядит вполне кэшебабельно. Не предел мечтаний, конечно, но всё ещё крайне вероятно оптимальнее стд мапы, где свиссмапа на свиссмапе (буквально, кстати).

Наконец-то применяю эти знания. Не зря ресёрчил.

Утка.

Энтропия и компрессия

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

С такой формулировкой, определение "энтропия есть мера хаоса" должно быть чуточку яснее: чем менее хаос упорядочен, тем более он, собственно, хаос. Шото типа холод - отсутствие тепла.

Сжатие - тема социально-значимая. Изначально мысль у меня возникла, когда с кодировкой Хаффмана игрался. Эффективность компрессии напрямую зависит от частотного распределения символов: чем больше разброс, тем эффективнее сжатие получается. Ну, то есть, чем более предсказуема система, или же чем больше дисперсия в распределении. ЧЕМ ВЫШЕ ГОРБИК НА ГРАФИКЕ. А это значит, что чем ниже энтропия строки, тем эффективнее можно провести сжатие.

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

Например, если у нас в ASCII строке идут 70 байт "а" и 30 байт "б", то P("a") = 0.7, P("б") = 0.3. Тогда энтропия равна 0.7*(-log 0.7) + 0.3*(-log 0.3) ≈ 0.88 бит. Это значит, что вместо использования фиксированного кодпоинта 8 бит шириной (на самом деле 7 + неиспользованный старший), мы можем закодировать каждый символ, используя всего ~0.88 бит. Коэффициент сжатия 9х!

Здесь, конечно, есть свои нюансы. Во-первых, биты не делятся. Поразительные умозаключения. Во-вторых, реальная жизнь трудна и полна разочарований. Всё.

Да и нельзя сказать, что это универсальное определение задачи компрессора. Энтропия и кодировка не являются равнозначными. Например, строки abababababab и ajftblkqnsmp имеют одинаковую энтропию, если принимать алфавит {a, b} для первой строки и {a, j, f, t, ...} для второй, поскольку каждый символ алфавита встречается ровно один раз. Но чтобы описать первую строку, нам понадобится лишь сказать, что ab повторяется 6 раз. Со второй строкой дела обстоят сложнее. Это называется колмогоровская сложность: количество ресурсов, необходимых для описания объекта.

Кодировка Хаффманна неплохо справится с обеими строками. Но если взять, например, английский алфавит и продублировать его несколько раз, тогда гораздо лучше справился бы lz77. Он ищет повторяющиеся последовательности (с ретроспективой в 32768 байт и плавающим окном) и подменяет их неким указателем - парой (offset, len), что довольно дёшево. Тогда коэффициент сжатия будет равен количеству дубликатов алфавита, минус полшишечки поправки на размер самой пары.

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

https://gfw.report/blog/geedge_and_mesa_leak/en/

Слили китайский файрволл. Доки, jira тикеты, блэклисты ресурсов, снапшот rpm-репозитория (на 500гб), исходный код. Вроде как там ещё и код DPI включён, поэтому интересна

китайская текнолоджия

В HTTP/1.1 была одна большая проблема - Head of Line Block. Одно подключение обрабатывает всего 1 запрос за раз.

Можно несколько запросов подряд отправить, вот прям одним пакетом. HTTP pipelining называется, но браузеры эту фичу по-дефолту (т.е. всегда) отключают, потому что слишком много серверов багованные были и нормально не умели их разруливать. Криворукие дегенераты, кстати, индиго-то прекрасно умеет. Но исходную проблему это не решает - у нас всё ещё одновременно обрабатывается всего 1 запрос на подключение.

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

Вот на тему нескольких подключений - хром (фуррилиса, скорее всего, тоже) имеют лимит в 6 параллельных подключений на домен. Некоторым было и этого недостаточно, и они упирались в HoL. Отсюда пошёл приём domain sharding, когда у нас несколько субдоменов а-ля api.example.com, static.example.com, чтобы "увеличить" лимит и иметь ещё больше параллельных потоков (подключений).

Это одно из двух главных новшеств HTTP/2: добавили наконец мультиплексирование. Это когда несколько потоков данных склеивают в один. Сам по себе термин из телекома пошёл, там провода вместе скручивали. Аналогично и здесь: теперь запросы разбиты на кусочки (фреймы), и у каждого кусочка свой стрим (медная/оптическая фибра). И вся эта радость летит по одному-единственному подключению. Всё ещё присутствует лимит на одновременно активные стримы, конечно, но в стандарте рекомендуют его выставлять на не менее 100, а в дикой природе обычно и вовсе 128 шуруют (степень двойки неспроста, кстати). А 128 одновременно выполняющихся запросов - это на два порядка больше чем 6, ёпта.

Нет, можно и подключений 128 вхоботить, но проблема во-первых в блэкбоксах (файрволлах), которые часто любят пропускать не больше 30 штук с одного адреса. А во-вторых, это в целом не очень приятная штука - и ядро много памяти под буфер для подключения выделяет, и больше их поллить надо (условный еполл масштабируется в логарифм, но всё равно — меньше = лучше), так ещё и холодный старт для каждого из них. Правда, теперь демультиплексировать фреймы из подключения в соответствующие горутины нужно мне самостоятельно ручками вместо ядра, да и за окнами следить теперь самому надо (когда-нибудь возможно и про них пост напетляю). Такова цена успеха. Ощущение присутствия инородного тела в прямой кишке.

Спасибо интел за пидорастические дроби

0.0000000000000000061234 видите? А должен быть сука ноль.

Не зря делал, наверное

Как напоминание всплывает

Может, я чего-то не вдупляю, но эти 32 октета - ни в пизду ни в сраку. Нахуя их учитывать? Они фактически таблицу на 80 байт превращают в 16, при том максимум вмещая всего 2 вхождения, третье-то уже не влезет. Таблица на 4096 байт вместит максимум 128 вхождений. ПОЛНОСТЬЮ ПУСТЫХ. 64 вхождения, если каждое занимает 32 байта (реальных) - а это не так уж и много, вообще-то. Какой-нибудь куки? Аха, хорошо, это дропнет примерно половину всей таблицы. И похуй, что моя имплементация вообще может вообще всего 24 байта оверхеда на вхождение накидывать.

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

Я крайне надеюсь, что в QPACK это позорище вырезали. Тем лучше, чем брутальнее.

А, да, HPACK. В HTTP/2 решили, что хорошей идеей будет сжимать заголовки. Что, в общем-то, и правда хорошая идея. Правильная, я бы даже сказал. Чем полагаться на обычные компрессоры, решили сделать лучше - и сварганили свою схему кодирования, гордо именуемую HPACK, и вынесенную аж в отдельный RFC7541 (сам HTTP/2 живёт в RFC7540). Не просто так, кстати: таким образом, они хотели обезопасить шпак от изменений в будущих HTTP/2 RFC. Да и в целом они его максимально негибким сделали, чтобы никто его никак не вертел без того, чтобы новый RFC публиковать. Так и вышло: для HTTP/3 схему всё-таки подкрутили, и опубликовали, как QPACK.

Ну и вот, в HTTP/2 HEADERS фреймах (ну или же CONTINUATION, если же в соответствующем стейте) передаются как раз заголовки в формате HPACK. "Поле", как они называются (решили абстрагироваться от "заголовок"), может быть одно из 5 типов:
1. Полная пара из таблицы
2. Ключ возможно в таблице, значение вот
3. Как 2, только в таблицу не добавляется
4. Как 2, только в таблицу НИ В КОЕМ СЛУЧАЕ не добавляется.

4 - это всякие сенситив заголовки а-ля токены аутентификации. Отличие от 3 в том, что intermediaries (они же всеразличные прокси и их друзья) обязаны также передать этот заголовок дальше, как never indexed.

5. Изменение размера таблицы - не так интересно, опустим.

Углубляться в то, как оно выглядит, я не буду. Для этого я оставил номер RFC🫶

Собственно, таблица, сердце всей схемы. Она делится на две части: статическая и динамическая. Они делят общее индексное пространство, но новые значения добавляются, понятно, только в динамическую. Таблица эта хранит целые пары заголовков - и ключ, и значение. В статической, правда, добрые 2/3 с пустыми значениями, но оно и понятно - они там только ради ключей. Ну, то есть, а хули в качестве значения для cookie давать?

Статическая таблица вмещает 60 пар, индексируется с единицы (потому что индекс 0 зарезервирован для литеральных ключей). То есть, динамическая таблица начинается с индекса 62. Вообще, она сама по себе интересна: при добавлении новой пары, она встаёт в самое начало, т.е. на индекс 62. Все предыдущие, соответственно, сдвигаются на +1. Когда максимальный размер таблицы превышается, самые старые вхождения дропаются до тех пор, пока новая пара не поместится. Попытаться засунуть 10-мегабайтный заголовок в таблицу на 4096 байт это не ошибка, кстати, просто таблица окажется пустой - все старые значения дропнутся, а новое один хуй не влезет. Правда, есть и более гуманные способы её очистить.

Ещё есть забавный момент, потому что ключ новой добавляемой пары может ссылаться на уже лежащий в таблице. И тогда может возникнуть нюанс, что ключ, на который как раз и ссылается новое вхождение, находится в конце и должен быть дропнут. Тогда у нас магическим образом возникает dangling pointer, только dangling index. Тоже об этом в стандарте предупреждают. Слава богу, что мене це не бентежить, я монофаллически держу всё в закольцованном буфере.

TL;DR вышесказанного:
- Статическая таблица по индексу 1-61;
- Динамическая таблица, начиная от индекса 62 включительно;
- Когда в динамическую таблицу попадает новая пара, она занимает индекс 62, остальные смещаются;
- Если добавление новой пары превышает максимальный размер таблицы, самые старые вхождения дропаются;
- Опасно дропать сразу, иначе может произойти жопа;
- Гигантская пара размером больше максимального размера просто очистит таблицу;
- Размер таблицы - сумма длин всех вхождений;
- Длина вхождения - длина ключа, значения и 32. На 32 всё ещё злюсь, из-за них тесты ебливей писать;


А вот что забыл упомянуть, так это опциональное кодирование Хаффманом для литералов. Что ключи, что значения могут быть им закодированы. Хаффман используется со статической таблицей кодов, также представленной в RFC. Естественно, длина учитывает только декодированное ключ-значение.

https://www.securitylab.ru/news/564421.php

Компилятор иногда разбивал корректировку стэкпоинтера в эпилоге функции на две инструкции. Поскольку долгоиграющие функции с 1.14 прерывались насильно сигналом SIGURG, иногда они заставали исполнение как раз между ними двумя, таким образом ломая стэк. Иногда - сегфолт, иногда - само неконсистентность стэка замечало. В 1.25, вроде как, исправили, выполняя операции сначала на временном регистре.

Вроде слабо, а вроде и у чуваков по 30 раз на дню падало. Вот уж соболезную)

https://en.wikipedia.org/wiki/Pentium_FDIV_bug

Сначала припирались, а потом таки согласились менять на исправленные всем желающим. Большие ж бабки потеряли тогда

Случайности не случайны!

В Zen5, тобишь. У них инструкция RDRAND сильно предвзята по отношению к нулю - возвращается в более 10% вызовах, при том с флагом успеха (регистр CF=1). Подозревают, что сам регистр некорректно определяет успешность операции, вот и помечает успешным то, что таковым не является.

При том это их не первый раз. На Zen2 уже было такое 6 лет назад, что после сна/гибернации инструкция начинала возвращать все включённые биты. Там аж системд стартовать отказывалось (поттеринг в ишшуе отослал автора к ядрописцам, конечно же).

Кстати, сам рандом они генерируют из тепловых шумов. Интересно, а они тоже просто взяли ринг буфер как пул энтропии?


Актуальный багрепорт + фикс ядра: https://lore.kernel.org/lkml/20251016182107.3496116-1-gourry@gourry.net/
Как это было когда-то: https://arstechnica.com/gadgets/2019/10/how-a-months-old-amd-microcode-bug-destroyed-my-weekend/

Кстати, у интела оно интересно устроено. Исходя из вики, они сначала берут сырой поток данных с тепловых датчиков, формируют из них пары по 256 бит и прогоняют через AES. В итоге имеем один монолитный кирпичик 256 бит отменной энтропии, что используется в качестве сида для ГПСЧ (NIST-certified, вся хуйня; правда, называют они его DRNG - digital random number generator). Каждые ~64 килобайта генератор ресидится.

Рядом ещё есть RDSEED, оно использует всё те же тепловые флуктуации, только работает асинхронно (отдельно от основного чипа) с собственной фиксированной тактовой частотой 3ГГц. Медленнее, чем RDRAND, предназначен так же, как и назван - чтобы софтварные ГПСЧ сидить случайными числами произвольной ширины. Что, по всей видимости, и есть ключевая разница от RDRAND, который годится приложениям, которым нужен просто качественный рандом фиксированной ширины.

Правда, состояние генератора они держут общим между всеми ядрами. Ну, то есть, лежит общий некий стейджинг буфер, из которого любой может спокойно читать. И в 2020 году мужики из амстердамского университета показали, что с первой попытки можно целый ECDSA ключ сразу после подписи извлечь, если с соседнего ядра вовремя тот самый буфер почитать. А это - классическая проблема с исполнением недоверенного кода, когда он может что-то пиздить у доверенного соседа. Выпустили заплатку микрокодом, теперь RDRAND, RDSEED, EGETKEY (кто?) выполняются исключительно одним ядром за раз, остальные ждут. Просто по завершению тот стейджинг буфер перезаписывается. Задели целый ряд процов с 2012 по 2019 годы, а фикс, по классике, вкурвил и без того низкий перф (софтварные ГПСЧ кратно быстрее, что удивительно; Mersenne-Twister так и вовсе во все 20 раз).

А ещё Теодор Тсо (тот, который умнее тебя и всей твоей семьи вместе взятой) высказывал сомнения по поводу этой штуки. Мол, интеловцы хотели в ядре продавить свой RDRAND как единственный источник для /dev/random. Что, естественно, а) небезопасно (в том числе благодаря прецедентам с AMD выше) и б) просто стрёмно. Ну, то есть, мы сейчас возьмём и пересадим почти весь серверный сегмент на рандом из впаянного чипа, который никто не знает, как работает, никто не может провести аудит, так он сам ещё и от около-государственной корпорации? Звучит надёжно, наливайте!

Ну, то есть, он используется, как один из источников. Но в 2013 оказалось, что всё сыпется, если туда оказывается посажен бэкдор, нацеленный на конкретный код (маловероятная ситуация, не так ли?). Проблему смягчили (вероятно, снизили общую долю в пуле или подкрутили ϵ, чтобы оттуда более униформные значения лезли; позже и об этом пост будет). Во FreeBSD инструкцию вообще от греха подальше вырезали.


В общем, очередное напоминание, что рандом - это сложно и ответственно, а блэкбоксы - плохо. AMD не хватает побольше тестирования.

Чем дольше всматриваешься в бездну, тем больше Тьюринг-полноты вокруг замечаешь. JustWiFi7 - в свой большой компьютер ты втыкаешь маленький компьютер под линуксом, который крутится на кастомной фирмвари. Теперь линукс запускается ещё и на формфакторе ноутбучной оперативки. Зато блютуз-адаптер на моём линуксе — нет. Этот маленький пидорский кусочек пластика рандомно отъебнул и теперь заводится где угодно, кроме моей машины. Я его матушку.