PDFlibPas-nimipuut: syklit, huonot /Limits ja jättilehdet

PDFlibPas, losLabin PDF Library for Delphi, kulkee PDF:n nimipuut ja numeropuut läpi eksplisiittisellä pinolla ja käytyjen solmujen joukolla versiosta v3.539.45 alkaen, joten sykliset /Kidst, jaetut lapset ja tuhansien tasojen syvyiset puut eivät enää kuluta kutsupinoa eivätkä monista merkintöjä. Versiosta v3.539.51 alkaen puuttuva, epäkelpo tai käänteinen /Limits-pari ei koskaan kätke haaraa, joka pitää avaimen hallussaan. Nimetyt kohteet, sivunimikkeet, liitteet ja asiakirjatason JavaScript lukevat kaikkien näiden kahden koodipolun kautta, mikä tekee niistä osan hyökkäyspintaa missä tahansa PDF:ssä, jota et ole itse tuottanut

Laukaisija on harvoin eksoottinen. Fuzzer, vihamielinen lähetys tai buginen inkrementaalinen tallennus kirjoittaa /Kids-merkinnän, joka osoittaa takaisin esivanhempaan, ja rekursiivinen kulkija kuolee pinoylivuotoon kaksikilotavuisessa tiedostossa. Hiljaisempi vika on haku, joka luottaa rikkinäiseen /Limits-taulukkoon ja raportoi "ei löytynyt" kohteelle, joka on selvästi paikallaan

Missä nimipuut ja numeropuut ilmestyvät PDF:ssä?

Nimipuut ja numeropuut ilmestyvät siellä, missä PDF kytkee suuren avainjoukon objekteihin, ja PDFlibPas lukee vähintään neljää niistä julkisten API:jen kautta. ISO 32000-1 §7.9.6 määrittelee nimipuun (merkkijonoavaimet, taulukko 36) ja §7.9.7 numeropuun (kokonaislukuavaimet, taulukko 37). Molemmat ovat suunnilleen tasapainotettuja puita, joiden juuressa ja välisolmuissa on /Kids, joiden lehdissä on lajitellut avain/arvo-parit muodossa /Names tai /Nums ja joiden ei-juurisolmuissa on kaksielementtinen /Limits-taulukko, jossa on pienin ja suurin avain niiden alla

Puu	Missä se asuu	Määrittely	PDFlibPas-luku-API
Nimetyt kohteet	/Dests nimisanakirjassa	§12.3.2.3	GetNamedDestination, sitten GetDestPage/GetDestType
Sivunimikkeet	/PageLabels katalogissa (numeropuu)	§12.4.2	GetPageLabel
Liitteet	/EmbeddedFiles nimisanakirjassa	§7.7.4, §7.11.4	EmbeddedFileCount, GetEmbeddedFileStrProperty
Asiakirjatason JavaScript	/JavaScript nimisanakirjassa	§7.7.4	GlobalJavaScriptCount, GlobalJavaScriptPackageName

Kaksi yksityiskohtaa kyseisessä taulukossa on helppo ohittaa. Nimetyillä kohteilla on myös vanhempi PDF 1.1 -muoto, pelkkä /Dests-sanakirja katalogissa avaimennettuna nimiobjekteilla, ja GetNamedDestination tarkistaa kyseisen sanakirjan ensin ennen kuin laskeutuu PDF 1.2:n nimipuuhun. Ja GetDocJavaScript ei ole nimipuun lukija yhtään: se palauttaa asiakirjan laukaisimiin kiinnitetyt skriptit katalogin /AA-sanakirjassa (WS, DS, WP, DP, DC), kun taas nimetyt skriptipaketit, jotka suoritetaan, kun asiakirja avautuu, asuvat /JavaScript-nimipuussa

Jokainen kyseisten rakenteiden tavu tulee tiedostosta. Määrittely sanoo, mitä kirjoittajan on tuotettava; se ei voi estää lukijaa vastaanottamasta jotain muuta, mikä on sama oppi kuin artikkelin Pascal-PDF-jäsentimen kovettaminen haitallisia tiedostoja vastaan takana, sovellettuna täällä puun muotoon puskurikokojen sijaan

