PDFlibPas name tree'leri: döngü, bozuk Limits, dev yapraklar

Delphi için losLab PDF kütüphanesi olan PDFlibPas, PDF name tree'leri ile number tree'lerini v3.539.45'ten beri açık bir yığın ve bir visited set ile geziyor; böylece döngülü /Kids, paylaşılan çocuklar ve binlerce katman derinliğindeki tree'ler call stack'i tüketmiyor ya da girdileri çoğaltmıyor. v3.539.51'den beri eksik, bozuk ya da ters çevrilmiş bir /Limits çifti, anahtarı tutan bir dalı asla saklayamaz. Named destination'lar, page label'lar, ekler ve belge düzeyi JavaScript'in hepsi bu iki kod yolundan okunur; bu da onları kendiniz üretmediğiniz her PDF'in attack surface'inin parçası yapar

Tetikleyici nadiren egzotiktir. Bir fuzzer, düşmanca bir yükleme ya da hatalı bir incremental save, bir ataya geri işaret eden /Kids girdisi yazar ve özyinelemeli bir gezgin iki kilobaytlık dosyada stack overflow ile ölür. Daha sessiz başarısızlık, bozuk bir /Limits dizisine güvenen ve apaçık orada olan bir hedef için "not found" bildiren bir aramadır

Name tree'leri ve number tree'leri bir PDF'te nerede görünür?

Name tree'leri ve number tree'leri, bir PDF'in büyük bir anahtar kümesini object'lere eşlediği her yerde görünür ve PDFlibPas en az dördünü public API'ler üzerinden okur. ISO 32000-1 §7.9.6 name tree'yi (string anahtarlar, Table 36), §7.9.7 ise number tree'yi (integer anahtarlar, Table 37) tanımlar. İkisi de dengeli-imsi tree'lerdir: kök ve ara düğümleri /Kids taşır, yaprakları sıralı key/value çiftlerini /Names ya da /Nums içinde taşır ve kök olmayan düğümleri altlarındaki en küçük ile en büyük anahtarı taşıyan iki elemanlı bir /Limits dizisi taşır

Tree	Nerede durur	Belirtim	PDFlibPas okuma API'si
Named destination'lar	Name sözlüğünde /Dests	§12.3.2.3	GetNamedDestination, ardından GetDestPage / GetDestType
Page label'lar	Katalogda /PageLabels (number tree)	§12.4.2	GetPageLabel
Ekler	Name sözlüğünde /EmbeddedFiles	§7.7.4, §7.11.4	EmbeddedFileCount, GetEmbeddedFileStrProperty
Belge düzeyi JavaScript	Name sözlüğünde /JavaScript	§7.7.4	GlobalJavaScriptCount, GlobalJavaScriptPackageName

O tablodaki iki ayrıntıyı kaçırmak kolaydır. Named destination'ların ayrıca daha eski bir PDF 1.1 biçimi vardır: name object'lerle anahtarlanan katalogdaki sade bir /Dests sözlüğü ve GetNamedDestination, PDF 1.2 name tree'sine inmeden önce o sözlüğü denetler. Ve GetDocJavaScript hiçbir name tree okuyucusu değildir: katalog /AA sözlüğündeki belge tetikleyicilerine bağlı script'leri döndürür (WS, DS, WP, DP, DC); belge açılırken koşan isimli script paketleri ise /JavaScript name tree'sinde yaşar

O yapıların her baytı dosyadan gelir. Belirtim bir yazıcının ne üreteceğini söyler; bir okuyucunun başka bir şey almasını engelleyemez — Pascal PDF ayrıştırıcısını kötücül dosyalara karşı sağlamlaştırmak yazısının ardındaki ders de budur, burada buffer boyutlarından çok tree biçimine uygulanır

Döngülü bir /Kids dizisi özyinelemeli tree gezginini neden çökertir?

Döngülü bir /Kids dizisi özyinelemeli gezgini çökertir, çünkü özyinelemenin içinde hiçbir şey daha önce bir düğüm gördüğünü fark etmez; kendi atasına referans veren bir çocuk, sonlu bir dosyayı sonsuz bir inişe çevirir. v3.539.45 öncesinde NameTreeLookup, NumTreeLookup, EnumNumTree ve dâhilî TPDFNameTree.ProcessNode çocuk başına bir kez kendini çağırıyordu. Tek bir kendi kendine referans süreci bitirmeye yetiyordu ve meşru ama çok derin bir tree hiç döngü olmadan da aynısını yapabiliyordu

