PDFlibPas name trees: sykler, feil Limits og enorme blader

PDFlibPas, losLabs PDF Library for Delphi, vandrer gjennom PDF name trees og number trees med en eksplisitt stakk og et visited-sett siden v3.539.45, så sykliske /Kids, delte barn og trær tusenvis av nivåer dype tømmer ikke lenger call stack-en eller dupliserer oppføringer. Siden v3.539.51 skjuler et manglende, misdannet eller reversert /Limits-par aldri en gren som holder nøkkelen. Navngitte destinasjoner, page labels, vedlegg og dokumentnivå JavaScript leses alle gjennom disse to kode-stiene, noe som gjør dem til en del av angrepsflaten til enhver PDF du ikke produserte selv

Utløseren er sjelden eksotisk. En fuzzer, et fiendtlig opplastet innhold eller en buggy inkrementell lagring skriver en /Kids-oppføring som peker tilbake på en forfar, og en rekursiv vandrer dør med en stack overflow på en to-kilobytes fil. Den stille feilen er et oppslag som stoler på en ødelagt /Limits-array og rapporterer «not found» for en destinasjon som åpenbart er der

Hvor dukker name trees og number trees opp i en PDF?

Name trees og number trees dukker opp der en PDF mapper et stort sett med nøkler til objekter, og PDFlibPas leser minst fire av dem gjennom offentlige API-er. ISO 32000-1 §7.9.6 definerer name tree-en (strengnøkler, Table 36) og §7.9.7 number tree-en (heltallsnøkler, Table 37). Begge er nokså balanserte trær hvis rot- og mellomnoder bærer /Kids, hvis blader bærer de sorterte nøkkel/verdi-parene i /Names eller /Nums, og hvis ikke-rot-noder bærer et /Limits-array med to elementer: den minste og største nøkkelen under dem

Tre	Hvor den bor	Spesifikasjon	PDFlibPas lese-API
Navngitte destinasjoner	/Dests i name dictionary-en	§12.3.2.3	GetNamedDestination, så GetDestPage / GetDestType
Page labels	/PageLabels i katalogen (number tree)	§12.4.2	GetPageLabel
Vedlegg	/EmbeddedFiles i name dictionary-en	§7.7.4, §7.11.4	EmbeddedFileCount, GetEmbeddedFileStrProperty
Dokumentnivå JavaScript	/JavaScript i name dictionary-en	§7.7.4	GlobalJavaScriptCount, GlobalJavaScriptPackageName

To detaljer i den tabellen er lette å overse. Navngitte destinasjoner har også en eldre PDF 1.1-form, en ren /Dests-ordbok i katalogen nøklet med name-objekter, og GetNamedDestination sjekker den ordboken først før den stiger ned i PDF 1.2 name tree-en. Og GetDocJavaScript er ikke en name tree-leser i det hele tatt: den returnerer skriptene festet til dokumenttriggere i katalogens /AA-ordbok (WS, DS, WP, DP, DC), mens de navngitte skriptpakkene som kjører når et dokument åpnes, bor i /JavaScript name tree-en

Hver byte av de strukturene kommer fra filen. Spesifikasjonen sier hva en skriver skal produsere; den kan ikke hindre en leser fra å motta noe annet, som er samme lærdom bak herding av en Pascal PDF-parser mot ondsinnede filer, anvendt her på tre-form i stedet for bufferstørrelser

Hvorfor krasjer et syklisk /Kids-array en rekursiv tree walker?

Et syklisk /Kids-array krasjer en rekursiv vandrer fordi ingenting i rekursjonen legger merke til at den har sett en node før, så et barn som refererer til sin egen forfar gjør en endelig fil om til et uendelig dyp. Før v3.539.45 kalte NameTreeLookup, NumTreeLookup, EnumNumTree og den interne TPDFNameTree.ProcessNode alle seg selv én gang per barn. En enkelt selvreferanse var nok til å avslutte prosessen, og et legitimt men svært dypt tre kunne gjøre det samme uten noen sykel i det hele tatt

