PDFlibPas 名称树：环、坏 /Limits 与巨型叶节点

PDFlibPas，losLab 面向 Delphi 的 PDF 库，从 v3.539.45 起以显式栈加已访问集合遍历 PDF 名称树与数字树，于是成环的 /Kids、共享的子节点和几千层深的树不再耗尽调用栈，也不再复制出重复表项。从 v3.539.51 起，缺失、畸形或颠倒的 /Limits 对永远藏不住持有该键的分支。命名目标、页面标签、附件和文档级 JavaScript 都经由这两条代码路径读取，这让它们成为任何非你亲手产出的 PDF 攻击面的一部分

触发条件很少花哨。fuzzer、恶意上传或一个有毛病的增量保存，写出一个指回祖先的 /Kids 表项，递归遍历器就在一个两 KB 的文件上死于栈溢出。更安静的失败是查找信任了坏掉的 /Limits 数组，对一个明明存在的目标报告“找不到”

名称树与数字树在 PDF 里出现在哪里？

PDF 需要把一大组键映射到对象的地方，就有名称树和数字树，PDFlibPas 至少有四个经由公开 API 读取。ISO 32000-1 §7.9.6 定义名称树（字符串键，Table 36），§7.9.7 定义数字树（整数键，Table 37）。两者都是近似平衡的树：根与中间节点带 /Kids，叶子把排好序的键值对放在 /Names 或 /Nums 里，非根节点带一个两元素的 /Limits 数组，记录其下最小与最大的键

树	位置	规范章节	PDFlibPas 读取 API
命名目标	名称字典里的 /Dests	§12.3.2.3	GetNamedDestination，随后 GetDestPage / GetDestType
页面标签	目录里的 /PageLabels（数字树）	§12.4.2	GetPageLabel
附件	名称字典里的 /EmbeddedFiles	§7.7.4, §7.11.4	EmbeddedFileCount、GetEmbeddedFileStrProperty
文档级 JavaScript	名称字典里的 /JavaScript	§7.7.4	GlobalJavaScriptCount、GlobalJavaScriptPackageName

表里有两个细节容易漏看。命名目标还有一个更老的 PDF 1.1 形式——目录里一个以名称对象为键的普通 /Dests 字典——GetNamedDestination 会先查这个字典，然后才下到 PDF 1.2 的名称树。而 GetDocJavaScript 根本不是名称树读取器：它返回目录 /AA 字典里挂在文档触发器上的脚本（WS、DS、WP、DP、DC），文档打开时运行的命名脚本包则住在 /JavaScript 名称树里

这些结构的每个字节都来自文件。规范说的是写入者应当产出什么，却拦不住读取者收到别的东西——加固 Pascal PDF 解析器以抵御恶意文件讲的正是同一个道理，这里用在树的形状而非缓冲区大小上

成环的 /Kids 数组为什么会让递归树遍历器崩溃？

成环的 /Kids 数组会让递归遍历器崩溃，因为递归里没有任何东西注意到「这个节点见过」，于是子节点引用自己的祖先，把有限文件变成无限下潜。v3.539.45 之前，NameTreeLookup、NumTreeLookup、EnumNumTree 和内部的 TPDFNameTree.ProcessNode 都对每个子节点递归调用自己。一个自引用就足以终结进程，一条合法但极深的树不用成环也能做到同样的事

温和些的变体不崩溃，但弄脏结果。两个 /Kids 表项引用同一片叶子时，朴素的枚举会访问它两次，附件计数或脚本包列表便报出不存在的表项

修复用堆上的显式后进先出栈加一个按字典同一性为键的已访问集合取代递归。节点在弹出时标记，而不是压入时，所以环引用可能在栈上短暂停留，但一冒头就被丢弃。每个去重后的节点恰好展开一次子节点，总工作量以不同字典的数目加上它们 /Kids 数组的总长度为界。深度不再是要紧事：4,096 层的链不过是循环的 4,096 次迭代加哈希集合里的 4,096 个表项

