Partial Information Decomposition (PID) represents multivariate mutual information via antichain-lattice that aims to specify which source groups can recover which informational components of a target. For three or more sources, widely desired PID axioms become mutually incompatible. This is often treated as an axiomatic tuning issue. This paper argues that the obstruction is representational, rooted in the antichain indexing itself, so that purely axiomatic adjustments within an antichain-lattice structure cannot resolve it in general. We first introduce System Information Decomposition (SID) for the special target-free three-variable setting, obtaining a self-consistent entropy decomposition with an operational redundancy definition. More fundamentally, we then show that for general multivariate PID, there is no universal rule that recovers the decomposed mutual information from the antichain-indexed information atoms. In particular, two systems can share identical atoms regardless of any axioms while having different mutual information. These results reveal the limits of antichain-lattice and motivate relation-based foundations for multivariate information measures.

With the proliferation of Cyber-Physical Systems (CPSs) in daily life, the security of these systems is becoming an pressing problem. Fuzz testing has recently gained attention as a promising approach for automatically detecting vulnerabilities, however, the prohibitively large search space of physical and cyber inputs remains an open research challenge. To address this gap, the paper draws on control theory, leveraging physics-informed control models to guide exploration of the input space. We design and develop ConTest, a fuzzing tool that leverages Lyapunov functions of the control model for both detection and mutation to efficiently search through the parameter space with a provable guarantee on the effectiveness of bug-finding effectiveness under bounded dynamic model errors. We implemented a prototype of ConTest and deployed it to detect spatial and temporal input validation bugs in two representative robotic vehicle (RV) platforms, ArduPilot and PX4. A total of 253 input validation bugs were found, 58 of them being zero-day bugs, and 54 of them were acknowledged by the vendors.

Cyber-physical systems (CPS) must interact with varying environments at fine-grained time-scales, assuring control safety and stability while optimizing application-specific performance objectives. To address those requirements, co-design of real-time control and scheduling has received considerable attention over multiple decades, to allow rigorous assurance of system properties while enabling diverse forms of adaptation to changing operating conditions. In this paper, we present a new formalization of the periodicity requirements for control inputs to (1) guarantee reachability of safe (and avoidance of unsafe) portions of the system state space, (2) adaptively manage dynamic periodicity constraints that may change as the state space is traversed, and (3) express minimum periods to enable safe hand-offs between high-performance controllers and more conservative backup controllers. Our evaluations of this approach confirm that it is able to maintain system safety and stability while optimizing system performance.

No abstract available.

Safety is a fundamental requirement of many robotic systems. Control barrier function (CBF)-based approaches have been proposed to guarantee the safety of robotic systems. However, the effectiveness of these approaches highly relies on the choice of CBFs. Inspired by the universal approximation power of neural networks, there is a growing trend toward representing CBFs using neural networks, leading to the notion of neural CBFs (NCBFs). Current NCBFs, however, are trained and deployed in benign environments, making them ineffective for scenarios where robotic systems experience sensor faults and attacks. In this paper, we study safety-critical control synthesis for robotic systems under sensor faults and attacks. Our main contribution is the development and synthesis of a new class of CBFs that we term fault tolerant neural control barrier function (FT-NCBF). We derive the necessary and sufficient conditions for FT-NCBFs to guarantee safety, and develop a data-driven method to learn FT-NCBFs by minimizing a loss function constructed using the derived conditions. Using the learned FT-NCBF, we synthesize a control input and formally prove the safety guarantee provided by our approach. We demonstrate our proposed approach using two case studies: obstacle avoidance problem for an autonomous mobile robot and spacecraft rendezvous problem, with code available via https://github.com/HongchaoZhang-HZ/FTNCBF.

Mutual information between two random variables is a well-studied notion, whose understanding is fairly complete. Mutual information between one random variable and a pair of other random variables, however, is a far more involved notion. Specifically, Shannon's mutual information does not capture fine-grained interactions between those three variables, resulting in limited insights in complex systems. To capture these fine-grained interactions, in 2010 Williams and Beer proposed to decompose this mutual information to information atoms, called unique, redundant, and synergistic, and proposed several operational axioms that these atoms must satisfy. In spite of numerous efforts, a general formula which satisfies these axioms has yet to be found. Inspired by Judea Pearl's do-calculus, we resolve this open problem by introducing the do-operation, an operation over the variable system which sets a certain marginal to a desired value, which is distinct from any existing approaches. Using this operation, we provide the first explicit formula for calculating the information atoms so that Williams and Beer's axioms are satisfied, as well as additional properties from subsequent studies in the field.

