Startseite > Embedded > Software > Minimalinvasiv testen

Branch-Coverage-Tests

Minimalinvasiv testen

12. August 2014, 11:30 Uhr | Heiko Rießland

▶ Diesen Artikel anhören

Fortsetzung des Artikels von Teil 2

Code-Optimierung: von leicht geändert bis total umgewandelt

Für eine normale switch-Anweisung in C/C++ (Listing 1) erzeugt der Compiler einen Maschinencode (Listing 2), der den Basisblöcken der switch-Anweisung noch zugeordnet werden kann. 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 der nächsten case-Konstante stattfindet. Existiert ein default-Block, wird dieser ausgeführt, wenn alle anderen Vergleiche fehlschlugen.

Jobangebote+ passend zum Thema

MACNICA ATD EUROPE - Ihre berufliche Zukunft

MACNICA ATD Europe GmbH, Ingolstadt

Alle Jobangebote im Elektroniknet Karrierebereich anzeigen

enum color{red, blue, orange, violet, yellow};
int ColorToOffset(enum color c) {
int offset;
switch(c) {
case(red):
offset=10;
break;
case(blue):
offset=12;
break;
...
case(yellow):
offset=0;
break;
default:
offset=-1;
break;
}
return offset;
}

Listing 1. Quellcodebeispiel für switch-Anweisung.

ColorToOffset: @ c is stored in r0
.L1:
CMP r0, #red @ if(c != red)
BNE .L2 @ goto L2
MOV r0, 10 @ retval =10
B .Lend @ break
.L2:
CMP r0, #blue @ if(c != blue) goto L3
BNE .L3
MOV r0, 12
B .Lend
...

.Ln:
CMP r0, #yellow @ if(c != yellow) goto Ldefault
BNE .Ldefault
MOV r0, 0
B .Lend
.Ldefault:
MOV r0,0
SUB r0,r0,#1
.Lend:
MOV PC,LR @return value is stored in r0

Listing 2. Assembler-Notation für die nichtoptimierte Switch-Anweisung.

In der ersten Optimierungsstufe versucht der Compiler zu erkennen, ob der Wertebereich der case-Konstanten klein genug ist, um den Vergleichswert im Kopf der switch-Anweisung als Index einer Tabelle verwenden zu können. Ist dem so, erzeugt der Compiler eine Sprungtabelle, indem er die Adressen der Labels in einer Tabelle speichert. Die case-Konstanten dienen in der Tabelle als Index. Ohne Einschränkung der Allgemeingültigkeit nehmen wir in Listing 3 an, dass die kleinste Konstante gleich Null ist. Ist dem nicht so, generiert der Compiler mit Hilfe eines konstanten Offsets eine Index-Umrechnung. Fehlen für Daten im Wertebereich der Tabelle entsprechende case-Statements, werden diese vom Compiler mit Referenzen auf den Default-Block ergänzt. Die Blöcke des Maschinencodes können im Falle der Sprungtabelle noch den Quellcode-Blöcken zugeordnet werden, jedoch erfordert es einigen Aufwand, die drei Basisblöcke der if-then-else-if-else-Anweisungen dem gesamten Kopf der switch-Anweisung richtig zuzuweisen.

ColorToOffset: @ c is stored in r0
CMP r0, #red @ if(expression < const_1) goto default
BLT .Ldefault
CMP r1, #yellow @ if(const_n < expression) goto default
BGT .Ldefault
ADR r2, jump_table @ goto *jump_table[expression]
ADD pc, r2, r1
.Lred:
MOV r0, #10
B .Lend
.Lblue:
MOV r0, #12
B .Lend
...
.Lyellow:
MOV r0, #0
B .Lend
.Ldefault:
MOV r0, #0
SUB r0, r0, #1
.Lend
MOV PC,LR
jump_table:
.word .Lred
.word .Lblue
...
.word .Lyellow

Listing 3. Assembler-Notation für Sprungtabellen-Optimierung.

