Wie kann ich Dateiprüfsummen effizient generieren und validieren?

12

Ich möchte in der Lage sein, Prüfsummen für große Dateisammlungen zu erfassen und zu validieren, die normalerweise in einer komplexen Verzeichnishierarchie verschachtelt sind.

Benötigt jede einzelne Datei eine Prüfsumme? Gibt es Möglichkeiten, die vorhandene Verzeichnisstruktur zu nutzen, um beispielsweise nur einen Knoten im Dateibaum und nicht unbedingt jede Datei innerhalb zu validieren?

Aaron Rubinstein
quelle
In den Antworten wird darauf hingewiesen, dass es wichtig ist, die Art der Bedrohung, die Sie abschwächen, und die Prüfsumme entsprechend zu unterscheiden. Eine frühere Antwort auf den Stapel "Bibliothek und Informationswissenschaft", die ich beigesteuert habe, könnte von Interesse sein, obwohl es hauptsächlich um HDFS geht.
Andy Jackson

Antworten:

13

Die effizienteste Methode zur Verwendung von Prüfsummen besteht darin, den Computer dazu zu bringen, alles zu tun. Verwenden Sie ein Dateisystem wie ZFS, dessen Prüfsummen (tatsächlich werden Hashes verwendet, die stärker als eine Prüfsumme sind) alle Daten beim Schreiben und bei jedem Lesen der Daten überprüfen. Der Nachteil ist natürlich, dass ZFS nicht weiß, wann das Löschen oder Überschreiben einer Datei ein Fehler ist und wann der normale Vorgang ausgeführt wird. Da ZFS jedoch für alle Aufgaben eine Schreibkopie-Semantik verwendet, können Sie das Risiko mithilfe der Snapshot-Funktion verringern .

ZFS kann auch automatisch Daten wiederherstellen, die eine Hash-Prüfung nicht bestehen, indem eine von Ihnen eingerichtete Redundanz verwendet wird, unabhängig davon, ob es sich um eine Parität im RAID5-Stil, Laufwerksspiegelungen oder doppelte Kopien handelt Daten, die Sie schreiben). Es speichert auch die Hashes in einem Merkle-Baum, wobei der Hash-Wert einer Datei von den Hashes der Blöcke abhängt, der Hash eines Verzeichniseintrags von den Hash-Werten der darin enthaltenen Dateien und Verzeichnisse abhängt und der Hash eines Dateisystems abhängt auf dem Hash des Stammverzeichnisses usw.

Unabhängig davon, für welche Lösung Sie sich entscheiden, werden Sie immer feststellen, dass der Prozess durch die Geschwindigkeit Ihrer Festplatten und nicht durch die Geschwindigkeit Ihrer CPU begrenzt ist.

Vergessen Sie auch nicht, die BER Ihrer Festplatten zu berücksichtigen. Sie sind schließlich bloße Rostplatten. Ein Consumer-Laufwerk hat eine Fehlerrate von 1 falsch gelesenen Bit pro 10 ^ 14 gelesenen Bits, was 1 Bit pro 11 gelesenen Terabyte entspricht. Wenn Sie einen 11-Terabyte-Datensatz haben und den Hash jeder Datei darin berechnen, haben Sie eine dieser Prüfsummen falsch berechnet und einen Block einer der Dateien im Datensatz dauerhaft beschädigt. ZFS kennt jedoch den Hash jedes Blocks, den es auf jeden Datenträger in Ihrem Pool geschrieben hat, und weiß daher, welcher Block verloren gegangen ist. Es kann dann die Redundanz (Parität, Spiegel oder zusätzliche Kopien) in Ihrem Pool verwenden, um die Daten in diesem Block mit den richtigen Werten neu zu schreiben.

Ben bringt jedoch einen guten Punkt in den Kommentaren vor. ZFS macht keine der vom Benutzer berechneten Hash-Werte verfügbar. Daten, die in ein ZFS-System eingegeben werden oder dieses verlassen, sollten daher von Hashes begleitet werden. Ich mag die Art und Weise, wie das Internetarchiv dies mit einer XML-Datei durchführt, die jedem Element im Archiv beiliegt. Siehe https://ia801605.us.archive.org/13/items/fakebook_the-firehouse-jazz-band-fake-book/fakebook_the-firehouse-jazz-band-fake-book_files.xml als Beispiel.