Neural Control Barrier Functions (NCBFs) have shown significant promise in enforcing safety constraints on nonlinear autonomous systems. State-of-the-art exact approaches to verifying safety of NCBF-based controllers exploit the piecewise-linear structure of ReLU neural networks, however, such approaches still rely on enumerating all of the activation regions of the network near the safety boundary, thus incurring high computation cost. In this paper, we propose a framework for Synthesis with Efficient Exact Verification (SEEV). Our framework consists of two components, namely (i) an NCBF synthesis algorithm that introduces a novel regularizer to reduce the number of activation regions at the safety boundary, and (ii) a verification algorithm that exploits tight over-approximations of the safety conditions to reduce the cost of verifying each piecewise-linear segment. Our simulations show that SEEV significantly improves verification efficiency while maintaining the CBF quality across various benchmark systems and neural network structures. Our code is available at https://github.com/HongchaoZhang-HZ/SEEV.

Cyber-physical systems (CPS), which are often required to satisfy critical properties such as safety, have been shown to be vulnerable to exploits originating from cyber and/or physical sides. Recently, novel resilient architectures, which equip CPS with capabilities of recovering to normal operations, have been developed to guarantee the safety of CPS under cyber attacks. These resilient architectures utilize distinct mechanisms involving different parameters and are seemingly unrelated. Currently, the analysis and design methods of one novel resilient architecture for CPS are not readily applicable to one another. Consequently, evaluating the appropriateness and effectiveness of a set of candidate resilient architectures to a given CPS is currently impractical. In this poster, we report our progress on the development of a common framework for analyzing the safety and assessing recovery performance of two or more resilient architectures intended for CPS under attacks. We formulate a hybrid model as a common representation of resilient architectures. Our insight is that the resilient architectures have a shared set of discrete states, including vulnerable, under attack, unsafe, and recovery modes, which can be mapped to the discrete states of the unifying hybrid model. The hybrid model enables a unified safety analysis. We parameterize the required behaviors for the cyber and physical components in order to guarantee safety. The parameters then inform the development of metrics to measure the resilience of CPS. For CPS consisting of multiple heterogeneous components, we show that the effect of interconnections on the spatial and temporal parameters can be quantified efficiently, allowing a compositional approach to the safety verification of large-scale CPS.

The opinions of members of a population are influenced by opinions of their peers, their own predispositions, and information from external sources via one or more information channels (e.g., news, social media). Due to individual cognitive biases, the perceptual impact of and importance assigned by agents to information on each channel can be different. In this paper, we propose a model of opinion evolution that uses prospect theory to represent perception of information from the external source along each channel. Our prospect-theoretic model reflects traits observed in humans such as loss aversion, assigning inflated (deflated) values to low (high) probability events, and evaluating outcomes relative to an individually known reference point. We consider the problem of determining information dissemination strategies for the external source to adopt in order to drive opinions of individuals towards a desired value. However, computing a strategy faces a challenge that agents' initial predispositions and functions characterizing their perceptions of information disseminated might be unknown. We overcome this challenge by using Gaussian process learning to estimate these unknown parameters. When the external source sends information over multiple channels, the problem of jointly selecting optimal dissemination strategies is in general, combinatorial. We prove that this problem is submodular, and design near-optimal dissemination algorithms. We evaluate our model on three different widely used large graphs that represent real-world social interactions. Our results indicate that the external source can effectively drive opinions towards a desired value when using prospect-theory based dissemination strategies.