Daha ılımlı bir varyant çökertmek yerine sonuçları bozar. İki /Kids girdisi aynı yaprağa referans verdiğinde saf bir numaralandırma onu iki kez ziyaret eder ve bir ek sayısı ya da script paketi listesi var olmayan girdiler bildirir

Düzeltme, özyinelemeyi heap üzerinde açık bir son-giren-ilk-çıkar yığınıyla ve dictionary kimliğiyle anahtarlanan bir visited set ile değiştirir. Bir düğüm, push edildiğinde değil pop edildiğinde işaretlenir; böylece döngülü bir referans yığında kısa süre kalabilir ama yeniden yüzeye çıktığı anda atılır. Her ayrı düğüm çocuklarını tam olarak bir kez genişletir; toplam iş, ayrı dictionary'lerin sayısı artı /Kids dizilerinin toplam uzunluğuyla sınırlanır. Derinlik önemini yitirir: 4.096 katmanlı bir zincir, bir döngünün 4.096 iterasyonu ve bir hash set'te 4.096 girdiden ibarettir

Yine de sıra önem taşır ve onu korumak için yığın ters beslenmek zorundadır. Çocuklar son indeksten ilkine doğru push edilir; böylece en soldaki çocuk ilk pop edilen olur ve yapraklar üreticinin yazdığı aynı soldan sağa sırayla çıkar. GetPageLabel buna bağlıdır: her numaralandırılmış aralığı gezinir ve başlangıç indeksi sayfaya eşit ya da onun altında olan sonuncuyu uygular; numaralandırmayı ters çevirmek 200. sayfaya sessizce ön-materyal stilini verirdi. Aşağıdaki iskelet, örüntüyü herhangi bir PDF object modelinden bağımsız, soyut bir düğüm tipi üzerinde gösterir

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // bir yaprakta boş
    Keys: TArray<string>;      // yaprak anahtarları, düzgün bir üreticide sıralı
    Values: TArray<Integer>;   // Keys'e paralel
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// /Limits bir ipucudur: yalnızca iyi biçimli, sıralı bir çift dal budayabilir
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;                      // döngü ya da paylaşılan çocuk: gördük
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // Soldaki çocuk önce çıksın diye sağdan sola push et
        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;
      // Bu yapraktaki ıskalama hüküm değildir: kardeşleri çıkarmaya devam et
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

Bir arama ilk eşleşen dalda neden duramaz?

Bir arama, aralığı eşleşen ilk dalda duramaz, çünkü gerçek bir dosyada /Limits aralıkları üst üste binebilir ya da yalan söyleyebilir ve anahtarı talep eden dal, onu tutan dal olmak zorunda değildir. v3.539.45 öncesi aramalar, /Limits'i anahtarı kapsayan ilk çocukta Found bayrağı set ediyor, ona iniyor ve başka bir kardeşe bakmıyordu. O çocuk boş, bayat ya da köke geri dönen bir döngü çıkarsa yanıt nil oluyordu — hemen ardından gelen kardeş anahtarı tutsa bile

Artık NameTreeLookup ile NumTreeLookup'in ikisini de ayakta tutan yeniden yazılmış FindTreeValue, aralığı anahtarı dışlamayan her çocuğu push eder ve bir eşleşme bulana ya da yığını boşaltana dek pop etmeyi sürdürür. Bir yaprak içindeki ıskalama yalnızca o yapraktaki ıskalamadır. İyi biçimli bir tree'de bu fazladan hiçbir şeye mal olmaz; bozuk birinde birkaç düğüm ziyareti daha pahalıya gelir ve doğru yanıtı döndürür

Yaprak araması aynı felsefeyi izler. ISO 32000-1, bir /Names dizisindeki anahtarların bayt değerine göre sıralı olmasını ister; dolayısıyla yaprakta önce binary search çalışır. O başarısız olursa PDFlibPas çiftlerin doğrusal taramasına döner, yoksa sıra dışı bir yaprak mevcut bir anahtarı görünmez kılardı. Sıralama bir hızlı yoldur, filtre değil

Arama bir yapısal çelişki üzerinde tahmin yürütmeyi de reddeder. Table 36 bir düğümün /Kids ya da /Names taşımasına izin verir, ikisine birden asla; arama yolu ikisini birden taşıyan düğümü bozuk sayar ve bir yorumu seçmek yerine onu atlar. EnumNumTree gibi numaralandırma yolları daha toleranslıdır ve ikisi de mevcutken /Kids'i izler

Bir okuyucu /Limits'e ne için güvenebilir?

