LlosLabソフトウェア開発ブログPDF、Delphi、およびドキュメントソフトウェア開発者向けのエンジニアリングノート。

技術記事

破損したPDFのXrefテーブル再構築:Delphiリカバリスキャン

Delphi PDF Library

PDFのクロスリファレンステーブルが使い物にならない場合、その修正はテーブルを完全に無視してファイル本体から再構築することである。PDFlibPas Delphi PDF Libraryは単一パスのトークンスキャナでこれを行い、目にした本物の間接オブジェクトヘッダーをすべて記録し、trailer辞書を復元して、再構築したテーブルを通常のローダーに渡す

PDFが破損したとき、最初に壊れるのは何か

クロスリファレンステーブルはPDFの中で最も脆弱な部分である。絶対バイトオフセットを保存している唯一の部分だからだ。ISO 32000-1 §7.5.4はこれらのエントリをファイル先頭からの10桁オフセットとして定義しており、§7.5.5はstartxrefキーワードをファイル末尾付近に置いてそのテーブル自体を指し示す。バイト列をずらすどんな編集も、これらの数値のすべてを無効化してしまう。テキストモードで走りCRLFを変換してしまったFTPセッション、途中で切れたダウンロード、共有ドライブ上で不良になったセクタ、インクリメンタル更新を正しく書かずに追記したバッチツール——これらはすべてオブジェクトデータを完璧に読める状態のまま残しつつ、インデックスだけをガベージにしてしまう

だからこそ「ファイルが破損しているため修復しています」というダイアログはこれほどありふれている。バイト列はほとんど常にそのまま残っている。失われているのは地図のほうだ。したがって再構築は失われたデータの法医学的復元ではなく、本体から導出できるインデックスの再構築であり、ユーザーが予想するよりもはるかに高い確率で成功する。ページツリー、フォント、画像といったコストの高いコンテンツには手が触れられていないからである

なぜ「N 0 obj」を検索すると誤検出が起きるのか

素朴な再構築は生のバイト列から「整数、整数、obj」というパターンを検索し、ヒットしたものをすべて記録する。それは検出しすぎてしまう。PDFはコンテナ形式であり、ファイルの3つの領域はオブジェクト文法にとって不透明である:コメント(§7.2)、文字列(§7.3.4)、そしてストリームデータ(§7.3.8)である。そのいずれもオブジェクトヘッダーとまったく同じに読めるバイト列を含みうるが、そのいずれもオブジェクトヘッダーではない。リテラル文字列内のキャプション、消し忘れたデバッグコメント、あるいは2メガバイトのFlateやDCT出力は、どれも喜んで99 0 objのように見えるものを生成してしまう

const
  Trap: AnsiString =
    '4 0 obj'#10 +
    '(a caption that mentions 88 0 obj)'#10 +   // literal string, not an object
    'endobj'#10 +
    '% 77 0 obj left over from a debug dump'#10 +  // comment, not an object
    '5 0 obj'#10 +
    '<< /Length 2097152 >>'#10 +
    'stream'#10 +
    { two MiB of compressed bytes that contain the byte sequence
      99 0 obj and, further along, a complete endstream }
    'endstream'#10 +
    'endobj'#10;

誤ったエントリは二重にコストがかかる。存在しないオブジェクト番号で再構築されたテーブルを汚染するうえ、ファイルの後方に現れる同じ番号の本物のオブジェクトを覆い隠してしまうことがある。そのためPDFlibPasはパターンマッチを一切行わない。トークン化を行うことで、カーソルの下にあるバイト列がコードなのかペイロードなのかを常に把握し、ペイロードは解釈されることなくスキップされる

64KiBブロックにわたる単一パスの状態機械

PDFlibPasはファイル全体をちょうど1回、64KiBブロック単位で、ISO 32000-1 §7.2のトークン規則と§7.3.10の間接オブジェクト構文に基づく状態機械でスキャンする。トークンは空白か区切り文字のいずれかで終わり、オブジェクトヘッダーは正のオブジェクト番号、非負の世代番号、そして裸のobjキーワードという完全な並びが確認されたときにのみ記録される。記録されるオフセットはobjキーワードの位置ではなく、オブジェクト番号トークンの開始位置であり、これはまさにクロスリファレンスエントリが指し示さなければならない位置である

function RebuildIsWhiteSpace(Value: Byte): Boolean;
begin
  Result := (Value = 0) or (Value = 9) or (Value = 10) or
            (Value = 12) or (Value = 13) or (Value = 32);
end;

function RebuildIsDelimiter(Value: Byte): Boolean;
begin
  Result := (Value = Ord('(')) or (Value = Ord(')')) or
            (Value = Ord('<')) or (Value = Ord('>')) or
            (Value = Ord('[')) or (Value = Ord(']')) or
            (Value = Ord('{')) or (Value = Ord('}')) or
            (Value = Ord('/')) or (Value = Ord('%'));
end;

重要な詳細は、トークンの状態と文字列の状態がブロック境界をまたいで生き延びることである。65536バイトの境界線をまたぐヘッダーも認識される。部分的なトークン、保留中の整数ペア、文字列内フラグのすべてが次のブロックへと持ち越されるからだ。バッファは固定されている:スキャン用に64KiB、意味を持ちうる最長トークン用に32バイトであり、ファイルサイズとともに増えていく配列はオブジェクト番号・世代番号・64ビットオフセットのリストだけであって、これらはファイルサイズではなく実際のオブジェクト数に比例する。実際にはこのスキャンは連続読み込みを発行し、文書全体で明示的なシークは最大でも2回しか行わない。これが、直接アクセスによるマージと分割に関する記事で論じた数百メガバイト規模の入力でも実用的である理由だ