Miksi syklinen /Kids-taulukko kaataa rekursiivisen puukulkijan?

Syklinen /Kids-taulukko kaataa rekursiivisen kulkijan, koska mikään rekursiossa ei huomaa nähneensä solmua aiemmin, joten lapsi, joka viittaa omaan esivanhempaansa, kääntää äärellisen tiedoston äärettömäksi laskeutumiseksi. Ennen v3.539.45 NameTreeLookup, NumTreeLookup, EnumNumTree ja sisäinen TPDFNameTree.ProcessNode kutsuivat kaikkia itseään kerran lasta kohden. Yksi itsensä viittaus riitti lopettamaan prosessin, ja laillinen mutta hyvin syvä puu saattoi tehdä saman ilman mitään sykliä

Lievempi muunnelma turmelee tuloksia kaatumisen sijaan. Kun kaksi /Kids-merkintää viittaa samaan lehteen, naiivi läpikäynti vierailee siinä kahdesti, ja liitelaskuri tai skriptipakettien luettelo raportoi merkintöjä, joita ei ole olemassa

Korjaus vaihtaa rekursion eksplisiittiseen pinoon, joka on keossa oleva last-in, first-out -pino, ja käytyjen solmujen joukkoon, joka on avaimennettu sanakirjan identiteetillä. Solmu merkitään, kun se ponnahtaa ulos, ei silloin, kun se työnnetään sisään, joten syklinen viittaus saattaa istua pinossa hetken mutta hylätään sillä hetkellä, kun se nousee takaisin ylös. Jokainen erillinen solmu laajentaa lapsensa täsmälleen kerran, mikä rajoittaa kokonaistyön erillisten sanakirjojen määrään plus niiden /Kids-taulukoiden kokonaispituuteen. Syvyys lakkaa merkitsemästä: 4 096 tason ketju on vain 4 096 silmukan kierrosta ja 4 096 merkintää hajautusjoukossa

Järjestys merkitsee silti yhä, ja pino on syötettävä takaperin sen säilyttämiseksi. Lapset työnnetään viimeisestä indeksistä ensimmäiseen, joten vasemmanpuoleisin lapsi ponnahtaa ulos ensin ja lehdet tulevat ulos samassa vasemmalta oikealle -järjestyksessä, jossa tuottaja ne kirjoitti. GetPageLabel riippuu siitä: se käy jokaisen luetellun välin läpi ja soveltaa viimeistä, jonka aloitusindeksi on sivussa tai sen alapuolella, joten läpikäynnin kääntäminen antaisi hiljaisesti sivulle 200 etutekstin tyylin. Alla oleva luuranko näyttää kaavan abstraktilla solutyypillä, riippumatta mistään PDF-objektimallista

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // tyhjä lehdessä
    Keys: TArray<string>;      // lehden avaimet, hyvin käyttäytyvän tuottajan lajittelemat
    Values: TArray<Integer>;   // samassa järjestyksessä kuin Keys
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// /Limits on vihje: vain hyvin muodostettu, järjestetty pari saa karsia haaran
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;                      // sykli tai jaettu lapsi: nähty
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // Työnnä oikealta vasemmalle, joten vasemmanpuoleisin lapsi ponnahtaa ensin
        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;
      // Osumatta jääminen tässä lehdessä ei ole tuomio: jatka sisarusten käsittelyä
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

Miksi haku ei voi pysähtyä ensimmäiseen osuvaan haaraan?

Haku ei voi pysähtyä ensimmäiseen haaraan, jonka väli osuu, koska todellisen tiedoston /Limits-välit voivat mennä päällekkäin tai valehdella, eikä haara, joka vaatii avaimen itselleen, ole välttämättä haara, joka pitää sen hallussaan. Ennen v3.539.45 olleet haut asettivat Found-flagin ensimmäiselle lapselle, jonka /Limits kattoi avaimen, laskeutuivat siihen eivätkä koskaan katsoineet toista sisarta. Jos kyseinen lapsi osoittautui tyhjäksi, vanhentuneeksi tai juureen takaisin kiertäväksi, vastaus oli nil, vaikka heti seuraava sisar pitikin avainta

