Alberi dei nomi in PDFlibPas: cicli, Limits e foglie enormi

PDFlibPas, la PDF Library di losLab per Delphi, percorre gli alberi dei nomi e i number tree del PDF con uno stack esplicito e un insieme dei visitati dalla v3.539.45, così i /Kids ciclici, i figli condivisi e gli alberi migliaia di livelli profondi non esauriscono più lo stack delle chiamate né duplicano voci. Dalla v3.539.51 una coppia /Limits mancante, malformata o invertita non nasconde mai un ramo che contiene la chiave. Named destinations, etichette di pagina, allegati e JavaScript a livello di documento leggono tutti attraverso questi due percorsi di codice, il che li rende parte della superficie d'attacco di qualsiasi PDF che non hai prodotto tu

L'elemento scatenante è raramente esotico. Un fuzzer, un upload ostile o un salvataggio incrementale bacato scrive una voce /Kids che punta indietro a un antenato, e un percorritore ricorsivo muore di stack overflow su un file di due kilobyte. Il fallimento più silenzioso è una ricerca che si fida di un array /Limits rotto e risponde "non trovato" per una destinazione che c'è eccome

Dove compaiono gli alberi dei nomi e dei numeri in un PDF?

Gli alberi dei nomi e i number tree compaiono ovunque un PDF mappa un grande insieme di chiavi a oggetti, e PDFlibPas ne legge almeno quattro attraverso API pubbliche. ISO 32000-1 §7.9.6 definisce il name tree (chiavi stringa, Table 36) e §7.9.7 il number tree (chiavi intere, Table 37). Entrambi sono alberi più o meno bilanciati il cui radice e i cui nodi intermedi portano /Kids, le cui foglie portano le coppie chiave/valore ordinate in /Names o /Nums, e i cui nodi non radice portano un array /Limits a due elementi con la chiave più piccola e più grande sotto di loro

Albero	Dove vive	Specificazione	API di lettura PDFlibPas
Named destinations	/Dests nel dizionario dei nomi	§12.3.2.3	GetNamedDestination, poi GetDestPage / GetDestType
Etichette di pagina	/PageLabels nel catalogo (number tree)	§12.4.2	GetPageLabel
Allegati	/EmbeddedFiles nel dizionario dei nomi	§7.7.4, §7.11.4	EmbeddedFileCount, GetEmbeddedFileStrProperty
JavaScript a livello di documento	/JavaScript nel dizionario dei nomi	§7.7.4	GlobalJavaScriptCount, GlobalJavaScriptPackageName

Due dettagli in quella tabella sono facili da perdere. Le named destinations hanno anche una forma più vecchia del PDF 1.1, un semplice dizionario /Dests nel catalogo indicizzato da oggetti nome, e GetNamedDestination controlla quel dizionario prima di scendere nell'albero dei nomi del PDF 1.2. E GetDocJavaScript non è affatto un lettore di name tree: restituisce gli script attaccati ai trigger del documento nel dizionario /AA del catalogo (WS, DS, WP, DP, DC), mentre i pacchetti di script nominati che girano all'apertura di un documento vivono nell'albero dei nomi /JavaScript

Ogni byte di quelle strutture viene dal file. La specifica dice cosa uno scrittore deve produrre; non può impedire a un lettore di ricevere altro, che è la stessa lezione dietro irrobustire un parser PDF Pascal contro file ostili, applicata qui alla forma dell'albero invece che alle dimensioni dei buffer

Perché un array /Kids ciclico manda in crash un percorritore ricorsivo?

Un array /Kids ciclico manda in crash un percorritore ricorsivo perché nulla nella ricorsione nota di aver già visto un nodo, così un figlio che riferisce il proprio antenato trasforma un file finito in una discesa infinita. Prima della v3.539.45, NameTreeLookup, NumTreeLookup, EnumNumTree e la TPDFNameTree.ProcessNode interna chiamavano tutte sé stesse una volta per figlio. Un solo autoriferimento bastava a terminare il processo, e un albero legittimo ma molto profondo poteva fare lo stesso senza alcun ciclo

