PDFlibPas name trees: cycli, foute /Limits en reuze-leaves

PDFlibPas, de losLab PDF Library voor Delphi, doorloopt PDF name trees en number trees sinds v3.539.45 met een expliciete stack en een visited set, dus cyclische /Kids, gedeelde kinderen en bomen van duizenden niveaus diep raken de call stack niet meer uitgeput en dubberen geen entries. Sinds v3.539.51 verbergt een ontbrekend, misvormd of omgekeerd /Limits-paar nooit meer een tak die de key bevat. Named destinations, page labels, attachments en document-level JavaScript lezen allemaal via deze twee codepaden, en daarmee horen ze bij het aanvalsoppervlak van elke PDF die u niet zelf heeft geproduceerd

De trigger is zelden exotisch. Een fuzzer, een vijandige upload of een buggy incrementele save schrijft een /Kids-entry die terugwijst naar een voorouder, en een recursieve walker sterft met een stack overflow op een bestand van twee kilobyte. De stillere falering is een lookup die een kapotte /Limits-array vertrouwt en "not found" meldt voor een destination die er duidelijk in staat

Waar duiken name trees en number trees op in een PDF?

Name trees en number trees duiken overal op waar een PDF een grote verzameling keys aan objecten koppelt, en PDFlibPas leest er ten minste vier van via publieke API's. ISO 32000-1 §7.9.6 definieert de name tree (string keys, Table 36) en §7.9.7 de number tree (integer keys, Table 37). Het zijn allebei tamelijk gebalanceerde bomen waarvan de root en tussenliggende nodes /Kids voeren, waarvan de leaves de gesorteerde key/value-paren in /Names of /Nums voeren, en waarvan de niet-root-nodes een /Limits-array van twee elementen voeren met de kleinste en grootste key eronder

Tree	Waar hij huist	Specificatie	PDFlibPas lees-API
Named destinations	/Dests in de name dictionary	§12.3.2.3	GetNamedDestination, daarna GetDestPage / GetDestType
Page labels	/PageLabels in de catalog (number tree)	§12.4.2	GetPageLabel
Attachments	/EmbeddedFiles in de name dictionary	§7.7.4, §7.11.4	EmbeddedFileCount, GetEmbeddedFileStrProperty
Document-level JavaScript	/JavaScript in de name dictionary	§7.7.4	GlobalJavaScriptCount, GlobalJavaScriptPackageName

Twee details in die tabel zijn makkelijk te missen. Named destinations hebben ook een oudere PDF 1.1-vorm, een platte /Dests-dictionary in de catalog met name objects als sleutel, en GetNamedDestination controleert eerst die dictionary voordat hij afdaalt in de name tree van PDF 1.2. En GetDocJavaScript is helemaal geen name-tree-lezer: hij geeft de scripts terug die aan documenttriggers in de /AA-dictionary van de catalog hangen (WS, DS, WP, DP, DC), terwijl de named script packages die draaien zodra een document opent in de /JavaScript name tree wonen

Elke byte van die structuren komt uit het bestand. De specificatie zegt wat een schrijver moet produceren; ze kan een lezer er niet van weerhouden iets anders te ontvangen, en dat is dezelfde les als bij het verharden van een Pascal PDF-parser tegen kwaadaardige bestanden, hier toegepast op boomvorm in plaats van buffergroottes

Waarom crasht een cyclische /Kids-array een recursieve tree walker?

Een cyclische /Kids-array crasht een recursieve walker omdat niets in de recursie opmerkt dat hij een node al eens heeft gezien, dus een kind dat naar zijn eigen voorouder verwijst maakt van een eindig bestand een oneindige afdaling. Vóór v3.539.45 riepen NameTreeLookup, NumTreeLookup, EnumNumTree en de interne TPDFNameTree.ProcessNode zichzelf allemaal één keer per kind aan. Eén zelfverwijzing was genoeg om het proces te beëindigen, en een legitieme maar zeer diepe boom kon hetzelfde flikken zonder enige cyclus

