Beste Möglichkeit zum Testen der CRC-Logik?

Wie kann ich überprüfen, dass zwei CRC-Implementierungen die gleichen Prüfsummen erzeugen?Beste Möglichkeit zum Testen der CRC-Logik?

Ich bin auf der Suche nach einer umfassenden CRC-Evaluierungsmethodik.

Quelle

2010-08-30 Joseph Weissman

Beachten Sie, dass das Testen für viele Eingaben wahrscheinlich zeigt, dass beide Implementierungen den gleichen Algorithmus verwenden, aber nicht, dass sie ordnungsgemäß implementiert werden. Wenn einer der CRC-Algorithmen einen Fencepost-Fehler hat, der nur bei Eingaben auftritt, die durch eine seltsame Formel mit Faktoren von 32 teilbar sind, kann der fehlerhafte Eingabefall sehr klein sein (was auch bedeutet, dass er meistens funktioniert). Dies ist in erster Linie nur ein Problem, wenn Sie versuchen, es selbst zu implementieren oder eine seltsame, schlecht getestete Implementierung in einer Diskussionsrunde verwenden. Gut getestete Implementierungen haben dieses Problem wahrscheinlich nicht. – Brian

Erstellen Sie mehrere Komponententests mit derselben Eingabe, die die Ausgabe beider Implementierungen miteinander vergleichen.

Quelle

2010-08-30 17:53:43 Bernard

Ich habe das an Ort und Stelle, aber wie können wir wissen, dass wir alle möglichen Eingaben (zumindest ein bedeutungsvolles Fragment) abgedeckt haben? Ich bin auf der Suche nach etwas, das mit der Art der CRCs zusammenhängt, die uns in die Richtung weisen können, wie diese Tests so geschrieben werden, dass der Eingabebereich effektiv abgedeckt wird. –

@ Joe- Eine Reihe von 20-30 zufälligen Eingaben unterschiedlicher Größe sollte ausreichen, um zu beweisen, dass die CRC-Algorithmen gleiche Ausgaben produzieren. Ich habe nie zwei Implementierungen gesehen, die eine "nahe" Ausgabe produziert haben; stattdessen führten selbst geringfügige Unterschiede zu großen Veränderungen in der Ausgabe.Davon abgesehen, wenn es sich um hausgemachte CRC-Implementierungen handelt, von denen nicht bekannt ist, dass sie fehlerfrei sind, kann ein Codierungsfehler Probleme für Ihre Tests verursachen. – bta

Ich weiß, meine obige Bemerkung ist "Beweis durch das Fehlen eines Gegenbeispiels", aber die Idee hält immer noch an. Wenn die Implementierungen unterschiedliche Polynome verwenden, erhalten Sie radikal unterschiedliche Ergebnisse. – bta

Durch Schreiben eines Komponententests für jeden, der die gleiche Eingabe entgegennimmt und mit der erwarteten Ausgabe vergleicht.

Quelle

2010-08-30 17:53:47

Ich verstehe - das ist was wir tun - aber woher wissen wir, dass wir den möglichen Input-Bereich erschöpft haben (oder sogar fast erschöpfen)? Ich suche nach etwas, das auf der Art basiert, wie CRCs spezifisch arbeiten. –

Erstens, wenn es eine Standard-CRC-Implementierung ist, sollten Sie in der Lage sein, bekannte Werte irgendwo im Netz zu finden.

Zweitens könnten Sie eine gewisse Anzahl von Nutzlasten generieren und jede CRC auf den Nutzlasten ausführen und überprüfen, ob die CRC-Werte übereinstimmen.

Quelle

2010-08-30 17:53:47

Sie können das Problem in Randfälle und Stichproben trennen.

Kantengehäuse. Es gibt zwei Variablen für den CRC-Eingang, die Anzahl der Bytes und den Wert jedes Bytes. Erstellen Sie also Arrays von 0, 1 und MAX_BYTES mit Werten von 0 bis MAX_BYTE_VALUE. Die Edge-Case-Suite wird wahrscheinlich in einer JUnit-Suite enthalten sein.

Stichproben. Unter Verwendung der obigen Bereiche führen Sie CRC auf zufällig generierten Arrays von Bytes in einer Schleife aus. Je länger Sie die Schleife laufen lassen, desto mehr erschöpfen Sie die Eingaben. Wenn Sie wenig Rechenleistung haben, sollten Sie den Test auf EC2 anwenden.

Quelle

2010-08-30 18:33:22

Eine nette Eigenschaft von CRCs ist, dass Sie für einen gegebenen Parametersatz (Polynom, Reflexion, Anfangszustand usw.) einen konstanten Wert erhalten, wenn Sie den CRC über den ursprünglichen Datensatz + den ursprünglichen CRC neu berechnen. Diese Konstanten werden für gemeinsame CRCs dokumentiert aber man kann sie einfach blind erzeugen zwei verschiedene zufällige Datensätze verwenden und überprüfen, ob sie gleich sind:

implementation 1: crc(rand_data_1 + crc(rand_data_1)) -> constant_1 
implementation 2: crc(rand_data_2 + crc(rand_data_2)) -> constant_2 
assert constant_1 == constant_2

Sie die gleiche Methode innerhalb einer Implementierung verwenden können, ein warmes wohliges Gefühl zu bekommen über seine Richtigkeit. Wenn Ihre Implementierung mit beliebigen Polynomen arbeitet, können Sie mit dem unitest jedes mögliche Polynom mit dieser Methode erschöpfend prüfen lassen, ohne zu wissen, was die Konstanten sind. Diese Technik ist leistungsfähig, aber es wäre auch sinnvoll, einen unabhängigen Test hinzuzufügen, der das Ergebnis basierend auf bekannten Eingaben für den pathologischen Fall verifiziert, wo Ihre CRC-Implementierungen schlechte Ergebnisse liefern, die durch die konstante Äquivalenzprüfung erhalten werden.

Quelle

2014-04-04 23:04:38

Beste Möglichkeit zum Testen der CRC-Logik?

Antwort

Verwandte Themen