Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

Algorytm sprawdzanie integralności danych w zewnętrznej pamięci FLASH

spanko 09 Mar 2016 18:10 729 17
  • #1 09 Mar 2016 18:10
    spanko
    Poziom 11  

    Witam
    Chciałbym umieścić w programie funkcję sprawdzającą dane zapisane w zewnętrznej pamięci Flash/ Eeprom. Wyczytałem że dobrym sposobem jest sprawdzanie sumy kontrolnej CRC, i tak też chciałem zrobić, tylko nie do końca wiem jak taki algorytm powinien wyglądać. Ja myślę że powinno to wyglądać tak:
    Dzielę sobie obszar pamięci na bloki każdy blok po x bajtów.
    Zapisuję bloki danych i na końcu każdego bloku umieszczam 1,2, lub 4 bajty sumy kontrolnej (w zależności czy będę używał crc8, crc16 czy crc32).
    sprawdzanie polegało by na cyklicznym ( raz na jakiś czas) odczycie jednego bloku przeliczeniu sumy kontrolnej i porównaniu z odczytaną tam sumą kontrolną.

    Czy takie moje rozumowanie jest dobre czy może powinno się to robić w inny sposób.
    Jeszcze takie pytanie czy są jakieś inne algorytmy sprawdzania poprawności danych zapisanych w zewnętrznych pamięciach flash/eeprom ?

    Pozdrawiam

    0 17
  • Pomocny post
    #2 09 Mar 2016 18:13
    tmf
    Moderator Mikrokontrolery Projektowanie

    Tak, takie rozumowanie jest ok. Zamiast CRC możesz zastosować inne sposoby, jednak złożoność obliczeniowa może być istotnie wyższa. CRC z kolei część procków liczy sprzętowo.

    0
  • #4 09 Mar 2016 21:48
    spanko
    Poziom 11  

    Dziękuje za szybką odpowiedź
    W swojej aplikacji chciałem wykorzystać jakiegoś stm32 więc bœdę mógł skorzystać ze sprzętowego CRC

    tmf

    mógłbyś podać jakie inne sposoby można stosować do sprawdzania integralności ?
    Słyszałem jeszcze o March C ale to wymaga zapisu komórki więc nie bardzo wg mnie nadaje się do pamięci Flash.



    Pozdrawiam

    0
  • #6 09 Mar 2016 22:00
    tmf
    Moderator Mikrokontrolery Projektowanie

    Np. funkcje skrótu - MD5, SHA. Służą one zazwyczaj do nieco innych celów, ale ponieważ jakakolwiek zmiana danych całkowicie zmienia wynik funkcji skrótu, więc moża je wykorzystać do kontroli integralności danych. Tyle, że zazwyczaj procki ich nie liczą sprzętowo, a złożoność obliczeniowa jest znacznie większa niż dla CRC. Potencjalnie jednak zabezpieczenie przez MD5 lub SHA jest lepsze, CRC nie wyłapie wszystkich błędów, no i jest większa szansa kolizji.

    0
  • #7 09 Mar 2016 22:05
    grko
    Poziom 32  

    @spanko Dla jakiej wielkości bloków danych będziesz liczył to CRC i jakie sa konsekwencje tego jak nasz algorytm będzie miał kolizję (policzy właściwe crc dla błędnego bloku)?Bo naprawdę do 90% zastosowań wystarczy crc-16.

    0
  • #8 09 Mar 2016 22:20
    spanko
    Poziom 11  

    Dziękuję za te informacje.
    temat zostawię na parę dni jeszcze otwarty jak by ktoś chciał coś sensownego dopisać.

    Grzegorz Kostka

    Wielkość danych bloków nie jest jeszcze dokładnie sprecyzowana, będą tam przechowywane wartości różnych ustawień bardziej i mniej ważne dla działania programu, ale jak już wspomniałem najprawdopodobniej będę używał stm32 a one(nie wiem czy wszystkie bo dokładnie ich nie przejrzałem)posiadają sprzętowy CRC32. Jeżeli jednak nie będę mógł użyć sprzętowego crc dokładniej przeanalizuje, które crc użyje.

    Pozdrawiam

    0
  • #9 09 Mar 2016 22:22
    vonar
    Poziom 28  

    Do kontroli integralności mogą też służyć funkcje MAC (np. szyfr blokowy w trybie CBC-MAC) i kody korekcyjne (ECC).

    Funkcje mieszające w kontroli przypadkowych błędów wygrywają z CRC przede wszystkim ze względu na swoją długość - popularne CRC właściwie kończą się na 32 bitach, a sensowny hash to 128 bitów w górę.

    0
  • #10 10 Mar 2016 22:47
    2675900
    Użytkownik usunął konto  
  • #11 10 Mar 2016 23:30
    grko
    Poziom 32  

    Cytat:

    W rakiecie balistycznej moze i tak lub reaktorze jądrowym czy statku kosmicznym


    Nie do końca. MD5 oraz SHA1 są powszechnie stosowane do weryfikacji integralności danych. SHA1 wykorzystywany min przez Gita jest tak dobry, że nie znaleziono jeszcze 2 wiadomości, które mają taki sam 160bitowy hash. Więc jak autor chce mieć absolutną (prawie ;)) pewność tego co mu siedzi w pamięci FLASH to powinien wybrać jeden z tych algorytmów.

    0
  • #12 11 Mar 2016 00:00
    2675900
    Użytkownik usunął konto  
  • #13 11 Mar 2016 09:55
    tmf
    Moderator Mikrokontrolery Projektowanie

    @Piotrus_999 CRC16 jest dosyć słabe. Wymiana więcej niż 16 bitów może pozostać niezauważona, a prawdopodobieństwo że dwa ciągi mają to samo CRC też jest spore. CRC to prosta i szybka w liczeniu funkcja i z tego powodu jest stosowana. Nie znaczy to, że jest zła, znaczy tylko, że trzeba sobie zdawać sprawę z ograniczeń. Jeśli np. 0,2% prawdopodobieństwo niezauważenia uszkodzenia danych jest akceptowalne to nie ma problemu. Z drugiej strony MD5 czy SHA dają prawdopodobieństwo graniczące z pewnością, że jakakolwiek zmiana danych zmieni wartość funkcji skrótu. Dla 32-bitowego procka (a nawet dla 8-bitowego) policzenie funkcji skrótu dla danych w FLASH/EEPROM to nie jest żadne obciążenie, biblioteki są gotowe więc czemu nie skorzystać...

    0
  • #14 11 Mar 2016 10:41
    grko
    Poziom 32  

    Cytat:

    Zgadzam się.
    No ale tu przyczyna jest nieco inna (dzałalnosc złych ludzi :))

    Raczej ingerencji hackerów w EEPROM czy FLASH sie nie spodziewamy.


    Wydaje mi się, że nie rozumiesz. SHA1/MD5 nie są stosowane do szyfrowania tylko do weryfikacji integralności danych. SHA1 w Gicie nie chroni przed atakiem hakierów tylko pozwala wykryć wszelkiego rodzaju uszkodzenia danych.

    0
  • #15 11 Mar 2016 11:10
    2675900
    Użytkownik usunął konto  
  • #16 11 Mar 2016 11:23
    Eagle
    Poziom 23  

    " 0,2% prawdopodobieństwo niezauważenia uszkodzenia danych jest akceptowalne"

    Możesz wyjaśnić jak dla CRC16 wyszło 0,2%

    Mając pakiet n bajtów + CRC16, musisz zmienić 16 bitów aby CRC16 ponowienie się zgadzało, więc jest 1/ 2^16
    więc prawdopodobieństwo niewykrycia jest : 0,0015%

    Przecież CRC16 oparty na wielomianie, nie jest prymitywną sumą danych czy XOR.
    Jeśli to nie wystarczy, można użyć CRC32, jednak autor musiałby ocenić prawdopodobieństwo i częstotliwość zakłóceń.

    Innym aspektem, który należałoby rozwiązać to sprawa atomowości, tz.
    - zapisałeś parametry wraz z prawidłową sumą CRC
    - dokonujesz zmiany parametrów, jednak przed zapisaniem CRC następuje nieoczekiwany reset. Wówczas w pamięci masz cześć danych nowych, cześć starych i niepasującą do wszystkiego CRC.

    Typowo taką trakcyjność robi się w następujący sposób:
    - w pamięci przechowujesz dwie kopie danych z CRC
    - podczas aktualizacji aktualizujesz pierwszą kopię
    - jeśli powiodło się kopiujesz pierwszą kopię do drugiej.

    Podczas odczytu, odczytujesz zawsze pierwszą kopię, jeśli jest uszkodzona to odtwarzasz dane z drugiej - ostatnia transakcja została przerwana.
    Jeśli pierwsza kopia jest poprawna i druga jest poprawna to nowsza jest pierwsza, więc należy ją skopiować do drugiej, podobnie jeśli druga jest uszkodzona przy pierwszej dobrej.
    Nie ma przypadku, w którym możliwe są uszkodzenie obu kopii, wykluczając wady pamięci.

    0
  • #17 11 Mar 2016 11:49
    vonar
    Poziom 28  

    Eagle napisał:
    Mając pakiet n bajtów + CRC16, musisz zmienić 16 bitów aby CRC16 ponowienie się zgadzało

    Te wszystkie liczby są z kosmosu wzięte.
    Obliczenie prawdopodobieństwa wystąpienia nie wykrytego błędu nie jest takie proste. Mogą wystarczyć nawet dwa (!) bity, zależy od wielomianu i długości wiadomości. Do tego w realnej sytuacji błędy niekoniecznie są doskonale przypadkowe, a stopa błędów medium może być trudna do oszacowania.

    Słuszna uwaga co do niepełnych zapisów, ale z punktu widzenia detekcji (a nie korekcji) błędów ta sytuacja nie jest taka zła.
    Atomowość możemy też zapewnić stosując system plików z dziennikiem (lub w całości opaty na nim, jak wiele systemów projektowanych dla pamięci flash).

    tmf napisał:
    Dla 32-bitowego procka (a nawet dla 8-bitowego) policzenie funkcji skrótu dla danych w FLASH/EEPROM to nie jest żadne obciążenie, biblioteki są gotowe więc czemu nie skorzystać

    Jeśli mamy sprzętowy szyfr blokowy o zadowalającej długości bloku to można jeszcze szybciej - zaszyfrować dane w trybie CBC jakimś stałym kluczem i wziąć ostatni blok wynikowy (uwaga: tylko do kontroli przypadkowych błędów, nie jako kryptograficzny hash!). Są też inne, bezpieczne sposoby (link), ale co blok zmienia się klucz, przez co są wolniejsze i tracą przewagę nad normalną funkcją skrótu.

    0
  • #18 11 Mar 2016 13:15
    2675900
    Użytkownik usunął konto