Predicting Errors in Concurrent Systems

Die Verbreitung von Multikernprozessoren hat die parallele Programmierung allgegenwärtig gemacht. Parallele Programmierung ist schwierig, da sie die Entwicklung auf Grund vielfacher Kontrollflüsse und Nicht-Determinismus fehleranfällig macht. Zusätzlich gibt es neue Arten von Fehlern, wie z.B. Wettläufe, Verklemmungen oder Reihenfolgeverletzung. Diese Fehler sind wegen der großen Anzahl von möglichen Verschränkungen schwer zu finden.
Dynamische Analyseansätze führen das Programm aus und untersuchen die beobachtete Ausführung. Dynamische Analyse ist präzise, da sie eine tatsächliche Ausführung mit realen Werten und Zuständen beobachtet. ... mehrDiese Ansätze erzeugen falsch Negative, wegen nicht erforschter Wege und Verschränkungen.
Die unterschiedlichen Verschränkungen treten mit unterschiedlicher Häufigkeit auf, wegen externer Faktoren, wie z.B. Compiler, Prozessor oder Arbeitslast. In dieser Arbeit präsentieren wir einen Ansatz, der Fehler aus einer einzigen Spur eines parallelen Programms vorhersagt. Wir berechnen off-line alternative Verschränkungen, um den Zeitmessungseffekt der beobachteten Ausführung zu reduzieren. Wir bauen ein Modell mit Hilfe einer Prozessalgebra, das die Reihenfolge der Spur verallgemeinert; es extrapoliert mögliche Verschränkungen. Im Modell wird nach verschiedenen Nebenläufigkeitsfehlern gesucht. Ein vorhergesagter Fehler wird von einer Verschränkung begleitet, die in dem Programm erzwungen wird, um den Fehler zu reproduzieren.
Der Ansatz wurde für Verklemmungs- und Wettlauferkennung im Vergleich zu anderen dynamischen Ansätzen evaluiert. Die Verringerung von falschen Warnungen bewegt sich im Bereich von 50% bis 86%, mit gleicher oder höherer Präzision. Das vorgestellte Werkzeug und sein Modell sind anpassbar für andere Reihenfolgeverletzungen. Diese Fehler erfordern eine Spezifikation, die die relevanten Ereignisse im Programm definiert und die gültigen oder ungültigen Ordnungen beschreibt. Wir zeigen dieses Vorgehen an sieben Anwendungsbeispielen.

The unstoppable popularity of multicore chips has made concurrent programming ubiquitous. Parallel programming is difficult; multiple control flows and non-determinism make the development error-prone. Additionally, it introduces a new set of errors such as data races, deadlocks, or order violations. These errors are difficult to find due to the large number of possible interleavings in a parallel program.
Dynamic analysis techniques execute a program and perform some checks on the observed execution. Dynamic analysis is precise, as it relates to an actual execution with real values and states. ... mehrThese approaches generate false negatives due to non-explored paths and interleavings. The different interleavings are manifested with varying frequency because of external factors such as compilers, processors, or workloads.
In this work we present an approach that predicts errors from a single trace of a parallel program. We compute alternative interleavings off-line to reduce the timing effects of the observed execution. Using a process algebra, we build a model that generalizes the ordering of the trace, extrapolating possible interleavings. The model is explored for different concurrency errors. A predicted error is accompanied by a schedule, which is enforced in the program to manifest the error.
The approach has been evaluated for deadlock and data race detection, and compared with other dynamic approaches. While maintaining or increasing precision, between 50% and 86% fewer false warnings were produced. The presented tool and its model are also customizable to support other kinds of ordering failures. These failures require a specification that defines the relevant events in the program and describes their valid or invalid orderings. This feature is demonstrated in seven use cases.