Abstract The network security analyzers use intrusion detection systems (IDSes) to distinguish malicious traffic from benign ones. The deep learning-based (DL-based) IDSes are proposed to auto-extract high-level features and eliminate the time-consuming and costly signature extraction process. However, this new generation of IDSes still needs to overcome a number of challenges to be employed in practical environments. One of the main issues of an applicable IDS is facing traffic concept drift, which manifests itself as new (i.e. , zero-day) attacks, in addition to the changing behavior of benign users/applications. Furthermore, a practical DL-based IDS needs to be conformed to a distributed (i.e. , multi-sensor) architecture in order to yield more accurate detections, create a collective attack knowledge based on the observations of different sensors, and also handle big data challenges for supporting high throughput networks. This paper proposes a novel multi-agent network intrusion detection framework to address the above shortcomings, considering a more practical scenario (i.e., online adaptable IDSes). This framework employs continual deep anomaly detectors for adapting each agent to the changing attack/benign patterns in its local traffic. In addition, a federated learning approach is proposed for sharing and exchanging local knowledge between different agents. Furthermore, the proposed framework implements sequential packet labeling for each flow, which provides an attack probability score for the flow by gradually observing each flow packet and updating its estimation. We evaluate the proposed framework by employing different deep models (including CNN-based and LSTM-based) over the CIC-IDS2017 and CSE-CIC-IDS2018 datasets. Through extensive evaluations and experiments, we show that the proposed distributed framework is well adapted to the traffic concept drift. More precisely, our results indicate that the CNN-based models are well suited for continually adapting to the traffic concept drift (i.e. , achieving an average detection rate of above 95% while needing just 128 new flows for the updating phase), and the LSTM-based models are a good candidate for sequential packet labeling in practical online IDSes (i.e. , detecting intrusions by just observing their first 15 packets).

We consider the problem of private information retrieval (PIR), where a single user with private side information (PSI) aims to retrieve multiple files from a library stored at some servers. We assume that the side information (SI) at the user includes a subset of files stored privately. Moreover, the identity of requests and side information at the user are not revealed to any of the servers. The problem involves finding the minimum load transmitted from the servers to the user such that the requested files can be decoded with the help of received data and side information. By providing matching lower and upper bounds for certain regimes, we characterize the minimum load imposed on all the servers. Our result shows that the capacity is the same as the capacity of a multi-message PIR problem without PSI, but with a library of reduced size, i.e., the library is equal to the original library size minus the size of SI. Finally, we extend our setup to the case where instead of storing complete files as SI, the user can store a fraction of files. For this scenario, we propose an achievability scheme based on which we discuss the best storing strategies.

We consider load balancing problem in a cache network consisting of storage-enabled servers forming a distributed content delivery scenario. Previously proposed load balancing solutions cannot perfectly balance out requests among servers, which is a critical issue in practical networks. Therefore, in this paper, we investigate a coded cache content placement where coded chunks of original files are stored in servers based on the files popularity distribution. In our scheme, upon each request arrival at the delivery phase, by dispatching enough coded chunks to the request origin from the nearest servers, the requested file can be decoded. Here, we show that if n requests arrive randomly at n servers, the proposed scheme results in the maximum load of O(1) in the network. This result is shown to be valid under various assumptions for the underlying network topology. Our results should be compared to the maximum load of two baseline schemes, namely, nearest replica and power of two choices strategies, which are O(log n) and O(log log n), respectively. This finding shows that using coding, results in a considerable load balancing performance improvement, without compromising communications cost performance. This is confirmed by performing extensive simulation results, in non-asymptotic regimes as well.

We consider the problem of private information retrieval (PIR) where a single user with private side information aims to retrieve multiple files from a library stored (uncoded) at a number of servers. We assume the side information at the user includes a subset of files stored privately (i.e., the server does not know the indices of these files). In addition, we require that the identity of requests and side information at the user are not revealed to any of the servers. The problem involves finding the minimum load to be transmitted from the servers to the user such that the requested files can be decoded with the help of received and side information. By providing matching lower and upper bounds, for certain regimes, we characterize the minimum load imposed to all the servers (i.e., the capacity of this PIR problem). Our result shows that the capacity is the same as the capacity of a multi-message PIR problem without private side information, but with a library of reduced size. The effective size of the library is equal to the original library size minus the size of side information.

