We investigate a rigorous simulation and testing-based validation method for autonomous driving systems that integrates an existing industrial simulator and a formally defined testing environment. The environment includes a scenario generator that drives the simulation process and a monitor that checks at runtime the observed behavior of the system against a set of system properties to be validated. The validation method consists in extracting from the simulator a semantic model of the simulated system including a metric graph, which is a mathematical model of the environment in which the vehicles of the system evolve. The monitor can verify properties formalized in a first-order linear temporal logic and provide diagnostics explaining their non-satisfaction. Instead of exploring the system behavior randomly as many simulators do, we propose a method to systematically generate sets of scenarios that cover potentially risky situations, especially for different types of junctions where specific traffic rules must be respected. We show that the systematic exploration of risky situations has uncovered many flaws in the real simulator that would have been very difficult to discover by a random exploration process.

Autonomous systems emerge from the need to progressively replace human operators by autonomous agents in a wide variety of application areas. We offer an analysis of the state of the art in developing autonomous systems, focusing on design and validation and showing that the multi-faceted challenges involved go well beyond the limits of weak AI. We argue that traditional model-based techniques are defeated by the complexity of the problem, while solutions based on end-to-end machine learning fail to provide the necessary trustworthiness. We advocate a hybrid design approach, which combines the two, adopting the best of each, and seeks tradeoffs between trustworthiness and performance. We claim that traditional risk analysis and mitigation techniques fail to scale and discuss the trend of moving away from correctness at design time and toward reliance on runtime assurance techniques. We argue that simulation and testing remain the only realistic approach for global validation and show how current methods can be adapted to autonomous systems. We conclude by discussing the factors that will play a decisive role in the acceptance of autonomous systems and by highlighting the urgent need for new theoretical foundations.

Providing safety guarantees for Autonomous Vehicle (AV) systems with machine-learning based controllers remains a challenging issue. In this work, we propose Simplex-Drive, a framework that can achieve runtime safety assurance for machine-learning enabled controllers of AVs. The proposed Simplex-Drive consists of an unverified Deep Reinforcement Learning (DRL)-based advanced controller (AC) that achieves desirable performance in complex scenarios, a Velocity-Obstacle (VO) based baseline safe controller (BC) with provably safety guarantees, and a verified mode management unit that monitors the operation status and switches the control authority between AC and BC based on safety-related conditions. We provide a formal correctness proof of Simplex-Drive and conduct a lane-changing case study in dense traffic scenarios. The simulation experiment results demonstrate that Simplex-Drive can always ensure the operation safety without sacrificing control performance, even if the DRL policy may lead to deviations from the safe status.

We study a novel principle for safe and efficient collision avoidance that adopts a mathematically elegant and general framework making as much as possible abstraction of the controlled vehicle’s dynamics and of its environment. Vehicle dynamics is characterized by pre-computed functions for accelerating and braking to a given speed. Environment is modeled by a function of time giving the free distance ahead of the controlled vehicle under the assumption that the obstacles are either fixed or are moving in the same direction. The main result is a control policy enforcing the vehicle’s speed so as to avoid collision and efficiently use the free distance ahead, provided some initial safety condition holds.The studied principle is applied to the design of a synchronous controller. We show that the controller is safe by construction. Furthermore, we show that the efficiency strictly increases for decreasing granularity of discretization. We present the implementation and experimental evaluations in the Carla autonomous driving simulator and investigate various performance issues.

We consider parameterized concurrent systems consisting of a finite but unknown number of components, obtained by replicating a given set of finite state automata.

We propose an automated method for computing inductive invariants used to proving deadlock freedom of parametric component-based systems. The method generalizes the approach for computing structural trap invariants from bounded to parametric systems with general architectures. It symbolically extracts trap invariants from interaction formulae defining the system architecture. The paper presents the theoretical foundations of the method, including new results for the first order monadic logic and proves its soundness. It also reports on a preliminary experimental evaluation on several textbook examples.