db48x
quelle
1
Du warst schneller als ich. Ich wollte auch ein Hash-basiertes System vorschlagen. Hash jede Datei, Hash die Datei-Hashes (+ Unterverzeichnis-Hashes) für ein Verzeichnis-Hash etc .. Der Kompromiss ist CPU / IO vs Fehlerwahrscheinlichkeit. Prüfsumme / CRC ist günstig, aber die Fehlerwahrscheinlichkeit steigt mit der Skalierung. Häufig verwendete Hashes beginnen jedoch mit einer viel geringeren Fehlerwahrscheinlichkeit.
The Diamond Z
3
Selbst wenn Sie ein Dateisystem wie ZFS ausführen (Btrfs verfügt ebenfalls über ähnliche Funktionen, befindet sich jedoch noch in der Entwicklung und wird derzeit nicht als produktionsbereit angesehen), müssen Sie einen regelmäßigen "Scrub" -Vorgang durchführen, um sicherzustellen, dass die Daten vorhanden sind gelesen und gegen die Prüfsummen oder Hashes überprüft. Nur Prüfsummen zu berechnen und dann nichts damit zu tun, bis Sie Zugriff auf die Daten benötigen , ist möglicherweise schlimmer als wertlos.
ein Lebenslauf vom
1
Ja, das ist ein guter Punkt. Mein letztes Scrub behebt 2 Kilobyte an Daten, die fehlerhaft geworden sind. Das sind vier Blöcke verteilt auf fünf Laufwerke! Je länger Sie zwischen den Lesevorgängen eines bestimmten Datenelements verweilen, desto höher ist die Wahrscheinlichkeit, dass Sie in einer einzelnen Datei genügend Fehler ansammeln, die nicht wiederhergestellt werden können.
1
Das Ausführen eines Userspace md5sum über ungefähr 150 GB Daten auf meinem Heim-PC dauerte ungefähr 40 Minuten, rein I / O-gebunden. Wenn wir das 100-fache skalieren, werden innerhalb von drei Tagen 15 TB auf Consumer-Hardware überprüft . Ich würde das sicherlich auch für ein großes Archiv mit einem richtig ausgewählten Intervall für machbar halten.
ein
3
ZFS berechnet Prüfsummen für Blöcke, nicht für Dateien oder Bitstreams, nein? Während ZFS das Rechenproblem löst, scheint es weniger überprüfbar zu sein und keine Fixity-Daten zu produzieren, die unabhängig vom Dateisystem portierbar sind - ein Muss für Archive.
6

Ich würde für jede Datei eine Prüfsumme generieren. Prüfsummen sind sehr klein, und das Generieren einer Prüfsumme für das gesamte Verzeichnis würde erfordern, dass Sie auch jede Datei verarbeiten (zumindest, wenn Sie nicht über eine Verzeichnisprüfsumme sprechen, die nur aus Verzeichniseinträgen besteht - ich würde sie auch erstellen, um sicherzustellen, dass keine Daten vorhanden sind ist gelöscht).

Angenommen, Sie haben eine Prüfsumme für das gesamte Archiv. Sie wissen, dass die Daten beschädigt sind, aber Sie wissen nicht, ob dies nur eine Datei ist und, was noch wichtiger ist, welche. Durch separate Prüfsummen erhalten Sie mehr Flexibilität. Sie können eine einzelne Datei erkennen, die beschädigt ist, und diese durch eine Datei aus einer anderen Sicherung ersetzen (bei der wiederum eine andere Datei beschädigt sein kann).

Auf diese Weise überleben Ihre Daten mit größerer Wahrscheinlichkeit.

Donau Seemann
quelle
Das macht sicherlich Sinn. Ich frage mich nur, welche Strategien es gibt, um das rechenintensive Kunststück zu meistern, Hunderttausende von Prüfsummen zu generieren und zu prüfen.
4

Vielleicht ist dies ein guter Zeitpunkt, um BagIt aufzurufen . Dies ist ein sehr einfaches und dennoch leistungsstarkes Dateiverpackungsformat, das für die Archivierung, Langzeitarchivierung und Übertragung digitaler Objekte vorgesehen ist. Zu den Nutzern zählen die Library of Congress und die California Digital Library.

