Code-Coverage undercover: Nutzen und Tücken Trace-basierter Codeabdeckung

Autor / Redakteur: Jens Braunes * / Holger Heller

Der Nachweis der Testqualität für sicherheitskritische Embedded-Systeme mit Hilfe von Code-Coverage-Analysen ist ein äußerst wichtiges, aber auch diffiziles Unterfangen.

Firmen zum Thema

Code-Coverage undercover: Trace-basierte Code-Coverage mit PLS richtig angehen
Code-Coverage undercover: Trace-basierte Code-Coverage mit PLS richtig angehen
(Bild: © stocksolutions - Fotolia)

Nach welchen grundlegenden Regeln man sich beim Softwaretest zur richten hat, geben einschlägige Normen wie ISO 26262 für den Automotive-Bereich vor. Dennoch offenbaren sich in deren praktischem Einsatz aber so manche Tücke, die es zu bewältigen gilt.

Um die Zuverlässigkeit eines Embedded-Systems beurteilen zu können, spielt die Qualität der verwendeten Tests eine maßgebliche Rolle. Eines der wichtigsten Werkzeuge zur Messung der Testgüte ist dabei die Code-Coverage-Analyse.

Bildergalerie
Bildergalerie mit 6 Bildern

Mittels dieser Analyse lässt sich ermitteln, ob durch die verwendenden Teststimuli oder die benutzten funktionalen Tests alle möglichen Programmteile bzw. Verzweigungen auch wirklich ausgeführt werden, also kein Code beim Testen vergessen wird, der später im Steuergerät doch zum Fehlverhalten führen kann. Zu beachten ist aber, dass ein Code-Coverage für sich alleine nichts über die Software-Qualität bezüglich Funktionalität oder Robustheit aussagt.

Code-Coverage wird in verschiedene Stufen unterteilt, wobei sich die einschlägige Literatur hinsichtlich deren Bezeichnungen leider nicht immer einig ist. Es empfiehlt sich deshalb, darauf zu achten, was im Rahmen der jeweils anzuwendenden Normen unter den dort verwendeten Begriffen tatsächlich zu verstehen ist. Für einen umfassenden Überblick sei ein Beitrag von R. Bär et.al. [1] empfohlen, der das Thema ausführlich behandelt.

Dieser Beitrag orientiert sich an der für den Automotive-Bereich relevanten Norm ISO 26262, die folgende Coverage-Arten unterscheidet:

  • Statement Coverage: Beim Statement Coverage wird ermittelt, wie viele Maschinenbefehle durch die Tests erreicht, also ausgeführt wurden. Programmverzweigungen werden nicht beachtet. Mit diesem Verfahren kann zwar nicht ausgeführter Programmcode („dead code“) aufgespürt werden, es erfüllt aber meist nicht die aktuellen Anforderungen an die Testqualität.
  • Branch Coverage: Die Ausführung aller möglichen Programmverzweigungen wird beim Branch Coverage überprüft. Im Falle einer einfachen IF-Anweisung muss also die Bedingung einmal den Wahrheitswert WAHR und einmal den Wert FALSCH annehmen. Da hier implizit auch alle Anweisungen erreicht werden müssen, ist das Statement Coverage bereits aus dem Ergebnis des Branch Coverage ableitbar.
  • MC/DC (Modified Condition/Decision Coverage): Für das MC/DC müssen für jede zusammengesetzte Bedingung alle darin enthaltenen Einzelbedingungen jeweils beide Wahrheitswerte annehmen, um als getestet zu gelten. Damit wird sichergestellt, dass jede Einzelbedingung auch unabhängig von den anderen beteiligten Einzelbedingungen das Gesamtergebnis bestimmt. In der praktischen Anwendung erweist sich dieses Verfahren allerdings als äußerst aufwändig, da insbesondere bei Schleifen, die bedingte Ausführungssequenzen enthalten, extrem viele Pfade zu betrachten sind.

Je nach Sicherheitsrelevanz eines zu testenden Modules legt die jeweils anzuwendende Norm bestimmte Stufen des Code-Coverages fest und verlangt deren Nachweis. Im Falle der ISO 26262 sind diese in den Automotive Safety Integrity Levels (ASIL) festgelegt, die jedoch nur eine Empfehlung aussprechen (Bild 1 / Tabelle 1).

Es wird deutlich, dass man dem Branch-Coverage ein hohes Maß an Aufmerksamkeit widmen sollte, da es in den meisten ASILs als „sehr zu empfehlen“ eingestuft ist. Auch andere Normen wie die für den Luftfahrtbereich wichtige DO-178C verlangen für mittlere bis höhere Software-Levels – vergleichbar mit den ASILs – den Nachweis des Branch-Coverages.