Uudelleenkirjoitettu FindTreeValue, joka tukee nykyään sekä NameTreeLookupia että NumTreeLookupia, työntää jokaisen lapsen, jonka väli ei sulje avainta pois, ja jatkaa ponnahduksia, kunnes löytää osuman tai tyhjentää pinon. Osumatta jääminen yhden lehden sisällä on vain osumatta jäämistä yhden lehden sisällä. Hyvin muodostetussa puussa tämä ei maksa mitään ylimääräistä; vaurioituneessa se maksaa muutaman solmuvierailun lisää ja palauttaa oikean vastauksen

Lehden haku noudattaa samaa filosofiaa. ISO 32000-1 vaatii /Names-taulukon avainten olevan lajiteltuja tavuarvon mukaan, joten lehti haetaan ensin binäärihaulla. Jos se epäonnistuu, PDFlibPas palaa parien lineaariseen läpikäyntiin, koska järjestyksetön lehti tekisi muuten läsnä olevan avaimen näkymättömäksi. Lajittelu on nopea polku, ei suodatin

Haku kieltäytyy myös arvaamasta yhden rakenteellisen ristiriidan kohdalla. Taulukko 36 antaa solmun kantaa joko /Kids tai /Names, ei koskaan molempia, ja hakupolku käsittelee molemmat kantavan solmun epäkelpona ja ohittaa sen yhden tulkinnan poimimisen sijaan. Läpikäyntipolut kuten EnumNumTree ovat sallivaisempia ja seuraavat /Kidsia, kun molemmat ovat läsnä

Mihin lukija saa luottaa /Limitsin kohdalla?

Lukija saa luottaa /Limitsiin vain työn ohittamisessa, ei koskaan siinä, että avain on poissa, ja vain silloin, kun pari on hyvin muodostettu. Taulukko 36 sanoo, että välisolmujen ja lehtien on kannettava /Limitsia kaksielementtisenä taulukkona pienimmästä ja suurimmasta avaimesta, mutta käytännössä merkintä katoaa käsimuokkausten jälkeen, pitää numeroita nimipuussa tai saapuu rajansa vaihtaneena. PDFlibPas v3.539.45 ja v3.539.51 ratkaisevat jokaisen tapauksen samalla tavalla: jos väliä ei voi lukea oikean tyypin järjestettynä parina, lapsi pysyy haettavana

• Puuttuva /Limits: vanha välitarkistus palautti False ja lapsi ohitettiin suoraan, joten merkinnän unohtanut tuottaja teki koko alipuunsa tavoittamattomaksi. Versiosta v3.539.45 alkaen lapsi haetaan
• Väärä tyyppi tai väärä pituus, kuten numerot nimipuussa tai yhden elementin taulukko: käsitellään täsmälleen puuttuvan merkinnän tavoin versiosta v3.539.45 alkaen
• Käänteiset rajat kuten [(Z) (A)] tai [9 0]: v3.539.45 käytti niitä yhä, eikä mikään avain voi täyttää ehtoa Lo <= Key <= Hi, kun Lo > Hi, joten haara suljettiin pois jokaisesta hausta. Versiosta v3.539.51 alkaen väliä käytetään karsimiseen vain, kun sen alaraja ei ylitä ylärajaa
• Hyvin muodostettu, järjestetty ja oikea: käytetään haaran ohittamiseen, mikä on koko merkinnän tarkoitus

Todelliset avaimet ratkaisevat lopputuloksen jokaisessa tapauksessa. Vihamielinen /Limits voi saada PDFlibPasin vierailemaan enemmässä solmuissa kuin on tarpeen, mutta epäkelpo ei voi enää saada olemassa olevaa kohdetta katoamaan. Kutsujan näkökulmasta mikään ei muutu: GetNamedDestination palauttaa arvon 0, kun nimi aidosti on poissa, ja muuten kohteen tunnisteen, ja kohdefunktiot vievät asian siitä eteenpäin

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;
    // Ensin katalogin /Dests (PDF 1.1), sitten /Dests-nimipuu
    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;

