Detecting busy waiting by means of static control flow analysis

Abstract

Ein Prozess, in dem Busy Waiting verwendet wird, überprüft wiederholt eine Bedingung, bis sie erfüllt ist, ohne die Bedingung selbst zu beeinflussen, weshalb hierbei Systemresourcen verschwendet werden und sogar Systemversagen auf Grund von Race Conditions möglich ist. Deshalb wird Busy Waiting als schlechte Programmierpraxis angesehen, kann es doch auch durch die Verwendung höherer Interprozesskommunikationsmethoden vermieden werden.<br />Gerade im Bereich der kritischen Anwendungen, für die Korrektheit und Ausfallsicherheit von entscheidender Bedeutung sind, spielt Softwarequalitätssicherung eine wichtige Rolle. Allerdings ist es diffizil und mühsam, Busy Waiting in bestehendem Quelltext per Hand aufzuspüren, weshalb für diesen Zweck ein Tool zur statischen Analyse unerlässlich ist.<br />Basierend auf einem existierenden Algorithmus zur Identifizierung von Busy Waiting durch Methoden der statischen Kontrollflussanalyse habe ich eine solche Analysesoftware entwickelt und parallel dazu das Analyseverfahren hinsichtlich Genauigkeit und Effizienz weiterentwickelt.<br />Nachdem gerade die Programmiersprache Ada häufig für kritische Anwendungen eingesetzt wird, entschied ich, nicht nur Ada-Programme als Ziel meiner Analyse zu wählen, sondern auch die Analysesoftware in dieser Sprache zu entwickeln.<br />Die wichtigsten Resultate meiner Arbeit sind ein Tool zur statischen Analyse von Ada-Programmen in Hinblick auf Busy Waiting und ein Framework, welches eine mächtige kontrollflussbasierte Darstellung von Ada-Quelltext generiert und so generell umfassende statische Kontrollflussanalyse ermöglicht.<br />

Busy waiting occurs whenever a process repeatedly checks a condition until it becomes true without influencing that condition itself, thereby effectively wasting system resources and introducing the risk of system failure due to race conditions. Hence, busy waiting is considered bad programming practice and can be avoided by the use of higher communication facilities.<br />In the development of critical systems, for which correctness and robustness are of vital importance, software quality assurance is of great value. However, it is difficult and impractical to manually discover busy waiting in existing program code, which is why a static analysis tool is needed for that purpose.<br />Based on an existing algorithm that targets the detection of busy waiting using methods of static control flow analysis, I developed such software and further improved the analysis methods to increase efficiency and sharpen the results.<br />Since the Ada programming language is often used for critical applications I selected it as target language for my analysis and also used it for the implementation of the analysis software itself.<br />The main results of my work are a static analysis tool for detecting busy waiting in Ada programs and a framework providing a powerful CFG-based representation of Ada source code facilitating comprehensive static control flow analysis in general.<br />