PDFlibPas Name Trees: Cycles, Bad Limits and Huge Leaves

PDFlibPas, the losLab PDF Library for Delphi, walks PDF name trees and number trees with an explicit stack and a visited set since v3.539.45, so cyclic /Kids, shared children and trees thousands of levels deep no longer exhaust the call stack or duplicate entries. Since v3.539.51 a missing, malformed or reversed /Limits pair never hides a branch that holds the key. Named destinations, page labels, attachments and document-level JavaScript all read through these two code paths, which makes them part of the attack surface of any PDF you did not produce yourself

The trigger is rarely exotic. A fuzzer, a hostile upload or a buggy incremental save writes a /Kids entry that points back at an ancestor, and a recursive walker dies with a stack overflow on a two-kilobyte file. The quieter failure is a lookup that trusts a broken /Limits array and reports "not found" for a destination that is plainly there

Where do name trees and number trees show up in a PDF?

Name trees and number trees show up wherever a PDF maps a large set of keys to objects, and PDFlibPas reads at least four of them through public APIs. ISO 32000-1 §7.9.6 defines the name tree (string keys, Table 36) and §7.9.7 the number tree (integer keys, Table 37). Both are balanced-ish trees whose root and intermediate nodes carry /Kids, whose leaves carry the sorted key/value pairs in /Names or /Nums, and whose non-root nodes carry a two-element /Limits array with the smallest and largest key below them

Tree	Where it lives	Specification	PDFlibPas read API
Named destinations	/Dests in the name dictionary	§12.3.2.3	GetNamedDestination, then GetDestPage / GetDestType
Page labels	/PageLabels in the catalog (number tree)	§12.4.2	GetPageLabel
Attachments	/EmbeddedFiles in the name dictionary	§7.7.4, §7.11.4	EmbeddedFileCount, GetEmbeddedFileStrProperty
Document-level JavaScript	/JavaScript in the name dictionary	§7.7.4	GlobalJavaScriptCount, GlobalJavaScriptPackageName

Two details in that table are easy to miss. Named destinations also have an older PDF 1.1 form, a plain /Dests dictionary in the catalog keyed by name objects, and GetNamedDestination checks that dictionary first before it descends the PDF 1.2 name tree. And GetDocJavaScript is not a name-tree reader at all: it returns the scripts attached to document triggers in the catalog /AA dictionary (WS, DS, WP, DP, DC), while the named script packages that run when a document opens live in the /JavaScript name tree

Every byte of those structures comes from the file. The specification says what a writer shall produce; it cannot stop a reader from receiving something else, which is the same lesson behind hardening a Pascal PDF parser against malicious files, applied here to tree shape rather than buffer sizes

Why does a cyclic /Kids array crash a recursive tree walker?

A cyclic /Kids array crashes a recursive walker because nothing in the recursion notices that it has seen a node before, so a child that references its own ancestor turns a finite file into an infinite descent. Before v3.539.45, NameTreeLookup, NumTreeLookup, EnumNumTree and the internal TPDFNameTree.ProcessNode all called themselves once per child. A single self-reference was enough to end the process, and a legitimate but very deep tree could do the same without any cycle at all

A milder variant corrupts results instead of crashing. When two /Kids entries reference the same leaf, a naive enumeration visits it twice, and an attachment count or a list of script packages reports entries that do not exist

The fix replaces recursion with an explicit last-in, first-out stack on the heap and a visited set keyed by dictionary identity. A node is marked when it is popped, not when it is pushed, so a cyclic reference may sit on the stack briefly but is discarded the moment it comes back up. Each distinct node expands its children exactly once, which bounds the total work by the number of distinct dictionaries plus the total length of their /Kids arrays. Depth stops mattering: a 4,096-level chain is just 4,096 iterations of a loop and 4,096 entries in a hash set