Una variante più mite corrompe i risultati invece di crashare. Quando due voci /Kids riferiscono la stessa foglia, un'enumerazione ingenua la visita due volte, e un conteggio di allegati o una lista di pacchetti di script riporta voci che non esistono

La correzione sostituisce la ricorsione con uno stack esplicito last-in, first-out sull'heap e un insieme dei visitati indicizzato per identità del dizionario. Un nodo viene marcato quando viene estratto, non quando viene inserito, così un riferimento ciclico può stare nello stack per un attimo ma viene scartato nel momento in cui riaffiora. Ogni nodo distinto espande i propri figli esattamente una volta, il che limita il lavoro totale al numero di dizionari distinti più la lunghezza totale dei loro array /Kids. La profondità smette di contare: una catena a 4.096 livelli è solo 4.096 iterazioni di un ciclo e 4.096 voci in un hash set

L'ordine però conta ancora, e lo stack va alimentato al contrario per conservarlo. I figli vengono inseriti dall'ultimo indice al primo, così il figlio più a sinistra viene estratto per primo e le foglie escono nello stesso ordine da sinistra a destra in cui il produttore le ha scritte. GetPageLabel dipende da questo: percorre ogni intervallo enumerato e applica l'ultimo il cui indice di partenza è alla pagina o sotto, quindi invertire l'enumerazione passerebbe in silenzio lo stile del frontespizio alla pagina 200. Lo scheletro qui sotto mostra il pattern su un tipo nodo astratto, indipendente da qualsiasi object model PDF

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // vuoto su una foglia
    Keys: TArray<string>;      // chiavi foglia, ordinate da un produttore per bene
    Values: TArray<Integer>;   // parallelo a Keys
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// /Limits è un indizio: solo una coppia ben formata e ordinata può potare un ramo
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;                      // ciclo o figlio condiviso: già visto
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // Inserisci da destra a sinistra così il kid più a sinistra esce per primo
        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;
      // Un mancato ritrovato in questa foglia non è un verdetto: continua coi fratelli
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

Perché una ricerca non può fermarsi al primo ramo corrispondente?

Una ricerca non può fermarsi al primo ramo il cui intervallo corrisponde, perché gli intervalli /Limits in un file reale possono sovrapporsi o mentire, e il ramo che rivendica la chiave non è necessariamente il ramo che la contiene. Le ricerche pre-v3.539.45 impostavano un flag Found sul primo figlio i cui /Limits coprivano la chiave, scendevano lì dentro e non guardavano mai un altro fratello. Se quel figlio si rivelava vuoto, stantio o un giro torna alla radice, la risposta era nil, anche quando il fratello immediatamente successivo teneva la chiave

La FindTreeValue riscritta, che ora sostiene sia NameTreeLookup sia NumTreeLookup, inserisce ogni figlio il cui intervallo non esclude la chiave e continua a pescare finché non trova una corrispondenza o non svuota lo stack. Un mancato ritrovato dentro una foglia è solo un mancato ritrovato dentro una foglia. In un albero ben formato non costa nulla in più; in uno danneggiato costa qualche visita di nodo in più e restituisce la risposta giusta

La ricerca nella foglia segue la stessa filosofia. ISO 32000-1 richiede che le chiavi in un array /Names siano ordinate per valore di byte, così la foglia viene cercata prima con una ricerca binaria. Se fallisce, PDFlibPas ripiega su una scansione lineare delle coppie, perché una foglia fuori ordine altrimenti renderebbe invisibile una chiave presente. L'ordinamento è una via rapida, non un filtro

La ricerca declina inoltre di indovinare su una contraddizione strutturale. La Table 36 consente a un nodo di portare o /Kids o /Names, mai entrambi, e il percorso di ricerca tratta un nodo che porta entrambi come malformato e lo salta invece di scegliere un'interpretazione. I percorsi di enumerazione come EnumNumTree sono più indulgenti e seguono /Kids quando entrambi sono presenti

Di cosa può fidarsi un lettore riguardo a /Limits?