While ensuring stability for linear systems is well understood, it remains a major challenge for nonlinear systems. A general approach in such cases is to compute a combination of a Lyapunov function and an associated control policy. However, finding Lyapunov functions for general nonlinear systems is a challenging task. To address this challenge, several methods have been proposed that represent Lyapunov functions using neural networks. However, such approaches either focus on continuous-time systems, or highly restricted classes of nonlinear dynamics. We propose the first approach for learning neural Lyapunov control in a broad class of discrete-time systems. Three key ingredients enable us to effectively learn provably stable control policies. The first is a novel mixed-integer linear programming approach for verifying the discrete-time Lyapunov stability conditions, leveraging the particular structure of these conditions. The second is a novel approach for computing verified sublevel sets. The third is a heuristic gradient-based method for quickly finding counterexamples to significantly speed up Lyapunov function learning. Our experiments on four standard benchmarks demonstrate that our approach significantly outperforms state-of-the-art baselines. For example, on the path tracking benchmark, we outperform recent neural Lyapunov control baselines by an order of magnitude in both running time and the size of the region of attraction, and on two of the four benchmarks (cartpole and PVTOL), ours is the first automated approach to return a provably stable controller. Our code is available at: https://github.com/jlwu002/nlc_discrete.

Control Barrier Functions (CBFs) are a popular approach for safe control of nonlinear systems. In CBF-based control, the desired safety properties of the system are mapped to nonnegativity of a CBF, and the control input is chosen to ensure that the CBF remains nonnegative for all time. Recently, machine learning methods that represent CBFs as neural networks (neural control barrier functions, or NCBFs) have shown great promise due to the universal representability of neural networks. However, verifying that a learned CBF guarantees safety remains a challenging research problem. This paper presents novel exact conditions and algorithms for verifying safety of feedforward NCBFs with ReLU activation functions. The key challenge in doing so is that, due to the piecewise linearity of the ReLU function, the NCBF will be nondifferentiable at certain points, thus invalidating traditional safety verification methods that assume a smooth barrier function. We resolve this issue by leveraging a generalization of Nagumo's theorem for proving invariance of sets with nonsmooth boundaries to derive necessary and sufficient conditions for safety. Based on this condition, we propose an algorithm for safety verification of NCBFs that first decomposes the NCBF into piecewise linear segments and then solves a nonlinear program to verify safety of each segment as well as the intersections of the linear segments. We mitigate the complexity by only considering the boundary of the safe region and by pruning the segments with Interval Bound Propagation (IBP) and linear relaxation. We evaluate our approach through numerical studies with comparison to state-of-the-art SMT-based methods. Our code is available at https://github.com/HongchaoZhang-HZ/exactverif-reluncbf-nips23.

Cyber-physical systems (CPS) are required to satisfy safety constraints in various application domains such as robotics, industrial manufacturing systems, and power systems. Faults and cyber attacks have been shown to cause safety violations, which can damage the system and endanger human lives. Resilient architectures have been proposed to ensure safety of CPS under such faults and attacks via methodologies including redundancy and restarting from safe operating conditions. The existing resilient architectures for CPS utilize different mechanisms to guarantee safety, and currently, there is no common framework to compare them. Moreover, the analysis and design undertaken for CPS employing one architecture is not readily extendable to another. In this article, we propose a timing-based framework for CPS employing various resilient architectures and develop a common methodology for safety analysis and computation of control policies and design parameters. Using the insight that the cyber subsystem operates in one out of a finite number of statuses, we first develop a hybrid system model that captures CPS adopting any of these architectures. Based on the hybrid system, we formulate the problem of joint computation of control policies and associated timing parameters for CPS to satisfy a given safety constraint and derive sufficient conditions for the solution. Utilizing the derived conditions, we provide an algorithm to compute control policies and timing parameters relevant to the employed architecture. We also note that our solution can be applied to a wide class of CPS with polynomial dynamics and also allows incorporation of new architectures. We verify our proposed framework by performing a case study on adaptive cruise control of vehicles.

Safety is a critical property in applications including robotics, transportation, and energy. Safety is especially challenging in reinforcement learning (RL) settings, in which uncertainty of the system dynamics may cause safety violations during exploration. Control Barrier Functions (CBFs), which enforce safety by constraining the control actions at each time step, are a promising approach for safety-critical control. This technique has been applied to ensure the safety of model-free RL, however, it has not been integrated into model-based RL. In this paper, we propose Uncertainty-Tolerant Control Barrier Functions (UTCBFs), a new class of CBFs to incorporate model uncertainty and provide provable safety guarantees with desired probability. Furthermore, we introduce an algorithm for model-based RL to guarantee safety by integrating CBFs with gradient-based policy search. Our approach is verified through a numerical study of a cart-pole system and an inverted pendulum system with comparison to state-of-the-art RL algorithms.

