Immer schön der Reihe nach!

Autoren: Gunther Vogel, Robert Bosch GmbH, und Dr. Daniel Simon, Axivion GmbH

Beitrag - Embedded Software Engineering Kongress 2016

 

Zur Steuerung eingebetteter Systemen werden häufig Interrupts eingesetzt, die ab einer gewissen Komplexität gründlich geplant und überwacht werden müssen. Gleichzeitig finden auch Multicore-Prozessoren immer weitere Verbreitung in sonst „ressourcenarmen Umgebungen“, so dass auch durch die technische Entwicklung das Thema nebenläufiges Programmieren als ein neues Paradigma für viele (Embedded) Programmierer immer wichtiger wird. Mit der Nebenläufigkeit von Software steigt die Gefahr von Race Conditions und folglich von obskurem, schwer nachvollziehbarem Laufzeitfehlverhalten der Systeme.

Dieser Beitrag stellt einen methodischen Rahmen vor, um Race Conditions mit konstruktiven Maßnahmen im Design und bei der Codierung zu bekämpfen. Um sicherzustellen, dass das Produkt bei seiner Auslieferung keine Race Conditions enthält, sind ergänzend auf analytische Werkzeuge gestützte Maßnahmen zu verwenden. Die konstruktiven und analytischen Maßnahmen werden erläutert und es wird gezeigt, wie die Ergebnisse über den Verlauf eines Entwicklungsprojekts effizient verwaltet werden können.

Inhaltliche Gliederung

• Was sind Race Conditions?
• Zielsetzung
• Rahmenbedingungen
• Konstruktives Vermeiden von Race Conditions
• Warum sind Design/Codier-Regeln nicht ausreichend?
• Analytische Verfahren und Erfahrungen mit ihrem Einsatz
• Lösungsansätze für die kontinuierliche Nutzung
• Zusammenfassung

 

Nutzen und Besonderheiten

Der Beitrag wendet sich an EntwicklungsleiterInnen und EntwicklerInnen von Embedded Systemen in C/C++, die mit Interrupts oder Multicore-Hardware arbeiten. Die Problemstellung von Race Conditions wird kurz erläutert. Dann werden konstruktive Maßnahmen zum Vermeiden von Race Conditions vorgestellt und deren Grenzen aufgezeigt. Der Beitrag erläutert, welche analytischen Maßnahmen darüber hinaus notwendig sind und wie Sie diese Maßnahmen durch Werkzeuge unterstützt im Projektalltag einsetzen können, um potentielles Fehlverhalten der Software frühzeitig zu erkennen und zu beheben.

Was sind Race Conditions?

Während bei der rein sequentiellen Programmierung noch genau feststeht, in welcher Reihenfolge einzelne Anweisungen ausgeführt werden, bestehen nebenläufige Softwaresysteme aus mehreren Handlungssträngen (Threads), bspw. Tasks oder Interrupts, die logisch parallel ausgeführt werden. Obwohl auch hier noch innerhalb eines Handlungsstrangs feststeht, in welcher Reihenfolge Anweisungen  ausgeführt werden, ist dies relativ zu anderen nicht mehr möglich. Solange die Handlungsstränge unabhängig voneinander ausgeführt werden und ihre Ergebnisse sich nicht durch die Nutzung von gemeinsamen Ressourcen beeinflussen können (z.B. CPU oder Speicher), ist diese Parallelität noch unproblematisch. Von einer Race Condition spricht man allerdings, sobald die Reihenfolge der Abarbeitung zwischen Handlungssträngen eine Auswirkung auf das Systemergebnis hat.

Ein wichtiges und häufig auftretendes Muster für Race Conditions ist das Data Race. Hier konkurrieren die nebenläufigen Handlungsstränge gleichzeitig um eine Ressource in Form einer gemeinsam verwendeten Variable oder eines Speicherbereichs und wenigstens einer der Handlungsstränge verändert den Zustand dieser Ressource. Bilden sich je Überlappung der Handlungsstränge unterschiedliche Ergebnisse, handelt es sich dann um eine Race Condition.

Zur Veranschaulichung eines Data-Races sollen zwei Threads betrachtet werden, die jeweils dieselbe Zählervariable inkrementieren (siehe hierzu Abbildung, PDF). Jeder Thread lädt hierzu erst den Wert der Variable in ein Register (load), inkrementiert dieses und speichert dann im Anschluss den berechneten Wert wieder zurück. Falls die Ausführungen der beiden Threads sich zeitlich überlappen, überschreibt einer das Ergebsnis des anderen. Der Effekt wäre, dass die Variable nur einmal inkrementiert wird, statt wie erwartet, zweimal.

