Welche Strategien gibt es für das Testen großer Zustandsautomaten?

Question

Ich habe einen großen und ziemlich komplexen Zustandsautomaten geerbt. Er hat 31 mögliche Zustände, die alle wirklich benötigt werden (großer Geschäftsprozess). Er hat die folgenden Eingaben:

• Enum: Aktueller Zustand (also 0 -> 30)
• Enum: Quelle (derzeit nur 2 Einträge)
• Boolesch: Anfrage
• Boolesch: Typ
• Enum: Status (3 Zustände)
• Enum: Handhabung (3 Zustände)
• Boolesch: Abgeschlossen

Eine Aufteilung in separate Zustandsautomaten scheint nicht möglich zu sein, da jeder Zustand unterschiedlich ist. Ich habe Tests für die gebräuchlichsten Eingänge geschrieben, mit einem Test pro Eingang, wobei alle Eingänge konstant sind, außer dem Zustand.

[Subject("Application Process States")]
public class When_state_is_meeting2Requested : AppProcessBase
{
    Establish context = () =>
    {
        //Setup....
    };

    Because of = () => process.Load(jas, vac);

    It Current_node_should_be_meeting2Requested = () => process.CurrentNode.ShouldBeOfType<meetingRequestedNode>();
    It Can_move_to_clientDeclined = () => Check(process, process.clientDeclined);
    It Can_move_to_meeting1Arranged = () => Check(process, process.meeting1Arranged);
    It Can_move_to_meeting2Arranged = () => Check(process, process.meeting2Arranged);
    It Can_move_to_Reject = () => Check(process, process.Reject);
    It Cannot_move_to_any_other_state = () => AllOthersFalse(process);
}

Niemand ist sich ganz sicher, wie die Ausgabe für jeden Zustand und jeden Satz von Eingaben aussehen sollte. Ich habe begonnen, Tests dafür zu schreiben. Allerdings muss ich etwas schreiben wie 4320 Tests (30 * 2 * 2 * 2 * 3 * 3 * 2).

Welche Vorschläge haben Sie für das Testen von Zustandsautomaten?

---

Editar: Ich spiele mit all den Vorschlägen und werde eine Antwort markieren, wenn ich eine gefunden habe, die am besten funktioniert.

Answer 1

Ich hatte einen endlichen Automaten für ein medizinisches Gerät konstruiert. Der FSM war über ein von mir definiertes XML-Format konfigurierbar.

Um eine Zustandsmaschine zu definieren, muss man sich auf die Erfahrung mit der Verwendung von Zustandsdiagrammen bei der Entwicklung digitaler Schaltungen stützen,

Sie müssen eine so genannte Turnpike Transition Map verwenden. An der Ostküste der Vereinigten Staaten tragen die meisten Autobahnen den Spitznamen Turnpikes. Die Mautbehörden geben eine Mautgebührenkarte heraus. Wenn ein mautpflichtiger Abschnitt 50 Ausfahrten hat, würde die Gebührenkarte eine Tabelle mit 50 Zeilen x 50 Spalten enthalten, in der die Ausfahrten sowohl in Zeilen als auch in Spalten vollständig aufgeführt sind. Um die Mautgebühr für die Einfahrt in die Ausfahrt 20 und die Ausfahrt 30 zu ermitteln, suchen Sie einfach den Schnittpunkt von Zeile 20 und Spalte 30.

Bei einem Zustandsautomaten mit 30 Zuständen wäre die Turnpike-Übergangskarte eine 30 x 30 Matrix, in der alle 30 möglichen Zustände zeilen- und spaltenweise aufgelistet sind. Wir entscheiden, dass die Zeilen die AKTUELLEN Zustände und die Spalten die NÄCHSTEN Zustände sein sollen.

Jede sich überschneidende Zelle würde den "Preis" für den Übergang von einem AKTUELLEN Zustand (Zeile) zu einem NÄCHSTEN Zustand (Spalte) auflisten. Anstelle eines einzelnen $-Wertes würde sich die Zelle jedoch auf eine Zeile in der Tabelle "Inputs" beziehen, die wir als "transition id" bezeichnen könnten.

