Ανακατασκευή Πίνακα Xref Κατεστραμμένου PDF σε Delphi

Όταν ένας πίνακας cross-reference PDF είναι μη χρησιμοποιήσιμος, η λύση είναι να αγνοηθεί εντελώς και να ανακατασκευαστεί από το σώμα του αρχείου. Η PDFlibPas Delphi PDF Library το κάνει αυτό με έναν σαρωτή tokens ενός περάσματος που καταγράφει κάθε γνήσια κεφαλίδα έμμεσου αντικειμένου που βλέπει, μετά ανακτά το dictionary του trailer και παραδίδει τον ανακατασκευασμένο πίνακα στον κανονικό loader

Τι σπάει πρώτο όταν ένα PDF καταστρέφεται

Ο πίνακας cross-reference είναι το πιο εύθραυστο μέρος ενός PDF, επειδή είναι το μόνο μέρος που αποθηκεύει απόλυτα byte offsets. Το ISO 32000-1 §7.5.4 ορίζει αυτές τις εγγραφές ως δεκαψήφια offsets από την αρχή του αρχείου, και η §7.5.5 τοποθετεί τη λέξη-κλειδί startxref κοντά στο τέλος να δείχνει στον ίδιο τον πίνακα. Κάθε ένας από αυτούς τους αριθμούς ακυρώνεται από οποιαδήποτε επεξεργασία που μετατοπίζει bytes. Μια συνεδρία FTP που έτρεξε σε text mode και μετέφρασε CRLF, μια περικομμένη λήψη, ένας τομέας που χάλασε σε έναν κοινόχρηστο δίσκο, ένα batch εργαλείο που προσάρτησε χωρίς να γράψει σωστά ένα incremental update: όλα αυτά αφήνουν τα δεδομένα αντικειμένων απόλυτα αναγνώσιμα και τον δείκτη να δείχνει σε σκουπίδια

Για αυτό το «το αρχείο είναι κατεστραμμένο και επιδιορθώνεται» είναι τόσο κοινός διάλογος. Τα bytes σχεδόν πάντα βρίσκονται ακόμα εκεί. Αυτό που έχει χαθεί είναι ο χάρτης. Η ανακατασκευή επομένως δεν είναι εγκληματολογική ανάκτηση χαμένων δεδομένων, είναι ανακατασκευή ενός δείκτη που μπορεί να προκύψει από το σώμα, και πετυχαίνει πολύ πιο συχνά από όσο περιμένουν οι χρήστες επειδή το ακριβό περιεχόμενο, τα page trees και οι γραμματοσειρές και οι εικόνες, παραμένει ανέγγιχτο

Γιατί η αναζήτηση για N 0 obj βρίσκει ψευδείς αντιστοιχίες;

Μια αφελής ανακατασκευή αναζητά στα ακατέργαστα bytes το μοτίβο «ακέραιος, ακέραιος, obj» και καταγράφει κάθε εύρεση. Βρίσκει πάρα πολλά. Το PDF είναι μορφή container, και τρεις περιοχές ενός αρχείου είναι αδιαφανείς στη γραμματική αντικειμένων: σχόλια (§7.2), strings (§7.3.4), και δεδομένα stream (§7.3.8). Οποιαδήποτε από αυτές μπορεί να περιέχει bytes που διαβάζονται ακριβώς σαν κεφαλίδα αντικειμένου, και καμία από αυτές δεν είναι κεφαλίδα αντικειμένου. Μια λεζάντα σε ένα literal string, ένα υπολειπόμενο σχόλιο debug, ή δύο megabytes εξόδου 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, κάτι που σημαίνει ότι πάντα ξέρει αν τα bytes κάτω από τον δρομέα είναι κώδικας ή payload, και το payload παραλείπεται χωρίς ποτέ να ερμηνευτεί

Μια μηχανή καταστάσεων ενός περάσματος πάνω σε blocks των 64 KiB

Η PDFlibPas σαρώνει ολόκληρο το αρχείο ακριβώς μία φορά, σε blocks των 64 KiB, με μια μηχανή καταστάσεων χτισμένη πάνω στους κανόνες tokens του ISO 32000-1 §7.2 και τη σύνταξη έμμεσου αντικειμένου της §7.3.10. Ένα token τελειώνει σε λευκό χαρακτήρα ή σε έναν από τους οριοθέτες, και μια κεφαλίδα αντικειμένου καταγράφεται μόνο όταν έχει παρατηρηθεί μια πλήρης ακολουθία θετικού αριθμού αντικειμένου, μη αρνητικού αριθμού generation, και γυμνής λέξης-κλειδί obj. Το καταγεγραμμένο offset είναι η αρχή του token του αριθμού αντικειμένου, που είναι αυτό στο οποίο πρέπει να δείχνει μια εγγραφή 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;