Zielsetzung

Für jedes Software-System soll bei Auslieferung gewährleistet sein, dass es keine funktionalen Fehler in Form von Race Conditions enthält.

Rahmenbedingungen

Den von uns berichteten Erfahrungen liegenf olgende Rahmenbedingungen zugrunde:

• Die Software-Entwicklung erfolgt komponentenbasiert mit späterer Integration der Komponenten zu einem Gesamtsystem.
• Die örtlich verteilte Entwicklung der eigenen Komponenten wird teilweise durch Off-The-Shelf Komponenten und Third-Party Komponenten ergänzt.
• Die Quelltexte als C/C++ Code aller wesentlichen Komponenten sind vorhanden.
• Der Entwicklungsprozess wird mit hoher Disziplin und Prozessreife umgesetzt.
• Die Einhaltung vom Prozess defnierten Vorgaben und Regeln wird umfassend geprüft.
• Best-Practices werden in der Form von Guidelines dokumentiert, die regelmäßig aktualisiert und geschult werden.
• Alle entstandenen Arbeitsprodukte werden über semi-formale Review-Prozesse geprüft.
• Die Komponenten und das Gesamtsystem durchlaufen vor der Auslieferung umfangreiche, durch Sicherheitsstandards geforderte Tests.

Wie können Race Conditions konstruktiv vermieden werden?

Race Conditions sollten möglichst gleich von Anfang durch das Design vermieden werden. Hier einige der Best-Practices, die dabei angewendet werden können:

1. Vermeiden von gemeinsam genutzten globalen Variablen: Einerseits sind globale Variablen oftmals die einzige Möglichkeit, Daten zwischen Tasks und Interrupts auszutauschen, andererseits sind sie auch eine der Hauptursachen von Race Conditions. Ein vollständiger Verzicht wie bei der reinen funktionalen Programmierung ist bei Embedded Systems noch nicht denkbar. Wohl bietet es sich aber an, die Interaktionen zwischen den Handlungssträngen klar zu strukturieren und somit auch die dabei verwendeten Variablen auf ein Minimum zu reduzieren.

2. Gruppierung miteinander in Beziehung stehenden Variablen in eine Datenstruktur: Beziehungen zwischen Variablen sollten angemessen und ausreichend dokumentiert oder durch programmiersprachliche Konstrukte gekennzeichnet werden. Zeigt bspw. eine Variable an, ob der Wert einer anderen gültig oder fehlerhaft ist, so sollten beide Elemente in eine gemeinsame Datenstruktur zusammengefasst und ihre Beziehung genau dokumentiert werden. Stellt nun ein Handlungsstrang diese Datenstruktur bereit, so ist klar, dass ein anderer diese erst verarbeiten darf, nachdem sie vollständig bereit stehen.

3. Schutz vor fehlerhafter Verwendung: Damit sich durch Verwendungen von Variablen oder Funktionen aus einem nicht dafür vorgesehenen Handlungsstrang keine Race Conditions ergeben, gehören Restriktionen, wie und aus welchem Kontext heraus eine Verwendung passieren darf, zu den standardmäßig zu dokumentierenden Eigenschaften. Sinnvoll sind hier Dokumentationstemplates, die dafür sorgen, dass die Beschreibungen einheitlich und vollständig sind.  Des Weiteren hat sich in Embedded Systemen mit wenigen Tasks und Interrupts auch die Definition einer Namenskonvention bewährt, die anzeigt, aus welchem Kontext (bspw. Interrupt oder Background-Task) die Funktion oder Variable verwendet werden darf. Darüber hinaus können die notwendigen Beschränkungen auch detailliert in Architekturmodellen dargestellt werden. Dies ist bei sicherkritischen Systemen mittlerweile Stand der Technik, insbesondere da auch automatisierte Verfahren zur Prüfung der Architekturmodelle gegen die Implementierung zur Verfügung stehen und sich somit die Beziehungen bereits während der Entwicklung auf Korrektheit prüfen lassen.

4. Guideline mit Desing- und Anti-Patterns zur Vermeidung von Race Conditions: Die Verwendung bewährter Design-Patterns hilft Fehler zu vermeiden und kann auch manuelle Prüfungen durch die Wiedererkennung von bekannten Mustern erleichtern. Beispiele aus unseren Guidelines sind Muster für gegenseitigen Ausschluss durch Interrupt Disabling oder binäre Semaphore, gegenseitiger Ausschluss über Zustandsvariablen, Verwendung von atomaten Variablen oder die Verwendung des Volatile-Qualifiers.