Bir okuyucu /Limits'e yalnızca işi atlamak için, bir anahtarın yokluğuna karar vermek için asla ve yalnızca çift iyi biçimliyken güvenebilir. Table 36, ara ve yaprak düğümlerinin en küçük ile en büyük anahtarın iki elemanlı dizisi olarak /Limits taşıması gerektiğini söyler; ama pratikte girdi elle düzenlemelerden sonra kaybolur, bir name tree'de sayılar tutar ya da sınırları değişmiş gelir. PDFlibPas v3.539.45 ile v3.539.51 her olguyu aynı biçimde çözümler: aralık, doğru tipte sıralı bir çift olarak okunamıyorsa çocuk aranabilir kalır

• Eksik /Limits: eski aralık denetimi False döndürüyor ve çocuk büsbütün atlanıyordu; girdiyi unutan bir üretici bütün alt tree'sini ulaşılmaz kılıyordu. v3.539.45'ten beri çocuk aranır
• Yanlış tip ya da yanlış uzunluk — bir name tree'de sayılar ya da tek elemanlı bir dizi gibi: v3.539.45'ten beri tam olarak eksik girdi gibi işlenir
• [(Z) (A)] ya da [9 0] gibi ters çevrilmiş sınırlar: v3.539.45 hâlâ onları kullanıyordu ve Lo > Hi iken hiçbir anahtar Lo <= Key <= Hi'yi sağlayamaz; dal her arama için dışlanıyordu. v3.539.51'den beri bir aralık, yalnızca alt sınırı üst sınırını aşmadığında budama için kullanılır
• İyi biçimli, sıralı ve doğru: dalı atlamak için kullanılır; girdinin bütün amacı budur

Gerçek anahtarlar her olguda sonucu belirler. Düşmanca bir /Limits, PDFlibPas'a gereğinden çok düğüm ziyaret ettirebilir ama bozuk bir artık var olan bir hedefi yok edemez. Çağıran tarafından hiçbir şey değişmez: GetNamedDestination, ad gerçekten yokken 0, aksi hâlde bir destination ID döndürür ve destination fonksiyonları işi oradan alır

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;
    // Önce Catalog /Dests (PDF 1.1), sonra /Dests name tree'si
    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 kökünde [(a) (z)] aralığı altında köke geri dönen bir çocuğu ve ters çevrilmiş [(z) (a)] limitleri altında gerçek girdiyi tutan ikinci bir çocuğu taşıyan elle yazılmış bir dosyaya karşı çalıştırıldığında bu prosedür, hedefi 2. sayfaya ve 2 view tipine (Fit) çözümler. v3.539.45 öncesinde aynı arama 0 döndürüyordu; çünkü döngülü çocuk anahtarı önce talep ediyor ve arama kardeşine hiç ulaşmıyordu. Yalnızca v3.539.45 yine 0 döndürüyordu; çünkü ters çevrilmiş aralık gerçek yaprağı dışlıyordu. Sonra bu hedeflere işaret eden outline'ı okuyacaksanız, Delphi'de PDF bookmark ve annotation action'larını okuma yardımcı yazısı action tarafını kapsar

32.769 isimli bir yaprak TPDFNameTree'yi nasıl kırdı?

32.769 name/value çifti taşıyan bir yaprak TPDFNameTree'yi kırdı, çünkü dâhilî FindIndex'i iki sayıyı tek bir 32 bitlik Integer'a paketliyordu: üst 16 bitte yaprağın dâhilî dizi listesindeki konumu, alt 16 bitte ise o yaprağın /Names dizisi içindeki girdi ofseti. Her çift iki dizi yuvası kaplar; dolayısıyla 32.769uncu çift, 32.768 indeksli çift, 65.536 ofsetinde — yani $10000 — başlar. O değer üst yarıya elir ve decoder onu bir sonraki yaprakta 0 ofseti olarak geri okur

TPDFNameTree, eklerin, global JavaScript paketlerinin ve named destination yazımlarının ardındaki sınıftır; sonuçları somutlaştıran da budur. Tek yapraklı bir tree'de sonraki yaprak yoktur; FindKey ile DeleteKey yaprak listesinin sonunun ötesini indeksliyordu. Çok yapraklı bir tree'de ise istenen yerine izleyen yaprağın ilk çiftini döndürüyor ya da siliyordu. Bu arada HasKey kendi taramasını koşturuyor ve anahtarı mevcut bildiriyordu; sınıf kendi kendisiyle çelişiyordu. API sembolü başına bir named destination taşıyan üretilmiş bir referans kılavuzu çabalamadan 32.768 girdiyi aşar ve bazı üreticiler hepsini tek bir düz yaprağa yazar