We present a criterion for checking local and global deadlock freedom of finite state systems expressed in BIP: a component-based framework for constructing complex distributed systems. Our criterion is evaluated by model-checking a set of subsystems of the overall large system. If satisfied in small subsystems, it implies deadlock-freedom of the overall system. If not satisfied, then we re-evaluate over larger subsystems, which improves the accuracy of the check. When the subsystem being checked becomes the entire system, our criterion becomes complete for deadlock-freedom. Hence our criterion only fails to decide deadlock freedom because of computational limitations: state-space explosion sets in when the subsystems become too large. Our method thus combines the possibility of fast response together with theoretical completeness. Other criteria for deadlock freedom, in contrast, are incomplete in principle, and so may fail to decide deadlock freedom even if unlimited computational resources are available. Also, our criterion certifies freedom from local deadlock, in which a subsystem is deadlocked while the rest of the system executes. Other criteria only certify freedom from global deadlock. We present experimental results for dining philosophers and for a multi-token-based resource allocation system, which subsumes several data arbiters and schedulers, including Milner’s token-based scheduler.

BIP is a component-based framework for system design that has important industrial applications. BIP is built on three pillars: behavior, interaction, and priority. In this paper, we introduce first-order interaction logic (FOIL) that extends BIP to systems parameterized in the number of components. We show that FOIL captures classical parameterized architectures such as token-passing rings, cliques of identical components communicating with rendezvous or broadcast, and client-server systems. Although the BIP framework includes efficient verification tools for statically-defined systems, none are available for parameterized systems with an unbounded number of components. The parameterized model checking literature contains a wealth of techniques for systems of classical architectures. However, application of these results requires a deep understanding of parameterized model checking techniques and their underlying mathematical models. To overcome these difficulties, we introduce a framework that automatically identifies parameterized model checking techniques applicable to a BIP design. To our knowledge, it is the first framework that allows one to apply prominent parameterized model checking results in a systematic way.

Abstract Architectures depict design principles: paradigms that can be understood by all, allow thinking on a higher plane and avoiding low-level mistakes. They provide means for ensuring correctness by construction by enforcing global properties characterizing the coordination between components. An architecture can be considered as an operator A that, applied to a set of components B , builds a composite component A ( B ) meeting a characteristic property Φ . Architecture composability is a basic and common problem faced by system designers. In this paper, we propose a formal and general framework for architecture composability based on an associative, commutative and idempotent architecture composition operator ⊕ . The main result is that if two architectures A 1 and A 2 enforce respectively safety properties Φ 1 and Φ 2 , the architecture A 1 ⊕ A 2 enforces the property Φ 1 ∧ Φ 2 , that is both properties are preserved by architecture composition. We also establish preservation of liveness properties by architecture composition. The presented results are illustrated by a running example and a case study.

Electronic design automation (EDA) has enabled the integrated circuit industry to sustain exponentially increasing product complexity growth until today, while maintaining consistent product development timeline and costs. We argue that the success of EDA-based design relies on the application of four interrelated principles: 1) separation of concerns implying a decomposition of a design flow into steps, each step dealing with specific aspects, namely user requirements, functional design, and implementation; 2) component-based design enabling the reasoned construction of complex systems as the composition of components; 3) semantic coherency meaning that descriptions used in successive design steps are semantically related through adequate semantic mappings; this implies, in particular, that the formalisms used at each design step are rooted in well-defined semantics; and 4) correctness by construction meaning that it is possible to guarantee essential properties of the designed system incrementally and compositionally along the design process. The paper discusses to what extent the EDA paradigm can be adapted to general mixed hardware/software (HW/SW) systems design through the application of these principles. It presents an overview of the problems raised by the rigorous system design of mixed HW/SW systems. Then, it presents a unified abstract framework for addressing these problems by identifying main research avenues.

Architectures are common means for organizing coordination between components in order to build complex systems and to make them manageable. Despite the progress of the state of the art over the past decades, there are still a lot of foundational issues that remain unsolved. In this talk we present a general framework for modeling architectures and their properties.

Rigorous System Design deals with the formalization of the design of mixed hardware/software systems. It advocates rigorous system design as a coherent and accountable model-based process leading from requirements to correct implementations. It presents the current state of the art in system design, discusses its limitations and identifies possible avenues for overcoming them. A rigorous system design flow is defined as a formal accountable and iterative process composed of steps, and based on four principles: 1) separation of concerns; 2) component-based construction; 3) semantic coherency; 4) correctness-by-construction. The combined application of these principles allows the definition of a methodology clearly identifying where human intervention and ingenuity are needed to resolve design choices, as well as activities that can be supported by tools to automate tedious and error-prone tasks. The presented view for rigorous system design has been amply implemented in the BIP (Behavior, Interaction, Priority) component framework and substantiated by numerous experimental results showing both its relevance and feasibility. Rigorous System Design concludes with a discussion advocating a system-centric vision for computing, identifying possible links with other disciplines and emphasizing centrality of system design. It is an ideal primer for researchers and practitioners interested in the design of mixed hardware/software systems.

