PDFlibPas name tree: ciklusi, loši Limits i ogromni listovi

PDFlibPas, losLab PDF Library za Delphi, obilazi PDF name tree i number tree sa eksplicitnim stekom i skupom posećenih od v3.539.45, pa ciklični /Kids, deljena deca i stabla hiljadama nivoa duboka više ne iscrpljuju call stack ni ne dupliraju unose. Od v3.539.51 nedostajući, deformisan ili obrnut par /Limits nikada ne sakriva granu koja drži ključ. Imenovane destinacije, oznake stranica, prilozi i JavaScript na nivou dokumenta svi se čitaju kroz ove dve kodne putanje, što ih čini delom napadačke površine svakog PDF-a koji sami niste proizveli

Okidač je retko egzotičan. Fuzzer, neprijateljski upload ili bagoviti inkrementalni snimak upiše /Kids unos koji pokazuje nazad na pretka, i rekurzivni obilazilac umire sa stack overflow na fajlu od dva kilobajta. Tiši kvar je potraga koja veruje polomljenom /Limits nizu i javlja „not found“ za destinaciju koja očigledno tamo jeste

Gde se name tree i number tree pojavljuju u PDF-u?

Name tree i number tree pojavljuju se svuda gde PDF mapira veliki skup ključeva na objekte, i PDFlibPas čita bar četiri od njih kroz javne API-je. ISO 32000-1 §7.9.6 definiše name tree (string ključevi, Table 36) a §7.9.7 number tree (celobrojni ključevi, Table 37). Oba su otprilike balansirana stabla čiji koren i posredni čvorovi nose /Kids, čiji listovi nose sortirane parove ključ/vrednost u /Names ili /Nums, i čiji ne-korenski čvorovi nose dvoelementni niz /Limits sa najmanjim i najvećim ključem ispod njih

Stablo	Gde živi	Specifikacija	PDFlibPas čitanje API
Imenovane destinacije	/Dests u name rečniku	§12.3.2.3	GetNamedDestination, pa GetDestPage / GetDestType
Oznake stranica	/PageLabels u katalogu (number tree)	§12.4.2	GetPageLabel
Prilozi	/EmbeddedFiles u name rečniku	§7.7.4, §7.11.4	EmbeddedFileCount, GetEmbeddedFileStrProperty
JavaScript na nivou dokumenta	/JavaScript u name rečniku	§7.7.4	GlobalJavaScriptCount, GlobalJavaScriptPackageName

Dva detalja u toj tabeli lako se previde. Imenovane destinacije imaju i stariji oblik iz PDF 1.1, običan /Dests rečnik u katalogu ključan name objektima, i GetNamedDestination prvo proverava taj rečnik pre nego što siđe u name tree iz PDF 1.2. A GetDocJavaScript uopšte nije čitač name tree: vraća skripte zakačene za okidače dokumenta u katalogovom /AA rečniku (WS, DS, WP, DP, DC), dok imenovani paketi skripti koji se izvršavaju kad se dokument otvori žive u /JavaScript name tree-u

Svaki bajt tih struktura dolazi iz fajla. Specifikacija kaže šta pisac treba da proizvede; ne može sprečiti čitača da primi nešto drugo, što je ista lekcija iza ojačavanja Pascal PDF parsera protiv zlonamernih fajlova, ovde primenjena na oblik stabla a ne na veličine bafera

Zašto ciklični /Kids niz obara rekurzivnog obilazioca stabla?

Ciklični /Kids niz obara rekurzivnog obilazioca jer ništa u rekurziji ne primeti da je čvor već videla, pa dete koje referencira sopstvenog pretka pretvara konačan fajl u beskonačan spust. Pre v3.539.45, NameTreeLookup, NumTreeLookup, EnumNumTree i interni TPDFNameTree.ProcessNode svi su zvali sami sebe jednom po detetu. Jedna sama-referenca bila je dovoljna da završi proces, i legitimno ali vrlo duboko stablo moglo je učiniti isto bez ijednog ciklusa

