Einblick in die statische Code-Analyse:
Auf verschlungenen Pfaden
Fortsetzung des Artikels von Teil 1
Einfache syntaktische Abfragen
Statische-Analyse-Werkzeuge können viele verschiedene Eigenschaften des Codes berechnen. Einige davon sind sehr oberflächlich und erfordern keine ausgefeilten Algorithmen, wie beispielsweise eine Regel, die die Verwendung der Goto-Sprunganweisung verbietet. Ein Prüfprogramm, das Verletzungen dieser Regel erkennt, muss lediglich den ASB des Programms nach dem Vorkommen der Anweisung durchsuchen. Natürlich könnte man auch im Quelltext nach „Goto“ suchen – würde dann aber das Wort auch an irrelevanten Stellen, z.B. in Kommentaren, finden. Deshalb ist die Suche über den abstrakten Syntaxbaum überlegen. Ein Checker, der die Verwendung einer verbotenen unsicheren Funktion wie gets() erkennt, wird am besten durch eine einfache Suche in der Symboltabelle umgesetzt.
Viele Prüfprogramme müssen den Kontext kennen, in dem ein Programmkonstrukt auftritt. Beispielsweise enthalten einige Codierrichtlinien Variable, die in einem äußeren Gültigkeitsbereich deklariert werden. Um diese zu finden, muss ein Checker die Hierarchie der Gültigkeitsbereiche quer durchsuchen können und für jede Variablendeklaration herausfinden, ob sie in einem der übergeordneten Gültigkeitsbereiche erscheint. Obwohl eine solche Eigenschaft komplexer ist als die vorher angeführten Beispiele, ist sie dennoch nur eine einfache syntaktische Eigenschaft des Codes. Wirklich interessant sind die semantischen Eigenschaften des Codes, deren Berechnung ausgefeiltere Algorithmen erfordert.
Anspruchsvolle semantische Abfragen
Viele interessante Eigenschaften eines Codes ergeben sich aus dem Ablauf der Ausführung. Beispielsweise tritt ein Use-after-Free-Fehler auf, wenn ein Basisregister nach der Freigabe dereferenziert wird. Um solche Fehler aufzuspüren, reicht ein einfacher Musterabgleich von Programmkonstrukten nicht aus. Stattdessen muss die Analyse den Kontrollfluss zwischen den Programmteilen erörtern können. Analysealgorithmen, die dazu in der Lage sind, werden als flussempfindlich bezeichnet und können am einfachsten in einer Phase, die das Kontrollflussdiagramm des Programms durchläuft, implementiert werden. Die Flussempfindlichkeit ist für alle, auch die einfachsten oberflächlichen Eigenschaften von grundlegender Bedeutung. Selbst die Statische-Analyse-Werkzeuge der frühen Generationen finden mit Hilfe flussempfindlicher Algorithmen einige Fehler.
Generell lassen sich flussempfindliche Algorithmen vergleichsweise einfach implementieren, wenn sich alle relevanten Anweisungen im gleichen Unterprogramm (Prozedur) befinden. Kann ein Algorithmus lediglich den Kontrollfluss für jeweils eine Prozedur analysieren, spricht man von einem intraprozeduralen Algorithmus. Um bei dem vorher genannten Beispiel zu bleiben: Ein solcher Algorithmus kann keinen Use-after-Free-Fehler auffinden, wenn die Freigabe in einem und die Verwendung in einer anderen Prozedur stattfindet. Dafür ist eine interprozedurale Analyse nötig. Sie kann alle Aufrufe an andere Abläufe so behandeln, dass sie die gleiche Wirkung haben, oder so, dass sie unterschiedlich sind. Eine Analyse, die das Letztere wählt, wird als kontextempfindlich bezeichnet.
Erwähnenswert in diesem Zusammenhang: Damit ein interprozeduraler Algorithmus am wirkungsvollsten ist, muss die Analyse an einem Modell mit ganzem Programm durchführbar sein. Eine nur an jeweils einer Übersetzungseinheit durchgeführte Analyse kann für die in dieser Datei definierten Abläufe interprozedural sein, aber sie ist nutzlos bei der Suche nach Fehlern, die darauf zurückzuführen sind, dass der Fluss die Grenzen der Übersetzungseinheiten überschreitet.
Dies ist der erste Unterschied zwischen fortgeschrittenen Statische-Analyse-Werkzeugen und den Tools der frühen Generation, wie Lint und dessen Ableger. Solche Werkzeuge können keine interprozedurale Analyse eines gesamten Programms ausführen, es sei denn auf eine sehr eingeschränkte und umständliche Art.
Es ist nicht nur wichtig zu wissen, wie der Kontrollfluss das Programm durchläuft, sondern auch, wie der Programmstatus ist. Fortgeschrittene Werkzeuge der statischen Analyse stellen den Programmstatus als Satz von Beziehungen dar, die z.B. die Werte der Variablen, die Länge der Puffer und den Status von Objekten wie Dateibeschreibungen zeigen. Mit diesen Gleichungen lassen sich beispielsweise Fakten wie x < y+1 oder die Länge von Speicher b = j–2 modellieren.
Die besten Werkzeuge für eine fortgeschrittene statische Analyse sind zudem pfadempfindlich, d.h. sie können Programmeigenschaften für einzelne Pfade durch das Programm berechnen (Pfadempfindlichkeit subsummiert Flussempfindlichkeit). Das Kontrollflussdiagramm in Bild 2 veranschaulicht die Wichtigkeit dieser Tatsache. Durch den ersten Teil gibt es zwei Pfade: ABD und ACD. Ein pfadempfindlicher Algorithmus kann per definitionem keine Eigenschaft bei D berechnen, die davon abhängt, ob die Ausführung dem einen oder dem anderen Pfad folgt. Zu D ist einzig bekannt, dass x den Wert 1 oder 2 besitzt. Ein pfadempfindlicher Algorithmus kommt andererseits zum selben Ergebnis, weiß allerdings, dass x den Wert 1 besitzt, wenn die Ausführung dem Pfad ABD folgt, und den Wert 2 bei Pfad ACD. Dies wird bei der Betrachtung von Folgepfaden bis hin zu H wichtig. Der flussempfindliche Algorithmus kann nur folgern, dass es für x und y vier mögliche Werte gibt: (1, 3), (1, 4), (2, 3) und (2, 4). Allerdings kann ein pfadempfindlicher Algorithmus noch mehr, denn obwohl es vier Pfade gibt, sind nur zwei von ihnen möglich. Die Verzweigungsbedingungen sind die gleichen; wird also bei A der wahre Zweig genommen, ist dies auch bei E bindend. Demzufolge sind bei H nur zwei Werte für x und y möglich: (1, 3) und (2, 4).
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?