In dem von mir entwickelten FSM für medizinische Geräte gab es Eingaben in Form von String, enums, int usw. Die Tabelle Eingänge listet diese Eingabestimuli spaltenweise auf.

Um die Eingabetabelle zu erstellen, müssen Sie eine einfache Routine schreiben, die alle möglichen Kombinationen von Eingaben auflistet. Aber die Tabelle wäre riesig. In Ihrem Fall hätte die Tabelle 4320 Zeilen und damit 4320 Übergangskennungen. Aber es ist keine langwierige Tabelle, weil Sie die Tabelle programmatisch erstellt haben. In meinem Fall habe ich ein einfaches JSP geschrieben, um die Eingabetabelle der Übergänge (und die Turnpike-Tabelle) im Browser aufzulisten oder als csv herunterzuladen, um sie in MS Excel anzuzeigen.

Es gibt zwei Möglichkeiten, diese beiden Tabellen zu erstellen.

1. die Entwurfsrichtung, in der Sie die Turnpike-Tabelle mit allen möglichen Übergängen konstruieren, wobei nicht erreichbare Übergänge ausgegraut werden. Dann erstellen Sie die Tabelle Eingänge mit allen erwarteten Eingängen für jeden erreichbaren Übergang, wobei die Zeilennummer als Übergangsnummer verwendet wird. Jede Transitions-ID wird in die entsprechende Zelle der Turnpike Transition Map übertragen. Da es sich bei der FSM jedoch um eine spärliche Matrix handelt, werden nicht alle Übergangskennungen in den Zellen der Turnpike-Übergangskarte verwendet. Außerdem kann eine Übergangskennung mehrfach verwendet werden, da dieselben Übergangsbedingungen für mehr als ein Paar von Zustandsänderungen gelten können.

2. die Testrichtung ist umgekehrt, wobei Sie die Tabelle Eingaben erstellen. Sie müssen eine allgemeine Routine für den erschöpfenden Übergangstest schreiben.
   Die Routine würde zunächst eine Übergangssequenztabelle lesen, um die Zustandsmaschine in einen Eingangszustand zu bringen und einen Testzyklus zu starten. Bei jedem CURRENT-Zustand ist sie bereit, alle 4320 Übergangskennungen zu durchlaufen. In jeder Zeile der CURRENT-Zustände in der Turnpike-Übergangstabelle gäbe es eine begrenzte Anzahl von Spalten mit gültigen NEXT-Zuständen.

Sie möchten, dass die Routine alle 4320 Zeilen der Eingänge durchläuft, die sie aus der Tabelle Eingänge liest, um sicherzustellen, dass unbenutzte Übergangs-IDs keine Auswirkungen auf einen AKTUELLEN Zustand haben. Sie möchten prüfen, ob alle effektiven Übergangs-IDs gültige Übergänge sind.

Das ist jedoch nicht möglich, denn sobald ein effektiver Übergang eingefügt wird, ändert sich der Zustand der Maschine in einen NÄCHSTEN Zustand und Sie können die restlichen Übergänge nicht mehr auf den vorherigen AKTUELLEN Zustand testen. Sobald die Maschine den Zustand wechselt, müssen Sie mit dem Testen wieder bei Übergangskennung 0 beginnen.

Übergangspfade können zyklisch oder irreversibel sein oder eine Kombination aus zyklischen und irreversiblen Abschnitten entlang des Pfades aufweisen.

Innerhalb Ihrer Prüfroutine benötigen Sie für jeden Zustand ein Register, um die letzte in diesen Zustand gepumpte Übergangskennung zu speichern. Jedes Mal, wenn der Test eine wirksame Übergangskennung erreicht, wird diese in diesem Register gespeichert. Wenn Sie also einen Zyklus abschließen und zu einem bereits durchlaufenen Zustand zurückkehren, beginnen Sie mit der Iteration der nächsten Übergangs-ID, die größer ist als die im Register gespeicherte.

