Drzewa nazw PDFlibPas: cykle, złe Limits i ogromne liście

PDFlibPas, biblioteka PDF losLab dla Delphi, obchodzi drzewa nazw i drzewa liczb PDF jawnym stosem i zbiorem odwiedzin od v3.539.45, więc cykliczne /Kids, wspólne dzieci i drzewa tysiące poziomów głębokie nie wyczerpują już stosu wywołań ani nie powielają wpisów. Od v3.539.51 brakująca, zniekształcona albo odwrócona para /Limits nigdy nie ukryje gałęzi trzymającej klucz. Nazwane cele, etykiety stron, załączniki i JavaScript na poziomie dokumentu czytają wszystkie przez te dwie ścieżki kodu, co czyni je częścią powierzchni ataku każdego PDF-a, którego nie wyprodukowałeś sam

Wyzwalacz rzadko bywa egzotyczny. Fuzzer, wrogi upload albo zbugowany zapis przyrostowy wpisuje wpis /Kids wskazujący z powrotem na przodka, a rekurencyjny obchodziacz zdycha przepełnieniem stosu na pliku o rozmiarze dwóch kilobajtów. Cichszą awarią jest wyszukiwanie, które ufa popsutej tablicy /Limits i zgłasza „nie znaleziono" dla celu, który jest tam jak na dłoni

Gdzie w PDF pojawiają się drzewa nazw i drzewa liczb?

Drzewa nazw i drzewa liczb pojawiają się wszędzie tam, gdzie PDF mapuje duży zbiór kluczy na obiekty, a PDFlibPas czyta co najmniej cztery z nich przez publiczne API. ISO 32000-1 §7.9.6 definiuje drzewo nazw (klucze napisowe, tabela 36), a §7.9.7 drzewo liczb (klucze całkowite, tabela 37). Oba to w miarę zbalansowane drzewa, których korzeń i węzły pośrednie niosą /Kids, których liście niosą posortowane pary klucz/wartość w /Names albo /Nums, a których węzły niekorzenne niosą dwuelementową tablicę /Limits z najmniejszym i największym kluczem pod sobą

Drzewo	Gdzie mieszka	Specyfikacja	API odczytu w PDFlibPas
Nazwane cele	/Dests w słowniku nazw	§12.3.2.3	GetNamedDestination, potem GetDestPage / GetDestType
Etykiety stron	/PageLabels w katalogu (drzewo liczb)	§12.4.2	GetPageLabel
Załączniki	/EmbeddedFiles w słowniku nazw	§7.7.4, §7.11.4	EmbeddedFileCount, GetEmbeddedFileStrProperty
JavaScript na poziomie dokumentu	/JavaScript w słowniku nazw	§7.7.4	GlobalJavaScriptCount, GlobalJavaScriptPackageName

Dwa szczegóły w tej tabeli łatwo przeoczyć. Nazwane cele mają też starszą postać z PDF 1.1, zwykły słownik /Dests w katalogu kluczowany obiektami nazw, a GetNamedDestination sprawdza najpierw ten słownik, zanim zejdzie do drzewa nazw z PDF 1.2. A GetDocJavaScript w ogóle nie jest czytnikiem drzew nazw: zwraca skrypty przypięte do wyzwalaczy dokumentu w słowniku /AA katalogu (WS, DS, WP, DP, DC), podczas gdy nazwane pakiety skryptów uruchamiane przy otwarciu dokumentu mieszkają w drzewie nazw /JavaScript

Każdy bajt tych struktur pochodzi z pliku. Specyfikacja mówi, co zapisujący ma wyprodukować; nie może zablokować czytelnikowi przyjęcia czegoś innego — to sama lekcja, która stoi za utwardzaniem parsera PDF w Pascalu wobec złośliwych plików, zastosowana tutaj do kształtu drzewa zamiast rozmiarów buforów

Dlaczego cykliczna tablica /Kids wywala rekurencyjnego obchodziacza drzewa?

