Name Tree PDF: Siklus, /Limits, dan Daun Besar di PDFlibPas

PDFlibPas, PDF Library losLab untuk Delphi, menelusuri name tree dan number tree PDF dengan explicit stack dan visited set sejak v3.539.45, sehingga /Kids bersiklus, anak bersama, dan tree sedalam ribuan level tak lagi menghabiskan call stack atau menduplikasi entri. Sejak v3.539.51 pasangan /Limits yang hilang, malformed, atau terbalik tak pernah lagi menyembunyikan cabang yang memegang key-nya. Named destination, page label, attachment, dan JavaScript level dokumen semuanya dibaca lewat dua jalur code ini, yang menjadikannya bagian dari attack surface PDF apa pun yang bukan hasil produksi Anda sendiri

Pemicunya jarang eksotis. Sebuah fuzzer, upload jahat, atau incremental save yang bermasalah menulis entri /Kids yang menunjuk kembali ke ancestor, dan walker rekursif mati dengan stack overflow di file dua kilobyte. Kegagalan yang lebih senyap adalah lookup yang percaya pada array /Limits yang rusak dan melaporkan "not found" untuk destination yang jelas-jelas ada

Di mana name tree dan number tree muncul di sebuah PDF?

Name tree dan number tree muncul di mana pun PDF memetakan sekumpulan key yang besar ke objek, dan PDFlibPas membaca setidaknya empat di antaranya lewat API publik. ISO 32000-1 §7.9.6 mendefinisikan name tree (key string, Table 36) dan §7.9.7 number tree (key integer, Table 37). Keduanya adalah tree yang mendekati seimbang, dengan root dan node antara membawa /Kids, leaf-nya membawa pasangan key/value terurut di /Names atau /Nums, dan node non-root membawa array /Limits dua elemen berisi key terkecil dan terbesar di bawahnya

Tree	Tempatnya	Spesifikasi	API baca PDFlibPas
Named destination	/Dests di name dictionary	§12.3.2.3	GetNamedDestination, lalu GetDestPage / GetDestType
Page label	/PageLabels di catalog (number tree)	§12.4.2	GetPageLabel
Attachment	/EmbeddedFiles di name dictionary	§7.7.4, §7.11.4	EmbeddedFileCount, GetEmbeddedFileStrProperty
JavaScript level dokumen	/JavaScript di name dictionary	§7.7.4	GlobalJavaScriptCount, GlobalJavaScriptPackageName

Dua detail di tabel itu gampang terlewat. Named destination juga punya bentuk PDF 1.1 yang lebih tua, sebuah dictionary /Dests polos di catalog yang di-key oleh name object, dan GetNamedDestination mengecek dictionary itu lebih dulu sebelum menuruni name tree PDF 1.2. Dan GetDocJavaScript sama sekali bukan pembaca name tree: ia mengembalikan script yang menempel pada trigger dokumen di dictionary /AA catalog (WS, DS, WP, DP, DC), sementara package script bernama yang jalan saat dokumen dibuka tinggal di name tree /JavaScript

Setiap byte struktur itu datang dari file. Spesifikasi menyatakan apa yang seharusnya dihasilkan writer; ia tak bisa menghalangi reader menerima hal lain, pelajaran yang sama di balik menghardening parser PDF Pascal terhadap file jahat, diterapkan di sini pada bentuk tree alih-alih ukuran buffer

Kenapa array /Kids bersiklus merusak tree walker rekursif?

Array /Kids bersiklus merusak walker rekursif karena tak ada apa pun di dalam rekursi itu yang menyadari bahwa ia pernah melihat node tersebut, sehingga anak yang mereferensikan ancestor-nya sendiri mengubah file terbatas menjadi penurunan tanpa akhir. Sebelum v3.539.45, NameTreeLookup, NumTreeLookup, EnumNumTree, dan TPDFNameTree.ProcessNode internal semuanya memanggil dirinya sendiri sekali per anak. Satu self-reference saja cukup mengakhiri prosesnya, dan tree yang sah tapi sangat dalam bisa melakukan hal yang sama tanpa siklus apa pun