Warum sind Design-/Codier-Regeln nicht ausreichend?

Die Erfahrung zeigt, dass selbst durch umfassende Regelwerke und Prozesse nicht alle Fehler verhindert werden können. Dies liegt im Grunde an der immer höheren Komplexität von Embedded Systemen und dem darin liegenden Risiko weitere und zusätzliche Fehler zu machen. Beispielsweise führen Kompositionsprobleme selbst bei bewährten und sicheren Komponenten dazu, dass in der Kombination neue Probleme entstehen können. Innerhalb hybrider Software-Systeme kann für Off-the-Shelf und Third-Party Komponenten nicht immer vorausgesetzt werden, dass die speziellen Design- und Codier-Regeln für selbstentwickelte Komponenten genutzt wurden. Technische und fachliche Prozesse sind mittlerweile so komplex, dass selbst erfahrene Entwickler nicht immer alle Details kennen oder berücksichtigen. Des Weiteren muss Software beständig an die wechselnden Bedürfnisse angepasst und überarbeitet werden, was wiederum dazu führt, dass die Zusammenhänge noch komplexer und das Risiko für weitere Fehler weiter steigt.

Analytische Verfahren und Erfahrungen mit ihrem Einsatz

Da trotz der beschriebenen konstruktiven Maßnahmen noch Race Conditions auftreten und diese durch Tests nicht ausreichend erfasst werden können, müssen analytische Verfahren zur weiteren Absicherung eingesetzt werden. Eine vollständige und ausschließlich manuelle Prüfung bei der Größe der heutigen Embedded Systeme ist praktisch nicht mehr möglich - nicht nur durch begrenzte Verfügbarkeit von menschlichen Reviewern, sondern eben auch und vor allem durch ihre Komplexität der Systeme. Entsprechend wird zur Steigerung der Effizienz und Effektivität auf statische Verfahren zur Code-Analyse, die eine konservative Überabschätzung ermitteln, was zum einen bedeutet, dass tatsächlich alle möglichen Probleme gemeldet werden, zum anderen aber auch eine hohe Anzahl von Falschmeldungen, so genannte False-Positives auftreten. Dies hat zur Folge, dass die Ergebnisse dann nochmals manuell bewertet werde müssen. Diese manuelle Prüfung ist immer noch aufwendig, obwohl sie bereits „günstiger“ als die oben genante vollständige manuelle Prüfung ist.

In einer Forschungskooperation mit der Universität Stuttgart wurde deshalb versucht, die Präzision der Code-Analyse-Verfahren zu verbessern. Als Ergebnis musste festgestellt werden, dass trotz der immer aufwändigeren (und rechenintensiven) Analyseverfahren, die Präzision letzten Endes nicht zufriedenstellend gesteigert werden konnte. Dies lag auch an den komplexen Synchronisierungsmustern der analysierten Embedded Systeme, die nicht vollständig von dem in der Forschungsgruppe entwickelten Werkzeug erfasst werden konnten.

Als Konsequenz setzen wir heute eher auf einfachere Analyseverfahren mit klar nachvollziehbaren Ergebnissen. Aktuell kommt hierfür ein Werkzeug aus der Axivion Bauhaus Suite zum Einsatz, das die Erkenntnisse aus der Forschungskooperation umgesetzt hat. Das Werkzeug ermöglicht einen einzelnen Software-Stand inklusive dem Einlesen der Quelltexte innerhalb einer knappen Stunde zu analysieren.

Durch die erwähnten konstruktiven Maßnahmen und Verbesserungen im Design der aktuellen Software-Generation konnte auch die nachträgliche Bewertung der Ergebnisse einfacher und effizienter gestaltet werden. Im Vergleich hat sich so der Bewertungsaufwand auf ein Drittel reduziert und ist mittlerweile auf etwa 40 Stunden für eine vollständige Bewertung gesunken. Je nach Reifegrad der Software wurden nach der Analyse zwischen 2% und 30% der gemeldeten Variablen nochmals überarbeitet. Hierbei wurden in etwa der Hälfte der Fälle echte funktionale Fehler behoben, die von relativ harmlos bis zu sicherheitskritisch reichten. Bei der anderen Hälfte wurden bei der Bewertung Unzulänglichkeiten im Design festgestellt, die zwar aktuell nicht kritisch erschienen, aber trotzdem verbessert wurden, um für die Zukunft Risiken auszuschließen oder die Wartbarkeit der Software zu erleichtern.