Cykliczna tablica /Kids wywala rekurencyjnego obchodziacza, bo nic w rekurencji nie zauważa, że dany węzeł już widziała, więc dziecko odwołujące się do własnego przodka zamienia skończony plik w nieskończone schodzenie. Przed v3.539.45 NameTreeLookup, NumTreeLookup, EnumNumTree i wewnętrzny TPDFNameTree.ProcessNode wołali się wszyscy raz na dziecko. Pojedyncze samoodwołanie wystarczało, żeby zakończyć proces, a legalne, ale bardzo głębokie drzewo mogło zrobić to samo bez żadnego cyklu

Łagodniejszy wariant psuje wyniki zamiast wywalać. Gdy dwa wpisy /Kids odwołują się do tego samego liścia, naiwna enumeracja odwiedza go dwa razy, a licznik załączników albo lista pakietów skryptów raportuje wpisy, które nie istnieją

Poprawka zastępuje rekurencję jawnym stosem LIFO na stercie i zbiorem odwiedzin kluczowanym tożsamością słowników. Węzeł jest zaznaczany w chwili zdjęcia, nie włożenia, więc cykliczna referencja może posiedzieć na stosie chwilę, ale jest wyrzucana w momencie wypłynięcia. Każdy odrębny węzeł rozwija swoje dzieci dokładnie raz, co ogranicza całkowitą pracę do liczby odrębnych słowników plus łącznej długości ich tablic /Kids. Głębokość przestaje mieć znaczenie: łańcuch o 4096 poziomach to po prostu 4096 iteracji pętli i 4096 wpisów w hash secie

Kolejność jednak wciąż ma znaczenie i stos trzeba karmić od tyłu, żeby ją utrzymać. Dzieci są wpychane od ostatniego indeksu do pierwszego, więc najdalsze z lewej dziecko jest zdejmowane pierwsze, a liście wychodzą w tej samej kolejności od lewej do prawej, w jakiej napisał je producent. GetPageLabel na tym polega: przechodzi każdy wyliczony zakres i stosuje ostatni, którego indeks startowy jest mniejszy bądź równy stronie, więc odwrócenie enumeracji po cichu dałoby stronie 200 styl przypisów wstępnych. Szkielet poniżej pokazuje wzorzec na abstrakcyjnym typie węzła, niezależnie od jakiegokolwiek modelu obiektów PDF

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // puste w liściu
    Keys: TArray<string>;      // klucze liścia, posortowane przez grzecznego producenta
    Values: TArray<Integer>;   // równoległe do Keys
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// /Limits to podpowiedź: gałąź może ściąć tylko dobrze uformowana, uporządkowana para
function LimitsExclude(Node: TTreeNode; const Key: string): Boolean;
begin
  Result := Node.HasLimits and (Node.LoKey <= Node.HiKey) and
    ((Key < Node.LoKey) or (Key > Node.HiKey));
end;

function FindValue(Root: TTreeNode; const Key: string;
  out Value: Integer): Boolean;
var
  Pending: TList<TTreeNode>;
  Visited: TDictionary<TTreeNode, Byte>;
  Node: TTreeNode;
  I: Integer;
begin
  Result := False;
  Value := 0;
  if Root = nil then
    Exit;
  Pending := TList<TTreeNode>.Create;
  Visited := TDictionary<TTreeNode, Byte>.Create;
  try
    Pending.Add(Root);
    while Pending.Count > 0 do
    begin
      Node := Pending[Pending.Count - 1];
      Pending.Delete(Pending.Count - 1);
      if Visited.ContainsKey(Node) then
        Continue;                      // cykl albo wspólne dziecko: już to widzieliśmy
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // Wpychaj od prawej do lewej, żeby lewe dziecko było zdejmowane pierwsze
        for I := High(Node.Kids) downto 0 do
          if (Node.Kids[I] <> nil) and not LimitsExclude(Node.Kids[I], Key) then
            Pending.Add(Node.Kids[I]);
      end
      else
        for I := 0 to High(Node.Keys) do
          if (Node.Keys[I] = Key) and (I <= High(Node.Values)) then
          begin
            Value := Node.Values[I];
            Exit(True);
          end;
      // Pudło w tym liściu to nie werdykt: zdejmuj dalej rodzeństwo
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

Dlaczego wyszukiwanie nie może stanąć na pierwszej pasującej gałęzi?