Η σημαντική λεπτομέρεια είναι ότι η κατάσταση token και η κατάσταση string επιβιώνουν σε ένα όριο block. Μια κεφαλίδα που εκτείνεται πάνω από τη γραμμή των 65536 bytes εξακολουθεί να αναγνωρίζεται, επειδή το μερικό token, το εκκρεμές ζεύγος ακεραίων, και οι σημαίες in-string μεταφέρονται όλα στο επόμενο block. Τα buffers είναι σταθερά: 64 KiB για τη σάρωση, 32 bytes για το μεγαλύτερο token που μπορεί να έχει σημασία, και οι μόνοι πίνακες που μεγαλώνουν με το αρχείο είναι οι λίστες αριθμού αντικειμένου, αριθμού generation και 64-bit offset, οι οποίες είναι ανάλογες με τον πραγματικό αριθμό αντικειμένων και όχι με το μέγεθος του αρχείου. Στην πράξη η σάρωση εκδίδει διαδοχικές αναγνώσεις και το πολύ δύο ρητά seeks σε ολόκληρο το έγγραφο, κάτι που την κάνει βιώσιμη στις πολλαπλών-εκατοντάδων-megabyte εισόδους που συζητούνται στο άρθρο για τη συγχώνευση και διαίρεση με άμεση πρόσβαση

Γιατί ένα stream δεν μπορεί να εμπιστεύεται ότι τελειώνει στο endstream;

Επειδή τα δεδομένα stream είναι αυθαίρετα bytes, και τα αυθαίρετα bytes μπορούν να σχηματίσουν κατά λάθος το endstream. Ένα stream που ξεκινά μετά τη λέξη-κλειδί stream πρέπει να παραλείπεται ως αδιαφανή δεδομένα μέχρι να τελειώσει πραγματικά, αλλά η πρώτη εμφάνιση της λέξης-κλειδί κλεισίματος είναι μόνο υποψήφια. Η PDFlibPas το επιλύει απαιτώντας επιβεβαίωση: ένα token endstream γίνεται αποδεκτό ως το πραγματικό τέλος του stream μόνο όταν το επόμενο token που δεν είναι λευκός χαρακτήρας είναι ένα αυτόνομο endobj, η ακολουθία που απαιτεί η §7.3.8 γύρω από ένα stream object. Μια τυχαία εύρεση μέσα σε συμπιεσμένα δεδομένα σχεδόν ποτέ δεν έχει αυτή τη συνέχεια, οπότε ο σαρωτής παραμένει μέσα στο stream και συνεχίζει. Δύο μικρότεροι κανόνες έχουν εξίσου σημασία. Η λέξη-κλειδί stream εισέρχεται σε κατάσταση stream μόνο όταν είναι γυμνή λέξη-κλειδί, οπότε ένα name object όπως /stream σε ένα dictionary ποτέ δεν την ενεργοποιεί. Και ένα token obj ή trailer τιμάται μόνο όταν το token δεν υπερέβη το όριο των 32 bytes και δεν ξεκινούσε με κάθετο. Χωρίς αυτούς τους δύο φύλακες ένα resource dictionary με λάθος ονόματα κλειδιών θα αρκούσε για να εκτροχιάσει τη σάρωση, κάτι που είναι ακριβώς η κατηγορία εχθρικής εισόδου που καλύπτεται στις σημειώσεις για την ασφαλή ανάλυση μη έμπιστων PDF

Εντοπισμός του πραγματικού τέλους του dictionary trailer

Η ανάκτηση των αντικειμένων είναι μόνο η μισή δουλειά, επειδή ο loader εξακολουθεί να χρειάζεται έναν trailer για να βρει το /Root. Η PDFlibPas θυμάται τις τελευταίες 64 θέσεις της λέξης-κλειδί trailer που βρέθηκαν κατά τη σάρωση και τις επικυρώνει προς τα πίσω, ξεκινώντας από την πιο πρόσφατη, ώστε ο πιο πρόσφατος χρησιμοποιήσιμος trailer να επικρατεί και μια μοναχική λέξη-κλειδί που δεν ακολουθείται από dictionary απλώς αποτυγχάνει στην επικύρωση και περνά στον προηγούμενο υποψήφιο. Κάθε υποψήφιος διαβάζεται με ένα όριο 1 MiB, και το τέλος του dictionary εντοπίζεται παρακολουθώντας το εμφωλευμένο βάθος << και >> μαζί με τις διαφυγές literal string, τα δεκαεξαδικά strings και τα σχόλια

