Einblick in die statische Code-Analyse:
Auf verschlungenen Pfaden
Fortsetzung des Artikels von Teil 2
Wandeln auf unbekannten Pfaden
Die Pfadempfindlichkeit ist aus mehreren Gründen entscheidend: Erstens ermöglicht sie Genauigkeit, d.h. weil sie undurchführbare Pfade erkennt, werden keine Fehler gemeldet, die vom Befolgen dieser Pfade abhängen. Zweitens kann für den Fall, dass der Endnutzer eine Warnung zu einem potenziellen Fehler erhält, der Pfad durch das Programm angezeigt werden, dem die Ausführung zur Auslösung des Fehlers folgen muss. Viele der heimtückischsten und am schwersten auffindbaren Bugs sind sehr subtil, da sie von ungewöhnlichen Umständen abhängen. Indem ein pfadempfindlicher Algorithmus auch solche nur selten ausgeführten Pfade erforscht, kann er diese Fehler finden.
Fortgeschrittene Statische-Analyse-Werkzeuge sind interprozedural, pfadempfindlich und für ganze Programme nutzbar. Vor allem ist zu bedenken, dass in den meisten Programmen eine unübersehbar hohe Anzahl an Pfaden existiert. Durch eine einzelne Funktion mit n Bedingungen und ohne Schleifen oder Funktionsaufrufe führen 2N Pfade. Sind Funktionsaufrufe zulässig, beträgt die Anzahl der Pfade 2^(2N), und sind Schleifen erlaubt, ist diese Anzahl unbegrenzt. Bei einem asynchronen Kontrollfluss des Programms (beispielsweise mit einer Unterbrechungsroutine) oder bei Verwendung von Threads erhöht sich die Anzahl der Pfade noch weiter. Eine Analyseroutine kann also unmöglich jeden dieser Pfade einzeln prüfen. Analysewerkzeuge umgehen dies, indem sie nach Möglichkeit Pfade unter rationalen Gesichtspunkten zusammenführen und indem sie die Anzahl der überprüften Pfade und die Menge der generierten Informationen begrenzen. In einigen Fällen werden bestimmte Klassen von Pfaden gänzlich ignoriert (beispielsweise außergewöhnliche oder asynchrone Pfade). Dadurch kann das Analysewerkzeug seine Aufgabe mit vertretbarem Zeitaufwand erfüllen.
Angesichts der Tatsache, dass sich alle Pfade unmöglich detailliert überprüfen lassen, ist eine Kenntnis der Strategien hilfreich, mit denen Analysewerkzeuge diese Einschränkung überwinden. Ein Weg ist die oben erwähnte Zusammenführung von Pfaden. Doch auch dann kann die Analyse die festgelegte Zeitdauer überschreiten, bevor alle überprüft wurden. Hierbei besteht die Gefahr, dass die Analyse einen Fehler auf einem der nicht überprüften Pfade übersieht. Normalerweise wird die Analyse mehrere Male während der Lebensdauer der Software durchgeführt. Wird bei jeder Analyse die gleiche Gruppe von Pfaden übersprungen, kann ein Fehler auf einem nicht überprüften Pfad unbegrenzt lange verborgen bleiben.
Die Lösung für dieses Problem ist die randomisierte Pfadüberprüfung. Bei Einsatz dieser Technik wählt die Analyse die Pfade nach dem Zufallsprinzip aus. Die Sinnhaftigkeit dieser Methode lässt sich gut am Beispiel einer Funktion veranschaulichen, bei der aufgrund der großen Anzahl die Prüfung von nur durchschnittlich 50 % aller Pfade möglich ist. Werden bei jeder Analyse die gleichen Pfade überprüft, dann liegt die Chance, dass ein Fehler auf ewig unentdeckt bleibt, bei 50 %. Bei einer ganz und gar zufälligen Analyse verringert sich die Wahrscheinlichkeit, dass ein Fehler nicht gefunden wird, exponentiell. Nach einer Analyse liegt sie bei 50 %, nach zweien bei 25 % und nach drei Analysen bei 12,5 %. Durchsucht eine Analyse p % der Pfade nach dem Zufallsprinzip, liegt die Wahrscheinlichkeit der Entdeckung eines Fehlers nach n Analysen bei (1–p)n.
Als einziger Nachteil der randomisierten Pfadüberprüfung ist die Analyse nicht deterministisch. Sie kann bei jedem Durchlauf unterschiedliche Fehlermeldungen anzeigen, was Benutzer zuweilen als störend empfinden. Nach dem Auffinden und Beheben eines Fehlers führt der Nutzer eine Analyse mit der Erwartung durch, dass die Wirksamkeit der Fehlerbeseitigung bestätigt wird. Nichtdeterminismus bedeutet, dass der Nutzer die Analyse mehrmals durchführen muss, um sicher zu sein, dass durch die Behebung des einen keine neuen Fehler entstanden sind. Diese Sorge ist zwar nicht unbegründet, in der Praxis überlappen sich allerdings bei Tools, die mit randomisierter Pfadüberprüfung arbeiten, die angezeigten Fehlermeldungen der einzelnen Analyse um 95 bis 98 %. Die Mathematik beweist, dass die randomisierte Pfadüberprüfung langfristig der deterministischen Überprüfung überlegen ist.
Zusammenführung
Für das Analyse-Tool gilt: Die Einheit der Granularität ist die Funktion. Zuerst erfolgt die topografische Ordnung des Aufrufdiagramms, sodass die Aufrufer über den Aufgerufenen stehen. Die Analyse beginnt mit den äußeren Funktionen, also denen, die keine anderen Funktionen aufrufen. Jeder Pfad wird auf eine Art untersucht, die einer abstrakten Ausführung ähnelt. Geht die Kontrolle von einer Anweisung auf die nächste über, aktualisiert die Analyse ein Gleichungssystem, das den Programmstatus modelliert. Trifft die Analyse auf einen Zweig, überprüft sie diese Gleichungen zuerst. Auf diese Weise stellt sie fest, ob entweder der wahre oder der falsche Zweig untersucht werden kann, sodass sie die Kontrolle undurchführbarer Pfade vermeidet. Im Verlauf dieser Überprüfung kann die Analyse ergeben, dass die Bedingungen für einen Laufzeitfehler erfüllt sind. Sind diese Bedingungen nicht kontextabhängig, erfolgt eine potenzielle Warnmeldung. Sind sie in der Tat kontextabhängig, wird ein Auslöser generiert. Er hat die Form einer Gleichung mit einigen freien Variablen und gibt die Bedingungen vor, die ein Fehler erfüllen muss, um offenkundig zu sein. Zum Einsatz kommt dies, wenn mehr Kontext verfügbar ist. Ist die Untersuchung einer Funktion abgeschlossen, bilden die Ergebnisse eine Gruppe von Zusammenfassungen, die den Effekt des Aufrufs einer Funktion und die eingangs erwähnten Auslöser verschlüsseln.
Die Analyse wird entlang des Aufrufdiagramms fortgesetzt. Die Untersuchung aller Aufruf-Funktionen erfolgt genauso wie bei den Aufgerufenen. Wird jedoch ein Funktionsaufruf gefunden, dienen die Gleichungen zur Zusammenfassung der Statusaktualisierung. Können die Auslöser für den Aufgerufenen in diesem Kontext erfüllt werden, kommt es zu einer potenziellen Warnmeldung. Dieser Prozess setzt sich bis an die Spitze des Aufrufdiagramms so lange fort, bis alle Funktionen analysiert sind.
Nicht zwingend führen die potenziellen Warnmeldungen zur Ausgabe einer Warnung. Stattdessen gibt es einen mehrstufigen Verfeinerungsprozess, mit Hilfe dessen eine noch gründlichere Prüfung des Pfades erfolgt. Die letzte Stufe nutzt eine bei weitem leistungsfähigere Schlussfolgerungs-Engine als die in der Pfadüberprüfung angewendete (ihr früherer Einsatz würde zu viel Zeit in Anspruch nehmen). CodeSonar nutzt dafür einen SMT-Solver. Kommt diese Engine nicht zu dem Ergebnis, dass der Pfad durchführbar ist, wird die Warnung als falsch-positiver Treffer verworfen. Wird der Pfad als durchführbar erkannt, erhält der Nutzer eine Fehlermeldung.
Bei den meisten Tools zur fortgeschrittenen statischen Analyse kann der Nutzer die Analyse auf verschiedene Arten anpassen, angefangen bei der Änderung einiger Parameterwerte bis zum Schreiben von Erweiterungen in einem speziellen API zum Auffinden interessanter Domain-spezifischer Programmeigenschaften. Der folgende Abschnitt beschreibt einige Möglichkeiten im Kontext von CodeSonar.
Jobangebote+ passend zum Thema
- Auf verschlungenen Pfaden
- Einfache syntaktische Abfragen
- Wandeln auf unbekannten Pfaden
- Optimierung der Parameter
Lesen Sie mehr zum Thema
Das könnte Sie auch interessieren
Unit-Tests
In der Theorie großartig, aber …
Betriebssysteme
Kostenlos - bis das Geschäft läuft
Fünf Ursachen für unliebsame Firmware-Fehler
Rezepte fürs Bugfixing
Software-Entwicklung
Vorgetäuschte Hardware
Software-Entwicklung:
Wo kommen bloß die Fehler her?