The correct and efficient implementation of general real-time applications remains very much an open problem. A key issue is meeting timing constraints whose satisfaction depends on features of the execution platform, in particular its speed. Existing rigorous implementation techniques are applicable to specific classes of systems, for example, with periodic tasks or time-deterministic systems. We present a general model-based implementation method for real-time systems based on the use of two models: • An abstract model representing the behaviour of real-time software as a timed automaton, which describes user-defined platform-independent timing constraints. Its transitions are timeless and correspond to the execution of statements of the real-time software. • A physical model representing the behaviour of the real-time software running on a given platform. It is obtained by assigning execution times to the transitions of the abstract model. A necessary condition for implementability is time-safety, that is, any (timed) execution sequence of the physical model is also an execution sequence of the abstract model. Time-safety simply means that the platform is fast enough to meet the timing requirements. As execution times of actions are not known exactly, time-safety is checked for the worst-case execution times of actions by making an assumption of time-robustness: time-safety is preserved when the speed of the execution platform increases. We show that, as a rule, physical models are not time-robust, and that time-determinism is a sufficient condition for time-robustness. For a given piece of real-time software and an execution platform corresponding to a time-robust model, we define an execution engine that coordinates the execution of the application software so that it meets its timing constraints. Furthermore, in the case of non-robustness, the execution engine can detect violations of time-safety and stop execution. We have implemented the execution engine for BIP programs with real-time constraints and validated the implementation method for two case studies. The experimental results for a module of a robotic application show that the CPU utilisation and the size of the model are reduced compared with existing implementations. The experimental results for an adaptive video encoder also show that a lack of time-robustness may seriously degrade the performance for increasing platform execution speed.

No abstract available.

Traditional engineering disciplines such as civil or mechanical engineering are based on solid theory for building artefacts with predictable behavior over their lifetime. In contrast, we lack similar constructivity results for computing systems engineering: computer science provides only partial answers to particular system design problems. With few exceptions, predictability is impossible to guarantee at design time and therefore, a posteriori verification remains the only means for ensuring their correct operation.

Embedded systems must interact with their real-time environment in a timely and dependable fashion. Most embedded-systems architectures and design processes consider "non-functional" properties such as time, energy, and reliability as an afterthought, when functional correctness has (hopefully) been achieved. As a result, embedded systems are often fragile in their real-time behaviour, and take longer to design and test than planned. Several techniques have been proposed to make real-time embedded systems more robust, and to ease the process of designing embedded systems:

A grand challenge in complex embedded systems design is developing methods and tools for modeling and analyzing the behavior of an application software running on multicore or distributed platforms. We propose a rigorous method and a tool chain that allows to obtain a faithful model representing the behavior of a mixed hardware/software system from a model of its application software and a model of its underlying hardware architecture. The system model can be simulated and analyzed for validation of both functional and extra-functional properties. The tool chain uses DOL (Distributed Operation Layer [1]) as the frontend for specifying the application software and hardware architecture, and BIP (Behavior Interaction Priority [2]) as the modeling and analysis framework. It is illustrated through the construction of system models of MJPEG and MPEG2 decoder applications running on MPARM, a multicore architecture.

Correct and efficient implementation of general real-time applications remains by far an open problem. A key issue is meeting timing constraints whose satisfaction depends on features of the execution platform, in particular its speed. Existing rigorous implementation techniques are applicable to specific classes of systems e.g. with periodic tasks, time deterministic systems.

