Дерева імен PDFlibPas: цикли, /Limits і величезні листки

PDFlibPas, PDF Library для Delphi від losLab, обходить дерева імен та дерева чисел PDF з явним стеком і набором відвіданих з v3.539.45, тож циклічні /Kids, спільні діти та дерева на тисячі рівнів углиб більше не вичерпують стек викликів і не дублюють записи. З v3.539.51 відсутня, деформована чи перевернута пара /Limits ніколи не ховає гілку, що містить ключ. Іменовані призначення, мітки сторінок, вкладення та JavaScript на рівні документа — усе це читається через ті два шляхи коду, що робить їх частиною поверхні атаки будь-якого PDF, який ви не робили самі

Тригер рідко буває екзотичним. Фаззер, ворожа вивантажена заготовка чи багнуване інкрементальне збереження пише запис /Kids, що вказує назад на предка, і рекурсивний обхідник помирає від переповнення стека на файлі завбільшки два кілобайти. Тиха відмова — це пошук, що довіряє зламаному масиву /Limits і звітує «not found» для призначення, яке очевидно є

Де дерева імен і дерева чисел трапляються в PDF?

Дерева імен і дерева чисел трапляються всюди, де PDF мапить велику множину ключів на об'єкти, і PDFlibPas читає принаймні чотири з них через публічні API. ISO 32000-1 §7.9.6 визначає name tree (рядкові ключі, Table 36), а §7.9.7 — number tree (цілочисельні ключі, Table 37). Обидва — майже збалансовані дерева, чиї корінь і проміжні вузли несуть /Kids, чиї листки несуть посортовані пари ключ/значення в /Names чи /Nums, а чиї некореневі вузли несуть двоелементний масив /Limits з найменшим і найбільшим ключами під ними

Дерево	Де живе	Специфікація	API читання PDFlibPas
Іменовані призначення	/Dests у словнику імен	§12.3.2.3	GetNamedDestination, потім GetDestPage / GetDestType
Мітки сторінок	/PageLabels у каталозі (number tree)	§12.4.2	GetPageLabel
Вкладення	/EmbeddedFiles у словнику імен	§7.7.4, §7.11.4	EmbeddedFileCount, GetEmbeddedFileStrProperty
JavaScript на рівні документа	/JavaScript у словнику імен	§7.7.4	GlobalJavaScriptCount, GlobalJavaScriptPackageName

Дві деталі в тій таблиці легко пропустити. Іменовані призначення мають ще й старішу форму PDF 1.1 — звичайний словник /Dests у каталозі з ключами-іменами, — і GetNamedDestination перевіряє той словник першим, перш ніж спускатися деревом імен PDF 1.2. А GetDocJavaScript узагалі не читач дерева імен: він повертає скрипти, прикріплені до тригерів документа в словнику /AA каталогу (WS, DS, WP, DP, DC), тоді як іменовані пакети скриптів, що запускаються при відкритті документа, живуть у дереві імен /JavaScript

Кожен байт тих структур приходить із файлу. Специфікація каже, що письменник зобов'язаний виробити; вона не може завадити читачеві отримати щось інше — той самий урок, що за загартуванням Pascal-парсера PDF проти зловмисних файлів, застосований тут до форми дерева, а не до розмірів буферів

Чому циклічний масив /Kids валить рекурсивного обхідника дерева?

Циклічний масив /Kids валить рекурсивного обхідника тому, що ніщо в рекурсії не помічає, що вузол уже бачено, тож дитина, що згадує власного предка, перетворює скінченний файл на нескінченне падіння вглиб. До v3.539.45 NameTreeLookup, NumTreeLookup, EnumNumTree і внутрішній TPDFNameTree.ProcessNode усі викликали себе по разу на дитину. Одного самозгадування достатньо, щоб убити процес, а легітимне, але дуже глибоке дерево могло зробити те саме без жодного циклу

