Name trees en PDFlibPas: ciclos y Limits que esconden claves

PDFlibPas, la PDF Library de losLab para Delphi, recorre los name trees y number trees de PDF con un stack explícito y un conjunto de visitados desde v3.539.45, así que unos /Kids cíclicos, hijos compartidos y árboles de miles de niveles de profundidad ya no agotan el call stack ni duplican entradas. Desde v3.539.51 un par /Limits ausente, mal formado o invertido jamás esconde una rama que contiene la clave. Los named destinations, los page labels, los attachments y el JavaScript a nivel de documento todos leen por estos dos caminos de código, lo que los vuelve parte de la superficie de ataque de cualquier PDF que usted no haya producido

El disparador rara vez es exótico. Un fuzzer, una subida hostil o un incremental save con bug escribe una entrada /Kids que apunta de vuelta a un ancestro, y un walker recursivo muere con stack overflow en un archivo de dos kilobytes. La falla más silenciosa es una búsqueda que confía en un array /Limits roto y reporta "no encontrado" para un destination que está claramente ahí

¿Dónde aparecen los name trees y number trees en un PDF?

Los name trees y number trees aparecen dondequiera que un PDF mapea un conjunto grande de claves a objetos, y PDFlibPas lee al menos cuatro de ellos por APIs públicas. ISO 32000-1 §7.9.6 define el name tree (claves string, Table 36) y §7.9.7 el number tree (claves enteras, Table 37). Ambos son árboles más o menos balanceados cuyo nodo raíz y nodos intermedios llevan /Kids, cuyas hojas llevan los pares clave/valor ordenados en /Names o /Nums, y cuyos nodos no raíz llevan un array /Limits de dos elementos con la menor y la mayor clave por debajo de ellos

Árbol	Dónde vive	Especificación	API de lectura de PDFlibPas
Named destinations	/Dests en el diccionario de nombres	§12.3.2.3	GetNamedDestination, luego GetDestPage / GetDestType
Page labels	/PageLabels en el catálogo (number tree)	§12.4.2	GetPageLabel
Attachments	/EmbeddedFiles en el diccionario de nombres	§7.7.4, §7.11.4	EmbeddedFileCount, GetEmbeddedFileStrProperty
JavaScript de documento	/JavaScript en el diccionario de nombres	§7.7.4	GlobalJavaScriptCount, GlobalJavaScriptPackageName

Dos detalles de esa tabla son fáciles de perder. Los named destinations también tienen una forma más vieja de PDF 1.1, un diccionario /Dests plano en el catálogo con claves de tipo name, y GetNamedDestination chequea ese diccionario primero antes de descender al name tree de PDF 1.2. Y GetDocJavaScript no es un lector de name trees para nada: devuelve los scripts adjuntos a los triggers de documento en el diccionario /AA del catálogo (WS, DS, WP, DP, DC), mientras que los paquetes de scripts nombrados que corren al abrir un documento viven en el name tree /JavaScript

Cada byte de esas estructuras viene del archivo. La especificación dice lo que un writer debe producir; no puede impedir que un reader reciba otra cosa, que es la misma lección detrás de endurecer un parser PDF en Pascal contra archivos maliciosos, aplicada aquí a la forma del árbol en vez de a los tamaños de buffer

¿Por qué un array /Kids cíclico tumba a un walker de árbol recursivo?

Un array /Kids cíclico tumba a un walker recursivo porque nada en la recursión se da cuenta de que ya vio un nodo, así que un hijo que referencia a su propio ancestro convierte un archivo finito en un descenso infinito. Antes de v3.539.45, NameTreeLookup, NumTreeLookup, EnumNumTree y el TPDFNameTree.ProcessNode interno se llamaban a sí mismos una vez por hijo. Una sola autorreferencia bastaba para terminar el proceso, y un árbol legítimo pero muy profundo podía lograr lo mismo sin ciclo alguno

