Gibt es formalisierte / mathematische Theorien zum Testen von Software?

12

Googeln "Software-Test-Theorie" scheint nur Theorien im weichen Sinne des Wortes zu geben; Ich habe nichts gefunden, was als Theorie im mathematischen, informationstheoretischen oder in einem anderen wissenschaftlichen Sinne klassifiziert werden könnte.

Was ich suche, ist etwas, das formalisiert, was Testen ist, die verwendeten Begriffe, was ein Testfall ist, die Machbarkeit, etwas zu testen, die Praktikabilität, etwas zu testen, das Ausmaß, in dem etwas getestet werden sollte, formale Definition / Erklärung von Codeabdeckung usw.

UPDATE: Ich bin mir auch nicht sicher, was die Verbindung zwischen der formalen Verifizierung und dem, was ich gefragt habe, betrifft, aber es gibt eindeutig eine Art von Verbindung.

Erik Kaplun
quelle
1
Softwaretests sind sehr wertvoll (z. B. Umsetzen von Unit-Tests in die Praxis), aber ihre Theorie wird immer einige Lücken aufweisen. Betrachten Sie dieses klassische Beispiel, double pihole(double value) { return (value - Math.PI) / (value - Math.PI); }das ich von meinem Mathematiklehrer gelernt habe . Dieser Code hat genau eine Lücke , die allein durch Black-Box-Tests nicht automatisch erkannt werden kann. In der Mathematik gibt es kein solches Loch. Im Kalkül dürfen Sie das Loch schließen, wenn die einseitigen Grenzen gleich sind.
rwong
4
Dies könnte einen Teil von dem , was Sie suchen - en.wikipedia.org/wiki/Formal_verification
enderland
1
Ich stimme dem Vorschlag von @ enderland zu. Es spielt keine Rolle, wie rigoros Ihre Herangehensweise an das Testen ist. Einige Fehler rutschen immer noch durch die Ritzen, und wenn Sie den Code mit Ihren Tests vertiefen, steigen die Kosten für die Suche nach neuen Fehlern. Dies ist wahrscheinlich der Grund, warum sich niemand die Mühe gemacht hat, den Begriff des Testens zu formalisieren - ein "heuristischer" Ansatz funktioniert mit weniger Training fast genauso gut.
Doval
Seitdem habe ich mich über abhängige Typen mit dem Land der formalen Verifikation vertraut gemacht und kann @Doval und enderland voll und ganz zustimmen.
Erik Kaplun
1
@rwong Ich nehme an, Sie spielen auf die Möglichkeit an, dass sowohl Zähler als auch Nenner gleich Null sind. Teilweise liegt das Problem am schlechten Design dieser Funktion. Wenn Sie über die mathematische formale Verifizierung sprechen, müssen Sie Ihre Funktionen nicht willkürlich, sondern nach formalen Regeln auf der Grundlage korrekter Datentypen zusammenstellen. In diesem Beispiel müsste die Divisionsfunktion verwendet werden (a,b)=>a/b, die um einen Überlaufwert erweitert werden muss, um korrekt zusammengesetzt werden zu können.
Dmitri Zaitsev

Antworten:

5

Ich kann nicht auf eine gute Online-Ressource verweisen (die englischen Wikipedia-Artikel zu diesen Themen sind in der Regel verbesserungsfähig), aber ich kann eine Vorlesung zusammenfassen, die auch grundlegende Testtheorien behandelte.

Testmodi

Es gibt verschiedene Testklassen, wie Unit-Tests oder Integrationstests . Ein Komponententest bestätigt, dass ein zusammenhängendes Stück Code (Funktion, Klasse, Modul), das für sich genommen erstellt wurde, wie erwartet funktioniert, während ein Integrationstest bestätigt, dass mehrere solcher Teile korrekt zusammenarbeiten.

Ein Testfall ist eine bekannte Umgebung, in der ein Teil des Codes ausgeführt wird, z. B. durch Verwendung einer bestimmten Testeingabe oder durch Verspotten anderer Klassen. Das Verhalten des Codes wird dann mit dem erwarteten Verhalten verglichen, z. B. einem bestimmten Rückgabewert.

Ein Test kann nur das Vorhandensein eines Fehlers beweisen, niemals das Fehlen aller Fehler. Tests setzen eine Obergrenze für die Programmkorrektheit fest.

Code-Abdeckung

Um Kennzahlen für die Codeabdeckung zu definieren, kann der Quellcode in ein Kontrollflussdiagramm übersetzt werden, in dem jeder Knoten ein lineares Codesegment enthält. Die Steuerung fließt nur am Ende jedes Blocks zwischen diesen Knoten und ist immer bedingt (wenn Bedingung, dann gehe zu Knoten A, sonst gehe zu Knoten B). Der Graph hat einen Startknoten und einen Endknoten.

  • Mit diesem Diagramm wird die Anweisungsabdeckung dargestellt das Verhältnis aller besuchten Knoten zu allen Knoten. Eine vollständige Berichterstattung ist für gründliche Tests nicht ausreichend.
  • Zweigabdeckung ist das Verhältnis aller besuchten Kanten zwischen Knoten in der CFG zu allen Kanten. Dadurch werden Schleifen nicht ausreichend getestet.
  • Die Pfadabdeckung ist das Verhältnis aller besuchten Pfade zu allen Pfaden, wobei ein Pfad eine beliebige Folge von Kanten vom Anfang bis zum Endknoten ist. Das Problem ist, dass es bei Schleifen unendlich viele Pfade geben kann, sodass die vollständige Pfadabdeckung praktisch nicht getestet werden kann.

