BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Nathalie Bertrand

Nathalie Bertrand appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Logic in Computer ScienceFormal Languages and Automata TheoryComputational Engineering, Finance, and ScienceDistributed, Parallel, and Cluster ComputingPerformanceComputer Science and Game TheoryCryptography and Securitymath.APmath.NAProgramming Languages

Catalog footprint

What is connected

12works
10topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

12 published item(s)

preprint2022arXiv

Holistic Verification of Blockchain Consensus

Blockchain has recently attracted the attention of the industry due, in part, to its ability to automate asset transfers. It requires distributed participants to reach a consensus on a block despite the presence of malicious (a.k.a. Byzantine) participants. Malicious participants exploit regularly weaknesses of these blockchain consensus algorithms, with sometimes devastating consequences. In fact, these weaknesses are quite common and are well illustrated by the flaws in the hand-written proofs of existing blockchain consensus protocols [63]. Paradoxically, until now, no blockchain consensus has been holistically verified using model checking. In this paper, we remedy this paradox by model checking for the first time a blockchain consensus used in industry. We propose a holistic approach to verify the consensus algorithm of the Red Belly Blockchain [20], for any number $n$ of processes and any number $f<n/3$ of Byzantine processes. We decompose directly the algorithm pseudocode in two parts -- an inner broadcast algorithm and an outer decision algorithm -- each modelled as a threshold automaton [36], and we formalize their expected properties in linear-time temporal logic. We then automatically check the inner broadcasting algorithm, under a carefully identified fairness assumption. For the verification of the outer algorithm, we simplify the model of the inner algorithm by relying on its checked properties. Doing so, we formally verify not only the safety properties of the Red Belly Blockchain consensus but also its liveness in about 70 seconds.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Parameterized safety verification of round-based shared-memory systems

We consider the parameterized verification problem for distributed algorithms where the goal is to develop techniques to prove the correctness of a given algorithm regardless of the number of participating processes. Motivated by an asynchronous binary consensus algorithm [J. Aspnes, Fast deterministic consensus in a noisy environment. Journal of Algorithms, 2002], we consider round-based distributed algorithms communicating with shared memory. A particular challenge in these systems is that 1) the number of processes is unbounded, and, more importantly, 2) there is a fresh set of registers at each round. A~verification algorithm thus needs to manage both sources of infinity. In this setting, we prove that the safety verification problem, which consists in deciding whether all possible executions avoid a given error state, is PSPACE-complete. For~negative instances of the safety verification problem, we~also provide exponential lower and upper bounds on the minimal number of processes needed for an error execution and on the minimal round on which the error state can be covered.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Use of 3D classified topographic data with FullSWOF for high resolution simulation of a river flood event over a dense urban area

High resolution (infra-metric) topographic data, including photogram-metric born 3D classified data, are becoming commonly available at large range of spatial extend, such as municipality or industrial site scale. This category of dataset is promising for high resolution (HR) Digital Surface Model (DSM) generation, allowing inclusion of fine above-ground structures which might influence overland flow hydrodynamic in urban environment. Nonetheless several categories of technical and numerical challenges arise from this type of data use with standard 2D Shallow Water Equations (SWE) based numerical codes. FullSWOF (Full Shallow Water equations for Overland Flow) is a code based on 2D SWE under conservative form. This code relies on a well-balanced finite volume method over a regular grid using numerical method based on hydrostatic reconstruction scheme. When compared to existing industrial codes used for urban flooding simulations, numerical approach implemented in FullSWOF allows to handle properly flow regime changes, preservation of water depth positivity at wet/dry cells transitions and steady state preservation. FullSWOF has already been tested on analytical solution library (SWASHES) and has been used to simulate runoff and dam-breaks. FullSWOFs above mentioned properties are of good interest for urban overland flow. Objectives of this study are (i) to assess the feasibility and added values of using HR 3D classified topographic data to model river overland flow and (ii) to take advantage of FullSWOF code properties for overland flow simulation in urban environment.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Proceedings Thirteenth Workshop on Quantitative Aspects of Programming Languages and Systems

This volume contains the proceedings of the Thirteenth Workshop on Quantitative Aspects of Programming Languages and Systems (QAPL 2015), held in London, UK, on 11 and 12 April, 2015. QAPL 2015 was a satellite event of the European Joint Conferences on Theory and Practice of Software (ETAPS) focussing on quantitative aspects of computation. The Program Committee of QAPL 2015 selected 8 regular papers and 2 presentation-only papers. The workshop programme included two QAPL keynote presentations by Catuscia Palamidessi (Inria/LIX, France) on "Quantitative Aspects of Privacy and Information Flow," and Holger Hermanns (Saarland University, Germany) on "Optimal Continuous Time Markov Decisions."

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Proceedings Twelfth International Workshop on Quantitative Aspects of Programming Languages and Systems

This volume contains the proceedings of the Twelfth Workshop on Quantitative Aspects of Programming Languages and Systems (QAPL 2014), held in Grenoble, France, on 12 and 13 April, 2014. QAPL 2014 was a satellite event of the European Joint Conferences on Theory and Practice of Software (ETAPS). The central theme of the workshop is that of quantitative aspects of computation. These aspects are related to the use of physical quantities (storage space, time, bandwidth, etc.) as well as mathematical quantities (e.g. probability and measures for reliability, security and trust), and play an important (sometimes essential) role in characterising the behaviour and determining the properties of systems. Such quantities are central to the definition of both the model of systems (architecture, language design, semantics) and the methodologies and tools for the analysis and verification of the systems properties. The aim of this workshop is to discuss the explicit use of quantitative information such as time and probabilities either directly in the model or as a tool for the analysis of systems.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Stochastic Timed Automata