We consider load balancing in a network of caching servers delivering contents to end users. Randomized load balancing via the so-called power of two choices is a well-known approach in parallel and distributed systems. In this framework, we investigate the tension between storage resources, communication cost, and load balancing performance. To this end, we propose a randomized load balancing scheme which simultaneously considers cache size limitation and proximity in the server redirection process. In contrast to the classical power of two choices setup, since the memory limitation and the proximity constraint cause correlation in the server selection process, we may not benefit from the power of two choices. However, we prove that in certain regimes of problem parameters, our scheme results in the maximum load of order Q(loglogn) (here n is the network size). This is an exponential improvement compared to the scheme which assigns each request to the nearest available replica. Interestingly, the extra communication cost incurred by our proposed scheme, compared to the nearest replica strategy, is small. Furthermore, our extensive simulations show that the trade-off trend does not depend on the network topology and library popularity profile details.

We consider load balancing in a network of caching servers delivering contents to end users. Randomized load balancing via the so-called power of two choices is a well-known approach in parallel and distributed systems that reduces network imbalance. In this paper, we propose a randomized load balancing scheme which simultaneously considers cache size limitation and proximity in the server redirection process. Since the memory limitation and the proximity constraint cause correlation in the server selection process, we may not benefit from the power of two choices in general. However, we prove that in certain regimes, in terms of memory limitation and proximity constraint, our scheme results in the maximum load of order Θ(log log n) (here n is the number of servers and requests), and at the same time, leads to a low communication cost. This is an exponential improvement in the maximum load compared to the scheme which assigns each request to the nearest available replica. Finally, we investigate our scheme performance by extensive simulations.

It is well known that load balancing and low delivery communication cost are two critical issues in mapping requests to servers in Content Delivery Networks (CDNs). However, the trade-off between these two performance metrics has not been yet quantitatively investigated in designing efficient request mapping schemes. In this work, we formalize this trade-off through a stochastic optimization problem. While the solutions to the problem in the extreme cases of minimum communication cost and optimum load balancing can be derived in closed form, finding the general solution is hard to derive. Thus we propose three heuristic mapping schemes and compare the trade-off performance of them through extensive simulations. Our simulation results show that at the expense of high query cost, we can achieve a good trade-off curve. Moreover, by benefiting from the power of multiple choices phenomenon, we can achieve almost the same performance with much less query cost. Finally, we can handle requests with different delay requirements at the cost of degrading network performance.

We consider a group of m trusted and authenticated nodes that aim to create a shared secret key K over a wireless channel in the presence of an eavesdropper Eve. We assume that there exists a state-dependent wireless broadcast channel from one of the honest nodes to the rest of them including Eve. All of the trusted nodes can also discuss over a cost-free, noiseless and unlimited rate public channel which is also overheard by Eve. For this setup, we develop an information-theoretically secure secret key agreement protocol. We show the optimality of this protocol for “linear deterministic” wireless broadcast channels. This model generalizes the packet erasure model studied in the literature for wireless broadcast channels. Here, the main idea is to convert a deterministic channel into multiple independent erasure channels by using superposition coding. For “state-dependent Gaussian” wireless broadcast channels, by using insights from the deterministic problem, we propose an achievability scheme based on a multi-layer wiretap code. By using the wiretap code, we can mimic the phenomenon of converting the wireless channel into multiple independent erasure channels. Then, finding the best achievable secret key generation rate leads to solving a non-convex power allocation problem over these channels (layers). We show that using a dynamic programming algorithm, one can obtain the best power allocation for this problem. Moreover, we prove the optimality of the proposed achievability scheme for the regime of high-SNR and large-dynamic range over the channel states in the (generalized) degrees of freedom sense.

