PDFlibPasネームツリー：サイクル、不正なLimits、巨大なリーフ

Delphi向けのlosLab PDF LibraryであるPDFlibPasは、v3.539.45以降、明示的スタックと訪問済みセットでPDFのネームツリーとナンバーツリーを歩きます。だから循環する/Kids、共有された子、数千レベルの深さの木が、コールスタックを使い果たしたりエントリーを複製したりすることはもうありません。v3.539.51以降、欠落、不正形式、逆転した/Limitsペアが、鍵を保持する枝を隠すことは決してありません。名前付き宛先、ページラベル、添付ファイル、ドキュメントレベルJavaScriptは、すべてこの2つのコード経路を通って読まれます。つまり、自分で作っていないPDFの攻撃面の一部だということです

引き金はほとんどが珍しいものではありません。ファザー、敵対的なアップロード、バグったインクリメンタル保存が、祖先を指し戻す/Kidsエントリーを書き込み、再帰ウォーカーは2キロバイトのファイルでスタックオーバーフロー死します。もっと静かな失敗は、壊れた/Limits配列を信じたルックアップが、明らかに存在する宛先に"not found"を報告する方です

PDFのどこにネームツリーとナンバーツリーが現れるか

PDFが大量の鍵をオブジェクトへマップする場所であればどこでも、ネームツリーとナンバーツリーは現れます。そしてPDFlibPasは、そのうち少なくとも4つを公開APIで読みます。ISO 32000-1 §7.9.6がネームツリー（文字列キー、Table 36）を、§7.9.7がナンバーツリー（整数キー、Table 37）を定義します。どちらも準バランス木で、ルートと中間ノードは/Kidsを運び、リーフはソート済みのキー／値ペアを/Namesか/Numsで運び、非ルートノードは、配下の最小キーと最大キーを入れた2要素の/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

この表には見落としやすい細部が2つあります。名前付き宛先には古いPDF 1.1形式もあり、こちらはカタログ内の素の/Dests辞書で、名前オブジェクトが鍵になります。GetNamedDestinationはPDF 1.2ネームツリーを降りる前に、まずこの辞書を確認します。そしてGetDocJavaScriptはネームツリーの読み手ではまったくありません。カタログの/AA辞書（WS、DS、WP、DP、DC）にあるドキュメントトリガーに付いたスクリプトを返すもので、ドキュメントが開くときに走る名前付きスクリプトパッケージは、/JavaScriptネームツリーに住んでいます

これらの構造の1バイト1バイトがファイルから来ます。仕様はライターが生むべきものを言うだけで、リーダーが別のものを受け取るのを止められません。Pascal PDFパーサーを悪意あるファイルに対して堅牢化する記事の教訓と同じで、ここでは木の形状に適用したまでです。バッファサイズではなく

循環する/Kids配列がなぜ再帰ツリーウォーカーをクラッシュさせるのか

循環する/Kids配列が再帰ウォーカーをクラッシュさせるのは、再帰のどこにも「このノードは前に見た」と気づく仕組みがないからです。自分の祖先を参照する子が、有限のファイルを無限下降に変えます。v3.539.45より前は、NameTreeLookup、NumTreeLookup、EnumNumTree、内部のTPDFNameTree.ProcessNodeが、子ごとに自分を呼んでいました。自己参照1つでプロセスを終わらせるのに十分で、合法的ではあっても非常に深い木も、サイクルなしで同じことをし得ました

もっと穏やかな変種は、クラッシュの代わりに結果を汚します。2つの/Kidsエントリーが同じリーフを参照していると、素朴な列挙はそれを2回訪れ、添付ファイルのカウントやスクリプトパッケージのリストが、存在しないエントリーを報告します

