Name tree của PDFlibPas: cycle, /Limits lỗi và leaf lớn

PDFlibPas, PDF Library for Delphi của losLab, đi qua name tree và number tree PDF bằng một stack tường minh cùng một tập visited kể từ v3.539.45, nên /Kids tạo cycle, các con dùng chung và những cây sâu hàng nghìn tầng không còn làm cạn call stack hay nhân đôi entry. Kể từ v3.539.51, một cặp /Limits thiếu, hỏng dạng hay đảo ngược không bao giờ giấu được một nhánh đang giữ key. Named destination, page label, attachment và JavaScript cấp tài liệu đều đọc qua hai đường code này, biến chúng thành một phần của bề mặt tấn công đối với bất kỳ PDF nào bạn không tự sinh ra

Thứ kích hoạt hiếm khi kỳ lạ. Một fuzzer, một bản upload có chủ địch hay một lần lưu tăng dần bị lỗi viết ra một entry /Kids trỏ ngược về tổ tiên, và một walker đệ quy chết vì stack overflow trên một tệp hai kilobyte. Cái thất bại êm hơn là một phép tra tin vào mảng /Limits hỏng và báo "không tìm thấy" với một destination đang nằm rõ ràng ngay đó

Name tree và number tree xuất hiện ở đâu trong một PDF?

Name tree và number tree xuất hiện ở bất kỳ chỗ nào PDF ánh xạ một tập key lớn sang các object, và PDFlibPas đọc ít nhất bốn chỗ như vậy qua các API public. ISO 32000-1 §7.9.6 định nghĩa name tree (key kiểu string, Bảng 36) và §7.9.7 định nghĩa number tree (key kiểu số nguyên, Bảng 37). Cả hai đều là những cây xấp xỉ cân bằng, node gốc và node trung gian mang /Kids, leaf mang các cặp key/giá trị đã sắp thứ tự trong /Names hay /Nums, còn các node không phải gốc mang một mảng /Limits hai phần tử với key nhỏ nhất và lớn nhất bên dưới

Cây	Nơi nằm	Đặc tả	API đọc của PDFlibPas
Named destination	/Dests trong name dictionary	§12.3.2.3	GetNamedDestination, rồi GetDestPage / GetDestType
Page label	/PageLabels trong catalog (number tree)	§12.4.2	GetPageLabel
Attachment	/EmbeddedFiles trong name dictionary	§7.7.4, §7.11.4	EmbeddedFileCount, GetEmbeddedFileStrProperty
JavaScript cấp tài liệu	/JavaScript trong name dictionary	§7.7.4	GlobalJavaScriptCount, GlobalJavaScriptPackageName

Hai chi tiết trong bảng ấy dễ bị bỏ qua. Named destination còn có một dạng cũ thời PDF 1.1, một dictionary /Dests thuần trong catalog đánh khóa bằng các name object, và GetNamedDestination kiểm tra dictionary đó trước rồi mới đi xuống name tree của PDF 1.2. Còn GetDocJavaScript chẳng phải một trình đọc name tree: nó trả về các script gắn vào document trigger trong dictionary /AA của catalog (WS, DS, WP, DP, DC), trong khi các script package có tên chạy khi tài liệu mở lại nằm trong name tree /JavaScript

Từng byte của những cấu trúc ấy đều đến từ tệp. Đặc tả nói writer phải sản xuất ra gì; nó không thể cản một reader nhận phải thứ khác — cùng một bài học đằng sau việc gia cố parser PDF Pascal trước tệp độc hại, áp dụng ở đây cho hình dạng cây thay vì kích thước buffer

Vì sao một mảng /Kids tạo cycle làm sập tree walker đệ quy?

Một mảng /Kids tạo cycle làm sập walker đệ quy vì chẳng gì trong đệ quy nhận ra nó đã từng gặp node này, nên một con trỏ về chính tổ tiên của nó biến một tệp hữu hạn thành một cuộc lặn vô tận. Trước v3.539.45, NameTreeLookup, NumTreeLookup, EnumNumTree và TPDFNameTree.ProcessNode nội bộ đều tự gọi mình một lần mỗi con. Một tham chiếu tự thân duy nhất đã đủ để kết thúc tiến trình, và một cây hợp lệ nhưng rất sâu cũng làm được điều tương tự mà chẳng cần cycle nào