Wyszukiwanie nie może stanąć na pierwszej gałęzi, której zakres pasuje, bo zakresy /Limits w prawdziwym pliku potrafią się nakładać albo kłamać, a gałąź, która rości sobie klucz, niekoniecznie jest gałęzią, która go trzyma. Wyszukiwania sprzed v3.539.45 stawiały flagę Found na pierwszym dziecku, którego /Limits pokrywało klucz, schodziły do niego i nigdy nie oglądały innego rodzeństwa. Jeśli to dziecko okazywało się puste, nieaktualne albo pętlą z powrotem do korzenia, odpowiedzią było nil, nawet gdy następne rodzeństwo trzymało klucz

Przepisany FindTreeValue, który teraz napędza i NameTreeLookup, i NumTreeLookup, wpycha każde dziecko, którego zakres nie wyklucza klucza, i zdejmuje ze stosu, dopóki nie znajdzie trafienia albo nie opróżni stosu. Pudło w jednym liściu to po prostu pudło w jednym liściu. W dobrze uformowanym drzewie nic to nie kosztuje; w uszkodzonym kosztuje kilka wizyt węzłów więcej i zwraca właściwą odpowiedź

Przeszukiwanie liścia trzyma tę samą filozofię. ISO 32000-1 wymaga, żeby klucze w tablicy /Names były posortowane według wartości bajtów, więc liść jest najpierw przeszukiwany wyszukiwaniem binarnym. Gdy ono zawiedzie, PDFlibPas wraca do liniowego skanu par, bo liść w złej kolejności uczyniłby inaczej obecnym klucz niewidzialnym. Sortowanie to fast path, nie filtr

Wyszukiwanie odmawia też zgadywania przy jednej sprzeczności strukturalnej. Tabela 36 pozwala węzłowi nieść /Kids albo /Names, nigdy oba, a ścieżka wyszukiwania traktuje węzeł niosący oba jako zniekształcony i pomija go, zamiast wybierać jedną interpretację. Ścieżki enumeracyjne, takie jak EnumNumTree, są pobłażliwsze i idą za /Kids, gdy są oba

Do czego czytelnik może ufać /Limits?

Czytelnik może ufać /Limits tylko po to, żeby pominąć pracę, nigdy po to, żeby orzec nieobecność klucza, i tylko przy dobrze uformowanej parze. Tabela 36 mówi, że węzły pośrednie i liście mają nieść /Limits jako dwuelementową tablicę z najmniejszym i największym kluczem, ale w praktyce wpis znika po ręcznych edycjach, trzyma liczby w drzewie nazw albo przychodzi z zamienionymi granicami. PDFlibPas v3.539.45 i v3.539.51 rozstrzygają każdy przypadek tak samo: jeśli zakresu nie da się przeczytać jako uporządkowanej pary właściwego typu, dziecko pozaje wyszukiwalne

• Brakujące /Limits: stary test zakresu zwracał False i dziecko było pomijane w całości, więc producent, który zapomniał wpisu, czynił całe swoje poddrzewo nieosiągalnym. Od v3.539.45 dziecko jest przeszukiwane
• Zły typ albo zła długość, jak liczby w drzewie nazw albo tablica jednoelementowa: traktowane dokładnie jak brakujący wpis od v3.539.45
• Odwrócone granice, takie jak [(Z) (A)] albo [9 0]: v3.539.45 wciąż ich używało, a żaden klucz nie spełni Lo <= Key <= Hi, gdy Lo > Hi, więc gałąź była wykluczana przy każdym wyszukiwaniu. Od v3.539.51 zakres służy do ścinania tylko wtedy, gdy jego dolna granica nie przekracza górnej
• Dobrze uformowane, uporządkowane i poprawne: używane do ścięcia gałęzi, o to przecież chodzi w tym wpisie

W każdym przypadku o wyniku decydują prawdziwe klucze. Wrogi /Limits może zmusić PDFlibPas do odwiedzenia więcej węzłów niż trzeba, ale zniekształcony już nie sprawi, że istniejący cel zniknie. Po stronie wołającego nic się nie zmienia: GetNamedDestination zwraca 0, gdy nazwy naprawdę nie ma, a w przeciwnym razie ID celu, a funkcje celów jadą z tym dalej