Varian yang lebih ringan merusak hasil alih-alih crash. Ketika dua entri /Kids mereferensikan leaf yang sama, enumerasi naif mengunjunginya dua kali, dan jumlah attachment atau daftar package script melaporkan entri yang tak ada

Perbaikannya mengganti rekursi dengan explicit stack last-in, first-out di heap dan sebuah visited set yang di-key oleh identitas dictionary. Node ditandai saat ia di-pop, bukan saat di-push, sehingga reference bersiklus boleh saja duduk sebentar di stack tapi dibuang begitu muncul kembali. Tiap node yang berbeda mengembangkan anak-anaknya tepat sekali, yang membatasi total kerja oleh jumlah dictionary berbeda plus panjang total array /Kids-nya. Kedalaman berhenti jadi soal: rantai 4.096 level hanyalah 4.096 iterasi loop dan 4.096 entri di hash set

Urutan tetap penting, dan stack harus diisi mundur agar urutan itu terjaga. Anak-anak di-push dari indeks terakhir turun ke pertama, sehingga anak paling kiri di-pop lebih dulu dan leaf keluar dalam urutan kiri-ke-kanan yang sama seperti yang ditulis producer. GetPageLabel bergantung pada itu: ia menelusuri setiap range hasil enumerasi dan menerapkan yang terakhir dengan indeks awal pada atau di bawah halaman, jadi membalik enumerasi akan diam-diam memberi halaman 200 gaya front-matter. Kerangka di bawah menunjukkan polanya pada tipe node abstrak, independen dari object model PDF mana pun

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // kosong pada leaf
    Keys: TArray<string>;      // key leaf, terurut oleh producer yang sopan
    Values: TArray<Integer>;   // paralel dengan Keys
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// /Limits cuma petunjuk: hanya pasangan well-formed dan terurut yang boleh memangkas cabang
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;                      // siklus atau anak bersama: sudah dilihat
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // Push kanan-ke-kiri agar kid paling kiri di-pop lebih dulu
        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;
      // Miss di leaf ini bukan vonis: terus pop sibling
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

Kenapa lookup tak boleh berhenti di cabang pertama yang cocok?

Lookup tak bisa berhenti di cabang pertama yang range-nya cocok, karena range /Limits di file nyata bisa tumpang tindih atau berbohong, dan cabang yang mengklaim key-nya belum tentu cabang yang memegangnya. Lookup pra-v3.539.45 men-set flag Found pada anak pertama yang /Limits-nya mencakup key, menuruni cabang itu, dan tak pernah melirik sibling lain. Kalau anak itu ternyata kosong, basi, atau loop kembali ke root, jawabannya nil, meskipun sibling persis berikutnya memegang key-nya

FindTreeValue yang ditulis ulang, yang kini menopang NameTreeLookup maupun NumTreeLookup, men-push setiap anak yang range-nya tak mengecualikan key dan terus pop sampai menemukan cocokan atau stack-nya kosong. Miss di dalam satu leaf hanyalah miss di dalam satu leaf. Di tree yang well-formed ini tak menambah biaya; di yang rusak, biayanya beberapa kunjungan node ekstra dan jawabannya benar

Pencarian leaf mengikuti filosofi yang sama. ISO 32000-1 mewajibkan key di array /Names terurut berdasarkan nilai byte, jadi leaf dicari dengan binary search lebih dulu. Kalau itu gagal, PDFlibPas turun ke scan linear atas pasangan-pasangannya, karena leaf yang tak terurut semestinya akan membuat key yang ada jadi tak terlihat. Pengurutan adalah fast path, bukan filter

Lookup juga menolak menebak pada satu kontradiksi struktural. Table 36 membolehkan node membawa /Kids atau /Names, tak pernah keduanya, dan jalur lookup memperlakukan node yang membawa keduanya sebagai malformed dan melewatinya alih-alih memilih satu interpretasi. Jalur enumerasi seperti EnumNumTree lebih toleran dan mengikuti /Kids ketika keduanya ada

Untuk apa reader boleh mempercayai /Limits?