Although distributed systems are widely used nowadays, their implementation and deployment is still a time-consuming, error-prone, and hardly predictive task. In this paper, we propose a methodology for producing automatically efficient and correct-by-construction distributed implementations by starting from a high-level model of the application software in BIP. BIP (Behavior, Interaction, Priority) is a component-based framework with formal semantics that rely on multi-party interactions for synchronizing components. Our methodology transforms arbitrary BIP models into Send/Receive BIP models, directly implementable on distributed execution platforms. The transformation consists of (1) breaking atomicity of actions in atomic components by replacing strong synchronizations with asynchronous Send/Receive interactions; (2) inserting several distributed controllers that coordinate execution of interactions according to a user-defined partition, and (3) augmenting the model with a distributed algorithm for handling conflicts between controllers preserving observational equivalence to the initial models. Currently, it is possible to generate from Send/Receive models stand-alone C++ implementations using either TCP sockets for conventional communication, or MPI implementation, for deployment on multi-core platforms. This method is fully implemented. We report concrete results obtained under different scenarios.

We consider a compositional method for the verification of component-based systems described in a subset of the BIP language encompassing multi-party interactions. The method is based on the use of two kinds of invariants. Component invariants are over-approximations of components' reach ability sets. Interaction invariants are constraints on the states of components involved in interactions. In this paper we propose fixed point characterization for computing interaction invariants. We also propose a new technique that takes the incremental design of the system into account. In many situations, the technique will help to avoid redoing all the verification process each time an interaction is added in the design. Our two techniques have been implemented as extension of the D-Finder toolset. The result has been applied to check deadlock-freedom on several case studies. Our experiments show that our new methodology is generally much faster than existing ones.

Behavior, Interaction, Priorities (BIP) is a component framework for constructing systems from a set of atomic components by using two kinds of composition operators: interactions and priorities. In this paper, we present a method that transforms the interactions of a component-based program in BIP and generates a functionally equivalent program. The method is based on the successive application of three types of source-to-source transformations: flattening of components, flattening of connectors, and composition of atomic components. We show that the system of the transformations is confluent and terminates. By exhaustive application of the transformations, any BIP component can be transformed into an equivalent monolithic component. From this component, efficient standalone C++ code can be generated. The method combines advantages of component-based description such as clarity, incremental construction, and reasoning with the possibility to generate efficient monolithic code. It has been integrated in the design methodology for BIP and it has been successfully applied to two non trivial examples described in this paper.

Summary form only given. The development of a satisfactory Embedded Systems Design Science provides a timely challenge and opportunity for reinvigorating Computer Science. Embedded systems are components integrating software and hardware jointly and specifically designed to provide given functionalities, which are often critical. They are used in many applications areas including transport, consumer electronics and electrical appliances, energy distribution, manufacturing systems etc. Embedded systems design requires techniques taking into account extra-functional requirements regarding optimal use of resources such as time, memory and energy while ensuring autonomy, reactivity and robustness. Jointly taking into account these requirements raises a grand scientific and technical challenge extending Computer Science with paradigms and methods from Control Theory and Electrical Engineering. Computer Science is based on discrete computation models not encompassing physical time and resources which are by their nature very different from analytic models used by other engineering disciplines. We summarise some current trends in embedded systems design and point out some of their characteristics, such as the chasm between analytical and computational models and the gap between safety critical and best-effort engineering practices. We call for a coherent scientific foundation for embedded systems design, and we discuss a few key demands on such a foundation: the need for encompassing several manifestations of heterogeneity, and the need for design paradigms ensuring constructivity and adaptivity. We discuss main aspects of this challenge and associated research directions for different areas such as modelling, programming, compilers, operating systems and networks.

International audience

Autonomous robots are complex systems that require the interaction/cooperation of numerous heterogeneous software components. Nowadays, robots are critical systems and must meet safety properties including in particular temporal and real-time constraints. We present a methodology for modeling and analyzing a robotic system using the BIP component framework integrated with an existing framework and architecture, the LAAS Architecture for Autonomous System, based on Geno

We provide an algebraic formalization of connectors in the BIP component framework. A connector relates a set of typed ports. Types are used to describe different modes of synchronization: rendezvous and broadcast, in particular. Connectors on a set of ports P are modeled as terms of the algebra AC(P), generated from P by using a binary fusion operator and a unary typing operator. Typing associates with terms (ports or connectors) synchronization types --- trigger or synchron --- that determine modes of synchronization. Broadcast interactions are initiated by triggers. Rendezvous is a maximal interaction of a connector including only synchrons. The semantics of AC(P) associates with a connector the set of its interactions. It induces on connectors an equivalence relation which is not a congruence as it is not stable for fusion. We provide a number of properties of AC(P) used to symbolically simplify and handle connectors. We provide examples illustrating applications of AC(P), including a general component model encompassing synchrony, methods for incremental model decomposition, and efficient implementation by using symbolic techniques.