En mildere variant korruperer resultater i stedet for å krasje. Når to /Kids-oppføringer refererer til samme blad, besøker en naiv oppregning det to ganger, og et antall vedlegg eller en liste over skriptpakker rapporterer oppføringer som ikke finnes

Fiksen erstatter rekursjon med en eksplisitt sist-inn, først-ut-stakk på haugen og et visited-sett nøklet etter ordbokidentitet. En node markeres når den poppes, ikke når den pushes, så en syklisk referanse kan ligge på stakken kort, men forkastes i det øyeblikket den kommer opp igjen. Hver distinkt node utvider barna sine nøyaktig én gang, noe som avgrenser det totale arbeidet med antallet distinkte ordbøker pluss total lengde av deres /Kids-arrayer. Dybde slutter å bety noe: en kjede på 4 096 nivåer er bare 4 096 iterasjoner av en løkke og 4 096 oppføringer i et hash-sett

Rekkefølgen betyr likevel noe, og stakken må mates baklengs for å beholde den. Barn pushes fra siste indeks ned til første, så det venstre barnet poppes først og bladene kommer ut i samme venstre-til-høyre-rekkefølge som produsenten skrev. GetPageLabel er avhengig av det: den går gjennom hvert oppregnede område og anvender det siste hvis startindeks er på eller under siden, så å reversere oppregningen ville i stillhet gitt side 200 front-matter-stilen. Skjelettet nedenfor viser mønsteret på en abstrakt nodetype, uavhengig av enhver PDF-objektmodell

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // tom på et blad
    Keys: TArray<string>;      // bladnøkler, sortert av en veloppført produsent
    Values: TArray<Integer>;   // parallell med Keys
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// /Limits er et hint: bare et velformet, ordnet par kan beskjæ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;                      // sykel eller delt barn: sett det
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // Push høyre-til-venstre så det venstre barnet 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 bom i dette bladet er ikke en dom: fortsett å poppe søsken
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

Hvorfor kan ikke et oppslag stoppe ved den første matchende grenen?

Et oppslag kan ikke stoppe ved den første grenen hvis område matcher, for /Limits-områder i en ekte fil kan overlappe eller lyve, og grenen som hevder nøkkelen, er ikke nødvendigvis grenen som holder den. Oppslagene før v3.539.45 satte et Found-flagg på det første barnet hvis /Limits dekket nøkkelen, steg ned i det, og så aldri på et annet søsken. Viste det barnet seg å være tomt, foreldet eller en løkke tilbake til roten, var svaret nil, selv når helt neste søsken holdt nøkkelen

Den omskrevne FindTreeValue, som nå ligger bak både NameTreeLookup og NumTreeLookup, pusher hvert barn hvis område ikke ekskluderer nøkkelen og fortsetter å poppe til den finner en match eller tømmer stakken. Et bom inne i ett blad er bare et bom inne i ett blad. I et velformet tre koster dette ingenting ekstra; i et skadet koster det noen flere nodebesøk og gir riktig svar

Bladsøk følger samme filosofi. ISO 32000-1 krever at nøklene i et /Names-array er sortert etter byteverdi, så bladet søkes først med binærsøk. Feiler det, faller PDFlibPas tilbake til en lineær skanning av parene, for et ut-av-rekkefølge-blad ville ellers gjort en tilstedeværende nøkkel usynlig. Sortering er en hurtigsti, ikke et filter

Oppslaget nekter også å gjette på én strukturell motsigelse. Table 36 lar en node bære enten /Kids eller /Names, aldri begge, og oppslagsstien behandler en node som bærer begge som misdannet og hopper over den i stedet for å velge én tolkning. Oppregningsstier som EnumNumTree er mer milde og følger /Kids når begge er til stede

Hva kan en leser stole på at /Limits gjelder?