Un lettore può fidarsi di /Limits solo per saltare lavoro, mai per decidere che una chiave è assente, e solo quando la coppia è ben formata. La Table 36 dice che i nodi intermedi e foglia devono portare /Limits come array a due elementi delle chiavi minore e maggiore, ma in pratica la voce sparisce dopo modifiche a mano, tiene numeri in un albero dei nomi, o arriva con i bordi invertiti. PDFlibPas v3.539.45 e v3.539.51 sistemano ogni caso allo stesso modo: se l'intervallo non si può leggere come coppia ordinata del tipo giusto, il figlio resta ricercabile

• /Limits mancanti: il vecchio controllo di intervallo restituiva False e il figlio veniva saltato del tutto, così un produttore che dimenticava la voce rendeva il proprio intero sottoalbero irraggiungibile. Dalla v3.539.45 il figlio viene cercato
• Tipo sbagliato o lunghezza sbagliata, come numeri in un albero dei nomi o un array a un elemento: trattato esattamente come una voce mancante dalla v3.539.45
• Bordi invertiti come [(Z) (A)] o [9 0]: la v3.539.45 li usava ancora, e nessuna chiave può soddisfare Lo <= Key <= Hi quando Lo > Hi, quindi il ramo veniva escluso per ogni ricerca. Dalla v3.539.51 un intervallo viene usato per la potatura solo quando il proprio bordo inferiore non supera il bordo superiore
• Ben formata, ordinata e corretta: usata per saltare il ramo, che è il senso stesso della voce

Le chiavi reali decidono l'esito in ogni caso. Un /Limits ostile può far visitare a PDFlibPas più nodi del necessario, ma uno malformato non può più far sparire una destinazione esistente. Dal lato del chiamante nulla cambia: GetNamedDestination restituisce 0 quando il nome è davvero assente e un ID di destinazione altrimenti, e le funzioni di destinazione prendono il volo da lì

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;
    // Prima il /Dests del catalogo (PDF 1.1), poi l'albero dei nomi /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;

Eseguito contro un file costruito a mano il cui radice /Dests ha un figlio che rimanda alla radice sotto un intervallo [(a) (z)] e un secondo figlio che tiene la voce reale sotto limiti invertiti [(z) (a)], questa procedura risolve la destinazione alla pagina 2 con tipo di vista 2 (Fit). Prima della v3.539.45 la stessa ricerca restituiva 0, perché il figlio ciclico rivendicava la chiave per primo e la ricerca non raggiungeva mai il fratello; la sola v3.539.45 restituiva ancora 0, perché l'intervallo invertito escludeva la foglia reale. Se poi leggi l'outline che punta a queste destinazioni, l'articolo compagno su leggere le azioni di segnalibri e annotazioni PDF in Delphi copre il lato azioni

Come una foglia con 32.769 nomi ha rotto TPDFNameTree?

Una foglia con 32.769 coppie nome/valore ha rotto TPDFNameTree perché la sua FindIndex interna impacchettava due numeri in un solo Integer a 32 bit: la posizione della foglia nella lista array interna nei 16 bit alti e l'offset della voce dentro l'array /Names di quella foglia nei 16 bit bassi. Ogni coppia occupa due slot dell'array, così la coppia 32.769, indice di coppia 32.768, parte all'offset 65.536, che è $10000. Quel valore riporta nei bit alti, e il decoder lo rileggeva come offset 0 nella foglia successiva

TPDFNameTree è la classe dietro allegati, pacchetti JavaScript globali e scritture di named destination, il che rende le conseguenze concrete. In un albero a foglia singola non c'è foglia successiva, così FindKey e DeleteKey indicizzavano oltre la fine della lista di foglie; in un albero a più foglie restituivano o cancellavano la prima coppia della foglia seguente invece di quella richiesta. Nel frattempo HasKey girava la propria scansione e riportava la chiave come presente, così la classe si contraddiceva. Un manuale di riferimento generato con una named destination per simbolo API supera le 32.768 voci senza sforzo, e alcuni produttori scrivono tutte in un'unica foglia piatta