Blaga varijanta kvari rezultate umesto da pada. Kad dva /Kids unosa referenciraju isti list, naivna enumeracija posećuje ga dvaput, i brojač priloga ili lista paketa skripti prijavljuje unose koji ne postoje

Popravka menja rekurziju eksplicitnim last-in, first-out stekom na hipu i skupom posećenih ključanim identitetom rečnika. Čvor se označava kad je skinut sa steka, a ne kad je stavljen, pa ciklična referenca može kratko sedeti na steku ali se baca u trenutku kad se vrati gore. Svaki različit čvor širi svoju decu tačno jednom, što ograničava ukupan rad brojem različitih rečnika plus ukupnom dužinom njihovih /Kids nizova. Dubina prestaje da je bitna: lanac od 4.096 nivoa je samo 4.096 iteracija petlje i 4.096 unosa u hash skupu

Redosled ipak još je bitan, i stek se mora puniti unazad da bi se sačuvao. Deca se stavljaju od poslednjeg indeksa do prvog, pa se krajnje levo dete skida prvo i listovi izlaze istim redom s-levo-u-desno kojim ih je proizvođač upisao. GetPageLabel zavisi od toga: obilazi svaki nabrojani opseg i primenjuje poslednji čiji je početni indeks na ili ispod stranice, pa bi obrnuta enumeracija tiho dala stranici 200 stil prednje grade. Skelet ispod pokazuje obrazac na apstraktnom tipu čvora, nezavisno od bilo kog PDF objektnog modela

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // prazno na listu
    Keys: TArray<string>;      // ključevi lista, sortirani od urednog proizvođača
    Values: TArray<Integer>;   // paralelno sa Keys
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// /Limits je nagoveštaj: samo dobro formiran, uređen par može odseći granu
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;                      // ciklus ili deljeno dete: viđeno
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // Stavite desno-u-levo da se krajnje levo dete skine prvo
        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;
      // Promašaj u ovom listu nije presuda: nastavite sa skidanjem braće
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

Zašto potraga ne može stati na prvoj odgovarajućoj grani?

Potraga ne može stati na prvoj grani čiji se opseg poklapa, jer se /Limits opsezi u pravom fajlu mogu preklapati ili lagati, i grana koja tvrdi ključ nije nužno grana koja ga drži. Pre-v3.539.45 potrage postavljale su Found zastavicu na prvo dete čiji je /Limits pokrivao ključ, silazile u njega i nikada gledale drugu sestru. Ako se to dete ispostavilo praznim, zastarelim ili petljom nazad ka korenu, odgovor je bio nil, čak i kad je sledeća sestra držala ključ

Prepravljeni FindTreeValue, koji sada stoji iza NameTreeLookup i NumTreeLookup, stavlja svako dete čiji opseg ne isključuje ključ i nastavlja da skida dok ne nađe pogodak ili ne isprazni stek. Promašaj unutar jednog lista samo je promašaj unutar jednog lista. U dobro formiranom stablu to ništa ne košta dodatno; u oštećenom košta par poseta čvorova više i vraća pravi odgovor

Pretraga lista prati istu filozofiju. ISO 32000-1 zahteva da ključevi u /Names nizu budu sortirani po bajt vrednosti, pa se list pretražuje prvo binarnom pretragom. Ako ta padne, PDFlibPas vraća se na linearni pregled parova, jer bi van-reda list inače učinio prisutan ključ nevidljivim. Sortiranje je brza putanja, a ne filter

Potraga takođe odbija da nagađa kod jedne strukturne protivrečnosti. Table 36 dopušta čvoru da nosi ili /Kids ili /Names, nikada oba, i putanja potrage tretira čvor koji nosi oba kao deformisan i preskače ga umesto da izabere jedno tumačenje. Enumeracione putanje poput EnumNumTree su blagoše i prate /Kids kad su oba prisutna

Za šta sme čitač verovati /Limits?

Čitač sme verovati /Limits samo da preskoči posao, nikada da odluči da ključ odsustvuje, i samo kad je par dobro formiran. Table 36 kaže da posredni i listni čvorovi treba da nose /Limits kao dvoelementni niz najmanjeg i najvećeg ključa, ali u praksi unos nestane posle ručnih izmena, drži brojeve u name tree-u, ili stiže sa zamenjenim granicama. PDFlibPas v3.539.45 i v3.539.51 rešavaju svaki slučaj isto: ako se opseg ne može pročitati kao uređeni par pravog tipa, dete ostaje pretraživo