// 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 ή ενός προσαρμοσμένου υπο-dictionary απορρίπτει σιωπηλά μεταδεδομένα από τα οποία μπορεί να εξαρτάται ένα κατάντη σύστημα. Αν το αρχείο είναι κρυπτογραφημένο, ο ανακτημένος trailer είναι αυτό που επιτρέπει να τρέξει η κανονική διαδρομή διαπιστευτηρίων, και η σημασιολογία επανάληψης είναι η ίδια που περιγράφεται στο άρθρο για τη φόρτωση κρυπτογραφημένου εγγράφου

Τι δεν μπορεί να σας επιστρέψει η ανακατασκευή

Η ανακατασκευή είναι μια βέλτιστη προσπάθεια, και η ειλικρίνεια για τα όριά της είναι μέρος της κυκλοφορίας της. Τρεις περιπτώσεις αποτυγχάνουν εντελώς. Τα αντικείμενα πακεταρισμένα μέσα σε object streams (§7.5.7) δεν είναι ατομικά ορατά σε μια σάρωση bytes, οπότε αν ένα container επιζήσει αλλά το cross-reference stream του (§7.5.8) όχι, τα αντικείμενα που κρατά δεν ευρετηριάζονται από την ανακατασκευή. Ένα αρχείο του οποίου το σώμα ήταν στην πραγματικότητα διεφθαρμένο, και όχι απλώς λάθος ευρετηριασμένο, θα παράγει κεφαλίδες των οποίων το περιεχόμενο δεν αναλύεται πια. Και ένα αρχείο χωρίς ανακτήσιμη λέξη-κλειδί trailer και χωρίς αναγνώσιμο catalog δεν έχει τίποτα στο οποίο να αγκυροβολήσει ένα δέντρο εγγράφου, ανεξάρτητα από το πόσες κεφαλίδες αντικειμένων βρέθηκαν

Οι διπλότυποι αριθμοί αντικειμένων είναι η ενδιαφέρουσα ενδιάμεση περίπτωση. Ένα αρχείο που έχει ενημερωθεί με incremental update περιέχει νόμιμα πολλαπλές generations του ίδιου αριθμού αντικειμένου, και η επιζώσα αλυσίδα cross-reference είναι η μόνη καταγραφή του ποια ήταν η τρέχουσα. Μια ανακατασκευή δεν διαθέτει αυτή την αλυσίδα, οπότε καταγράφει κάθε κεφαλίδα που βλέπει με τη σειρά του αρχείου και επιλύει βάσει αριθμού αντικειμένου εκ των υστέρων. Συνήθως επικρατεί η μεταγενέστερη αναθεώρηση, κάτι που συνήθως είναι σωστό, αλλά ένα έγγραφο που ενημερώθηκε και μετά επαναφέρθηκε εν μέρει μπορεί να επανέλθει διακριτικά διαφορετικό από αυτό που περιέγραφε το αρχικό xref. Τα linearised αρχεία φέρουν την ίδια επιφύλαξη από την αντίθετη κατεύθυνση: η διάταξη της πρώτης σελίδας και οι πίνακες hint είναι χωρίς νόημα μόλις αναγεννηθεί το ευρετήριο, οπότε ένα επιδιορθωμένο αρχείο πρέπει να αντιμετωπίζεται ως απλό, μη linearised έγγραφο

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;

Η εναλλακτική είναι αυτόματη: η PDFlibPas εκτελεί την ακατέργαστη σάρωση όποτε η αλυσίδα cross-reference δεν μπορεί να διαβαστεί, και επίσης όταν κάθε εγγραφή σε χρήση δηλώνει offset μηδέν, κάτι που είναι η υπογραφή ενός πίνακα που γράφτηκε αλλά ποτέ δεν συμπληρώθηκε. Η GetDocumentRepaired επιστρέφει 1 όταν έτρεξε αυτή η διαδρομή, και αξίζει να καταγράφεται αντί να αγνοείται, επειδή ένα έγγραφο που φορτώθηκε μέσω ανακατασκευής θα πρέπει να ξανααποθηκευτεί σε καθαρό αρχείο αντί να μείνει σε ένα pipeline σαν να μη συνέβη τίποτα. Η αποθήκευσή του γράφει έναν φρέσκο, συνεπή πίνακα cross-reference, που είναι η φθηνότερη δυνατή διόρθωση για κάθε κατάντη καταναλωτή

Η διαδρομή ανακατασκευής, η σημαία GetDocumentRepaired και ο streaming loader που παρουσιάζονται εδώ αποτελούν μέρος της PDFlibPas Delphi PDF Library, μαζί με τα APIs ανάλυσης, rendering και υπογραφής που καλύπτονται αλλού σε αυτό το blog