PDFlibPas imenska drevesa: cikli, meje in velikanski listi

PDFlibPas, losLabova knjižnica PDF za Delphi, prehaja imenska in številska drevesa PDF z izrecnim skladom in množico obiskanih od v3.539.45, tako da ciklični /Kids, deljeni otroci in drevesa, globoka na tisoče ravni, ne izčrpajo več sklada klicev ali podvajajo vnosov. Od v3.539.51 manjkajoč, okvarjen ali obrnjen par /Limits nikoli več ne skrije veje, ki drži ključ. Imenovane destinacije, oznake strani, priloge in JavaScript na ravni dokumenta vsi berejo skozi ti dva kodna predora, kar jih dela delom napadalne površine vsakega PDF-ja, ki ga niste izdelali sami

Sprožilec je redko eksotičen. Fuzzer, sovražna nalaganja ali hroščat inkrementalni shranjevalnik zapiše vnos /Kids, ki kaže nazaj na prednika, rekurzivni prehajalec pa pogine s prelitjem sklada na datoteki, veliki dva kilobajta. Tišja odpoved je iskanje, ki zaupa pokvarjenemu seznamu /Limits in poroča "ni najdeno" za destinacijo, ki je očitno tam

Kje se imenska in številska drevesa pojavijo v PDF-ju?

Imenska in številska drevesa se pojavijo povsod, kjer PDF preslika veliko množico ključev na objekte, PDFlibPas pa bere vsaj štiri od njih skozi javne API-je. ISO 32000-1 §7.9.6 definira imensko drevo (nizovni ključi, tabela 36) in §7.9.7 številsko drevo (celoštevilčni ključi, tabela 37). Oba sta približno uravnoteženi drevesi, katerih koren in vmesni vozli nosijo /Kids, njihovi listi pa sortirane pare ključ/vrednost v /Names ali /Nums, ne-korenni vozli pa dvoelementen seznam /Limits z najmanjšim in največjim ključem pod njimi

Drevo	Kje živi	Specifikacija	Berilni API PDFlibPas
Imenovane destinacije	/Dests v imenskem slovarju	§12.3.2.3	GetNamedDestination, nato GetDestPage / GetDestType
Oznake strani	/PageLabels v katalogu (številsko drevo)	§12.4.2	GetPageLabel
Priloge	/EmbeddedFiles v imenskem slovarju	§7.7.4, §7.11.4	EmbeddedFileCount, GetEmbeddedFileStrProperty
JavaScript na ravni dokumenta	/JavaScript v imenskem slovarju	§7.7.4	GlobalJavaScriptCount, GlobalJavaScriptPackageName

Dve podrobnosti v tej tabeli sta lahko ujeta. Imenovane destinacije imajo tudi starejšo obliko iz PDF 1.1, navaden slovar /Dests v katalogu, indeksiran z objekti imen, GetNamedDestination pa ta slovar preveri najprej, preden se spusti v imensko drevo PDF 1.2. In GetDocJavaScript sploh ni bralnik imenskih dreves: vrne skripte, pripete sprožilcem dokumenta v slovarju kataloga /AA (WS, DS, WP, DP, DC), medtem ko poimenovani skriptni paketi, ki tečejo, ko se dokument odpre, živijo v imenskem drevesu /JavaScript

Vsak bajt teh struktur prihaja iz datoteke. Specifikacija pravi, kaj naj izdelovalec proizvede; ne more preprečiti bralniku, da prejme kaj drugega — to je ista lekcija kot pri utrjevanju Pascal razčlenjevalnika PDF proti zlonamernim datotekam, tukaj uporabljena na obliko drevesa namesto na velikosti predpomnilnikov

Zakaj cikličen seznam /Kids sesuje rekurzivnega prehajalca drevesa?

Cikličen seznam /Kids sesuje rekurzivnega prehajalca, ker se nič v rekurziji ne zaveda, da je vozel že videla, tako da otrok, ki navaja svojega lastnega prednika, spremeni končno datoteko v neskončen spust. Pred v3.539.45 so se NameTreeLookup, NumTreeLookup, EnumNumTree in notranji TPDFNameTree.ProcessNode vsi klicali sami enkrat na otroka. Ena sama samosklicna referenca je zadoščala, da se proces konča, in legitemerno zelo globoko drevo je lahko storilo isto brez vsakega cikla

