Search

The proliferation of Internet of Things (IoT) devices has led to many applications, including smart homes, smart cities and smart industrial control systems. Attacks like Distributed Denial of Service, event control hijacking, spoofing, event replay and zero day attacks are prevalent in smart environments. Conventional Network Intrusion Detection Systems (NIDSs) are tedious to deploy in the smart environment because of numerous communication architectures, manufacturer policies, technologies, standards and application-specific services. To overcome these challenges, we modeled the operational behavior of IoT network events using timed ACs and proposed a novel hybrid NIDS in this paper. A web server is integrated with IoT devices for remote access, and Constrained Application Protocol is employed in inter- and intra-smart device communication. Experiments are conducted in real time to validate our proposal and achieve 99.17% detection accuracy and 0.01% false positives. [ABSTRACT FROM AUTHOR]

Stream processing platforms allow processing and analyzing realtime data. A recognized system for this purpose is the so-called Storm platform, an open-source system for distributed computing, which is a scalable, fast and, fault-tolerant. The Storm platform may be deployed on a large number of processors. However, determining the proper number of processors that are suitable to execute a given Storm based software application is a challenging task, especially if the application is intended to serve a very large user community. One way of solving this is by employing a simulation model that allows the evaluation of its performance under different workload scenarios. In this paper, a simulation model of a Storm application using the DEVS formalism is presented, then, an equivalent model is described using Timed Automata (TA). Throughout a procedure called "Bisimulation", it is checked that both models are effectively equivalent. Finally, the model defined using TA is formally verified evaluating its properties, proving that the simulation model has the same behavior as the real applications. [ABSTRACT FROM AUTHOR]

For real-time simulations, the fidelity of simulation depends not only on the functional accuracy of simulation but also on its timeliness. It is helpful for simulation designers if they can analyze and verify that a simulation will always meet its timing requirements without unnecessarily sacrificing functional accuracy. Abstracting the simulated processes simply as software tasks allows us to transform the problem of verifying timeliness into a schedulability analysis problem where tasks are checked as to whether they are schedulable under the timing constraints or not. In this paper we extend a timed automaton-based framework due to Fersman and Yi for schedulability analysis of real-time systems, for the special case of real-time multiframe cosimulations. To the best of our knowledge, this work is the first to analyze the schedulability of single- or multiframe real-time simulations. We found that there are some special requirements posed by multiframe simulations, which necessitate changes and improvements in the existing framework designed for actual real-time systems. We made the required theoretical extensions to the framework and implemented our extended framework in UPPAAL, a tool for modeling, simulation, and verification of real-time systems modeled as timed automata. The functional correctness and resource requirements of the implemented framework are then demonstrated using simple examples. [ABSTRACT FROM AUTHOR]

In this paper, we adapt lazy abstraction with interpolants for reachability analysis of timed automaton. It involves computing an abstract reachability tree whose nodes are labeled by a location and a given set of predicates. The set of predicates over-approximates the reachable clock valuations of the corresponding location, and the approximation is refined when a spurious counterexample appears. A more precise approximation usually contains fewer spurious counterexamples that require refinement, but as a result it may delay the convergence of the algorithm. The state-of-the-art lazy abstraction algorithms employ interpolants to produce an approximation that is closer to the actual reachable clock valuation to eliminate the spurious errors. However, interpolant also cannot ensure the quality of the resulting approximation, as it blindly relies on the SMT solver. In order to produce optimal approximation, we assign to each node a maximal lower and upper bounds (LU-bounds) function to produce a node-specific LU-bounds abstraction; the abstraction can further over-approximate the reachable clock valuations without introducing extra spurious counterexamples. Furthermore, in our algorithm, LU-bounds are refined only when a spurious counterexample occurs. Hence, only those clock valuations that lead to error nodes are excluded. An alternative benefit of the LU-bounds abstraction is that it ensures that the abstraction-refinement loop terminates. © 2015 Institute of Electrical Engineers of Japan. Published by John Wiley & Sons, Inc. [ABSTRACT FROM AUTHOR]

