Launching LMF - the Formal Methods Laboratory

The Laboratoire Méthodes Formelles (LMF) was founded on 1 January 2021 as a joint research centre of University Paris-Saclay, CNRS, ENS Paris-Saclay, Inria, and CentraleSupélec with a main focus on formal methods. The new laboratory combines the expertise of about 100 members from the former Laboratoire Spécification et Vérification (LSV) and the VALS team of Laboratoire de Recherche en Informatique (LRI).

In our mission to enlighten the digital world through Mathematical Logic, we rely on formal methods as a tool to analyse, model, and reason about computing systems, such as computer programs, security protocols, and hardware designs. Our research targets a wide range of computational paradigms, from classical to emerging ones such as biological and quantum computing.

LMF is structured around three hubs: Proofs and Models, which lie at the heart of our historical background, and Interactions, that is aimed at fostering cross-fertilisation between formal methods and other domains in computing science and beyond.

ACTS 2023 - Workshop on Automata, Concurrency, and Timed Systems

The 6th edition of the Workshop on Automata, Concurrency, and Timed Systems took place from 30 May to 2 June 2023 at ENS Paris-Saclay.

The workshop series emerged from a long-standing Indo-French cooperation in the areas of ACTS: Automata and Logic, Concurrency Theory, and Timed Systems. As a special event, this year's programme featured a session in honour of Paul Gastin on the occasion of his retirement.

Read more...

Soutenance de thèse : Nathan Thomasset

Stratégies à mémoire finie dans les jeux concurrents à deux joueurs.

Jeudi 21 décembre 2023 à 14h00
ENS Paris-Saclay, Salle 1Z71, zoom

Résumé. On étudie des jeux concurrents à deux joueurs de durée infinie qui se jouent de la façon suivante : chaque tour, les deux joueurs choisissent chacun une action sans connaître le choix actuel de l'adversaire. Sur un nombre de tours infini, cette procédure génère une suite infinie de paires d'actions. Cette suite est alors gagnante pour le Joueur 1 si elle appartient à l'ensemble gagnant du jeu. Read more...

Atomic congestion games with non-separable costs: an application to smart charging

Speaker: Yezekaël Hayel, Université d'Avignon

Tuesday March 12 2024, 14:00, Room 1Z56

Abstract: Atomic congestion games with separable costs are a specific type of non-cooperative games with a finite number of players where the cost of a commodity depends on the number of players choosing it. But in many applications, resources may be correlated in the sense that the resource cost may depend on the usage of other resources, and thus cost function is non-separable. This is the case for traffic models with opposite directions dependencies, resource graph games, and smart charging games to cite a few examples. In this talk, after introducing the concepts of atomic congestion games with non-separable costs, a specific smart charging game will illustrate such game theoretical framework. In this particular setting, we prove the existence of pure Nash Equilibrium by showing ordinal potential function existence. We also demonstrate the convergence of a simple Reinforcement Learning algorithm to the pure NE for both synchronous and asynchronous versions. Finally, the recent framework of Resource Graph Games will be presented. In this setting, dependencies between resources are modeled as an oriented graph. This new framework generalizes atomic congestion games with non-separable costs and opens new questions about the existence and uniqueness of pure NE in this general setup.

PhD Defence: Xavier Denis

Deductive Verification of Rust Programs
by Xavier Denis

Monday 18 December 2023 at 2pm
Batiment 660, Amphitheatre and video conferencing Zoom link.

Abstract. Rust is a programming language introduced in 2015, which provides the programmer with safety features regarding the use of memory. The goal of this thesis is the development of a deductive verification tool for the Rust language, by leveraging the specificities of its type system, in order to simplify memory aliasing management, among other things. Read more...

Soutenance de thèse : Antoine Lanco

Stratégies pour la réduction forte

Vendredi 15 décembre 2023 14h

Université Paris-Saclay, bâtiment 660 (amphithéâtre) et visioconférence