不过顺序仍然要紧，栈必须反着喂才能保住它。子节点从最后一个索引压到第一个，于是最左边的子节点先弹出，叶子按写入者写的从左到右顺序出来。GetPageLabel 依赖这一点：它遍历每个枚举出的区间，应用起始索引不大于页码的最后一个，所以把枚举反过来，第 200 页就会无声地拿到前置内容的样式。下面的骨架代码在一个抽象节点类型上演示这个模式，不依赖任何 PDF 对象模型

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // 叶子上为空
    Keys: TArray<string>;      // 叶子键，按规矩的写入者会排好序
    Values: TArray<Integer>;   // 与 Keys 平行
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// /Limits 只是个提示：只有良构、有序的对才有资格剪枝
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;                      // 环或共享子节点：见过了
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // 从右向左压入，最左边的子节点先弹出
        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;
      // 这片叶子里没找到不算结论：继续弹兄弟节点
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

查找为什么不能在第一个匹配的分支上停手？

查找不能在第一个范围匹配的分支上停手，因为真实文件里的 /Limits 范围可能重叠、可能撒谎，声称拥有该键的分支未必是真正持有它的分支。v3.539.45 之前的查找在第一个 /Limits 覆盖该键的子节点上设置 Found 标志，下钻进去，然后不再看任何兄弟。如果那个子节点结果是空的、过期的或绕回根节点的环，答案就是 nil，哪怕紧挨着的下一个兄弟正握着这个键

重写的 FindTreeValue——现在同时支撑 NameTreeLookup 和 NumTreeLookup——把范围不排除该键的每个子节点都压栈，持续弹出直到命中或栈空。一片叶子里的未命中只是那片叶子里的未命中。良构的树上这不多花一分钱；损坏的树上多访问几个节点，换来正确答案

叶子内查找遵循同一哲学。ISO 32000-1 要求 /Names 数组里的键按字节值排序，所以先用二分查找搜叶子。失败则回退到对键值对的线性扫描，否则乱序的叶子会让实际存在的键隐身。排序是快速路径，不是过滤器

查找在一处结构矛盾上也拒绝猜测。Table 36 允许节点带 /Kids 或 /Names，绝不同时带两者；查找路径把两者都带的节点当畸形处理，直接跳过而不挑一种解释。枚举路径如 EnumNumTree 更宽容，两者都在时跟 /Kids 走

读取者可以拿 /Limits 信什么？

读取者只能在「跳过工作量」上信 /Limits，绝不能拿它判定键不存在，而且仅当那对值良构时才行。Table 36 说中间与叶节点应当携带由最小、最大键组成的两元素 /Limits 数组，但实际上这个表项会在手工编辑后丢失，会在名称树里装着数字，或者上下界颠倒着送来。PDFlibPas v3.539.45 与 v3.539.51 对每种情形的处理一致：范围读不成正确类型的有序对，子节点就保持可搜索

• 缺失 /Limits：旧的范围检查返回 False，子节点被整个跳过，忘了写这个表项的写入者就此让自己的整棵子树不可达。从 v3.539.45 起会搜索该子节点
• 类型错或长度错，比如名称树里装数字、或只有一个元素的数组：从 v3.539.45 起按缺失表项处理
• 上下界颠倒，如 [(Z) (A)] 或 [9 0]：v3.539.45 仍在使用它们，而 Lo > Hi 时没有键能满足 Lo <= Key <= Hi，于是该分支对每次查找都被排除。从 v3.539.51 起，只有下界不超过上界的范围才用于剪枝
• 良构、有序且正确：用于跳过分支——这正是这个表项存在的全部意义

每种情形下，决定结果的都是真实键。敌意的 /Limits 能让 PDFlibPas 多访问一些节点，但畸形的 /Limits 再也无法让一个存在的目标消失。调用侧什么都没变：GetNamedDestination 在名字确实不存在时返回 0，否则返回目标 ID，剩下的交给各目标函数

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;
    // 先查目录 /Dests（PDF 1.1），再查 /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;

拿手工构造的文件跑一遍——它的 /Dests 根有一个在 [(a) (z)] 范围下绕回根节点的子节点，还有第二个子节点在颠倒的 [(z) (a)] 范围下握着真实表项——这个过程会把目标解析到第 2 页、视图类型 2（Fit）。v3.539.45 之前同样的查找返回 0，因为绕环的子节点先声称该键归它，搜索永远到不了它的兄弟；单有 v3.539.45 仍返回 0，因为颠倒的范围把真实叶子排除了。如果你接着要读指向这些目标的书签，在 Delphi 里读取 PDF 书签与注解动作那篇姊妹文章覆盖动作这一侧

32,769 个名称的叶子是怎么搞坏 TPDFNameTree 的？

