PDFlibPas névfák: ciklusok, rossz Limits és óriáslevelek

A PDFlibPas, a losLab Delphi PDF Libraryje, v3.539.45 óta explicit veremmel és meglátogatott halmazzal járja a PDF névfákat és számfákat, így a ciklikus /Kids, a megosztott gyerekek és az ezres szintmélységű fák többé nem merítik ki a hívásveremet, és nem duplikálnak bejegyzéseket. v3.539.51 óta hiányzó, formátlan vagy fordított /Limits pár soha nem rejthet el egy kulcsot hordozó ágat. Nevesített destinációk, oldalcímkék, csatolmányok és dokumentumszintű JavaScript mind ezen a két kódon át olvas, ami bármely olyan PDF támadási felületévé teszi őket, amit nem te állítottál elő

A trigger ritkán egzotikus. Egy fuzzer, egy ellenséges feltöltés vagy egy hibás inkrementális mentés olyan /Kids bejegyzést ír, ami visszamutat egy ősre, és a rekurzív bejáró stack overflow-val hal el egy két kilobájtos fájlon. A halkabb hiba egy olyan keresés, ami megbízik egy törött /Limits tömbben, és „nincs" jelet ad egy destinációra, ami nyilvánvalóan ott van

Hol bukkan fel névfa és számfa egy PDF-ben?

Névfa és számfa ott bukkan fel, ahol egy PDF nagy kulcshalmazt rendez objektumokra, és a PDFlibPas legalább négyet olvas belőlük nyilvános API-okon át. Az ISO 32000-1 §7.9.6-a definiálja a névfat (string kulcsok, 36. táblázat), a §7.9.7 a számfat (egész kulcsok, 37. táblázat). Mindkettő félig kiegyensúlyozott fa, aminek gyökere és köztes csomópontjai /Kids-et hordoznak, levelei a rendezett kulcs/érték párokat /Names-ben vagy /Nums-ban, a nem gyökér csomópontjai pedig egy két elemű /Limits tömböt a alattuk lévő legkisebb és legnagyobb kulccsal

Fa	Hol lakik	Specifikáció	PDFlibPas olvasó API
Nevesített destinációk	/Dests a névszótárban	§12.3.2.3	GetNamedDestination, aztán GetDestPage / GetDestType
Oldalcímkék	/PageLabels a catalogban (számfa)	§12.4.2	GetPageLabel
Csatolmányok	/EmbeddedFiles a névszótárban	§7.7.4, §7.11.4	EmbeddedFileCount, GetEmbeddedFileStrProperty
Dokumentumszintű JavaScript	/JavaScript a névszótárban	§7.7.4	GlobalJavaScriptCount, GlobalJavaScriptPackageName

A táblázatban két részlet könnyen elkerüli a figyelmet. A nevesített destinációknak van egy idősebb PDF 1.1 formája is, egy sima /Dests szótár a catalogban, name objektumokkal kulcsrazva, és a GetNamedDestination előbb azt a szótárt nézi meg, mielőtt lemászana a PDF 1.2 névfára. A GetDocJavaScript pedig egyáltalán nem névfa-olvasó: a catalog /AA szótárában a dokumentum triggereire akasztott scripteket adja vissza (WS, DS, WP, DP, DC), miközben azok a nevesített script packageek, amik dokumentumnyitáskor futnak, a /JavaScript névfában laknak

Ezeknek a struktúráknak minden bájtja a fájlból jön. A specifikáció azt mondja meg, mit kell egy írónak produkálnia; nem akadályozhatja meg az olvasót abban, hogy mást kapjon, ami ugyanaz a tanulság, ami a Pascal PDF parser rosszindulatú fájlok elleni megerősítése mögött áll, csak itt faformára alkalmazva, nem pufferméretekre

Miért dönti el a ciklikus /Kids tömb a rekurzív fa bejárót?

Egy ciklikus /Kids tömb azért dönti el a rekurzív bejárót, mert a rekurzióban semmi nem veszi észre, hogy már látott egy csomópontot, így egy saját ősére hivatkozó gyerek egy véges fájlból végtelen süllyedést csinál. v3.539.45 előtt a NameTreeLookup, a NumTreeLookup, az EnumNumTree és a belső TPDFNameTree.ProcessNode mind gyerekenként egyszer meghívta önmagát. Egyetlen önreferencia is elég volt a folyamat lezárásához, és egy legális, de nagyon mély fa ugyanezt megtehette ciklus nélkül is