Increasingly large trip demands have strained urban transportation capacity, which consequently leads to traffic congestion and rapid growth of greenhouse gas emissions. In this work, we focus on achieving sustainable transportation by incentivizing passengers to switch from private cars to public transport. We address the following challenges. First, the passengers incur inconvenience costs when changing their transit behaviors due to delay and discomfort, and thus need to be reimbursed. Second, the inconvenience cost, however, is unknown to the government when choosing the incentives. Furthermore, changing transit behaviors raises privacy concerns from passengers. An adversary could infer personal information (e.g., daily routine, region of interest, and wealth) by observing the decisions made by the government, which are known to the public. We adopt the concept of differential privacy and propose privacy-preserving incentive designs under two settings, denoted as two-way communication and one-way communication. Under two-way communication, passengers submit bids and then the government determines the incentives, whereas in one-way communication, the government simply sets a price without acquiring information from the passengers. We formulate the problem under two-way communication as a mixed integer linear program and propose a polynomial-time approximation algorithm. We show the proposed approach achieves truthfulness, individual rationality, social optimality, and differential privacy. Under one-way communication, we focus on how the government should design the incentives without revealing passengers’ inconvenience costs while still preserving differential privacy. We formulate the problem as a convex program and propose a differentially private and near-optimal solution algorithm. A numerical case study using the Caltrans Performance Measurement System (PeMS) data source is presented as evaluation. The results show that the proposed approaches achieve a win-win situation in which both the government and passengers obtain non-negative utilities.

This paper presents a new masquerade attack called the cloaking attack and provides formal analyses for clock skew-based intrusion detection systems (IDSs) that detect masquerade attacks in the controller area network (CAN) in automobiles. In the cloaking attack, the adversary manipulates the message inter-transmission times of spoofed messages by adding delays so as to emulate a desired clock skew and avoid detection. In order to predict and characterize the impact of the cloaking attack in terms of the attack success probability on a given CAN bus and IDS, we develop formal models for two clock skew-based IDSs, i.e., the state-of-the-art (SOTA) IDS and its adaptation to the widely used network time protocol (NTP), using parameters of the attacker, the detector, and the hardware platform. To the best of our knowledge, this is the first paper that provides formal analyses of clock skew-based IDSs in automotive CAN. We implement the cloaking attack on two hardware testbeds, a prototype and a real vehicle (the University of Washington EcoCAR), and demonstrate its effectiveness against both the SOTA and NTP-based IDSs. By comparing each predicted attack success probability curve against its experimental curve, we find that the average prediction error is within 3.0% for the SOTA IDS and 5.7% for the NTP-based IDS.

Submodular maximization enables efficient approximation of machine learning, networking, and language processing problems. Typically, these problems have been shown to have matroid constraints, which generalize matching and partition conditions. Developing scalable, distributed submodular optimization algorithms that guarantee the same performance as centralized techniques has been an active area of research. In this paper, we address the problem of developing scalable distributed algorithms for submodular maximization with a matroid constraint. Our key step is to construct an auxiliary function from the submodular objective function, and develop distributed exchange-based algorithms for optimizing the auxiliary function. We first introduce a distributed algorithm for maximizing a submodular function with a matroid constraint. We then develop an algorithm for maximizing time-varying submodular functions under partition matroid constraints, which arises in sensor placement and data caching. We prove that both algorithms provide (1-1/e) optimality bounds, and hence achieve the same guarantees as the best centralized algorithms.

