Über die effizienz des automatischen testens

Abstract

Wir analysieren die Effizienz des zufälligen und systematischen Ansatzes zum automatischen Programmtesten. Dabei nutzen wir wenige, einfache, jedoch realistische Annahmen um ein generelles probabilistisches Modell für das Softwaretesten zu entwickeln. Die zwei wichtigsten Ziele des automatischen Softwaretestens sind (i) in minimaler Zeit mit einem gewissen Zuversichtsgrad x festzustellen, daß das Programm korrekt funktioniert und (ii) eine maximale Anzahl an Fehlern innerhalb eines gegebenen Zeitbudgets $\hat n$ im Programm zu finden. Zu beiden Fällen berechnen wir eine obere Schranke für die Zeit eines systematischen Tests relativ zur Zeit eines zufälligen Tests. Im ersten Fall (i) zeigen wir auch, daß diese Schranke asymptotisch nur von x abhängt. Nehmen wir zum Beispiel an, daß ein Zufallstestgenerator R lediglich 10ms braucht um einen Test zu generieren und auszuführen. Um mit Zuversicht feststellen zu können, daß ein Programm P für 90\% seiner Eingaben korrekt funktioniert, darf der effektivste, systematische Testgenerator S0 nicht länger als 41ms brauchen um einen Test zu generieren und auszuführen! Andernfalls kann R im Durchschnitt schneller etablieren, daß P für 90\% seiner Eingaben korrekt funktioniert.