Section: Overall Objectives

Overall Objectives

The VeriDis project team includes members of the MOSEL team of LORIA, the computer science laboratory in Nancy, and members of the Automation of Logic Research Group at Max-Planck Institute for Informatics (MPII) in Saarbrücken. It is headed by Stephan Merz and Christoph Weidenbach. VeriDis was created in 2010 as a local team of Inria Nancy Grand-Est. After a positive evaluation of the project proposal in the spring of 2011, the team was officially created in July 2012.

The objectives of VeriDis are to contribute to the advances in automated and interactive theorem proving and to exploit them for the formal development of concurrent and distributed algorithms and systems, within the framework of mathematically precise and practically applicable development methods. We intend to assist algorithm and system designers carrying out formally proved developments, where proofs of relevant properties, as well as bugs, can be found with a high degree of automation.

Automated as well as interactive deduction techniques are already having substantial impact. In particular, they have been successfully applied to the verification and analysis of sequential programs, often in combination with static analysis and software model checking. Ideally, systems and their properties would be specified in high-level, expressive languages, errors in specifications would be discovered automatically, and finally, full verification could also be performed completely automatically. Due to the inherent complexity of the problem this cannot be achieved in general. However, we have observed important advances in automated and interactive theorem proving in recent years. We are particularly interested in the integration of different deduction techniques and tools, including the combination of relevant theories such as arithmetic in automated theorem proving. These advances suggest that a substantially higher degree of automation can be achieved in system verification over what is available in today's verification tools.

VeriDis proposes to exploit and further develop automation in system verification, and to apply its techniques within the context of concurrent and distributed algorithms, which are by now ubiquitous and whose verification is a big challenge. Concurrency problems are central to the development and verification of programs for multi- and many-core architectures, and distributed computation underlies the paradigms of grid and cloud computing. Typical application problems that we address include the verification of algorithms and protocols for peer-to-peer and overlay networks, such as distributed hash tables, multicast trees or gossip-based protocols. The potential of distributed systems for increased resilience to component failures makes them attractive in many contexts, but also makes formal verification important and challenging. We aim to move current research in this area on to a new level of productivity and quality. To give a concrete example: today a network protocol engineer designing a new distributed protocol may validate it using testing or model checking. Model checking will help finding bugs, but can only guarantee properties of a high-level model of the protocol, usually restricted to finite instances. Testing distributed systems and protocols is notoriously difficult because corner cases are hard to establish and reproduce. Also, many testing techniques require implementation, which is expensive and time-consuming, and errors are found only when they can no longer be fixed cheaply. The techniques that we develop aim at automatically proving significant properties of the protocol already at the design phase. Our methods will be applicable to designs and algorithms that are typical for components of operating systems, distributed services, and down to the (mobile) network systems industry.