Ein BagIt-Tool (es gibt es in mehreren Programmiersprachen) legt Ihre Dateien in einer bestimmten Verzeichnisstruktur ab und führt die Prüfsumme / das Hashing für Sie aus. Das ist alles.

PS: Natürlich können BagIt-Tools auch Taschen anhand der enthaltenen Prüfsummen / Hashes überprüfen, und Sie können Taschen einige Metadaten hinzufügen. Aber das ist so komplex wie Taschen.

Christian Pietsch
quelle
1

Diese Antwort ist eine Kombination aus @ lechlukasz und @ db48x , die auch einige Punkte aus Kommentaren sowie einige meiner eigenen Gedanken enthält.

Der einfache Weg nach vorne ist ein kombinierter Ansatz aus Dateisystem und separaten Metadaten.

Wenn Sie ein Dateisystem wie ZFS oder Btrfs verwenden, das Daten-Hashing und -Validierung im laufenden Betrieb ausführt (beachten Sie, dass Btrfs zwar große Fortschritte erzielt hat, aber derzeit noch nicht als produktionsbereit eingestuft wird), können Sie vernünftig sein Stellen Sie sicher, dass, wenn die Daten von der Festplatte gelesen werden können, ohne dass das Betriebssystem einen Fehler macht, die gelesenen Daten in der vom Dateisystem vorgesehenen Weise auf die Festplatte geschrieben wurden. Durch Ausführen von periodischen "Scrub" -Operationen werden alle Daten gelesen und mit der Vorstellung des Dateisystems verglichen, wie sie sein sollten.

Dies schützt jedoch nur vor einer Beschädigung der Festplatte (unlesbare Blöcke, direkte Hardwareschreibfehler, ungültige Schreibvorgänge, die Teile der Daten direkt auf dem Blockgerät beschädigen usw.). Es schützt nicht vor einem Softwarefehler, einer fehlerhaften Benutzeroperation oder bösartiger Software, die über die vorgesehenen Betriebssystemeinrichtungen zum Arbeiten mit Dateien funktioniert, vorausgesetzt, diese Einrichtungen sind frei von solchen Fehlern.

Zum Schutz vor letzterem benötigen Sie eine weitere Schutzschicht. Prüfsummen- oder Hashing-Daten aus Sicht einer Benutzeranwendung schützen vor vielen der oben genannten Risiken, müssen jedoch separat ausgeführt werden (entweder als integrierte Prozessaktion in der Software oder als vollständig separater Prozess).

