PDFlibPas 네임 트리: 사이클, 나쁜 Limits, 거대한 리프

losLab PDF Library for Delphi인 PDFlibPas는 v3.539.45부터 명시적 스택과 방문 집합으로 PDF 네임 트리와 넘버 트리를 걷습니다. 그래서 순환 /Kids, 공유 자식, 수천 수준 깊이의 트리가 더 이상 콜 스택을 소진하거나 엔트리를 복제하지 않습니다. v3.539.51부터는 빠졌거나 malformed이거나 뒤집힌 /Limits 쌍이 키를 담은 가지를 결코 숨기지 않습니다. 이름 붙은 대상(named destination), 페이지 레이블, 첨부, 문서 수준 JavaScript가 모두 이 두 코드 경로를 통해 읽히므로, 직접 만들지 않은 어떤 PDF의 공격 표면에도 이들이 포함됩니다

방아쇠는 별난 경우가 드뭅니다. 퍼저, 적대적 업로드, 버그 있는 증분 저장이 조상을 되가리키는 /Kids 엔트리를 쓰면, 재귀 걷기는 2킬로바이트 파일에서 스택 오버플로로 죽습니다. 더 조용한 실패는 깨진 /Limits 배열을 신뢰한 탐색이 눈에 뻔히 있는 대상에게 "not found"를 보고하는 것입니다

PDF에서 네임 트리와 넘버 트리는 어디에 나타날까?

네임 트리와 넘버 트리는 PDF가 큰 키 집합을 오브젝트에 사상하는 곳이면 어디든 나타나고, PDFlibPas는 공개 API로 그중 최소한 넷을 읽습니다. ISO 32000-1 §7.9.6이 네임 트리(문자열 키, 표 36)를, §7.9.7이 넘버 트리(정수 키, 표 37)를 정의합니다. 둘 다 대체로 균형 잡힌 트리로, 루트와 중간 노드는 /Kids를 들고, 리프는 정렬된 키/값 쌍을 /Names나 /Nums에 담고, 루트가 아닌 노드는 자기 아래의 가장 작은 키와 가장 큰 키를 담은 두 요소 /Limits 배열을 듭니다

트리	사는 곳	규격	PDFlibPas 읽기 API
이름 붙은 대상	이름 딕셔너리의 /Dests	§12.3.2.3	GetNamedDestination, 이어서 GetDestPage / GetDestType
페이지 레이블	카탈로그의 /PageLabels(넘버 트리)	§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 엔트리가 같은 리프를 참조하면 순진한 열거는 그것을 두 번 방문하고, 첨부 개수나 스크립트 패키지 목록이 존재하지 않는 엔트리를 보고합니다

수정은 재귀를 힙 위의 명시적 LIFO 스택과 딕셔너리 정체성을 키로 하는 방문 집합으로 바꿉니다. 노드는 푸시될 때가 아니라 팝될 때 표시되므로, 순환 참조는 스택에 잠깐 앉아 있을 수 있지만 다시 올라오는 순간 버려집니다. 각 서로 다른 노드는 자식을 정확히 한 번 펼치므로, 전체 작업량은 서로 다른 딕셔너리 수 더하기 그들의 /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
        // 가장 왼쪽 kid가 먼저 팝되도록 오른쪽에서 왼쪽으로 푸시
        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 전의 탐색들은 /Limits가 키를 커버하는 첫 자식에 Found 플래그를 세우고 그 안으로 내려간 뒤 다른 형제를 절대 보지 않았습니다. 그 자식이 빈 것이나 오래되었거나 루트로 되돌아가는 루프로 판명되면, 바로 다음 형제가 키를 들고 있어도 답은 nil이었습니다

이제 NameTreeLookup과 NumTreeLookup을 모두 떠받치는 다시 쓴 FindTreeValue는 범위가 키를 배제하지 않는 모든 자식을 푸시하고, 매치를 찾거나 스택이 빌 때까지 팝을 계속합니다. 한 리프 안의 미스는 그저 한 리프 안의 미스일 뿐입니다. 잘 만들어진 트리에서는 추가 비용이 없고, 깨진 트리에서는 노드 방문 몇 번의 비용으로 올바른 답을 돌려줍니다

