Überblick

• Hardware-in-the-loop-Test
• Spezifikationsbasiertes Testen: (1) Prüfen (2) Testdaten generieren
• Testen vs. formaler Beweis
  • Testen kann gegen Beweis konvergieren
  • in der Praxis aber meist zu aufwendig, deswegen: Heuristiken für "relvante", "gute", ... Testfälle
• Testen abhängig von der Anwendung:
  • sicherheitskritische Anwendungen
  • Testen wird in Standards (z.B. Eisenbahn, Luftfahrt) gefordert
• Test im Gegensatz zu: statischer Analyse, symbolische Ausführung, Review, Inspektion
• Testfälle
  • was will ich prüfen?
  • Bedingungen
  • Eingaben
  • erwartete Ausgaben
  • ... auf Basis der Anforderungen
• Testprozeduren: Implementierung der Testfälle (Testdaten generieren + Ausgaben prüfen, s.o.)
• Übungsserie 1:
  • Anforderungen spezifizieren
  • Testfälle entwerfen (inkl. Anforderungsüberdeckungsmatrix)
  • Testprozeduren implementieren
  • Beispiel war: Unix-Kommando ln

Klassifizierung von Tests

• Klassifizierung nach Qualitätskriterien
• (Produkt-)Qualität:
  • Wirksamkeit: kann nur validiert werden
  • Korrektheit: kann (z.B. durch Testen) geprüft werden - Prüfen gegen die Anforderungen
• Testhierarchie: System Acceptance Test ... Unit Tests
• Funktionale Eigenschaften (Daten, Datentransformation, Kausaleigenschaften, Zeitverhalten, Struktureigenschaften)
  • u.a.: Code Coverage (aus Struktureigenschaften/Funktionale Eigenschaften)
• Nicht-funktionale Eigenschaften:
  • u.a. Robustheit: Unterscheidung zwischen Normalverhalten und Ausnahmeverhalten
• Beobachtungstiefe: Black Box vs. White Box

Kombinatorische Systeme

• Vorüberlegung: Testling ist ein zustandsveränderndes System
• State-Transition-System (S, S₀, T)
• Kombinatorisches System: Hat gerade keinen Internzustand
• S = IN × OUT × TIME, wobei die Outputs o ∈ OUT direkt von den Inputs i ∈ IN abhängen
• Prüfbarkeit von Eingabefolgen: die Eingaben dürfen nicht schneller hintereinander folgen, als die Latenz β des Systems "erlaubt".

• alle Kombinationen von Eingaben werden getestet
• gut: falls der Testling tatsächlich zustandslos ist, findet man alle Fehler
• schlecht: im allgemeinen ist diese Überdeckung schon zu aufwendig; nur für wenige Inputs und schnelle Systeme geeignet
• Übungsserie 2:
  • Testen von PLS (kombinatorische Variante) gemäß der Kombinationsüberdeckung

• die Übergänge zwischen allen Kombinationen von Eingaben werden getestet
• also werden auch alle Kombinationen von Eingaben getestet
• der Gewinn: falls der Testling einen Internzustand hat und somit die Ausgaben vom Vorzustand abhängen, dann findet man manche zusätzlichen Fehler:
  Bsp: Fehlerhaftes or-Gatter mit 2 Inputs:
  
  • Spec.: out(11)=1, out(10)=1, out(01)=1, out(00)=0
  • Impl.: out(11)=1, out(10)=1, out(00)=0, out(01) berechnet nichts, sondern läßt die alten Ausgabe
  Kombinationsüberdeckungstest, z.B.:
  • out(11)=1, out(10)=1, out(01)=1, out(00)=0, Test bestanden, Fehler nicht gefunden
  Übergangsüberdeckungstest, z.B.:
  • out(11) ---> out(10)=1
  • out(11) ---> out(01)=1
  • out(11) ---> out(00)=0
  • out(10) ---> out(11)=1
  • out(10) ---> out(01)=1
  • out(10) ---> out(00)=0
  • out(01) ---> out(11)=1
  • out(01) ---> out(10)=1
  • out(01) ---> out(00)=0
  • out(00) ---> out(11)=1
  • out(00) ---> out(10)=1
  • out(00) ---> out(01)=0 Fehler gefunden