Order still matters, though, and the stack has to be fed backwards to keep it. Children are pushed from the last index down to the first, so the leftmost child is popped first and the leaves come out in the same left-to-right order the producer wrote. GetPageLabel depends on that: it walks every enumerated range and applies the last one whose start index is at or below the page, so reversing the enumeration would silently hand page 200 the front-matter style. The skeleton below shows the pattern on an abstract node type, independent of any PDF object model

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // empty on a leaf
    Keys: TArray<string>;      // leaf keys, sorted by a well-behaved producer
    Values: TArray<Integer>;   // parallel to Keys
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// /Limits is a hint: only a well-formed, ordered pair may prune a branch
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 or shared child: seen it
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // Push right-to-left so the leftmost kid is popped first
        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;
      // A miss in this leaf is not a verdict: keep popping siblings
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

Why can't a lookup stop at the first matching branch?

A lookup cannot stop at the first branch whose range matches, because /Limits ranges in a real file can overlap or lie, and the branch that claims the key is not necessarily the branch that holds it. The pre-v3.539.45 lookups set a Found flag on the first child whose /Limits covered the key, descended into it, and never looked at another sibling. If that child turned out to be empty, stale or a loop back to the root, the answer was nil, even when the very next sibling held the key

The rewritten FindTreeValue, which now backs both NameTreeLookup and NumTreeLookup, pushes every child whose range does not exclude the key and keeps popping until it finds a match or empties the stack. A miss inside one leaf is just a miss inside one leaf. In a well-formed tree this costs nothing extra; in a damaged one it costs a few more node visits and returns the right answer

Leaf search follows the same philosophy. ISO 32000-1 requires the keys in a /Names array to be sorted by byte value, so the leaf is searched with a binary search first. If that fails, PDFlibPas falls back to a linear scan of the pairs, because an out-of-order leaf would otherwise make a present key invisible. Sorting is a fast path, not a filter

The lookup also declines to guess on one structural contradiction. Table 36 lets a node carry either /Kids or /Names, never both, and the lookup path treats a node that carries both as malformed and skips it rather than picking one interpretation. Enumeration paths such as EnumNumTree are more lenient and follow /Kids when both are present

What may a reader trust /Limits for?

A reader may trust /Limits only to skip work, never to decide that a key is absent, and only when the pair is well formed. Table 36 says intermediate and leaf nodes shall carry /Limits as a two-element array of the least and greatest keys, but in practice the entry goes missing after hand edits, holds numbers in a name tree, or arrives with its bounds swapped. PDFlibPas v3.539.45 and v3.539.51 settle each case the same way: if the range cannot be read as an ordered pair of the right type, the child stays searchable

• Missing /Limits: the old range check returned False and the child was skipped outright, so a producer that forgot the entry made its whole subtree unreachable. Since v3.539.45 the child is searched
• Wrong type or wrong length, such as numbers in a name tree or a one-element array: treated exactly like a missing entry since v3.539.45
• Reversed bounds such as [(Z) (A)] or [9 0]: v3.539.45 still used them, and no key can satisfy Lo <= Key <= Hi when Lo > Hi, so the branch was excluded for every lookup. Since v3.539.51 a range is used for pruning only when its lower bound does not exceed its upper bound
• Well formed, ordered and correct: used to skip the branch, which is the whole point of the entry

The real keys decide the outcome in every case. A hostile /Limits can make PDFlibPas visit more nodes than necessary, but a malformed one can no longer make an existing destination disappear. From the caller's side nothing changes: GetNamedDestination returns 0 when the name really is absent and a destination ID otherwise, and the destination functions take it from there

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) first, then the /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;

Run against a hand-built file whose /Dests root has one child that loops back to the root under a [(a) (z)] range and a second child holding the real entry under reversed [(z) (a)] limits, this procedure resolves the destination to page 2 with view type 2 (Fit). Before v3.539.45 the same lookup returned 0, because the looping child claimed the key first and the search never reached its sibling; v3.539.45 alone still returned 0, because the reversed range excluded the real leaf. If you then read the outline that points at these destinations, the companion article on reading PDF bookmark and annotation actions in Delphi covers the action side