Een mildere variant corrumpeert resultaten in plaats van te crashen. Als twee /Kids-entries naar dezelfde leaf verwijzen, bezoekt een naïeve enumeratie haar twee keer, en een attachmenttelling of een lijst van script packages meldt entries die niet bestaan

De fix vervangt recursie door een expliciete last-in, first-out-stack op de heap en een visited set gesleuteld op dictionary-identiteit. Een node wordt gemarkeerd zodra hij wordt gepopt, niet zodra hij wordt gepusht, dus een cyclische verwijzing mag kort op de stack zitten maar wordt weggegooid op het moment dat hij weer omhoogkomt. Elke unieke node vouwt zijn kinderen precies één keer uit, wat het totale werk begrenst op het aantal unieke dictionaries plus de totale lengte van hun /Kids-arrays. Diepte stopt met tellen: een keten van 4.096 niveaus is gewoon 4.096 iteraties van een lus en 4.096 entries in een hash set

Volgorde telt echter nog steeds, en de stack moet omgekeerd gevoed worden om haar te houden. Kinderen worden vanaf de laatste index tot de eerste gepusht, dus het linkerkind wordt eerst gepopt en de leaves komen in dezelfde linker-naar-rechter-volgorde naar buiten als waarin de producent ze schreef. GetPageLabel leunt daarop: hij doorloopt elke geënumereerde range en past de laatste toe waarvan de startindex op of onder de pagina ligt, dus de enumeratie omdraaien zou pagina 200 stilletjes de front-matter-stijl geven. Het skelet hieronder toont het patroon op een abstract nodetype, los van elk PDF-objectmodel

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // leeg op een leaf
    Keys: TArray<string>;      // leaf-keys, gesorteerd door een nette producent
    Values: TArray<Integer>;   // parallel aan Keys
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// /Limits is een hint: alleen een goed gevormd, geordend paar mag een tak snoeien
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;                      // cycle of gedeeld kind: al gezien
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // Van rechts naar links pushen zodat het linkerkind eerst wordt gepopt
        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;
      // Een miss in deze leaf is geen oordeel: blijf siblings poppen
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

Waarom kan een lookup niet stoppen bij de eerste matchende tak?

Een lookup kan niet stoppen bij de eerste tak waarvan de range matcht, want /Limits-ranges in een echt bestand kunnen overlappen of liegen, en de tak die de key claimt is niet noodzakelijk de tak die hem bevat. De lookups van vóór v3.539.45 zetten een Found-vlag op het eerste kind waarvan de /Limits de key omsloot, daalden erin af en keken nooit naar een andere sibling. Bleek dat kind leeg, verouderd of een lus terug naar de root, dan was het antwoord nil, ook al hield de allereerstvolgende sibling de key

De herschreven FindTreeValue, die nu zowel NameTreeLookup als NumTreeLookup onderbouwt, pusht elk kind waarvan de range de key niet uitsluit en blijft poppen tot hij een match vindt of de stack leeg is. Een miss in één leaf is gewoon een miss in één leaf. In een goed gevormde boom kost dat niets extra; in een beschadigde kost het een paar extra nodebezoeken en levert het juiste antwoord op

Het doorzoeken van een leaf volgt dezelfde filosofie. ISO 32000-1 eist dat de keys in een /Names-array op bytewaarde gesorteerd zijn, dus de leaf wordt eerst met een binaire zoektocht doorzocht. Lukt dat niet, dan valt PDFlibPas terug op een lineaire scan van de paren, want een leaf in verkeerde volgorde zou anders een aanwezige key onzichtbaar maken. Sorteren is een snel pad, geen filter

De lookup weigert ook te gokken bij één structurele contradictie. Table 36 staat een node of /Kids of /Names toe, nooit allebei, en het lookuppad behandelt een node die allebei voert als misvormd en slaat haar over in plaats van één interpretatie te kiezen. Enumeratiepaden zoals EnumNumTree zijn soepeler en volgen /Kids als allebei aanwezig zijn

Waarvoor mag een lezer /Limits vertrouwen?