uses
  PDFlibrary;

procedure LookUpDestination(const FileName, DestName: string);
var
  Lib: TPDFlib;
  DestID: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile(FileName, '') <> 1 then
    begin
      WriteLn('Load failed, error ', Lib.LastErrorCode);
      Exit;
    end;
    // Najpierw /Dests w katalogu (PDF 1.1), potem drzewo nazw /Dests
    DestID := Lib.GetNamedDestination(DestName);
    if DestID = 0 then
      WriteLn('No destination named ', DestName)
    else if Lib.GetDestPage(DestID) = 0 then
      WriteLn(DestName, ' exists but does not resolve to a page')
    else
      WriteLn(DestName, ' -> page ', Lib.GetDestPage(DestID),
        ', view type ', Lib.GetDestType(DestID));  // 1 = XYZ, 2 = Fit ...
  finally
    Lib.Free;
  end;
end;

Uruchomiona na ręcznie zbudowanym pliku, którego korzeń /Dests ma jedno dziecko zapętlające się z powrotem do korzenia pod zakresem [(a) (z)] i drugie dziecko trzymające prawdziwy wpis pod odwróconymi granicami [(z) (a)], ta procedura rozwiązuje cel do strony 2 z typem widoku 2 (Fit). Przed v3.539.45 to samo wyszukiwanie zwracało 0, bo zapętlone dziecko rościło klucz pierwsze, a poszukiwanie nigdy nie dochodziło do jego rodzeństwa; samo v3.539.45 wciąż zwracało 0, bo odwrócony zakres wykluczał prawdziwy liść. Jeśli czytasz potem konspekt wskazujący na te cele, artykuł siostrzany o czytaniu akcji zakładek i adnotacji PDF w Delphi omawia stronę akcji

Jak liść z 32 769 nazwami wywalił TPDFNameTree?

Liść z 32 769 parami nazwa/wartość wywalił TPDFNameTree, bo jego wewnętrzny FindIndex upakowywał dwie liczby w jednym Integer 32-bitowym: pozycję liścia na wewnętrznej liście tablic w starszych 16 bitach i offset wpisu wewnątrz tablicy /Names tego liścia w młodszych 16 bitach. Każda para zajmuje dwa sloty tablicy, więc para nr 32 769, o indeksie 32 768, startuje na offsecie 65 536, czyli $10000. Ta wartość przenosi się do starszej połowy, a dekoder czytał ją z powrotem jako offset 0 w następnym liściu

TPDFNameTree to klasa stojąca za załącznikami, globalnymi pakietami JavaScript i zapisami nazwanych celów, co czyni konsekwencje konkretnymi. W drzewie jedno-liściowym nie ma następnego liścia, więc FindKey i DeleteKey indeksowały za koniec listy liści; w drzewie wielo-liściowym zwracały albo kasowały pierwszą parę następnego liścia zamiast tej żądanej. W międzyczasie HasKey robił własny skan i raportował klucz jako obecny, więc klasa przeczyła sama sobie. Generowana dokumentacja z jednym nazwanym celem na symbol API przekracza 32 768 wpisów bez wysiłku, a niektórzy producenci zapisują je wszystkie w jednym płaskim liściu

Od v3.539.45 FindIndex zwraca indeks tablicy przez osobny parametr out, a pełny offset wpisu jako swój wynik, więc żadna z wartości nie jest obcinana. To samo wydanie dokręciło dwóch sąsiadów. KeyName liczy i zwraca teraz wyłącznie prawdziwe klucze napisowe i zwraca pusty napis dla indeksu 0 albo niższego, gdzie wcześniej rzutował cokolwiek, co stało za niewłaściwym kluczem. HasKey nie traktuje już klucza numerycznego ani innego niewłaściwego jako pustej nazwy. Dla liścia takiego jak [(Valid) 42 123 456] HasKey('') to teraz False, a KeyName(2) zwraca pusty napis

