XZ бэкдор нашумел. Не только потому что нагло, а ещё и потому, что технически интересно. Пускай в конце концов всё равно обосрались из-за непонимания фундамента. Я его тоже не понимаю, кстати.
Но во всей этой шумихе, мне больше всего понравилось, как они дерево пожали.
Бэкдор загрузился раньше других, и теперь ему нужно ждать, когда линкер подыщет всю вкусноту. Бэкдор для этого добавляет хук, который вызывается для каждого нового символа, и ему нужно понять, нужный ли это символ (например, функция загрузки RSA ключа). Проблема: условная строка
RSA_public_decrypt@got.plt в бинаре появиться не должна. Это было бы банально слишком подозрительно. Решение? Построить дерево.С деревом строки больше нигде явно не встречаются. Тех строк вообще номинально нет, дерево служит эдакой таинственной коробочкой "Это нужная строка? Да/Нет". Мои примеры с поиском, возвращающим true/false - не такие уж и бесполезные, как оказалось.
Места не так уж и много, поэтому китаец взял наш любимый array mapped trie. (Про китайца я, правда, выражаю сомнения. Легко на них всё сбросить.) Только там вместо того, чтобы хранить все узлы полностью в одном массиве, вынесли битмапы в отдельный, второй массив. Всё для того, чтобы можно было там хранить только уникальные битмапы (а узлы на них, соответственно, ссылаются). Такое дерево может спокойно похудеть на 20-30%. Правда, я не уверен, сработает ли такое на бОльших масштабах (при сохранении арности): всё-таки фокус такой LZ-style компрессии в том, что индекс на битмапу меньше размера самой битмапы.
Если интересно почитать более общий обзор, то прекрасная статья здесь. Ещё неплохой материал у herm1t с канала @ruheight конкретно про дерево и почему китаец начал хорошо, а кончил... Ну, как кончил, в общем.