32,769 对名称/值的叶子搞坏了 TPDFNameTree，因为它内部的 FindIndex 把两个数塞进一个 32 位 Integer：高 16 位是叶子在内部数组列表里的位置，低 16 位是该叶子 /Names 数组内的表项偏移。每对占两个数组槽，于是第 32,769 对——对索引 32,768——从偏移 65,536 也就是 $10000 开始。这个值进位到高半段，解码回来就成了下一片叶子的偏移 0

TPDFNameTree 是附件、全局 JavaScript 包和命名目标写入背后的类，后果因此很具体。单叶子树没有「下一片叶子」，FindKey 和 DeleteKey 便索引到叶子列表末尾之外；多叶子树里它们返回或删除的是下一片叶子的第一对，而不是请求的那对。与此同时 HasKey 跑自己的扫描，报告键存在——类跟自己打起架来。一份每个 API 符号一个命名目标的生成版参考手册，轻轻松松越过 32,768 个表项，而且有些写入者把它们全塞进一个扁平叶子

从 v3.539.45 起，FindIndex 经独立的 out 参数返回数组索引，以函数结果返回完整表项偏移，两个值都不再截断。同一版本还收紧了两个邻居。KeyName 现在只统计并返回真正的字符串键，索引为 0 或更小时返回空字符串——此前它会把无效键后面跟的任何对象强转过来。HasKey 不再把数字或其他非法键当空名称。对形如 [(Valid) 42 123 456] 的叶子，HasKey('') 现在是 False，KeyName(2) 返回空字符串

procedure AuditTrees(const FileName: string);
var
  Lib: TPDFlib;
  I: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile(FileName, '') <> 1 then
      Exit;
    // /PageLabels 数字树；没有它的文件返回普通页码
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // /EmbeddedFiles 名称树；索引从 1 起，非字符串键跳过
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // 名称、MIME 类型
    // /JavaScript 名称树：列出包名，不执行任何东西
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

在同一个手工构造的文件上——它的 /PageLabels 根把一片叶子列了两次并引用自身——这份审计为两页各打印一次 i 和 A-1，每个区间一次，外加来自同样指回自身根节点的 /JavaScript 树的那个脚本包。页面标签的写入侧与 /Kids 根还有一段旧账，见 修复存进 /Kids 数字树的 PDF 页面标签；AddPageLabels 插入前会先把这样的根拍平，靠的正是这里描述的同一套 EnumNumTree 枚举

这些加固仍然不保证什么？

这轮加固保证终止、顺序稳定，以及在真实键完好的树上的正确结果；它不能让一棵损坏的树表达作者本意。在它之上构建之前，有几条边界值得知道

• 已访问集合按对象同一性工作。内容完全相同的两个不同字典是两个节点，所以复制而非引用叶子的写入者照样产出重复表项
• 良构、有序但撒谎的 /Limits 照样剪枝。把范围当优化的读取者，不可能同时对一个看起来可信的假范围免疫；唯一的替代是完全无视 /Limits，扫描每片叶子
• 枚举保持文件顺序但不排序。GetPageLabel 应用起始索引不大于页码的最后一个枚举区间，乱序写区间的写入者得到的就是文件序语义
• 内存随不同节点与表项的数量增长。遍历只多出一个列表和一个哈希集合，别无其他，但解析之后 100 MB 的名称树仍是 100 MB 的名称树
• 一片叶子内部的重复键不会被报告。二分查找返回它先碰到的那个匹配对；线性回退保留它扫到的最后一个匹配

速查：从不可信文件读取 PDF 树

• 升级到 v3.539.45 或更高，获得环安全、栈安全的名称树与数字树遍历；升级到 v3.539.51 或更高，颠倒的 /Limits 不再藏键
• 把 GetNamedDestination 返回 0 当作“不存在”，把 GetDestPage 返回 0 当作“存在但不可用”
• /JavaScript 名称树用 GlobalJavaScriptCount 和 GlobalJavaScriptPackageName；GetDocJavaScript 读的是目录 /AA 触发器
• 附件与脚本包的索引从 1 数到库报告的数量；非法键不计入
• 在你自己的树代码里，弹出时标记已访问、反向压入子节点、/Limits 只在它是类型正确且有序的对时才用于剪枝

预检工具、归档器和阅读器在任何页面渲染之前就要读这些树，所以它们必须经得住上传队列里来的任何东西。上文描述的树读取器随 PDFlibPas（PDF Library for Delphi）发布，Delphi 与 Free Pascal 均可构建