PDFlibPas navnetræer: cyklusser, ringe /Limits og kæmpeblade

PDFlibPas, losLabs PDF Library til Delphi, gennemløber PDF-navnetræer og nummertræer med en eksplicit stak og et visited-set siden v3.539.45, så cykliske /Kids, delte børn og træer tusindvis af niveauer dybt ikke længere udtømmer call stacken eller duplikerer poster. Siden v3.539.51 skjuler et manglende, misdannet eller omvendt /Limits-par aldrig en gren, der holder nøglen. Navngivne destinationer, sidelabels, vedhæftninger og dokumentniveau-JavaScript læser alle gennem disse to kodeveje, hvilket gør dem til en del af angrebsfladen på enhver PDF, du ikke selv har produceret

Triggeren er sjældent eksotisk. En fuzzer, et fjendtligt upload eller en buggy inkrementel gemning skriver en /Kids-post, der peger tilbage på en forfader, og en rekursiv walker dør med en stack overflow på en fil på to kilobyte. Den stille fejlmåde er et opslag, der stoler på et ødelagt /Limits-array og melder "not found" for en destination, der åbenlyst er der

Hvor optræder navnetræer og nummertræer i en PDF?

Navnetræer og nummertræer optræder, hvor end en PDF afbilleder en stor mængde nøgler til objekter, og PDFlibPas læser mindst fire af dem gennem offentlige API'er. ISO 32000-1 §7.9.6 definerer navnetræet (strengnøgler, Table 36) og §7.9.7 nummertræet (heltalsnøgler, Table 37). Begge er nogenlunde balancerede træer, hvis rod og mellemnoder bærer /Kids, hvis blade bærer de sorterede nøgle/værdi-par i /Names eller /Nums, og hvis ikke-rodnoder bærer et toelements /Limits-array med den mindste og største nøgle under dem

Træ	Hvor det ligger	Specification	PDFlibPas-læse-API
Navngivne destinationer	/Dests i name dictionary	§12.3.2.3	GetNamedDestination, derefter GetDestPage / GetDestType
Sidelabels	/PageLabels i kataloget (nummertræ)	§12.4.2	GetPageLabel
Vedhæftninger	/EmbeddedFiles i name dictionary	§7.7.4, §7.11.4	EmbeddedFileCount, GetEmbeddedFileStrProperty
Dokumentniveau-JavaScript	/JavaScript i name dictionary	§7.7.4	GlobalJavaScriptCount, GlobalJavaScriptPackageName

To detaljer i den tabel er lette at overse. Navngivne destinationer har også en ældre PDF 1.1-form, en ren /Dests-dictionary i kataloget indekseret efter navneobjekter, og GetNamedDestination tjekker den dictionary først, inden den går ned ad PDF 1.2-navnetræet. Og GetDocJavaScript er slet ikke en navnetræ-læser: den returnerer scripts, der hænger på dokumenttriggere i katalogets /AA-dictionary (WS, DS, WP, DP, DC), mens de navngivne scriptpakker, der kører, når et dokument åbnes, bor i /JavaScript-navnetræet

Hver byte af de strukturer kommer fra filen. Specificationen siger, hvad en writer skal producere; den kan ikke forhindre en reader i at modtage noget andet, hvilket er samme lektie som bag hærdning af en Pascal-PDF-parser mod ondsindede filer, anvendt her på træform frem for bufferstørrelser

Hvorfor crasher et cyklisk /Kids-array en rekursiv træ-walker?

Et cyklisk /Kids-array crasher en rekursiv walker, fordi intet i rekursionen bemærker, at den har set en node før, så et barn, der refererer sin egen forfader, omdanner en endelig fil til et uendeligt fald. Før v3.539.45 kaldte NameTreeLookup, NumTreeLookup, EnumNumTree og den interne TPDFNameTree.ProcessNode alle sig selv én gang pr. barn. En enkelt selvreference var nok til at afslutte processen, og et legitimt men meget dybt træ kunne gøre det samme uden nogen cyklus overhovedet