Egy enyhébb változat az eredményeket rontja el összeomlás helyett. Ha két /Kids bejegyzés ugyanarra a levélre hivatkozik, egy naiv enumeráció kétszer járja, és egy csatolmányszámláló vagy script package lista nem létező bejegyzéseket jelent

A javítás a rekurziót explicit, a halmon élő verem-első-be-ki veremre cseréli, meg egy meglátogatott halmazra, ami szótárazonosítót használ kulcsnak. Egy csomópont akkor kap jelölést, amikor kikerül a veremből, nem amikor bekerül, így egy ciklikus hivatkozás lehet rövid ideig a veremben, de abban a pillanatban eldobják, amikor visszajön fel. Minden külön csomópont pontosan egyszer bontja ki a gyerekeit, ami a teljes munkát a külön szótárak számára plusz a /Kids tömbjeik összhosszára szorítja. A mélység megszűnik számítani: egy 4 096 szintű lánc csupán 4 096 ciklusiteráció és 4 096 bejegyzés egy hash halmazban

A sorrend viszont továbbra is számít, és a vermet visszafelé kell etetni, hogy megmaradjon. A gyerekek az utolsó indextől az elsőig kerülnek a verembe, így a bal szélső gyerek jön ki először, és a levelek ugyanabban a balról jobbra sorrendben jönnek, ahogy a producer írta. A GetPageLabel ezen nyugszik: végigjár minden enumerált tartományt, és az utolsót alkalmazza, aminek a kezdőindexe az oldalnál nem nagyobb, így az enumeráció megfordítása csendben az előszó stílusát adná a 200. oldalnak. Az alábbi csontváz a mintát absztrakt csomóponttípuson mutatja, bármely PDF objektummodelltől függetlenül

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // üres egy levélen
    Keys: TArray<string>;      // levélkulcsok, jóhiszemű producertől rendezve
    Values: TArray<Integer>;   // párhuzamos a Keyssel
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// A /Limits tipp: csak jól formált, rendezett pár nyírhat le ágat
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;                      // ciklus vagy megosztott gyerek: láttuk
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // Jobbról balra tolsd, hogy a bal szélső gyerek jöjjön ki először
        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;
      // Egy találatlan ebben a levélben nem ítélet: popold tovább a testvéreket
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

Miért nem állhat meg a keresés az első egyező ágnál?

Egy keresés nem állhat meg az első olyan ágnál, aminek a tartománya egyezik, mert egy valós fájlban a /Limits tartományok fedhetnek át vagy hazudhatnak, és nem biztos, hogy az az ág tartja a kulcsot, ami magának követeli. A v3.539.45 előtti keresések Found flaget állítottak arra az első gyerekre, aminek a /Limits-e fedte a kulcsot, belementek, és több testvérre nem néztek. Ha az a gyerek üresnek, elavultnak vagy a gyökérre visszaloopnak bizonyult, a válasz nil volt, akkor is, ha a közvetlen következő testvér tartotta a kulcsot

Az átírt FindTreeValue, ami most már a NameTreeLookup-ot és a NumTreeLookup-ot is viszi, minden olyan gyereket a verembe tesz, aminek a tartománya nem zárja ki a kulcsot, és addig popol, míg találatot nem talál vagy ki nem ürül a verem. Egy találatlan egy levélben csak egy találatlan egy levélben. Jól formált fában ez semmi pluszköltség; sérültben néhány plusz csomópontlátogatás, cserébe a jó választ adja

A levélkeresés ugyanazt a filozófiát követi. Az ISO 32000-1 megköveteli, hogy a /Names tömb kulcsai bájtérték szerint rendezettek legyenek, így a levelet előbb bináris kereséssel nézi. Ha az elbukik, a PDFlibPas a párok lineáris átfésülésére áll át, mert egy soron kívüli levél egyébként láthatatlanná tenné egy jelen lévő kulcsot. A rendezés gyorsút, nem szűrő

A keresés egy szerkezeti ellentmondásban nem találgat. A 36. táblázat szerint egy csomópont /Kids-et vagy /Names-t hordozhat, sosem mindkettőt, és a keresési út azt a csomópontot, ami mindkettőt hordozza, formátlankezeli és kihagyja, ahelyett, hogy valamelyik értelmezést választaná. Az enumerációs utak, mint az EnumNumTree, elnézőbbek, és mindkettő jelenlétében a /Kids-et követik

Mire hihet el egy olvasó a /Limitsnek?