Een lezer mag /Limits alleen vertrouwen om werk over te slaan, nooit om te besluiten dat een key afwezig is, en alleen als het paar goed gevormd is. Table 36 zegt dat tussenliggende en leaf-nodes /Limits moeten voeren als een array van twee elementen met de kleinste en grootste key, maar in de praktijk raakt de entry kwijt na handmatige edits, bevat ze nummers in een name tree, of komt ze binnen met verwisselde grenzen. PDFlibPas v3.539.45 en v3.539.51 beslechten elk geval op dezelfde manier: valt de range niet te lezen als een geordend paar van het juiste type, dan blijft het kind doorzoekbaar

• Ontbrekende /Limits: de oude rangecheck gaf False terug en het kind werd ronduit overgeslagen, dus een producent die de entry vergat maakte zijn hele subtree onbereikbaar. Sinds v3.539.45 wordt het kind doorzocht
• Verkeerd type of verkeerde lengte, zoals nummers in een name tree of een array met één element: sinds v3.539.45 exact behandeld als een ontbrekende entry
• Omgekeerde grenzen zoals [(Z) (A)] of [9 0]: v3.539.45 gebruikte ze nog, en geen enkele key kan aan Lo <= Key <= Hi voldoen als Lo > Hi, dus de tak werd bij elke lookup uitgesloten. Sinds v3.539.51 wordt een range alleen gebruikt om te snoeien als zijn ondergrens zijn bovengrens niet overstijgt
• Goed gevormd, geordend en correct: gebruikt om de tak over te slaan, en dat is precies het doel van de entry

De echte keys bepalen in elk geval de uitkomst. Een vijandige /Limits kan PDFlibPas meer nodes laten bezoeken dan nodig, maar een misvormde kan een bestaande destination niet langer laten verdwijnen. Vanuit de aanroeper verandert niets: GetNamedDestination geeft 0 terug als de naam echt afwezig is en anders een destination-ID, en de destination-functies pakken het daar op

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;
    // Eerst catalogus /Dests (PDF 1.1), daarna de /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;

Draai tegen een handgebouwd bestand waarvan de /Dests-root één kind heeft dat onder een [(a) (z)]-range terugluccht naar de root en een tweede kind dat de echte entry houdt onder omgekeerde [(z) (a)]-limits, dan lost deze procedure de destination op naar pagina 2 met view type 2 (Fit). Vóór v3.539.45 gaf dezelfde lookup 0 terug, want het lussende kind claimde de key eerst en de zoektocht bereikte zijn sibling nooit; alleen v3.539.45 gaf nog steeds 0 terug, want de omgekeerde range sloot de echte leaf uit. Als u daarna de outline leest die naar deze destinations wijst, behandelt het zusterartikel over PDF-bookmark- en annotatie-acties lezen in Delphi de actiekant

Hoe brak een leaf met 32.769 namen TPDFNameTree?

Een leaf met 32.769 naam/waarde-paren brak TPDFNameTree, want zijn interne FindIndex propte twee getallen in één 32-bit Integer: de positie van de leaf in de interne arraylijst in de hoge 16 bits en de entry-offset binnen de /Names-array van die leaf in de lage 16 bits. Elk paar beslaat twee arrayslots, dus het 32.769ste paar, paarindex 32.768, begint op offset 65.536, oftewel $10000. Die waarde loopt door in de hoge helft, en de decoder las haar terug als offset 0 in de volgende leaf

TPDFNameTree is de klasse achter attachments, globale JavaScript-pakketten en named-destination-schrijfacties, wat de gevolgen concreet maakt. In een boom met één leaf is er geen volgende leaf, dus FindKey en DeleteKey indexeerden voorbij het einde van de leaflijst; in een boom met meerdere leaves gaven of verwijderden ze het eerste paar van de volgende leaf in plaats van het gevraagde. Ondertussen draaide HasKey zijn eigen scan en meldde de key als aanwezig, dus de klasse sprak zichzelf tegen. Een gegenereerde referentiemanual met één named destination per API-symbol komt 32.768 entries voorbij zonder zich in te spannen, en sommige producenten schrijven ze allemaal in één platte leaf