Aber auch im Softwaretest ohne Bindung an irgendwelche Normen kann es durchaus sinnvoll sein, Hilfsmittel wie das Code-Coverage zu nutzen. Auf diese Weise lässt sich nämlich durchaus eine deutliche Erhöhung der Testqualität erreichen.

Coverage messen, Programmcode instrumentieren

Beim Code-Coverage handelt es sich um ein kontrollflussbasiertes Verfahren. Dafür muss zuerst das zu messende Programm oder Modul mit den entsprechenden Stimuli ausgeführt oder zumindest simuliert werden. Anschließend wird je nach Coverage-Stufe die Ausführung von Statements, Verzweigungen oder Einzelbedingungen bewertet.

Eine Möglichkeit, die notwendigen Daten zu gewinnen, ist die Instrumentierung des originalen Programmcodes. Die Konsequenz daraus ist aber, dass der eingefügte Testcode nicht nur das Laufzeitverhalten und die Codegröße, sondern gegebenenfalls sogar das Speicherlayout, beeinflusst. Bei sicherheitskritischen Anwendungen oder Systemen mit hohen Echtzeitanforderungen ist dies durchaus ein kritischer Punkt.

Trace als Alternative, um Statement-Coverage abzuleiten

Will man auf die Instrumentierung verzichten und ist zudem auf ein exaktes Zeitverhalten der zu testeten Applikation angewiesen, kommt man eigentlich um Trace nicht herum. Dafür ist aber eine geeignete Trace-Hardware inklusive einer Trace-Schnittstelle zum Coverage-Tool durch das Embedded-System bereitzustellen. Zumindest für den betrachteten Automotive-Sektor kann man inzwischen auf entsprechend ausgestaltete Controller zurückgreifen. Mittlerweile ist die Verfügbarkeit von Trace sogar ein K.-o.-Kriterium bei der Plattformentscheidung.

Aus den gewonnen Trace-Daten – typischerweise sind das die Adressen der ausgeführten Maschinenbefehle oder zumindest der Verzweigungsoperationen – lässt sich mit Hilfe entsprechend geeigneter Werkzeuge sehr leicht ein Statement-Coverage ableiten. Kniffeliger wird es hingegen bei den höheren Coverage-Stufen. Hier sind auch Informationen zur Programmstruktur, also dem Kontrollflussgraphen notwendig (Bild 2).

Unter anderem benötigt das Coverage-Tool diesen, um anhand der aufgezeichneten Adressen die Richtung zu ermitteln, welche die Programmausführung nach einer bedingten Verzweigung eingeschlagen hat und natürlich auch um festzustellen, welche Programmteile überhaupt nicht ausgeführt wurden. Letzte sind ja im Trace schlichtweg nicht vorhanden. Das Wissen darüber muss also aus einer anderen Quelle kommen. Aus nichtoptimierten Code lässt sich der Kontrollfluss relativ einfach aus dem verfügbaren Quellcode und den Debug-Informationen im ELF-File herleiten. Bei optimiertem Code wird es hingegen schnell kompliziert.

Bildergalerie
Bildergalerie mit 6 Bildern

Optimierter Code – anders als man denkt

Jeder Entwickler weiß, dass eine direkte Übersetzung des Quellcodes in ausführbare Maschineninstruktionen weder hinsichtlich der Laufzeit noch des Speicherbedarfes optimal ist. Compiler bieten daher verschiedene Optimierungsmöglichkeiten, die teilweise recht aggressiv die Struktur des Maschinencodes verändern. So geht oftmals die eindeutige Zuordnung von Basisblöcken des Quellcodes – also den ausschließlich sequenziellen Codepartien – zu denen des Maschinencodes verloren.

Basisblöcke können unter anderem vervielfältigt, zusammengefasst oder eliminiert werden. Solche Programmtransformationen treten beispielsweise bei Schleifentransformationen (Schleifenspaltung, -vereinigung oder -expansion), „if-then-else“-Transformationen (z.B. Eliminierung eines Anweisungszweiges) oder bei der Umwandlung von Basisblöcken in Tabellenzugriffe auf. Letzteres stellt vor allem für das Branch-Coverage eine Herausforderung dar.

Betrachten wir folgendes Beispiel: Für eine normale switch-Anweisung in C/C++ (Listing 1) erzeugt der Compiler zuerst einen Maschinencode, der den Basisblöcken der switch-Anweisung noch zugeordnet werden kann (Listing 2). Zu Beginn jedes Blockes wird überprüft, ob der Wert im Kopf der switch-Anweisung mit der case-Konstante übereinstimmt. Falls nicht, wird das nächste Label angesprungen, wo dann die Prüfung mit nächsten case-Konstanten stattfindet. Existiert ein default-Block, wird dieser ausgeführt, wenn alle anderen Vergleiche fehlschlugen.

