Dr.-Ing. Norbert Oster, Akad. ORat - DOTgEAr

imageUnivIS-Beauftragte, Wiss. Mitarbeiter
Sprechstunde:
    nach Vereinbarung, Raum 05.158, (Anmeldung bitte per Mail)

Navigation


Automatische datenflussorientierte Testfallerzeugung für objekt-orientierte Softwaresysteme mittels Evolutionärer Verfahren

Downloads:


Kurzbeschreibung:

.gEAr-Meilensteine
Die Zunahme der Komplexität moderner Softwaresysteme stellt trotz deutlich verbesserter Entwicklungsmethoden heute noch das Haupthindernis auf dem Weg zur fehlerfreien Programmerstellung dar. Größe und Budget heutiger Projekte verbieten meist eine vollständige formale Verifikation, die selbst in realisierbaren Fällen nur die logische Domäne der Programme und nicht ihr reales Umfeld einbezieht, weshalb dem Testen als Qualitätssicherungsmaßnahme vor der Freigabe der Software ein hoher Stellenwert eingeräumt wird. Um die Chancen der Fehlererkennung während der Testphase zu erhöhen, werden Testfälle nach unterschiedlichen Strategien ausgewählt: Während funktionales Testen die Eingaben aus den spezifizierten Anforderungen herleitet, streben strukturelle Tests eine möglichst vollständige Ausführung des Codes an. Bedingt durch die Komplexität der Kontrollstrukturen ist die Ermittlung geeigneter Testdaten zur Erfüllung datenflussorientierter Überdeckungskriterien besonders zeitaufwändig. Selbst wenn Testdaten zufällig generiert werden, müssen sie darüber hinaus meist manuell auf Korrektheit überprüft werden, so dass ihre Anzahl entscheidend zu Buche schlägt.
Ziel des laufenden Projekts ist es, die Generierung adäquater Mengen datenflussorientierter Testfälle zu automatisieren und unterschiedliche Verfahren hinsichtlich ihrer Eignung nach verschiedenen Kriterien (Güte, Aufwand) zu untersuchen. Als geeignete Such- und Optimierungsalgorithmen haben sich Evolutionäre Verfahren in unterschiedlichen Anwendungen erwiesen. Bisherige Arbeiten empfehlen bereits Genetische Algorithmen, jedoch wurde ihre Anwendbarkeit lediglich auf einfache Kontrollflusskriterien (etwa nach erzielten Anweisungs- oder Verzweigungsüberdeckungsmaßen) untersucht. Auch hat man bisher entweder eigene Programmiersprachen definiert oder bestehende soweit eingeschränkt, dass die Verfahren nicht mehr ohne weiteres auf reale Projekte übertragbar sind.