En leser kan stole på /Limits bare for å hoppe over arbeid, aldri for å avgjøre at en nøkkel mangler, og bare når paret er velformet. Table 36 sier at mellom- og bladnoder skal bære /Limits som et to-element-array av den minste og største nøkkelen, men i praksis forsvinner oppføringen etter manuelle redigeringer, holder tall i en name tree, eller kommer med grensene byttet. PDFlibPas v3.539.45 og v3.539.51 avgjør hvert tilfelle på samme måte: kan området ikke leses som et ordnet par av riktig type, forblir barnet søkbart

• Manglende /Limits: den gamle områdekontrollen returnerte False og barnet ble hoppet fullstendig over, så en produsent som glemte oppføringen, gjorde hele sitt subtree utilgjengelig. Siden v3.539.45 søkes barnet
• Feil type eller feil lengde, som tall i en name tree eller et array med ett element: behandlet nøyaktig som en manglende oppføring siden v3.539.45
• Reverserte grenser som [(Z) (A)] eller [9 0]: v3.539.45 brukte dem fortsatt, og ingen nøkkel kan tilfredsstille Lo <= Key <= Hi når Lo > Hi, så grenen ble ekskludert for hvert oppslag. Siden v3.539.51 brukes et område til beskjæring bare når dets nedre grense ikke overstiger dets øvre
• Velformet, ordnet og korrekt: brukes til å hoppe over grenen, som er hele poenget med oppføringen

De ekte nøklene avgjør utfallet i hvert tilfelle. En fiendtlig /Limits kan få PDFlibPas til å besøke flere noder enn nødvendig, men en misdannet kan ikke lenger få en eksisterende destinasjon til å forsvinne. Fra kallerens side endrer ingenting seg: GetNamedDestination returnerer 0 når navnet virkelig mangler og en destinasjons-ID ellers, og destinasjonsfunksjonene tar det 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, så /Dests name tree-en
    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;

Kjørt mot en håndbygd fil hvis /Dests-rot har ett barn som looper tilbake til roten under et [(a) (z)]-område og et andre barn som holder den ekte oppføringen under reverserte [(z) (a)]-limits, løser denne prosedyren destinasjonen til side 2 med visningstype 2 (Fit). Før v3.539.45 returnerte samme oppslag 0, for det loopende barnet hevdet nøkkelen først, og søket nådde aldri sitt søsken; v3.539.45 alene returnerte fortsatt 0, for det reverserte området ekskluderte det ekte bladet. Leter du så i outline-en som peker på disse destinasjonene, dekker følgeartikkelen om å lese PDF-bokmerke- og annoteringshandlinger i Delphi handlingssiden

Hvordan knuste et blad med 32 769 navn TPDFNameTree?

Et blad med 32 769 navn/verdi-par knuste TPDFNameTree fordi dets interne FindIndex pakket to tall inn i én 32-bits Integer: bladets posisjon i den interne arraylisten i de øvre 16 bitene og oppførings-offseten innenfor bladets /Names-array i de lavere 16 bitene. Hvert par opptar to array-plasser, så det 32 769. paret, parindeks 32 768, starter på offset 65 536, som er $10000. Den verdien bæres inn i den øvre halvdelen, og dekoderen leste den tilbake som offset 0 i neste blad

TPDFNameTree er klassen bak vedlegg, globale JavaScript-pakker og skriving av navngitte destinasjoner, noe som gjør konsekvensene konkrete. I et tre med ett blad finnes det ikke noe neste blad, så FindKey og DeleteKey indekserte forbi slutten av bladlisten; i et tre med flere blader returnerte eller slettet de det første paret i følgende blad i stedet for det etterspurte. I mellomtiden kjørte HasKey sin egen skanning og rapporterte nøkkelen som til stede, så klassen motsa seg selv. En generert referansehåndbok med én navngitt destinasjon per API-symbol krysser 32 768 oppføringer uten å prøve, og noen produsenter skriver alle inn i ett enkelt flatt blad

