Search

SMPT (for Satisfiability Modulo Petri Net) is a model checker for reachability problems in Petri nets. It started as a portfolio of methods to experiment with symbolic model checking, and was designed to be easily extended. Some distinctive features are its ability to benefit from structural reductions and to generate verdict certificates. Our tool is quite mature and performed well compared to other state-of-the-art tools in the Model Checking Contest., FM 2023 - 25th International Symposium on Formal Methods,, Mar 2023, L{\"u}beck, Germany

This work introduces a general formulation of the reconfiguration problem for untimed discrete-event systems (DES), which can be treated directly by supervisory control theory (SCT). To model the reconfiguration requirements we introduce the concept of reconfiguration specification (RS); here reconfiguration events (RE) are introduced to force a transition from one system configuration to another. Standard SCT synthesis is employed to obtain a reconfiguration supervisor (RSUP) in which designated states serve as the source states for RE. The reconfiguration problem itself is formulated as that of establishing guaranteed finite reachability of a desired RE source state in RSUP from the current state in RSUP at which a change in configuration is commanded by an external user. The solvability (or otherwise) of this reachability problem is established by backtracking as in standard dynamic programming., 2017 14th International Conference on Electrical Engineering, Computing Science and Automatic Control (CCE)

Reachability analysis is one of the most basic and challenging problems in verification. We investigate this problem in multi-agent reinforcement learning (MARL) system by transforming the reachability analysis to decision-making problem tackled by mixed integer linear programming (MILP) solver Gurobi. We define syntax and semantics for multi-role strategy logic (mrSL) which is used to describe the reachability specification. The logic mrSL is a variant of SL to express properties, which provide a holistic perspective to describe reachability properties instead of specifying a specific agent reaches a certain state in the MARL system. And the algorithms to translate reachability property into MILP constraints are provided. A tool called MAReachAnalysis is introduced, which uses Gurobi to solve the corresponding reachability problem and evaluate it on the predator-prey task of multi-agent deep deterministic policy gradient (MADDPG) example, discussion of the experimental results obtained on a range of test cases.

International audience; Polynomial Interrupt Timed Automata (PolITA) are finite automata with clocks organized along hierarchical levels. These clocks are equipped with an interruption mechanism, well suited to the modeling of real-time operating systems. Moreover, transitions between states contain polynomial guards and updates. The reachability problem in this class is known to be in 2EXPTIME with a decision procedure based on the cylindrical algebraic decomposition. We improve this complexity to EXPSPACE mainly using a combinatorial argument and we include a reduction leading to a PSPACE lower bound.

A rotor walk in a directed graph can be thought of as a deterministic version of a Markov Chain, where a pebble moves from vertex to vertex following a simple rule until a terminal vertex, or sink, has been reached. The ARRIVAL problem, as defined by Dohrau et al. [Dohrau et al., 2017], consists in determining which sink will be reached. While the walk itself can take an exponential number of steps, this problem belongs to the complexity class NP ∩ co-NP without being known to be in P. In this work, we define a class of directed graphs, namely tree-like multigraphs, which are multigraphs having the global shape of an undirected tree. We prove that in this class, ARRIVAL can be solved in almost linear time, while the number of steps of a rotor walk can still be exponential. Then, we give an application of this result to solve some deterministic analogs of stochastic models (e.g., Markovian decision processes, Stochastic Games)., LIPIcs, Vol. 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), pages 12:1-12:14

