PDFlibPas name trees: cykly, zlé /Limits a obrovské listy

PDFlibPas, losLab PDF Library for Delphi, prechádza PDF name trees a number trees od v3.539.45 s explicitným stackom a množinou navštívených, takže cyklické /Kids, zdieľaní potomkovia a stromy tisíce úrovní hlboké už nevyčerpajú call stack ani nezdvoja položky. Od v3.539.51 chýbajúci, deformovaný alebo prevrátený pár /Limits nikdy neschovejú vetvu, ktorá kľúč drží. Named destinations, page labels, prílohy aj document-level JavaScript všetky čítajú cez tieto dve kódové cesty, čo z nich robí súčasť attack surface každého PDF, ktoré ste sami nevyrobili

Spúšťač je zriedka exotický. Fuzzer, nepriateľský upload alebo bugnutý inkrementálny zápis produkuje položku /Kids ukazujúcu späť na predka a rekurzívny walker umrie stack overflowom na dvojkilobajtovom súbore. Tichšie zlyhanie je vyhľadávanie, ktoré verí pokazenému poľu /Limits a hlási „not found“ pre destináciu, ktorá tam zjavne je

Kde sa name trees a number trees v PDF vyskytujú?

Name trees a number trees sa objavujú všade, kde PDF mapuje veľkú sadu kľúčov na objekty a PDFlibPas číta aspoň štyri z nich cez verejné API. ISO 32000-1 §7.9.6 definuje name tree (reťazcové kľúče, Table 36) a §7.9.7 number tree (celočíselné kľúče, Table 37). Oba sú vyrovnané-ish stromy, ktorých koreň a medziuzly nesú /Kids, listy nesú utriedené páry kľúč/hodnota v /Names alebo /Nums a ne-koreňové uzly nesú dvojprvkové pole /Limits s najmenším a najväčším kľúčom pod nimi

Strom	Kde býva	Špecifikácia	Čítacie API PDFlibPas
Named destinations	/Dests v name slovníku	§12.3.2.3	GetNamedDestination, potom GetDestPage / GetDestType
Page labels	/PageLabels v katalógu (number tree)	§12.4.2	GetPageLabel
Prílohy	/EmbeddedFiles v name slovníku	§7.7.4, §7.11.4	EmbeddedFileCount, GetEmbeddedFileStrProperty
Document-level JavaScript	/JavaScript v name slovníku	§7.7.4	GlobalJavaScriptCount, GlobalJavaScriptPackageName

Dva detaily v tej tabuľke sa dajú ľahko prehliadnúť. Named destinations majú aj staršiu formu z PDF 1.1, holý slovník /Dests v katalógu kľúčovaný name objektmi a GetNamedDestination kontroluje ten slovník najprv, skôr než zlezne do name tree z PDF 1.2. A GetDocJavaScript nie je vôbec čítač name tree: vracia skripty pripnuté na document triggre v katalógovom slovníku /AA (WS, DS, WP, DP, DC), zatiaľ čo pomenované skriptové balíky bežiace pri otvorení dokumentu bývajú v name tree /JavaScript

Každý bajt tých štruktúr pochádza zo súboru. Špecifikácia hovorí, čo má producent vyrábať; nedokáže zabrániť čítačovi prijať niečo iné, čo je tá istá lekcia ako za posilňovaním Pascal PDF parsera proti škodlivým súborom, tu aplikovaná na tvar stromu namiesto veľkostí bufferov

Prečo cyklické pole /Kids rozbije rekurzívneho walker stromu?

Cyklické pole /Kids rozbije rekurzívneho walker a preto, lebo nič v rekurzii si nevšimne, že uzol už videlo, takže potomok odkazujúci na vlastného predka zmení konečný súbor na nekonečný zostup. Pred v3.539.45 volali NameTreeLookup, NumTreeLookup, EnumNumTree aj interné TPDFNameTree.ProcessNode samy seba raz za každého potomka. Jedina sebarezistencia stačila na ukončenie procesu a legitímny, ale extrémne hlboký strom dokázal to isté bez akéhokoľvek cyklu

Miernejšia varianta korumpuje výsledky namiesto pádu. Keď dve položky /Kids referencujú ten istý list, naivná enumerácia ho navštívi dvakrát a počet príloh alebo zoznam skriptových balíkov hlási položky, ktoré neexistujú

