Domanda: È Checksum o CRC meglio per controllare i dati scritti su unità flash USB?

Questo post offre una panoramica semplice per capire quale metodo di verifica è migliore quando si scrivono dati su una chiavetta USB. In fondo trovi collegamenti di riferimento che approfondiscono entrambi i metodi se questa introduzione non è sufficiente.

Risposta breve: il Controllo di Ridondanza Ciclica (CRC) è generalmente il metodo migliore per verificare i dati scritti su un’unità flash USB.

Molti pensano che un checksum sia la scelta migliore (il più popolare è l’MD5) perché è più semplice da comprendere e da implementare. Tuttavia, la verifica basata su checksum presenta difetti e, per questo, non è ideale per convalidare i dati scritti su una chiavetta USB.

Qual è la differenza tra somma di controllo e verifica CRC? Il metodo checksum usa l’addizione nei calcoli matematici per verificare se tutti i dati sono stati scritti correttamente. Il CRC usa la divisione lunga binaria nei propri calcoli per determinare la correttezza dei dati.

I metodi basati su checksum contano i bit totali in un pacchetto di dati e includono tale somma quando i dati vengono trasmessi. Il ricevitore legge il valore di checksum e ripete il calcolo per verificare che tutto torni. Anche quando i totali coincidono, esiste un’elevata probabilità che durante la trasmissione alcuni bit siano cambiati o scambiati, producendo comunque un valore “corretto” al termine del calcolo.

In termini molto semplici: immagina un bidone con arance e mele rosse spedito da Los Angeles a New York. Si conta tutto prima della spedizione, ma lungo il percorso alcune mele rosse vengono sostituite con mele verdi. All’arrivo il numero totale di frutti è lo stesso, ma il ricevitore non sa che dovevano essere solo mele rosse. Il checksum “torna”, ma il contenuto effettivo è cambiato.

Il CRC è altrettanto “semplice” come concetto di aggiunta, ma utilizza la divisione lunga. Il vantaggio è che “guarda” l’intero pacchetto per confermare l’integrità, invece di affidarsi a una somma totale. Come nella divisione lunga tradizionale, la divisione binaria opera sul dividendo usando il divisore.

Poiché il CRC è più complesso da spiegare, riprendiamo l’esempio delle mele e arance: questa volta frutti su vassoi (come in una scatola di uova), impilati ordinatamente. Il manifesto specifica numero di strati, quantità e colori. All’arrivo, il ricevitore può verificare facilmente sia gli strati che la composizione: non solo il totale, ma anche la struttura—proprio come fa il CRC sull’intero pacchetto.

Nel calcolo CRC si sceglie un polinomio/divisore “dato”. Si aggiungono alla fine del pacchetto tanti zeri quanto la lunghezza del divisore meno uno e si esegue la divisione binaria lunga. Si ottiene un resto: la parte “ciclica” consiste nel sostituire quei bit finali con il resto, cosicché alla verifica (nuova divisione) il resto risulti zero se non ci sono errori. In questo modo, tutti i bit del pacchetto vengono effettivamente considerati.

Un aiuto visivo rende tutto più chiaro; osserva i grafici seguenti e il processo avrà più senso.

La scelta del metodo di verifica nella trasmissione dati nasce spesso dal “rumore” sulle linee, non da attacchi intenzionali. Il rumore può derivare da cattivo design elettrico (per esempio PCB della chiavetta), messa a terra insufficiente (molte chiavette usano due PCB, ma la specifica USB indica PCB a quattro strati), o materiali scadenti. Con un metodo affidabile come il CRC, il ricevitore può determinare con maggiore confidenza se i dati sono stati inviati e ricevuti correttamente.

Fonte: Grazie agli ingegneri Nexcopy Inc. per aver reso accessibile un argomento tecnico complesso.

Riferimenti:

• Binary Long Division
  https://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html
• Definizioni CRC (Wikipedia)
  https://en.wikipedia.org/wiki/Cyclic_redundancy_check
• Teoria e codice CRC in C/C++ (Barr Group)
  https://www.barrgroup.com/Embedded-Systems/How-To/CRC-Math-Theory

