Восстановление таблиц xref повреждённых PDF: скан в Delphi

Когда таблица перекрёстных ссылок PDF непригодна к использованию, решение — полностью её игнорировать и перестроить из тела файла. PDFlibPas Delphi PDF Library делает это однопроходным токенным сканером, который фиксирует каждый настоящий заголовок косвенного объекта, который встречает, затем восстанавливает словарь трейлера и передаёт реконструированную таблицу обычному загрузчику

Что ломается первым, когда PDF повреждён

Таблица перекрёстных ссылок — самая хрупкая часть PDF, потому что это единственная часть, хранящая абсолютные байтовые смещения. ISO 32000-1 §7.5.4 определяет эти записи как десятизначные смещения от начала файла, а §7.5.5 помещает ключевое слово startxref ближе к концу, указывающим на саму таблицу. Каждое из этих чисел становится недействительным при любой правке, сдвигающей байты. FTP-сессия, прошедшая в текстовом режиме и преобразовавшая CRLF, оборванная загрузка, сектор, испортившийся на общем диске, пакетный инструмент, дописавший данные без корректной записи инкрементального обновления — все они оставляют данные объектов совершенно читаемыми, а индекс указывающим на мусор

Именно поэтому диалог «файл повреждён и восстанавливается» так распространён. Байты почти всегда всё ещё на месте. Пропала карта. Реконструкция, таким образом, — это не криминалистическое восстановление утраченных данных, а перестройка индекса, который можно вывести из тела, и она удаётся гораздо чаще, чем ожидают пользователи, потому что дорогое содержимое — деревья страниц, шрифты и изображения — остаётся нетронутым

Почему поиск N 0 obj даёт ложные совпадения?

Наивная реконструкция ищет в сырых байтах паттерн «целое, целое, obj» и записывает каждое попадание. Она находит слишком много. PDF — это контейнерный формат, и три области файла непрозрачны для грамматики объектов: комментарии (§7.2), строки (§7.3.4) и данные потоков (§7.3.8). Любая из них может содержать байты, читающиеся в точности как заголовок объекта, и ни одна из них заголовком объекта не является. Подпись в литеральной строке, оставшийся отладочный комментарий или два мегабайта вывода Flate или DCT — всё это с готовностью произведёт нечто, выглядящее как 99 0 obj

const
  Trap: AnsiString =
    '4 0 obj'#10 +
    '(a caption that mentions 88 0 obj)'#10 +   // literal string, not an object
    'endobj'#10 +
    '% 77 0 obj left over from a debug dump'#10 +  // comment, not an object
    '5 0 obj'#10 +
    '<< /Length 2097152 >>'#10 +
    'stream'#10 +
    { two MiB of compressed bytes that contain the byte sequence
      99 0 obj and, further along, a complete endstream }
    'endstream'#10 +
    'endobj'#10;

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

Однопроходный конечный автомат по блокам 64 КиБ

PDFlibPas сканирует весь файл ровно один раз, блоками по 64 КиБ, с конечным автоматом, построенным на правилах токенов ISO 32000-1 §7.2 и синтаксисе косвенного объекта §7.3.10. Токен заканчивается на пробеле или на одном из символов-разделителей, и заголовок объекта записывается только когда увидена полная последовательность из положительного номера объекта, неотрицательного номера поколения и голого ключевого слова obj. Записанное смещение — это начало токена номера объекта, а именно на него должна указывать запись перекрёстных ссылок, а не позиция ключевого слова obj

function RebuildIsWhiteSpace(Value: Byte): Boolean;
begin
  Result := (Value = 0) or (Value = 9) or (Value = 10) or
            (Value = 12) or (Value = 13) or (Value = 32);
end;

function RebuildIsDelimiter(Value: Byte): Boolean;
begin
  Result := (Value = Ord('(')) or (Value = Ord(')')) or
            (Value = Ord('<')) or (Value = Ord('>')) or
            (Value = Ord('[')) or (Value = Ord(']')) or
            (Value = Ord('{')) or (Value = Ord('}')) or
            (Value = Ord('/')) or (Value = Ord('%'));
end;

Важная деталь в том, что состояние токена и состояние строки переживают границу блока. Заголовок, оказавшийся на стыке линии в 65536 байт, всё равно распознаётся, потому что частичный токен, ожидающая пара целых и флаги нахождения внутри строки — всё переносится в следующий блок. Буферы фиксированы: 64 КиБ для скана, 32 байта для самого длинного токена, который вообще может иметь значение, и единственные массивы, растущие вместе с файлом, — это списки номера объекта, номера поколения и 64-битного смещения, пропорциональные реальному числу объектов, а не размеру файла. На практике скан выполняет последовательные чтения и не более двух явных перемещений по всему документу, что и делает его жизнеспособным на входных данных в несколько сотен мегабайт, обсуждаемых в статье о прямом доступе, слиянии и разделении

Почему потоку нельзя доверять завершение на endstream?