Oprava mení rekurziu na explicitný last-in, first-out stack na heap a množinu navštívených kľúčovanú identitou slovníka. Uzol sa označí v momente vypojenia, nie pri prijatí, takže cyklická referencia môže chvíľu sedieť na stacku, ale zahodí sa, akonáhle vyjde naspäť nahor. Každý odlišný uzol expanduje svojich potomkov presne raz, čo ohraničuje celkovú prácu počtom odlišných slovníkov plus celkovou dĺžkou ich polí /Kids. Hĺbka prestane hrať rolu: reťaz 4 096 úrovní je len 4 096 iterácií slučky a 4 096 položiek v hash množine

Poradie aj naďalej hrá rolu a stack sa musí kŕmiť odzadu, aby ho uchovalo. Potomkovia sa tlačia od posledného indexu po prvý, takže najľavejší potomok sa vypojí ako prvý a listy vychádzajú v tom istom poradí zľava doprava, v akom ich zapisuje producent. GetPageLabel na tom závisí: prechádza každý enumerovaný rozsah a aplikuje posledný, ktorého štartovací index je na strane alebo pod ňou, takže prevrátená enumerácia by potichu dala strane 200 štýl prednej záložky. Kostra nižšie ukazuje vzor na abstraktnom uzlovom type, nezávisle od akéhokoľvek PDF objektového modelu

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // prázdne na liste
    Keys: TArray<string>;      // kľúče listu, utriedené slušným producentom
    Values: TArray<Integer>;   // paralelne ku Keys
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// /Limits je hint: vetvu môže orezať len dobre utvorený, utriedený pár
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;                      // cyklus alebo zdieľaný potomok: už videno
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // Tlačte sprava doľava, aby sa najľavejší potomok vypojil ako prvý
        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;
      // Minul v tomto liste nie je rozsudok: pokračujte vo vypojení súrodencov
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

Prečo nesmie vyhľadávanie skončiť na prvej zhodnej vetve?

Vyhľadávanie nesmie skončiť na prvej vetve, ktorej rozsah sedí, lebo rozsahy /Limits v reálnom súbore sa môžu prekrývať alebo klamať a vetva, ktorá si kľúč nárokuje, nie je nutne vetva, ktorá ho drží. Vyhľadávania pred v3.539.45 nastavili príznak Found na prvom potomkovi, ktorého /Limits kľúč pokrýval, zlezli do neho a nikdy nepozreli na iného súrodenca. Keď ten potomok vyšiel prázdny, zastaralý alebo ako slučka späť ku koreňu, odpoveďou bolo nil dokonca aj vtedy, keď úplne ďalší súrodenec kľúč držal

Rewritnuté FindTreeValue, ktoré teraz nosí na chrbte NameTreeLookup aj NumTreeLookup, tlačí každého potomka, ktorého rozsah kľúč nevylučuje, a vypojáva, kým nájde zhodu alebo sa stack nevyprázdni. Minul vo vnútri jedného listu je len minul vo vnútri jedného listu. V dobre utvorenom strome to nič nestojí; v poškodenom stojí pár ďalších návštev uzlov a vráti správnu odpoveď

Hľadanie v liste sa drží tej istej filozofie. ISO 32000-1 vyžaduje, aby kľúče v poli /Names boli utriedené podľa bajtovej hodnoty, takže list sa najprv prehľadá binárnym vyhľadávaním. Ak to zlyhá, PDFlibPas prepadne na lineárny prechod párov, lebo neusporiadaný list by inak spravil prítomný kľúč neviditeľným. Utriedenie je rýchla cesta, nie filter

Vyhľadávanie sa navyše odmieta hádať pri jednom štrukturálnom rozpore. Table 36 dovoľuje uzlu niesť buď /Kids, alebo /Names, nikdy oboje, a vyhľadávacia cesta berie uzol nesúci oboje ako deformovaný a preskočí ho namiesto výberu jedného výkladu. Enumeračné cesty ako EnumNumTree sú zhovievavejšie a pri oboch prítomných nasledujú /Kids

Načo smie čítač /Limits veriť?