Penso che abbiamo tutti sentito dire che una chiavetta USB può essere utilizzata solo un certo numero di volte. Alcuni dicono 1.000 scritture, altri 100.000. Una cosa è certa: è impossibile stabilirlo per un dispositivo specifico. Il ciclo di vita di una USB è direttamente correlato alla memoria flash e, da modello a modello o da formato a formato, è difficile sapere quale sia la qualità della flash impiegata. Detto questo, possiamo spiegare la teoria per far durare le unità USB più a lungo. Per lo più si riduce a due elementi: (a) tipo e qualità della memoria e (b) tecnica di wear leveling (livellamento dell’usura).

Come breve riepilogo, la flash NAND in una USB può essere SLC, MLC o TLC (Single-Level Cell, Multi-Level Cell o Triple-Level Cell). Oggi, nella maggior parte delle chiavette USB si trovano MLC e TLC; SLC si vede, ma in genere su dispositivi di fascia alta.

Il wear leveling è una tecnica per prolungare la durata della memoria flash cancellabile. In sintesi, la memoria flash è composta da segmenti/celle cancellabili che possono essere impostati su 0 o 1 (carica positiva o negativa). Tuttavia, dopo un certo numero di cicli di cancellazione e scrittura, una cella diventa troppo instabile per un uso affidabile.

Il livellamento dell’usura è l’algoritmo usato dal controller del dispositivo per distribuire in modo uniforme cancellazioni e scritture su tutto il supporto flash. Tipicamente la flash può avere tra 3.000 e 5.000 cicli di cancellazione/scrittura. Oltre all’area utile, la flash dispone anche di celle di riserva (blocchi specifici a vita estesa) che possono gestire fino a ~100.000 scritture. Qui il controller ri-mappa i segmenti logori verso le celle migliori da usare durante i cicli di cancellazione/scrittura.

Esistono tre tipi di livellamento dell’usura:

Nessun wear leveling

Un sistema di storage flash senza wear leveling non durerà a lungo se si scrivono spesso dati. Senza livellamento, il controller assegna in modo permanente gli indirizzi logici dell’host agli indirizzi fisici della flash. Ogni riscrittura di un blocco già scritto richiede lettura, cancellazione, modifica e riscrittura nella stessa posizione: processo dispendioso e concentrato sempre sugli stessi blocchi, che si usurano rapidamente mentre altre aree restano inutilizzate. Quando alcuni blocchi raggiungono fine vita, l’unità non è più operabile.

Wear leveling dinamico

Il primo tipo sviluppato è il wear leveling dinamico: utilizza una mappa che collega gli indirizzi di blocco logici dell’host alla flash fisica. Quando l’host riscrive dati, la mappa si aggiorna: il blocco fisico originale viene marcato come invalido e a quella voce si assegna un nuovo blocco. Ogni volta che un blocco viene riscritto, finisce in una posizione fisica diversa.

Wear leveling statico

Il wear leveling statico usa anch’esso una mappa, ma sposta periodicamente anche i blocchi “freddi” (pochi cambiamenti) così che le celle poco usate possano essere impiegate da altri dati. Questo effetto di rotazione consente al supporto di operare finché la maggior parte dei blocchi non si avvicina alla fine vita, massimizzando la longevità USB Flash con wear leveling.

Oltre ai tre approcci di wear leveling, ci sono tre tecniche generali per prolungare la vita di un drive USB:

• Correzione degli errori (ECC): codice che rileva/corregge errori e registra i blocchi danneggiati, evitando il riutilizzo in scritture future.
• Pool di riserva (spare blocks): se una scrittura fallisce su un blocco, i dati vengono reindirizzati a un blocco di riserva sano.
• Monitoraggio dell’utilizzo: tenere traccia dei blocchi meno utilizzati di recente; anche le strutture di dati della coda devono essere oggetto di wear leveling poiché cambiano continuamente.

Fonti: Wikipedia – Wear leveling e Nexcopy Inc., produttore di duplicatori USB.