Một biến thể dịu hơn thì làm hỏng kết quả thay vì sập. Khi hai entry /Kids tham chiếu cùng một leaf, một phép liệt kê ngây thơ ghé nó hai lần, và một con đếm attachment hay một danh sách script package báo các entry không tồn tại

Bản sửa thay đệ quy bằng một stack vào-sau-ra-trước tường minh trên heap cùng một tập visited đánh khóa bằng định danh dictionary. Một node được đánh dấu khi nó được lấy ra, không phải khi được đẩy vào, nên một tham chiếu cycle có thể ngồi trên stack một lát nhưng bị vứt ngay khoảnh khắc nó nổi lên trở lại. Mỗi node phân biệt trải con của mình đúng một lần, chặn tổng công việc bằng số dictionary phân biệt cộng tổng độ dài các mảng /Kids của chúng. Độ sâu ngừng có ý nghĩa: một chuỗi 4.096 tầng chỉ là 4.096 vòng lặp và 4.096 entry trong một hash set

Thứ tự vẫn quan trọng đấy, và stack phải được nạp ngược để giữ nó. Các con được đẩy vào từ chỉ số cuối xuống chỉ số đầu, nên con ngoài cùng bên trái được lấy ra trước và các leaf ra theo cùng trật tự trái-sang-phải mà producer đã viết. GetPageLabel dựa vào đúng chuyện đó: nó đi qua mọi dải đã liệt kê và áp dải cuối cùng có chỉ số bắt đầu tại hoặc dưới số trang, nên đảo chiều phép liệt kê sẽ lặng lẽ trao cho trang 200 kiểu style của phần mở đầu. Bộ khung dưới đây minh họa mẫu này trên một kiểu node trừu tượng, không dính dáng tới mô hình object PDF nào

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // rỗng ở leaf
    Keys: TArray<string>;      // các key của leaf, do producer đứng đắn sắp thứ tự
    Values: TArray<Integer>;   // song song với Keys
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// /Limits chỉ là gợi ý: chỉ một cặp có dạng đúng, có thứ tự mới được cắt nhánh
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;                      // cycle hoặc con dùng chung: đã gặp
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // Đẩy từ phải sang trái để kid ngoài cùng bên trái được lấy ra trước
        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;
      // Trượt trong leaf này chưa phải phán quyết: cứ lấy tiếp các anh em
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

Vì sao một phép tra không thể dừng ở nhánh khớp đầu tiên?

Một phép tra không thể dừng ở nhánh đầu tiên có dải khớp, vì các dải /Limits trong tệp thật có thể chồng lên nhau hoặc nói dối, và nhánh đòi key chưa chắc là nhánh giữ key. Các phép tra trước v3.539.45 đặt flag Found lên con đầu tiên có /Limits phủ key, lao xuống đó, và chẳng bao giờ nhìn thêm anh em nào khác. Nếu con đó hóa ra rỗng, cũ kỹ hay là một vòng quay về gốc, câu trả lời là nil, dù anh em kế bên đang giữ key

FindTreeValue viết lại, nay đỡ cả NameTreeLookup lẫn NumTreeLookup, đẩy vào mọi con có dải không loại trừ key và lấy ra mãi cho tới khi tìm được chỗ khớp hoặc cạn stack. Trượt trong một leaf chỉ là trượt trong một leaf. Trên cây có dạng đúng, chuyện này không tốn thêm gì; trên cây hỏng, nó tốn vài lần ghé node nữa và trả về câu trả lời đúng

Tìm trong leaf theo đúng triết lý ấy. ISO 32000-1 đòi các key trong mảng /Names phải được sắp theo giá trị byte, nên leaf được tìm bằng binary search trước. Nếu thất bại, PDFlibPas quay về quét tuyến tính các cặp, vì một leaf lệch thứ tự nếu không sẽ biến một key đang tồn tại thành vô hình. Sắp thứ tự là đường tắt, không phải bộ lọc

Phép tra cũng từ chối đoán mò ở một mâu thuẫn cấu trúc. Bảng 36 cho một node mang hoặc /Kids hoặc /Names, không bao giờ cả hai, và đường tra coi node mang cả hai là hỏng dạng rồi bỏ qua nó thay vì chọn một cách hiểu. Các đường liệt kê như EnumNumTree khoan dung hơn và bám /Kids khi cả hai cùng có mặt

Reader có thể tin /Limits cho việc gì?