En mildere variant korrumperer resultater i stedet for at crashe. Når to /Kids-poster refererer samme blad, besøger en naiv optælling det to gange, og et vedhæftningsantal eller en liste over scriptpakker melder poster, der ikke findes

Fixet erstatter rekursion med en eksplicit last-in, first-out-stak på heapen og et visited-set nøglet efter dictionary-identitet. En node markeres, når den poppes, ikke når den pushes, så en cyklisk reference må ligge kort på stakken, men kasseres i det øjeblik, den kommer op igen. Hver distinkt node udvider sine børn præcis én gang, hvilket afgrænser det samlede arbejde til antallet af distinkte dictionaries plus den samlede længde af deres /Kids-arrays. Dybden holder op med at betyde noget: en kæde på 4.096 niveauer er bare 4.096 iterationer af en løkke og 4.096 poster i et hash set

Rækkefølgen betyder dog stadig noget, og stakken skal fyldes baglæns for at bevare den. Børn pushes fra sidste indeks ned til første, så det venstre barn poppes først, og bladene kommer ud i samme venstre-til-højre-rækkefølge, som produceren skrev dem. GetPageLabel er afhængig af det: den går hvert optalt interval igennem og anvender det sidste, hvis startindeks ligger på eller under siden, så at vende optællingen om ville stille give side 200 forordningsstilen. Skelettet nedenfor viser mønsteret på en abstrakt nodetype, uafhængigt af enhver PDF object model

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // tom på et blad
    Keys: TArray<string>;      // bladnøgler, sorteret af en pænt opførende producer
    Values: TArray<Integer>;   // parallelt med Keys
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// /Limits er et hint: kun et velformet, ordnet par må beskære en gren
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 eller delt barn: set det
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // Push højre-til-venstre, så det venstre barn poppes først
        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;
      // Et miss i dette blad er ikke en dom: fortsæt med at poppe søskende
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

Hvorfor kan et opslag ikke stoppe ved den første matchende gren?

Et opslag kan ikke stoppe ved den første gren, hvis interval matcher, for /Limits-intervaller i en rigtig fil kan overlappe eller lyve, og grenen, der hævder nøglen, er ikke nødvendigvis den gren, der holder den. Opslagene før v3.539.45 satte et Found-flag ved det første barn, hvis /Limits dækkede nøglen, gik ned i det og kiggede aldrig på en anden søskende. Viste det barn sig at være tomt, forældet eller en løkke tilbage til roden, var svaret nil, selv når den allernæste søskende holdt nøglen

Den omskrevne FindTreeValue, der nu bærer både NameTreeLookup og NumTreeLookup, pusher hvert barn, hvis interval ikke udelukker nøglen, og bliver ved med at poppe, til den finder et match eller tømmer stakken. Et miss i ét blad er bare et miss i ét blad. I et velformet træ koster det ikke noget ekstra; i et beskadiget koster det et par ekstra nodebesøg og returnerer det rigtige svar

Bladsøgningen følger samme filosofi. ISO 32000-1 kræver, at nøglerne i et /Names-array er sorteret efter byteværdi, så bladet søges først med en binær søgning. Fejler den, falder PDFlibPas tilbage til en lineær gennemgang af parrene, for et blad i forkert rækkefølge ville ellers gøre en tilstedeværende nøgle usynlig. Sortering er en hurtig vej, ikke et filter

Opslaget nægter også at gætte ved én strukturel modsætning. Table 36 lader en node bære enten /Kids eller /Names, aldrig begge, og opslagsvejen behandler en node, der bærer begge, som misdannet og springer den over i stedet for at vælge én fortolkning. Optællingsveje som EnumNumTree er mere eftergivende og følger /Kids, når begge er til stede

Hvad må en reader stole på /Limits til?

