Verbesserung von Testalgorithmen: Mathematische Ansätze beim Softwaretest

Neue Testdesignmethoden entstehen nicht immer gleichzeitig. Ein erheblicher Teil moderner Testpraktiken hat sich durch sorgfältige theoretische und experimentelle Arbeit bei der Anpassung mathematischer Modelle entwickelt. Obwohl man kein Mathematiker sein muss, um ein guter Tester zu sein, kann es von Vorteil sein, die theoretischen Grundlagen hinter Testmethoden zu verstehen.

Maximierung der Abdeckung und Minimierung der Anzahl von Testfällen

Mathematische Logik kann angewendet werden, um die Codeabdeckung für ein System zu optimieren. Betrachten wir ein einfaches Beispiel mit einer „if“-Anweisung, die zwei Zweige und eine lange logische Formel in der Bedingung enthält:

 if ( (& a2) & (!(a2 || a4) ) || a3 ) { # action 1 } else { # action 2 }

Um beide Zweige abzudecken, ist es notwendig, die Struktur der Formel zu verstehen. Man könnte sich fragen, was kann getan werden? Sie können diesen Codeabschnitt (logische Formel) jederzeit ausführlich testen, was zu 16 Tests führt. Allerdings ist das eine ganze Menge, und es sollten Anstrengungen unternommen werden, die Anzahl der Tests zu reduzieren. Die Anzahl der Tests kann mithilfe der MC/DC-Methode (Modified Condition/Decision Coverage) reduziert werden (ergibt 11–12 Tests). Wenn die Filialabdeckung zum Testen von Risiken ausreicht, sind nur zwei Tests erforderlich, es ist jedoch unklar, welche.

Um dieses Problem zu lösen, kann die Boolesche Algebra auf die logische Formel angewendet werden:

 if( (& a2) & (! (a2 || a4) ) || a3 ) = = ( (& a2) & ( (!a2 || !a4) ) || a3 ) = = ( a1 & a2 & !a2 & !a4 || a3 ) = = 0 || a3 = a3

Nach Umformung der Originalformel zeigt sich, dass nur eine Variable a3 tatsächlich Einfluss auf den Wahrheitswert hat. Dadurch wird das Erhalten von Testfällen einfacher (einer mit und der andere mit a3 == false ). Darüber hinaus wird deutlich, dass der Code nicht optimiert ist, da es seltsam ist, einen komplexen logischen Ausdruck zu haben, der nur von einer Variablen abhängt. Leider kommen solche Situationen in der Realität recht häufig vor und das bereitgestellte Beispiel ist relativ einfach.

Abschließend:

• 2 Tests, wenn umfassende Tests durchgeführt werden

• 2 Tests mit der MC/DC-Methode

• 2 Tests, ob Zweigstellenabdeckung angewendet wird

  
  

Im Allgemeinen können logische Ausdrücke mithilfe von Algebra, mathematischen Methoden und Algorithmen vereinfacht (minimiert) werden. Es gibt mindestens drei ähnliche Methoden. Direkte Transformationen mithilfe der Booleschen Algebra funktionieren, wie oben erläutert, immer. Es können Methoden zur Ausdrucksminimierung gefunden und angewendet werden, die die Merkmale der spezifischen Domäne berücksichtigen und sich dabei nicht nur auf Mathematik und Logik, sondern auch auf die Besonderheiten der Domäne stützen.

Optimierung paarweiser Tests

Bei der paarweisen Testmethode werden Testsätze so generiert, dass nicht alle möglichen Kombinationen von Eingabeparametern durch ausführliche Tests getestet werden (was zeit- und ressourcenintensiv sein kann), sondern dass Testsätze so gestaltet werden, dass jeder Parameterwert mit jedem kombiniert wird Wert der anderen getesteten Parameter mindestens einmal. Dadurch wird die Anzahl der Testfälle deutlich reduziert.

Es handelt sich um eine etablierte und häufig verwendete Methode. Leider funktioniert diese Methode jedoch nicht immer, da die Systeme immer komplexer werden. Es stellt sich die Frage: Reicht paarweises Testen aus, um ein komplexes System mit zahlreichen Eingabeparametern gründlich zu testen? Diese Frage beschäftigt viele Testexperten und Forscher, darunter auch das National Institute of Standards and Technology (NIST) in den Vereinigten Staaten.

• Pairwise finds 65-97% of errors
• 3-way finds 89-99% of errors
• 4-way finds 96-100% of errors
• 5-way finds 96-100% of errors
• 6-way finds 100% of errors

Studien zufolge werden beim paarweisen Testen in 65–97 % der Fälle Fehler gefunden. Wenn wir anfangen, nicht Parameterpaare, sondern Dreier- oder Viererpaare zu kombinieren, also k-Wege-Tests zu verwenden, erhalten wir eine größere Anzahl von Tests, fangen aber auch mehr Fehler ein.

Angenommen, ein System hat zwei Parameter mit jeweils drei Werten und drei Parameter mit jeweils zwei Werten:

• Pairwise: 10 tests with 14% coverage
• 3-way: 18 tests with 25% coverage
• 4-way: 36 tests with 50% coverage
• 5-way: 72 tests with 100% coverage

Sie können ein zufriedenstellendes Maß an Testabdeckung und eine akzeptable Anzahl von Testfällen wählen.

Die Grundlage für „pairwise“ sind orthogonale Arrays, die n-Tupel (Paare, Tripel, Quadrupel, ...) von Werten gleich oft enthalten.

Die übliche Grundlage für paarweise und k-Wege-Tests ist OA(N, V^k, t) , wobei:

• N ist die Anzahl der Zeilen

• k ist die Anzahl der Spalten

• V ist die Anzahl der verschiedenen Werte in einer Spalte

• t ist die Stärke (t=2 für paarweise)

  
  

In OA enthält jeder Satz von t Spalten alle t Tupel gleich oft.

Anstelle orthogonaler Matrizen ist es besser, abdeckende Matrizen zu verwenden. Diese Matrizen unterscheiden sich von orthogonalen Matrizen dadurch, dass jeder Wertesatz mindestens einmal und nicht „gleich oft“ vorkommt. In diesem Fall gibt es etwas weniger Tests. Bei abdeckenden Matrizen kann es zwar zu falschen Testfällen kommen, aber insgesamt ist der Testprozess deutlich schneller. Dadurch wird der Testprozess deutlich vereinfacht.

CA(N, V^k, t), wobei:

• N ist die Anzahl der Zeilen
• k ist die Anzahl der Spalten
• V ist die Anzahl der verschiedenen Werte in einer Spalte
• t ist die Stärke (t=2 für paarweise)

In CA enthält jeder Satz von t-Spalten alle t-Tupel mindestens einmal. Die Verwendung von Abdeckmatrizen ermöglicht den Übergang vom paarweisen zum k-Wege-Testen, ohne die Anzahl der Tests wesentlich zu erhöhen.

Systemzustände und Prüfung sich ändernder Systemzustände

Normalerweise (fast immer) hat ein System mehr als zwei Zustände: „funktioniert“ und „funktioniert nicht“. Betrachten wir einen Teil der Staaten, die eine Lagerbestellung haben. Ein Auftrag zum Kauf oder Verkauf von Aktien muss eine Reihe von Zuständen durchlaufen, damit die Transaktion abgeschlossen werden kann. Zuerst wird die Bestellung erstellt, dann von der Börse bestätigt, es folgen zahlreiche kleine Kauftransaktionen und schließlich wird die benötigte Menge an Aktien gekauft oder verkauft. Alle Zustände einer Aktienorder spiegeln sich in Handelssystemen wider und alle Übergänge und Zustände müssen selbstverständlich getestet werden.

Fast immer werden entweder alle Zustände oder alle Übergänge getestet, aber meistens werden beide überprüft. Eine vollständige Abdeckung ist erreichbar, aber zeitaufwändig, teuer und ressourcenintensiv.

Graphen und endliche Automaten

Betrachten wir das Problem des Handlungsreisenden (Commi Voyager) und den De-Bruijn-Algorithmus. Es genügt zu verstehen, dass der Algorithmus es ermöglicht, einen optimalen oder ausreichend optimalen Satz kurzer Pfade zu erhalten, die in einem Graphen durchlaufen werden können, um ihn vollständig abzudecken (streng genommen kann jeder andere Algorithmus verwendet werden, der etwas Ähnliches leistet, oder man kann einen erfinden benutzerdefinierter Algorithmus).

• Nehmen Sie zunächst die Anfangszustände des Systems und erstellen Sie ein neues Diagramm, bei dem die Eckpunkte den Übergängen im ursprünglichen Diagramm entsprechen.
• Als nächstes bedecken Sie die Eckpunkte des neuen Diagramms, also die Übergänge im alten.
• Einige Pfade sind offensichtlich und erweisen sich als recht kurz (was zum Testen von Zuständen und Übergängen des Systems sehr praktisch ist).
• Bauen Sie weitere Wege weiter. Dadurch können sie zu lang werden (und das ist nicht gut).

Betrachten wir das folgende Beispiel, um die Situation zu analysieren:

Es gibt drei Tester. Der Erste führt den ersten Test durch, der Zweite – den zweiten Test, der Dritte – den dritten Test. Die ersten beiden werden die ersten beiden Tests ziemlich schnell abschließen, da die Pfade kurz sind (im Vergleich zum dritten, da die ersten beiden Pfade kurz sind), aber der letzte wird sehr lange dauern (da der dritte Pfad sehr lang ist). lang).