修正は、再帰をヒープ上の明示的なLIFOスタックと、辞書の同一性を鍵とする訪問済みセットで置き換えます。ノードに印が付くのはプッシュされたときではなくポップされたときなので、循環参照は一瞬スタックに座っていても、戻ってきた瞬間に捨てられます。個々の異なるノードは子をちょうど1回展開するので、総仕事量は、異なる辞書の数にそれらの/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配列のキーがバイト値順にソートされていることを要求するので、リーフはまず二分探索で検索されます。失敗したら、PDFlibPasはペアの線形走査へフォールバックします。順序が乱れたリーフでは、存在する鍵が見えなくなってしまうからです。ソートは高速経路であって、フィルターではありません

ルックアップは、ある構造的矛盾について推測を拒みもします。Table 36はノードに/Kidsか/Namesのどちらか一方を許し、両方は許しません。ルックアップ経路は両方を運ぶノードを不正形式として扱い、どちらかの解釈を選ぶ代わりにスキップします。EnumNumTreeのような列挙経路はもっと寛容で、両方あるときは/Kidsに従います

リーダーが/Limitsを信じていいこととは

リーダーが/Limitsを信じていいのは、仕事を省くためだけで、鍵が存在しないと決めるためでは決してなく、しかもペアが整形式のときに限ります。Table 36は、中間ノードとリーフノードが最小キーと最大キーの2要素配列として/Limitsを運ぶべきだと述べます。しかし実地では、手編集の後にエントリーが消えたり、ネームツリーに数字が入ったり、境界が入れ替わったまま届いたりします。PDFlibPas v3.539.45とv3.539.51は、各ケースを同じやり方で決着させます。範囲を正しい型の順序付きペアとして読めないなら、子は探索可能なまま

• 欠落する/Limits：旧範囲チェックはFalseを返し、子は丸ごとスキップされていました。エントリーを忘れたプロデューサーは、サブツリー全体を到達不能にしていたのです。v3.539.45以降、子は探索されます
• 型違いや長さ違い。ネームツリーに入った数字や1要素配列など：v3.539.45以降、欠落エントリーとまったく同じに扱われます
• 逆転した境界。[(Z) (A)]や[9 0]など：v3.539.45はまだそれを使っていました。Lo > HiのときLo <= Key <= Hiを満たす鍵は存在しないので、枝はすべてのルックアップで排除されていました。v3.539.51以降、範囲が枝刈りに使われるのは、下限が上限を超えないときだけです
• 整形式、順序付き、そして正しい：枝をスキップするために使われます。エントリーの存在意義はまさにそこにあります

実際のキーが、あらゆるケースで結果を決めます。敵対的な/LimitsはPDFlibPasに必要以上のノードを訪れさせられますが、不正形式のものが既存の宛先を消すことはもうできません。呼び出し側からは何も変わりません。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)]範囲のもとでルートへループする子を1つと、逆転した[(z) (a)]リミッツのもとで実エントリーを保持する2つ目の子を持つ手組みファイルに対して実行すると、この手順は宛先をページ2、ビュータイプ2（Fit）へ解決します。v3.539.45より前は、同じルックアップが0を返していました。ループする子が先に鍵を主張し、検索が兄弟に届かなかったからです。v3.539.45単独でもまだ0でした。逆転した範囲が実リーフを排除していたからです。これらの宛先を指すアウトラインも読むなら、DelphiでPDFブックマークとアノテーションアクションを読むの姉妹記事がアクション側を扱います

32,769個の名前を持つリーフがTPDFNameTreeをどう壊したか

32,769個の名前／値ペアを持つリーフがTPDFNameTreeを壊したのは、内部のFindIndexが2つの数を1つの32ビットIntegerに詰めていたからです。上位16ビットに内部配列リストでのリーフ位置、下位16ビットにそのリーフの/Names配列内でのエントリーオフセット。各ペアは配列スロットを2つ占めるので、32,769番目のペア、ペアインデックス32,768は、オフセット65,536、つまり$10000から始まります。この値が上位半分へ桁上がりし、デコーダーはそれを次のリーフのオフセット0として読み戻しました

