PDFlibPas name treeovi: ciklusi, loši Limits, veliki listovi

PDFlibPas, losLab PDF Library za Delphi, obilazi PDF name i number treeove eksplicitnim stogom i skupom posjećenih od v3.539.45, pa ciklični /Kids, dijeljena djeca i stabla tisućama razina duboka više ne iscrpljuju stog poziva ni ne dupliciraju unose. Od v3.539.51 nedostajući, neispravan ili obrnut /Limits par nikad ne sakriva granu koja drži ključ. Imenovane destinacije, oznake stranica, privici i JavaScript na razini dokumenta svi se čitaju kroz ove dvije putanje koda, što ih čini dijelom napadačke površine svakog PDF-a koji niste sami proizveli

Okidač je retko egzotičan. Fuzzer, neprijateljski upload ili bagoviti inkrementalni save zapiše /Kids unos koji pokazuje natrag na predka, i rekurzivni obilazak umire sa stack overflowom na datoteci od dva kilobajta. Tiši kvar jest pretraga koja vjeruje pokvarenom /Limits polju i javlja „not found" za destinaciju koja očito tamo stoji

Gdje se name i number treeovi pojavljuju u PDF-u?

Name i number treeovi pojavljuju se gdje god PDF mapira veliki skup ključeva na objekte, a PDFlibPas čita barem četiri od njih kroz javne API-je. ISO 32000-1 §7.9.6 definira name tree (string ključevi, Tablica 36), a §7.9.7 number tree (cijelobrojni ključevi, Tablica 37). Oboje su prilično balansirana stabla čiji korijen i posredni čvorovi nose /Kids, čiji listovi nose sortirane parove ključ/vrijednost u /Names ili /Nums, i čiji ne-korijenski čvorovi nose dvoelementno /Limits polje s najmanjim i najvećim ključem ispod njih

Stablo	Gdje živi	Specifikacija	PDFlibPas čitajući API
Imenovane destinacije	/Dests u name rječniku	§12.3.2.3	GetNamedDestination, zatim GetDestPage / GetDestType
Oznake stranica	/PageLabels u katalogu (number tree)	§12.4.2	GetPageLabel
Privici	/EmbeddedFiles u name rječniku	§7.7.4, §7.11.4	EmbeddedFileCount, GetEmbeddedFileStrProperty
JavaScript na razini dokumenta	/JavaScript u name rječniku	§7.7.4	GlobalJavaScriptCount, GlobalJavaScriptPackageName

Dva detalja u toj tablici lako se promaše. Imenovane destinacije imaju i stariji PDF 1.1 oblik, obični /Dests rječnik u katalogu ključan name objektima, a GetNamedDestination taj rječnik provjerava prije nego što siđe u PDF 1.2 name tree. A GetDocJavaScript uopće nije čitač name treeova: vraća skripte prikačene na okidače dokumenta u katalogovom /AA rječniku (WS, DS, WP, DP, DC), dok se imenovani skriptni paketi koji se izvršavaju kad se dokument otvori nalaze u /JavaScript name treeu

Svaki bajt tih struktura dolazi iz datoteke. Specifikacija kaže što pisac treba proizvesti; ne može spriječiti čitača da primi nešto drugo, što je ista lekcija iza otvrđivanja Pascal PDF parsera protiv zlonamjernih datoteka, ovdje primijenjena na oblik stabla umjesto na veličine međuspremnika

Zašto ciklično /Kids polje ruši rekurzivnog obilaziča stabla?

Ciklično /Kids polje ruši rekurzivnog obilaziča jer ništa u rekurziji ne primijeti da je čvor već vidjela, pa dijete koje referencira vlastitog predka pretvara konačnu datoteku u beskonačni spust. Prije v3.539.45 NameTreeLookup, NumTreeLookup, EnumNumTree i interni TPDFNameTree.ProcessNode svi su se sami pozivali jednom po djetetu. Jedna samoreferencija bila je dovoljna da završi proces, a legitimno, ali vrlo duboko stablo moglo je učiniti isto bez ijednog ciklusa