En reader må kun stole på /Limits til at springe arbejde over, aldrig til at afgøre, at en nøgle mangler, og kun når paret er velformet. Table 36 siger, at mellem- og bladnoder skal bære /Limits som et toelements-array af den mindste og største nøgle, men i praksis forsvinder posten efter håndredigeringer, indeholder tal i et navnetræ eller ankommer med grænserne byttet om. PDFlibPas v3.539.45 og v3.539.51 behandler hvert tilfælde på samme måde: kan intervallet ikke læses som et ordnet par af den rigtige type, forbliver barnet søgbart

• Manglende /Limits: det gamle interval-tjek returnerede False, og barnet blev sprunget helt over, så en producer, der glemte posten, gjorde sin hele subtree utilgængelig. Siden v3.539.45 søges barnet
• Forkert type eller forkert længde, som tal i et navnetræ eller et ét-elements-array: behandles præcis som en manglende post siden v3.539.45
• Omvendte grænser som [(Z) (A)] eller [9 0]: v3.539.45 brugte dem stadig, og ingen nøgle kan opfylde Lo <= Key <= Hi, når Lo > Hi, så grenen blev udelukket ved hvert opslag. Siden v3.539.51 bruges et interval til beskæring, kun når dets nedre grænse ikke overstiger dets øvre
• Velformet, ordnet og korrekt: bruges til at springe grenen over, hvilket er hele pointen med posten

De rigtige nøgler afgør udfaldet i hvert tilfælde. Et fjendtligt /Limits kan få PDFlibPas til at besøge flere noder end nødvendigt, men et misdannet kan ikke længere få en eksisterende destination til at forsvinde. Set fra kalderens side ændres intet: GetNamedDestination returnerer 0, når navnet virkelig mangler, og et destination-ID ellers, og destinationsfunktionerne tager derfra

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;
    // Catalog /Dests (PDF 1.1) først, derefter /Dests-navnetræet
    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;

Kørt mod en håndbygget fil, hvis /Dests-rod har ét barn, der looper tilbage til roden under et [(a) (z)]-interval, og et andet barn med den rigtige post under omvendte [(z) (a)]-limits, opløser denne procedure destinationen til side 2 med view type 2 (Fit). Før v3.539.45 returnerede samme opslag 0, for det loopende barn hævdede nøglen først, og søgningen nåede aldrig dets søskende; v3.539.45 alene returnerede stadig 0, for det omvendte interval udelukkede det rigtige blad. Læser du derefter outline'en, der peger på disse destinationer, dækker lederartiklen om læsning af PDF-bookmark- og annotation-actions i Delphi action-siden

Hvordan brød et blad med 32.769 navne TPDFNameTree?

Et blad med 32.769 navne/værdi-par brød TPDFNameTree, fordi dets interne FindIndex pakkede to tal ind i én 32-bit Integer: bladets position i den interne array-liste i de øverste 16 bit og post-offsetet inden for bladets /Names-array i de nederste 16 bit. Hvert par optager to array-slots, så par nr. 32.769, parindeks 32.768, starter ved offset 65.536, hvilket er $10000. Den værdi løber ind i den øverste halvdel, og dekoderen læste den tilbage som offset 0 i næste blad

TPDFNameTree er klassen bag vedhæftninger, globale JavaScript-pakker og navnetræsdestination-skrivninger, hvilket gør konsekvenserne konkrete. I et ét-blads-træ er der intet næste blad, så FindKey og DeleteKey indekserede forbi slutningen af bladlisten; i et multi-blads-træ returnerede eller slettede de første par af følgende blad i stedet for det anmodede. Imens kørte HasKey sin egen scanning og meldte nøglen som til stede, så klassen modsagde sig selv. En genereret referencemanual med ét navngivet mål pr. API-symbol krydser 32.768 poster uden at anstrenge sig, og nogle producenter skriver alle ind i ét fladt blad

