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

Étienne André

Étienne André appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Formal Languages and Automata TheoryLogic in Computer ScienceSystems and Controleess.SYOperating SystemsSoftware EngineeringCryptography and SecurityDistributed, Parallel, and Cluster ComputingSymbolic Computation

Catalog footprint

What is connected

12works
9topics
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)

preprint2024arXiv

Parameterized Verification of Disjunctive Timed Networks

We introduce new techniques for the parameterized verification of disjunctive timed networks (DTNs), i.e., networks of timed automata (TAs) that communicate via location guards that enable a transition only if there is another process in a given location. This computational model has been considered in the literature before, example applications are gossiping clock synchronization protocols or planning problems. We address the minimum-time reachability problem (Minreach) in DTNs, and show how to efficiently solve it based on a novel zone graph algorithm. We further show that solving Minreach allows us to construct a summary TA capturing exactly the possible behaviors of a single TA within a DTN of arbitrary size. The combination of these two results enables the parameterized verification of DTNs, while avoiding the construction of an exponential-size cutoff system required by existing results. Additionally, we develop sufficient conditions for solving Minreach and parameterized verification problems even in certain cases where locations that appear in location guards can have clock invariants, a case that has usually been excluded in the literature. Our techniques are also implemented, and experiments show their practicality.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Exemplifying parametric timed specifications over signals with bounded behavior

Specifying properties can be challenging work. In this paper, we propose an automated approach to exemplify properties given in the form of automata extended with timing constraints and timing parameters, and that can also encode constraints over real-valued signals. That is, given such a specification and given an admissible automaton for each signal, we output concrete runs exemplifying real (or impossible) runs for this specification. Specifically, our method takes as input a specification, and a set of admissible behaviors, all given as a subclass of rectangular hybrid automata, namely timed automata extended with arbitrary clock rates, signal constraints, and timing parameters. Our method then generates concrete runs exemplifying the specification.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Timed automata as a formalism for expressing security: A survey on theory and practice

Timed automata are a common formalism for the verification of concurrent systems subject to timing constraints. They extend finite-state automata with clocks, that constrain the system behavior in locations, and to take transitions. While timed automata were originally designed for safety (in the wide sense of correctness w.r.t. a formal property), they were progressively used in a number of works to guarantee security properties. In this work, we review works studying security properties for timed automata in the last two decades. We notably review theoretical works, with a particular focus on opacity, as well as more practical works, with a particular focus on attack trees and their extensions. We derive main conclusions concerning open perspectives, as well as tool support.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Zone extrapolations in parametric timed automata

Timed automata (TAs) are an efficient formalism to model and verify systems with hard timing constraints, and concurrency. While TAs assume exact timing constants with infinite precision, parametric TAs (PTAs) leverage this limitation and increase their expressiveness, at the cost of undecidability. A practical explanation for the efficiency of TAs is zone extrapolation, where clock valuations beyond a given constant are considered equivalent. This concept cannot be easily extended to PTAs, due to the fact that parameters can be unbounded. In this work, we propose several definitions of extrapolation for PTAs based on the M-extrapolation, and we study their correctness. Our experiments show an overall decrease of the computation time and, most importantly, allow termination of some previously unsolvable benchmarks.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Automated synthesis of local time requirement for service composition

Service composition aims at achieving a business goal by composing existing service-based applications or components. The response time of a service is crucial especially in time critical business environments, which is often stated as a clause in service level agreements between service providers and service users. To meet the guaranteed response time requirement of a composite service, it is important to select a feasible set of component services such that their response time will collectively satisfy the response time requirement of the composite service. In this work, we use the BPEL modeling language, that aims at specifying Web services. We extend it with timing parameters, and equip it with a formal semantics. Then, we propose a fully automated approach to synthesize the response time requirement of component services modeled using BPEL, in the form of a constraint on the local response times. The synthesized requirement will guarantee the satisfaction of the global response time requirement, statically or dynamically. We implemented our work into a tool, Selamat, and performed several experiments to evaluate the validity of our approach.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Guaranteed phase synchronization of hybrid oscillators using symbolic Euler's method: The Brusselator and biped examples

The phenomenon of phase synchronization was evidenced in the 17th century by Huygens while observing two pendulums of clocks leaning against the same wall. This phenomenon has more recently appeared as a widespread phenomenon in nature, and turns out to have multiple industrial applications. The exact parameter values of the system for which the phenomenon manifests itself are however delicate to obtain in general, and it is interesting to find formal sufficient conditions to guarantee phase synchronization. Using the notion of reachability, we give here such a formal method. More precisely, our method selects a portion $S$ of the state space, and shows that any solution starting at $S$ returns to $S$ within a fixed number of periods $k$. Besides, our method shows that the components of the solution are then (almost) in phase. We explain how the method applies on the Brusselator reaction-diffusion and the biped walker examples.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Robust optimal control using dynamic programming and guaranteed Euler's method