Ajettaessa käsin rakennettua tiedostoa vasten, jonka /Dests-juuressa on yksi lapsi, joka kiertää takaisin juureen välin [(a) (z)] alla, ja toinen lapsi, joka pitää todellista merkintää käänteisten [(z) (a)]-rajojen alla, kyseinen menettely ratkaisee kohteen sivulle 2 näkymätyypillä 2 (Fit). Ennen v3.539.45:ää sama haku palautti arvon 0, koska kiertävä lapsi vaati avaimen ensin eikä haku koskaan ylettynyt sen sisarelle; pelkkä v3.539.45 palautti yhä arvon 0, koska käänteinen väli sulki todellisen lehden pois. Jos luet sitten sisällysluettelon, joka osoittaa näihin kohteisiin, artikkeli PDF-kirjanmerkkien ja annotaatioiden toimintojen lukeminen Delphissä kattaa toimintopuolen

Miten 32 769 nimen lehti rikkoi TPDFNameTree:n?

Lehti, jossa on 32 769 nimi/arvo-paria, rikkoi TPDFNameTreen, koska sen sisäinen FindIndex pakkasi kaksi lukua yhteen 32-bittiseen Integeriin: lehden sijainnin sisäisessä taulukkoluettelossa ylempään 16 bittiin ja merkinnän siirtymän kyseisen lehden /Names-taulukon sisällä alempaan 16 bittiin. Jokainen pari vie kaksi taulukkopaikkaa, joten 32 769. pari, pari-indeksi 32 768, alkaa siirtymästä 65 536, joka on $10000. Kyseinen arvo kantautuu ylempään puolikkaaseen, ja dekooderi luki sen takaisin siirtymänä 0 seuraavassa lehdessä

TPDFNameTree on luokka liitteiden, globaalien JavaScript-pakettien ja nimettyjen kohteiden kirjoitusten takana, mikä tekee seurauksista konkreettiset. Yksilehtisessä puussa ei ole seuraavaa lehteä, joten FindKey ja DeleteKey indeksoivat lehtiluettelon lopun yli; monilehtisessä puussa ne palauttivat tai poistivat seuraavan lehden ensimmäisen parin pyydetyn sijaan. Samaan aikaan HasKey ajoi oman läpikäyntinsä ja raportoi avaimen läsnäolevaksi, joten luokka oli ristiriidassa itsensä kanssa. Generoitu referenssimanuaali, jossa on yksi nimetty kohde API-symbolia kohden, ylittää 32 768 merkintää yrittämättä, ja jotkut tuottajat kirjoittavat kaikki yhteen litteään lehteen

Versiosta v3.539.45 alkaen FindIndex palauttaa taulukkoindeksin erillisen out-parametrin kautta ja koko merkinnän siirtymän tuloksenaan, joten kumpikaan arvo ei katkea. Sama julkaisu kiristi kaksi naapuria. KeyName laskee nykyään ja palauttaa vain aitoja merkkijonoavaimia ja palauttaa tyhjän merkkijonon indeksille 0 tai sen alle, missä se aiemmin valoi mitä tahansa virheellisen avaimen jälkeistä objektia. HasKey ei enää käsittele numeerista tai muuten virheellistä avainta tyhjänä nimenä. Lehdelle kuten [(Valid) 42 123 456] HasKey('') on nyt False ja KeyName(2) palauttaa tyhjän merkkijonon

procedure AuditTrees(const FileName: string);
var
  Lib: TPDFlib;
  I: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile(FileName, '') <> 1 then
      Exit;
    // /PageLabels-numeropuu; tiedostot ilman sitä palauttavat tavalliset sivunumerot
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // /EmbeddedFiles-nimipuu; indeksit 1-pohjaisia, ei-merkkijonoavaimet ohitetaan
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // nimi, MIME-tyyppi
    // /JavaScript-nimipuu: luetteloi pakettien nimet, älä suorita mitään
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