The generalized belief propagation (GBP), introduced by Yedidia et al., is an extension of the belief propagation (BP) algorithm, which is widely used in different problems involved in calculating exact or approximate marginals of probability distributions. In many problems, it has been observed that the accuracy of GBP outperforms that of BP considerably. However, due to its generally higher complexity compared to BP, its application is limited in practice. In this paper, we introduce a stochastic version of GBP called stochastic generalized belief propagation (SGBP) that can be considered as an extension to the stochastic BP (SBP) algorithm introduced by Noorshams et al. They have shown that SBP reduces the complexity per iteration of BP by an order of magnitude in alphabet size. In contrast to SBP, SGBP can reduce the computation complexity if certain topological conditions are met by the region graph associated to a graphical model. However, this reduction can be larger than only one order of magnitude in alphabet size. In this paper, we characterize these conditions and the amount of complexity gain that one can obtain by using SGBP. Finally, using similar proof techniques employed by Noorshams et al., for general graphical models satisfy contraction conditions, we prove the asymptotic convergence of SGBP to the unique GBP fixed point, as well as providing non-asymptotic upper bounds on the mean square error and on the high probability error.

Recent empirical results have demonstrated that generalized belief propagation (GBP) can be used to closely estimate the capacity of certain 2D runlength-limited constraints. We provide a partial analytical validation of these observations by showing that GBP yields a lower bound on the partition function of 2D Ising models with restricted grid size. While previous papers have proved that belief propagation (BP) can be used to obtain a lower bound on the partition function of 2D Ising models, this paper is the first work that analyzes GBP-based partition function approximations of 2D Ising models.

In [1], [2] it is shown that the minimum broadcast rate of a linear index code over a finite field Fqis equal to an algebraic invariant of the underlying digraph, called minrankq. In [3], it is proved that for F2and any positive integer k, minrankq(G) ≤ k if and only if there exists a homomorphism from the complement of the graph G to the complement of a particular undirected graph family called “graph family {Gk}”. As observed in [2], by combining these two results one can relate the linear index coding problem of undirected graphs to the graph homomorphism problem. In [4], a direct connection between linear index coding problem and graph homomorphism problem is introduced. In contrast to the former approach, the direct connection holds for digraphs as well and applies to any field size. More precisely, in [4], a graph family {Hkq} has been introduced and shown that whether or not the scalar linear index of a digraph G is less than or equal to k is equivalent to the existence of a graph homomorphism from the complement of G to the complement of Hkq. In this paper, we first study the structure of the digraphs Hkqdefined in [4]. Analogous to the result of [2] about undirected graphs, we prove that Hkqare vertex transitive digraphs. Using this, and by applying a lemma of Hell and Nesetril [5], we derive a class of necessary conditions for digraphs G to satisfy lindq(G) ≤ k. Particularly, we obtain new lower bounds on lindq(G). Our next result is about the computational complexity of scalar linear index of a digraph. It is known that deciding whether the scalar linear index of an undirected graph is equal to k or not is NP-complete for k ≥ 3 and is polynomially decidable for k = 1, 2 [3]. For digraphs, it is shown in [6] that for the binary alphabet, the decision problem for k = 2 is NP-complete. We use graph homomorphism framework to extend this result to arbitrary alphabet.

In this work, we study the problem of index coding from graph homomorphism perspective. We show that the minimum broadcast rate of an index coding problem for different variations of the problem such as non-linear, scalar, and vector index code, can be upper bounded by the minimum broadcast rate of another index coding problem when there exists a homomorphism from the complement of the side information graph of the first problem to that of the second problem. As a result, we show that several upper bounds on scalar and vector index code problem are special cases of one of our main theorems. For the linear scalar index coding problem, it has been shown in [1] that the binary linear index of a graph is equal to a graph theoretical parameter called minrank of the graph. For undirected graphs, in [2] it is shown that minrank(G) = k if and only if there exists a homomorphism from G to a predefined graph Gk. Combining these two results, it follows that for undirected graphs, all the digraphs with linear index of at most k coincide with the graphs G for which there exists a homomorphism from G to Gk. In this paper, we give a direct proof to this result that works for digraphs as well. We show how to use this classification result to generate lower bounds on scalar and vector index. In particular, we provide a lower bound for the scalar index of a digraph in terms of the chromatic number of its complement. Using our framework, we show that by changing the field size, linear index of a digraph can be at most increased by a factor that is independent from the number of the nodes.