We provide an algebraic formalisation of connectors in BIP. These are used to structure interactions in a component-based system. A connector relates a set of typed ports. Types are used to describe different modes of synchronisation: rendezvous and broadcast, in particular.

We present a quality management method for multimedia applications. The method takes as input an application software composed of actions. The execution times of actions are unknown increasing junctions of quality level parameters. The method allows the construction of a quality manager which computes adequate action quality levels so as to meet QoS requirements for a given platform. These include deadlines for the actions as well as quality maximization and smoothness. We extend and improve results of a previous paper by focusing on the reduction of overhead due to quality management. We propose a symbolic quality management method using speed diagrams, a representation of the system's dynamics. Instead of numerically computing a quality level for each action, the quality manager changes action quality levels based on the knowledge of constraints characterizing control relaxation regions. These are sets of states in which quality management for a given number of steps can be relaxed without degrading quality. We provide experimental results for quality management of an MPEG encoder, in particular performance benchmarks for both numeric and symbolic quality management.

We apply a model construction methodology to TinyOS- based networks, using the behavior-interaction-priority (BIP) component framework. The methodology consists in building the model of a node as the composition of a model extracted from a nesC program describing the application, and models of TinyOS components. Models for networks are obtained by composition of models for nodes by using BIP connectors implementing different types of radio chan- nels. This opens the way for enhanced analysis and early error detection by using verification techniques.

Summary form only given. We present a framework for the component-based construction of embedded systems. The framework is based on a general semantic model, encompassing various models of computation for real-time systems. It is characterized by the combined use of models for behavior, interaction and dynamic priorities. Interaction models describe interactions between components by using connectors with synchronization types. Dynamic priorities are used to specify controllers and schedulers in particular. We also present a methodology for model-based composition of real-time systems using this semantic model. The methodology enables correct-by-construction development for properties such as deadlock-freedom and progress, as well as incremental construction and associativity of composition operators. We present two implementations of the framework in system modeling and validation tools developed at Verimag: 1) A partial implementation in the state exploration platform of the IF tool suite dedicated to the validation of asynchronous system modeling languages such as UML and SDL; 2) A more recent full implementation in a platform for the execution of both synchronous and asynchronous components. The methodology is illustrated by the use of these tools on case studies for real-time systems modeling and validation

We present a methodology for modeling heterogeneous real-time components. Components are obtained as the superposition of three layers: behavior, specified as a set of transitions; Interactions between transitions of the behavior; Priorities, used to choose amongst possible interactions. A parameterized binary composition operator is used to compose components layer by layer. We present the BIP language for the description and composition of layered components as well as associated tools for executing and analyzing components on a dedicated platform. The language provides a powerful mechanism for structuring interactions involving rendezvous and broadcast. We show that synchronous and timed systems are particular classes of components. Finally, we provide examples and compare the BIP framework to existing ones for heterogeneous component-based modeling

We propose a method for fine grain QoS control of dataflow applications. We assume that the application software is described as the composition of actions (C-functions) with quality level parameters. The method allows a QoS controller to be computed from this description, and also average execution times, worst case execution times and deadlines for its actions. The controller computes dynamically feasible schedules and quality assignments for their actions. Furthermore, the control policy ensures optimal time budget utilization. A prototype tool implementing the method is shown, as well as experimental results for a non trivial example. The results show the interest of fine grain QoS control for video encoders.

We propose a method for fine grain QoS control of real-time applications. The method allows adapting the overall system behavior by adequately setting the quality level parameters of its actions. The objective of the control policy is to meet QoS requirements including three types of properties: 1) safety that is, no deadline is missed; 2) optimality that is, maximization of the available time budget; 3) smoothness of quality levels. The method takes as input a model of the application software, QoS requirements and platform-dependent timing information, and produces a controlled application software meeting the QoS requirements on the target platform. This paper provides a complete formalization of the quality control problem. It proposes a new control management policy ensuring safety, near-optimality and smoothness. It also describes a prototype tool implementing the quality control algorithm and experimental results about its application to a video encoder.