procedure AuditTrees(const FileName: string);
var
  Lib: TPDFlib;
  I: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile(FileName, '') <> 1 then
      Exit;
    // Drzewo liczb /PageLabels; pliki bez niego zwracają gołe numery stron
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // Drzewo nazw /EmbeddedFiles; indeksy od 1, klucze nietekstowe pomijane
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // nazwa, typ MIME
    // Drzewo nazw /JavaScript: wypisz nazwy pakietów, niczego nie wykonuj
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

Na tym samym ręcznie budowanym pliku, którego korzeń /PageLabels wypisuje jeden liść dwa razy i odwołuje się do samego siebie, ten audyt drukuje i i A-1 dla dwóch stron, każdy zakres po jednym razie, oraz jedyny pakiet skryptów z drzewa /JavaScript, które też wskazuje z powrotem na własny korzeń. Strona zapisu etykiet stron ma własną historię z korzeniami /Kids, opisaną w naprawianiu etykiet stron PDF trzymanych w drzewach liczb /Kids; AddPageLabels spłaszcza taki korzeń przed wstawieniem i polega na tej samej enumeracji EnumNumTree, którą opisano tutaj

Czego to utwardzenie wciąż nie gwarantuje?

Utwardzenie gwarantuje zakończenie, stabilną kolejność i poprawne wyniki dla drzew, których prawdziwe klucze są nietknięte; nie sprawi, że uszkodzone drzewo znaczy to, co zamierzał jego autor. Kilka ograniczeń warto znać, zanim się na nim zbudujesz

• Zbiór odwiedzin działa na tożsamości obiektów. Dwa odrębne słowniki o identycznej treści to dwa węzły, więc producent kopiujący liść zamiast się do niego odwoływać wciąż wyprodukuje zduplikowane wpisy
• Dobrze uformowane, uporządkowane, ale kłamliwe /Limits wciąż ścina. Czytelnik używający zakresów jako optymalizacji nie może być zarazem odporny na zakres kłamiący przekonująco; jedyna alternatywa to ignorować /Limits w całości i skanować każdy liść
• Enumeracja zachowuje kolejność z pliku, ale nie sortuje. GetPageLabel stosuje ostatni wyliczony zakres na poziomie strony albo poniżej, więc producent zapisujący zakresy w nieuporządkowanej kolejności dostaje semantykę kolejności z pliku
• Pamięć rośnie z liczbą odrębnych węzłów i wpisów. Przechodzenie dodaje listę i hash set, nic więcej, ale drzewo nazw na 100 MB pozostaje drzewem nazw na 100 MB także po sparsowaniu
• Zduplikowane klucze wewnątrz jednego liścia nie są raportowane. Wyszukiwanie binarne zwraca pierwszą trafioną pasującą parę; liniowy fallback zostawia ostatnie trafienie ze skanu

Ściąga: czytanie drzew PDF z plików niezaufanych

• Zaktualizuj do v3.539.45 lub nowszego dla odpornego na cykle i stos przechodzenia drzew nazw i drzew liczb, a do v3.539.51 lub nowszego, żeby odwrócone /Limits nie ukrywały już kluczy
• Traktuj 0 z GetNamedDestination jako „nieobecny", a 0 z GetDestPage jako „obecny, ale bezużyteczny"
• Używaj GlobalJavaScriptCount i GlobalJavaScriptPackageName dla drzewa nazw /JavaScript; GetDocJavaScript czyta zamiast tego wyzwalacze /AA katalogu
• Indeksuj załączniki i pakiety skryptów od 1 do liczby, którą raportuje biblioteka; niewłaściwe klucze nie są liczone
• We własnym kodzie drzew zaznaczaj węzły jako odwiedzone przy zdjęciu, wpychaj dzieci w odwrotnej kolejności i pozwól /Limits ściąć gałąź tylko, gdy to dobrze otypowana, uporządkowana para

Narzędzia preflight, archiwizery i przeglądarki czytają te drzewa, zanim jakakolwiek strona zostanie wyrenderowana, więc muszą przeżyć cokolwiek przyjdzie z kolejki uploadu. Czytniki drzew opisane powyżej jadą w pakiecie z PDFlibPas, biblioteką PDF dla Delphi, która buduje się zarówno w Delphi, jak i Free Pascal