Blagodnejša različica pokvari rezultate, namesto da sesuje. Ko dva vnosa /Kids navajata isti list, ga naivno naštevanje obišče dvakrat in števec prilog ali seznam skriptnih paketov poroča vnose, ki ne obstajajo

Popravek zamenja rekurzijo z izrecnim skladom zadnji-vhoda, prvi-izhoda na kupu in množico obiskanih, indeksirano po identiteti slovarjev. Vozel je označen, ko je vzet s sklada, ne ko je podan nanj, tako da lahko ciklični sklic kratko leži na skladu, a je zavržen v trenutku, ko pride nazaj na vrh. Vsak različen vozel razširi svoje otroke točno enkrat, kar omeji skupno delo s številom različnih slovarjev plus skupno dolžino njihovih seznamov /Kids. Globina preneha šteti: veriga 4.096 ravni je le 4.096 ponovitev zanke in 4.096 vnosov v zgoščeni množici

Vrstni red pa vseeno šteje in sklad ga mora hraniti tako, da se ga hrani od zadaj. Otroci so podani od zadnjega indeksa do prvega, tako da je skrajno levi otrok vzet prvi in listi pridejo ven v istem vrstnem redu od leve proti desni, kakor ga je zapisal izdelovalec. GetPageLabel je od tega odvisen: prehodi vsako naštetena razpon in uveljavi zadnjega, katerega začetni indeks je na ali pod stranjo, tako da bi obrnjeno naštevanje tiho dalo strani 200 slog prednega gradiva. Okostje spodaj prikaže vzorec na abstraktnem tipu vozla, neodvisno od katerega koli objektnega modela PDF

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // prazno na listu
    Keys: TArray<string>;      // ključi lista, razvrščeni od pridnega izdelovalca
    Values: TArray<Integer>;   // vzporedno s Keys
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// /Limits je namig: vejo lahko odreže samo dobro oblikovan, urejen par
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;                      // cikel ali deljen otrok: že videno
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // Podajte od desne proti levi, da je skrajno levi otrok vzet prvi
        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;
      // Zgrešitev v tem listu ni sodba: nadaljujte s sestrami
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

Zakaj iskanje ne sme obstati pri prvi ujemajoči veji?

Iskanje ne sme obstati pri prvi veji, katere razpon se ujema, ker se lahko razponi /Limits v resnični datoteki prekrivajo ali lažejo in veja, ki zahteva ključ, ni nujno veja, ki ga drži. Iskanja pred v3.539.45 so na prvem otroku, katerega /Limits je pokrival ključ, nastavila zastavico Found, se spustila vanj in nikoli več pogledala sestro. Če se je ta otrok izkazal za praznega, zastarelega ali zanko nazaj na koren, je bil odgovor nil, tudi kadar je naslednja sestra držala ključ

Prepisani FindTreeValue, ki zdaj stoji za NameTreeLookup in NumTreeLookup, poda vsakega otroka, katerega razpon ne izključuje ključa, in vzema vozle s sklada, dokler ne najde zadetka ali dokler se sklad ne izprazni. Zgrešitev znotraj enega lista je le zgrešitev znotraj enega lista. V dobro oblikovanem drevesu to ne stane ničesar dodatnega; v poškodovanem stane nekaj obiskov vozlov dodatno in vrne pravi odgovor

Iskanje po listu sledi isti filozofiji. ISO 32000-1 zahteva, da so ključi v seznamu /Names razvrščeni po bajtni vrednosti, zato se list najprej preišče z binarnim iskanjem. Če to odpove, PDFlibPas pade nazaj na linearni pregled parov, ker bi list izven vrstnega reda sicer naredil prisoten ključ neviden. Razvrščanje je hitra pot, ne filter

Iskanje se tudi odkloni od ugibanja pri eni strukturni protislovnosti. Tabela 36 dopušča, da vozel nosi /Kids ali /Names, nikoli oboje, pot iskanja pa vozel, ki nosi oboje, obravnava kot okvarjenega in ga preskoči, namesto da bi izbral eno od razlag. Poti naštevanja, kot je EnumNumTree, so popustljivejše in sledijo /Kids, kadar sta prisotna oboje

Za kaj sme bralnik zaupati /Limits?