Sinds v3.539.45 geeft FindIndex de arrayindex terug via een aparte out-parameter en de volledige entry-offset als resultaat, dus geen van beide waarden wordt afgekapt. Dezelfde release strakte twee buren aan. KeyName telt en geeft nu alleen echte string keys terug en geeft een lege string terug voor een index van 0 of lager, waar hij eerder welk object dan ook dat op een ongeldige key volgde castte. HasKey behandelt een numerieke of anderszins ongeldige key niet langer als een lege naam. Voor een leaf zoals [(Valid) 42 123 456] is HasKey('') nu False en geeft KeyName(2) een lege string terug

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; bestanden zonder krijgen gewone paginanummers
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // /EmbeddedFiles name tree; indexen zijn 1-based, niet-string-keys overgeslagen
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // naam, MIME-type
    // /JavaScript name tree: pakketnamen tonen, niets uitvoeren
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

Op hetzelfde handgebouwde bestand, waarvan de /PageLabels-root één leaf twee keer opvoert en naar zichzelf verwijst, print deze audit i en A-1 voor de twee pagina's, elke range één keer, en het ene script package uit een /JavaScript-boom die ook naar zijn eigen root wijst. De schrijfkant van page labels heeft een eigen voorgeschiedenis met /Kids-roots, behandeld in PDF page labels repareren die in /Kids number trees zitten; AddPageLabels vlakt zo'n root af voordat hij invoegt, en leunt op dezelfde EnumNumTree-enumeratie die hier is beschreven

Wat garandeert deze verharding nog steeds niet?

De verharding garandeert terminatie, stabiele volgorde en correcte resultaten voor bomen waarvan de echte keys intact zijn; ze maakt van een beschadigde boom geen boom die bedoelt wat zijn auteur bedoelde. Een paar grenzen zijn de moeite waard om te kennen voordat u erop bouwt

• De visited set werkt op objectidentiteit. Twee verschillende dictionaries met identieke inhoud zijn twee nodes, dus een producent die een leaf kopieert in plaats van te refereren levert nog steeds dubbele entries op
• Een goed gevormde, geordende maar foute /Limits snoeit nog steeds. Een lezer die ranges als optimalisatie gebruikt kan niet tegelijk immuun zijn voor een range die geloofwaardig liegt; het enige alternatief is /Limits volledig negeren en elke leaf scannen
• Enumeratie bewaart bestandsvolgorde maar sorteert niet. GetPageLabel past de laatst geënumereerde range op of onder de pagina toe, dus een producent die ranges in verkeerde volgorde schrijft krijgt bestandsvolgorde-semantiek
• Geheugen groeit mee met het aantal unieke nodes en entries. De traversal voegt een lijst en een hash set toe, niets meer, maar een name tree van 100 MB blijft na het parsen een name tree van 100 MB
• Dubbele keys binnen één leaf worden niet gemeld. De binaire zoektocht geeft het eerst geraakte matchende paar terug; de lineaire fallback houdt de laatste match die hij scant

Snelnaslag: PDF-bomen lezen uit onbetrouwbare bestanden

• Upgrade naar v3.539.45 of later voor cycle-veilige, stack-veilige traversal van name trees en number trees, en naar v3.539.51 of later zodat omgekeerde /Limits geen keys meer verbergen
• Zie GetNamedDestination die 0 teruggeeft als "afwezig", en GetDestPage die 0 teruggeeft als "aanwezig maar onbruikbaar"
• Gebruik GlobalJavaScriptCount en GlobalJavaScriptPackageName voor de /JavaScript name tree; GetDocJavaScript leest in plaats daarvan catalog-/AA-triggers
• Indexeer attachments en script packages van 1 tot het aantal dat de library meldt; ongeldige keys worden niet meegeteld
• Markeer in uw eigen boomcode nodes als bezocht bij het poppen, push kinderen omgekeerd, en laat /Limits alleen snoeien als het een goed getypeerd, geordend paar is

Pre-flighttools, archivers en viewers lezen deze bomen voordat er ook maar één pagina wordt gerenderd, dus ze moeten overleven wat er ook in een uploadwachtrij aankomt. De hierboven beschreven boomlezers worden geleverd met PDFlibPas, de PDF Library for Delphi, die met zowel Delphi als Free Pascal bouwt