Egy olvasó a /Limits-nek csak munkamegtakarításért hihet, soha arra, hogy egy kulcs hiányzik, és csak akkor, ha a pár jól formált. A 36. táblázat kimondja, hogy a köztes és levélcsomópontok két elemű /Limits tömböt hordoznak a legkisebb és legnagyobb kulccsal, a gyakorlatban viszont a bejegyzés kézi szerkesztések után eltűnik, számokat tart egy névfában, vagy felcserélt határokkal érkezik. A PDFlibPas v3.539.45-e és v3.539.51-e minden esetet ugyanúgy dönt el: ha a tartomány nem olvasható jó típusú rendezett párként, a gyerek kereshető marad

• Hiányzó /Limits: a régi tartományteszt False-t adott, és a gyerek egy csapásra kimaradt, így egy producer, ami elfelejtette a bejegyzést, az egész alcsomóját elérhetetlenné tette. v3.539.45 óta a gyereket megkeresik
• Rossz típus vagy rossz hossz, például számok egy névfában vagy egyetlen elemű tömb: v3.539.45 óta pontosan úgy kezelik, mint egy hiányzó bejegyzést
• Fordított határok, mint a [(Z) (A)] vagy a [9 0]: a v3.539.45 még használta őket, és egyetlen kulcs sem elégítheti ki a Lo <= Key <= Hi-t, ha Lo > Hi, így az ág minden keresésnél kimaradt. v3.539.51 óta egy tartomány csak akkor szolgál metszésre, ha az alsó határa nem lépi túl a felső határát
• Jól formált, rendezett és helyes: ágkihagyásra használt, ami a bejegyzés értelme

A valódi kulcsok döntik el minden esetben a kimenetet. Egy ellenséges /Limits arra kényszerítheti a PDFlibPast, hogy több csomópontot látogasson a szükségesnél, de egy formátlan már nem tudhat el egy meglévő destinációt. A hívó oldaláról semmi sem változik: a GetNamedDestination 0-t ad, ha a név tényleg hiányzik, egyébként destináció-ID-t, és a destinációfüggvények onnan viszik tovább

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;
    // Előbb a catalog /Dests (PDF 1.1), aztán a /Dests névfa
    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;

Egy kézzel épített fájlon futtatva, aminek a /Dests gyökerének egy gyereke visszaloop a gyökérre egy [(a) (z)] tartomány alatt, a második gyereke pedig a valódi bejegyzést tartja fordított [(z) (a)] limit alatt, ez az eljárás a destinációt a 2. oldalra oldja fel 2-es nézettípussal (Fit). v3.539.45 előtt ugyanez a keresés 0-t adott, mert a loopoló gyerek követelte először a kulcsot, és a keresés sosem érte el a testvérét; a v3.539.45 önmagában is 0-t adott, mert a fordított tartomány kizárta a valódi levelet. Ha utána kiolvasod az outline-t, ami ezekre a destinációkra mutat, a PDF bookmark és annotáció akciók olvasása Delphiben tárgyú társcikk az akció oldalt fedi le

Hogyan törte meg a TPDFNameTree-t egy 32 769 neves levél?

Egy 32 769 név/érték párt hordozó levél megtörte a TPDFNameTree-t, mert a belső FindIndex-e két számot zsúfolt egy 32 bites Integer-be: a levél pozícióját a belső tömblistában a magas 16 bitbe, a bejegyzés offszetjét az adott levél /Names tömbjén belül az alacsony 16 bitbe. Minden pár két tömbhelyet foglal, így a 32 769-edik pár, a 32 768-as pair index, a 65 536-os offszetnél kezdődik, ami $10000. Ez az érték átvitelként átmegy a magas felére, és a dekódoló a következő levél 0-s offszetjeként olvasta vissza

A TPDFNameTree az az osztály, ami a csatolmányok, a globális JavaScript packageek és a nevesített destináció írások mögött áll, ami kézzelfoghatóvá teszi a következményeket. Egyetlen levelű fában nincs következő levél, így a FindKey és a DeleteKey a levéllista vége után indexelt; többlevelű fában a következő levél első párját adták vagy törölték a kért helyett. Közben a HasKey saját átfésülést futtatott, és jelen lévőnek jelezte a kulcsot, így az osztály önmagának ellentmondott. Egy generált referenciakézikönyv API szimbólumonként egy nevesített destinációval kéretlenül átlépi a 32 768 bejegyzést, és egyes producerek mindegyiket egyetlen lapos levélbe írják