Petri nets, equivalently presentable as vector addition systems with states, are an established model of concurrency with widespread applications. The reachability problem, where we ask whether from a given initial configuration there exists a sequence of valid execution steps reaching a given final configuration, is the central algorithmic problem for this model. The complexity of the problem has remained, until recently, one of the hardest open questions in verification of concurrent systems. A first upper bound has been provided only in 2015 by Leroux and Schmitz, then refined by the same authors to non-primitive recursive Ackermannian upper bound in 2019. The exponential space lower bound, shown by Lipton already in 1976, remained the only known for over 40 years until a breakthrough non-elementary lower bound by Czerwi��ski, Lasota, Lazic, Leroux and Mazowiecki in 2019. Finally, a matching Ackermannian lower bound announced this year by Czerwi��ski and Orlikowski, and independently by Leroux, established the complexity of the problem. Our primary contribution is an improvement of the former construction, making it conceptually simpler and more direct. On the way we improve the lower bound for vector addition systems with states in fixed dimension (or, equivalently, Petri nets with fixed number of places): while Czerwi��ski and Orlikowski prove F_k-hardness (hardness for kth level in Grzegorczyk Hierarchy) in dimension 6k, our simplified construction yields F_k-hardness already in dimension 3k+2., LIPIcs, Vol. 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), pages 46:1-46:15

We briefly describe recent advances on understanding the complexity of the reachability problem for vector addition systems (or equivalently for vector addition systems with states - VASSes). We present a zoo of a few involved VASS examples, which illustrate various aspects of hardness of VASSes and various techniques of proving lower complexity bounds., LIPIcs, Vol. 243, 33rd International Conference on Concurrency Theory (CONCUR 2022), pages 5:1-5:13

We study the reachability problem for affine $\mathbb{Z}$-VASS, which are integer vector addition systems with states in which transitions perform affine transformations on the counters. This problem is easily seen to be undecidable in general, and we therefore restrict ourselves to affine $\mathbb{Z}$-VASS with the finite-monoid property (afmp-$\mathbb{Z}$-VASS). The latter have the property that the monoid generated by the matrices appearing in their affine transformations is finite. The class of afmp-$\mathbb{Z}$-VASS encompasses classical operations of counter machines such as resets, permutations, transfers and copies. We show that reachability in an afmp-$\mathbb{Z}$-VASS reduces to reachability in a $\mathbb{Z}$-VASS whose control-states grow linearly in the size of the matrix monoid. Our construction shows that reachability relations of afmp-$\mathbb{Z}$-VASS are semilinear, and in particular enables us to show that reachability in $\mathbb{Z}$-VASS with transfers and $\mathbb{Z}$-VASS with copies is PSPACE-complete. We then focus on the reachability problem for affine $\mathbb{Z}$-VASS with monogenic monoids: (possibly infinite) matrix monoids generated by a single matrix. We show that, in a particular case, the reachability problem is decidable for this class, disproving a conjecture about affine $\mathbb{Z}$-VASS with infinite matrix monoids we raised in a preliminary version of this paper. We complement this result by presenting an affine $\mathbb{Z}$-VASS with monogenic matrix monoid and undecidable reachability relation.

Vector addition systems with states (VASS) are widely used for the formal verification of concurrent systems. Given their tremendous computational complexity, practical approaches have relied on techniques such as reachability relaxations, e.g., allowing for negative intermediate counter values. It is natural to question their feasibility for VASS enriched with primitives that typically translate into undecidability. Spurred by this concern, we pinpoint the complexity of integer relaxations with respect to arbitrary classes of affine operations. More specifically, we provide a trichotomy on the complexity of integer reachability in VASS extended with affine operations (affine VASS). Namely, we show that it is NP-complete for VASS with resets, PSPACE-complete for VASS with (pseudo-)transfers and VASS with (pseudo-)copies, and undecidable for any other class. We further present a dichotomy for standard reachability in affine VASS: it is decidable for VASS with permutations, and undecidable for any other class. This yields a complete and unified complexity landscape of reachability in affine VASS. We also consider the reachability problem parameterized by a fixed affine VASS, rather than a class, and we show that the complexity landscape is arbitrary in this setting.