Blaga varijanta kvari rezultate umjesto da ruši. Kad dva /Kids unosa referenciraju isti list, naivna enumeracija posjećuje ga dvaput, i brojač privika ili lista skriptnih paketa javlja unose koji ne postoje

Popravak zamjenjuje rekurziju eksplicitnim last-in, first-out stogom na heapu i skupom posjećenih s ključem po identitetu rječnika. Čvor se označava kad se skine sa stoga, a ne kad se stavi, pa ciklična referenca može kratko stajati na stogu ali se odbacuje onog trenutka kad se vrati gore. Svaki distinktni čvor širi svoju djecu točno jednom, što ukupan rad vezuje uz broj distinktnih rječnika plus ukupnu duljinu njihovih /Kids polja. Dubina prestaje biti važna: lanac od 4.096 razina samo je 4.096 iteracija petlje i 4.096 unosa u hash skupu

Redoslijed, međutim, i dalje je važan, i stog se mora hraniti unatrag da ga zadrži. Djeca se guraju od zadnjeg indeksa prema prvom, pa se krajnje lijevo dijete skida prvo i listovi izlaze u istom redoslijedu s lijeva na desno u kojem ih je proizvođač zapisao. GetPageLabel od toga ovisi: prelazi svaki enumerirani raspon i primjenjuje posljednji čiji je početni indeks na stranici ili ispod nje, pa bi obrnuta enumeracija tiho dala stranici 200 stil prednje građe. Skelet dolje pokazuje obrazac na apstraktnom tipu čvora, neovisno o bilo kojem PDF objektnom modelu

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 s Keys
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// /Limits je nagovještaj: samo dobro oblikovan, uređen par smije rezati 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 dijeljeno dijete: viđeno
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // Gurajte s desna na lijevo da se krajnje lijevo dijete 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 skidati braću
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

Zašto pretraga ne smije stati na prvoj odgovarajućoj grani?

Pretraga ne smije stati na prvoj grani čiji se raspon poklopi, jer /Limits rasponi u stvarnoj datoteci mogu se preklapati ili lagati, i grana koja traži ključ nije nužno grana koja ga drži. Pretrage prije v3.539.45 postavljale su Found zastavicu na prvom djetetu čiji je /Limits pokrivao ključ, spuštale su se u njega i nikad pogledale drugu braću. Ako se to dijete ispostavilo praznim, zastarjelim ili petljom natrag na korijen, odgovor je bio nil, i kad je upravo sljedeći brat držao ključ

Prepravljeni FindTreeValue, koji sada stoji iza NameTreeLookup i NumTreeLookup, stavlja svako dijete čiji raspon ne isključuje ključ i nastavlja skidati dok ne pronađe podudaranje ili ne isprazni stog. Promašaj unutar jednog lista samo je promašaj unutar jednog lista. U dobro oblikovanom stablu to ne košta ništa viška; u oštećenom košta par posjeta čvorovima više i vraća pravi odgovor

Pretraga lista slijedi istu filozofiju. ISO 32000-1 zahtijeva da ključevi u /Names polju budu sortirani po bajtnoj vrijednosti, pa se list najprije pretražuje binarnim pretraživanjem. Ako to padne, PDFlibPas vraća se na linearni pregled parova, jer bi lista izvan reda inače učinila prisutan ključ nevidljivim. Sortiranje je brz put, ne filter

Pretraga također odbija nagađati kod jedne strukturalne kontradikcije. Tablica 36 dopušta čvoru da nosi ili /Kids ili /Names, nikad oboje, i putanja pretraživanja tretira čvor koji nosi oboje kao neispravan i preskače ga umjesto da odabere jedno tumačenje. Enumeracijske putanje poput EnumNumTree popustljivije su i slijede /Kids kad su oboje prisutni

Za što smije čitač vjerovati /Limits?

