Search

In recent years, opacity has received increasing attention in terms of analyzing security and privacy problems. Opacity is a confidentiality property that characterizes a system's ability to hide its secret information from any external intruders. A systematic overview of opacity in the context of discrete event systems (DESs) was conducted; this paper firstly reviews the verification methods and computational complexity of the opacity in DESs using the formalisms of automata and Petri nets. When the system is verified to be non-opaque, the approaches that synthesize an opaque system are summarized. Finally, the future research directions and open problems of opacity in DES are also reviewed.

Deadlock is an undesired situation in multithreaded software since it can lead to the stoppage of software. This paper studies the problem of deadlock control of multithreaded software based on Gadara nets, which are well studied for modelling concurrent programs. In particular, an iterative deadlock prevention policy based on siphons is proposed for a class of ordinary Gadara nets where the initial marking of each idle place is one. At each iteration, we compute emptiable siphons containing the smallest number of resource places. Then, bad markings are computed based on these siphons. On the basis of the bad markings, a constraint is constructed that forbids not only bad markings that empty one of the siphons but also some other bad markings. The algorithm is carried out until no emptiable siphon exists in the net. Compared with the existing methods, the resultant net derived from the proposed method is live and maximally permissive with a simpler supervisor. Finally, two examples are provided to illustrate the proposed deadlock prevention policy.

This paper focuses on establishing a Petri net (PN)-based deadlock prevention policy for large-scale systems whose state spaces are prone to the explosion problem phenomenon. When using the reachability analysis technique, the main burden is that the number of states grows exponentially with respect to the PN structure and, thereby, synthesizing a lively controlled Petri net model (PNM) becomes an extremely complex procedure. The proposed method reduces the initial marking of the PNM to reduce the size of the reachability graph. Such a reachability graph is reduced exponentially and the activity places are derived iteratively using a well-established invariant-based control method. When the PNM becomes live, the control places are integrated to the original PNM and, therefore, the advantage of this method lies in that the control of the original PN model starts at an earlier stage, i.e., before enumerating the full reachability graph and which we call it one-step control-ahead of a PNM. Compared with the existing methods, the new method requires the control of a very small-sized reachability graph and, therefore, it is convenient for largescale and bounded PNs. Two examples are used to illustrate the proposed approach. Experimental results show that we can obtain optimal supervisors for the net models.

A deluge of approaches has been proposed to implement and deploy a computationally effective and maximally permissive liveness-enforcing supervisor for sequential resource allocation systems (RASs). However, they are stalled by the computational complexity of a large state space that grows exponentially with respect to the size of an underlying RAS. The attention of this work is restricted to a special class of RASs: Disjunctive/Single-unit (D/SU)-RASs. Given an initial resource configuration of a D/SU-RAS, a complete state enumeration can be obtained through pure algebraic operations on this configuration with the pre-computed initial basis state space. When an explicit and complete enumeration of reachable states is impossible (due to the limited memory and storage space), we propose the exact number of reachable states. In this case, given a state vector, its reachability can be decided by an algebraic method. Experimental studies demonstrate the efficiency of the proposed approach.