A communicating system is \(k\)-synchronizable if all of the message sequence charts representing the executions can be divided into slices of k sends followed by k receptions. It was previously shown that, for a fixed given k, one could decide whether a communicating system is \(k\)-synchronizable. This result is interesting because the reachability problem can be solved for \(k\)-synchronizable systems. However, the decision procedure assumes that the bound k is fixed. In this paper we improve this result and show that it is possible to decide if such a bound k exists.

Stealthy attacks on Industrial Control Systems can cause significant damage while evading detection. In this paper, instead of focusing on the detection of stealthy attacks, we aim to provide early warnings to operators, in order to avoid physical damage and preserve in advance data that may serve as an evidence during an investigation. We propose a framework to provide grounds for suspicion, i.e. preliminary indicators reflecting the likelihood of success of a stealthy attack. We propose two grounds for suspicion based on the behaviour of the physical process: (i) feasibility of a stealthy attack, and (ii) proximity to unsafe operating regions. We propose a metric to measure grounds for suspicion in real-time and provide soundness principles to ensure that such a metric is consistent with the grounds for suspicion. We apply our framework to Linear Time-Invariant (LTI) systems and formulate the suspicion metric computation as a real-time reachability problem. We validate our framework on a case study involving the benchmark Tennessee-Eastman process. We show through numerical simulation that we can provide early warnings well before a potential stealthy attack can cause damage, while incurring minimal load on the network. Finally, we apply our framework on a use case to illustrate its usefulness in supporting early evidence collection.

International audience; Vector addition systems with states (VASS for short), or equivalently Petri nets are one of the most popular formal methods for the representation and the analysis of parallel processes. The central algorithmic problem is reachability: whether from a given initial configuration there exists a sequence of valid execution steps that reaches a given final configuration. This paper provides an overview of results about the reachability problem for VASS related to Presburger arithmetic, by presenting 1) a simple algorithm for deciding the reachability problem based on invariants definable in Presburger arithmetic, 2) the class of flat VASS for computing reachability sets in Presburger arithmetic, and 3) complexity results about the reachability problem for flat VASS.

Petri nets are an important formal paradigm for modeling and analysis of discrete event systems. The related areas of application of Petri nets include deadlock avoidance and prevention, supervisory control, forbidden state detection, different aspects of flexible manufacturing systems, and many others (Zhou & DiCesare, 1993; Holloway et al., 1997; Boel et al., 1995). Quite often, given a discrete-event system, the designer is interested in determining whether the system can transit from an initial state to another, target state as a result of some operations from a predefined set. In terms of Petri nets, the answer to this question is obtained as a solution of a reachability problem. The reachability problem in Petri nets is formulated as follows: for any Petri net PN, with an initial marking M0, and for some other marking M, determine whether the relation M ∈ R(PN, M0) is true, where R(PN, M0) is the reachability set of PN for its initial marking M0 (Murata, 1989). The decidability of the reachability problem has been proved for a number of restricted classes of Petri nets, and there are efficient algorithms for such classes as acyclic Petri nets, marked graphs, and others (Kodama & Murata, 1988; Caprotti et al., 1995; Kostin, 1997). It has been shown that the reachability problem is decidable for generalized Petri nets as well (Mayr, 1984). The fundamental contribution of the paper (Mayr, 1984) is in proving that the reachability problem for generalized Petri nets is decidable. However, being highly important theoretically, the practical use of the algorithm described in that paper is limited. Actually, the algorithm creates a series of so called regular constrained refined graphs, each of which is a generalization of the basic coverability tree. As the author admits, the first refined graph would enumerate the whole reachability set of the given Petri net. In practice, two different approaches are used most often to determine the reachability of a marking in Petri nets. The first approach is based on the creation and investigation of a complete or reduced reachability graph. The main drawback of this approach is a state explosion problem. A closely related technique is the use of stubborn sets. The main purpose of the stubborn sets technique is to choose, for each marking of the net, a set of transitions to fire that is large enough to preserve some desired information about the Petri net, but is as small as possible to get a significant reduction of the resulting reachability graph (Varpaaniemi, 1998). Unfortunately, generation of minimal or reduced reachability graphs in finite state systems is known to be an NP-hard problem (Peled, 1993). If Petri net has no