Čítač smie /Limits veriť len na preskočenie práce, nikdy na rozhodnutie, že kľúč chýba, a to len keď je pár dobre utvorený. Table 36 hovorí, že medziuzly aj listy majú niesť /Limits ako dvojprvkové pole najmenšieho a najväčšieho kľúča, ale v praxi tá položka po ruke editáciách mizne, drží čísla v name tree alebo prichádza s vymenenými hranicami. PDFlibPas v3.539.45 a v3.539.51 riešia každý prípad rovnako: ak sa rozsah nedá prečítať ako utriedený pár správneho typu, potomok ostanú prehľadávateľný

• Chýbajúce /Limits: stará rozsahová kontrola vrátila False a potomok sa preskočil úplne, takže producent, ktorý zabudol na položku, spravil celý svoj podstrom nedostupný. Od v3.539.45 sa potomok prehľadáva
• Zlý typ alebo zlá dĺžka, ako čísla v name tree alebo jednoprvkové pole: od v3.539.45 brané presne ako chýbajúca položka
• Prevrátené hranice ako [(Z) (A)] alebo [9 0]: v3.539.45 ich ešte používal a žiadny kľúč nemôže splniť Lo <= Key <= Hi, keď Lo > Hi, takže vetva bola vylúčená pre každé vyhľadávanie. Od v3.539.51 sa rozsah na prerezávanie používa len vtedy, keď spodná hranica neprevyšuje hornú
• Dobre utvorený, utriedený a správny: používa sa na preskočenie vetvy, čo je celý zmysel položky

O výsledku v každom prípade rozhodujú skutočné kľúče. Nepriateľské /Limits dokáže prinútiť PDFlibPas navštíviť viac uzlov, než je treba, ale deformované už nedokáže spraviť zmiznúť existujúcu destináciu. Zo strany volajúceho sa nič nemení: GetNamedDestination vracia 0, keď meno naozaj chýba, a destination ID inak, a destination funkcie vedenie preberajú

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;
    // Najprv katalógový /Dests (PDF 1.1), potom name tree /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;

Spustené proti ručne postavenému súboru, ktorého koreň /Dests má jednoho potomka slučiaceho sa späť ku koreňu pod rozsahom [(a) (z)] a druhého potomka držiaceho skutočnú položku pod prevrátenými limitami [(z) (a)], táto procedúra vyrieši destináciu na stranu 2 s view typom 2 (Fit). Pred v3.539.45 vrátilo to isté vyhľadávanie 0, lebo slučiaci potomok si kľúč nárokoval ako prvý a hľadanie sa nikdy nedostalo k jeho súrodencovi; samotné v3.539.45 stále vrátilo 0, lebo prevrátený rozsah vylúčil skutočný list. Ak potom čítate osnovu ukazujúcu na tieto destinácie, akciu stranu pokrýva súrodenecký článok o čítaní PDF bookmark a annotation akcií v Delphi

Ako list s 32 769 menami rozbil TPDFNameTree?

List s 32 769 pármi meno/hodnota rozbil TPDFNameTree preto, lebo jeho interné FindIndex zbalovalo dve čísla do jedného 32-bitového Integer: pozíciu listu v internej array liste do vysokých 16 bitov a offset položky v poli /Names tohto listu do nízkych 16 bitov. Každý pár zaberá dve sloty poľa, takže 32 769. pár, pár index 32 768, začína na ofsete 65 536, čo je $10000. Tá hodnota sa prenesie do vysokej polovice a dekodér ju prečítal späť ako offset 0 v ďalšom liste

TPDFNameTree je trieda za prílohami, globálnymi JavaScript balíkmi a zápismi named destinácií, čo robí následky konkrétnymi. V jedinolistovom strome žiadny ďalší list neexistuje, takže FindKey a DeleteKey indexovali za koniec listu listu; vo viac-listovom strome vrátili alebo vymazali prvý pár nasledujúceho listu namiesto požadovaného. Medzitým HasKey behal vlastný scan a hlásil kľúč ako prítomný, takže trieda sama sebe odporovala. Generovaný referenčný manuál s jednou named destináciou na API symbol prekročí 32 768 položiek bez snaženia a niektorí producenti zapisujú všetky do jediného plochého listu

Od v3.539.45 vracia FindIndex array index cez samostatný out parameter a plný offset položky ako svoj výsledok, takže žiadna hodnota sa neskráti. Ten istý release dotiahol dvoch susedov. KeyName teraz počíta a vracia len skutočné reťazcové kľúče a pre index 0 alebo menej vracia prázdny reťazec, kde predtým pretypovalo hocijaký objekt nasledujúci po neplatnom kľúči. HasKey už neberie numerický alebo inak neplatný kľúč ako prázdne meno. Pre list ako [(Valid) 42 123 456] je teraz HasKey('') False a KeyName(2) vracia prázdny reťazec