We focus on the control and the synthesis of secure timed systems which are modelled as timed automata. The security property that the system must satisfy is anon-interferenceproperty. Intuitively, non-interference ensures the absence of any causal dependency from a high-level domain to a lower level domain. Various notions of non-interference have been defined in the literature, and in this paper, we focus onstrong non-deterministic non-interference(SNNI) and two (bi)simulation-based variants thereof (cosimulation-based SNNI and bisimulation-based SNNI). These properties and their extensions have been mostly studied in the context of discrete event systems, while it is now well-known that time is an important attack vector against secure systems. At the same time, there is an obvious interest in going beyond simple verification to control problems: to be able to automatically make systems secure. We consider non-interference properties in the challenging setting of control of dense-time systems specified bytimed automataand we study the two following problems: (1) check whether it is possible to find a sub-system so that it is non-interferent; if yes, (2) compute a (largest) sub-system which is non-interferent. We exhibit decidable sub-classes for these problems, assess their theoretical complexities and provide effective algorithms based on the classical framework of timed games. [ABSTRACT FROM AUTHOR]

Nowadays medical software is tightly coupled with medical devices that perform patient state monitoring and lately even some basic treatment procedures. Medical guidelines (GLs) can be seen as specification of a medical system which requires their computer-interpretable representation of medical GLs. Until now most of the medical GLs are often represented in a textual format and therefore often suffer from such structural problems as incompleteness, inconsistencies, ambiguity and redundancy, which makes the translation process to the machine-interpretable language more complicated. Computer-based interpretation of GLs can improve the quality of protocols as well as the quality of medical service. Several GLs formal representation methods have been presented recently. Only some of them enable automatic formal verification by introducing an additional translation path to the existing model checking environments. However, if a verified property fails it is difficult to trace back the result needed to change the model. Moreover, these formalisms provide the notion of time mostly in terms of actions order. In this paper we preset the application of a well-know formal behaviour representation approach of embedded systems design domain to medical GLs interpretation. We use Timed Automata extended with Tasks (TAT) and TIMES toolbox to represent medical GLs as a system behaviour in a computer interpretable form. We discuss the verification issues with the help of the anticancer drug imatinib case study. [ABSTRACT FROM AUTHOR]

For the complex systems, the development of a methodology of fault diagnosis is important. Indeed, for such systems, an efficient diagnosis contributes to the improvement of the availability, the growth of production, and, of course, the reduction of maintenance costs. It is a key action in the improvement of performance of industrial feature. This paper proposes a new approach to diagnose complex systems modeled by communicating timed automata. Each component has been modeled separately by a timed automaton integrating various operating modes while the communication between the various components is carried out by the control module. Starting from each module of the complex system, a single deterministic automaton, called a diagnoser, is constructed that uses observable events to detect the occurrence of a failure. This modeling formalism provides means for formal verification of the complex system model and its diagnoser. The model-checking methods are used to check correctness properties. The steps of the method are described by an algorithm and illustrated through a batch neutralization process. The implementation of the algorithm is also discussed. [ABSTRACT FROM AUTHOR]

Abstract: To overcome the sky-rocketing verification cost of embedded software, symbolic model-checking technology of dense-time automata has been proposed as an automated solution. The construction of a timed precondition is a central component in the technology. The general formulation for a timed precondition operator needs to check the continuity of time progress and usually results in high complexity in the construction. However, when the state space characterized by the path condition is convex, we can use a more efficient convex timed precondition operator. In this work, we discuss the concept of time-convexity that allows us to relax the restrictions on the application of the convex timed precondition operator in place of the general one. We present examples in model-checking that engender a non-time-convex space of time progress. Nevertheless, we have also identified a class of timed computation tree logic (TCTL) formulas that only characterize time-convex state spaces. This class includes several important types of TCTL formulas, including some timed inevitabilities with deadlines. We then present a new formulation for the efficient evaluation of general timed inevitabilities with non-time-convex path conditions. The new formulation also leads to a new technique for the approximate evaluation of timed inevitabilities with better precision. Finally, we report our implementation and experiments. [Copyright &y& Elsevier]

Abstract: We show that max-plus polyhedra are usable as a data structure in reachability analysis of timed automata. Drawing inspiration from the extensive work that has been done on difference bound matrices, as well as previous work on max-plus polyhedra in other areas, we develop the algorithms needed to perform forward and backward reachability analysis using max-plus polyhedra. To show that the approach works in practice and theory alike, we have created a proof-of-concept implementation on top of the model checker opaal. [Copyright &y& Elsevier]