Dalla v3.539.45, FindIndex restituisce l'indice di array attraverso un parametro out separato e l'offset completo della voce come risultato, così nessun valore viene troncato. La stessa release ha irrobustito due vicini. KeyName ora conta e restituisce solo chiavi stringa genuine e restituisce una stringa vuota per un indice di 0 o sotto, dove prima faceva un cast di qualsiasi oggetto seguisse una chiave non valida. HasKey non tratta più una chiave numerica o altrimenti non valida come un nome vuoto. Per una foglia come [(Valid) 42 123 456], HasKey('') ora è False e KeyName(2) restituisce una stringa vuota

procedure AuditTrees(const FileName: string);
var
  Lib: TPDFlib;
  I: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile(FileName, '') <> 1 then
      Exit;
    // Number tree /PageLabels; i file senza restituiscono numeri di pagina semplici
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // Albero dei nomi /EmbeddedFiles; indici a base 1, chiavi non stringa saltate
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // nome, tipo MIME
    // Albero dei nomi /JavaScript: elenca i nomi dei pacchetti, non esegue nulla
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

Sullo stesso file costruito a mano, il cui radice /PageLabels elenca una foglia due volte e riferisce sé stesso, questo audit stampa i e A-1 per le due pagine, ogni intervallo una volta, e l'unico pacchetto di script da un albero /JavaScript che rimanda anch'esso alla propria radice. Il lato scrittura delle etichette di pagina ha una sua storia con i radici /Kids, coperta in correggere le etichette di pagina PDF conservate in number tree /Kids; AddPageLabels appiattisce un tale radice prima di inserire, e conta sulla stessa enumerazione EnumNumTree descritta qui

Che cosa non garantisce ancora questo irrobustimento?

L'irrobustimento garantisce terminazione, ordine stabile e risultati corretti per alberi le cui chiavi reali sono intatte; non fa sì che un albero danneggiato significhi ciò che il suo autore intendeva. Diversi limiti valgono la pena conoscere prima di costruirci sopra

• L'insieme dei visitati lavora per identità di oggetto. Due dizionari distinti con contenuto identico sono due nodi, così un produttore che copia una foglia invece di riferirla produce comunque voci duplicate
• Un /Limits ben formato, ordinato ma sbagliato pota comunque. Un lettore che usa gli intervalli come ottimizzazione non può anche essere immune a un intervallo che mente in modo plausibile; l'unica alternativa è ignorare del tutto /Limits e scansionare ogni foglia
• L'enumerazione conserva l'ordine del file ma non ordina. GetPageLabel applica l'ultimo intervallo enumerato alla pagina o sotto, quindi un produttore che scrive gli intervalli fuori ordine ottiene semantica da ordine di file
• La memoria cresce con il numero di nodi e voci distinti. Il percorso aggiunge una lista e un hash set, nient'altro, ma un albero dei nomi da 100 MB resta un albero dei nomi da 100 MB anche dopo l'analisi
• Le chiavi duplicate dentro una foglia non vengono riportate. La ricerca binaria restituisce la prima coppia corrispondente che colpisce; il ripiego lineare conserva l'ultima corrispondenza che scansa

Riferimento rapido: leggere gli alberi PDF da file non fidati

• Passa alla v3.539.45 o successiva per un percorso degli alberi dei nomi e dei number tree al sicuro da cicli e stack, e alla v3.539.51 o successiva perché le /Limits invertite non nascondano più chiavi
• Tratta il 0 restituito da GetNamedDestination come "assente", e lo 0 di GetDestPage come "presente ma inutilizzabile"
• Usa GlobalJavaScriptCount e GlobalJavaScriptPackageName per l'albero dei nomi /JavaScript; GetDocJavaScript legge invece i trigger /AA del catalogo
• Indicizza allegati e pacchetti di script da 1 al conteggio che riporta la libreria; le chiavi non valide non vengono contate
• Nel tuo codice ad albero, marca i nodi visitati al pop, inserisci i figli al contrario, e lascia che /Limits poti solo quando è una coppia ben tipizzata e ordinata

I tool di pre-volo, gli archiviatori e i viewer leggono questi alberi prima che qualsiasi pagina venga renderizzata, quindi devono sopravvivere a qualunque cosa arrivi in una coda di upload. I lettori di alberi descritti sopra viaggiano con PDFlibPas, la PDF Library per Delphi, che compila sia con Delphi sia con Free Pascal