A stochastic timed automaton is a purely stochastic process defined on a timed automaton, in which both delays and discrete choices are made randomly. We study the almost-sure model-checking problem for this model, that is, given a stochastic timed automaton A and a property $Φ$, we want to decide whether A satisfies $Φ$ with probability 1. In this paper, we identify several classes of automata and of properties for which this can be decided. The proof relies on the construction of a finite abstraction, called the thick graph, that we interpret as a finite Markov chain, and for which we can decide the almost-sure model-checking problem. Correctness of the abstraction holds when automata are almost-surely fair, which we show, is the case for two large classes of systems, single- clock automata and so-called weak-reactive automata. Techniques employed in this article gather tools from real-time verification and probabilistic verification, as well as topological games played on timed automata.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Emptiness and Universality Problems in Timed Automata with Positive Frequency

The languages of infinite timed words accepted by timed automata are traditionally defined using Buchi-like conditions. These acceptance conditions focus on the set of locations visited infinitely often along a run, but completely ignore quantitative timing aspects. In this paper we propose a natural quantitative semantics for timed automata based on the so-called frequency, which measures the proportion of time spent in the accepting locations. We study various properties of timed languages accepted with positive frequency, and in particular the emptiness and universality problems.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Solving Stochastic Büchi Games on Infinite Arenas with a Finite Attractor

We consider games played on an infinite probabilistic arena where the first player aims at satisfying generalized Büchi objectives almost surely, i.e., with probability one. We provide a fixpoint characterization of the winning sets and associated winning strategies in the case where the arena satisfies the finite-attractor property. From this we directly deduce the decidability of these games on probabilistic lossy channel systems.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Bounded Satisfiability for PCTL

While model checking PCTL for Markov chains is decidable in polynomial-time, the decidability of PCTL satisfiability, as well as its finite model property, are long standing open problems. While general satisfiability is an intriguing challenge from a purely theoretical point of view, we argue that general solutions would not be of interest to practitioners: such solutions could be too big to be implementable or even infinite. Inspired by bounded synthesis techniques, we turn to the more applied problem of seeking models of a bounded size: we restrict our search to implementable -- and therefore reasonably simple -- models. We propose a procedure to decide whether or not a given PCTL formula has an implementable model by reducing it to an SMT problem. We have implemented our techniques and found that they can be applied to the practical problem of sanity checking -- a procedure that allows a system designer to check whether their formula has an unexpectedly small model.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Off-line test selection with test purposes for non-deterministic timed automata

This article proposes novel off-line test generation techniques from non-deterministic timed automata with inputs and outputs (TAIOs) in the formal framework of the tioco conformance theory. In this context, a first problem is the determinization of TAIOs, which is necessary to foresee next enabled actions after an observable trace, but is in general impossible because not all timed automata are determinizable. This problem is solved thanks to an approximate determinization using a game approach. The algorithm performs an io-abstraction which preserves the tioco conformance relation and thus guarantees the soundness of generated test cases. A second problem is the selection of test cases from a TAIO specification. The selection here relies on a precise description of timed behaviors to be tested which is carried out by expressive test purposes modeled by a generalization of TAIOs. Finally, an algorithm is described which generates test cases in the form of TAIOs equipped with verdicts, using a symbolic co-reachability analysis guided by the test purpose. Properties of test cases are then analyzed with respect to the precision of the approximate determinization: when determinization is exact, which is the case on known determinizable classes, in addition to soundness, properties characterizing the adequacy of test cases verdicts are also guaranteed.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Probabilistic regular graphs

Deterministic graph grammars generate regular graphs, that form a structural extension of configuration graphs of pushdown systems. In this paper, we study a probabilistic extension of regular graphs obtained by labelling the terminal arcs of the graph grammars by probabilities. Stochastic properties of these graphs are expressed using PCTL, a probabilistic extension of computation tree logic. We present here an algorithm to perform approximate verification of PCTL formulae. Moreover, we prove that the exact model-checking problem for PCTL on probabilistic regular graphs is undecidable, unless restricting to qualitative properties. Our results generalise those of EKM06, on probabilistic pushdown automata, using similar methods combined with graph grammars techniques.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

Verifying nondeterministic probabilistic channel systems against $ω$-regular linear-time properties

Lossy channel systems (LCSs) are systems of finite state automata that communicate via unreliable unbounded fifo channels. In order to circumvent the undecidability of model checking for nondeterministic LCSs, probabilistic models have been introduced, where it can be decided whether a linear-time property holds almost surely. However, such fully probabilistic systems are not a faithful model of nondeterministic protocols. We study a hybrid model for LCSs where losses of messages are seen as faults occurring with some given probability, and where the internal behavior of the system remains nondeterministic. Thus the semantics is in terms of infinite-state Markov decision processes. The purpose of this article is to discuss the decidability of linear-time properties formalized by formulas of linear temporal logic (LTL). Our focus is on the qualitative setting where one asks, e.g., whether a LTL-formula holds almost surely or with zero probability (in case the formula describes the bad behaviors). Surprisingly, it turns out that -- in contrast to finite-state Markov decision processes -- the satisfaction relation for LTL formulas depends on the chosen type of schedulers that resolve the nondeterminism. While all variants of the qualitative LTL model checking problem for the full class of history-dependent schedulers are undecidable, the same questions for finite-memory scheduler can be solved algorithmically. However, the restriction to reachability properties and special kinds of recurrent reachability properties yields decidable verification problems for the full class of schedulers, which -- for this restricted class of properties -- are as powerful as finite-memory schedulers, or even a subclass of them.

0 citations0 reviewsNo code linkedOpen access