Reader boleh mempercayai /Limits hanya untuk melewati kerja, tak pernah untuk memutuskan bahwa key tak ada, dan hanya ketika pasangannya well-formed. Table 36 menyatakan node antara dan leaf wajib membawa /Limits sebagai array dua elemen berisi key terkecil dan terbesar, tapi praktiknya entri itu hilang setelah edit tangan, berisi angka di name tree, atau datang dengan batasnya tertukar. PDFlibPas v3.539.45 dan v3.539.51 menyelesaikan tiap kasus dengan cara yang sama: kalau range tak bisa dibaca sebagai pasangan terurut bertipe benar, anaknya tetap dicari

• /Limits hilang: range check lama mengembalikan False dan anaknya dilewati bulat-bulat, sehingga producer yang lupa menulis entri membuat seluruh subtree-nya tak terjangkau. Sejak v3.539.45 anaknya dicari
• Tipe salah atau panjang salah, seperti angka di name tree atau array satu elemen: diperlakukan persis seperti entri hilang sejak v3.539.45
• Batas terbalik seperti [(Z) (A)] atau [9 0]: v3.539.45 masih memakainya, dan tak ada key yang bisa memenuhi Lo <= Key <= Hi ketika Lo > Hi, sehingga cabang itu dieksklusi untuk setiap lookup. Sejak v3.539.51 sebuah range dipakai untuk memangkas hanya ketika batas bawahnya tak melebihi batas atasnya
• Well-formed, terurut, dan benar: dipakai untuk melewati cabang, dan itulah inti keberadaan entrinya

Key sungguhan yang menentukan hasil di setiap kasus. /Limits jahat bisa membuat PDFlibPas mengunjungi lebih banyak node dari perlu, tapi yang malformed tak lagi bisa membuat destination yang ada lenyap. Dari sisi caller tak ada yang berubah: GetNamedDestination mengembalikan 0 ketika namanya memang tak ada dan destination ID selain itu, dan fungsi-fungsi destination melanjutkan dari situ

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) lebih dulu, lalu 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;

Dijalankan terhadap file buatan tangan yang root /Dests-nya punya satu anak yang berputar kembali ke root di bawah range [(a) (z)] dan anak kedua yang memegang entri asli di bawah limits terbalik [(z) (a)], prosedur ini me-resolve destination ke halaman 2 dengan view type 2 (Fit). Sebelum v3.539.45 lookup yang sama mengembalikan 0, karena anak yang berputar mengklaim key-nya lebih dulu dan pencarian tak pernah sampai ke sibling-nya; v3.539.45 saja masih mengembalikan 0, karena range terbalik mengeksklusi leaf aslinya. Kalau Anda kemudian membaca outline yang menunjuk ke destination-destination ini, artikel pendamping tentang membaca action bookmark dan annotation PDF di Delphi membahas sisi action-nya

Bagaimana leaf dengan 32.769 nama merusak TPDFNameTree?

Leaf dengan 32.769 pasangan name/value merusak TPDFNameTree karena FindIndex internalnya memadatkan dua angka ke satu Integer 32-bit: posisi leaf di array list internal di 16 bit tinggi dan offset entri di dalam array /Names leaf itu di 16 bit rendah. Tiap pasangan menempati dua slot array, jadi pasangan ke-32.769, indeks pasangan 32.768, mulai di offset 65.536, yaitu $10000. Nilai itu carry ke paruh tinggi, dan decoder membacanya kembali sebagai offset 0 di leaf berikutnya

TPDFNameTree adalah class di balik attachment, package JavaScript global, dan penulisan named destination, yang membuat konsekuensinya konkret. Di tree satu leaf tak ada leaf berikutnya, jadi FindKey dan DeleteKey mengindeks melampaui ujung daftar leaf; di tree multi-leaf keduanya mengembalikan atau menghapus pasangan pertama leaf berikutnya alih-alih yang diminta. Sementara itu HasKey menjalankan scan miliknya sendiri dan melaporkan key itu ada, sehingga class ini kontradiksi dengan dirinya sendiri. Reference manual hasil generate dengan satu named destination per simbol API melewati 32.768 entri tanpa usaha, dan beberapa producer menulis semuanya ke satu leaf datar