Reader chỉ được tin /Limits để bỏ bớt công việc, không bao giờ được tin để kết luận key vắng mặt, và chỉ khi cặp giá trị có dạng đúng. Bảng 36 nói node trung gian và node leaf phải mang /Limits là mảng hai phần tử gồm key nhỏ nhất và lớn nhất, nhưng trên thực tế entry mất tích sau các lần sửa tay, chứa số trong một name tree, hoặc tới nơi với hai biên đảo cho nhau. PDFlibPas v3.539.45 và v3.539.51 xử lý từng trường hợp theo cùng một kiểu: nếu dải không đọc được thành một cặp có thứ tự đúng kiểu, con vẫn tiếp tục được tìm

• /Limits mất tích: phép kiểm dải cũ trả về False và con bị bỏ qua thẳng tay, nên một producer quên entry đã biến cả cây con của mình thành không với tới. Kể từ v3.539.45, con được tìm kiếm
• Sai kiểu hay sai độ dài, như chứa số trong name tree hay mảng một phần tử: xử lý y hệt entry mất tích kể từ v3.539.45
• Biên đảo như [(Z) (A)] hay [9 0]: v3.539.45 vẫn dùng chúng, và chẳng key nào thỏa Lo <= Key <= Hi khi Lo > Hi, nên nhánh bị loại với mọi phép tra. Kể từ v3.539.51, một dải chỉ được dùng để cắt nhánh khi biên dưới không vượt biên trên
• Có dạng đúng, có thứ tự và chính xác: được dùng để bỏ nhánh, vốn là toàn bộ ý nghĩa của entry

Các key thật quyết định kết quả trong mọi trường hợp. Một /Limits chủ địch có thể khiến PDFlibPas ghé nhiều node hơn cần, nhưng một entry hỏng dạng không còn biến mất được một destination đang tồn tại. Từ phía người gọi, không gì đổi: GetNamedDestination trả về 0 khi cái tên thật sự vắng mặt và một destination ID trong các trường hợp khác, còn các hàm destination lo phần còn lại

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 trong catalog (PDF 1.1) trước, rồi tới 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;

Chạy trên một tệp dựng tay mà gốc /Dests có một con quay vòng về gốc trong dải [(a) (z)] và một con thứ hai giữ entry thật trong giới hạn bị đảo [(z) (a)], thủ tục này phân giải destination về trang 2 với view type 2 (Fit). Trước v3.539.45, cùng phép tra ấy trả về 0, vì con quay vòng đòi key trước và phép tìm chẳng bao giờ chạm tới anh em của nó; riêng v3.539.45 vẫn trả về 0, vì dải bị đảo loại trừ leaf thật. Nếu bạn sau đó đọc phần outline trỏ tới các destination này, bài đồng hành về đọc action của bookmark và annotation PDF trong Delphi đề cập phần action

Một leaf với 32.769 cái tên đã phá TPDFNameTree thế nào?

Một leaf với 32.769 cặp tên/giá trị đã phá TPDFNameTree vì FindIndex nội bộ của nó nhồi hai con số vào một Integer 32-bit: vị trí của leaf trong danh sách mảng nội bộ nằm ở 16 bit cao, còn offset entry trong mảng /Names của leaf ấy nằm ở 16 bit thấp. Mỗi cặp chiếm hai slot mảng, nên cặp thứ 32.769 — cặp chỉ số 32.768 — bắt đầu tại offset 65.536, tức $10000. Giá trị ấy tràn sang nửa cao, và decoder đọc lại nó thành offset 0 ở leaf kế tiếp

TPDFNameTree là class đứng sau attachment, script package toàn cục và việc ghi named destination, điều khiến hậu quả trở nên cụ thể. Trên cây một leaf thì không có leaf kế tiếp, nên FindKey và DeleteKey truy cập vượt qua cuối danh sách leaf; trên cây nhiều leaf, chúng trả về hoặc xóa cặp đầu tiên của leaf bên cạnh thay vì cặp được yêu cầu. Trong lúc đó HasKey chạy phép quét riêng của mình và báo key có mặt, nên class tự mâu thuẫn với chính nó. Một sổ tay tham chiếu sinh tự động với một named destination cho mỗi ký hiệu API vượt 32.768 entry chẳng cần cố, và một số producer ghi tất cả vào một leaf phẳng duy nhất