Siden v3.539.45 returnerer FindIndex arrayindeksen gjennom en egen out-parameter og hele oppførings-offseten som sitt resultat, så ingen av verdiene kuttes. Samme utgivelse strammet til to naboer. KeyName teller og returnerer nå bare ekte strengnøkler og returnerer en tom streng for en indeks på 0 eller under, der den tidligere castet hvilket som helst objekt som fulgte en ugyldig nøkkel. HasKey behandler ikke lenger en numerisk eller annenvis ugyldig nøkkel som et tomt navn. For et blad som [(Valid) 42 123 456] er HasKey('') nå 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 number tree; filer uten en returnerer rene sidetall
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // /EmbeddedFiles name tree; indekser er 1-baserte, ikke-streng-nøkler hoppet over
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // navn, MIME-type
    // /JavaScript name tree: list pakkenavn, kjør ingenting
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

På samme håndbygde fil, hvis /PageLabels-rot lister ett blad to ganger og refererer til seg selv, skriver denne revisjonen ut i og A-1 for de to sidene, hvert område én gang, og den ene skriptpakken fra et /JavaScript-tre som også peker tilbake på sin egen rot. Skrivesiden av page labels har sin egen historie med /Kids-røtter, dekket i å fikse PDF page labels lagret i /Kids number trees; AddPageLabels flater ut en slik rot før innsetting, og den er avhengig av samme EnumNumTree-oppregning som er beskrevet her

Hva garanterer denne herdingen fortsatt ikke?

Herdingen garanterer terminering, stabil rekkefølge og korrekte resultater for trær hvis ekte nøkler er intakte; den gjør ikke et skadet tre til å bety det forfatteren mente. Flere begrensninger er verdt å kjenne før du bygger videre på den

• Visited-settet virker etter objektidentitet. To distinkte ordbøker med identisk innhold er to noder, så en produsent som kopierer et blad i stedet for å referere til det, gir fortsatt dupliserte oppføringer
• Et velformet, ordnet men feil /Limits beskjærer fortsatt. En leser som bruker områder som en optimalisering, kan ikke også være immun mot et område som lyver troverdig; eneste alternativ er å ignorere /Limits fullstendig og skanne hvert blad
• Oppregning bevarer filrekkefølge, men sorterer ikke. GetPageLabel anvender det sist oppregnede området på eller under siden, så en produsent som skriver områder i ut-av-rekkefølge, får filrekkefølge-semantikk
• Minne vokser med antallet distinkte noder og oppføringer. Traverseringen legger til en liste og et hash-sett, ingenting mer, men et name tree på 100 MB er fortsatt et name tree på 100 MB etter parsing
• Dupliserte nøkler inne i ett blad rapporteres ikke. Binærsøket returnerer det matchende paret det treffer først; den lineære fallbacken beholder siste match den skanner

Hurtigreferanse: å lese PDF-trær fra utruelige filer

• Oppgrader til v3.539.45 eller senere for sykkeltrygg og stakktrygg traversering av name trees og number trees, og til v3.539.51 eller senere så reverserte /Limits ikke lenger skjuler nøkler
• Behandle GetNamedDestination som returnerer 0 som «fraværende», og GetDestPage som returnerer 0 som «til stede men ubrukelig»
• Bruk GlobalJavaScriptCount og GlobalJavaScriptPackageName for /JavaScript name tree-en; GetDocJavaScript leser katalogens /AA-triggere i stedet
• Indekser vedlegg og skriptpakker fra 1 til antallet biblioteket rapporterer; ugyldige nøkler telles ikke
• I din egen tre-kode, marker noder som besøkt ved pop, push barn i revers, og la /Limits beskjære bare når det er et veltypet, ordnet par

Pre-flight-verktøy, arkiverere og viewere leser disse trærne før noen side rendres, så de må overleve hva som enn ankommer i en opplastingskø. De tre-leserne som er beskrevet over, følger med PDFlibPas, PDF Library for Delphi, som bygger med både Delphi og Free Pascal