Search

The first attempts to apply the k-induction method to software verification are only recent. In this paper, we present a novel proof by induction algorithm, which is built on the top of a symbolic context-bounded model checker and uses an iterative deepening approach to verify, for each step k up to a given maximum, whether a given safety property $$\phi $$ holds in the program. The proposed k-induction algorithm consists of three different cases, called base case, forward condition, and inductive step. Intuitively, in the base case, we aim to find a counterexample with up to k loop unwindings; in the forward condition, we check whether loops have been fully unrolled and that $$\phi $$ holds in all states reachable within k unwindings; and in the inductive step, we check that whenever $$\phi $$ holds for k unwindings, it also holds after the next unwinding of the system. The algorithm was implemented in two different ways, a sequential and a parallel one, and the results were compared. Experimental results show that both forms of the algorithm can handle a wide variety of safety properties extracted from standard benchmarks, ranging from reachability to time constraints. And by comparison, the parallel algorithm solves more verification tasks in less time. This paper marks the first application of the k-induction algorithm to a broader range of C programs; in particular, we show that our k-induction method outperforms CPAChecker in terms of correct results, which is a state-of-the-art k-induction-based verification tool for C programs. [ABSTRACT FROM AUTHOR]

A Mix Net is a cryptographic protocol that unlinks the correspondence between its inputs and its outputs. In this paper, we formally analyse a Mix Net using the process algebra CSP and its associated model checker FDR. The protocol that we verify removes the reliance on a Web Bulletin Board: rather than communicating via a Web Bulletin Board, the protocol allows the mix servers to communicate directly, exchanging signed messages and maintaining their own records of the messages they have received. Mix Net analyses in the literature are invariably focused on safety properties; important liveness properties, such as deadlock freedom, are wholly neglected. This is an unhappy omission, however, since a Mix Net that produces no results is of little use. In contrast, we verify here that the Mix Net is guaranteed to terminate, with each honest mix server outputting the decrypted vector of plaintexts alongside a chain proving that each re-encryption/permutation and partial decryption operation was performed correctly, under the assumption that there is an honest majority of them acting according to the protocol. [ABSTRACT FROM AUTHOR]

We present a framework that supports the formal verification of early requirements specifications. The framework is based on Formal Tropos, a specification language that adopts primitive concepts for modeling early requirements (such as actor, goal, and strategic dependency), along with a rich temporal specification language. We show how existing formal analysis techniques, and in particular model checking, can be adapted for the automatic verification of Formal Tropos specifications. These techniques have been implemented in a tool, called the T-Tool, that maps Formal Tropos specifications into a language that can be handled by the NuSMV model checker. Finally, we evaluate our methodology on a course-exam management case study. Our experiments show that formal analysis reveals gaps and inconsistencies in early requirements specifications that are by no means trivial to discover without the help of formal analysis tools. [ABSTRACT FROM AUTHOR]