Bei Anwendung des De-Bruijn-Algorithmus kann die dritte Sequenz in mehrere kürzere Sequenzen „zerschnitten“ werden und die Ausführung aller Tests effizient parallelisiert werden.

Wir können am Ende mehr Tests durchführen, aber im Falle einer parallelen Ausführung werden die Tests viel schneller abgeschlossen, da die Tests kürzer sind.

Darüber hinaus besteht bei mehr Tests eine größere Flexibilität bei der Ausführung. Alle Tests können gleichzeitig ausgeführt werden oder uninteressante und weniger wichtige Tests können entfernt werden. Tests, die die wichtigsten Zustände des Systems durchlaufen, können höhere Prioritäten zugewiesen werden. Es gibt viele Möglichkeiten, die Ergebnisse des Algorithmus zu nutzen.

Ein Pluspunkt ist, dass der Algorithmus keine domänenspezifischen Dinge verwendet; es arbeitet mit absolut abstrakten Zuständen und Übergängen des Systems.

Bei dieser Technik hängt viel davon ab, wie der Algorithmus verwendet wird. Im extremsten Fall wissen die Tester möglicherweise nichts über die Logik hinter den Übergängen zwischen Zuständen. In einer solchen Situation wird die lange Kette von Zustandsübergängen vom Algorithmus in mehrere kurze „geschnitten“. Einige dieser Ketten könnten sich als bedeutungslos erweisen. Daher müssen die erhaltenen Ketten auf ihre Plausibilität und diejenigen, die für den Test wichtig und aussagekräftig sind, bewertet werden. Sinnlos und unwichtig, aber mögliche Wege zur Änderung der Systemzustände können Aufschluss darüber geben, welcher Teil des Systems geändert werden muss, und es wird deutlich, welcher Teil genau ist.