• Übungsserie 3:
  • Testen von PLS (kombinatorische Variante) gemäß der Übergangsüberdeckung
  • Gescheite Implementierung der Übergangsauswahl:
    • todo-Liste
    • pro Kombination von Eingaben (Eingabevektor) eine Menge von Folgeeingabevektoren
    • nach Möglichkeit vom aktuellen Eingabevektor einen Folgevektor wählen, zu dem bislang noch kein Übergang gemacht wurde
    • sonst zufällig wählen

• Heuristik 1: Übergänge zwischen Eingabevektoren wählen, die Änderungen in den Ausgaben erfordern
• Verfeinerung: möglichst viele Änderungen in den Ausgaben erzwingen
• Heuristik 2: Übergänge wählen, bei denen genau die Inputs geändert werden, die für die Änderung der Outputs verantwortlich sind
• Technik:
  • Disjunktive Normalform (der booleschen Spec)
  • inkl. Minterme
  • Primimplikanten-Darstellung ableiten
  • jetzt Übergänge "zwischen Primimplikanten" wählen, mit möglichst großen Änderungen an den Outputs
• Verfeinerung: "nicht-verantwortliche" Eingaben dabei wiederum zufällig kombinieren, um "mit Glück" noch weitere Fehler aufzudecken

• OBDDs (Ordered Binary Decision Diagrams) verwenden
• separate Diagramme für (1) Testdatengenerierung und (2) Prüfen
• für die Testdatengenerierung:
  Von der Wurzel aus zuerst die erwarteten Ausgaben kodieren (danach wollen wir nämlich aussuchen), dann absteigend die Eingaben.
• für das Prüfen:
  Andersherum: zuerst die Eingaben, dann die Ausgaben.
• Reduktion der Bäume:
  1. Identische Teilbäume einsparen.
  2. Variablen überspringen, die keinen Einfluß auf die Ausgaben haben (entspricht der Idee der Primimplikanten).

Zustandsbasierte Systeme

• Formalismen: endliche Automaten, CSP; bei uns im Fokus: Statecharts
• Flache Statecharts:
  • Zustände
  • Transitionen (Zustandsübergänge)
  • mit: Condition/Guard, Signal/Event, Action
  • Timer sind gegeben: per Action setzen, beim Ablaufen Signal empfangen
• Hierarchische Statecharts:
  • Zustände können wiederum ganze Statecharts enthalten
  • enthaltenes Statechart ist genau dann aktiv, wenn der Behälterzustand aktiv ist (spezifiziert als das detaillierte Verhalten)
• Weiterhin: globale Variablen (erweitern den Zustandsraum, "Zustände" heißen dann besser "Locations")
• Parallele Kombination von Statecharts
• Testen von zustandsbasierten Systemen:
  1. Was kann man beobachten?
     • Events/Signals
     • Globale Variablen
     • Timer
     • Locations (Zustände), falls White-Box-Test
• Übungsserie 4:
  • Testen eines zustandsbasierten Systems
  • keine Hierarchie
  • Test des SUT gegen Statecharts-Simulation
  • vereinfachtes Testvorgehen ... (Details s. Übungsblatt)

• Testsequenzen für zustandsbasierte Spezifikationen generieren
• Gewinn: wenn man alle Testsequenzen testet, weiß man, daß der Testling korrekt ist
• Einschränkungen:
  1. flache Statecharts
  2. sequentielle Statecharts
  3. keine (globalen) Variablen
  4. keine Zeit
• Annahmen:
  1. Das Verhalten der Spezifikation bzw. des Testlings hängt ausschließlich vom aktuellen Zustand und den anliegenden Eingaben ab, so wie es durch die ausgehende Transitionen definiert ist.
     D.h., es ist keine zusätzliche Historie gespeichert, die das Verhalten beeinflußt.
     
  2. Der Testling hat genau so viele Zustände wie die Spezifikation.