Siden v3.539.45 returnerer FindIndex array-indekset gennem en separat out-parameter og det fulde post-offset som sit resultat, så ingen af værdierne trunkeres. Samme release strammede to naboer. KeyName tæller og returnerer nu kun ægte strengnøgler og returnerer en tom streng for et indeks på 0 eller derunder, hvor den tidligere castede, hvad end objektet efter en ugyldig nøgle var. HasKey behandler ikke længere en numerisk eller andenvis ugyldig nøgle som et tomt navn. For et blad som [(Valid) 42 123 456] er HasKey('') nu False, og KeyName(2) returnerer en tom streng

procedure AuditTrees(const FileName: string);
var
  Lib: TPDFlib;
  I: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile(FileName, '') <> 1 then
      Exit;
    // /PageLabels-nummertræ; filer uden ét returnerer rene sidetal
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // /EmbeddedFiles-navnetræ; indekser er 1-baserede, ikke-streng-nøgler skippes
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // navn, MIME-type
    // /JavaScript-navnetræ: listar pakkenavne, eksekverer intet
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

På samme håndbyggede fil, hvis /PageLabels-rod lister ét blad to gange og refererer sig selv, printer denne audit i og A-1 for de to sider, hvert interval én gang, og den enkelte scriptpakke fra et /JavaScript-træ, der også peger tilbage på sin egen rod. Skrivesiden af sidelabels har sin egen historie med /Kids-rodder, dækket i at fikse PDF-sidelabels gemt i /Kids-nummertræer; AddPageLabels flader sådan en rod ud, inden den indsætter, og den støtter sig til samme EnumNumTree-optælling, som er beskrevet her

Hvad garanterer denne hærdning stadig ikke?

Hærdningen garanterer terminering, stabil rækkefølge og korrekte resultater for træer, hvis rigtige nøgler er intakte; den får ikke et beskadiget træ til at betyde, hvad dets forfatter mente. Flere grænser er værd at kende, inden du bygger på den

• Visited-settet virker efter objektidentitet. To distinkte dictionaries med identisk indhold er to noder, så en producent, der kopierer et blad i stedet for at referere det, giver stadig duplikerede poster
• Et velformet, ordnet men forkert /Limits beskærer stadig. En reader, der bruger intervaller som en optimering, kan ikke samtidig være immun over for et interval, der lyver troværdigt; det eneste alternativ er at ignorere /Limits helt og scanne hvert blad
• Optælling bevarer filrækkefølge, men sorterer ikke. GetPageLabel anvender det sidste optalte interval på eller under siden, så en producent, der skriver intervaller i uorden, får filrækkefølge-semantik
• Hukommelsen vokser med antallet af distinkte noder og poster. Gennemløbet tilføjer en liste og et hash set, ikke mere, men et navnetræ på 100 MB er stadig et navnetræ på 100 MB efter parsing
• Duplikerede nøgler inde i ét blad meldes ikke. Den binære søgning returnerer, hvilket matchende par den rammer først; det lineære fallback beholder det sidste match, den scanner

Hurtig reference: læsning af PDF-træer fra utroværdige filer

• Opgradér til v3.539.45 eller senere for cykelsikker, staksikker gennemløbning af navnetræer og nummertræer, og til v3.539.51 eller senere, så omvendte /Limits ikke længere skjuler nøgler
• Behandl GetNamedDestination, der returnerer 0, som "fraværende", og GetDestPage, der returnerer 0, som "til stede men ubrugelig"
• Brug GlobalJavaScriptCount og GlobalJavaScriptPackageName til /JavaScript-navnetræet; GetDocJavaScript læser i stedet katalogets /AA-triggere
• Indeksér vedhæftninger og scriptpakker fra 1 til det antal, biblioteket melder; ugyldige nøgler tælles ikke med
• I din egen trækode: markér noder som besøgt ved pop, push børn i omvendt rækkefølge, og lad /Limits beskære, kun når det er et velformet, ordnet par

Pre-flight-værktøjer, arkiveringsprogrammer og viewers læser disse træer, før nogen side renderer, så de skal overleve, hvad end der ankommer i en uploadkø. Trælæserne ovenfor følger med PDFlibPas, PDF Library til Delphi, som bygger med både Delphi og Free Pascal