Odbudowa uszkodzonych tabel xref PDF: skan odzyskiwania Delphi

Gdy tabela cross-reference PDF jest nieużyteczna, rozwiązaniem jest całkowite jej zignorowanie i odbudowa z ciała pliku. PDFlibPas Delphi PDF Library robi to za pomocą jednoprzebiegowego skanera tokenów, który zapisuje każdy prawdziwy nagłówek obiektu pośredniego, jaki napotka, następnie odzyskuje słownik trailera i przekazuje odbudowaną tabelę normalnemu loaderowi

Co psuje się najpierw, gdy PDF jest uszkodzony?

Tabela cross-reference jest najbardziej kruchą częścią PDF, ponieważ jest jedyną częścią przechowującą bezwzględne przesunięcia bajtowe. ISO 32000-1 §7.5.4 definiuje te wpisy jako dziesięciocyfrowe przesunięcia od początku pliku, a §7.5.5 umieszcza słowo kluczowe startxref blisko końca, wskazując na samą tabelę. Każda z tych liczb zostaje unieważniona przez dowolną edycję przesuwającą bajty. Sesja FTP działająca w trybie tekstowym i tłumacząca CRLF, przerwane pobieranie, wadliwy sektor na współdzielonym dysku, narzędzie wsadowe, które dopisało dane bez poprawnego zapisania aktualizacji przyrostowej: wszystkie one pozostawiają dane obiektów doskonale czytelne, a indeks wskazujący na śmieci

Dlatego „plik jest uszkodzony i jest naprawiany” to tak powszechny komunikat. Bajty niemal zawsze wciąż tam są. To, czego brakuje, to mapa. Odbudowa nie jest więc odzyskiwaniem utraconych danych w sensie kryminalistycznym, jest odbudową indeksu, który można wyprowadzić z ciała, i udaje się znacznie częściej, niż użytkownicy oczekują, ponieważ kosztowna zawartość, drzewa stron oraz czcionki i obrazy, pozostaje nietknięta

Dlaczego skanowanie w poszukiwaniu N 0 obj znajduje fałszywe trafienia?

Naiwna odbudowa przeszukuje surowe bajty w poszukiwaniu wzorca „liczba całkowita, liczba całkowita, obj” i zapisuje każde trafienie. Znajduje za dużo. PDF jest formatem kontenerowym, a trzy regiony pliku są nieprzezroczyste dla gramatyki obiektów: komentarze (§7.2), ciągi znaków (§7.3.4) i dane strumieni (§7.3.8). Każdy z nich może zawierać bajty czytające się dokładnie jak nagłówek obiektu, a żaden z nich nagłówkiem obiektu nie jest. Podpis w literalnym ciągu znaków, pozostawiony komentarz debugowy lub dwa megabajty wyjścia Flate lub DCT — wszystkie chętnie wytworzą coś, co wygląda jak 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;

Każdy fałszywy wpis kosztuje dwa razy. Zanieczyszcza odbudowaną tabelę numerem obiektu, który nie istnieje, i może przesłonić prawdziwy obiekt o tym samym numerze, który pojawia się później w pliku. PDFlibPas dlatego w ogóle nie dopasowuje wzorców. Tokenizuje, co oznacza, że zawsze wie, czy bajty pod kursorem to kod, czy ładunek, a ładunek jest pomijany bez interpretowania

Jednoprzebiegowa maszyna stanów po blokach 64 KiB

PDFlibPas skanuje cały plik dokładnie raz, w blokach po 64 KiB, za pomocą maszyny stanów zbudowanej na zasadach tokenów z ISO 32000-1 §7.2 i składni obiektu pośredniego z §7.3.10. Token kończy się na białym znaku lub jednym ze znaków ograniczających, a nagłówek obiektu jest zapisywany tylko wtedy, gdy widziana została kompletna sekwencja: dodatni numer obiektu, nieujemny numer generacji i gołe słowo kluczowe obj. Zapisane przesunięcie to początek tokenu numeru obiektu, na co musi wskazywać wpis cross-reference, a nie pozycja słowa kluczowego 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;

Istotny szczegół polega na tym, że stan tokenu i stan ciągu znaków przetrwają granicę bloku. Nagłówek, który rozciąga się na granicy 65536 bajtów, jest nadal rozpoznawany, ponieważ częściowy token, oczekująca para liczb całkowitych i flagi wnętrza ciągu wszystkie przenoszą się do następnego bloku. Bufory są stałe: 64 KiB na skan, 32 bajty na najdłuższy token, jaki w ogóle może mieć znaczenie, a jedyne tablice rosnące wraz z plikiem to listy numerów obiektów, numerów generacji i 64-bitowych przesunięć, które są proporcjonalne do rzeczywistej liczby obiektów, a nie do rozmiaru pliku. W praktyce skan wykonuje sekwencyjne odczyty i co najwyżej dwa jawne seeki na całym dokumencie, co czyni go wykonalnym na wejściach o rozmiarze wielu setek megabajtów omawianych w artykule o bezpośrednim dostępie przy scalaniu i dzieleniu

Dlaczego strumieniowi nie można zaufać, że zakończy się na endstream?