We investigate computational complexity of the reachability problem for vector addition systems (or, equivalently, Petri nets), the central algorithmic problem in verification of concurrent systems. Concerning its complexity, after 40 years of stagnation, a non-elementary lower bound has been shown recently: the problem needs a tower of exponentials of time or space, where the height of tower is linear in the input size. We improve on this lower bound, by increasing the height of tower from linear to exponential. As a side-effect, we obtain better lower bounds for vector addition systems of fixed dimension., LIPIcs, Vol. 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pages 128:1-128:15

We address the problem of verifying the reachability problem in programs running under the formal model Px86 defined recently by Raad et al. in POPL'20 for the persistent Intel x86 architecture. We prove that this problem is decidable. To achieve that, we provide a new formal model that is equivalent to Px86 and that has the feature of being a well structured system. Deriving this new model is the result of a deep investigation of the properties of Px86 and the interplay of its components.

The main topic of this thesis is the analysis of evolution equations reflecting issues in ecology and population dynamics. In mathematical modelling, the impact of environmental elements and the interaction between species is read into the role of heterogeneity in equations and interactions in coupled systems. In this direction, we investigate three separate problems. The first problem addresses the evolution of a single population living in a periodic medium with a fast diffusion line; this corresponds to the study of a reaction-diffusion system with equations in different dimensions. Result on asymptotic behaviour are derived through the study of some generalised principal eigenvalues. We find that the presence of the road has no impact on the survival chances of the population, despite the deleterious effect expected from fragmentation. The second study regards a model describing the competition between two populations in a situation of asymmetrically aggressive interactions; this consists in a system of two ODEs. The evolution progresses through two possible scenarios, where only one population survives. The interpretation of one of the parameters as the aggressiveness of the attacker naturally raises questions of controllability. We characterise the set of initial conditions leading to the victory of the attacker through a suitable (possibly time-dependant) strategy. The third part of this thesis analyses the time decay of some evolution equations with classical and fractional time derivatives. Depending on the type of derivative and some degree of non-degeneracy of the spatial operator, quantitative polynomial or exponential estimates are entailed., Le sujet principal de cette thèse est l'analyse des équations de l'évolution reflétant les questions d'écologie et de dynamique des populations. Dans la modélisation mathématique, l'impact des éléments environnementaux et l'interaction entre les espèces est lu dans le rôle de l'hétérogénéité dans les équations et les interactions dans les systèmes couplés. Dans cette direction, nous étudions trois problèmes distincts. Le premier traite l'évolution d'une population vivant dans un milieu périodique avec une ligne de diffusion rapide ; cela correspond à l'étude d'un système de réaction-diffusion avec des équations dans différentes dimensions. Nous obtenons des résultats sur le comportement asymptotique par l'étude de quelques valeurs propres principales généralisées. Nous constatons que la route n'a aucun impact sur les chances de survie de la population. La deuxième étude porte sur un modèle décrivant la compétition entre deux populations dans une situation d'interactions asymétriquement agressives ; il s'agit d'un système de deux EDO. L'évolution progresse à travers deux scénarios possibles, où une seule population survit. L'interprétation d'un des paramètres comme étant l'agressivité de l’attaquant soulève naturellement des questions de contrôlabilité. Nous caractérisons l'ensemble des conditions initiales menant à la victoire par une stratégie appropriée (éventuellement dépendante du temps). La troisième partie de cette thèse analyse la décroissance temporelle de certaines équations d'évolution avec des dérivées temporelles classiques et fractionnaires. Selon le type de dérivée et un certain degré de non-dégénérescence de l'opérateur spatial, des estimations quantitatives polynomiales ou exponentielles sont réalisées.

