שחזור טבלאות Xref פגומות ב-PDF: סריקת שחזור ב-Delphi

כאשר טבלת cross-reference של PDF אינה שמישה, התיקון הוא להתעלם ממנה לגמרי ולבנות אותה מחדש מגוף הקובץ. PDFlibPas Delphi PDF Library עושה זאת באמצעות סורק טוקנים במעבר יחיד שרושם כל כותרת אובייקט עקיף אמיתית שהוא רואה, ואז משחזר את מילון ה-trailer ומעביר את הטבלה המשוחזרת לטוען הרגיל

מה נשבר ראשון כש-PDF פגום

טבלת ה-cross-reference היא החלק השביר ביותר ב-PDF, כי היא החלק היחיד שמאחסן byte offsets מוחלטים. ISO 32000-1 §7.5.4 מגדיר את הרשומות הללו כ-offsets עשרוניים בני עשר ספרות מתחילת הקובץ, ו-§7.5.5 שם את מילת המפתח startxref קרוב לסוף כשהיא מצביעה על הטבלה עצמה. כל אחד מהמספרים הללו נפסל על ידי כל עריכה שמזיזה בייטים. הפעלת FTP שרצה במצב טקסט ותרגמה CRLF, הורדה שנקטעה, סקטור שהתקלקל בכונן משותף, כלי אצווה שהוסיף בלי לכתוב עדכון מצטבר כראוי: כולם משאירים את נתוני האובייקטים קריאים לחלוטין ואת האינדקס מצביע על זבל

זו הסיבה ש"הקובץ פגום ומתוקן" הוא דיאלוג כה נפוץ. הבייטים כמעט תמיד עדיין שם. מה שאבד הוא המפה. שחזור לכן אינו התאוששות פורנזית של נתונים אבודים, אלא בנייה מחדש של אינדקס שניתן לגזור מהגוף, והוא מצליח הרבה יותר ממה שמשתמשים מצפים כי התוכן היקר, עצי העמודים, הגופנים והתמונות, לא נגע בו איש

מדוע חיפוש אחר N 0 obj מוצא התאמות שווא?

שחזור נאיבי מחפש בבייטים הגולמיים את התבנית "מספר שלם, מספר שלם, obj" ורושם כל פגיעה. הוא מוצא יותר מדי. PDF הוא פורמט מכולה, ושלושה אזורים בקובץ אטומים לדקדוק האובייקטים: הערות (§7.2), מחרוזות (§7.3.4), ונתוני stream (§7.3.8). כל אחד מהם יכול להכיל בייטים שנקראים בדיוק כמו כותרת אובייקט, ואף אחד מהם אינו כותרת אובייקט. כיתוב במחרוזת literal, הערת דיבאג שנשארה, או שני מגה-בייט של פלט Flate או DCT יפיקו בשמחה משהו שנראה כמו 99 0 obj

const
  Trap: AnsiString =
    '4 0 obj'#10 +
    '(a caption that mentions 88 0 obj)'#10 +   // literal string, not an object
    'endobj'#10 +
    '% 77 0 obj left over from a debug dump'#10 +  // comment, not an object
    '5 0 obj'#10 +
    '<< /Length 2097152 >>'#10 +
    'stream'#10 +
    { two MiB of compressed bytes that contain the byte sequence
      99 0 obj and, further along, a complete endstream }
    'endstream'#10 +
    'endobj'#10;

כל רשומת שווא עולה פעמיים. היא מזהמת את הטבלה המשוחזרת במספר אובייקט שלא קיים, והיא יכולה להסתיר אובייקט אמיתי עם אותו מספר שמופיע מאוחר יותר בקובץ. PDFlibPas לכן לא מבצע pattern-matching כלל. הוא מבצע tokenisation, כלומר הוא תמיד יודע אם הבייטים תחת הסמן הם קוד או מטען, ומטען מדולג בלי שהוא אי פעם מתפרש

מכונת מצבים במעבר יחיד על בלוקים של 64 KiB

PDFlibPas סורק את כל הקובץ בדיוק פעם אחת, בבלוקים של 64 KiB, עם מכונת מצבים הבנויה על כללי הטוקנים של ISO 32000-1 §7.2 ותחביר האובייקט העקיף של §7.3.10. טוקן מסתיים ברווח לבן או באחד מתווי המפריד, וכותרת אובייקט נרשמת רק כאשר נראתה רצף שלם של מספר אובייקט חיובי, מספר generation לא-שלילי, ומילת מפתח obj חשופה. ה-offset הנרשם הוא תחילת הטוקן של מספר האובייקט, וזה מה שרשומת cross-reference צריכה להצביע עליו, לא המיקום של מילת המפתח obj