Die wichtigsten Schlussfolgerungen können wie folgt betrachtet werden:

• Algorithmen zur Minimierung logischer Ausdrücke sorgen für maximale Testabdeckung bei minimalem Aufwand. Es ist nicht immer notwendig, Minimierungsalgorithmen zu verwenden – manchmal ist es Zeitverschwendung; Es gibt universelle Ansätze.
• Eine vollständige Testabdeckung könnte mit einem kleinen Satz kurzer Testfälle erreicht werden, die einfach zu parallelisieren, zu automatisieren, flexibel und unabhängig sind.
• Die Analyse von Statistiken zur Anwendungsnutzung unter realen Bedingungen ermöglicht die Optimierung und Anpassung bestehender Testdesigntechniken und das Erreichen der erforderlichen Testabdeckung, wodurch die Anwendungsqualität gewährleistet wird.
• Die Modifikation des paarweisen Testens ermöglicht tiefgreifendere Tests mit größerer Testabdeckung als Standardalgorithmen und mit nahezu den gleichen Ressourcen.
• Einige Algorithmen können in Fällen effektiv sein, in denen Standardtestdesigntechniken weniger effizient sind.
• Das Scheitern kombinatorischer Testentwurfstechniken bringt einige Herausforderungen mit sich.
• Die erhaltenen Algorithmen können leicht an verschiedene Systeme angepasst werden und erfordern keine besonderen Kenntnisse der Domäne.

Was kleinere Nachteile betrifft, ist es erwähnenswert:

• Einige Algorithmen sind nicht in allen Fällen effektiv und relevant. In vielen Situationen sind Standardtechniken für den Testentwurf gleichermaßen oder manchmal sogar effektiver.
• Die Anwendung von Algorithmen erfordert einige mathematische Kenntnisse und manchmal mehr Zeit für ihre Anwendung, sodass sie in vielen Situationen auch ein entscheidender Faktor sein kann.