v3.539.45'ten beri FindIndex dizi indeksini ayrı bir out parametresiyle, tam girdi ofsetini ise sonucu olarak döndürür; iki değer de kırpılmaz. Aynı sürüm iki komşuyu da sıkılaştırdı. KeyName artık yalnızca gerçek string anahtarları sayıp döndürür ve 0 ya da altındaki indeks için boş string verir; önceden geçersiz bir anahtarı izleyen herhangi bir object'e cast ediyordu. HasKey artık sayısal ya da başka türlü geçersiz bir anahtarı boş ad saymıyor. [(Valid) 42 123 456] gibi bir yaprak için HasKey('') artık False'tur ve KeyName(2) boş string döndürür

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'si; olmayanı düz sayfa numaraları döndürür
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // /EmbeddedFiles name tree'si; indeksler 1 tabanlı, string olmayan anahtarlar atlanır
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // ad, MIME tipi
    // /JavaScript name tree'si: paket adlarını listele, hiçbirini çalıştırma
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

Aynı elle yazılmış dosyada — /PageLabels kökü bir yaprağı iki kez listeliyor ve kendine referans veriyor — bu denetim iki sayfa için i ile A-1'i basar, her aralığı bir kez, ve kendi köküne geri işaret eden bir /JavaScript tree'sinden gelen tek script paketini basar. Page label'ların yazma tarafının /Kids kökleriyle kendi tarihi vardır; /Kids number tree'lerinde saklanan PDF page label'larının düzeltilmesinde kapsanır. AddPageLabels eklemeden önce böyle bir kökü düzleştirir ve burada anlatılan aynı EnumNumTree numaralandırmasına dayanır

Bu sağlamlaştırma hâlâ neyi garanti etmez?

Sağlamlaştırma, gerçek anahtarları sapasağlam tree'ler için sonlanmayı, kararlı sırayı ve doğru sonuçları garanti eder; bozuk bir tree'ye yazarının kastettiği anlamı vermez. Üzerine inşa etmeden önce bilinmeye değer birkaç sınır vardır

• Visited set object kimliğiyle çalışır. İçerikleri özdeş iki ayrı dictionary iki düğümdür; dolayısıyla bir yaprağa referans vermek yerine onu kopyalayan bir üretici hâlâ çift girdi üretir
• İyi biçimli, sıralı ama yanlış bir /Limits hâlâ budar. Aralıkları bir optimizasyon olarak kullanan bir okuyucu, inandırıcı yalan söyleyen bir aralığa karşı da bağışık olamaz; tek alternatif /Limits'i büsbütün yok sayıp her yaprağı taramaktır
• Numaralandırma dosya sırasını korur ama sıralamaz. GetPageLabel, sayfaya eşit ya da onun altındaki son numaralandırılmış aralığı uygular; aralıkları sıra dışı yazan bir üretici dosya-sırası semantiği alır
• Bellek, ayrı düğüm ve girdi sayısıyla büyür. Gezinme bir liste ve bir hash set ekler, başka hiçbir şey; ama 100 MBlik bir name tree ayrıştırmadan sonra da 100 MBlik name tree'dir
• Tek yaprak içindeki çift anahtarlar bildirilmez. Binary search, ilk hangi eşleşen çifte çarparsa onu döndürür; doğrusal yedek, taradığı son eşleşmeyi tutar

Hızlı başvuru: güvenilmeyen dosyalardan PDF tree'leri okuma

• Name tree'leri ve number tree'lerin döngüye ve yığına dayanıklı gezinimi için v3.539.45 ve sonrasına, ters çevrilmiş /Limits'in anahtarları artık saklamaması için v3.539.51 ve sonrasına yükseltin
• GetNamedDestination'in 0 döndürmesini "yok" sayın, GetDestPage'in 0 döndürmesini "var ama kullanılamaz" sayın
• /JavaScript name tree'si için GlobalJavaScriptCount ile GlobalJavaScriptPackageName'i kullanın; GetDocJavaScript onun yerine katalog /AA tetikleyicilerini okur
• Ekleri ve script paketlerini 1'den kütüphanenin bildirdiği sayıya dek indeksleyin; geçersiz anahtarlar sayılmaz
• Kendi tree kodunuzda düğümleri pop'ta ziyaret edilmiş işaretleyin, çocukları ters push edin ve /Limits'e yalnızca iyi tipli, sıralı bir çiftken budurtun

Pre-flight araçları, arşivleyiciler ve görüntüleyiciler bu tree'leri herhangi bir sayfa render edilmeden önce okur; dolayısıyla bir yükleme kuyruğuna ne gelirse gelsin ayakta kalmak zorundadırlar. Yukarıda anlatılan tree okuyucuları, hem Delphi hem Free Pascal ile derlenen Delphi PDF kütüphanesi PDFlibPas ile gelir