v3.539.45 óta a FindIndex a tömbindexet külön out paraméteren át adja, a teljes bejegyzés offszetet pedig eredményként, így egyik érték sem csonkolódik. Ugyanez a kiadás két szomszédját is megszorította. A KeyName mostantól csak valódi string kulcsokat számol és ad vissza, 0-s vagy az alatti indexre üres stringet ad, ahol korábban bármit castolt, ami egy érvénytelen kulcsot követett. A HasKey numerikus vagy más módon érvénytelen kulcsot már nem kezel üres névként. Egy [(Valid) 42 123 456] levélnél a HasKey('') most False, a KeyName(2) pedig üres stringet ad

procedure AuditTrees(const FileName: string);
var
  Lib: TPDFlib;
  I: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile(FileName, '') <> 1 then
      Exit;
    // /PageLabels számfa; a nélkülük érkező fájlok sima oldalszámot adnak
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // /EmbeddedFiles névfa; az indexek 1-alapúak, a nem string kulcsok kimaradnak
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // név, MIME típus
    // /JavaScript névfa: csak package neveket listáz, semmit nem futtat
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

Ugyanazon a kézzel épített fájlon, aminek a /PageLabels gyökere egy levelet kétszer sorol és önmagára hivatkozik, ez az audit i-t és A-1-et ír a két oldalra, tartományonként egyszer, meg az egyetlen script package-et egy /JavaScript fából, ami szintén a saját gyökerére mutat vissza. Az oldalcímkék író oldala is megírta a maga történetét /Kids gyökerekkel, amit a PDF oldalcímkék javítása /Kids számfákban tárolva cikk fed le; az AddPageLabels kilapítja az ilyen gyökeret, mielőtt beszúrná, és ugyanarra az itt leírt EnumNumTree enumerációra épít

Mit nem garantál még ez a megerősítés?

A megerősítés leállást, stabil sorrendet és helyes eredményeket garantál azoknál a fáknál, amiknek a valódi kulcsai épek; nem teszi viszont értelmessé, hogy egy sérült fa azt jelentse, amit a szerzője szánt. Néhány korlát érdemes ismerni, mielőtt ráépítesz

• A meglátogatott halmaz objektumazonossággal dolgozik. Két különböző szótár azonos tartalommal két csomópont, így egy producer, ami lemásolja a levelet hivatkozás helyett, továbbra is dupla bejegyzéseket ad
• Egy jól formált, rendezett, de rossz /Limits továbbra is metsz. Egy olvasó, ami a tartományokat optimalizálásként használja, nem lehet közben immunis egy hihetően hazudó tartományra; az egyetlen alternatíva a /Limits teljes ignorálása és minden levél átfésülése
• Az enumeráció megőrzi a fájsorrendet, de nem rendez. A GetPageLabel az utolsó enumerált, az oldalnál nem nagyobb kezdőindexű tartományt alkalmazza, így egy soron kívül író producer fájsorrend-semantikát kap
• A memória a külön csomópontok és bejegyzések számával nő. A bejárás hozzáad egy listát és egy hash halmazt, többet nem, de egy 100 MB-os névfa parzolás után is 100 MB-os névfa
• Egy levélen belüli dupla kulcsokról nem számol be. A bináris keresés azt az egyező párt adja, amibe előbb beletallál; a lineáris fallback az utolsó megtalált egyezést tartja

Gyorsreferencia: PDF fák olvasása megbízhatatlan fájlokból

• Frissíts v3.539.45-re vagy újabbra ciklus- és verembiztos névfa- és számfabejárásért, v3.539.51-re vagy újabbra pedig azért, hogy a fordított /Limits-ek többé ne rejtsenek el kulcsokat
• A GetNamedDestination 0-ját kezeld „hiányzik"-ként, a GetDestPage 0-ját pedig „jelen van, de használhatatlan"-ként
• A /JavaScript névfához a GlobalJavaScriptCount-ot és a GlobalJavaScriptPackageName-t használd; a GetDocJavaScript ehelyett catalog /AA triggereket olvas
• A csatolmányokat és script packageeket 1-től a library által jelentett darabszámig indexeld; az érvénytelen kulcsok nem számolódnak
• A saját fakódodban jelöld meglátogatottnak a csomópontokat popkor, fordított sorrendben told a gyerekeket, és a /Limits csak akkor metszen, ha jól típusos rendezett pár

Az előellenőrző eszközök, archiválók és nézegetők ezekkel a fákkal találkoznak, mielőtt bármely oldal renderelődne, így túlélniük kell azt, ami egy feltöltési sorba érkezik. A fenti faolvasók a PDFlibPas, a PDF Library for Delphi csomagban érkeznek, ami Delphivel és Free Pascallel egyaránt fordul