• Nedostajući /Limits: stara provera opsega vraćala je False i dete je preskakano odmah, pa je proizvođač koji zaboravi unos učinio svoje celo podstablo nedostižnim. Od v3.539.45 dete se pretražuje
• Pogrešan tip ili pogrešna dužina, poput brojeva u name tree-u ili niza od jednog elementa: tretirano tačno kao nedostajući unos od v3.539.45
• Obrnute granice poput [(Z) (A)] ili [9 0]: v3.539.45 ih je i dalje koristio, i nijedan ključ ne može zadovoljiti Lo <= Key <= Hi kad je Lo > Hi, pa je grana bila isključena za svaku potragu. Od v3.539.51 opseg se koristi za odsecanje samo kad njegova donja granica ne premašuje gornju
• Dobro formiran, uređen i ispravan: koristi se da preskoči granu, što je cela poenta unosa

Pravi ključevi odlučuju ishod u svakom slučaju. Neprijateljski /Limits može naterrati PDFlibPas da poseti više čvorova nego što treba, ali deformisani više ne može učiniti da postojeća destinacija nestane. Sa strane pozivaoca ništa se ne menja: GetNamedDestination vraća 0 kad ime zaista odsustvuje i destination ID inače, a funkcije destinacija preuzimaju odatle

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;
    // Katalog /Dests (PDF 1.1) prvo, pa /Dests name tree
    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;

Pokrenut nad ručno građenim fajlom čiji /Dests koren ima jedno dete koje se vraća petljom na koren pod [(a) (z)] opsegom i drugo dete koje drži pravi unos pod obrnutim [(z) (a)] granicama, ova procedura razrešava destinaciju na stranicu 2 sa tipom prikaza 2 (Fit). Pre v3.539.45 ista potraga vraćala je 0, jer je petljasto dete tvrdilo ključ prvo i pretraga nikada nije stigla do njegove sestre; samo v3.539.45 i dalje je vraćao 0, jer je obrnuti opseg isključivao pravi list. Ako onda čitate outline koji pokazuje na ove destinacije, pratilac članak o čitanju PDF bookmark i anotacijskih akcija u Delphi-ju pokriva stranu akcija

Kako je list sa 32.769 imena polomio TPDFNameTree?

List sa 32.769 parova ime/vrednost polomio je TPDFNameTree jer je njegov interni FindIndex spakovao dva broja u jedan 32-bitni Integer: poziciju lista u internoj listi nizova u gornjih 16 bitova i ofset unosa unutar /Names niza tog lista u donjih 16 bitova. Svaki par zauzima dva mesta niza, pa 32.769. par, indeks para 32.768, počinje na ofsetu 65.536, što je $10000. Ta vrednost prenosi se u gornju polovinu, i dekoder ju je čitao nazad kao ofset 0 u sledećem listu

TPDFNameTree je klasa iza priloga, globalnih JavaScript paketa i upisa imenovanih destinacija, što posledice čini konkretnim. U stablu sa jednim listom nema sledećeg lista, pa su FindKey i DeleteKey indeksirali iza kraja liste listova; u višelistnom stablu vraćali su ili brisali prvi par sledećeg lista umesto traženog. U međuvremenu HasKey vodio je sopstvenu pretragu i prijavljivao ključ kao prisutan, pa se klasa protivrečila sama sebi. Generisani priručnik sa jednom imenovanom destinacijom po API simbolu prelazi 32.768 unosa bez truda, i neki proizvođači upisuju sve njih u jedan ravan list

Od v3.539.45, FindIndex vraća indeks niza kroz poseban out parametar i potpun ofset unosa kao svoj rezultat, pa nijedna vrednost se ne seče. Isto izdanje zateglo je dva suseda. KeyName sada broji i vraća samo prave string ključeve i vraća prazan string za indeks 0 ili ispod, gde je ranije pretvarao bilo koji objekat iza nevažećeg ključa. HasKey više ne tretira numerički ili inače nevažeći ključ kao prazno ime. Za list poput [(Valid) 42 123 456], HasKey('') je sada False i KeyName(2) vraća prazan string

