Was sind bewährte Methoden zum Testen von Programmen mit stochastischem Verhalten?

14

Während meiner Forschungs- und Entwicklungsarbeit schreibe ich oft Programme, deren Verhalten in gewissem Maße zufällig ist. Wenn ich zum Beispiel in der genetischen Programmierung arbeite, schreibe ich oft Programme, die beliebigen zufälligen Quellcode generieren und ausführen.

Ein Problem beim Testen eines solchen Codes besteht darin, dass Fehler häufig nur sporadisch auftreten und sich nur sehr schwer reproduzieren lassen. Dies geht über das Einstellen eines zufälligen Startwerts auf denselben Wert und das erneute Starten der Ausführung hinaus.

Beispielsweise könnte Code eine Nachricht aus dem Kernel-Ring-Puffer lesen und dann bedingte Sprünge auf den Nachrichteninhalt ausführen. Natürlich hat sich der Zustand des Ringpuffers geändert, wenn man später versucht, das Problem zu reproduzieren.

Auch wenn dieses Verhalten ein Feature ist , kann es auf unerwartete Weise anderen Code auslösen und somit häufig Fehler aufdecken, die von Komponententests (oder menschlichen Testern) nicht gefunden werden.

Gibt es bewährte Verfahren zum Testen solcher Systeme? In diesem Fall wären einige Referenzen sehr hilfreich. Wenn nicht, sind alle anderen Vorschläge willkommen!

John Doucette
quelle
5
Können Sie den Kernel-Ringpuffer nicht auch verspotten? Und andere zufällige Aspekte Ihres Codes?
Jonathan Merlet
1
@JonathanMerlet Möglicherweise, aber das Problem ist, dass der Code bei der Bereitstellung Zugriff auf den echten Ringpuffer hat (in der Tat auf ein echtes Betriebssystem). Wenn ich also nur eine verspottete Version teste, verschiebe ich die Entdeckung dieser Bugs erst später.
John Doucette
Es scheint mir, dass das Problem nicht mit dem zufälligen Verhalten des Programms zusammenhängt (da dies durch den zufälligen Startwert gesteuert werden kann), sondern mit bestimmten Zuständen dieses "Kernel-Ringpuffers". Ihre Frage lautet also tatsächlich: Wie teste ich ein Programm, das vom externen Status abhängt?
AakashM
@ AakashM, ja, das ist ein besserer Weg, es auszudrücken. Genauer gesagt, ein Programm mit einem externen Status, das stochastisch auf den externen Status zugreift oder diesen ändert.
John Doucette

Antworten:

7

Es ist nützlich, wie vorgeschlagen Hooks hinzuzufügen, um genaue Status wiederherzustellen. Instrumentieren Sie das System auch so, dass es seine "Seeds" (in Ihrem Fall einschließlich des PRNG-Seeds sowie des Kernel-Ringpuffers und anderer Quellen für nicht deterministische Eingaben) ablegen kann.

Führen Sie dann Ihre Tests sowohl mit echten Zufallseingaben als auch im Regressionsstil mit zuvor entdeckten interessanten Fällen aus.

Für den speziellen Fall, dass Sie auf den Kernel zugreifen, würde ich auf jeden Fall empfehlen, einen Schein anzufertigen. Verwenden Sie den Mock, um Äquivalenzklassen zu erzwingen, die in der Praxis weniger häufig auftreten, und zwar im Sinne von "leer" und "voll" für Container oder "0, 1, 2 ^ n, 2 ^ n + 1, viele" für zählbare Dinge. Dann können Sie mit dem Schein und mit der Realität testen, in dem Wissen, dass Sie die Fälle behandelt und getestet haben, an die Sie bisher gedacht haben.

Was ich vorschlage, ist im Grunde genommen eine Mischung aus deterministischen und nicht deterministischen Eingaben, wobei die deterministischen eine Mischung aus denen sind, an die Sie denken können, und denen, die Sie überrascht haben.

Stephan A. Terre
quelle
6

Eine vernünftige Sache ist es, den Zufallszahlengenerator mit einem konstanten Wert für die Tests auszustatten, damit Sie ein deterministisches Verhalten erhalten.

Dima
quelle
1
Dies; oder verspotten Sie das prng vollständig
jk.
1
Danke für den Vorschlag! Ich mache dies bereits für Unit-Tests, kann aber nicht alle möglichen Programme von Hand testen.
John Doucette
2
Dies bedeutet jedoch, dass Sie nicht testen können, ob die Zufälligkeit ordnungsgemäß funktioniert.
Louis Rhys,
2

Ich denke, statistische Tests sind der einzige Weg. So wie Zufallszahlen durch statistische Tests auf ihre Zufälligkeit "getestet" werden, müssen es auch Algorithmen sein, die sich zufälligen Verhaltens bedienen.

Führen Sie den Algorithmus einfach mehrmals mit derselben oder einer anderen Eingabe aus und vergleichen Sie ihn miteinander. Das Problem bei diesem Ansatz ist die massive Erhöhung der Rechenzeit, die zum Beenden des Tests erforderlich ist.

Euphorisch
quelle
Nicht unbedingt, da Sie einen kleinen "übergreifenden" Satz von Eingaben auswählen und mehrere Male ausführen können. Die Anzahl der Eingaben, die zur Überprüfung der Zuverlässigkeit erforderlich sind, ist möglicherweise geringer. Dieser "überspannende" Satz sollte jeden Zweig des Codes eingeben, alle Objekte initialisieren usw.
Daniel Moskovich
2

Ich bin kein Spezialist auf diesem Gebiet, aber es gibt eine wissenschaftliche Literatur zu stochastischen Programmtests.

Wenn Sie Testklassen nicht einfach erstellen können, kann ein statistischer Test verwendet werden, wie #Euphoric sagte. Borning et al. Vergleichen Sie einen traditionellen und einen statistischen Ansatz. Eine Verallgemeinerung der von @Euphoric vorgeschlagenen statistischen Tests könnte die von Whittaker diskutierte sein. Er schlug vor, ein stochastisches Modell des gewünschten (in Ihrem Fall stochastischen) Verhaltens zu erstellen und dann spezifische Testfälle aus diesem Modell zu generieren (siehe sein spezielles Papier ).

mgoeminne
quelle
Vielen Dank! Sieht sehr hilfreich aus. Für diejenigen außerhalb der akademischen Einrichtungen kann eine vorgedruckte Version des Papiers aus dem Google Code Repository des Autors hier abgerufen
John Doucette