1. Alle Zustände der Spezifikation werden aufgesucht:
   Man braucht Startsequenzen, welche vom Startzustand zu jedem Zustand führen.
2. Von jedem so aufgesuchten Zustand werden alle ausgehenden Transitionen einmal gefeuert.
3. Anschließend wird sichergestellt, daß der richtige Folgezustand) eingenommen wurde.
   Weil gemäß obiger Annahme das Folgeverhalten ausschließlich durch die ausgehenden Transitionen definiert wird und sichergestellt ist, daß alle Zustände aufgesucht werden, sind alle möglichen Verhalten somit getestet.
   Insbesondere braucht man keine Pfadüberdeckung.
   Beachte: Wegen der Annahme über die identische Anzahl der Zustände sind somit alle Zustände des Testlings auch abgedeckt, und somit kann der Testling keine weiteren (abweichenden) Verhalten verbergen.

1. die "Transitionsüberdeckung"/"transition cover":
   Beinhaltet die Startsequenzen und alle ausgehenden Transitionen
2. die "Charakterisierungsmenge":
   Beinhaltet alle Sequenzen, die eindeutig zeigen, aus welchem Zustand man sie startet. Somit kann man den richtigen Folgezustand erkennen.

Erzeugung der Baumstruktur für das "transition cover"

1. Level 1: Sei Knoten K die Wurzel des Baumes TC mit zugehörigem Zustand Z: Z ist der Startzustand des Zustandsdiagramms.
2. Level (n+1): Annahme: TC ist bis zum Level n konstruiert.
   Traversiere alle TC-Knoten K_i vom Level n. K_i ist Blatt, wenn K_i schon auf einem Level 0,...,n (als Blatt) auftaucht. Sei Z_i der zu K_i gehörige Zustand. Für jede ausgehende Transition t_j mit Zielzustand Y_j erzeuge einen Kindknoten K_j von K_i. Bezeichne den neuen Verbinder mit dem Input der Transition t_j.

         1/a              1/a
        /--              /--
        | /              | /
      /---\    0/a     /---\
  --->| P |----------->| Q |
      \---/            \---/
      ^   ^           ^  |
      |    \     1/b /   |
      |  0/a\       /    | 0/b
      |      \ /---\     /
      \--------| R |<----
        2/b    \---/

(ein) resultierender Baum:

                     (P)
                     / \
                  1 /   \ 0
                   /     \
                 (P)     (Q)
                         / \
                      1 /   \ 0
                       /     \
                     (Q)     (R)
                            / | \
                         1 /  |0 \ 2
                          /   |   \
                        (Q)  (P)  (P)

"transition cover"

Das ist die Menge T der Eingabefolgen, die durch alle Pfadpräfixe aus der Baumstruktur (d.h. alle Teilpfade, die bei der Wurzel beginnen) festgelegt sind:
T = {<>, <1>, <0>, <0,1>, <0,0>, <0,0,1>, <0,0,0>, <0,0,2>}

Characterization Set

Hier: W = {<1,0>}

Resultierende Testsequenzen

W-Methode (m>0)

• Man kann Fehler für Testlinge finden, welche mehr Zustände haben als die Spezifikation:
  Annahme: (Anzahl der Zustände des Testlings) - (Anzahl der Zustände der Spezifikation) = m > 0
• D.h., daß jeder Fehler eines solchen Testlings mit Sicherheit gefunden wird.

1. Es reicht nicht mehr, nach dem "transition cover" direkt zu prüfen, ob schon der richtige Zustand eingenommen wurde;
   nun müssen vorher noch bis zu m weitere Zustände besucht werden.
2. Dieses wird erreicht, indem nun alle möglichen Eingabefolgen mit Länge =< m getestet werden.
3. Sind nun alle Zustände besucht worden, reicht es schließlich, mittels des "characterization sets" zu prüfen, daß schließlich wieder ein Zustand eingenommen wurde, welcher dem der Spezifikation entspricht.
   (Das darauffolgende Verhalten ist dann wg. der angenommenen Obergrenze von Zuständen im Testling wieder korrekt.)