Ihre Routine müsste sich um die irreversiblen Abschnitte eines Übergangspfades kümmern. Wenn eine Maschine in einen Endzustand gebracht wird, startet sie den Test vom Eingangszustand aus neu und wiederholt die 4320 Eingaben der nächsten Übergangskennung, die größer als die für einen Zustand gespeicherte ist. Auf diese Weise könnten Sie alle möglichen Übergangspfade des Automaten erschöpfend ermitteln.

Glücklicherweise sind FSMs spärliche Matrizen effektiver Übergänge, da ein erschöpfendes Testen nicht die gesamte Kombination aus Anzahl der Übergangs-Ids x Anzahl der möglichen Zustände zum Quadrat verbrauchen würde. Schwierig wird es jedoch, wenn man es mit einem alten FSM zu tun hat, bei dem visuelle oder Temperaturzustände nicht in das Testsystem zurückgeführt werden können und man jeden Zustand visuell überwachen muss. Das wäre hässlich, aber wir haben trotzdem zwei Wochen damit verbracht, das Gerät zusätzlich visuell zu testen, indem wir nur die effektiven Übergänge durchlaufen haben.

Möglicherweise benötigen Sie keine Übergangssequenztabelle (für jeden Eintrittspunktzustand, den die Testroutine lesen muss, um die Maschine zu einem gewünschten Eintrittspunkt zu bringen), wenn Ihr FSM es Ihnen ermöglicht, einen Eintrittspunkt mit einem einfachen Reset zu erreichen und die Anwendung einer Übergangskennung ihn einfach zu einem Eintrittspunktzustand bringt. Eine Routine, die in der Lage ist, eine Übergangssequenztabelle zu lesen, ist jedoch nützlich, da man häufig in die Mitte des Zustandsnetzwerks gehen und die Prüfung von dort aus starten muss.

Sie sollten sich mit der Verwendung von Übergangs- und Zustandsdiagrammen vertraut machen, da es sehr nützlich ist, alle möglichen und nicht dokumentierten Zustände einer Maschine aufzuspüren und die Benutzer zu befragen, ob sie diese tatsächlich ausgegraut haben wollen (Übergänge unwirksam und Zustände unerreichbar gemacht).

Der Vorteil, den ich hatte, war, dass es sich um ein neues Gerät handelte und ich die Wahl hatte, den Zustandsautomaten so zu gestalten, dass er XML-Dateien lesen konnte, was bedeutete, dass ich das Verhalten des Zustandsautomaten so ändern konnte, wie ich es wollte, eigentlich so, wie es der Kunde wollte, und ich konnte sicherstellen, dass unbenutzte Übergangskennungen wirklich unwirksam waren.

Für das Java-Listing des Finite-State-Machine-Controllers http://code.google.com/p/synthfuljava/source/browse/#svn/trunk/xml/org/synthful . Testroutinen sind nicht enthalten.

Answer 2

Prüfung auf der Grundlage der Anforderungen. Wenn ein bestimmter Zustand immer dann in einen bestimmten anderen Zustand übergehen muss, wenn Erledigt wahr ist, dann schreiben Sie einen Test, der automatisch alle Kombinationen der anderen Eingänge durchläuft (das sollten nur ein paar for-Schleifen sein), um zu beweisen, dass die anderen Eingänge korrekt ignoriert werden. Am Ende sollten Sie einen Test für jeden Übergangsbogen haben. Ich schätze, das sind etwa 100 oder 150 Tests, nicht 4000.

Answer 3

Sie könnten folgende Untersuchungen in Erwägung ziehen Modellbasierte Tests . Es gibt einige Tools, die in solchen Situationen bei der Testerstellung helfen. Ich empfehle normalerweise MBT .

Answer 4

Brute-Force-Tests mit Abdeckungstests scheinen ein guter Anfang zu sein.