Samalla käsintehdyllä tiedostolla, jonka /PageLabels-juuri luetteloi yhden lehden kahdesti ja viittaa itseensä, kyseinen tarkistus tulostaa i ja A-1 kahdelle sivulle, jokaisen välin kerran, ja ainoan skriptipaketin /JavaScript-puusta, joka myös osoittaa takaisin omaan juureensa. Sivunimikkeiden kirjoituspuolella on oma historiansa /Kids-juurten kanssa, joka käsitellään artikkelissa /Kids-numeropuihin talletettujen PDF-sivunimikkeiden korjaaminen; AddPageLabels litistää tällaisen juuren ennen lisäämistä, ja se nojaa samaan tässä kuvattuun EnumNumTree-läpikäyntiin

Mitä tämä kovettaminen yhä ei takaa?

Kovettaminen takaa terminoinnin, vakaan järjestyksen ja oikeat tulokset puille, joiden todelliset avaimet ovat ehjät; se ei tee vaurioituneesta puusta sitä, mitä sen tekijä aikoi. Useita rajoja on syytä tuntea ennen kuin rakennat sen varaan

• Käytyjen solmujen joukko toimii objekti-identiteetillä. Kaksi erillistä sanakirjaa, joiden sisältö on identtinen, on kaksi solmua, joten lehden kopioiva tuottaja sen viittaamisen sijaan tuottaa yhä kaksoismerkintöjä
• Hyvin muodostettu, järjestetty mutta väärä /Limits karsii yhä. Lukija, joka käyttää välejä optimointina, ei voi samalla olla immuuni uskottavasti valehtelevalle välille; ainoa vaihtoehto on ohittaa /Limits kokonaan ja käydä jokainen lehti läpi
• Läpikäynti säilyttää tiedostojärjestyksen mutta ei lajittele. GetPageLabel soveltaa viimeisimmän luetellun välin sivussa tai sen alapuolella, joten järjestyksettömiä välejä kirjoittava tuottaja saa tiedostojärjestyksen semantiikan
• Muisti kasvaa erillisten solmujen ja merkintöjen määrän mukana. Läpikäynti lisää luettelon ja hajautusjoukon, ei mitään muuta, mutta 100 MB:n nimipuu on yhä 100 MB:n nimipuu jäsennyksen jälkeen
• Kaksoisavaimia yhden lehden sisällä ei raportoida. Binäärihaku palauttaa sen osuvan parin, johon se osuu ensin; lineaarinen varapolku pitää viimeisimmän läpikäymänsä osuman

Pikaopas: PDF-puiden lukeminen epäluotettavista tiedostoista

• Päivitys versioon v3.539.45 tai uudempaan sykliturvallista, pinoturvallista nimipuiden ja numeropuiden läpikäyntiä varten, ja versioon v3.539.51 tai uudempaan, jotta käänteinen /Limits ei enää kätke avaimia
• Käsittele GetNamedDestinationin palauttama arvo 0 "poissa olevana" ja GetDestPagein palauttama arvo 0 "läsnä mutta käyttokelvottomana"
• Käytä funktioita GlobalJavaScriptCount ja GlobalJavaScriptPackageName /JavaScript-nimipuuhun; GetDocJavaScript lukee sen sijaan katalogin /AA-laukaisimia
• Indeksoi liitteet ja skriptipaketit arvosta 1 kirjaston raportoimaan määrään; virheellisiä avaimia ei lasketa
• Omassa puukoodissasi merkitse solmut käydyksi ponnahduksessa, työnnä lapset käänteisessä järjestyksessä ja anna /Limitsin karsia vain, kun se on hyvin tyypitetty, järjestetty pari

Esitarkistustyökalut, arkistoijat ja katseluohjelmat lukevat kyseiset puut ennen kuin yksikään sivu on renderöitynyt, joten niiden on selviydyttävä kaikesta, mitä latausjonoon saapuu. Yllä kuvatut puiden lukijat toimitetaan mukana paketissa PDFlibPas, PDF Library for Delphi, joka kääntyy sekä Delphillä että Free Pascalilla