Der Compiler hat hier verschiedene Möglichkeiten der Optimierung. Bei kleinen Wertebereichen der case-Konstanten kann diese beispielsweise als Index in eine Sprungtabelle verwendet werden, welche die Adressen der Label enthält (Listing 3). Damit fallen bereits die Basisblöcke der Vergleiche weg. Für Werte außerhalb des Wertebereiches wird einfach zum default-Label gesprungen.

Für das gewählte Beispiel ist aber noch ein weiterer Optimierungsschritt möglich. Da alle Anweisungen innerhalb der case-Blöcke konstante Werte zurückliefern, kann der Compiler die Rückgabewerte in einer Wertetabelle ablegen und die case-Konstante wiederum als Index verwenden (Listing 4). Damit lassen sich die Sprünge komplett eliminieren. Alle case-Blöcke sind nun in einem einzigen Basisblock vereint.

Bildergalerie
Bildergalerie mit 6 Bildern

Um aus den gewonnenen Adressen im Trace ein Statement-Coverage zu ermitteln, reichen normalerweise schon die Standard-Debug-Informationen aus. Für das interessantere Branch-Coverage hingegen fehlen in den im DWARF-Format vorliegenden Debug-Informationen die Verknüpfungen zwischen den Basisblöcken, also die Kanten des Kontrollflussgraphen. Zwar kann aus dem Instruction-Trace ermittelt werden, welche Programmverzweigung genommen bzw. bei direkten Sprüngen auch, welche nicht genommen wurden, aber sobald indirekte Sprünge mit nahezu beliebig vielen Sprungzielen ins Spiel kommen, sind die tatsächlich existierenden Verzweigungen nicht mehr ermittelbar. Folglich kann so ein Branch-Coverage nicht korrekt berechnet werden.

Für unser Beispiel mit der Sprungtabelle wäre in diesem Fall nicht mehr ermittelbar, welche möglichen Verzweigungen ausgeführt wurden und welche nicht. Voraussetzung dafür wäre entweder eine aufwendige statische Code-Analyse, welche die Optimierung erkennt, oder Debug-Information über die Basisblock-Verknüpfungen.

Im Beispiel mit der Wertetabelle wird die Analyse noch aufwendiger, da hier anhand der Speicherzugriffe ermittelt werden müsste, um welchen ausgeführten case-Zweig es sich handelt. Instruction-Trace allein reicht dafür nicht mehr aus, für die Auswertung ist zusätzlich zwingend noch Daten-Trace erforderlich. An dieser Stelle müssen die derzeit verfügbaren Tools noch kapitulieren und es bleibt in der Verantwortung der Entwickler bzw. Tester, ob solche aggressiven Optimierungen tatsächlich zugelassen bzw. wie diese durch die Qualitätssicherung behandelt werden.

Der Compiler hilft, den Kontrollflussplan zu erzeugen

Glücklicherweise gibt es dennoch Mittel und Wege, auch für trace-basierte Code-Coverage von optimiertem Code verlässliche Ergebnisse zu erhalten. Zumindest für die Sprungtabellen-Optimierung liegen die Kontrollflussinformationen, die für die exakte Ermittlung des Branch-Coverages aus Trace-Daten benötigt werden, ja vor. Unter anderem sind das die Identifikationsnummern, Adressen, und Größen der verschiedenen nach Funktion aufgeteilten Basisblöcke sowie die Anzahl und die Identifikationsnummern der Nachfolger eines Basisblockes. Der Compiler selbst benötigt diese Informationen ohnehin für seine Transformationen. Es ist also nur ein kleiner Schritt, daraus den Kontrollflussgraphen zu erzeugen und ihn als Ergänzung zum DWARF-Format auch dem Coverage-Tool verfügbar zu machen.

Bei PLS wurde deshalb exemplarisch für den gcc eine solche Ergänzung vorgenommen. Da sich dabei nur die Debug-Section ändert und diese ja nicht in den Controller geladen wird, beeinflussen die zusätzlichen Informationen weder die Codegenerierung noch den Speicherverbrauch und das Laufzeitverhalten. Seitens des Coverage-Tools, in diesem Falle der Universal Debug Engine (UDE), werden die nun verfügbaren Kontrollflussinformationen mit den gewonnen Trace-Daten verknüpft. Damit ist eine Branch-Coverage-Analyse nichtinvasiv, ohne Instrumentierung und damit ohne Verletzung des Laufzeitverhaltens für optimierten Code möglich.

Literatur

[1] R. Bär, A. Behr, D. Fischer: "Code-Coverage auf Embedded-Systemen"; ESE-Kongress 2012

* Jens Braunes ist Software-Architekt bei PLS Programmierbare Logik & Systeme, Lauta.

Artikelfiles und Artikellinks

(ID:43140991)