М'якший варіант псує результати замість падіння. Коли два записи /Kids згадують той самий листок, наївна енумерація відвідує його двічі, і кількість вкладень чи список пакетів скриптів звітує записи, яких не існує

Виправлення замінює рекурсію явним стеком «останнім увійшов — першим вийшов» у купі та набором відвіданих, ключованим тотожністю словника. Вузол позначається, коли його виймають, а не коли кладуть, тож циклічне посилання може посидіти на стеку трохи, але викидається тієї ж миті, коли повертається вгору. Кожен окремий вузол розгортає своїх дітей рівно один раз, що обмежує загальну роботу кількістю окремих словників плюс сумарною довжиною їхніх масивів /Kids. Глибина перестає мати значення: ланцюг на 4 096 рівнів — це просто 4 096 ітерацій циклу і 4 096 записів у хеші

Порядок усе ще важить, і стек треба годувати навпаки, щоб його зберегти. Діти кладуться від останнього індексу до першого, тож найлівіша дитина виймається першою, і листки виходять у тому ж порядку зліва праворуч, у якому їх написав продуцент. GetPageLabel на тому тримається: він проходить кожен енумерований діапазон і застосовує останній, чий стартовий індекс не перевищує сторінку, тож звернення енумерації тихо вручало б сторінці 200 стиль вступних сторінок. Скелет нижче показує шаблон на абстрактному типі вузла, незалежно від будь-якої об'єктної моделі PDF

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // порожній на листку
    Keys: TArray<string>;      // ключі листка, посортовані чемним продуцентом
    Values: TArray<Integer>;   // паралельно до Keys
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// /Limits — це підказка: обрізати гілку може лише добре сформована впорядкована пара
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;                      // цикл чи спільна дитина: вже бачили
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // Кладемо справа ліворуч, щоб лівіша дитина виймалась першою
        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;
      // Промах у цьому листку — не вирок: продовжуємо виймати сусідів
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

Чому пошук не може зупинитися на першій збіжній гілці?

Пошук не може зупинятися на першій гілці, чий діапазон збігається, бо діапазони /Limits у реальному файлі можуть перетинатися чи брехати, і гілка, що заявляє ключ, — не обов'язково гілка, що його тримає. Пошуки до v3.539.45 ставили прапорець Found на першій дитині, чий /Limits покривав ключ, спускалися в неї і більше не дивилися на інших сусідів. Якщо та дитина виявлялася порожньою, застарілою чи петлею назад до кореня, відповіддю було nil, навіть коли найближчий сусід тримав ключ

Переписаний FindTreeValue, який тепер стоїть за обома NameTreeLookup і NumTreeLookup, кладе кожну дитину, чий діапазон не виключає ключ, і продовжує виймати, доки не знайде збіг чи не спорожнить стек. Промах усередині одного листка — це просто промах усередині одного листка. У добре сформованому дереві це не коштує нічого зайвого; у пошкодженому — кількох зайвих відвідувань вузлів і правильної відповіді

Пошук у листку дотримується тієї ж філософії. ISO 32000-1 вимагає, щоб ключі в масиві /Names були посортовані за значенням байтів, тож листок спершу шукається бінарним пошуком. Якщо це не вдається, PDFlibPas падає назад на лінійний прохід пар, бо не впорядкований листок інакше зробив би наявний ключ невидимим. Сортування — це швидкий шлях, а не фільтр

Пошук відмовляється вгадувати ще в одній структурній суперечності. Table 36 дозволяє вузлові нести або /Kids, або /Names, ніколи обидва, і шлях пошуку ставиться до вузла з обома як до деформованого і пропускає його, замість того щоб обирати одну інтерпретацію. Шляхи енумерації, як-от EnumNumTree, поблажливіші та йдуть за /Kids, коли присутні обидва

У що читачеві можна довіряти /Limits?

