Search

As an information-flow privacy property, opacity characterizes whether a malicious external observer (referred to as an intruder) is able to infer the secret behavior of a system. This paper addresses the problem of opacity enforcement using edit functions in discrete event systems modeled by partially observed deterministic finite automata. A defender uses the edit function as an interface at the output of a system to manipulate actual observations through insertion, substitution, and deletion operations so that the intruder will be prevented from inferring the secret behavior of the system. Unlike existing work which usually assumes that the observation capabilities of the intruder and the defender are identical, we consider a more general setting where they may observe incomparable subsets of events generated by the system.To characterize whether the defender has the ability to enforce opacity of the system under this setting, the notion of \emph{$ic$-enforceability} is introduced. Then, the opacity enforcement problem is transformed to a two-player game, with imperfect information between the system and the defender, which can be used to determine a feasible decision-making strategy for the defender. Within the game scheme, an edit mechanism is constructed to enumerate all feasible edit actions following system behavior. We further show that an $ic$-enforcing edit function (if one exists) can be synthesized from the edit mechanism to enforce opacity.

In this paper, we consider partially observable timed automata endowed with a single clock. A time interval is associated with each transition specifying at which clock values it may occur. In addition, a resetting condition associated to a transition specifies how the clock value is updated upon its occurrence. This work deals with the estimation of the current state given a timed observation, i.e., a succession of pairs of an observable event and the time instant at which the event has occurred. The problem of state reachability in the timed automaton is reduced to the reachability analysis of the associated zone automaton, which provides a purely discrete event description of the behaviour of the timed automaton. An algorithm is formulated to provide an offline approach for state estimation of a timed automaton based on the assumption that the clock is reset upon the occurrence of each observable transition., Comment: This is the arXiv version of a manuscript that has been conditionally accepted for publication in the IEEE Transactions on Automatic Control in 2023

Deep networks can usually depend on extracting more structural information to improve denoising results. However, they may ignore correlation between pixels from an image to pursue better denoising performance. Window transformer can use long- and short-distance modeling to interact pixels to address mentioned problem. To make a tradeoff between distance modeling and denoising time, we propose a heterogeneous window transformer (HWformer) for image denoising. HWformer first designs heterogeneous global windows to capture global context information for improving denoising effects. To build a bridge between long and short-distance modeling, global windows are horizontally and vertically shifted to facilitate diversified information without increasing denoising time. To prevent the information loss phenomenon of independent patches, sparse idea is guided a feed-forward network to extract local information of neighboring patches. The proposed HWformer only takes 30% of popular Restormer in terms of denoising time.

This paper studies the problem of increasing the connectivity of an ad-hoc peer-to-peer network subject to cyber-attacks targeting the agents in the network. The adopted strategy involves the design of local interaction rules for the agents to locally modify the graph topology by adding and removing links with neighbors. Two distributed protocols are presented to boost the algebraic connectivity of the network graph beyond $k-2\sqrt{k-1}$ where $k\in \mathbb{N}$ is a free design parameter; these two protocols are achieved through the distributed construction of random (approximate) regular graphs. One protocol leverages coordinated actions between pairs of neighboring agents and is mathematically proven to converge to the desired graph topology. The other protocol relies solely on the uncoordinated actions of individual agents and it is validated by a spectral analysis through Monte-Carlo simulations. Numerical simulations offer a comparative analysis with other state-of-the-art algorithms, showing the ability of both proposed protocols to maintain high levels of connectivity despite attacks carried out with full knowledge of the network structure, and highlighting their superior performance.

In this paper, we investigate the verification and enforcement of strong state-based opacity (SBO) in discrete-event systems modeled as partially-observed (nondeterministic) finite-state automata, including strong K-step opacity (K-SSO), strong current-state opacity (SCSO), strong initial-state opacity (SISO), and strong infinite-step opacity (Inf-SSO). They are stronger versions of four widely-studied standard opacity notions, respectively. We firstly propose a new notion of K-SSO, and then we construct a concurrent-composition structure that is a variant of our previously-proposed one to verify it. Based on this structure, a verification algorithm for the proposed notion of K-SSO is designed. Also, an upper bound on K in the proposed K-SSO is derived. Secondly, we propose a distinctive opacity-enforcement mechanism that has better scalability than the existing ones (such as supervisory control). The basic philosophy of this new mechanism is choosing a subset of controllable transitions to disable before an original system starts to run in order to cut off all its runs that violate a notion of strong SBO of interest. Accordingly, the algorithms for enforcing the above-mentioned four notions of strong SBO are designed using the proposed two concurrent-composition structures. In particular, the designed algorithm for enforcing Inf-SSO has lower time complexity than the existing one in the literature, and does not depend on any assumption. Finally, we illustrate the applications of the designed algorithms using examples., Comment: 30 pages, 20 figures, partial results in Section 3 were presented at IEEE Conference on Decision and Control, 2022. arXiv admin note: text overlap with arXiv:2204.04698