Čitač smije vjerovati /Limits samo da preskoči posao, nikad da odluči da ključ nije prisutan, i samo kad je par dobro oblikovan. Tablica 36 kaže da posredni i listni čvorovi trebaju nositi /Limits kao dvoelementno polje najmanjeg i najvećeg ključa, ali u praksi unos nestaje nakon ručnih izmjena, drži brojeve u name treeu, ili stiže s zamijenjenim granicama. PDFlibPas v3.539.45 i v3.539.51 rješavaju svaki slučaj isto: ako se raspon ne može pročitati kao uređeni par pravog tipa, dijete ostaje pretraživo

• Nedostajući /Limits: stara provjera raspona vraćala je False i dijete je preskakano uspravo, pa je proizvođač koji je zaboravio unos učinio cijelo svoje podstablo nedohvatnim. Od v3.539.45 dijete se pretražuje
• Pogrešan tip ili pogrešna duljina, poput brojeva u name treeu ili polja od jednog elementa: tretira se točno kao nedostajući unos od v3.539.45
• Obrnute granice poput [(Z) (A)] ili [9 0]: v3.539.45 još ih je koristio, i nijedan ključ ne može zadovoljiti Lo <= Key <= Hi kad je Lo > Hi, pa je grana bila isključena za svaku pretragu. Od v3.539.51 raspon se koristi za rezanje samo kad njegova donja granica ne premašuje gornju
• Dobro oblikovan, uređen i točan: koristi se da se preskoči grana, što je i smisao unosa

Stvarni ključovi odlučuju ishod u svakom slučaju. Neprijateljski /Limits može natjerati PDFlibPas da posjeti više čvorova nego što treba, ali neispravan više ne može učiniti da postojeća destinacija nestane. Sa strane pozivatelja ništa se ne mijenja: GetNamedDestination vraća 0 kad ime stvarno nije prisutno, a ID destinacije inače, i destinacijske funkcije 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) prvi, 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;

Pokrenuta nad ručno građenom datotekom čiji /Dests korijen ima jedno dijete koje se vraća petljom na korijen pod [(a) (z)] rasponom i drugo dijete koje drži pravi unos pod obrnutim [(z) (a)] granicama, ova procedura razrješuje destinaciju na stranicu 2 s tipom prikaza 2 (Fit). Prije v3.539.45 ista je pretraga vraćala 0, jer je petljajuće dijete tražilo ključ prvo i pretraga nikad nije došla do njegova brata; sam v3.539.45 i dalje je vraćao 0, jer je obrnuti raspon isključio pravi list. Ako zatim čitate outline koji pokazuje na te destinacije, prateći članak o čitanju PDF bookmark i anotacijskih akcija u Delphiju pokriva stranu akcija

Kako je list sa 32.769 imena slomio TPDFNameTree?

List sa 32.769 parova ime/vrijednost slomio je TPDFNameTree jer je njegov interni FindIndex spakirao dva broja u jedan 32-bitni Integer: poziciju lista u internoj listi polja u gornjih 16 bitova i pomak unosa unutar /Names polja tog lista u donjih 16 bitova. Svaki par zauzima dva slota polja, pa 32.769. par, indeks para 32.768, počinje na pomaku 65.536, što je $10000. Ta vrijednost prenosi se u gornju polovicu, i dekoder ju je pročitao natrag kao pomak 0 u sljedećem listu

TPDFNameTree jest razred iza privika, globalnih JavaScript paketa i zapisa imenovanih destinacija, što posljedice čini konkretnima. U stablu s jednim listom nema sljedećeg lista, pa su FindKey i DeleteKey indeksirali iza kraja liste listova; u višelistnom stablu vratili su ili obrisali prvi par sljedećeg lista umjesto traženoga. U međuvremenu je HasKey vodio vlastito skeniranje i javljao ključ kao prisutan, pa se razred sam proturječio. Generirani referentni priručnik s jednom imenovanom destinacijom po API simbolu pređe 32.768 unosa bez truda, i neki proizvođači sve njih zapišu u jedan ravan list