Mit der heutigen Hardware und den praktischen Funktionen zum Speichern großer Datenmengen (Festplatten mit rotierendem Plattenteller im Gegensatz zu Solid-State-Festplatten / SSDs) sind selbst komplexe Hashing-Algorithmen wie SHA1 weitgehend E / A-gebunden - das heißt, die Geschwindigkeit Die Geschwindigkeit, mit der die Daten gehasht werden, hängt von der Lesegeschwindigkeit des Speichersystems ab und nicht von der Fähigkeit des Computerprozessors, den Hash zu berechnen. Ich habe ein Experiment mit einem MD5-Hashing-Prozess auf Benutzerbasis mit einer Datenmenge von ca. 150 GB auf einem Mid-Tier-Consumer-PC im Jahr 2012 durchgeführt und es wurde beendet, nachdem die Festplatte im Wesentlichen ohne Unterbrechung etwa 40 Minuten lang getestet worden war. Wenn Sie diese Zahlen auf das 100-fache skalieren, erhalten Sie die MD5-Hashes einer 15-TB-Sammlung in ungefähr drei Tagen auf derselben Hardware. Durch Hinzufügen der Leseübertragungsrate (die leicht erreicht werden kann, zRAID 0 ist beispielsweise Striping ohne Redundanz und wird häufig verwendet, um eine höhere Lese- / Schreibleistung zu erzielen, möglicherweise in Kombination mit RAID 1 ( RAID 10 ). Die Zeit bis zur Fertigstellung kann bei gleicher Datenmenge verkürzt werden.

Wenn Sie beides kombinieren, erhalten Sie das Beste aus beiden Welten: Das Dateisystem gibt Ihnen die Gewissheit, dass das, was Sie beim Lesen der Datei erhalten haben, das tatsächlich Geschriebene ist, und ein separater Fixitätsprüfungsprozess kann die gesamte Sammlung durchlaufen, um sicherzustellen, dass die Daten vorhanden sind gespeichert stimmt noch mit dem überein, was in das Archiv aufgenommen wurde. Jegliche Inkonsistenz zwischen beiden (Dateisystem sagt, dass die Datei in Ordnung ist, Fixitätsprüfung sagt, dass dies nicht der Fall ist) weist auf eine Datei hin, die außerhalb des beabsichtigten Betriebsmodus des Archivs, jedoch innerhalb der Einrichtungen des Betriebssystems geändert wurde, wodurch eine Wiederherstellung von einem sekundären System veranlasst wird kopieren (sichern). Der Fixity Check kann somit in einem längeren Zeitintervall durchgeführt werden, was für sehr große Archive unabdingbar ist. Bei einem erfolgreichen Lesevorgang ist jedoch sichergestellt, dass Online-Zugriffe auf der Hardware nicht verfälscht werden. Allgemein gesagt, Die Archivierungssoftware kann sich darauf verlassen, dass das Dateisystem Inkonsistenzen als Lesefehler meldet und im Hintergrund eine separate Fixitätsprüfung durchführt, wenn der Benutzer mit der Datei arbeitet und eine entsprechende Meldung anzeigt, die darauf hinweist, dass die Datei nicht mit der aufgenommenen Datei übereinstimmt in das Archiv. Bei Verwendung eines Block-Hashing-Dateisystems würde ein solches Schema nur minimale Auswirkungen auf die wahrgenommene Leistung haben und dennoch sicherstellen, dass der Inhalt korrekt ist.

ein CVn
quelle
1

Ich habe die Antworten durchgearbeitet, und obwohl mir die Idee gefällt, mich auf ZFS zu verlassen, um die Datenebenenfehler zu behandeln, gibt es immer noch das Problem, dass die Dateien versehentlich oder in böswilliger Absicht geändert werden. ZFS schützt Sie in diesem Fall nicht und gibt Ihnen, wie bereits erwähnt, keinen vom Benutzer sichtbaren "Hash", der zur externen Validierung an einer anderen Stelle gespeichert werden kann.

Es gibt eine Linux-Anwendung namens TripWire, die ausgiebig zur Überwachung von ausführbaren Systemdateien verwendet wurde, um sicherzustellen, dass sie nach einem Angriff nicht geändert wurden. Dieses Projekt wurde anscheinend jetzt aufgegeben, aber es gibt ein neues AIDE (Advanced Intrusion Detection Environment), das unter ServerFault empfohlen wird:

/server/62539/tripwire-and-alternatives

Bei der Installation wird es alle x Minuten ausgeführt, benutzerdefiniert, und es werden alle von Ihnen angegebenen Ordner auf Änderungen in den Dateien überprüft. Es muss einmal ausgeführt werden, um alle Datei-Hashes zu berechnen. Anschließend werden alle Hashes mit der aktuellen Datei verglichen und sichergestellt, dass sie immer noch identisch sind. Sie können angeben, welche Art von Hash oder Kombination von Hashes verwendet werden soll (ich würde nichts Schwächeres als SHA-256 empfehlen), welche Dateiattribute verwendet werden sollen (Inhalt, Größe, modifizierter Zeitstempel usw.), wie oft geprüft wird, wie / wo die Hash-Datenbank usw. gespeichert werden soll

Einige mögen diesen Overkill in Betracht ziehen, aber je nach den Anforderungen des OP kann er sich sicherer fühlen, dass die von ihm gespeicherten Daten nach einer bestimmten Zeit gleich bleiben.

mjuarez
quelle
0

Das National Archives of Australia hat den [Checksum Checker] ( http://checksumchecker.sourceforge.net/ ) entwickelt, der unter der GPLv3 frei verfügbar ist.

Es liest eine Prüfsumme und einen Algorithmus aus einer Datenbank, berechnet dann die Prüfsumme für die Datei neu, vergleicht die beiden Werte und meldet, ob ein Fehler vorliegt. Es unterstützt die Algorithmen MD5, SHA1, SHA2, SHA256 und SHA512.

Andere Software in ihrem digitalen Repository [DPR] ( http://dpr.sourceforge.net/ ) generiert die anfängliche Prüfsumme (sowie alle anderen Verarbeitungsaktivitäten).

John Lovejoy
quelle