Ponieważ dane strumienia to dowolne bajty, a dowolne bajty mogą przypadkiem złożyć się na endstream. Strumień zaczynający się po słowie kluczowym stream musi być pomijany jako nieprzezroczyste dane, aż faktycznie się zakończy, ale pierwsze wystąpienie zamykającego słowa kluczowego jest tylko kandydatem. PDFlibPas rozwiązuje to, wymagając potwierdzenia: token endstream jest akceptowany jako prawdziwy koniec strumienia tylko wtedy, gdy następny token niebędący białym znakiem to samodzielny endobj, sekwencja wymagana przez §7.3.8 wokół obiektu strumienia. Przypadkowe trafienie wewnątrz skompresowanych danych niemal nigdy nie ma takiej kontynuacji, więc skaner pozostaje wewnątrz strumienia i kontynuuje. Dwie mniejsze zasady mają równie duże znaczenie. Słowo kluczowe stream wchodzi w stan strumienia tylko wtedy, gdy jest gołym słowem kluczowym, więc obiekt nazwy taki jak /stream w słowniku nigdy go nie wyzwala. A token obj lub trailer jest honorowany tylko wtedy, gdy token nie przekroczył limitu 32 bajtów i nie zaczynał się od ukośnika. Bez tych dwóch zabezpieczeń słownik zasobów z niewłaściwymi nazwami kluczy wystarczyłby, aby zboczyć skan, co jest dokładnie tą klasą wrogich danych wejściowych omówioną w notatkach o bezpiecznym parsowaniu niezaufanego PDF

Znajdowanie prawdziwego końca słownika trailera

Odzyskanie obiektów to tylko połowa zadania, ponieważ loader nadal potrzebuje trailera, aby znaleźć /Root. PDFlibPas zapamiętuje ostatnie 64 pozycje słowa kluczowego trailer znalezione podczas skanowania i waliduje je wstecz, od najnowszych, więc wygrywa najnowszy użyteczny trailer, a przypadkowe słowo kluczowe, po którym nie następuje słownik, po prostu nie przechodzi walidacji i spada do poprzedniego kandydata. Każdy kandydat jest odczytywany z limitem 1 MiB, a koniec słownika jest lokalizowany przez śledzenie zagnieżdżonej głębokości << i >> wraz z ucieczkami literalnych ciągów znaków, ciągami szesnastkowymi i komentarzami

// 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

Śledzenie głębokości nie jest akademickie. Obcięty trailer, który traci /Encrypt, zamienia odzyskiwalny zaszyfrowany dokument w niemożliwy do otwarcia, a utrata /Info lub niestandardowego pod-słownika po cichu odrzuca metadane, od których może zależeć system dalszy w łańcuchu. Jeśli plik jest zaszyfrowany, odzyskany trailer to to, co pozwala uruchomić normalną ścieżkę uwierzytelniania, a semantyka ponawiania jest taka sama jak opisana w artykule o wczytywaniu zaszyfrowanych dokumentów

Czego odbudowa nie może ci zwrócić

Odbudowa jest podejściem best-effort, a bycie szczerym co do jej ograniczeń jest częścią jej wdrożenia. Trzy przypadki zawodzą całkowicie. Obiekty zapakowane wewnątrz strumieni obiektów (§7.5.7) nie są indywidualnie widoczne dla skanu bajtowego, więc jeśli kontener przetrwa, ale jego strumień cross-reference (§7.5.8) nie, obiekty, które trzyma, nie są indeksowane przez odbudowę. Plik, którego ciało zostało rzeczywiście uszkodzone, a nie tylko błędnie zindeksowane, wytworzy nagłówki, których zawartość już się nie parsuje. A plik bez odzyskiwalnego słowa kluczowego trailer i bez czytelnego katalogu nie ma niczego, do czego mógłby zakotwiczyć drzewo dokumentu, niezależnie od tego, ile nagłówków obiektów znaleziono

Zduplikowane numery obiektów to ciekawy przypadek pośredni. Przyrostowo zaktualizowany plik zgodnie z prawem zawiera kilka generacji tego samego numeru obiektu, a przetrwały łańcuch cross-reference jest jedynym zapisem tego, który był aktualny. Odbudowa nie ma tego łańcucha, więc zapisuje każdy napotkany nagłówek w kolejności pliku i rozwiązuje po numerze obiektu później. Zwykle wygrywa późniejsza wersja, co zwykle jest poprawne, ale dokument, który został zaktualizowany, a następnie częściowo cofnięty, może wrócić subtelnie inny niż to, co opisywał oryginalny xref. Zlinearyzowane pliki niosą to samo zastrzeżenie z drugiej strony: układ pierwszej strony i tabele hint stają się bezsensowne po regeneracji indeksu, więc naprawiony plik powinien być traktowany jak zwykły, niezlinearyzowany dokument

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;

Zapasowa ścieżka jest automatyczna: PDFlibPas uruchamia surowy skan zawsze, gdy łańcuch cross-reference nie może zostać odczytany, a także gdy każdy wpis w użyciu twierdzi, że ma przesunięcie zero, co jest sygnaturą tabeli, która została zapisana, ale nigdy nie wypełniona. GetDocumentRepaired zwraca 1, gdy ta ścieżka została uruchomiona, i warto to zalogować, a nie zignorować, ponieważ dokument, który wczytał się przez odbudowę, powinien zostać ponownie zapisany do czystego pliku, zamiast pozostać w pipeline, jakby nic się nie stało. Zapisanie go tworzy świeżą, spójną tabelę cross-reference, co jest najtańszą możliwą naprawą dla każdego dalszego konsumenta

Ścieżka odbudowy, flaga GetDocumentRepaired i pokazany tutaj loader strumieniowy są częścią PDFlibPas Delphi PDF Library, obok API parsowania, renderowania i podpisywania omówionych gdzie indziej na tym blogu