Es ist daher oft nützlich, die Bedingungsüberdeckung zu überprüfen .

  • In der einfachen Bedingungsabdeckung ist jede atomare Bedingung einmal wahr und einmal falsch - dies garantiert jedoch keine vollständige Bedingungsabdeckung.
  • In der Mehrfachbedingungsabdeckung haben die atomaren Bedingungen alle Kombinationen von trueund angenommen false. Dies setzt eine vollständige Zweigabdeckung voraus, ist jedoch ziemlich teuer. Das Programm kann zusätzliche Einschränkungen haben, die bestimmte Kombinationen ausschließen. Diese Technik ist gut, um eine Zweigabdeckung zu erhalten, kann toten Code finden, kann jedoch keine Fehler finden, die von der falschen Seite stammen Zustand zurückzuführen sind.
  • In der minimalen Mehrfachbedingungsabdeckung ist jede atomare und zusammengesetzte Bedingung einmal wahr und falsch. Dies impliziert immer noch eine vollständige Zweigabdeckung. Es handelt sich um eine Teilmenge der Mehrfachbedingungsabdeckung, die jedoch weniger Testfälle erfordert.

Bei der Erstellung von Testeingaben unter Verwendung der Bedingungsabdeckung sollte der Kurzschluss berücksichtigt werden. Beispielsweise,

function foo(A, B) {
  if (A && B) x()
  else        y()
}

muss mit getestet werden foo(false, whatever), foo(true, false)undfoo(true, true) für eine vollständige minimale Abdeckung mehrerer Zustände.

Wenn Sie Objekte haben, die sich in mehreren Zuständen befinden können, ist es sinnvoll, alle Zustandsübergänge analog zu Kontrollabläufen zu testen.

Es gibt einige komplexere Kennzahlen für die Abdeckung, sie ähneln jedoch im Allgemeinen den hier dargestellten Kennzahlen.

Dies sind White-Box- Testmethoden, die teilweise automatisiert werden können. Beachten Sie, dass eine Unit-Test-Suite eine hohe Codeabdeckung durch eine ausgewählte Metrik anstreben sollte, jedoch nicht immer 100%. Es ist besonders schwierig, die Ausnahmebehandlung zu testen, wenn Fehler an bestimmten Stellen injiziert werden müssen.

Funktionstests

Dann gibt es Funktionstests, die bestätigen, dass der Code der Spezifikation entspricht, indem die Implementierung als Black Box betrachtet wird. Solche Tests sind sowohl für Komponententests als auch für Integrationstests nützlich. Da es unmöglich ist, mit allen möglichen Eingabedaten zu testen (z. B. die Stringlänge mit allen möglichen Strings zu testen), ist es nützlich, die Eingabe (und Ausgabe) in äquivalente Klassen zu gruppieren - wenn dies length("foo")korrekt foo("bar")ist, funktioniert dies wahrscheinlich auch. Für jede mögliche Kombination zwischen Eingangs- und Ausgangsäquivalenzklassen wird mindestens ein repräsentativer Eingang ausgewählt und getestet.

Man sollte zusätzlich testen

  • Grenzfälle length(""), foo("x"), length(longer_than_INT_MAX),
  • Werte, die von der Sprache, aber nicht vom Vertrag der Funktion zugelassen sind length(null), und
  • mögliche Junk-Daten length("null byte in \x00 the middle")...

Bei numerischen Werten bedeutet dies Testen 0, ±1, ±x, MAX, MIN, ±∞, NaNund bei Gleitkommavergleichen Testen von zwei benachbarten Gleitkommazahlen. Als weitere Ergänzung können zufällige Testwerte aus den Äquivalenzklassen ausgewählt werden. Um das Debuggen zu vereinfachen, lohnt es sich, den verwendeten Startwert aufzuzeichnen.

Nichtfunktionale Tests: Belastungstests, Stresstests

Eine Software hat nicht-funktionale Anforderungen, die ebenfalls getestet werden müssen. Dazu gehört das Testen an den definierten Grenzen (Lasttests) und darüber hinaus (Stresstests). Bei einem Computerspiel kann dies bedeuten, dass in einem Auslastungstest eine Mindestanzahl von Bildern pro Sekunde festgelegt wird. Eine Website wird möglicherweise einem Stresstest unterzogen, um die Antwortzeiten zu ermitteln, wenn doppelt so viele Besucher wie erwartet die Server beschädigen. Solche Tests sind nicht nur für ganze Systeme relevant, sondern auch für einzelne Entitäten. Wie verschlechtert sich eine Hash-Tabelle mit einer Million Einträgen?