Читачеві можна довіряти /Limits лише щоб пропускати роботу, ніколи — щоб вирішувати, що ключ відсутній, і лише коли пара добре сформована. Table 36 каже, що проміжні вузли та листки зобов'язані нести /Limits як двоелементний масив найменшого та найбільшого ключів, але на практиці запис зникає після ручних правок, тримає числа в дереві імен чи приходить із переплутаними межами. PDFlibPas v3.539.45 і v3.539.51 розрішують кожен випадок однаково: якщо діапазон не читається як упорядкована пара правильного типу, дитина лишається доступною для пошуку

• Відсутній /Limits: стара перевірка діапазону повертала False і дитина пропускалася цілком, тож продуцент, що забув запис, робив усе своє піддерево недосяжним. З v3.539.45 дитина шукається
• Неправильний тип чи неправильна довжина, як-от числа в дереві імен чи одноелементний масив: трактуються точно як відсутній запис з v3.539.45
• Перевернуті межі, як-от [(Z) (A)] чи [9 0]: v3.539.45 досі їх використовував, а жоден ключ не може задовольнити Lo <= Key <= Hi, коли Lo > Hi, тож гілка виключалася для кожного пошуку. З v3.539.51 діапазон використовується для обрізання лише коли його нижча межа не перевищує верхню
• Добре сформована, впорядкована і правильна: використовується, щоб пропустити гілку — у тому й сенс запису

Справжні ключі вирішують результат у кожному випадку. Ворожий /Limits може змусити PDFlibPas відвідати більше вузлів, ніж треба, але деформований вже не може зробити наявне призначення зниклим. З боку викликача нічого не змінюється: GetNamedDestination повертає 0, коли імені справді немає, і ідентифікатор призначення інакше, а функції призначень беруть його звідти

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;
    // Спершу /Dests каталогу (PDF 1.1), потім дерево імен /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;

Запущений проти рукописного файлу, чий корінь /Dests має одну дитину, що зациклюється назад на корінь під діапазоном [(a) (z)], і другу дитину, що тримає справжній запис під перевернутими лімітами [(z) (a)], ця процедура розрішує призначення на сторінку 2 з типом перегляду 2 (Fit). До v3.539.45 той самий пошук повертав 0, бо зациклена дитина заявляла ключ першою і пошук ніколи не доходив до її сусіда; сам v3.539.45 повертав 0, бо перевернутий діапазон виключав справжній листок. Якщо далі ви читаєте зміст, що вказує на ті призначення, супутня стаття про читання дій закладок і анотацій PDF у Delphi покриває бік дій

Як листок із 32769 іменами зламав TPDFNameTree?

Листок із 32769 парами ім'я/значення зламав TPDFNameTree, бо його внутрішній FindIndex запаковував два числа в один 32-бітовий Integer: позицію листка в внутрішньому списку масивів у старших 16 бітах і зміщення запису всередині масиву /Names того листка в молодших 16 бітах. Кожна пара займає два слоти масиву, тож 32769-та пара, пара з індексом 32768, стартує зі зміщення 65 536, тобто $10000. Те значення перетікає в старшу половину, і декодер читав його назад як зміщення 0 у наступному листку

TPDFNameTree — клас за вкладеннями, глобальними пакетами JavaScript і записами іменованих призначень, що робить наслідки конкретними. В одноклистковому дереві наступного листка немає, тож FindKey і DeleteKey індексували за кінець списку листків; у багатолистковому вони повертали чи видаляли першу пару наступного листка замість запитаної. Тим часом HasKey ганяв власний прохід і звітував ключ як наявний, тож клас суперечив сам собі. Згенерований довідник з одним іменованим призначенням на символ API переступає 32768 записів без жодного зусилля, а деякі продуценти пишуть усі їх в один плоский листок

З v3.539.45 FindIndex повертає індекс масиву через окремий параметр out, а повне зміщення запису — як свій результат, тож жодне значення не обрізається. Той самий реліз підтив два сусіди. KeyName тепер лічити і повертає лише справжні рядкові ключі і повертає порожній рядок для індексу 0 чи нижче, де раніше кастав усе, що йшло за недійсним ключем. HasKey більше не трактує числовий чи інший недійсний ключ як порожнє ім'я. Для листка на кшталт [(Valid) 42 123 456] HasKey('') тепер False, а KeyName(2) повертає порожній рядок