리프 검색도 같은 철학을 따릅니다. ISO 32000-1은 /Names 배열의 키가 바이트 값으로 정렬되기를 요구하므로, 리프는 먼저 이진 검색으로 찾습니다. 실패하면 PDFlibPas는 쌍들의 선형 스캔으로 폴백합니다. 순서가 어긋난 리프가 있는 키를 보이지 않게 만들 수 있기 때문입니다. 정렬은 빠른 경로이지 필터가 아닙니다

탐색은 한 구조 모순에 대해서는 추측을 거절합니다. 표 36은 노드가 /Kids나 /Names 둘 중 하나만 들게 하고 절대 둘 다 들지 못하게 하는데, 탐색 경로는 둘 다 든 노드를 malformed로 취급해 어느 한 해석을 고르는 대신 건너뜁니다. EnumNumTree 같은 열거 경로는 더 관대해서 둘 다 있으면 /Kids를 따릅니다

읽는 쪽은 /Limits를 무엇에 대해 신뢰할 수 있을까?

읽는 쪽은 /Limits를 작업을 건너뛰는 데에만 신뢰할 수 있고, 키가 없다고 판정하는 데에는 결코 신뢰할 수 없으며, 쌍이 잘 만들어졌을 때만 그렇습니다. 표 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 > Hi일 때 Lo <= Key <= Hi를 만족하는 키는 없으므로 가지는 모든 탐색에서 배제됐습니다. v3.539.51부터 범위는 하한이 상한을 넘지 않을 때만 가지치기에 쓰입니다
• 잘 만들어지고, 순서가 있고, 올바른 경우: 가지를 건너뛰는 데 쓰입니다. 그 엔트리의 존재 이유입니다

진짜 키가 모든 케이스의 결과를 결정합니다. 적대적인 /Limits는 PDFlibPas로 하여금 필요 이상의 노드를 방문하게 할 수 있지만, malformed인 것은 더 이상 기존 대상을 사라지게 할 수 없습니다. 호출자 쪽에서는 아무것도 바뀌지 않습니다. GetNamedDestination은 이름이 정말로 없을 때 0을, 그렇지 않으면 대상 ID를 돌려주고, 대상 함수들이 거기서 이어받습니다

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)] limits 아래에서 진짜 엔트리를 담은 둘째 자식을 가진 손작성 파일에 대해 돌리면, 대상을 뷰 타입 2(Fit)의 2페이지로 해석합니다. v3.539.45 전에는 같은 탐색이 0을 돌려줬습니다. 루프 자식이 키를 먼저 주장했고 검색은 형제에 닿지 않았기 때문이죠. v3.539.45만으로도 여전히 0이었습니다. 뒤집힌 범위가 진짜 리프를 배제했으니까요. 이어서 이 대상들을 가리키는 outline을 읽는다면, Delphi에서 PDF 북마크와 어노테이션 액션 읽기 짝글이가 액션 쪽을 다룹니다

32,769개 이름을 담은 리프는 TPDFNameTree를 어떻게 깨뜨렸을까?

32,769개 이름/값 쌍을 담은 리프는 TPDFNameTree를 깨뜨렸습니다. 내부 FindIndex가 두 숫자를 하나의 32비트 Integer에 포장했기 때문입니다. 상위 16비트에 내부 배열 리스트에서의 리프 위치, 하위 16비트에 그 리프의 /Names 배열 안에서의 엔트리 오프셋이죠. 각 쌍은 배열 슬롯 두 개를 차지하므로, 32,769번째 쌍(쌍 인덱스 32,768)은 오프셋 65,536, 즉 $10000에서 시작합니다. 그 값이 상위 절반으로 올림수되고, 디코더는 그것을 다음 리프의 오프셋 0으로 읽어 돌렸습니다