なぜストリームがendstreamで終わることを信頼できないのか

ストリームデータは任意のバイト列であり、任意のバイト列は偶然endstreamという綴りになりうるからだ。streamキーワードの後に始まるストリームは、本当に終わるまで不透明なデータとしてスキップされなければならないが、終了キーワードの最初の出現は単なる候補にすぎない。PDFlibPasはこれを裏付けを要求することで解決する:endstreamトークンは、次の非空白トークンが単独のendobjであるとき——つまり§7.3.8がストリームオブジェクトの周りで要求する並びであるとき——にのみ、ストリームの本当の終端として受け入れられる。圧縮データ内の偶然のヒットにはほとんどの場合そのような後続が伴わないため、スキャナはストリームの内側に留まり続ける。それより小さな2つの規則も同じくらい重要だ。streamキーワードは、それが裸のキーワードであるときにのみストリーム状態に入る。したがって辞書内の/streamのような名前オブジェクトがこれを引き起こすことは決してない。そしてobjやtrailerトークンは、そのトークンが32バイトの上限を超えておらず、かつソリダスで始まっていない場合にのみ尊重される。この2つの防御がなければ、間違ったキー名を持つリソース辞書だけでスキャンを脱線させるのに十分であり、それはまさに信頼できないPDFを安全に解析するに関するノートで扱った敵対的入力の一種である

trailer辞書の本当の終端を見つける

オブジェクトを復元するのは仕事の半分にすぎない。ローダーは/Rootを見つけるためのtrailerを依然として必要とするからだ。PDFlibPasはスキャン中に見つかった直近64個のtrailerキーワードの位置を記憶し、最も新しいものから逆順に検証する。そのため最新の使用可能なtrailerが勝ち、辞書が後続しないはぐれキーワードは単に検証に失敗して前の候補へと落ちていく。各候補は1MiBの上限で読み込まれ、辞書の終端はネストした<<と>>の深さを、リテラル文字列のエスケープ、16進文字列、コメントとともに追跡することで特定される

// A naive reader that stops at the first '>>' truncates this trailer,
// and a fixed 2048-byte window can cut it in half on a large one
'trailer'#10 +
'<< /Size 5 /Root 1 0 R' +
'   /Custom << /Text (value >> preserved) >> >>'#10

深さの追跡は机上の議論ではない。/Encryptを失った切り詰められたtrailerは、復元可能だった暗号化文書を開けない文書に変えてしまい、/Infoやカスタムのサブ辞書を失うことは、下流システムが依存しているかもしれないメタデータを静かに捨ててしまう。ファイルが暗号化されている場合、復元されたtrailerこそが通常の認証情報経路を実行させるものであり、そのリトライの意味論は暗号化文書の読み込みに関する記事で説明したものと同じである

再構築で取り戻せないもの

再構築はベストエフォートであり、その限界について正直であることも実装の一部である。3つのケースは端的に失敗する。オブジェクトストリーム(§7.5.7)内にパックされたオブジェクトはバイトスキャンからは個別に見えないため、コンテナは生き残ってもそのクロスリファレンスストリーム(§7.5.8)が生き残らなければ、それが保持するオブジェクトは再構築によってインデックスされない。単に誤ってインデックスされただけでなく本体そのものが実際に破損しているファイルは、内容がもはやパースできないヘッダーを生成する。そして回復可能なtrailerキーワードもなく、読み取れるカタログもないファイルは、いくつオブジェクトヘッダーが見つかったとしても文書ツリーを繋ぎ止める場所を持たない

重複するオブジェクト番号は興味深い中間ケースである。インクリメンタルに更新されたファイルは同じオブジェクト番号の複数の世代を正当に含んでおり、どれが現行だったかを記録しているのは生き残ったクロスリファレンスの連鎖だけである。再構築にはその連鎖がないため、見つけたヘッダーをファイル内の順序で記録し、その後オブジェクト番号によって解決する。通常はより新しいリビジョンが勝ち、それは通常正しいのだが、更新されたのちに部分的にロールバックされた文書は、元のxrefが記述していたものとは微妙に異なる形で戻ってくることがある。線形化されたファイルも反対方向から同じ注意点を抱える:インデックスが再生成されてしまえば最初のページのレイアウトとヒントテーブルは意味を持たなくなるため、修復されたファイルは線形化されていない普通の文書として扱うべきである

var
  Pdf: TPDFlib;
begin
  Pdf := TPDFlib.Create;
  try
    if Pdf.LoadFromFile('truncated-invoice.pdf', '') = 1 then
    begin
      if Pdf.GetDocumentRepaired = 1 then
        LogWarning('xref was unusable; the table was reconstructed');
      if Pdf.PageCount > 0 then
        Pdf.SaveToFile('recovered-invoice.pdf');   // writes a clean xref
    end;
  finally
    Pdf.Free;
  end;
end;

フォールバックは自動である:PDFlibPasはクロスリファレンスの連鎖が読み取れないときはいつでも生スキャンを実行し、さらに使用中のすべてのエントリがオフセット0を主張しているとき——これは書かれはしたが決して埋められなかったテーブルの徴候である——にも実行する。GetDocumentRepairedはこの経路が実行されたときに1を返し、これは無視するのではなくログに残す価値がある。再構築によって読み込まれた文書は、何事もなかったかのようにパイプラインに残すのではなく、クリーンなファイルへ保存し直すべきだからだ。保存すれば新しく整合したクロスリファレンステーブルが書かれ、これはあらゆる下流の利用者にとって最も安上がりな修正になる

ここで示した再構築経路、GetDocumentRepairedフラグ、そしてストリーミングローダーは、このブログの他所で扱っている解析・レンダリング・署名APIとともにPDFlibPas Delphi PDF Libraryの一部である