In this work we study an Arbitrarily Varying Channel (AVC) with quadratic power constraints on the transmitter and a so-called “oblivious” jammer (along with additional AWGN) under a maximum probability of error criterion, and no private randomness between the transmitter and the receiver. This is in contrast to similar AVC models under the average probability of error criterion considered in [1], [2], and models wherein common randomness is allowed [3] - these distinctions are important in some communication scenarios outlined below. We consider the regime where the jammer's power constraint is smaller than the transmitter's power constraint (in the other regime it is known no positive rate is possible). For this regime we show the existence of stochastic codes (with no common randomness between the transmitter and receiver) that enables reliable communication at the same rate as when the jammer is replaced with AWGN with the same power constraint. This matches known information-theoretic outer bounds. In addition to being a stronger result than that in [1] (enabling recovery of the results therein), our proof techniques are also somewhat more direct, and hence may be of independent interest.

In this paper, we propose an “arbitrarily varying channel” (AVC) approach to study the capacity of noncoherent transmission in a network that employs randomized linear network coding. The network operation is modeled by a matrix channel over a finite field where the transfer matrix changes arbitrarily from time-slot to time-slot but up to a known distribution over its rank. By extending the AVC results to this setup, we characterize the capacity of such a non-coherent transmission scheme and show that subspace coding is optimal for achieving the capacity. By imposing a probability distribution over the state space of an AVC, we obtain a channel which we called “partially arbitrarily varying channel” (PAVC). In this work, we characterize the “randomized” as well as the “deterministic” code capacity of a PAVC under the average error probability criterion. Although we introduce the PAVC to model the non-coherent network coding, this extension to an AVC might be of its own interest as well.

Systems that employ network coding for content distribution convey to the receivers linear combinations of the source packets. If we assume randomized network coding, during this process, the network nodes collect random subspaces of the space spanned by the source packets. We establish several fundamental properties of the random subspaces induced in such a system and show that these subspaces implicitly carry topological information about the network and its state that can be passively collected and inferred. We leverage this information toward a number of applications that are interesting in their own right, such as topology inference, bottleneck discovery in peer-to-peer systems, and locating Byzantine attackers. We thus argue that randomized network coding, apart from its better known properties for improving information delivery rate, can additionally facilitate network management and control.

We consider a group of m trusted nodes that aim to create a shared secret key K, using a state-dependent wireless broadcast channel that exists from one of the honest nodes to the rest of the nodes including a passive eavesdropper Eve. All of the trusted nodes can also discuss over a cost-free and unlimited rate public channel which is also observed by Eve. For this setup, we develop an information-theoretically secure secret key agreement protocol. We show the optimality of this protocol for linear deterministic wireless broadcast channels as well as in the high-SNR regime for wireless channels with large dynamic range over channel states.

We consider the problem of multicasting information from a source to a set of receivers over a network where intermediate network nodes perform randomized linear network coding operations on the source packets. We propose a channel model for the noncoherent network coding introduced by Koetter and Kschischang in , that captures the essence of such a network operation, and calculate the capacity as a function of network parameters. We prove that use of subspace coding is optimal, and show that, in some cases, the capacity-achieving distribution uses subspaces of several dimensions, where the employed dimensions depend on the packet length. This model and the results also allow us to give guidelines on when subspace coding is beneficial for the proposed model and by how much, in comparison to a coding vector approach, from a capacity viewpoint. We extend our results to the case of multiple source multicast that creates a virtual multiple access channel.