In unserem Beispiel kann der Compiler aber noch eine weitere Optimierung durchführen. Dafür versucht er zu erkennen, ob die Ausdrücke der Blöcke konstant sind bzw. ob sich ihr Wert bereits während der Compilierung ermitteln lässt. Im Beispiel können alle Zuweisungen durch Konstanten ersetzt werden. Ist dies für alle case-Blöcke der Fall, kann der Compiler die sonst nötigen Sprünge komplett einsparen und den Wert durch einen Wertetabellen-Zugriff (Listing 4) ermitteln. Dadurch werden alle case-Basisblöcke in einem einzigen Maschinencode-Basisblock vereint. Auch hier erscheint der Kopfblock der switch-Anweisung als if-then-else-Anweisung und kann dementsprechend wie zuvor erkannt und zugeordnet werden.

ColorToOffset: @ c is stored in r0
CMP r0, #red @ if(expression < red) goto default
BLT .Ldefault
CMP r1, #yellow @ if(yellow < expression) goto default
BGT .Ldefault
LDR r0, value_table [r0, LSL #2] @ retval = value_table[c]
B .Lend
.Ldefault:
MOV r0, #0
SUB r0, r0, #1
.Lend
MOV PC,LR
value_table:
.word 10
.word 12
...
.word 0

Listing 4. Assembler-Notation für Wertetabellen–Optimierung.

Dieser Code kann noch weiter optimiert werden, wenn architekturbedingte Anweisungen eingeführt werden. Listing 5 zeigt eine Variante der Optimierung, in der alle Sprünge eliminiert wurden. Voraussetzung dafür ist, bedingte Anweisungen so einzusetzen, dass der Kontrollfluss linear fortgesetzt werden kann und Prozessor-Flags über die Ausführung einer Anweisung entscheiden. In diesem Fall stehen dann n Basisblöcke des Quellcodes einem einzigen Basisblock in Maschinencode gegenüber. Die Erkennung der im Maschinencode noch enthaltenen if-then-else-Anweisung erfordert allerdings einen enormen Aufwand durch das Debug Tool. In der Regel sind bei einer solchen Optimierung auch die ursprünglichen Debug-Zeileninformationen so verändert, dass alle Zeilennummern auf den gesamten Anweisungsblock verweisen.

ColorToOffset: @ c is stored in r0
MOV r1,r0 @ save c in temp register
LDR r0, &value_default @ retval=-1;
CMP r1, #red @ if(expression < red) {
MOVLT PC,LR @ return retval; (in r0) }
CMP r1, yellow @ if(yellow >= expression) {
ADRLE r2, &value_table @
LDRLE r0, [r2, r1, LSL #2] @ retval = value_table[c] }
MOV PC,LR @ return retval; (in r0)
 value_default:
.word 0xffffffff
value_table:
.word 10
.word 12
...
.word 0

Listing 5. Assembler-Notation für Wertetabellen-Optimierung und Sprungeliminierung

Das nachfolgend beschriebene Verfahren beruht auf der Übergabe der dem Compiler bekannten Informationen zur Änderung der Programmstruktur an den Debugger. Das macht eine nachträgliche Erkennung überflüssig, die aufwendig, fehlerträchtig und ggf. sogar nicht eindeutig ist.

Minimalinvasiv testen
Path Coverage
Code-Optimierung: von leicht geändert bis total umgewandelt
Erkennung der Programmstruktur

Kooperation von PLS und LieberLieber Software

Modellorientiert entwickeln, testen und debuggen

Lizenzen, Exportbestimmungen, Schwachstellen:

Open Source Code effektiv verwalten

Entwicklungswerkzeuge

Automatisch testen im Zielsystem

Forum Funktionale Sicherheit 2014

Fehler sind menschlich

Betriebssysteme

Linux mit Sicherheit

Kooperation im Tool-Bereich

Hitex vertreibt UDE von PLS

Software-Sicherheit

Protection Suite von Wibu schützt und lizenziert