Od v3.539.45 FindIndex vraća indeks polja kroz zasebni out parametar, a puni pomak unosa kao svoj rezultat, pa se nijedna vrijednost ne reže. Isto izdanje steglo je dva susjeda. KeyName sada broji i vraća samo prave string ključeve i vraća prazan string za indeks 0 ili ispod, gdje je prije castao bilo koji objekt 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, a 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; datoteke 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-bazirani, ne-string ključevi se preskaču
    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 istom ručno građenom datotekom, čiji /PageLabels korijen izlistava jedan list dvaput i referencira sam sebe, ova revizija ispisuje i i A-1 za dvije stranice, svaki raspon jednom, i jedini skriptni paket iz /JavaScript stabla koje također pokazuje natrag na vlastiti korijen. Strana zapisa oznaka stranica ima vlastitu povijest s /Kids korijenima, obrađena u popravku PDF oznaka stranica spremljenih u /Kids number treeovima; AddPageLabels takav korijen izravna prije umetanja, i oslanja se na istu EnumNumTree enumeraciju ovdje opisanu

Što ovo otvrđivanje još uvijek ne jamči?

Otvrđivanje jamči završetak, stabilan redoslijed i točne rezultate za stabla čiji su stvarni ključovi netaknuti; ne čini da oštećeno stablo znači ono što je njegov autor mislio. Nekoliko granica vrijedi znati prije nego što na tome gradite

• Skup posjećenih radi po identitetu objekta. Dva distinktna rječnika s identičnim sadržajem dva su čvora, pa proizvođač koji kopira list umjesto da ga referencira i dalje daje duplicirane unose
• Dobro oblikovan, uređen ali pogrešan /Limits i dalje reže. Čitač koji koristi raspone kao optimizaciju ne može biti imun i na raspon koji uvjerljivo laže; jedina alternativa jest ignorirati /Limits potpuno i pregledati svaki list
• Enumeracija čuva redoslijed datoteke ali ne sortira. GetPageLabel primjenjuje posljednji enumerirani raspon na stranici ili ispod nje, pa proizvođač koji piše raspon izvan reda dobiva semantiku redoslijeda datoteke
• Memorija raste s brojem distinktnih čvorova i unosa. Obilazak dodaje listu i hash skup, ništa više, ali 100 MB name tree i dalje je 100 MB name tree nakon parsiranja
• Duplicirani ključevi unutar jednog lista ne javljaju se. Binarno pretraživanje vraća bilo koji podudarni par koji prvo pogodi; linearni fallback zadržava posljednje podudaranje koje pregleda

Brza referenca: čitanje PDF stabala iz nepouzdanih datoteka

• Nadogradite na v3.539.45 ili kasniji za obilazak name i number treeova siguran od ciklusa i stoga, i na v3.539.51 ili kasniji da obrnuti /Limits više ne skrivaju ključeve
• Tretirajte GetNamedDestination koji vraća 0 kao „odsutan", a GetDestPage koji vraća 0 kao „prisutan ali neupotrebljiv"
• Koristite GlobalJavaScriptCount i GlobalJavaScriptPackageName za /JavaScript name tree; GetDocJavaScript umjesto toga čita katalogove /AA okidače
• Indeksirajte privike i skriptne pakete od 1 do broja koji biblioteka javlja; nevažeći ključevi se ne broje
• U vlastitom kodu stabla označavajte čvorove posjećenima pri skidanju, gurajte djecu obrnuto, i dopustite /Limits da reže samo kad je dobro tipiziran, uređen par

Pre-flight alati, arhivari i preglednici čitaju ta stabla prije nego se bilo koja stranica renderira, pa moraju preživjeti sve što stigne u red za upload. Čitači stabala opisani gore isporučuju se s PDFlibPasom, PDF Library za Delphi, koji se gradi i s Delphijem i s Free Pascalom