procedure AuditTrees(const FileName: string);
var
  Lib: TPDFlib;
  I: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile(FileName, '') <> 1 then
      Exit;
    // Дерево чисел /PageLabels; файли без нього повертають голі номери сторінок
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // Дерево імен /EmbeddedFiles; індекси з 1, нестрокові ключі пропускаються
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // ім'я, MIME-тип
    // Дерево імен /JavaScript: перелічуємо імена пакетів, нічого не виконуємо
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

На тому самому рукописному файлі, чий корінь /PageLabels перелічує один листок двічі і згадує сам себе, цей аудит друкує i та A-1 для двох сторінок, кожен діапазон по одному разу, і єдиний пакет скриптів із дерева /JavaScript, що теж вказує на власний корінь. Записуваний бік міток сторінок має власну історію з коренями /Kids, описану в полагодженні міток сторінок PDF, збережених у деревах чисел /Kids; AddPageLabels розплющує такий корінь перед вставлянням і спирається на ту саму енумерацію EnumNumTree, описану тут

Чого це загартування досі не гарантує?

Загартування гарантує зупинення, стабільний порядок і правильні результати для дерев, чиї справжні ключі неушкоджені; воно не робить пошкоджене дерево таким, що означає задум його автора. Кілька меж варто знати, перш ніж будувати на ньому

• Набір відвіданих працює за тотожністю об'єктів. Два різні словники з однаковим вмістом — це два вузли, тож продуцент, що копіює листок замість згадування, досі дає дубльовані записи
• Добре сформований, впорядкований, але неправдивий /Limits досі обрізає. Читач, що користується діапазонами як оптимізацією, не може водночас бути неуразливим до діапазону, який правдоподібно бреше; єдина альтернатива — ігнорувати /Limits цілком і сканувати кожен листок
• Енумерація зберігає порядок файлу, але не сортує. GetPageLabel застосовує останній енумерований діапазон, не вищий за сторінку, тож продуцент, що пише діапазони безладно, отримує семантику порядку файлу
• Пам'ять зростає з кількістю окремих вузлів і записів. Обхід додає список і хеш, нічого більше, але дерево імен на 100 МБ досі є деревом імен на 100 МБ після розбору
• Дубльовані ключі всередині одного листка не звітуються. Бінарний пошук повертає яку завгодно збіжну пару, на яку натрапить першою; лінійний фолбек тримає останній збіг, який пройшов

Шпаргалка: читання дерев PDF із недовірених файлів

• Оновіться до v3.539.45 чи новішої заради обходу дерев імен та чисел, безпечного щодо циклів і стека, і до v3.539.51 чи новішої, щоб перевернуті /Limits більше не ховали ключі
• Трактуйте GetNamedDestination, що повернув 0, як «відсутнє», а GetDestPage, що повернув 0, як «наявне, але непридатне»
• Користуйтеся GlobalJavaScriptCount і GlobalJavaScriptPackageName для дерева імен /JavaScript; GetDocJavaScript натомість читає тригери каталогу /AA
• Індексуйте вкладення та пакети скриптів від 1 до кількості, яку звітує бібліотека; недійсні ключі не лічаться
• У власному деревному коді позначайте вузли відвіданими при вийманні, кладіть дітей у зворотному порядку і дозволяйте /Limits обрізати лише коли це добре типізована впорядкована пара

Pre-flight інструменти, архіватори та переглядачі читають ці дерева до того, як відрендериться хоч одна сторінка, тож їм доводиться виживати з усім, що прибуває у черзі вивантажень. Читачі дерев, описані вище, постачаються з PDFlibPas, PDF Library для Delphi, яка збирається і Delphi, і Free Pascal