Possibilities of reduction of the number of time variables in a timed automaton used for synchronization of components in physical systems, for example, lasers are investigated. Reduction of the number of time variables allows problems of testing of the components for compliance with requirement specification to be simplified. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we study the complexity of model-checking formulas of four important real-time logics (, and ) over restricted sets of timed paths. The classes of restricted sets of timed paths that we consider are (i) a single finite (or ultimately periodic) timed path, (ii) an infinite set of finite (or infinite) timed paths defined by a finite (or ultimately periodic) path in a region graph, (iii) an infinite set of finite (or infinite) timed paths defined by a finite (or ultimately periodic) path in a zone graph. Several results are quite negative: and remain undecidable along region- and zone-paths. On the other hand, we obtained PTIME algorithms for model-checking along a region path, and for along a single timed path. [Copyright &y& Elsevier]

This paper concerns the modelling and diagnosis of discrete-event systems. The timed automaton is used as a discrete-event representation of such systems. The diagnosis is based on the investigation whether the measured input and output sequences are consistent with the timed automaton. The paper describes how the timed automaton can be obtained by qualitative identification using a set of measurement data and how it can be used together with the diagnostic algorithm to detect and identify faults. An important aspect of this method is the decomposition of the diagnostic system into the model and diagnostic algorithm which makes it possible to use the same algorithm for different systems by simply exchanging the model. The results are applied to industrial actuators. [ABSTRACT FROM AUTHOR]

The general theory of randomly timed automata is developed: starting with the practical motivation and presentation of the envisaged notion, the categorical theory of minimization, aggregation, encapsulation, interconnection and realization of such automata is worked out. All these constructions are presented universally: minimization and realization as adjunctions, aggregation as product, interconnection as cartesian lifting, and encapsulation as co-cartesian lifting. Stochastic timed automata are shown to be a particular case of randomly timed automata. The notion of stochastic timed automaton is shown to be too restrictive to establish a self contained theory of combination and realization. [Copyright &y& Elsevier]

Real-time systems interact with their environment using time constrained input/output signals. Examples of real-time systems include patient monitoring systems, and telecommunication systems, anct-tetecommunication systems. For such systems a functional misbehavior or a deviation from the specified time constraints may have catastrophic consequences [27]. Therefore, ensuring the correctness of real-time systems becomes necessary. Two different techniques are usually used to cope with the correctness of a software system prior to its deployment, namely, verification and testing. In this paper, we address the issue of testing real-time software systems specified as a Timed Input Output Automaton (TIOA). TIOA is a variant of timed automaton [1], [2], [22], [29]. We introduce the syntax and semantics of TIOA. We present the potential faults that can be encountered in a timed system implementation. We study these different faults based on TIOA model and look at their effects on the execution of the system using the region graph. We present a method for generating timed test cases. This method is based on a state characterization technique and consists of the following three steps: First, we sample the region graph using a suitable granularity, in order to construct a subautomaton easily testable, called Grid Automaton. Then, we transform the Grid Automaton into a Nondeterministic Timed Finite State Machine (NTFSM). Finally, we adapt the Generalized Wp-method [23] to generate timed test cases from NTFSM. We assess the fault coverage of our test cases generation method and prove its ability to detect all the possible faults. Throughout the paper, we use examples to illustrate the various concepts and techniques used in our approach. [ABSTRACT FROM AUTHOR]

Cyber–Physical Production Systems (CPPSs) are hybrid systems composed of a discrete and continuous part. However, most of the applied machine learning algorithms handle the dynamics of the two parts separately and in different fashions: for the discrete part, the notion of discrete events (and their timings) is essential (e.g. when learning automata or rules), while the dynamics of the continuous part is often defined by differential equations or time-series models. Reconciling the different nature of the two is a major challenge for machine learning. One solution is to express continuous behavior in discrete terms, i.e. the explicit events are extracted. Then, at the cost of information loss caused by discretization, the overall behavior can be jointly analyzed. This paper proposes a novel machine learning discretization approach called DENTA (Deep Network Timed Automaton) which solves the aforementioned challenges through the construction of an (overall) deterministic timed automaton from the original hybrid data. First, it hierarchically extracts new features from the continuous data using a deep network of stacked restricted Boltzmann machines (RBMs). We show that high-level RBM abstractions can further be used to automatically detect meaningful discrete events in continuous system behavior. Finally, a discrete representation of overall system behavior in the form of a timed automaton is created, which allows a joint timing analysis of the whole system. The model is verified by the anomaly detection on a synthetic and a real-world dataset and the results show clear advantages of the approach for a specific class of systems. [ABSTRACT FROM AUTHOR]