procedure AuditTrees(const FileName: string);
var
  Lib: TPDFlib;
  I: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile(FileName, '') <> 1 then
      Exit;
    // Number tree /PageLabels; súbory bez neho vraciajú holé čísla strán
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // Name tree /EmbeddedFiles; indexy sú 1-based, nereťazcové kľúče sa preskočia
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // meno, MIME typ
    // Name tree /JavaScript: vypíše mená balíkov, nič nevykoná
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

Na tom istom ručne postavenom súbore, ktorého koreň /PageLabels vypisuje jeden list dvakrát a referencuje sám seba, vytlačí tento audit i a A-1 pre dve strany, každý rozsah raz, a jediný skriptový balík z name tree /JavaScript, ktorá tiež ukazuje späť na vlastný koreň. Zapisovacia strana page labelov má s koreňmi /Kids vlastnú históriu, pokrytú v článku o oprave PDF page labels uložených v /Kids number trees; AddPageLabels taký koreň pred vložením sploští a spolieha sa na rovnakú enumeráciu EnumNumTree popísanú tu

Čo toto posilnenie aj naďalej negarantuje?

Posilnenie garantuje ukončenie, stabilné poradie a správne výsledky pre stromy, ktorých skutočné kľúče sú neporušené; nedokáže spraviť, aby poškodený strom znamenal to, čo jeho autor zamýšľal. Pár limitov stojí za poznanie skôr, než na tom začnete stavať

• Množina navštívených pracuje s identitou objektov. Dva odlišné slovníky s totožným obsahom sú dva uzly, takže producent, ktorý list skopíruje namiesto referencovania, stále vyprodukuje zdvojené položky
• Dobre utvorený, utriedený, ale nesprávny /Limits aj naďalej orezáva. Čítač, ktorý používa rozsahy ako optimalizáciu, nemôže byť zároveň imunný voči rozsahu, ktorý verohodne klame; jediná alternatíva je ignorovať /Limits úplne a prehľadávať každý list
• Enumerácia zachováva poradie súboru, ale netriedi. GetPageLabel aplikuje posledný enumerovaný rozsah na strane alebo pod ňou, takže producent zapisujúci rozsahy neusporiadane dostane sémantiku poradia súboru
• Pamäť rastie s počtom odlišných uzlov a položiek. Prechod pridá list a hash množinu, nič viac, ale 100 MB name tree je po parsnutí stále 100 MB name tree
• Zdvojené kľúče vo vnútri jedného listu sa nehlásia. Binárne vyhľadávanie vráti ľubovoľný zhodný pár, ktorého zasiahne ako prvý; lineárna záloha drží poslednú zhodu, ktorú prejde

Rýchla referencia: čítanie PDF stromov z nedôveryhodných súborov

• Upgradujte na v3.539.45 alebo novšiu kvôli cyklo-bezpečnému, stack-bezpečnému prechodu name trees a number trees a na v3.539.51 alebo novšiu, aby prevrátené /Limits už neschovávali kľúče
• Berte vrátenie 0 z GetNamedDestination ako „absent“ a vrátenie 0 z GetDestPage ako „prítomné, ale nepoužiteľné“
• Používajte GlobalJavaScriptCount a GlobalJavaScriptPackageName pre name tree /JavaScript; GetDocJavaScript číta namiesto toho katalógové triggre /AA
• Indexujte prílohy a skriptové balíky od 1 po počet, ktorý knižnica hlási; neplatné kľúče sa nepočítajú
• Vo vlastnom stromovom kóde označujte uzly ako navštívené pri vypojení, tlačte potomkov v opačnom poradí a nechajte /Limits orezávať len vtedy, keď je to dobre typovaný, utriedený pár

Pre-flight nástroje, archivátory a prehliadače čítajú tieto stromy skôr, než sa vyrenderuje akákoľvek strana, takže musia prežiť čokoľvek, čo príde vo frontu uploadov. Čítače stromov popísané vyššie dodáva PDFlibPas, PDF Library for Delphi, ktoré sa zostavuje s Delphi aj Free Pascal