Erreichte Meilensteine:

  • Dynamische Analyse der Testausführung
    Um die während der Ausführung eines Testfalls tatsächlich überdeckten Definitions- / Benutzungspaare (sogenannter def/use Paare) zu ermitteln, wurde ein Werkzeug zur Überwachung der dynamischen Ausführung eines Java-Programms entwickelt. Dieses Werkzeug instrumentiert den Quellcode des Testobjekts so, dass während eines einzelnen Testlaufs alle dazu relevanten Datenflussinformationen protokolliert werden. Die Ergebnisse wurden anlässlich der internationalen Tagung PSAM7/ESREL'04 publiziert.
  • Globale Optimierung von Testdatensätzen
    Aufbauend auf der dynamischen Bewertung der von einem Testdatensatz erzielten Überdeckung wurde ein Verfahren entwickelt, um optimale Testdatensätze mittels klassischer und evolutionärer Suchstrategien zu generieren. Dabei werden Testdatensätze nach ihrem zu minimierenden Umfang sowie der zu maximierenden Anzahl der von ihnen überdeckten Datenflusspaare bewertet. Die erzielte globale Optimierung erfordert keine detaillierte Kenntnis der Kontrollflussstruktur des Testobjekts. Zur Generierung der Testdatensätze wurden unterschiedliche selbstadaptive Evolutionäre Verfahren sowie genetische Operatoren eingesetzt und vergleichend bewertet. Die verschiedenen Kombinationen wurden in einem parallelisierten, verteilten Werkzeug realisiert und getestet. Einzelheiten wurden von der GI-Fachgruppe TAV veröffentlicht.
  • Statische Analyse des Testobjekts
    Zur Bewertung der relativen Güte der vom Evolutionären Verfahren ermittelten Ergebnisse wird zusätzlich zu den tatsächlich erreichten Überdeckungsmaßen (siehe dynamische Analyse) die Kenntnis der maximal erzielbaren Überdeckung benötigt, das heißt der Gesamtanzahl der von Tests auszuführenden Knoten, Kanten und Teilpfade des Kontrollflussgraphen. Zu diesem Zweck wurde ein statischer Analysator realisiert, welcher darüber hinaus auch die jeweiligen Definitionen und Benutzungen (sowie alle sie verbindenden DU-Teilpfade) jeder Variablen im datenflussannotierten Kontrollflussgraphen lokalisiert. Ergänzt um die Ergebnisse der dynamischen Analyse kann zum einen ein besseres Abbruchkriterium für die globale Optimierung definiert werden, zum anderen wird die im folgenden beschriebene lokale Optimierung unterstützt.
  • Bestimmung des Fehleraufdeckungspotentials der automatisch generierten Testfälle
    Zusätzlich zur Bewertung der relativen Güte einer Testfallmenge im Sinne der Überdeckung (siehe statische Analyse) wurde im vorliegenden Projekt auch eine Schätzung der Qualität automatisch generierter Testfälle durch Betrachtung ihres Fehleraufdeckungspotentials angestrebt. Dazu wurde ein Back-to-back-Testverfahren nach dem Prinzip des Mutationstestens umgesetzt. Dabei werden repräsentative Fehler in das ursprüngliche Programm injiziert und das Verhalten der modifizierten Variante bei der Ausführung der generierten Testfälle mit dem der unveränderten Fassung verglichen. Der Anteil der verfälschten Programme, bei denen eine Abweichung im Verhalten aufgedeckt werden konnte, ist ein Indikator für das Fehleraufdeckungspotential der Testfallmenge. Die Ergebnisse der letzten beiden Teilaufgaben wurden anlässlich der internationalen Tagung SOQUA 2005 publiziert.
  • Ausdehnung des Ansatzes auf weitere Teststrategien
    Das entwickelte Verfahren zur multi-objektiven Generierung und Optimierung von Testfällen lässt sich auch auf andere Teststrategien übertragen. Wählt man Überdeckungskriterien, welche zu den betrachteten datenflussorientierten Strategien orthogonal sind, ist die Erkennung anderer Fehlerarten zu erwarten. Im Rahmen eines Teilprojektes wurde beispielsweise ein Ansatz zur statischen Analyse des Testobjekts und dynamischen Analyse der Testausführung im Hinblick auf das Kriterium der Bedingungsüberdeckung entwickelt und implementiert. Ebenso wurde in einem weiteren Teilprojekt eine Unterstützung für das Kriterium der strukturellen Grenzwerttestüberdeckung umgesetzt, wodurch in Kombination mit den bestehenden Kriterien eine zusätzliche Erhöhung der Fehleraufdeckungsquote zu erwarten ist.
  • Ergänzung des Verfahrens um automatische Testtreibergeneratoren
    Da für die automatische Generierung von Testfällen spezialisierte Testtreiber notwendig sind, welche sich nur bedingt zur manuellen Überprüfung der Testergebnisse eignen, wurde darüber hinaus im Rahmen eines Teilprojektes eine zweistufige automatische Testtreibergenerierung umgesetzt. Diese erstellt zunächst parametrisierbare Testtreiber, welche ausschließlich während der Testfalloptimierung eingesetzt werden, und übersetzt diese anschließend in die übliche jUnit-Syntax, sobald die generierten und optimierten Testdaten vorliegen.
  • Experimentelle Bewertung des entwickelten Werkzeugs
    Die praktische Relevanz des entwickelten Verfahrens wurde in verschiedenen experimentellen Einsätzen erprobt und bewertet. Als Testobjekte dienten dabei Java-Packages mit bis zu 27 Klassen (5439 Codezeilen). Die nebenläufige Testausführung während der Generierung und Optimierung der Testfälle wurde auf bis zu 58 vernetzten Rechnern parallelisiert. Die Ergebnisse wurden anlässlich der internationalen Tagung SAFECOMP 2006 veröffentlicht.

Geplante Meilensteine:

  • Erweiterung des Leistungsumfangs der automatischen Generierung
    Zusätzlich zu den bereits unterstützten Testkriterien aus der Familie der Kontroll- und Datenflussstrategien, wird die Methode und das umgesetzte Werkzeug auf weitere Testverfahren ausgedehnt. Auf der Basis der bereits entwickelten Verfahren und Werkzeuge, ist zu untersuchen, wie die obigen Forschungsergebnisse unter Einsatz von fach-spezifischem Wissen dahingehend erweitert und verbessert werden können, um die Heuristiken schneller und effizienter zu gestalten - beispielweise unter Einsatz verteilter Evolutionärer Verfahren.
  • Portierung des Werkzeugs zur Unterstützung weiterer Programmiersprachen
    Nachdem die Implementierung der automatischen Erstellung von Testtreibern und der Generierung und Optimierung von Testdaten für Java-Programme bereits erfolgreich abgeschlossen wurde, ist die breitere Anwendbarkeit des Werkzeugs in der Industrie dadurch zu erreichen, dass die Unterstützung weiterer Programmiersprachen angeboten wird. Dazu gehört insbesondere die im eingebetteten Bereich verbreitete Familie der Sprache C - darunter die aktuelleren Derivate C++ und C#. Aufbauend auf den bisherigen Erkenntnissen für Java wird das bestehende Werkzeug um eine statische und eine dynamische Analyse für C#-Programme ergänzt.
  • Generierung zusätzlich erforderlicher Testdaten mittels lokaler Optimierung
    Aus der bereits erfolgten Lokalisierung der Datenflusspaare (siehe statische Analyse) lassen sich insbesondere die für die Erfüllung des Testkriteriums fehlenden Testpfade ermitteln. Zugehörige Testfälle sollen durch die Anwendung Evolutionärer Verfahren in einer lokalen Optimierung generiert werden. Dazu wird eine neue Fitnessfunktion aufgrund graphentheoretischer Eigenschaften des Kontrollflussgraphen definiert. Die bereits umgesetzte Instrumentierung (dynamische Analyse) des Testobjekts wird passend erweitert. Somit wird die automatische Generierung der Testfälle gezielter lokal gelenkt und hinsichtlich Zeitaufwand und erzielter Datenflussabdeckung weiter verbessert.
watermark seal