TPDFNameTree는 첨부, 전역 JavaScript 패키지, 이름 붙은 대상 쓰기 뒤에 있는 클래스이므로 결과가 구체적입니다. 단일 리프 트리에는 다음 리프가 없으니 FindKey와 DeleteKey가 리프 목록 끝을 넘어 인덱싱했고, 다중 리프 트리에서는 요청된 쌍 대신 다음 리프의 첫 쌍을 반환하거나 삭제했습니다. 한편 HasKey는 자기 스캔을 돌려 키가 있다고 보고했으니, 클래스가 스스로와 모순됐습니다. API 심볼마다 이름 붙은 대상 하나씩 달린 생성된 레퍼런스 매뉴얼은 애쓰지 않아도 32,768 엔트리를 넘고, 일부 생산자는 그 전부를 단일 평면 리프에 씁니다

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 루트와 함께 별도의 역사가 있는데, /Kids 넘버 트리에 저장된 PDF 페이지 레이블 고치기가 다룹니다. AddPageLabels는 삽입 전에 그런 루트를 평평하게 만들며, 여기서 기술한 같은 EnumNumTree 열거에 의지합니다

이 강화는 여전히 무엇을 보장하지 않을까?

이 강화는 진짜 키가 온전한 트리에 대해 종료, 안정적인 순서, 올바른 결과를 보장합니다. 깨진 트리가 저자가 의도한 뜻을 갖게 만들지는 않죠. 그 위에 뭔가를 세우기 전에 알아둘 만한 한계 몇 가지가 있습니다

• 방문 집합은 오브젝트 정체성으로 동작합니다. 내용이 같은 서로 다른 두 딕셔너리는 두 노드이므로, 참조 대신 리프를 복사하는 생산자는 여전히 중복 엔트리를 내놓습니다
• 잘 만들어지고 순서가 있지만 틀린 /Limits는 여전히 가지치기합니다. 범위를 최적화로 쓰는 읽는 쪽은 그럴듯하게 거짓말하는 범위에 면역일 수도 없습니다. 유일한 대안은 /Limits를 완전히 무시하고 모든 리프를 스캔하는 것
• 열거는 파일 순서를 보존하지만 정렬하지는 않습니다. GetPageLabel은 페이지 이하인 마지막 열거 범위를 적용하므로, 범위를 순서 없이 쓰는 생산자는 파일 순서 시맨틱스를 받습니다
• 메모리는 서로 다른 노드와 엔트리 수에 따라 자랍니다. 순회는 리스트와 해시 집합을 더할 뿐이지만, 100 MB 네임 트리는 파싱 후에도 여전히 100 MB 네임 트리입니다
• 한 리프 안의 중복 키는 보고되지 않습니다. 이진 검색은 처음 닿는 매치 쌍을 반환하고, 선형 폴백은 스캔하는 마지막 매치를 유지합니다

빠른 참조: 신뢰할 수 없는 파일에서 PDF 트리 읽기

• 네임 트리와 넘버 트리의 사이클 안전, 스택 안전 순회를 위해 v3.539.45 이상으로, 그리고 뒤집힌 /Limits가 키를 더 이상 숨기지 않게 하려면 v3.539.51 이상으로 업그레이드
• GetNamedDestination이 0을 돌려주면 "없음"으로, GetDestPage가 0을 돌려주면 "있지만 쓸 수 없음"으로 취급
• /JavaScript 네임 트리에는 GlobalJavaScriptCount와 GlobalJavaScriptPackageName을 쓸 것. GetDocJavaScript는 대신 카탈로그 /AA 트리거를 읽음
• 첨부와 스크립트 패키지는 1부터 라이브러리가 보고한 개수까지 인덱싱할 것. 잘못된 키는 세지 않음
• 직접 쓰는 트리 코드에서는 노드를 팝 시점에 방문 표시하고, 자식을 거꾸로 푸시하며, /Limits는 타입이 맞고 순서가 있는 쌍일 때만 가지치기하게 할 것

프리플라이트 도구, 아카이버, 뷰어는 어떤 페이지도 렌더링되기 전에 이 트리들을 읽으므로, 업로드 큐에 뭐든 도착해도 살아남아야 합니다. 위에서 기술한 트리 리더는 Delphi와 Free Pascal 양쪽으로 빌드되는 PDFlibPas, PDF Library for Delphi에 실려 나갑니다