Bralnik sme /Limits zaupati samo za preskočanje dela, nikoli za odločitev, da ključa ni, in to samo, kadar je par dobro oblikovan. Tabela 36 pravi, da morajo vmesni in listni vozli nositi /Limits kot dvoelementen seznam najmanjšega in največjega ključa, v praksi pa vnos izgine po ročnih urejanjih, drži števila v imenskem drevesu ali pride z zamenjanimi mejami. PDFlibPas v3.539.45 in v3.539.51 vsak primer uredita enako: kadar se razpon ne da prebrati kot urejen par pravega tipa, ostane otrok preiščljiv

• Manjkajoči /Limits: stari preizkus razpona je vrnil False in otrok je bil preskočen popolnoma, tako da je izdelovalec, ki je pozabil vnos, naredil svoje celotno poddrevo nedosegljivo. Od v3.539.45 se otrok preišče
• Napačen tip ali napačna dolžina, na primer števila v imenskem drevesu ali enoelementen seznam: obravnavano točno kot manjkajoč vnos od v3.539.45
• Obrnjene meje, kot je [(Z) (A)] ali [9 0]: v3.539.45 ju je še uporabljal in noben ključ ne more izpolniti Lo <= Key <= Hi, kadar je Lo > Hi, tako da je bila veja izključena za vsako iskanje. Od v3.539.51 se razpon uporablja za obrezovanje samo, kadar njegova spodnja meja ne presega zgornje
• Dobro oblikovan, urejen in pravilen: uporabljen za preskočanje veje — to je cel namen vnosa

Pravi ključi odločajo o izidu v vsakem primeru. Sovražni /Limits lahko naredi, da PDFlibPas obišče več vozlov, kot je treba, okvarjen pa ne more več narediti, da obstoječa destinacija izgine. S strani klicalca se nič ne spremeni: GetNamedDestination vrne 0, kadar imena res ni, sicer pa ID destinacije, funkcije destinacij pa prevzamejo od tam

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;
    // Najprej katalog /Dests (PDF 1.1), nato imensko drevo /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;

Pognan na ročno zgrajeni datoteki, katere koren /Dests ima enega otroka, ki se vrača na koren pod razponom [(a) (z)], in drugega otroka, ki drži pravi vnos pod obrnjenimi mejami [(z) (a)], ta procedura razreši destinacijo na stran 2 z vrsto pogleda 2 (Fit). Pred v3.539.45 je isto iskanje vrnilo 0, ker je vračajoči se otrok zahteval ključ prvi in iskanje nikoli ni doseglo njegove sestre; sam v3.539.45 je še vedno vrnil 0, ker je obrnjen razpon izključil pravi list. Če nato berete oris, ki kaže na te destinacije, sestrski članek o brananju dejanj zaznamkov in anotacij PDF v Delphiju pokriva stran dejanj

Kako je list s 32.769 imeni pokvaril TPDFNameTree?

List s 32.769 pari ime/vrednost je pokvaril TPDFNameTree, ker je njegov notranji FindIndex spravil dve števili v en 32-bitni Integer: položaj lista v notranjem seznamu v zgornjih 16 bitih in odmik vnosa znotraj seznama /Names tega lista v spodnjih 16 bitih. Vsak par zasede dve mesti v seznamu, tako da 32.769. par, par z indeksom 32.768, začne pri odmiku 65.536, kar je $10000. Ta vrednost se prenese v zgornjo polovico in dekodirnik jo je prebral nazaj kot odmik 0 v naslednjem listu

TPDFNameTree je razred za prilogami, globalnimi skriptnimi paketi in pisanjem imenovanih destinacij, kar posledice naredi konkretnimi. V drevesu z enim listom naslednjega lista ni, zato sta se FindKey in DeleteKey indeksirala čez konec seznama listov; v drevesu z več listi sta vrnila ali izbrisala prvi par naslednjega lista namesto zahtevanega. Medtem je HasKey poganjal svoj lasten pregled in poročal ključ kot prisoten, tako da si je razred nasprotoval sam. Ustvarjen referenčni priročnik z eno imenovano destinacijo za vsak simbol API prečka 32.768 vnosov brez truda, nekateri izdelovalci pa vse zapišejo v en sam raven list

Od v3.539.45 FindIndex vrne seznamovni indeks skozi ločen parameter out in celoten odmik vnosa kot svoj rezultat, tako da se nobena vrednost ne truncira. Isti izdaji je zaostrila še dva soseda. KeyName zdaj šteje in vrača samo prave nizovne ključe ter vrne prazen niz za indeks 0 ali manj, kjer je prej ulil kateri koli objekt, ki je sledil neveljavnemu ključu. HasKey številskega ali kako drugače neveljavnega ključa ne obravnava več kot prazno ime. Za list, kot je [(Valid) 42 123 456], je HasKey('') zdaj False in KeyName(2) vrne prazen niz