Logical Methods in Computer Science ; Volume 16, Issue 4 ; 1860-5974, In the last two decades, there has been much progress on model checking of both probabilistic systems and higher-order programs. In spite of the emergence of higher-order probabilistic programming languages, not much has been done to combine those two approaches. In this paper, we initiate a study on the probabilistic higher-order model checking problem, by giving some first theoretical and experimental results. As a first step towards our goal, we introduce PHORS, a probabilistic extension of higher-order recursion schemes (HORS), as a model of probabilistic higher-order programs. The model of PHORS may alternatively be viewed as a higher-order extension of recursive Markov chains. We then investigate the probabilistic termination problem -- or, equivalently, the probabilistic reachability problem. We prove that almost sure termination of order-2 PHORS is undecidable. We also provide a fixpoint characterization of the termination probability of PHORS, and develop a sound (but possibly incomplete) procedure for approximately computing the termination probability. We have implemented the procedure for order-2 PHORSs, and confirmed that the procedure works well through preliminary experiments that are reported at the end of the article.

We prove that any two-pass graph streaming algorithm for the $s-t$ reachability problem in $n$ -vertex directed graphs requires near-quadratic space of $n^{2-o(1)}$ bits. As a corollary, we also obtain near-quadratic space lower bounds for several other fundamental problems including maximum bipartite matching and (approximate) shortest path in undirected graphs. Our results collectively imply that a wide range of graph problems admit essentially no non-trivial streaming algorithm even when two passes over the input is allowed. Prior to our work, such impossibility results were only known for single-pass streaming algorithms, and the best two-pass lower bounds only ruled out $o(n^{7/6})$ space algorithms, leaving open a large gap between (trivial) upper bounds and lower bounds.

Vector addition system with states is an ubiquitous model of computation with extensive applications in computer science. The reachability problem for vector addition systems is central since many other problems reduce to that question. The problem is decidable and it was recently proved that the dimension of the vector addition system is an important parameter of the complexity. In fixed dimensions larger than two, the complexity is not known (with huge complexity gaps). In dimension two, the reachability problem was shown to be PSPACE-complete by Blondin et al. in 2015. We consider an extension of this model, called 2-TVASS, where the first counter can be tested for zero. This model naturally extends the classical model of one counter automata (OCA). We show that reachability is still solvable in polynomial space for 2-TVASS. As in the work Blondin et al., our approach relies on the existence of small reachability certificates obtained by concatenating polynomially many cycles., Comment: Full version of the paper with the same title and authors in the proceedings of CONCUR 2020

Part 1: Full Papers; International audience; Clock-dependent probabilistic timed automata extend classical timed automata with discrete probabilistic choice, where the probabilities are allowed to depend on the exact values of the clocks. Previous work has shown that the quantitative reachability problem for clock-dependent probabilistic timed automata with at least three clocks is undecidable. In this paper, we consider the subclass of clock-dependent probabilistic timed automata that have one clock, that have clock dependencies described by affine functions, and that satisfy an initialisation condition requiring that, at some point between taking edges with non-trivial clock dependencies, the clock must have an integer value. We present an approach for solving in polynomial time quantitative and qualitative reachability problems of such one-clock initialised clock-dependent probabilistic timed automata. Our results are obtained by a transformation to interval Markov decision processes.

International audience; Deciding privacy-type properties of deterministic cryptographic protocols such as anonymity and strong secrecy can be reduced to deciding the symbolic equivalence of processes, where each process is described by a set of possible symbolic traces. This equivalence is parameterized by a deduction system that describes which actions and observations an intruder can perform on a running system. We present in this paper a notion of finitary deduction systems. For this class of deduction system, we first reduce the problem of the equivalence of processes with no disequations to the resolution of reachability problem on each symbolic trace of one process, and then testing whether each solution found is solution of a related trace in the other process. We then extend this reduction to the case of generic deterministic finite processes in which symbolic traces may contain disequalities.