Subsequence invariants

Abstract

In this thesis, we introduce subsequence invariants, a new class of invariants for the specification and verification of systems. Unlike state invariants, which refer to the state variables of the system, subsequence invariants characterize the behavior of a concurrent system in terms of the occurrences of sequences of synchronization events. The first type of such invariants, pure subsequence invariants, are linear constraints over the possible numbers of such occurrences, where we allow every occurrence of a subsequence to be interleaved arbitrarily with other events. We then describe the more general class of phased subsequence invariants, in which additional restrictions can be placed on the events that may occur between those of a given sequence. In either case, subsequence invariants are preserved when a given process is composed with additional processes. subsequence invariants can therefore be computed individually for each process and then be used to reason about the full system. We present an efficient algorithm for the computation of subsequence invariants of finite-state systems. Our construction can be applied incrementally to obtain a growing set of invariants given a growing set of event sequences. We then address the problem of proving subsequence invariants of infinite-state systems. For this we use an abstraction refinement procedure that uses small, incrementally transformed graph-based abstractions. In order to explain the techniques we use, we first introduce a simpler version of this method for statebased properties, and then show how to verify subsequence invariants.

Inhalt dieser Arbeit sind Subsequenzinvarianten, eine neue Klasse von Invarianten für die Systemspezifikation und -verifikation. Im Gegensatz zu zustandsbasierten Invarianten, die über den Zustandsvariablen des Systems definiert sind, beschreiben Subsequenzinvarianten das gewünschte Systemverhalten anhand des Auftretens verschiedener Synchronisationsfolgen. Wir beschreiben zunächst reine Subsequenzinvarianten, welche durch lineare Gleichungen auf den möglichen Häufigkeiten solcher Folgen von Events gegeben sind, zwischen denen jeweils beliebige andere Events autreten dürfen. Im Anschluss verallgemeinern wir diese zu Subsequenzinvarianten mit Phasen, in denen eine Synchronisationsfolge neben der eigentlichen Folge von Events auch durch Beschränkungen auf den dazwischen auftretenden Events gegeben sein kann. Beide Klassen von Invarianten bleiben gültig, wenn ein Prozess, für den sie gelten, mit beliebigen anderen Prozessen kombiniert wird. Sie können daher für jeden einzelnen Prozess berechnet und dann zur Verifikation des gesamten Systems verwendet werden. Wir präsentieren einen effizienten Algorithmus für die Berechnung von Subsequenzinvarianten auf Systemen mit endlichen Zustandsräumen. Diese Konstruktion kann auch inkrementell angewandt werden, wenn die Menge der betrachteten Subsequenzen allmählich wächst. Für die Berechnung von Subsequenzinvarianten für Systeme mit unendlichem Zustandsraum führen wir eine Methode ein, die auf dem Prinzip der Abstraktionsverfeinerung basiert. Unsere Version dieses Ansatzes zeichnet sich durch die Verwendung sehr kleiner, graphenbasierter Abstraktionen aus. Wir präsentieren zunächst eine einfachere Variante des Verfahrens für zustandsbasierte Fehlerbedingungen, an der sich die verwendeten Operationen leichter demonstrieren lassen, und beschreiben dann die Anpassungen für die Verifikation von Subsequenzinvarianten.