procedure AuditTrees(const FileName: string);
var
  Lib: TPDFlib;
  I: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile(FileName, '') <> 1 then
      Exit;
    // Številsko drevo /PageLabels; datoteke brez njega vrnejo navadne številke strani
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // Imensko drevo /EmbeddedFiles; indeksi so od 1, ne-nizovni ključi preskočeni
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // ime, vrsta MIME
    // Imensko drevo /JavaScript: našteti imena paketov, ne izvesti ničesar
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

Na isti ročno zgrajeni datoteki, katere koren /PageLabels našteje en list dvakrat in se navaja sam, ta revizija natisne i in A-1 za dve strani, vsak razpon enkrat, ter en sam skriptni paket iz drevesa /JavaScript, ki prav tako kaže nazaj na svoj koren. Pisalna stran oznak strani ima z koreni /Kids svojo zgodovino, pokrito v popravljanju oznak strani PDF, shranjenih v številskih drevesih /Kids; AddPageLabels takšen koren splošči, preden vstavlja, in se zanaša na isto naštevanje EnumNumTree, opisano tukaj

Kaj ta utrditev še vedno ne jamči?

Utrditev jamči zaustavitev, stabilen vrstni red in pravilne rezultate za drevesa, katerih pravi ključi so nedotaknjeni; ne naredi pa, da bi poškodovano drevo pomenilo tisto, kar je nameraval njegov avtor. Nekaj mej je vredno poznati, preden na njej gradite

• Množica obiskanih dela po identiteti objektov. Dva različna slovarja z enako vsebino sta dva vozla, tako da izdelovalec, ki lista skopira, namesto da bi ga navajal, še vedno dobi podvojene vnose
• Dobro oblikovani, urejeni, a napačni /Limits še vedno obreže. Bralnik, ki razponov uporablja kot optimizacijo, ne more biti hkrati imun na razpon, ki verjetno laže; edina alternativa je ignorirati /Limits popolnoma in preiščiti vsak list
• Naštevanje ohranja vrstni red datoteke, a ne razvršča. GetPageLabel uveljavi zadnji naštetega razpon na ali pod stranjo, tako da izdelovalec, ki razpone zapiše izven vrstnega reda, dobi semantiko vrstnega reda datoteke
• Pomnilnik raste s številom različnih vozlov in vnosov. Prehod doda seznam in zgoščeno množico, nič več, a 100 MB imensko drevo je še vedno 100 MB imensko drevo po razčlenitvi
• Podvojeni ključi znotraj enega lista niso poročani. Binarno iskanje vrne kar koli ujemajoči par, ki ga zadene prvi; linearna rezerva obdrži zadnji zadetek, ki ga pregleda

Hiter pregled: branje dreves PDF iz nezaupljivih datotek

• Nadgradite na v3.539.45 ali novejši za prehod imenskih in številskih dreves, varen glede ciklov in sklada, ter na v3.539.51 ali novejši, tako da obrnjeni /Limits ne skrijejo več ključev
• Vrnitev 0 od GetNamedDestination obravnavajte kot "odsoten", vrnitev 0 od GetDestPage pa kot "prisoten, a neuporaben"
• Uporabite GlobalJavaScriptCount in GlobalJavaScriptPackageName za imensko drevo /JavaScript; GetDocJavaScript bere namesto tega sprožilce kataloga /AA
• Indeksirajte priloge in skriptne pakete od 1 do števca, ki ga poroča knjižnica; neveljavni ključi se ne štejejo
• V svoji lastni kodi dreves označujte vozle obiskane ob izstrelitvi, podajajte otroke obrnjeno in pustite /Limits obrezati samo, kadar je dobro tipiziran, urejen par

Orodja za predhodne preglede, arhivirniki in pregledovalniki berejo ta drevesa, preden se izriše katera koli stran, zato morajo preživeti karkoli prispel v čakalno vrsto nalaganj. Bralniki dreves, opisani zgoraj, prihajajo z PDFlibPas, knjižnico PDF za Delphi, ki se zgradi z Delphijem in Free Pascalom