Résumé: La sémantique d’un langage de programmation, et d’un langage fonctionnel en particulier, laisse généralement une certaine liberté quant à l’ordre dans lequel sont effectuées les différentes opérations. Les différentes stratégies qui peuvent être adoptées, comme l'appel par valeur ou l'évaluation paresseuse, bénéficient déjà à la fois d'un large corpus théorique et de nombreuses implémentations efficaces. Ce corpus cependant est majoritairement tourné vers un objectif d'évaluation des programmes, c'est-à-dire de production d'une valeur. Le cadre associé est celui de l'évaluation faible, dans lequel aucune évaluation n'est effectuée à l'intérieur d'une fonction qui ne serait pas totalement appliquée. En effet, dans un langage fonctionnel la fermeture représentant une telle fonction est déjà en elle-même considérée comme une valeur. Read more...

PhD Defence: Giann Karlo

Ecosystem causal analysis using Petri net unfoldings
by Giann Karlo

Thursday 14 December 2023 at 9 am
ENS Paris-Saclay, Room 1Z53 and Zoom

Giann Karlo

Abstract. Many verification problems for concurrent systems have been successfully addressed by various methods over the years, particularly Petri net unfoldings. However, questions of long-term behavior and stabilization have received relatively little attention. For instance, crucial features of the long-term dynamics of ecosystems, such as basins of attraction and tipping points, remain difficult to identify and quantify with good coverage. Read more...

Gilles Dowek lauréat du Grand prix Inria - Académie des sciences 2023

Le Grand prix 2023 Inria-Académie des sciences a été décerné à Gilles Dowek.

Parallèlement à ses travaux scientifiques et techniques, Gilles Dowek a contribué à la construction d'une philosophie naissante de l'informatique, qui se construit dans un dialogue entre philosophes et scientifiques. Il s'est, en particulier, intéressé à la place du calcul en mathématiques, à la différence entre les langues et les langages et aux rapports entre la thèse de Church-Turing et celle de Galilée.

— Citation du prix

Le Prix Inria – Académie des sciences récompense depuis 2013 une ou un scientifique ayant contribué de manière exceptionnelle au champ des sciences informatiques et mathématiques.

Read more...

Hubert Comon-Lundh receives LICS 2023 Test-of-Time Award

Hubert Comon-Lundh

Hubert Comon-Lundh received the LICS Test-of-Time Award 2023 for the article Intruder Deductions, Constraint Solving and Insecurity Decision in Presence of Exclusive Or (ArXiv preprint) co-authored with Vitaly Shmatikov (SRI International). The award was shared with the related paper An NP Decision Procedure for Protocol Insecurity with XOR by Yannick Chevalier, Ralf Küsters, Michaël Rusinowitch, and Mathieu Turuani.

Cryptographic protocols rely on cryptographic primitives to achieve goals such as data privacy and data authenticity in the presence of an attacker. Their use in important applications such as communications over the Internet or credit card payments calls for the automated verification of their security. These two papers made important progress on algorithmic aspects of protocol verification with additional operators, including XOR which is widely used in real-life applications.

Specifically, these papers establish the decidability of insecurity of cryptographic protocols with XOR and other equational theories. Chevalier et al. prove membership in NP when restricted to XOR, while Comon and Shmatikov prove decidability in a broader setting. In addition to definitively settling the complexity question for these cases, the lasting value of this line of work is demonstrated by mature verification tools such as ProVerif, Tamarin, Maude-NPA, and CPSA.— Jury Laudation

Read more...

Alonzo Church Award 2023 for Jacques-Henri Jourdan

Congratulations to Jacques-Henri Jourdan and his co-authors who will receive the 2023 Alonzo Church Award for their outstanding contributions to Logic and computation with the design and implementation of Iris, a higher-order concurrent separation logic framework. The Award will be presented at the 50th EATCS International Colloquium on Automata, Languages and Programming, ICALP 2023, in July.

Iris has been widely used in academia, and also in industry, e.g., by engineers at Meta to verify the core components of an interprocess communication system for a new operating system.

Read more...