Opacity is a property that captures security concerns in cyber-physical systems and its verification plays a significant role. This paper investigates the verifications of K-step and infinite-step weak and strong opacity for partially observed nondeterministic finite state automata. K-step weak opacity is checked by constructing, for some states in the observer, appropriate state-trees, to propose a necessary and sufficient condition. Based on the relation between K-step weak and infinite-step weak opacity, a condition that determines when a system is not infinite-step weak opaque is presented. Regarding K-step and infinite-step strong opacity, we develop a secret-involved projected automaton, based on which we construct secret-unvisited state trees to derive a necessary and sufficient condition for K-step strong opacity. Furthermore, an algorithm is reported to compute a verifier that can be used to obtain a necessary and sufficient condition for infinite-step strong opacity. It is argued that, in some particular cases, the proposed methods achieve reduced complexity compared with the state of the art.

Inspired by privacy problems where the behavior of a system should not be revealed to an external curious observer, we investigate event concealment and concealability enforcement in discrete event systems modeled as non-deterministic finite automata under partial observation. Given a subset of secret events in a given system, concealability holds if the occurrence of all secret events remains hidden to a curious observer (an eavesdropper). A secret event is said to be (at least under some executions) unconcealable (inferable) if its occurrence can be indirectly determined with certainty after a finite number of observations. When concealability of a system does not hold (i.e., one or more secret events are unconcealable), we analyze how a defender, placed at the interface of the system with the eavesdropper, can be used to enforce concealability. The defender takes as input each observed event of the system and outputs a carefully modified event sequence (seen by the eavesdropper) using event deletion, insertion, or replacement. The defender is said to be C-enforceable if, following the occurrence of the secret events and regardless of subsequent activity generated by the system, it can always deploy a strategy to manipulate observations and conceal the events perpetually. We discuss systematic procedures to detect the presence of unconcealable secret events and verify C-Enforceability using techniques from state estimation and event diagnosis. We also propose a polynomial complexity construction for obtaining one necessary and one sufficient condition for C-Enforceability.

In this paper, we revisit the verification of strong K-step opacity (K-SSO) for partially-observed discrete-event systems modeled as nondeterministic finite-state automata. As a stronger version of the standard K-step opacity, K-SSO requires that an intruder cannot make sure whether or not a secret state has been visited within the last K observable steps. To efficiently verify K-SSO, we propose a new concurrent-composition structure, which is a variant of our previously- proposed one. Based on this new structure, we design an algorithm for deciding K-SSO and prove that the proposed algorithm not only reduces the time complexity of the existing algorithms, but also does not depend on the value of K. Furthermore, a new upper bound on the value of K in K-SSO is derived, which also reduces the existing upper bound on K in the literature. Finally, we illustrate the proposed algorithm by a simple example., Comment: 6 pages, 2 figures, submitted to IEEE CDC on March 28, 2022

Opacity, as an important property in information-flow security, characterizes the ability of a system to keep some secret information from an intruder. In discrete-event systems, based on a standard setting in which an intruder has the complete knowledge of the system's structure, the standard versions of current-state opacity and initial-state opacity cannot perfectly characterize high-level privacy requirements. To overcome such a limitation, in this paper we propose two stronger versions of opacity in partially-observed discrete-event systems, called \emph{strong current-state opacity} and \emph{strong initial-state opacity}. Strong current-state opacity describes that an intruder never makes for sure whether a system is in a secret state at the current time, that is, if a system satisfies this property, then for each run of the system ended by a secret state, there exists a non-secret run whose observation is the same as that of the previous run. Strong initial-state opacity captures that the visit of a secret state at the initial time cannot be inferred by an intruder at any instant. Specifically, a system is said to be strongly initial-state opaque if for each run starting from a secret state, there exists a non-secret run of the system that has the same observation as the previous run has. To verify these two properties, we propose two information structures using a novel concurrent-composition technique, which has exponential-time complexity $O(|X|^4|\Sigma_o||\Sigma_{uo}||\Sigma|2^{|X|})$, where $|X|$ (resp., $|\Sigma|$, $|\Sigma_o|$, $|\Sigma_{uo}|$) is the number of states (resp., events, observable events, unobservable events) of a system., Comment: 10 pages, 11 figures