function RebuildIsWhiteSpace(Value: Byte): Boolean;
begin
  Result := (Value = 0) or (Value = 9) or (Value = 10) or
            (Value = 12) or (Value = 13) or (Value = 32);
end;

function RebuildIsDelimiter(Value: Byte): Boolean;
begin
  Result := (Value = Ord('(')) or (Value = Ord(')')) or
            (Value = Ord('<')) or (Value = Ord('>')) or
            (Value = Ord('[')) or (Value = Ord(']')) or
            (Value = Ord('{')) or (Value = Ord('}')) or
            (Value = Ord('/')) or (Value = Ord('%'));
end;

הפרט החשוב הוא שמצב הטוקן ומצב המחרוזת שורדים חציית גבול בלוק. כותרת שמתפרשת על פני קו 65536 הבייטים עדיין מזוהה, כי הטוקן החלקי, זוג המספרים השלמים הממתין, ודגלי ה-in-string כולם עוברים לבלוק הבא. ה-buffers קבועים: 64 KiB לסריקה, 32 בייט לטוקן הארוך ביותר שאי פעם יכול להיות חשוב, והמערכים היחידים שגדלים עם הקובץ הם רשימות מספר האובייקט, מספר ה-generation וה-offset בן 64 סיביות, שפרופורציוניות למספר האובייקטים האמיתי ולא לגודל הקובץ. בפועל הסריקה מבצעת קריאות רציפות ולכל היותר שני seek מפורשים על פני כל המסמך, וזה מה שהופך אותה לישימה על קלטי מאות מגה-בייט הנדונים בהמאמר על גישה ישירה למיזוג ופיצול

מדוע אי אפשר לסמוך על stream שיסתיים ב-endstream?

כי נתוני stream הם בייטים שרירותיים, ובייטים שרירותיים יכולים לאיית endstream במקרה. stream שמתחיל אחרי מילת המפתח stream חייב לדלג עליו כנתונים אטומים עד שהוא באמת מסתיים, אך ההופעה הראשונה של מילת המפתח הסוגרת היא רק מועמדת. PDFlibPas פותר זאת על ידי דרישת אימות נוסף: טוקן endstream מתקבל כסוף האמיתי של ה-stream רק כאשר הטוקן הבא שאינו רווח לבן הוא endobj עצמאי, הרצף ש-§7.3.8 דורש סביב אובייקט stream. פגיעה מקרית בתוך נתונים דחוסים כמעט אף פעם אין לה את ההמשך הזה, כך שהסורק נשאר בתוך ה-stream וממשיך. שני כללים קטנים יותר חשובים באותה מידה. מילת המפתח stream נכנסת למצב stream רק כשהיא מילת מפתח חשופה, כך ששם אובייקט כמו /stream במילון לעולם לא מפעיל אותה. וטוקן obj או trailer מכובד רק כשהטוקן לא חרג ממגבלת 32 הבייט ולא התחיל בקו נטוי. בלי שני השומרים הללו, מילון משאבים עם שמות מפתח שגויים היה מספיק כדי להוציא את הסריקה ממסלולה, וזו בדיוק הקטגוריה של קלט עוין המכוסה בהערות על ניתוח בטוח של PDF לא מהימן

מציאת הסוף האמיתי של מילון ה-trailer

שחזור האובייקטים הוא רק חצי מהעבודה, כי הטוען עדיין זקוק ל-trailer כדי למצוא את /Root. PDFlibPas זוכר את 64 המיקומים האחרונים של מילת המפתח trailer שנמצאו במהלך הסריקה ומאמת אותם אחורה, החדש ביותר ראשון, כך שה-trailer השמיש החדש ביותר מנצח, ומילת מפתח תועה שלא מלווה במילון פשוט נכשלת באימות ונופלת למועמד הקודם. כל מועמד נקרא עם תקרה של 1 MiB, וסוף המילון מאותר על ידי מעקב אחר עומק << ו->> מקונן יחד עם escapes של מחרוזות literal, מחרוזות הקסדצימליות והערות