Set-based integration methods allow to prove properties of differential systems, which take into account bounded disturbances. The systems (either time-discrete, time-continuous or hybrid) satisfying such properties are said to be "robust". In the context of optimal control synthesis, the set-based methods are generally extensions of numerical optimal methods of two classes: first, methods based on convex optimization; second, methods based on the dynamic programming principle. Heymann et al. have recently shown that, for certain systems of low dimension, the second numerical method can give better solutions than the first one. They have built a solver (Bocop) that implements both numerical methods. We show in this paper that a set-based extension of a method of the second class which uses a guaranteed Euler integration method, allows us to find such good solutions. Besides, these solutions enjoy the property of robustness against uncertainties on initial conditions and bounded disturbances. We demonstrate the practical interest of our method on an example taken from the numerical Bocop solver. We also give a variant of our method, inspired by the method of Model Predictive Control, that allows us to find more efficiently an optimal control at the price of losing robustness.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Proceedings 1st International Workshop on Synthesis of Continuous Parameters

This volume contains the proceedings of the 1st International Workshop on Synthesis of Continuous Parameters (SynCoP'14). The workshop was held in Grenoble, France on April 6th, 2014, as a satellite event of the 17th European Joint Conferences on Theory and Practice of Software (ETAPS'14). SynCoP aims at bringing together researchers working on parameter synthesis for systems with continuous variables, where the parameters consist of a (usually dense) set of constant values. Synthesis problems for such parameters arise for real-time, hybrid or probabilistic systems in a large variety application domains. A parameter could be, e.g., a delay in a real-time system, or a reaction rate in a biological cell model. The objective of the synthesis problem is to identify suitable parameters to achieve desired behavior, or to verify the behavior for a given range of parameter values. This volume contains seven contributions: two invited talks and five regular papers.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Toward Parametric Timed Interfaces for Real-Time Components

We propose here a framework to model real-time components consisting of concurrent real-time tasks running on a single processor, using parametric timed automata. Our framework is generic and modular, so as to be easily adapted to different schedulers and more complex task models. We first perform a parametric schedulability analysis of the components using the inverse method. We show that the method unfortunately does not provide satisfactory results when the task periods are consid- ered as parameters. After identifying and explaining the problem, we present a solution adapting the model by making use of the worst-case scenario in schedulability analysis. We show that the analysis with the inverse method always converges on the modified model when the system load is strictly less than 100%. Finally, we show how to use our parametric analysis for the generation of timed interfaces in compositional system design.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Translating UML State Machines to Coloured Petri Nets Using Acceleo: A Report

UML state machines are widely used to specify dynamic systems behaviours. However its semantics is described informally, thus preventing the application of model checking techniques that could guarantee the system safety. In a former work, we proposed a formalisation of non-concurrent UML state machines using coloured Petri nets, so as to allow for formal verification. In this paper, we report our experience to implement this translation in an automated manner using the model-to-text transformation tool Acceleo. Whereas Acceleo provides interesting features that facilitated our translation process, it also suffers from limitations uneasy to overcome.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Parametric Schedulability Analysis of Fixed Priority Real-Time Distributed Systems

Parametric analysis is a powerful tool for designing modern embedded systems, because it permits to explore the space of design parameters, and to check the robustness of the system with respect to variations of some uncontrollable variable. In this paper, we address the problem of parametric schedulability analysis of distributed real-time systems scheduled by fixed priority. In particular, we propose two different approaches to parametric analysis: the first one is a novel technique based on classical schedulability analysis, whereas the second approach is based on model checking of Parametric Timed Automata (PTA). The proposed analytic method extends existing sensitivity analysis for single processors to the case of a distributed system, supporting preemptive and non-preemptive scheduling, jitters and unconstrained deadlines. Parametric Timed Automata are used to model all possible behaviours of a distributed system, and therefore it is a necessary and sufficient analysis. Both techniques have been implemented in two software tools, and they have been compared with classical holistic analysis on two meaningful test cases. The results show that the analytic method provides results similar to classical holistic analysis in a very efficient way, whereas the PTA approach is slower but covers the entire space of solutions.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

IMITATOR II: A Tool for Solving the Good Parameters Problem in Timed Automata

We present here Imitator II, a new version of Imitator, a tool implementing the "inverse method" for parametric timed automata: given a reference valuation of the parameters, it synthesizes a constraint such that, for any valuation satisfying this constraint, the system behaves the same as under the reference valuation in terms of traces, i.e., alternating sequences of locations and actions. Imitator II also implements the "behavioral cartography algorithm", allowing us to solve the following good parameters problem: find a set of valuations within a given bounded parametric domain for which the system behaves well. We present new features and optimizations of the tool, and give results of applications to various examples of asynchronous circuits and communication protocols.

0 citations0 reviewsNo code linkedOpen access