Maximization of submodular set functions arises in wireless applications such as scheduling, caching, and leader selection. For a centralized entity with oracle access to the submodular function, submodular maximization can be approximated up to a constant factor using polynomial-time algorithms; such an entity, however, may be unavailable in decentralized wireless networks. In this paper, we consider maximization of a time-varying submodular function by distributed, resource-constrained nodes. We present algorithms for unconstrained distributed submodular maximization, as well as monotone submodular maximization subject to cardinality constraints. For the unconstrained submodular maximization problem, our algorithm achieves an expected optimality gap of 1/3. For cardinality-constrained submodular maximization, our algorithm achieves an expected optimality gap of 1/2, while reducing the storage and communication overhead, as well as the computation requirements of the nodes, compared to existing techniques. We evaluate our approach through an experimental study using sensor scheduling data, and find that our approach is within ten percent of the best achievable utility in the unconstrained case and within five percent in the constrained case.

In certain applications, the locations of events reported by a sensor network need to remain anonymous. That is, unauthorized observers must be unable to detect the origin of such events by analyzing the network traffic. Known as the source anonymity problem, this problem has emerged as an important topic in the security of wireless sensor networks, with variety of techniques based on different adversarial assumptions being proposed. In this work, we present a new framework for modeling, analyzing, and evaluating anonymity in sensor networks. The novelty of the proposed framework is twofold: first, it introduces the notion of "interval indistinguishability” and provides a quantitative measure to model anonymity in wireless sensor networks; second, it maps source anonymity to the statistical problem of binary hypothesis testing with nuisance parameters. We then analyze existing solutions for designing anonymous sensor networks using the proposed model. We show how mapping source anonymity to binary hypothesis testing with nuisance parameters leads to converting the problem of exposing private source information into searching for an appropriate data transformation that removes or minimize the effect of the nuisance information. By doing so, we transform the problem from analyzing real-valued sample points to binary codes, which opens the door for coding theory to be incorporated into the study of anonymous sensor networks. Finally, we discuss how existing solutions can be modified to improve their anonymity.

In RFID literature, most “privacy-preserving” protocols require the reader to search all tags in the system in order to identify a single tag. In another class of protocols, the search complexity is reduced to be logarithmic in the number of tags, but it comes with two major drawbacks: it requires a large communication overhead over the fragile wireless channel, and the compromise of a tag in the system reveals secret information about other, uncompromised, tags in the same system. In this work, we take a different approach to address time complexity of private identification in large-scale RFID systems. We utilize the special architecture of RFID systems to propose a symmetric-key privacy-preserving authentication protocol for RFID systems with constant-time identification. Instead of increasing communication overhead, the existence of a large storage device in RFID systems, the database, is utilized for improving the time efficiency of tag identification.

In RFID literature, most “privacy-preserving” protocols require the reader to search all tags in the system in order to identify a single tag. In another class of protocols, the search complexity is reduced to be logarithmic in the number of tags, but it comes with two major drawbacks: it requires a large communication overhead over the fragile wireless channel, and the compromise of a tag in the system reveals secret information about other, uncompromised, tags in the same system. In this work, we take a different approach to address time-complexity of private identification in large-scale RFID systems. We utilize the special architecture of RFID systems to propose the first symmetric-key privacy-preserving authentication protocol for RFID systems with constant-time identification. Instead of increasing communication overhead, the existence of a large storage device in RFID systems, the database, is utilized for improving the time efficiency of tag identification.

In this work, we investigate the security of anonymous wireless sensor networks. To lay down the foundations of a formal framework, we develop a new model for analyzing and evaluating anonymity in sensor networks. The novelty of the proposed model is twofold: first, it introduces the notion of ``interval indistinguishability" that is stronger than existing notions; second, it provides a quantitative measure to evaluate anonymity in sensor networks. The significance of the proposed model is that it captures a source of information leakage that cannot be captured using existing models. By analyzing current anonymous designs under the proposed model, we expose the source of information leakage that is undetectable by existing models and quantify the anonymity of current designs. Finally, we show how the proposed model can lead to a general and intuitive direction for improving the anonymity of current designs.

Wireless sensor networks are often used in applications where message confidentiality, integrity, and authentication are required. Cryptography is a common mechanism for meeting these security requirements. The use of cryptography requires that nodes share secret keys, which are typically assigned to each node according to key distribution schemes. Given a key distribution, there is currently no design metric for evaluating vulnerability to key exposure. In this work, we introduce a metric for analyzing and comparing the resilience of key distributions by introducing the concept of a Link Key Security Metric (LKSM). We define the properties needed in an LKSM and provide a metric that satisfies them.