// A naive reader that stops at the first '>>' truncates this trailer,
// and a fixed 2048-byte window can cut it in half on a large one
'trailer'#10 +
'<< /Size 5 /Root 1 0 R' +
'   /Custom << /Text (value >> preserved) >> >>'#10

מעקב העומק אינו אקדמי. trailer שנקטע ומאבד את /Encrypt הופך מסמך מוצפן הניתן לשחזור לבלתי ניתן לפתיחה, ואיבוד /Info או תת-מילון מותאם אישית מוחק בשקט metadata שמערכת במורד הזרם עשויה להסתמך עליה. אם הקובץ מוצפן, ה-trailer המשוחזר הוא מה שמאפשר לנתיב האישורים הרגיל לרוץ, וסמנטיקת הניסיון החוזר זהה לזו המתוארת בהמאמר על טעינת מסמכים מוצפנים

מה שחזור לא יכול להחזיר לך

שחזור הוא מאמץ מיטבי, וכנות לגבי גבולותיו היא חלק מהוצאתו לשוק. שלושה מקרים נכשלים לגמרי. אובייקטים ארוזים בתוך object streams (§7.5.7) אינם גלויים בנפרד לסריקת בייטים, כך שאם מכולה שורדת אך ה-cross-reference stream שלה (§7.5.8) לא, האובייקטים שהיא מחזיקה אינם מאונדקסים על ידי הבנייה מחדש. קובץ שגופו נפגם באמת, ולא רק שהאינדקס שלו הוטעה, יפיק כותרות שתוכנן כבר לא מתנתח. וקובץ ללא מילת מפתח trailer ניתנת לשחזור ובלי catalog קריא אין לו על מה לעגן עץ מסמך, לא משנה כמה כותרות אובייקט נמצאו

מספרי אובייקט כפולים הם המקרה האמצעי המעניין. קובץ שעודכן באופן מצטבר מכיל באופן לגיטימי כמה דורות (generations) של אותו מספר אובייקט, ושרשרת ה-cross-reference ששרדה היא הרישום היחיד של מי היה הנוכחי. בנייה מחדש אין לה את השרשרת הזו, כך שהיא רושמת כל כותרת שהיא רואה בסדר הקובץ ופותרת לפי מספר אובייקט לאחר מכן. בדרך כלל הגרסה המאוחרת מנצחת, מה שבדרך כלל נכון, אך מסמך שעודכן ואז הוחזר חלקית יכול לחזור שונה בעדינות ממה שה-xref המקורי תיאר. קבצים מלוניארזים (linearised) נושאים אותה אזהרה מהכיוון ההפוך: פריסת העמוד הראשון וטבלאות ה-hint חסרות משמעות ברגע שהאינדקס נוצר מחדש, כך שקובץ מתוקן צריך להיחשב כמסמך רגיל, לא-לינארי

var
  Pdf: TPDFlib;
begin
  Pdf := TPDFlib.Create;
  try
    if Pdf.LoadFromFile('truncated-invoice.pdf', '') = 1 then
    begin
      if Pdf.GetDocumentRepaired = 1 then
        LogWarning('xref was unusable; the table was reconstructed');
      if Pdf.PageCount > 0 then
        Pdf.SaveToFile('recovered-invoice.pdf');   // writes a clean xref
    end;
  finally
    Pdf.Free;
  end;
end;

הנפילה חזרה (fallback) אוטומטית: PDFlibPas מריץ את הסריקה הגולמית בכל פעם ששרשרת ה-cross-reference אינה ניתנת לקריאה, וגם כאשר כל רשומה בשימוש טוענת offset אפס, שזה החתימה של טבלה שנכתבה אך מעולם לא מולאה. GetDocumentRepaired מחזיר 1 כשהנתיב הזה רץ, וכדאי לתעד זאת במקום להתעלם, כי מסמך שנטען דרך שחזור צריך להישמר מחדש לקובץ נקי במקום להישאר בצינור כאילו לא קרה כלום. שמירתו כותבת טבלת cross-reference טרייה ועקבית, וזה התיקון הזול ביותר האפשרי עבור כל צרכן במורד הזרם

נתיב השחזור, דגל GetDocumentRepaired והטוען הזורם המוצגים כאן הם חלק מ-PDFlibPas Delphi PDF Library, לצד ה-API-ים לניתוח, רינדור וחתימה המכוסים במקומות אחרים בבלוג זה