Sejak v3.539.45, FindIndex mengembalikan indeks array lewat parameter out terpisah dan offset entri penuh sebagai hasilnya, sehingga tak ada nilai yang terpotong. Release yang sama mengetatkan dua tetangganya. KeyName kini hanya menghitung dan mengembalikan key string sungguhan dan mengembalikan string kosong untuk indeks 0 atau di bawahnya, yang sebelumnya men-cast objek apa pun yang menyusul key invalid. HasKey tak lagi memperlakukan key numerik atau invalid lainnya sebagai nama kosong. Untuk leaf seperti [(Valid) 42 123 456], HasKey('') kini False dan KeyName(2) mengembalikan string kosong

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; file tanpa itu mengembalikan nomor halaman polos
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // Name tree /EmbeddedFiles; indeks 1-based, key non-string dilewati
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // name, MIME type
    // Name tree /JavaScript: daftar nama package, tanpa mengeksekusi apa pun
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

Di file buatan tangan yang sama, yang root /PageLabels-nya mendaftar satu leaf dua kali dan mereferensikan dirinya sendiri, audit ini mencetak i dan A-1 untuk kedua halaman, tiap range sekali, dan satu-satunya package script dari tree /JavaScript yang juga menunjuk kembali ke root-nya sendiri. Sisi tulis page label punya sejarah sendiri dengan root /Kids, dibahas di memperbaiki page label PDF yang tersimpan di number tree /Kids; AddPageLabels meratakan root semacam itu sebelum menyisipkan, dan ia bergantung pada enumerasi EnumNumTree yang sama yang dijelaskan di sini

Apa yang masih tak dijamin oleh hardening ini?

Hardening ini menjamin terminasi, urutan stabil, dan hasil yang benar untuk tree yang key sungguhannya utuh; ia tak membuat tree yang rusak berarti seperti yang dimaksudkan pembuatnya. Beberapa batas layak diketahui sebelum Anda membangun di atasnya

• Visited set bekerja dengan identitas objek. Dua dictionary berbeda dengan konten identik adalah dua node, jadi producer yang menyalin leaf alih-alih mereferensikannya tetap menghasilkan entri duplikat
• /Limits yang well-formed, terurut, tapi salah tetap memangkas. Reader yang memakai range sebagai optimasi tak mungkin sekaligus kebal terhadap range yang berbohong secara meyakinkan; satu-satunya alternatif adalah mengabaikan /Limits sepenuhnya dan memindai setiap leaf
• Enumerasi melestarikan urutan file tapi tak mengurutkan. GetPageLabel menerapkan range terakhir yang dienumerasi pada atau di bawah halaman, jadi producer yang menulis range tak berurutan mendapat semantik urutan file
• Memori tumbuh dengan jumlah node dan entri yang berbeda. Traversalnya menambah satu list dan satu hash set, tak lebih, tapi name tree 100 MB tetaplah name tree 100 MB setelah di-parse
• Key duplikat di dalam satu leaf tak dilaporkan. Binary search mengembalikan pasangan cocok mana pun yang kena pertama; fallback linear menyimpan cocokan terakhir yang dipindainya

Referensi cepat: membaca tree PDF dari file tak terpercaya

• Upgrade ke v3.539.45 atau lebih baru untuk traversal name tree dan number tree yang aman siklus dan aman stack, dan ke v3.539.51 atau lebih baru agar /Limits terbalik tak lagi menyembunyikan key
• Perlakukan GetNamedDestination yang mengembalikan 0 sebagai "tak ada", dan GetDestPage yang mengembalikan 0 sebagai "ada tapi tak terpakai"
• Pakai GlobalJavaScriptCount dan GlobalJavaScriptPackageName untuk name tree /JavaScript; GetDocJavaScript membaca trigger /AA catalog sebagai gantinya
• Indeks attachment dan package script dari 1 sampai jumlah yang dilaporkan library; key invalid tak dihitung
• Di code tree Anda sendiri, tandai node visited saat pop, push anak dalam urutan terbalik, dan biarkan /Limits memangkas hanya ketika ia pasangan bertipe benar dan terurut

Tool pre-flight, archiver, dan viewer membaca tree-tree ini sebelum halaman mana pun dirender, jadi mereka harus selamat dari apa pun yang tiba di antrean upload. Pembaca tree yang dijelaskan di atas dikirim bersama PDFlibPas, PDF Library untuk Delphi, yang dibangun dengan Delphi maupun Free Pascal