Una variante más leve corrompe resultados en vez de colgarse. Cuando dos entradas /Kids referencian la misma hoja, una enumeración ingenua la visita dos veces, y un conteo de attachments o una lista de paquetes de scripts reporta entradas que no existen

La corrección reemplaza la recursión con un stack explícito last-in, first-out en el heap y un conjunto de visitados con clave de identidad de diccionario. Un nodo se marca cuando se saca del stack, no cuando se mete, así que una referencia cíclica puede sentarse en el stack un momento pero se descarta en cuanto vuelve a subir. Cada nodo distinto expande a sus hijos exactamente una vez, lo que acota el trabajo total por el número de diccionarios distintos más el largo total de sus arrays /Kids. La profundidad deja de importar: una cadena de 4,096 niveles son solo 4,096 iteraciones de un loop y 4,096 entradas en un hash set

El orden todavía importa, eso sí, y al stack hay que alimentarlo al revés para conservarlo. Los hijos se empujan desde el último índice hasta el primero, así que el hijo más a la izquierda se saca primero y las hojas salen en el mismo orden de izquierda a derecha en que las escribió el productor. GetPageLabel depende de eso: recorre cada rango enumerado y aplica el último cuyo índice de arranque esté en o bajo la página, así que invertir la enumeración le entregaría en silencio a la página 200 el estilo del front matter. El esqueleto de abajo muestra el patrón sobre un tipo de nodo abstracto, independiente de cualquier modelo de objetos PDF

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // vacío en una hoja
    Keys: TArray<string>;      // claves de hoja, ordenadas por un productor que se porta bien
    Values: TArray<Integer>;   // paralelo a Keys
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// /Limits es una pista: solo un par bien formado y ordenado puede podar una rama
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 hijo compartido: ya lo vimos
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // Empuje de derecha a izquierda así el kid más a la izquierda sale primero
        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 miss en esta hoja no es un veredicto: siga sacando hermanos
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

¿Por qué una búsqueda no puede detenerse en la primera rama que coincide?

Una búsqueda no puede detenerse en la primera rama cuyo rango coincide, porque los rangos /Limits en un archivo real pueden solaparse o mentir, y la rama que reclama la clave no es necesariamente la que la contiene. Las búsquedas anteriores a v3.539.45 ponían un flag Found en el primer hijo cuyo /Limits cubría la clave, descendían en él, y nunca miraban otro hermano. Si ese hijo resultaba vacío, obsoleto o era un loop de vuelta al root, la respuesta era nil, incluso cuando el hermano siguiente justo contenía la clave

El FindTreeValue reescrito, que ahora respalda tanto a NameTreeLookup como a NumTreeLookup, empuja cada hijo cuyo rango no excluye la clave y sigue sacando nodos hasta encontrar una coincidencia o vaciar el stack. Un miss dentro de una hoja es solo un miss dentro de una hoja. En un árbol bien formado esto no cuesta nada extra; en uno dañado cuesta unas visitas de nodos más y devuelve la respuesta correcta

La búsqueda en la hoja sigue la misma filosofía. ISO 32000-1 exige que las claves de un array /Names estén ordenadas por valor de byte, así que la hoja se busca primero con búsqueda binaria. Si eso falla, PDFlibPas recurre a un barrido lineal de los pares, porque una hoja desordenada haría invisible una clave presente. Ordenar es un fast path, no un filtro

La búsqueda además se niega a adivinar ante una contradicción estructural. La Table 36 permite que un nodo lleve /Kids o /Names, nunca ambos, y el camino de búsqueda trata un nodo que lleva ambos como mal formado y lo salta en vez de elegir una interpretación. Los caminos de enumeración como EnumNumTree son más tolerantes y siguen /Kids cuando ambos están presentes

¿En qué puede confiar un reader respecto de /Limits?