Auffallend war allerdings, dass auch nach den funktionalen Änderungen noch meist dieselben Variablen von der Analyse gemeldet wurden, da sie weiterhin nicht in der Lage war, die verwendeten Synchronisationsmuster lückenlos zu erkennen. Letzteres führt dazu, dass mit der zunehmenden Reife der analysierten Software auch die Präzision der Analyseergebnisse abnimmt. Allgemein besteht in dem effizienten Umgang mit der hohen Anzahl von False Positives der Analyse die größte Herausforderung für die kontinuierliche Nutzung der Analyse. Für die Fortentwicklung der Code-Analysen sind Verbesserungen dieser Punkte weit oben auf der Agenda.

Lösungsansätze für die kontinuierliche Nutzung

Wird die Analyse begleitend zur Entwicklung kontinuierlich eingesetzt fällt auf, dass über die Zeit große Teile der Meldungen aus dem Werkzeug stabil bleiben. Durch Änderungen während der Entwicklung können zwar neue Race Conditions entstehen und alte gelöst werden. Gemäß unserer Erfahrung bleiben aber gelöste Race Conditions sehr häufig in den Resultaten als False-Positives erhalten, und die Anzahl von innerhalb kurzer Zeit neu entstehenden Race Conditions sind typischerweise gering. Somit stellt sich die Frage, wie die Ergebnisse effizienter und trotzdem ohne kritische Fehler zu übersehen, verarbeitet werden können. Hierzu muss zunächst festgelegt werden, welche der alten Bewertungen für gemeldete Variablen noch weiterhin gültig sind und auf einen neuen Software-Stand übertragen werden können, und welche der Ergebnisse erneut geprüft werden müssen.

Als Kompromiss werden deshalb die folgenden Heuristiken zur Auswahl der zu überprüfenden Variablen vorgeschlagen: 

1. Variablen, die bisher noch nicht gemeldet wurden - Für diese liegen keine Bewertungsergebnisse vor. Sie müssen also vollständig geprüft werden.
2. Variablen, für die neue Zugriffe hinzugekommen sind - Hier können durch die neuen Zugriffe neue Race Conditions entstehen. Die Variablen müssen entsprechend auf Basis der bisherigen Bewertungen nochmals geprüft werden.
3. Variablen, deren Zugriffe aus neuen Thread-Kontexten erreicht werden - Bei der Bewertung muss ermittelt weren, ob neue Race Conditions durch Aufrufe existierender Funktionen aus neuen Threads erzeugt wurden.

Gemäß unseren Erfahrungen aus dem Vergleich von vollständigen Bewertungen, können über diese Heuristiken alle bisher entdeckten kritische Fehler mit wesentlich geringerem Aufwand abgedeckt werden. Wir emfpehlen darüber hinaus trotzdem, frühere Bewertungen, die übernommen werden sollen, wenigstens stichprobenhaft zu wiederholen, um der Gefahr von Falschbewertungen abzumindern.

Zusammenfassung

In diesem Beitrag berichteten wir von unseren Erfahrungen mit konstruktiven und analytischen Verfahren zur Vermeidung von Race Conditions. Dabei hat sich gezeigt, dass nur statische Werkzeuge in der Lage sind, eine vollständige Abdeckung zu erreichen. Trotz des hohen Bewertungsaufwands hat sich der Einsatz des Werkzeugs als nützlich zur Absicherung gegen Race Conditions erwiesen und ist aus unserer Sicht eine empfehlenswerte Ergänzung zu bestehenden Qualitätsmaßnahmen.

 

Beitrag als PDF downloaden

 

---

Multicore - unsere Trainings & Coachings

Wollen Sie sich auf den aktuellen Stand der Technik bringen?

Dann informieren Sie sich hier zu Schulungen/ Seminaren/ Trainings/ Workshops und individuellen Coachings von MircoConsult zum Thema Multicore /Mikrocontroller.

 

Training & Coaching zu den weiteren Themen unseren Portfolios finden Sie hier.

---

Multicore - Fachwissen

Wertvolles Fachwissen zum Thema Multicore /Mikrocontroller steht hier für Sie zum kostenfreien Download bereit.

Zu den Fachinformationen

 
Fachwissen zu weiteren Themen unseren Portfolios finden Sie hier.