How did a leaf with 32,769 names break TPDFNameTree?

A leaf with 32,769 name/value pairs broke TPDFNameTree because its internal FindIndex packed two numbers into one 32-bit Integer: the leaf's position in the internal array list in the high 16 bits and the entry offset within that leaf's /Names array in the low 16 bits. Each pair occupies two array slots, so the 32,769th pair, pair index 32,768, starts at offset 65,536, which is $10000. That value carries into the high half, and the decoder read it back as offset 0 in the next leaf

TPDFNameTree is the class behind attachments, global JavaScript packages and named-destination writes, which makes the consequences concrete. In a single-leaf tree there is no next leaf, so FindKey and DeleteKey indexed past the end of the leaf list; in a multi-leaf tree they returned or deleted the first pair of the following leaf instead of the one requested. Meanwhile HasKey ran its own scan and reported the key as present, so the class contradicted itself. A generated reference manual with one named destination per API symbol crosses 32,768 entries without trying, and some producers write all of them into a single flat leaf

Since v3.539.45, FindIndex returns the array index through a separate out parameter and the full entry offset as its result, so neither value is truncated. The same release tightened two neighbours. KeyName now counts and returns only genuine string keys and returns an empty string for an index of 0 or below, where it previously cast whatever object followed an invalid key. HasKey no longer treats a numeric or otherwise invalid key as an empty name. For a leaf such as [(Valid) 42 123 456], HasKey('') is now False and KeyName(2) returns an empty string

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; files without one return plain page numbers
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // /EmbeddedFiles name tree; indexes are 1-based, non-string keys skipped
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // name, MIME type
    // /JavaScript name tree: list package names, execute nothing
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

On the same hand-built file, whose /PageLabels root lists one leaf twice and references itself, this audit prints i and A-1 for the two pages, each range once, and the single script package from a /JavaScript tree that also points back at its own root. The write side of page labels has its own history with /Kids roots, covered in fixing PDF page labels stored in /Kids number trees; AddPageLabels flattens such a root before inserting, and it relies on the same EnumNumTree enumeration described here

What does this hardening still not guarantee?

The hardening guarantees termination, stable order and correct results for trees whose real keys are intact; it does not make a damaged tree mean what its author intended. Several limits are worth knowing before you build on it

• The visited set works by object identity. Two distinct dictionaries with identical content are two nodes, so a producer that copies a leaf instead of referencing it still yields duplicate entries
• A well-formed, ordered but wrong /Limits still prunes. A reader that uses ranges as an optimisation cannot also be immune to a range that lies plausibly; the only alternative is to ignore /Limits entirely and scan every leaf
• Enumeration preserves file order but does not sort. GetPageLabel applies the last enumerated range at or below the page, so a producer that writes ranges out of order gets file-order semantics
• Memory grows with the number of distinct nodes and entries. The traversal adds a list and a hash set, nothing more, but a 100 MB name tree is still a 100 MB name tree after parsing
• Duplicate keys inside one leaf are not reported. The binary search returns whichever matching pair it hits first; the linear fallback keeps the last match it scans

Quick reference: reading PDF trees from untrusted files

• Upgrade to v3.539.45 or later for cycle-safe, stack-safe traversal of name trees and number trees, and to v3.539.51 or later so reversed /Limits no longer hide keys
• Treat GetNamedDestination returning 0 as "absent", and GetDestPage returning 0 as "present but unusable"
• Use GlobalJavaScriptCount and GlobalJavaScriptPackageName for the /JavaScript name tree; GetDocJavaScript reads catalog /AA triggers instead
• Index attachments and script packages from 1 to the count the library reports; invalid keys are not counted
• In your own tree code, mark nodes visited on pop, push children in reverse, and let /Limits prune only when it is a well-typed, ordered pair

Pre-flight tools, archivers and viewers read these trees before any page is rendered, so they have to survive whatever arrives in an upload queue. The tree readers described above ship with PDFlibPas, the PDF Library for Delphi, which builds with both Delphi and Free Pascal