Un reader puede confiar en /Limits solo para saltarse trabajo, jamás para decidir que una clave está ausente, y solo cuando el par está bien formado. La Table 36 dice que los nodos intermedios y las hojas deben llevar /Limits como un array de dos elementos con la menor y la mayor clave, pero en la práctica la entrada desaparece tras ediciones a mano, contiene números en un name tree, o llega con sus límites invertidos. PDFlibPas v3.539.45 y v3.539.51 resuelven cada caso igual: si el rango no se puede leer como un par ordenado del tipo correcto, el hijo sigue siendo buscable

• /Limits ausente: el viejo chequeo de rango devolvía False y el hijo se saltaba de plano, así que un productor que olvidó la entrada dejaba todo su subtree inalcanzable. Desde v3.539.45 el hijo se busca
• Tipo equivocado o largo equivocado, como números en un name tree o un array de un elemento: tratado exactamente como una entrada ausente desde v3.539.45
• Límites invertidos como [(Z) (A)] o [9 0]: v3.539.45 todavía los usaba, y ninguna clave puede satisfacer Lo <= Key <= Hi cuando Lo > Hi, así que la rama quedaba excluida para toda búsqueda. Desde v3.539.51 un rango se usa para podar solo cuando su cota inferior no supera su cota superior
• Bien formado, ordenado y correcto: se usa para saltarse la rama, que es todo el punto de la entrada

Las claves reales deciden el desenlace en todos los casos. Un /Limits hostil puede hacer que PDFlibPas visite más nodos de los necesarios, pero uno mal formado ya no puede hacer desaparecer un destination existente. Desde el lado de quien llama nada cambia: GetNamedDestination devuelve 0 cuando el nombre de verdad está ausente y un ID de destination en caso contrario, y las funciones de destination toman el relevo desde ahí

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;
    // Primero el /Dests del catálogo (PDF 1.1), luego el name tree /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;

Corrido contra un archivo armado a mano cuyo root /Dests tiene un hijo que hace loop de vuelta al root bajo un rango [(a) (z)] y un segundo hijo que contiene la entrada real bajo límites invertidos [(z) (a)], este procedimiento resuelve el destination a la página 2 con view type 2 (Fit). Antes de v3.539.45 la misma búsqueda devolvía 0, porque el hijo en loop reclamaba la clave primero y la búsqueda nunca llegaba a su hermano; v3.539.45 solo seguía devolviendo 0, porque el rango invertido excluía la hoja real. Si después lee el outline que apunta a estos destinations, el artículo compañero sobre leer acciones de bookmarks y anotaciones PDF en Delphi cubre el lado de las acciones

¿Cómo una hoja con 32,769 nombres rompió a TPDFNameTree?

Una hoja con 32,769 pares nombre/valor rompió TPDFNameTree porque su FindIndex interno empacaba dos números en un solo Integer de 32 bits: la posición de la hoja en la lista interna de arrays en los 16 bits altos, y el offset de la entrada dentro del array /Names de esa hoja en los 16 bits bajos. Cada par ocupa dos slots del array, así que el par 32,769, el de índice 32,768, arranca en el offset 65,536, que es $10000. Ese valor se arrastra a la mitad alta, y el decoder lo leía de vuelta como offset 0 en la hoja siguiente

TPDFNameTree es la clase detrás de los attachments, los paquetes globales de JavaScript y las escrituras de named destinations, lo que vuelve las consecuencias concretas. En un árbol de una sola hoja no hay hoja siguiente, así que FindKey y DeleteKey indexaban más allá del final de la lista de hojas; en un árbol de varias hojas devolvían o borraban el primer par de la hoja siguiente en vez del pedido. Mientras tanto HasKey corría su propio barrido y reportaba la clave como presente, así que la clase se contradecía a sí misma. Un manual de referencia generado con un named destination por símbolo de API cruza las 32,768 entradas sin esforzarse, y algunos productores escriben todas en una sola hoja plana