Auffalten aller möglichen Eingabefolgen mit Länge =< m

Resultierende Testsequenzen

Somit für das Beispiel mit m=2:
T ◦ Z
= T ◦ ( Σ⁰◦W ∪ Σ¹◦W ∪ Σ²◦W )
= T ◦ {<1,0>, <0,1,0>, <1,1,0>, <2,1,0>, <0,0,1,0>, <0,1,1,0>, <0,2,1,0>, <1,0,1,0>, <1,1,1,0>, <1,2,1,0>, <2,0,1,0>, <2,1,1,0>, <2,2,1,0>}

=

{<1,0>, <0,1,0>, <1,1,0>, <2,1,0>, <0,0,1,0>, <0,1,1,0>, <0,2,1,0>, <1,0,1,0>, <1,1,1,0>, <1,2,1,0>, <2,0,1,0>, <2,1,1,0>, <2,2,1,0>}
∪
{<1,1,0>, <1,0,1,0>, <1,1,1,0>, <1,2,1,0>, <1,0,0,1,0>, <1,0,1,1,0>, <1,0,2,1,0>, <1,1,0,1,0>, <1,1,1,1,0>, <1,1,2,1,0>, <1,2,0,1,0>, <1,2,1,1,0>, <1,2,2,1,0>}
∪
{<0,1,0>, <0,0,1,0>, <0,1,1,0>, <0,2,1,0>, <0,0,0,1,0>, <0,0,1,1,0>, <0,0,2,1,0>, <0,1,0,1,0>, <0,1,1,1,0>, <0,1,2,1,0>, <0,2,0,1,0>, <0,2,1,1,0>, <0,2,2,1,0>}
∪
{<0,1,1,0>, <0,1,0,1,0>, <0,1,1,1,0>, <0,1,2,1,0>, <0,1,0,0,1,0>, <0,1,0,1,1,0>, <0,1,0,2,1,0>, <0,1,1,0,1,0>, <0,1,1,1,1,0>, <0,1,1,2,1,0>, <0,1,2,0,1,0>, <0,1,2,1,1,0>, <0,1,2,2,1,0>}
∪
{<0,0,1,0>, <0,0,0,1,0>, <0,0,1,1,0>, <0,0,2,1,0>, <0,0,0,0,1,0>, <0,0,0,1,1,0>, <0,0,0,2,1,0>, <0,0,1,0,1,0>, <0,0,1,1,1,0>, <0,0,1,2,1,0>, <0,0,2,0,1,0>, <0,0,2,1,1,0>, <0,0,2,2,1,0>}
∪
{<0,0,1,1,0>, <0,0,1,0,1,0>, <0,0,1,1,1,0>, <0,0,1,2,1,0>, <0,0,1,0,0,1,0>, <0,0,1,0,1,1,0>, <0,0,1,0,2,1,0>, <0,0,1,1,0,1,0>, <0,0,1,1,1,1,0>, <0,0,1,1,2,1,0>, <0,0,1,2,0,1,0>, <0,0,1,2,1,1,0>, <0,0,1,2,2,1,0>}
∪
{<0,0,0,1,0>, <0,0,0,0,1,0>, <0,0,0,1,1,0>, <0,0,0,2,1,0>, <0,0,0,0,0,1,0>, <0,0,0,0,1,1,0>, <0,0,0,0,2,1,0>, <0,0,0,1,0,1,0>, <0,0,0,1,1,1,0>, <0,0,0,1,2,1,0>, <0,0,0,2,0,1,0>, <0,0,0,2,1,1,0>, <0,0,0,2,2,1,0>}
∪
{<0,0,2,1,0>, <0,0,2,0,1,0>, <0,0,2,1,1,0>, <0,0,2,2,1,0>, <0,0,2,0,0,1,0>, <0,0,2,0,1,1,0>, <0,0,2,0,2,1,0>, <0,0,2,1,0,1,0>, <0,0,2,1,1,1,0>, <0,0,2,1,2,1,0>, <0,0,2,2,0,1,0>, <0,0,2,2,1,1,0>, <0,0,2,2,2,1,0>}