Vorhersagende Überwachung mit starken Trace-Präfixen

Laufzeit-vorhersagende Analysen erweitern die Abdeckung traditioneller dynamischer Analyse-basierter Fehlererkennungstechniken, indem sie einen Raum feasilitärer Umstellungen der beobachteten Ausführung identifizieren und bestimmen, ob eine dieser Umstellungen einen Verstoß gegen eine gewünschte Sicherheitsanforderung zeigt. Der beliebteste Ansatz zur Modellierung des Raums der feasilitärer Umstellungen erfolgt durch die Spuräquivalenz von Mazurkiewicz. Die Einfachheit des Rahmens führt auch zu effizienten vorhersagenden Analysen und ist das De-facto-Mittel zur Erlangung von raum- und zeiteffizienten Algorithmen zur Überwachung paralleler Programme. In dieser Arbeit untersuchen wir, wie wir die Vorhersagekraft des spurenbasierten Denkens verbessern können, während wir weiterhin die algorithmischen Vorteile, die es bietet, beibehalten. In diesem Zusammenhang erweitern wir die Spurentheorie, indem wir eine Klasse von Präfixen auf natürliche Weise einbetten, die wir starke Trace-Präfixe nennen. Wir charakterisieren starke Trace-Präfixe formal durch eine erweiterte Abhängigkeitsrelation, untersuchen deren Vorhersagekraft und stellen eine enge Verbindung zu dem zuvor vorgeschlagenen Begriff der synchronisationsbewahrenden korrekten Umstellungen her, der im Kontext von Datenrennen und Deadlock-Vorhersagen entwickelt wurde. Anschließend zeigen wir, dass trotz der erhöhten Vorhersagekraft starke Trace-Präfixe weiterhin die algorithmischen Vorteile von Mazurkiewicz-Spuren im Kontext der Vorhersage gegenüber Ko-Sicherheitsanforderungen genießen und neue Algorithmen für synchronisationsbewahrende Datenrennen und Deadlocks mit einer besseren asymptotischen Raum- und Zeitnutzung ableiten. Wir zeigen auch, dass starke Trace-Präfixe mehr Verstöße gegen Muster-Sprachen erfassen können. Wir implementieren unsere vorgeschlagenen Algorithmen und unsere Bewertung bestätigt den praktischen Nutzen des Denkens auf der Grundlage starker Präfix-Spuren.