Desde v3.539.45, FindIndex devuelve el índice del array por un parámetro out separado y el offset completo de la entrada como resultado, así que ningún valor se trunca. La misma versión apretó dos vecinos. KeyName ahora cuenta y devuelve solo claves string genuinas y devuelve un string vacío para un índice de 0 o menos, donde antes casteaba el objeto que fuera que siguiera a una clave inválida. HasKey ya no trata una clave numérica o inválida como un nombre vacío. Para una hoja como [(Valid) 42 123 456], HasKey('') ahora es False y KeyName(2) devuelve un string vacío

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; los archivos sin uno devuelven números de página simples
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // Name tree /EmbeddedFiles; los índices son 1-based, las claves no string se saltan
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // nombre, tipo MIME
    // Name tree /JavaScript: liste nombres de paquetes, no ejecute nada
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

Sobre el mismo archivo armado a mano, cuyo root /PageLabels lista una hoja dos veces y se referencia a sí mismo, esta auditoría imprime i y A-1 para las dos páginas, cada rango una vez, y el único paquete de scripts de un árbol /JavaScript que también apunta de vuelta a su propio root. El lado de escritura de los page labels tiene su propia historia con roots /Kids, cubierta en corregir los page labels PDF guardados en number trees /Kids; AddPageLabels aplana ese root antes de insertar, y depende de la misma enumeración EnumNumTree descrita aquí

¿Qué no garantiza todavía este hardening?

El hardening garantiza terminación, orden estable y resultados correctos para árboles cuyas claves reales están intactas; no hace que un árbol dañado signifique lo que su autor pretendía. Varios límites conviene conocer antes de construir sobre él

• El conjunto de visitados funciona por identidad de objeto. Dos diccionarios distintos con contenido idéntico son dos nodos, así que un productor que copia una hoja en vez de referenciarla igual produce entradas duplicadas
• Un /Limits bien formado, ordenado pero equivocado sigue podando. Un reader que usa rangos como optimización no puede también ser inmune a un rango que miente de forma plausible; la única alternativa es ignorar /Limits por completo y barrer cada hoja
• La enumeración preserva el orden del archivo pero no ordena. GetPageLabel aplica el último rango enumerado en o bajo la página, así que un productor que escribe rangos desordenados obtiene semántica de orden de archivo
• La memoria crece con el número de nodos y entradas distintos. El recorrido agrega una lista y un hash set, nada más, pero un name tree de 100 MB sigue siendo un name tree de 100 MB después del parseo
• Las claves duplicadas dentro de una hoja no se reportan. La búsqueda binaria devuelve el primer par coincidente que pisa; el fallback lineal conserva la última coincidencia que barre

Referencia rápida: leer árboles PDF de archivos no confiables

• Actualice a v3.539.45 o posterior para un recorrido de name trees y number trees seguro ante ciclos y ante el stack, y a v3.539.51 o posterior para que los /Limits invertidos ya no escondan claves
• Trate un GetNamedDestination que devuelve 0 como "ausente", y un GetDestPage que devuelve 0 como "presente pero inutilizable"
• Use GlobalJavaScriptCount y GlobalJavaScriptPackageName para el name tree /JavaScript; GetDocJavaScript lee en cambio los triggers /AA del catálogo
• Indexe attachments y paquetes de scripts de 1 al conteo que reporta la librería; las claves inválidas no se cuentan
• En su propio código de árboles, marque nodos visitados al sacarlos, empuje los hijos en reversa, y deje que /Limits pode solo cuando es un par bien tipado y ordenado

Las herramientas de pre-vuelo, los archivadores y los visores leen estos árboles antes de que cualquier página se renderice, así que tienen que sobrevivir a lo que sea que llegue en una cola de subidas. Los lectores de árboles descritos arriba vienen con PDFlibPas, la PDF Library para Delphi, que compila tanto con Delphi como con Free Pascal