Today's routing protocols critically rely on the assumption that the underlying hardware is trusted. Given the increasing number of attacks on network devices, and recent reports on hardware backdoors this assumption has become questionable. Indeed, with the critical role computer networks play today, the contrast between our security assumptions and reality is problematic. This paper presents Software-Defined Adversarial Trajectory Sampling (SoftATS), an OpenFlow-based mechanism to efficiently monitor packet trajectories, also in the presence of non-cooperating or even adversarial switches or routers, e.g., containing hardware backdoors. Our approach is based on a secure, redundant and adaptive sample distribution scheme which allows us to provably detect adversarial switches or routers trying to reroute, mirror, drop, inject, or modify packets (i.e., header and or payload). We evaluate the effectiveness of our approach in different adversarial settings, report on a proof-of-concept implementation, and provide a first evaluation of the performance overheads of such a scheme.
The paper most closely related to ours is by @cite_52 . The authors present a smart generalization of trajectory sampling where hash values are shared between a subset of switches, rendering it hard for an adversary to avoid detection. The authors also present a first simulation of the possibility to detect packet drop, modifications and substitution attacks. Our paper builds upon this work in multiple respects. We initiate the study of injection attacks and observe that if combined with drop attacks, injection attacks introduce a number of more sophisticated attacks. Accordingly, we extend and formally and empirically analyze detection algorithm guarantees under various misbehaviors, including injections, mirroring, rerouting, or modifications of headers and or payloads. Unlike prior work, our hash assignment algorithm is completely random, eliminating bias for pairs and their assigned hash values. Moreover, our detection algorithm does not rely on an aggregation of trajectories and counters. Instead, we use the collector's (controller's) global view of the network (i.e., the network policy oracle) to compute every sampled packet's trajectory which gives us a per sample detection accuracy rather than an aggregate. We demonstrate that our detection algorithm can be parallelized using multiple threads (and possibly multiple collectors).
@cite_52
2022229650 2792169732 2345718780 1757513105
We consider the sequential (i.e., online) detection of false data injection attacks in smart grid, which aims to manipulate the state estimation procedure by injecting malicious data to the monitoring meters. The unknown parameters in the system, namely the state vector, injected malicious data and the set of attacked meters pose a significant challenge for designing a robust, computationally efficient, and high-performance detector. We propose a sequential detector based on the generalized likelihood ratio to address this challenge. Specifically, the proposed detector is designed to be robust to a variety of attacking strategies, and load situations in the power system, and its computational complexity linearly scales with the number of meters. Moreover, it considerably outperforms the existing first-order cumulative sum detector in terms of the average detection delay and robustness to various attacking strategies. For wide-area monitoring in smart grid, we further develop a distributed sequential detector using an adaptive sampling technique called level-triggered sampling. The resulting distributed detector features single bit per sample in terms of the communication overhead, while preserving the high performance of the proposed centralized detector. In this paper, online detection of false data injection attacks and denial of service attacks in the smart grid is studied. The system is modeled as a discrete-time linear dynamic system and state estimation is performed using the Kalman filter. The generalized cumulative sum algorithm is employed for quickest detection of the cyber-attacks. Detectors are proposed in both centralized and distributed settings. The proposed detectors are robust to time-varying states, attacks, and set of attacked meters. Online estimates of the unknown attack variables are provided, that can be crucial for a quick system recovery. In the distributed setting, due to bandwidth constraints, local centers can only transmit quantized messages to the global center, and a novel event-based sampling scheme called level-crossing sampling with hysteresis is proposed that is shown to exhibit significant advantages compared with the conventional uniform-in-time sampling scheme. Moreover, a distributed dynamic state estimator is proposed based on information filters. Numerical examples illustrate the fast and accurate response of the proposed detectors in detecting both structured and random attacks and their advantages over existing methods. This paper examines the close interplay between cooperation and adaptation for distributed detection schemes over fully decentralized networks. The combined attributes of cooperation and adaptation are necessary to enable networks of detectors to continually learn from streaming data and to continually track drifts in the state of nature when deciding in favor of one hypothesis or another. The results in this paper establish a fundamental scaling law for the steady-state probabilities of miss detection and false alarm in the slow adaptation regime, when the agents interact with each other according to distributed strategies that employ small constant step-sizes. The latter are critical to enable continuous adaptation and learning. This paper establishes three key results. First, it is shown that the output of the collaborative process at each agent has a steady-state distribution. Second, it is shown that this distribution is asymptotically Gaussian in the slow adaptation regime of small step-sizes. Third, by carrying out a detailed large deviations analysis, closed-form expressions are derived for the decaying rates of the false-alarm and miss-detection probabilities. Interesting insights are gained from these expressions. In particular, it is verified that as the step-size @math decreases, the error probabilities are driven to zero exponentially fast as functions of @math , and that the exponents governing the decay increase linearly in the number of agents. It is also verified that the scaling laws governing the errors of detection and the errors of estimation over the network behave very differently, with the former having exponential decay proportional to @math , while the latter scales linearly with decay proportional to @math . Moreover, and interestingly, it is shown that the cooperative strategy allows each agent to reach the same detection performance, in terms of detection error exponents, of a centralized stochastic-gradient solution. The results of this paper are illustrated by applying them to canonical distributed detection problems. This paper is motivated by two applications, namely i) generalizations of cuckoo hashing, a computationally simple approach to assigning keys to objects, and ii) load balancing in content distribution networks, where one is interested in determining the impact of content replication on performance. These two problems admit a common abstraction: in both scenarios, performance is characterized by the maximum weight of a generalization of a matching in a bipartite graph, featuring node and edge capacities. Our main result is a law of large numbers characterizing the asymptotic maximum weight matching in the limit of large bipartite random graphs, when the graphs admit a local weak limit that is a tree. This result specializes to the two application scenarios, yielding new results in both contexts. In contrast with previous results, the key novelty is the ability to handle edge capacities with arbitrary integer values. An analysis of belief propagation algorithms (BP) with multivariate belief vectors underlies the proof. In particular, we show convergence of the corresponding BP by exploiting monotonicity of the belief vectors with respect to the so-called upshifted likelihood ratio stochastic order. This auxiliary result can be of independent interest, providing a new set of structural conditions which ensure convergence of BP.