Kể từ v3.539.45, FindIndex trả về chỉ số mảng qua một tham số out riêng và offset entry đầy đủ làm kết quả, nên không giá trị nào bị cắt. Cùng đợt phát hành ấy siết thêm hai bên cạnh. KeyName giờ chỉ đếm và trả về các key string đúng nghĩa, trả về chuỗi rỗng với chỉ số 0 hay thấp hơn, trong khi trước đây nó ép kiểu bất cứ object nào đứng sau một key không hợp lệ. HasKey không còn coi một key dạng số hay không hợp lệ khác là một tên rỗng. Với một leaf như [(Valid) 42 123 456], HasKey('') giờ là False và KeyName(2) trả về chuỗi rỗng

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; tệp thiếu nó trả về số trang thường
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // name tree /EmbeddedFiles; chỉ số bắt đầu từ 1, key không phải string bị bỏ qua
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // tên, kiểu MIME
    // name tree /JavaScript: liệt kê tên package, không chạy gì cả
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

Trên cùng tệp dựng tay ấy, với gốc /PageLabels liệt kê một leaf hai lần và tham chiếu chính nó, phép audit này in i và A-1 cho hai trang, mỗi dải đúng một lần, cùng script package duy nhất từ một cây /JavaScript cũng trỏ ngược về gốc của chính nó. Phía ghi của page label có riêng một lịch sử với các gốc /Kids, đã kể trong sửa page label PDF lưu trong number tree dạng /Kids; AddPageLabels làm phẳng kiểu gốc ấy trước khi chèn, và nó dựa vào đúng phép liệt kê EnumNumTree mô tả ở đây

Phần gia cố này vẫn không bảo đảm điều gì?

Phần gia cố bảo đảm kết thúc, thứ tự ổn định và kết quả đúng cho những cây mà key thật còn nguyên vẹn; nó không biến một cây hỏng thành có nghĩa như tác giả định. Vài giới hạn đáng biết trước khi bạn dựng lên trên đó

• Tập visited hoạt động theo định danh object. Hai dictionary phân biệt với nội dung y hệt là hai node, nên một producer chép leaf thay vì tham chiếu tới nó vẫn cho ra các entry trùng nhau
• Một /Limits có dạng đúng, có thứ tự nhưng sai nội dung vẫn cắt nhánh. Một reader dùng dải làm tối ưu hóa không thể vừa miễn nhiễm với một dải nói dối trông rất hợp lý được; phương án duy nhất là bỏ hẳn /Limits và quét mọi leaf
• Phép liệt kê giữ thứ tự tệp nhưng không sắp. GetPageLabel áp dải được liệt kê cuối cùng tại hoặc dưới số trang, nên producer viết các dải lộn xộn sẽ nhận ngữ nghĩa theo thứ tự tệp
• Bộ nhớ tăng theo số node và entry phân biệt. Phép duyệt thêm vào một danh sách và một hash set, không hơn, nhưng một name tree 100 MB vẫn là một name tree 100 MB sau khi parse
• Các key trùng nhau trong cùng một leaf không được báo. Binary search trả về cặp khớp nào nó chạm đầu tiên; nhánh tuyến tính dự phòng giữ kết quả khớp cuối cùng nó quét

Tra nhanh: đọc cây PDF từ các tệp không đáng tin

• Nâng lên v3.539.45 trở lên để duyệt name tree và number tree an toàn với cycle, an toàn với stack, và lên v3.539.51 trở lên để /Limits bị đảo không còn giấu key
• Coi GetNamedDestination trả về 0 là "vắng mặt", còn GetDestPage trả về 0 là "có mặt nhưng không dùng được"
• Dùng GlobalJavaScriptCount và GlobalJavaScriptPackageName cho name tree /JavaScript; GetDocJavaScript đọc các trigger /AA trong catalog thay vào đó
• Đánh chỉ số attachment và script package từ 1 tới con số thư viện báo; các key không hợp lệ không được đếm
• Trong code cây của riêng bạn, hãy đánh dấu node đã ghé lúc lấy ra, đẩy con vào theo chiều ngược, và chỉ để /Limits cắt nhánh khi nó là một cặp đúng kiểu, có thứ tự

Công cụ pre-flight, trình lưu trữ và viewer đọc những cây này trước khi bất kỳ trang nào được render, nên chúng phải sống sót qua bất cứ thứ gì xếp hàng vào hộp upload. Các trình đọc cây mô tả ở trên đi kèm PDFlibPas, PDF Library for Delphi, thứ build được với cả Delphi lẫn Free Pascal