Comment générer et valider efficacement des sommes de contrôle de fichiers?

J'aimerais pouvoir capturer et valider des sommes de contrôle pour des collections de fichiers à grande échelle, généralement imbriquées dans une hiérarchie de répertoires complexes.

Chaque fichier a-t-il besoin d'une somme de contrôle? Existe-t-il des moyens de tirer parti de la structure de répertoires existante pour, par exemple, valider uniquement un nœud dans l'arborescence de fichiers et pas nécessairement tous les fichiers qu'il contient?

Le moyen le plus efficace d'utiliser les sommes de contrôle est de faire en sorte que l'ordinateur fasse tout. Utilisez un système de fichiers tel que ZFS qui somme de contrôle (en fait, il utilise des hachages, qui sont plus forts qu'une somme de contrôle) toutes les données lors de leur écriture, et les vérifie chaque fois que les données sont lues. Bien sûr, l'inconvénient est que ZFS ne sait pas quand la suppression ou l'écrasement d'un fichier est une erreur et quand c'est un fonctionnement normal, mais parce que ZFS utilise la sémantique de copie sur écriture pour tout, vous pouvez utiliser sa fonction d'instantané pour atténuer le risque .

ZFS peut également restaurer automatiquement les données qui échouent à une vérification de hachage en utilisant toute redondance que vous avez configurée, que ce soit la parité de style raid5, des miroirs de lecteur ou des copies en double (ajoutez la propriété copies = N à n'importe quel système de fichiers ZFS et il stockera N copies de toutes les données que vous écrivez). Il stocke également les hachages dans une arborescence Merkle, où la valeur de hachage d'un fichier dépend des hachages des blocs, le hachage d'une entrée de répertoire dépend des valeurs de hachage des fichiers et répertoires qu'il contient, le hachage d'un système de fichiers dépend sur le hachage du répertoire racine, etc.

Quelle que soit la solution avec laquelle vous vous retrouvez, vous constaterez toujours que le processus est limité par la vitesse de vos disques, et non par la vitesse de votre CPU.

N'oubliez pas non plus de prendre en compte le BER de vos disques. Ce ne sont, après tout, que de simples plaques de rouille tournoyante. Un lecteur de niveau consommateur a un taux d'erreur de 1 bit de lecture incorrecte pour chaque 10 ^ 14 bits lus, ce qui correspond à 1 bit sur 11 téraoctets que vous lisez. Si vous avez un ensemble de données de 11 téraoctets et que vous calculez le hachage de chaque fichier qu'il contient, vous aurez calculé une de ces sommes de contrôle de manière incorrecte et endommagé définitivement un bloc de l'un des fichiers de l'ensemble de données. ZFS, cependant, connaît le hachage de chaque bloc qu'il a écrit sur chaque disque de votre pool, et sait donc quel bloc a été perdu. Il peut ensuite utiliser la redondance (parité, miroirs ou copies supplémentaires) dans votre pool pour réécrire les données de ce bloc avec les valeurs correctes.

Ben soulève cependant un bon point dans les commentaires. ZFS n'expose aucune des valeurs de hachage qu'il calcule à l'utilisateur, donc les données qui entrent ou sortent d'un système ZFS doivent être accompagnées de hachages. J'aime la façon dont Internet Archive le fait avec un fichier xml qui accompagne chaque élément de l'archive. Voir https://ia801605.us.archive.org/13/items/fakebook_the-firehouse-jazz-band-fake-book/fakebook_the-firehouse-jazz-band-fake-book_files.xml comme exemple.

Je générerais une somme de contrôle pour chaque fichier. Les sommes de contrôle sont très petites, et la génération de la somme de contrôle pour l'ensemble du répertoire vous obligerait à traiter également chaque fichier (du moins si vous ne parlez pas de la somme de contrôle du répertoire, faite uniquement à partir des entrées du répertoire - je les ferais également, pour vous assurer qu'aucune donnée est supprimé).

Supposons que vous ayez une somme de contrôle pour l'archive entière. Vous savez que les données sont corrompues, mais vous ne savez pas s'il s'agit d'un seul fichier et, plus important encore, lequel. Le fait d'avoir des sommes de contrôle séparées vous donne plus de flexibilité. Vous pouvez détecter un seul fichier qui est corrompu et le remplacer à partir du fichier d'une autre sauvegarde (qui, à son tour, peut avoir un autre fichier corrompu).

De cette façon, vos données sont plus susceptibles de survivre.

C'est peut-être le bon moment pour évoquer BagIt . Il s'agit d'un format d'emballage de fichiers très simple mais puissant destiné à l'archivage, à la conservation à long terme et au transfert d'objets numériques. Les utilisateurs incluent la Library of Congress et la California Digital Library.

Un outil BagIt (ils existent dans plusieurs langages de programmation) place vos fichiers dans une certaine structure de répertoires et fait la somme de contrôle / hachage pour vous. C'est tout.

PS: Bien sûr, les outils BagIt peuvent également vérifier les sacs par rapport aux sommes de contrôle / hachages inclus, et vous pouvez ajouter des métadonnées aux sacs. Mais c'est aussi complexe que les sacs.

Cette réponse est une combinaison de celle de @ lechlukasz et @ db48x , incorporant également certains points soulevés dans les commentaires ainsi que certaines de mes propres pensées.

Le chemin simple à suivre est une approche combinée de système de fichiers et de métadonnées distinctes.

En utilisant un système de fichiers qui effectue le hachage et la validation des données à la volée, comme ZFS ou Btrfs (notez que bien que de grandes avancées aient été faites, Btrfs n'est pas considéré comme prêt pour une utilisation en production pour le moment), vous pouvez être raisonnablement assurez-vous que si les données peuvent être lues sur le disque sans que le système d'exploitation ne fasse d'erreur, alors les données lues ont été écrites sur le disque de la manière prévue par le système de fichiers. En exécutant des opérations de "nettoyage" périodiques, toutes les données sont lues et vérifiées par rapport à l'idée du système de fichiers de ce qu'elles devraient être.

Cependant, cela ne protège que contre la corruption sur le disque (blocs illisibles, erreurs d'écriture matérielle pure et simple, écritures non valides qui corrompent des parties des données directement sur le périphérique de bloc, etc.). Il ne protège pas contre un bogue logiciel, une opération incorrecte de l'utilisateur ou un logiciel malveillant qui fonctionne via les installations du système d'exploitation prévues pour travailler avec des fichiers, en supposant que ces installations sont exemptes de ces bogues.

Pour vous protéger contre ces derniers, vous avez besoin d'une autre couche de protection. Le contrôle de somme ou le hachage des données du point de vue d'une application utilisateur aidera à protéger contre de nombreux risques mentionnés ci-dessus, mais doit être effectué séparément (soit en tant qu'action de processus intégrée dans le logiciel, soit en tant que processus complètement distinct).

Avec le matériel d'aujourd'hui et ce qui est pratique pour stocker de grandes quantités de données (disques durs à plateau tournant par opposition aux disques SSD / SSD), même les algorithmes de hachage complexes tels que SHA1 seront largement liés aux E / S - c'est-à-dire la vitesse à laquelle les données sont hachées sera fonction de la vitesse de lecture du système de stockage, plutôt que de la capacité du processeur de l'ordinateur à calculer le hachage. J'ai fait une expérience avec l'exécution d'un processus de hachage MD5 dans l'espace utilisateur sur environ 150 Go de données sur ce qui était en 2012 un PC grand public, et il s'est terminé après avoir exercé le disque essentiellement sans interruption pendant environ 40 minutes. En multipliant par 100 ces chiffres, vous obtiendrez les hachages MD5 d'une collection de 15 To en environ trois jours sur ce même matériel. En ajoutant le taux de transfert de lecture (qui peut être facilement réalisé, par exempleRAID 0, par exemple, est un striping sans redondance, couramment utilisé pour obtenir des performances de lecture / écriture plus élevées, éventuellement en combinaison avec RAID 1 formant RAID 10 ), le temps jusqu'à la fin peut être réduit pour la même quantité de données.

En combinant les deux, vous obtenez le meilleur des deux mondes: le système de fichiers vous donne l'assurance que ce que vous avez reçu lors de la lecture du fichier est ce qui a été réellement écrit, et un processus de vérification de la fixité distinct peut s'exécuter sur l'ensemble de la collection, garantissant que les données stocké correspond toujours à ce qui a été ingéré dans l'archive. Toute incohérence entre les deux (le système de fichiers dit que le fichier est OK, la vérification de la fixité dit que ce n'est pas le cas) indiquera un fichier qui a été modifié en dehors du mode de fonctionnement prévu de l'archive mais à partir des installations du système d'exploitation, provoquant une restauration à partir d'un secondaire copie (sauvegarde). Le contrôle de fixité peut ainsi s'exécuter à un intervalle de temps plus long, ce qui devient essentiel pour les très grandes archives, mais tous les accès en ligne sont toujours garantis de ne pas être corrompus sur le matériel si les lectures réussissent. En principe, le logiciel d'archivage pourrait s'appuyer sur le système de fichiers pour signaler les incohérences en tant qu'erreurs de lecture et effectuer une vérification de la fixité distincte en arrière-plan pendant que l'utilisateur travaille avec le fichier et affiche un message approprié si cela indique que le fichier ne correspond pas à ce qui a été ingéré dans l'archive. En utilisant un système de fichiers de hachage de blocs, un tel schéma aurait un impact minimal sur les performances perçues tout en garantissant que le contenu est correct.

J'ai parcouru les réponses, et même si j'aime l'idée de s'appuyer sur ZFS pour gérer les erreurs de la couche de données, il y a toujours le problème de la modification des fichiers, par erreur ou par malveillance. ZFS ne vous protégera pas dans ce cas, et comme quelqu'un d'autre l'a mentionné, il ne vous donnera pas un "hachage" visible par l'utilisateur pour le stocker ailleurs pour une validation externe.

Il existe une application Linux appelée TripWire qui a été largement utilisée pour surveiller les exécutables du système, pour valider qu'ils n'ont pas été modifiés après une attaque. Ce projet est apparemment maintenant abandonné, mais il y en a un nouveau appelé AIDE (Advanced Intrusion Detection Environment), recommandé sur ServerFault:

/server/62539/tripwire-and-alternatives

Lors de l'installation, il s'exécutait toutes les x minutes, configurable par l'utilisateur et vérifiait tous les dossiers que vous spécifiez pour les modifications dans les fichiers. Il doit s'exécuter une fois pour calculer tous les hachages de fichier, puis après cela, il vérifie tous les hachages par rapport au fichier actuel et s'assure qu'ils sont toujours les mêmes. Vous pouvez spécifier le type de hachage ou la combinaison de hachages à utiliser (je ne recommanderais rien de plus faible que SHA-256), les attributs de fichier à utiliser (contenu, taille, horodatage modifié, etc.), la fréquence à laquelle il vérifie, comment / où stocker la base de données de hachage, etc.

Certains pourraient considérer cette exagération, mais selon les exigences du PO, cela pourrait lui donner plus de tranquillité d'esprit que les données qu'il stocke resteront les mêmes après un certain temps.

Les Archives nationales d'Australie ont développé [Checksum Checker] ( http://checksumchecker.sourceforge.net/ ) qui est disponible gratuitement sous GPLv3.

Il lit une somme de contrôle et un algorithme dans une base de données, puis recalcule la somme de contrôle du fichier, compare les deux valeurs et signale s'il y a une erreur. Il prend en charge les algorithmes MD5, SHA1, SHA2, SHA256 et SHA512.

D'autres logiciels dans leur référentiel numérique [DPR] ( http://dpr.sourceforge.net/ ) génèrent la somme de contrôle initiale (ainsi que toutes les autres activités de traitement)