TPDFNameTreeは添付ファイル、グローバルJavaScriptパッケージ、名前付き宛先の書き込みを支えるクラスです。影響は具体的です。単一リーフの木では次のリーフが存在しないので、FindKeyとDeleteKeyはリーフリストの末尾の先をインデックスしました。複数リーフの木では、要求されたペアではなく、次のリーフの最初のペアを返したり削除したりしました。その一方でHasKeyは自分の走査を回して鍵は存在すると報告し、クラスが自己矛盾しました。APIシンボルごとに名前付き宛先を1つ持つ生成リファレンスマニュアルなら、努力せずとも32,768エントリーを越えますし、それをすべて単一のフラットなリーフへ書くプロデューサーもあります

v3.539.45以降、FindIndexは配列インデックスを別のoutパラメーターで返し、完全なエントリーオフセットを結果として返すので、どちらの値も切り詰められません。同じリリースで隣の2つも引き締まりました。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ルートがあるリーフを2回列挙し自分自身を参照するもの——に対して、この監査は2ページのためにiとA-1を、各範囲1回ずつ印字し、やはり自分のルートを指し戻す/JavaScriptツリーからは単一のスクリプトパッケージを印字します。ページラベルの書き込み側には、/Kidsルートをめぐる独自の歴史があり、/Kidsナンバーツリーに格納されたPDFページラベルの修正で扱っています。AddPageLabelsは挿入前にその種のルートを平坦化し、ここで述べたのと同じEnumNumTree列挙に依存しています

この堅牢化がそれでも保証しないもの

この堅牢化が保証するのは、実際のキーが無事な木に対する終了性、安定した順序、正しい結果です。壊れた木を、作者が意図した意味にすることはありません。その上に構築する前に、いくつかの限界を知っておく価値があります

• 訪問済みセットはオブジェクトの同一性で働きます。内容が同一の2つの別辞書は2ノードです。リーフを参照せずコピーするプロデューサーは、重複エントリーを作り続けます
• 整形式で順序付きだが間違った/Limitsは、依然として枝を刈ります。範囲を最適化として使うリーダーは、それらしく嘘をつく範囲への免疫も持てません。唯一の代替は、/Limitsを完全に無視して全リーフを走査することです
• 列挙はファイル順を保ちますが、ソートはしません。GetPageLabelはページ以下の最後に列挙された範囲を適用するので、範囲を順序無視で書くプロデューサーは、ファイル順のセマンティクスを受け取ります
• メモリは異なるノードとエントリーの数とともに増えます。走査が追加するのはリストとハッシュセット、それだけですが、100 MBのネームツリーはパース後も100 MBのネームツリーです
• 1つのリーフ内の重複キーは報告されません。二分探索は最初に当たったマッチペアをどれでも返し、線形フォールバックは走査した最後のマッチを保持します

クイックリファレンス：信頼できないファイルからPDFツリーを読む

• サイクル安全、スタック安全なネームツリー／ナンバーツリー走査にはv3.539.45以降へ、逆転した/Limitsが鍵を隠さないようにするにはv3.539.51以降へアップグレードする
• GetNamedDestinationの0は「不在」、GetDestPageの0は「存在するが使用不能」と受け取る
• /JavaScriptネームツリーにはGlobalJavaScriptCountとGlobalJavaScriptPackageNameを使う。GetDocJavaScriptは代わりにカタログの/AAトリガーを読む
• 添付ファイルとスクリプトパッケージは1からライブラリが報告するカウントまででインデックスする。無効なキーは数えられません
• 自前のツリーコードでは、ノードにポップ時に訪問印を付け、子は逆順に積み、/Limitsは正しい型の順序付きペアのときだけ枝刈りに使う

プリフライトツール、アーカイバー、ビューアーは、どのページが描画されるより先にこれらのツリーを読みます。だからアップロードキューに届くどんなものにも耐えなければなりません。上で述べたツーリーリーダーは、DelphiとFree Pascalの両方でビルドされるPDFlibPas（Delphi向けPDF Library）に同梱されています