We present an overview of results developed mainly at Verimag, by the author and his colleagues, on a framework for component-based construction, characterized by the following: the behavior of atomic components is represented by transition systems; components are built from a set of atomic components by using "glue" operators; for each component, it is possible to separate its behavior from its structure, due to specific properties of glue operators. We show an instance of this framework, which combines two independent classes of glue operators, interaction models and priorities. The combination of interaction models and priorities is expressive enough to encompass heterogeneous interaction and execution. We show that separation between behavior and structure is instrumental for correctness-by-construction. Finally, we discuss new research problems related to a structure-dependent notion of expressiveness.

The design of embedded real-time systems requires skills from multiple specific disciplines, including, but not limited to, control, computer science, and electronics. This often involves experts from differing backgrounds, who do not recognize that they address similar, if not identical, issues from complementary angles. Design methodologies are lacking in rigor and discipline so that demonstrating correctness of an embedded design, if at all possible, is a very expensive proposition that may delay significantly the introduction of a critical product. While the economic importance of embedded systems is widely acknowledged, academia has not paid enough attention to the education of a community of high-quality embedded system designers, an obvious difficulty being the need of interdisciplinarity in a period where specialization has been the target of most education systems. This paper presents the reflections that took place in the European Network of Excellence Artist leading us to propose principles and structured contents for building curricula on embedded software and systems.

Modeling real-time systems raises non trivial problems for the definition of usable modeling languages and the application of model-based development approaches. We identify key problems and present corresponding research directions for the incremental construction of timed models for real-time systems. We present a framework that may provide some solutions and an associated methodology for model construction. Timed models of real-time systems are obtained by adding timing constraints to their application software. These constraints take into account execution times of atomic statements, the dynamics of the external environment, as well as quality of service requirements. The framework combines two kinds of composition operators for timed components: x Restriction operators which are unary operators parameterized by a safety property. Their application on a component restricts its behavior so as to meet the associated property. Dynamic priorities correspond to a class of restriction operators which preserve deadlockfreedom of their arguments. x Parallel composition operators, parameterized by interaction models. These models describe interactions between actions offered by the composed components and their associated synchronization requirements. We show that the combination of parallel composition and restriction operators allows compositional modeling of real-time systems, in particular of aspects related to heterogeneous interaction and execution, resource sharing and scheduling. Scheduling policies are modeled by dynamic priorities. The framework supports composition of scheduling policies and provides compositionality and composability results for deadlock-freedom of scheduled systems. We show applications of these results, including model-based development of applications in Esterel and real-time Java, as well as a partial implementation of the framework in Verimag’s IF toolset.

We present a methodology for building timed models of real-time systems by adding time constraints to their application software. The applied constraints take into account execution times of atomic statements, the behavior of the system's external environment, and scheduling policies. The timed models of the application obtained in this manner can be analyzed by using time analysis techniques to check relevant real-time properties. We show an instance of the methodology developed in the TAXYS project for the modeling and analysis of real-time systems programmed in the Esterel language. This language has been extended to describe, by using pragmas, time constraints characterizing the execution platform and the external environment. An analyzable timed model of the real-time system is produced by composing instrumented C-code generated by the compiler. The latter has been re-engineered in order to take into account the pragmas. Finally, we report on applications of TAXYS to several nontrivial examples.

We present a tool for the design and validation of embedded real time applications. The tool integrates two approaches: the use of the synchronous programming language, ESTEREL for design, and the application of model checking techniques for validation of real time properties. Validation is carried out on a global formal model (timed automata) taking into account the effective implementation of the application on the target hardware architecture as well as its external environment behavior.

We present a framework integrating specification and scheduler generation for real time systems. In a first step, the system, which can include arbitrarily designed tasks (cyclic or sporadic, with or without precedence constraints, any number of resources and CPUs) is specified as a timed Petri net. In a second step, our tool generates the most general non preemptive online scheduler for the specification, using a controller synthesis technique.

We present a general framework for the formal specification and algorithmic analysis of hybrid systems. A hybrid system consists of a discrete program with an analog environment. We model hybrid systems as finite automata equipped with variables that evolve continuously with time according to dynamical laws. For verification purposes, we restrict ourselves to linear hybrid systems, where all variables follow piecewise-linear trajectories. We provide decidability and undecidability results for classes of linear hybrid systems, and we show that standard program-analysis techniques can be adapted to linear hybrid systems. In particular, we consider symbolic model-checking and minimization procedures that are based on the reachability analysis of an infinite state space. The procedures iteratively compute state sets that are definable as unions of convex polyhedra in multidimensional real space. We also present approximation techniques for dealing with systems for which the iterative procedures do not converge.