procedure AuditTrees(const FileName: string);
var
  Lib: TPDFlib;
  I: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile(FileName, '') <> 1 then
      Exit;
    // /PageLabels number tree; fajlovi bez njega vraćaju obične brojeve stranica
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // /EmbeddedFiles name tree; indeksi su 1-bazni, ne-string ključevi preskočeni
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // ime, MIME tip
    // /JavaScript name tree: izlistaj imena paketa, ništa ne izvršavaj
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

Nad istim ručno građenim fajlom, čiji /PageLabels koren izlistava jedan list dvaput i referencira sam sebe, ova provera ispisuje i i A-1 za dve stranice, svaki opseg jednom, i jedini paket skripti iz /JavaScript stabla koje takođe pokazuje nazad na sopstveni koren. Strana upisa oznaka stranica ima sopstvenu istoriju sa /Kids korenima, pokrivena u popravi PDF oznaka stranica pohranjenih u /Kids number tree-ovima; AddPageLabels izravna takav koren pre ubacivanja, i oslanja se na istu EnumNumTree enumeraciju opisanu ovde

Šta ovo ojačavanje još uvek ne garantuje?

Ojačavanje garantuje završetak, stabilan redosled i ispravne rezultate za stabla čiji su pravi ključevi netaknuti; ne čini da oštećeno stablo znači ono što je njegov autor nameravao. Nekoliko granica vredi znati pre nego što gradite na tome

• Skup posećenih radi po identitetu objekta. Dva različita rečnika sa istim sadržajem su dva čvora, pa proizvođač koji kopira list umesto da ga referencira i dalje daje duplirane unose
• Dobro formiran, uređen ali pogrešan /Limits i dalje odseca. Čitač koji koristi opsege kao optimizaciju ne može biti imun ni na opseg koji uverljivo laže; jedina alternativa je ignorisati /Limits potpuno i pregledati svaki list
• Enumeracija čuva redosled fajla ali ne sortira. GetPageLabel primenjuje poslednji nabrojani opseg na ili ispod stranice, pa proizvođač koji upisuje opsege van reda dobija semantiku redosleda fajla
• Memorija raste sa brojem različitih čvorova i unosa. Obilazak dodaje listu i hash skup, ništa više, ali 100 MB name tree je i posle parsiranja 100 MB name tree
• Duplirani ključevi unutar jednog lista ne prijavljuju se. Binarna pretraga vraća bilo koji pogodak koji prvo nađe; linearni fallback čuva poslednji pogodak koji pregleda

Brzi pregled: čitanje PDF stabala iz nepouzdanih fajlova

• Nadogradite na v3.539.45 ili noviji za ciklus-siguran, stek-siguran obilazak name tree i number tree, i na v3.539.51 ili noviji da obrnuti /Limits više ne sakrivaju ključeve
• Tretirajte GetNamedDestination koji vraća 0 kao „odsutno“, a GetDestPage koji vraća 0 kao „prisutno ali neupotrebljivo“
• Koristite GlobalJavaScriptCount i GlobalJavaScriptPackageName za /JavaScript name tree; GetDocJavaScript umesto toga čita katalogove /AA okidače
• Indeksirajte priloge i pakete skripti od 1 do broja koji biblioteka prijavljuje; nevažeći ključevi se ne broje
• U sopstvenom kodu stabla, označavajte čvorove posećenim pri skidanju, stavljajte decu obrnuto, i pustite /Limits da seče samo kad je dobro-tipovan, uređen par

Pre-flight alati, arhiveri i preglednici čitaju ova stabla pre nego što se bilo koja stranica renderuje, pa moraju preživeti šta god stigne u red za upload. Čitači stabala opisani gore isporučuju se sa PDFlibPas, PDF Library za Delphi, koji se gradi i sa Delphi-jem i sa Free Pascalom