Andere Arten von Tests sind Tests des gesamten Systems, bei denen Szenarien simuliert werden, oder Abnahmetests zum Nachweis, dass der Entwicklungsvertrag erfüllt wurde.

Nicht-Testmethoden

Bewertungen

Es gibt nicht testende Techniken, die zur Qualitätssicherung eingesetzt werden können. Beispiele sind exemplarische Vorgehensweisen, formale Codeüberprüfungen oder Paarprogrammierung. Während einige Teile automatisiert werden können (z. B. durch Verwendung von Linters), sind diese im Allgemeinen zeitintensiv. Codeüberprüfungen durch erfahrene Programmierer weisen jedoch eine hohe Fehlerentdeckungsrate auf und sind besonders während des Entwurfs nützlich, wenn keine automatisierten Tests möglich sind.

Warum schreiben wir immer noch Tests, wenn Code-Reviews so gut sind? Der große Vorteil von Testsuiten besteht darin, dass sie (meistens) automatisch ausgeführt werden können und daher für Regressionstests sehr nützlich sind .

Formale Überprüfung

Die formale Verifizierung geht und beweist bestimmte Eigenschaften des Codes. Die manuelle Überprüfung ist vor allem für kritische Teile und weniger für ganze Programme sinnvoll. Beweise setzen der Programmkorrektheit eine Untergrenze . Proofs können bis zu einem gewissen Grad automatisiert werden, z. B. über eine statische Typprüfung.

Bestimmte Invarianten können mit assertAnweisungen explizit überprüft werden .


Alle diese Techniken haben ihren Platz und ergänzen sich. TDD schreibt die Funktionstests im Voraus, aber die Tests können anhand ihrer Abdeckungsmetriken beurteilt werden, sobald der Code implementiert ist.

Das Schreiben von testbarem Code bedeutet das Schreiben kleiner Codeeinheiten, die separat getestet werden können (Hilfsfunktionen mit geeigneter Granularität, Prinzip der Einzelverantwortung). Je weniger Argumente jede Funktion benötigt, desto besser. Ein solcher Code eignet sich auch zum Einfügen von Scheinobjekten, z. B. durch Abhängigkeitsinjektion.

amon
quelle
2
Ich die aufwendige Antwort zu schätzen wissen, aber ich fürchte , es so gut wie nichts mit dem zu tun hat , was ich fragte :) Aber, zum Glück, programmers.stackexchange.com/questions/78675/... scheint so nah zu sein , wie es kommt , was ich anstreben.
Erik Kaplun
Das ist großartiges Zeug. Kannst du irgendwelche Bücher oder Dinge empfehlen?
Marcin
4

Vielleicht beantwortet "spezifikationsbasiertes Testen" auch Ihre Frage. Überprüfen Sie diese Testmodule (die ich noch nicht verwendet habe). Sie müssen einen mathematischen Ausdruck schreiben, um Sätze von Testwerten anzugeben, anstatt einen Einheitentest unter Verwendung ausgewählter einzelner Datenwerte zu schreiben.

Test :: Lectrotest

Wie der Autor sagt, wurde dieses Perl-Modul von Haskells Quick-Check-Modul inspiriert . Es gibt weitere Links auf dieser Seite, von denen einige tot sind.

knb
quelle
2

Ein mathematisch basierter Ansatz ist das Testen aller Paare . Die Idee ist, dass die meisten Fehler durch die Auswahl einer einzelnen Konfigurationsoption aktiviert werden und der größte Teil der verbleibenden Fehler durch ein bestimmtes Paar von Optionen, die gleichzeitig ausgeführt werden. Somit können die meisten durch Testen "aller Paare" gefangen werden. Eine mathematische Erklärung (mit Verallgemeinerungen) finden Sie hier:

Das AETG-System: Ein Ansatz zum Testen basierend auf kombinatorischem Design

(Es gibt noch viele weitere Referenzen)

David Ketcheson
quelle
2

Es werden einige mathematische Gleichungen verwendet, dies hängt jedoch von der Art der von Ihnen verwendeten Softwaretests ab. Beispielsweise geht die Annahme kritischer Fehler davon aus, dass Fehler kaum das Produkt von zwei oder mehr gleichzeitigen Fehlern sind. Die folgende Gleichung lautet: f = 4n + 1. f = Funktion, die die Anzahl der Testfälle für eine gegebene Anzahl von Variablen ( n) + 1 berechnet, ist die Addition der Konstanten, wobei alle Variablen den Nennwert annehmen.

Eine andere Art von Tests , die mathematische Gleichungen erfordert , ist Robustheitstest die Robustheit testet, oder Richtigkeit von Testfällen in einem Testprozess. In diesem Test würden Sie Variablen innerhalb des zulässigen Eingabebereichs (fehlerfreie Testfälle) und Eingabevariablen außerhalb des Eingabebereichs (fehlerhafte Testfälle) eingeben. Sie würden die folgende mathematische Gleichung verwenden: f = 6n + 1 . 6n gibt an, dass jede Variable 6 verschiedene Werte annehmen muss, während die anderen Werte den Nennwert annehmen. * + 1 * steht für die Addition der Konstanten 1.

Charles Lucas Shabazz
quelle