We describe finite-state programs over real-numbered time in a guarded-command language with real-valued clocks or, equivalently, as finite automata with real-valued clocks. Model checking answers the question which states of a real-time program satisfy a branching-time specification (given in an extension of CTL with clock variables). We develop an algorithm that computes this set of states symbolically as a fixpoint of a functional on state predicates, without constructing the state space. For this purpose, we introduce a μ-calculus on computation trees over real-numbered time. Unfortunately, many standard program properties, such as response for all nonzeno execution sequences (during which time diverges), cannot be characterized by fixpoints: we show that the expressiveness of the timed μ-calculus is incomparable to the expressiveness of timed CTL. Fortunately, this result does not impair the symbolic verification of "implementable" real-time programs-those whose safety constraints are machine-closed with respect to diverging time and whose fairness constraints are restricted to finite upper bounds on clock values. All timed CTL properties of such programs are shown to be computable as finitely approximable fixpoints in a simple decidable theory.

The verification problem for real-time properties involving duration constraints (predicates) is addressed. The duration of a state property, along an interval of a computation sequence of a real-time system, is the time the property is true. In particular, the global time spent in such an interval is the duration of the formula 'true'. The real-time logic TCTL is extended to a duration logic called SDTL in which duration constraints can be expressed. The problem of the verification of SDTL formulas with respect to a class of timed models of reactive systems is investigated. New model checking procedures are proposed for the most significant properties expressible in SDTL, including eventuality and invariance properties. Such results are provided for the two cases of discrete and dense time.>

This paper presents the tools ALDEBARAN, CESAR, CESAR.ADT and CLEOPATRE which constitute a tool- box for compiling and verifying LOTOS programs. The principles of these tools are described, as well as their performances and limitations. Finally, the formal verification of the ret/REL atomic multicast protocol is given as an example to illustrate the practical use of the tool- box.

Finite-state programs over real-numbered time in a guarded-command language with real-valued clocks are described. Model checking answers the question of which states of a real-time program satisfy a branching-time specification. An algorithm that computes this set of states symbolically as a fixpoint of a functional on state predicates, without constructing the state space, is given.>

A method for the implementation and analysis of real-time systems, based on the compilation of specification extended automata is proposed. The method is illustrated for a simple specification language that can be viewed as the extension of a language for the description of systems of communicating processes, by adding timeout and watchdog constructs. The main result is that such a language can be compiled into timed automata, which are extended automata with timers. Timers are special state variables that can be set to zero by transitions, and whose values measure the time elapsed since their last reset. Timed automata do not make any assumption about the nature of time and adopt an event-driven execution mode. Their complexity does not depend on the values of the parameters of timeouts and watchdogs used in specifications. These features allow the application on timed automata of efficient code generation and analysis techniques. In particular, it is shown how symbolic model-checking of real-time properties can be directly applied to this model.>

In this paper, we propose a notion of fairness for transition systems and a logic for proving properties under the fairness assumption corresponding to this notion. We consider that the concept of fairness which is useful is "fair reachability" of a given set of states P in a system, i.e. reachability of states of P when considering only the computations such that if, during their execution, reaching states of P is possible infinitely often, then states of P are visited infinitely often. This definition of fairness suggests the introduction of a branching time logic FCL, the temporal operators of which express, for a given set of states P, the modalities "it is possible that P" and "it is inevitable that P" by considering fair reachability of P. The main result is that, given a transition system S and a formula f of FCL expressing some property of S under the assumption of fairness, there exists a formula f′ belonging to a branching time logic CL such that : f is valid for S in FCL iff f′ is valid for S in CL. This result shows that proving a property under the assumption of fairness is equivalent to proving some other property without this assumption and that the study of FCL can be made via the "unfair" logic CL, easier to study and for which several results already exist.

We suggest a methodology and a language to permit the study of a system's behavior (functional validation, evaluation of global performances, critical situations). Every system is regarded as an interconnection of communicating modules functioning in a synchronous or asynchronous manner. The control section and the data section of each module are described separately in terms of respectively non-procedural and procedural sub-languages.