In a significant class of sensor-network applications, the identities of the reporting sensors constitute the bulk of the communicated data, whereas the message itself can be as small as a single bit - for instance, in many cases, sensors are used to detect whether and where a certain interesting condition occurred, or to track incremental environmental changes at fixed locations. In such scenarios, the traditional network-protocol paradigm of separately specifying the source identity and the message in distinct fields leads to inefficient communication. This work addresses the question of how communication should happen in such identity-aware sensor networks. We calculate theoretical performance bounds for this type of communication, where 'performance' refers to the number of transmitted bits. We propose a communication protocol, where the identity and message of each source are specified jointly using subspace coding. We show through analysis and simulation that our protocol's performance is close to optimal and compare it to the performance of a traditional protocol, where identity and message are specified separately.

In a significant class of sensor-network applications, the identities of the reporting sensors constitute the bulk of the communicated data, whereas the message itself can be as small as a single bit - for instance, in many cases, sensors are used to detect whether and where a certain interesting condition occured, or to track incremental environmental changes at fixed locations. In such scenarios, the traditional network-protocol paradigm of separately specifying the source identity and the message in distinct fields leads to inefficient communication. This work addresses the question of how should communication happen in such identity-aware sensor networks. We reexamine the traditional source-identity/message separation and propose a scheme for jointly encoding the two. We use this to develop a communication method for identity-aware sensor networks and show it to be energy efficient, simple to implement, and gracefully adaptable to scenarios frequently encountered in sensor networks - for instance, node failures, or large numbers of nodes where only few are active during each reporting round.

In networks that employ network coding, two main approaches have been proposed in the literature to allow the receivers to recover the source information: (i) use of coding vectors, that keep track of the linear combinations the received packets contain, and (ii) subspace coding, that dispenses of the need to know the linear combinations, since information is conveyed from the choice of subspaces alone. Both these approaches impose the strong requirement that all source packets get potentially combined. We here present a third approach that relaxes this assumption, and is thus not a special case from either of the previous two. This relaxation allows to employ compressed coding vectors to efficiently convey the coding coefficients, without altering the operation of intermediate network nodes. We develop optimal designs for such vectors.

The min-cut value towards a single receiver in a network with unit capacity edges can be achieved by routing a single bit. The multicast theorem in network coding shows that, the common min-cut value towards N ¿ 1 receivers can also be achieved using packets of length logN bits, if the operations the intermediate nodes perform are deterministically known at the receivers. We here calculate the capacity in the case where these operations are unknown, and characterize how the capacity depends on the min-cut value and the packet length.

We consider multisource non-coherent network coding, where multiple sources send information to one or multiple receivers. We prove that this is equivalent to a ldquosubspacerdquo channel, that takes subspaces as inputs and outputs. We then show that the rate of each individual receiver is upper bounded as deltai(T - delta1- delta2), where deltaiis what we define to be the ldquodominatingrdquo dimension in the subspace codebook of source i, and T is the ldquocoherencerdquo time of the network.

We examine the problem of multiple sources transmitting information to one or more receivers that require the information from all the sources, over a network where the network nodes perform randomized network coding. We consider the noncoherent case, where neither the sources nor the receivers have any knowledge of the intermediate nodes operations. We formulate a model for this problem, inspired from block- fading noncoherent MIMO communications. We prove, using information theoretic tools, that coding over subspaces is sufficient to achieve the capacity, and give bounds for the capacity. We then examine the associated combinatorial problem of code design. We extend the work by Koetter and Kschischang [3] to code constructions for the multisource case. Our constructions can also be viewed as coding for the noncoherent multiple-access finite-field channel.

Randomized network coding has network nodes randomly combine and exchange linear combinations of the source packets. A header appended to the packet, called coding vector, specifies the exact linear combination that each packet carries. The main contribution of this work is to investigate properties of the subspaces spanned by the collected coding vectors in each network node. We use these properties to exhibit the relationship between the network topology and the subspaces collected at the nodes. This allows us to passively infer the network topology for a general class of graphs.