Потому что данные потока — это произвольные байты, а произвольные байты могут случайно сложиться в endstream. Поток, начинающийся после ключевого слова stream, должен пропускаться как непрозрачные данные, пока он действительно не закончится, но первое появление закрывающего ключевого слова — лишь кандидат. PDFlibPas решает это, требуя подтверждения: токен endstream принимается за настоящий конец потока только когда следующий непробельный токен — это самостоятельный endobj, последовательность, которую требует §7.3.8 вокруг объекта-потока. Случайное попадание внутри сжатых данных почти никогда не имеет такого продолжения, поэтому сканер остаётся внутри потока и продолжает движение. Ещё два меньших правила важны не менее. Ключевое слово stream входит в состояние потока только когда это голое ключевое слово, так что объект-имя вроде /stream в словаре никогда его не запускает. И токен obj или trailer учитывается только когда токен не переполнил лимит в 32 байта и не начинался с солидуса. Без этих двух предохранителей словарь ресурсов с неверными именами ключей был бы достаточен, чтобы сбить скан с пути, — а это именно тот класс враждебного входа, что покрыт в заметках о безопасном парсинге ненадёжных PDF

Поиск настоящего конца словаря трейлера

Восстановление объектов — только половина дела, потому что загрузчику всё ещё нужен трейлер, чтобы найти /Root. PDFlibPas запоминает позиции последних 64 найденных при скане ключевых слов trailer и валидирует их в обратном порядке, начиная с самого нового, так что новейший пригодный трейлер побеждает, а случайное ключевое слово, за которым не следует словарь, просто не проходит валидацию и передаёт эстафету предыдущему кандидату. Каждый кандидат читается с ограничением в 1 МиБ, а конец словаря находится отслеживанием вложенной глубины << и >> наряду с экранированием литеральных строк, шестнадцатеричными строками и комментариями

// A naive reader that stops at the first '>>' truncates this trailer,
// and a fixed 2048-byte window can cut it in half on a large one
'trailer'#10 +
'<< /Size 5 /Root 1 0 R' +
'   /Custom << /Text (value >> preserved) >> >>'#10

Отслеживание глубины — не академическое упражнение. Усечённый трейлер, потерявший /Encrypt, превращает восстанавливаемый зашифрованный документ в неоткрываемый, а потеря /Info или частного вложенного словаря молча отбрасывает метаданные, от которых может зависеть нижестоящая система. Если файл зашифрован, восстановленный трейлер — это то, что позволяет пройти обычному пути учётных данных, и семантика повторных попыток та же, что описана в статье о загрузке зашифрованного документа

Что реконструкция не может вам вернуть

Реконструкция — это попытка сделать лучшее из возможного, и честность насчёт её пределов — часть выпуска в продакшн. Три случая проваливаются полностью. Объекты, упакованные внутри потоков объектов (§7.5.7), не видны байтовому сканированию по отдельности, так что если контейнер выживает, а его поток перекрёстных ссылок (§7.5.8) — нет, объекты, которые он содержит, не индексируются реконструкцией. Файл, чьё тело было действительно повреждено, а не просто неверно проиндексировано, произведёт заголовки, чьё содержимое больше не парсится. А файл без восстановимого ключевого слова trailer и без читаемого каталога не имеет ничего, к чему привязать дерево документа, независимо от того, сколько заголовков объектов было найдено

Дублирующиеся номера объектов — интересный промежуточный случай. Инкрементально обновлённый файл законно содержит несколько поколений одного и того же номера объекта, и выживший цепочка перекрёстных ссылок — единственная запись о том, какое из них актуально. У реконструкции этой цепочки нет, поэтому она записывает каждый встреченный заголовок в порядке файла и разрешает по номеру объекта впоследствии. Обычно побеждает более поздняя редакция, что обычно верно, но документ, который был обновлён, а затем частично откачен назад, может вернуться заметно отличающимся от того, что описывал исходный xref. Линеаризованные файлы несут ту же оговорку с другой стороны: разметка первой страницы и таблицы подсказок теряют смысл, как только индекс перегенерирован, так что восстановленный файл следует трактовать как обычный, не линеаризованный документ

var
  Pdf: TPDFlib;
begin
  Pdf := TPDFlib.Create;
  try
    if Pdf.LoadFromFile('truncated-invoice.pdf', '') = 1 then
    begin
      if Pdf.GetDocumentRepaired = 1 then
        LogWarning('xref was unusable; the table was reconstructed');
      if Pdf.PageCount > 0 then
        Pdf.SaveToFile('recovered-invoice.pdf');   // writes a clean xref
    end;
  finally
    Pdf.Free;
  end;
end;

Резервный путь автоматический: PDFlibPas запускает сырой скан всякий раз, когда цепочку перекрёстных ссылок прочитать не получается, а также когда каждая используемая запись заявляет смещение ноль, что является признаком таблицы, которая была записана, но никогда не заполнена. GetDocumentRepaired возвращает 1, когда этот путь был пройден, и его стоит журналировать, а не игнорировать, потому что документ, загруженный через реконструкцию, следует пересохранить в чистый файл, а не оставлять в конвейере, как будто ничего не случилось. Сохранение записывает свежую, согласованную таблицу перекрёстных ссылок, что является дешевейшим возможным решением для каждого нижестоящего потребителя

Путь реконструкции, флаг GetDocumentRepaired и потоковый загрузчик, показанные здесь, — часть PDFlibPas Delphi PDF Library, наряду с API парсинга, рендеринга и подписи, охваченными в других статьях этого блога