Hacker News Digest

В задаче Google CTF 2025 webz исследуется уязвимость в патче Google-zlib, который увеличивает размер таблицы Хаффмана и убирает проверки на переполнение. Это позволяет обойти защиту от oversubscription и incomplete set, что ведёт к использованию неинициализированной памяти в таблице.

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

• Обсуждается уязвимость в модифицированной версии zlib, созданной специально для CTF-задачи Google, а не в основной библиотеке.
• Участники отмечают сложность и искусственный характер задач Google CTF, но предлагают ресурсы для обучения и тренировки.
• Проводятся параллели между этой уязвимостью и ранее обнаруженной уязвимостью в WebP.
• Подчёркивается, что ошибку можно быстро найти с помощью фаззинга, без необходимости привлечения ИИ.
• Уточняется, что заголовок исходной статьи содержал пометку "[CTF]", указывающую на соревновательный контекст.

Изначальный алгоритм декодирования изображений с камеры Quicktake 150 на процессоре 6502 работал 70 минут. Основная проблема — сложный формат сжатия на основе кодирования Хаффмана и 16-битной математикой, что крайне неэффективно для 8-битного процессора.

Оптимизация началась с отказа от декодирования цвета, поскольку итоговое изображение было монохромным. Это сократило обработку только до зелёных пикселей матрицы Байера. Далее удалили ненужные буферы и промежуточные шаги, включая интерполяцию, что уменьшило размер вывода до 320×240. В итоге остался лишь один используемый буфер из трёх. Эти изменения сократили количество инструкций с 301 млн до 25 млн, а время декодирования — до минуты. Ключевой вывод: алгоритмическая оптимизация даёт больший выигрыш, чем низкоуровневая оптимизация кода.

• Обсуждение визуального парадокса: изображение с чередующимися черными пикселями кажется более четким, чем изображение без них, несмотря на одинаковый объем информации.
• Ностальгия по низкоуровневому программированию и работе с аппаратными ограничениями (память, скорость) как к refreshing практике для инженеров.
• Технические гипотезы о причинах визуальных артефактов (масштабирование браузером, адаптивная подсветка, HDR-режим).
• Критика современного ПО: несмотря на миллионократный рост мощности hardware, воспринимаемая скорость и отзывчивость интерфейсов часто снизились.
• Идея о необходимости целенаправленной оптимизации кода для повышения эффективности, возможно, с использованием ИИ.

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

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

• Критика недостаточной визуализации динамических блоков и таблиц Хаффмана в gzip/deflate, отсутствие пояснений к параметрам и символам.
• Запросы на улучшение: добавление легенды для цветов, объяснение формата backreference (например, "x4<-135"), поддержка многоблочных текстов.
• Обсуждение технических проблем: несоответствие подсчёта байтов, отсутствие паддинга, предложения по визуализации Brotli и zopfli.
• Упомянуты альтернативные инструменты для визуализации deflate, отмечена сложность кодирования динамических таблиц Хаффмана.
• Шуточные комментарии о тестовых данных (Bee Movie script) и замечания об опечатках в названиях (zlib vs Z-Lib).

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

Ключевой идеей стало применение простой двухслойной нейросети, обученной на лету, что дало прирост в 2–3% по сравнению с классическим Huffman-кодированием. Такой гибридный метод показывает, как даже базовое ML может решать узкоспециализированные задачи, где точность предсказаний критична. Практический вывод: машинное обучение может быть интегрировано в низкоуровневые системы для нетривиального улучшения производительности.

• Автор выражает разочарование отсутствием связи между обсуждаемым алгоритмом BZip2/BZip3 и языком программирования Ada в статье.
• Несколько пользователей жалуются на чрезмерно навязчивую и мешающую чтению рекламу на сайте.
• Обсуждается использование блокировщиков рекламы (AdBlock, Pi-hole, NextDNS) как необходимое средство для комфортного просмотра сайтов.
• Один пользователь отмечает, что не видит рекламы без блокировщика, что вызывает удивление у других.
• Упоминается, что даже ФБР рекомендует использовать блокировщики рекламы в целях безопасности.

День 2: строим дерево Хаффмана

Переписал bz2.adb на чистые структуры:
Bit_Writer, MTF, RLE, Burrows_Wheeler, Huffman.
Каждая структура = пакет + скрытый тип + конструктор Create, методы Encode, Flush, Reset.

Huffman

• Считаем частоты 256 байт + 2 служебных символа (RUNA, RUNB).
• Строим дерево: Node (частота, символ, левый, правый).
• Сортируем список узлов по частоте, склеиваем два минимальных, повторяем, пока не останется один корень.
• Коды длиной ≤ 20 бит (требование BZip2).
• Генерируем таблицу Code_Length[0..257] и Code_Value[0..257].

Оптимизация

• Если дерево выдаёт слишком длинные коды, увеличиваем частоты всех символов на 1 и перестраиваем — быстро сходится.
• Память: дерево живёт только во время построения, затем храним только таблицы.

Интеграция
Huffman.Encode получает поток MTF/RLE-символов, пишет в Bit_Writer:

1. 16-битная маска 0x425A ("BZ").
2. 8-битная версия 0x68.
3. Таблица длин кодов (передаём как 4-битные значения).
4. Сами данные: коды Хаффмана + биты RLE-последовательностей.

Итог за день

• 400 строк Ada, 0 зависимостей.
• Код компилируется gnatmake -O2 bz2.adb за 0.3 с.
• Тест: echo "abracadabra" | ./bz2 > out.bz2, bunzip2 принимает без ошибок.

Завтра: многопоточность и буферизация.

• Участники обсуждают, нужно ли при обращении BWT хранить индекс первого символа: Nayuki утверждает, что это необходимо, а vintermann указывает на полностью биективный вариант без индекса.
• Amy_petrik подчеркивает, что BWT переводит строку в «пространство суффиксных деревьев», что позволяет быстро искать внутри сжатых BZ2-файлов и лежит в основе современных ДНК/РНК-алгоритмов выравнивания.
• Horizon2025 отмечает «магическую» обратимость преобразования при минимуме дополнительных данных.