-
Improving Graph Machine Learning Performance Through Feature Augmentation Based on Network Control Theory
Authors:
Anwar Said,
Obaid Ullah Ahmad,
Waseem Abbas,
Mudassir Shabbir,
Xenofon Koutsoukos
Abstract:
Network control theory (NCT) offers a robust analytical framework for understanding the influence of network topology on dynamic behaviors, enabling researchers to decipher how certain patterns of external control measures can steer system dynamics towards desired states. Distinguished from other structure-function methodologies, NCT's predictive capabilities can be coupled with deploying Graph Ne…
▽ More
Network control theory (NCT) offers a robust analytical framework for understanding the influence of network topology on dynamic behaviors, enabling researchers to decipher how certain patterns of external control measures can steer system dynamics towards desired states. Distinguished from other structure-function methodologies, NCT's predictive capabilities can be coupled with deploying Graph Neural Networks (GNNs), which have demonstrated exceptional utility in various network-based learning tasks. However, the performance of GNNs heavily relies on the expressiveness of node features, and the lack of node features can greatly degrade their performance. Furthermore, many real-world systems may lack node-level information, posing a challenge for GNNs.To tackle this challenge, we introduce a novel approach, NCT-based Enhanced Feature Augmentation (NCT-EFA), that assimilates average controllability, along with other centrality indices, into the feature augmentation pipeline to enhance GNNs performance. Our evaluation of NCT-EFA, on six benchmark GNN models across two experimental setting. solely employing average controllability and in combination with additional centrality metrics. showcases an improved performance reaching as high as 11%. Our results demonstrate that incorporating NCT into feature enrichment can substantively extend the applicability and heighten the performance of GNNs in scenarios where node-level information is unavailable.
△ Less
Submitted 3 May, 2024;
originally announced May 2024.
-
Control-based Graph Embeddings with Data Augmentation for Contrastive Learning
Authors:
Obaid Ullah Ahmad,
Anwar Said,
Mudassir Shabbir,
Waseem Abbas,
Xenofon Koutsoukos
Abstract:
In this paper, we study the problem of unsupervised graph representation learning by harnessing the control properties of dynamical networks defined on graphs. Our approach introduces a novel framework for contrastive learning, a widely prevalent technique for unsupervised representation learning. A crucial step in contrastive learning is the creation of 'augmented' graphs from the input graphs. T…
▽ More
In this paper, we study the problem of unsupervised graph representation learning by harnessing the control properties of dynamical networks defined on graphs. Our approach introduces a novel framework for contrastive learning, a widely prevalent technique for unsupervised representation learning. A crucial step in contrastive learning is the creation of 'augmented' graphs from the input graphs. Though different from the original graphs, these augmented graphs retain the original graph's structural characteristics. Here, we propose a unique method for generating these augmented graphs by leveraging the control properties of networks. The core concept revolves around perturbing the original graph to create a new one while preserving the controllability properties specific to networks and graphs. Compared to the existing methods, we demonstrate that this innovative approach enhances the effectiveness of contrastive learning frameworks, leading to superior results regarding the accuracy of the classification tasks. The key innovation lies in our ability to decode the network structure using these control properties, opening new avenues for unsupervised graph representation learning.
△ Less
Submitted 17 April, 2024; v1 submitted 7 March, 2024;
originally announced March 2024.
-
Enhanced Graph Neural Networks with Ego-Centric Spectral Subgraph Embeddings Augmentation
Authors:
Anwar Said,
Mudassir Shabbir,
Tyler Derr,
Waseem Abbas,
Xenofon Koutsoukos
Abstract:
Graph Neural Networks (GNNs) have shown remarkable merit in performing various learning-based tasks in complex networks. The superior performance of GNNs often correlates with the availability and quality of node-level features in the input networks. However, for many network applications, such node-level information may be missing or unreliable, thereby limiting the applicability and efficacy of…
▽ More
Graph Neural Networks (GNNs) have shown remarkable merit in performing various learning-based tasks in complex networks. The superior performance of GNNs often correlates with the availability and quality of node-level features in the input networks. However, for many network applications, such node-level information may be missing or unreliable, thereby limiting the applicability and efficacy of GNNs. To address this limitation, we present a novel approach denoted as Ego-centric Spectral subGraph Embedding Augmentation (ESGEA), which aims to enhance and design node features, particularly in scenarios where information is lacking. Our method leverages the topological structure of the local subgraph to create topology-aware node features. The subgraph features are generated using an efficient spectral graph embedding technique, and they serve as node features that capture the local topological organization of the network. The explicit node features, if present, are then enhanced with the subgraph embeddings in order to improve the overall performance. ESGEA is compatible with any GNN-based architecture and is effective even in the absence of node features. We evaluate the proposed method in a social network graph classification task where node attributes are unavailable, as well as in a node classification task where node features are corrupted or even absent. The evaluation results on seven datasets and eight baseline models indicate up to a 10% improvement in AUC and a 7% improvement in accuracy for graph and node classification tasks, respectively.
△ Less
Submitted 10 October, 2023;
originally announced October 2023.
-
A Survey of Graph Unlearning
Authors:
Anwar Said,
Tyler Derr,
Mudassir Shabbir,
Waseem Abbas,
Xenofon Koutsoukos
Abstract:
Graph unlearning emerges as a crucial advancement in the pursuit of responsible AI, providing the means to remove sensitive data traces from trained models, thereby upholding the right to be forgotten. It is evident that graph machine learning exhibits sensitivity to data privacy and adversarial attacks, necessitating the application of graph unlearning techniques to address these concerns effecti…
▽ More
Graph unlearning emerges as a crucial advancement in the pursuit of responsible AI, providing the means to remove sensitive data traces from trained models, thereby upholding the right to be forgotten. It is evident that graph machine learning exhibits sensitivity to data privacy and adversarial attacks, necessitating the application of graph unlearning techniques to address these concerns effectively. In this comprehensive survey paper, we present the first systematic review of graph unlearning approaches, encompassing a diverse array of methodologies and offering a detailed taxonomy and up-to-date literature overview to facilitate the understanding of researchers new to this field. Additionally, we establish the vital connections between graph unlearning and differential privacy, augmenting our understanding of the relevance of privacy-preserving techniques in this context. To ensure clarity, we provide lucid explanations of the fundamental concepts and evaluation measures used in graph unlearning, catering to a broader audience with varying levels of expertise. Delving into potential applications, we explore the versatility of graph unlearning across various domains, including but not limited to social networks, adversarial settings, and resource-constrained environments like the Internet of Things (IoT), illustrating its potential impact in safeguarding data privacy and enhancing AI systems' robustness. Finally, we shed light on promising research directions, encouraging further progress and innovation within the domain of graph unlearning. By laying a solid foundation and fostering continued progress, this survey seeks to inspire researchers to further advance the field of graph unlearning, thereby instilling confidence in the ethical growth of AI systems and reinforcing the responsible application of machine learning techniques in various domains.
△ Less
Submitted 7 October, 2023; v1 submitted 23 August, 2023;
originally announced October 2023.
-
Controllability Backbone in Networks
Authors:
Obaid Ullah Ahmad,
Waseem Abbas,
Mudassir Shabbir
Abstract:
This paper studies the controllability backbone problem in dynamical networks defined over graphs. The main idea of the controllability backbone is to identify a small subset of edges in a given network such that any subnetwork containing those edges/links has at least the same network controllability as the original network while assuming the same set of input/leader vertices. We consider the str…
▽ More
This paper studies the controllability backbone problem in dynamical networks defined over graphs. The main idea of the controllability backbone is to identify a small subset of edges in a given network such that any subnetwork containing those edges/links has at least the same network controllability as the original network while assuming the same set of input/leader vertices. We consider the strong structural controllability (SSC) in our work, which is useful but computationally challenging. Thus, we utilize two lower bounds on the network's SSC based on the zero forcing notion and graph distances. We provide algorithms to compute controllability backbones while preserving these lower bounds. We thoroughly analyze the proposed algorithms and compute the number of edges in the controllability backbones. Finally, we compare and numerically evaluate our methods on random graphs.
△ Less
Submitted 5 September, 2023;
originally announced September 2023.
-
Computing Graph Descriptors on Edge Streams
Authors:
Zohair Raza Hassan,
Sarwan Ali,
Imdadullah Khan,
Mudassir Shabbir,
Waseem Abbas
Abstract:
Feature extraction is an essential task in graph analytics. These feature vectors, called graph descriptors, are used in downstream vector-space-based graph analysis models. This idea has proved fruitful in the past, with spectral-based graph descriptors providing state-of-the-art classification accuracy. However, known algorithms to compute meaningful descriptors do not scale to large graphs sinc…
▽ More
Feature extraction is an essential task in graph analytics. These feature vectors, called graph descriptors, are used in downstream vector-space-based graph analysis models. This idea has proved fruitful in the past, with spectral-based graph descriptors providing state-of-the-art classification accuracy. However, known algorithms to compute meaningful descriptors do not scale to large graphs since: (1) they require storing the entire graph in memory, and (2) the end-user has no control over the algorithm's runtime. In this paper, we present streaming algorithms to approximately compute three different graph descriptors capturing the essential structure of graphs. Operating on edge streams allows us to avoid storing the entire graph in memory, and controlling the sample size enables us to keep the runtime of our algorithms within desired bounds. We demonstrate the efficacy of the proposed descriptors by analyzing the approximation error and classification accuracy. Our scalable algorithms compute descriptors of graphs with millions of edges within minutes. Moreover, these descriptors yield predictive accuracy comparable to the state-of-the-art methods but can be computed using only 25% as much memory.
△ Less
Submitted 8 April, 2023; v1 submitted 2 September, 2021;
originally announced September 2021.
-
Edge Augmentation with Controllability Constraints in Directed Laplacian Networks
Authors:
Waseem Abbas,
Mudassir Shabbir,
Yasin Yazıcıoglu,
Xenofon Koutsoukos
Abstract:
In this paper, we study the maximum edge augmentation problem in directed Laplacian networks to improve their robustness while preserving lower bounds on their strong structural controllability (SSC). Since adding edges could adversely impact network controllability, the main objective is to maximally densify a given network by selectively adding missing edges while ensuring that SSC of the networ…
▽ More
In this paper, we study the maximum edge augmentation problem in directed Laplacian networks to improve their robustness while preserving lower bounds on their strong structural controllability (SSC). Since adding edges could adversely impact network controllability, the main objective is to maximally densify a given network by selectively adding missing edges while ensuring that SSC of the network does not deteriorate beyond certain levels specified by the SSC bounds. We consider two widely used bounds: first is based on the notion of zero forcing (ZF), and the second relies on the distances between nodes in a graph. We provide an edge augmentation algorithm that adds the maximum number of edges in a graph while preserving the ZF-based SSC bound, and also derive a closed-form expression for the exact number of edges added to the graph. Then, we examine the edge augmentation problem while preserving the distance-based bound and present a randomized algorithm that guarantees an approximate solution with high probability. Finally, we numerically evaluate and compare these edge augmentation solutions.
△ Less
Submitted 12 May, 2021;
originally announced May 2021.
-
Deep Learning based Joint Precoder Design and Antenna Selection for Partially Connected Hybrid Massive MIMO Systems
Authors:
Salman Khalid,
Waqas bin Abbas,
Farhan Khalid
Abstract:
Efficient resource allocation with hybrid precoder design is essential for massive MIMO systems operating in millimeter wave (mmW) domain. Owing to a higher energy efficiency and a lower complexity of a partially connected hybrid architecture, in this letter, we propose a joint deep convolutional neural network (CNN) based scheme for precoder design and antenna selection of a partially connected m…
▽ More
Efficient resource allocation with hybrid precoder design is essential for massive MIMO systems operating in millimeter wave (mmW) domain. Owing to a higher energy efficiency and a lower complexity of a partially connected hybrid architecture, in this letter, we propose a joint deep convolutional neural network (CNN) based scheme for precoder design and antenna selection of a partially connected massive MIMO hybrid system. Precoder design and antenna selection is formulated as a regression and classification problem, respectively, for CNN. The channel data is fed to the first CNN network which outputs a subset of selected antennas having the optimal spectral efficiency. This subset is again fed to the second CNN to obtain the block diagonal precoder for a partially connected architecture. Simulation results verifies the superiority of CNN based approach over conventional iterative and alternating minimization (alt-min) algorithms. Moreover, the proposed scheme is computationally efficient and is not very sensitive to channel irregularities.
△ Less
Submitted 2 February, 2021;
originally announced February 2021.
-
Byzantine Resilient Distributed Multi-Task Learning
Authors:
Jiani Li,
Waseem Abbas,
Xenofon Koutsoukos
Abstract:
Distributed multi-task learning provides significant advantages in multi-agent networks with heterogeneous data sources where agents aim to learn distinct but correlated models simultaneously.However, distributed algorithms for learning relatedness among tasks are not resilient in the presence of Byzantine agents. In this paper, we present an approach for Byzantine resilient distributed multi-task…
▽ More
Distributed multi-task learning provides significant advantages in multi-agent networks with heterogeneous data sources where agents aim to learn distinct but correlated models simultaneously.However, distributed algorithms for learning relatedness among tasks are not resilient in the presence of Byzantine agents. In this paper, we present an approach for Byzantine resilient distributed multi-task learning. We propose an efficient online weight assignment rule by measuring the accumulated loss using an agent's data and its neighbors' models. A small accumulated loss indicates a large similarity between the two tasks. In order to ensure the Byzantine resilience of the aggregation at a normal agent, we introduce a step for filtering out larger losses. We analyze the approach for convex models and show that normal agents converge resiliently towards the global minimum.Further, aggregation with the proposed weight assignment rule always results in an improved expected regret than the non-cooperative case. Finally, we demonstrate the approach using three case studies, including regression and classification problems, and show that our method exhibits good empirical performance for non-convex models, such as convolutional neural networks.
△ Less
Submitted 7 January, 2021; v1 submitted 25 October, 2020;
originally announced October 2020.
-
User Selection in Millimeter Wave Massive MIMO System using Convolutional Neural Networks
Authors:
Salman Khalid,
Waqas bin Abbas,
Farhan Khalid,
Michele Zorzi
Abstract:
A hybrid architecture for millimeter wave (mmW) massive MIMO systems is considered practically implementable due to low power consumption and high energy efficiency. However, due to the limited number of RF chains, user selection becomes necessary for such architecture. Traditional user selection algorithms suffer from high computational complexity and, therefore, may not be scalable in 5G and bey…
▽ More
A hybrid architecture for millimeter wave (mmW) massive MIMO systems is considered practically implementable due to low power consumption and high energy efficiency. However, due to the limited number of RF chains, user selection becomes necessary for such architecture. Traditional user selection algorithms suffer from high computational complexity and, therefore, may not be scalable in 5G and beyond wireless mobile communications. To address this issue, in this letter we propose a low complexity CNN framework for user selection. The proposed CNN accepts as input the channel matrix and gives as output the selected users. Simulation results show that the proposed CNN performs close to optimal exhaustive search in terms of achievable rate, with negligible computational complexity. In addition, CNN based user selection outperforms the evolutionary algorithm and the greedy algorithm in terms of both achievable rate and computational complexity. Finally, simulation results also show that the proposed CNN based user selection scheme is robust to channel imperfections.
△ Less
Submitted 30 June, 2020;
originally announced June 2020.
-
Resilient Distributed Diffusion in Networks with Adversaries
Authors:
Jiani Li,
Waseem Abbas,
Xenofon Koutsoukos
Abstract:
In this paper, we study resilient distributed diffusion for multi-task estimation in the presence of adversaries where networked agents must estimate distinct but correlated states of interest by processing streaming data. We show that in general diffusion strategies are not resilient to malicious agents that do not adhere to the diffusion-based information processing rules. In particular, by expl…
▽ More
In this paper, we study resilient distributed diffusion for multi-task estimation in the presence of adversaries where networked agents must estimate distinct but correlated states of interest by processing streaming data. We show that in general diffusion strategies are not resilient to malicious agents that do not adhere to the diffusion-based information processing rules. In particular, by exploiting the adaptive weights used for diffusing information, we develop time-dependent attack models that drive normal agents to converge to states selected by the attacker. We show that an attacker that has complete knowledge of the system can always drive its targeted agents to its desired estimates. Moreover, an attacker that does not have complete knowledge of the system including streaming data of targeted agents or the parameters they use in diffusion algorithms, can still be successful in deploying an attack by approximating the needed information. The attack models can be used for both stationary and non-stationary state estimation.In addition, we present and analyze a resilient distributed diffusion algorithm that is resilient to any data falsification attack in which the number of compromised agents in the local neighborhood of a normal agent is bounded. The proposed algorithm guarantees that all normal agents converge to their true target states if appropriate parameters are selected. We also analyze trade-off between the resilience of distributed diffusion and its performance in terms of steady-state mean-square-deviation (MSD) from the correct estimates. Finally, we evaluate the proposed attack models and resilient distributed diffusion algorithm using stationary and non-stationary multi-target localization.
△ Less
Submitted 23 March, 2020;
originally announced March 2020.
-
Estimating Descriptors for Large Graphs
Authors:
Zohair Raza Hassan,
Mudassir Shabbir,
Imdadullah Khan,
Waseem Abbas
Abstract:
Embedding networks into a fixed dimensional feature space, while preserving its essential structural properties is a fundamental task in graph analytics. These feature vectors (graph descriptors) are used to measure the pairwise similarity between graphs. This enables applying data mining algorithms (e.g classification, clustering, or anomaly detection) on graph-structured data which have numerous…
▽ More
Embedding networks into a fixed dimensional feature space, while preserving its essential structural properties is a fundamental task in graph analytics. These feature vectors (graph descriptors) are used to measure the pairwise similarity between graphs. This enables applying data mining algorithms (e.g classification, clustering, or anomaly detection) on graph-structured data which have numerous applications in multiple domains. State-of-the-art algorithms for computing descriptors require the entire graph to be in memory, entailing a huge memory footprint, and thus do not scale well to increasing sizes of real-world networks. In this work, we propose streaming algorithms to efficiently approximate descriptors by estimating counts of sub-graphs of order $k\leq 4$, and thereby devise extensions of two existing graph comparison paradigms: the Graphlet Kernel and NetSimile. Our algorithms require a single scan over the edge stream, have space complexity that is a fraction of the input size, and approximate embeddings via a simple sampling scheme. Our design exploits the trade-off between available memory and estimation accuracy to provide a method that works well for limited memory requirements. We perform extensive experiments on real-world networks and demonstrate that our algorithms scale well to massive graphs.
△ Less
Submitted 19 February, 2020; v1 submitted 28 January, 2020;
originally announced January 2020.
-
Patch-based Generative Adversarial Network Towards Retinal Vessel Segmentation
Authors:
Waseem Abbas,
Muhammad Haroon Shakeel,
Numan Khurshid,
Murtaza Taj
Abstract:
Retinal blood vessels are considered to be the reliable diagnostic biomarkers of ophthalmologic and diabetic retinopathy. Monitoring and diagnosis totally depends on expert analysis of both thin and thick retinal vessels which has recently been carried out by various artificial intelligent techniques. Existing deep learning methods attempt to segment retinal vessels using a unified loss function o…
▽ More
Retinal blood vessels are considered to be the reliable diagnostic biomarkers of ophthalmologic and diabetic retinopathy. Monitoring and diagnosis totally depends on expert analysis of both thin and thick retinal vessels which has recently been carried out by various artificial intelligent techniques. Existing deep learning methods attempt to segment retinal vessels using a unified loss function optimized for both thin and thick vessels with equal importance. Due to variable thickness, biased distribution, and difference in spatial features of thin and thick vessels, unified loss function are more influential towards identification of thick vessels resulting in weak segmentation. To address this problem, a conditional patch-based generative adversarial network is proposed which utilizes a generator network and a patch-based discriminator network conditioned on the sample data with an additional loss function to learn both thin and thick vessels. Experiments are conducted on publicly available STARE and DRIVE datasets which show that the proposed model outperforms the state-of-the-art methods.
△ Less
Submitted 21 December, 2019;
originally announced December 2019.
-
Leveraging Diversity for Achieving Resilient Consensus in Sparse Networks
Authors:
Faiq Ghawash,
Waseem Abbas
Abstract:
A networked system can be made resilient against adversaries and attacks if the underlying network graph is structurally robust. For instance, to achieve distributed consensus in the presence of adversaries, the underlying network graph needs to satisfy certain robustness conditions. A typical approach to making networks structurally robust is to strategically add extra links between nodes, which…
▽ More
A networked system can be made resilient against adversaries and attacks if the underlying network graph is structurally robust. For instance, to achieve distributed consensus in the presence of adversaries, the underlying network graph needs to satisfy certain robustness conditions. A typical approach to making networks structurally robust is to strategically add extra links between nodes, which might be prohibitively expensive. In this paper, we propose an alternative way of improving network's robustness, that is by considering heterogeneity of nodes. Nodes in a network can be of different types and can have multiple variants. As a result, different nodes can have disjoint sets of vulnerabilities, which means that an attacker can only compromise a particular type of nodes by exploiting a particular vulnerability. We show that, by such a diversification of nodes, attacker's ability to change the underlying network structure is significantly reduced. Consequently, even a sparse network with heterogeneous nodes can exhibit the properties of a structurally robust network. Using these ideas, we propose a distributed control policy that utilizes heterogeneity in the network to achieve resilient consensus in adversarial environment. We extend the notion of $(r,s)$-robustness to incorporate the diversity of nodes and provide necessary and sufficient conditions to guarantee resilient distributed consensus in heterogeneous networks. Finally we study the properties and construction of robust graphs with heterogeneous nodes.
△ Less
Submitted 24 July, 2019;
originally announced July 2019.
-
Locomotion and gesture tracking in mice and small animals for neurosceince applications: A survey
Authors:
Waseem Abbas,
David Masip Rodo
Abstract:
Neuroscience has traditionally relied on manually observing lab animals in controlled environments. Researchers usually record animals behaving in free or restrained manner and then annotate the data manually. The manual annotation is not desirable for three reasons; one, it is time consuming, two, it is prone to human errors and three, no two human annotators will 100\% agree on annotation, so it…
▽ More
Neuroscience has traditionally relied on manually observing lab animals in controlled environments. Researchers usually record animals behaving in free or restrained manner and then annotate the data manually. The manual annotation is not desirable for three reasons; one, it is time consuming, two, it is prone to human errors and three, no two human annotators will 100\% agree on annotation, so it is not reproducible. Consequently, automated annotation of such data has gained traction because it is efficient and replicable. Usually, the automatic annotation of neuroscience data relies on computer vision and machine leaning techniques. In this article, we have covered most of the approaches taken by researchers for locomotion and gesture tracking of lab animals. We have divided these papers in categories based upon the hardware they use and the software approach they take. We also have summarized their strengths and weaknesses.
△ Less
Submitted 25 March, 2019;
originally announced March 2019.
-
Millimeter Wave Receiver Comparison Under Energy vs Spectral Efficiency Trade-off
Authors:
Waqas bin Abbas,
Felipe Gomez-Cuba,
Michele Zorzi
Abstract:
Receivers for mmWave systems suffer from high power consumption in Analog to Digital Converters (ADC), and there is a need to compare the three major receiver architectures: Analog, Hybrid and Digital Combining (AC, HC and DC). Moreover, the specific power consumption figure of merit of ADCs varies significantly between different component designs in the literature, so that comparisons performed f…
▽ More
Receivers for mmWave systems suffer from high power consumption in Analog to Digital Converters (ADC), and there is a need to compare the three major receiver architectures: Analog, Hybrid and Digital Combining (AC, HC and DC). Moreover, the specific power consumption figure of merit of ADCs varies significantly between different component designs in the literature, so that comparisons performed for one ADC model - no matter how representative of the state of the art - do not necessarily carry over to other ADC designs with different figures of merit. In this work, we formulate a comparison method between AC, HC and DC that can be easily reproduced with different power consumption parameters and provides all information for receiver architecture selection in a compact chart figure. We also present an interpretation of the receiver selection decision problem as a multi-objective utility optimization to find the best Spectral Efficiency (SE) versus Energy Efficiency (EE) trade-off. We use existing results on the achievable rate of AC, HC and DC systems and an Additive Quantization Noise Model (AQNM) of the ADC capacity degradation. For some example commercial component parameters, we show that the usually held belief that DC requires the highest power is not valid in many cases. Rather, either DC or HC alternatively result in the better SE vs EE trade-off depending strongly on the considered component parameters and on the weight assigned to SE vs EE in the utility maximization.
△ Less
Submitted 28 January, 2019; v1 submitted 30 November, 2018;
originally announced November 2018.
-
Synergistic Security for the Industrial Internet of Things: Integrating Redundancy, Diversity, and Hardening
Authors:
Aron Laszka,
Waseem Abbas,
Yevgeniy Vorobeychik,
Xenofon Koutsoukos
Abstract:
As the Industrial Internet of Things (IIot) becomes more prevalent in critical application domains, ensuring security and resilience in the face of cyber-attacks is becoming an issue of paramount importance. Cyber-attacks against critical infrastructures, for example, against smart water-distribution and transportation systems, pose serious threats to public health and safety. Owing to the severit…
▽ More
As the Industrial Internet of Things (IIot) becomes more prevalent in critical application domains, ensuring security and resilience in the face of cyber-attacks is becoming an issue of paramount importance. Cyber-attacks against critical infrastructures, for example, against smart water-distribution and transportation systems, pose serious threats to public health and safety. Owing to the severity of these threats, a variety of security techniques are available. However, no single technique can address the whole spectrum of cyber-attacks that may be launched by a determined and resourceful attacker. In light of this, we consider a multi-pronged approach for designing secure and resilient IIoT systems, which integrates redundancy, diversity, and hardening techniques. We introduce a framework for quantifying cyber-security risks and optimizing IIoT design by determining security investments in redundancy, diversity, and hardening. To demonstrate the applicability of our framework, we present two case studies in water distribution and transportation a case study in water-distribution systems. Our numerical evaluation shows that integrating redundancy, diversity, and hardening can lead to reduced security risk at the same cost.
△ Less
Submitted 27 August, 2018;
originally announced August 2018.
-
Detection and Mitigation of Attacks on Transportation Networks as a Multi-Stage Security Game
Authors:
Aron Laszka,
Waseem Abbas,
Yevgeniy Vorobeychik,
Xenofon Koutsoukos
Abstract:
In recent years, state-of-the-art traffic-control devices have evolved from standalone hardware to networked smart devices. Smart traffic control enables operators to decrease traffic congestion and environmental impact by acquiring real-time traffic data and changing traffic signals from fixed to adaptive schedules. However, these capabilities have inadvertently exposed traffic control to a wide…
▽ More
In recent years, state-of-the-art traffic-control devices have evolved from standalone hardware to networked smart devices. Smart traffic control enables operators to decrease traffic congestion and environmental impact by acquiring real-time traffic data and changing traffic signals from fixed to adaptive schedules. However, these capabilities have inadvertently exposed traffic control to a wide range of cyber-attacks, which adversaries can easily mount through wireless networks or even through the Internet. Indeed, recent studies have found that a large number of traffic signals that are deployed in practice suffer from exploitable vulnerabilities, which adversaries may use to take control of the devices. Thanks to the hardware-based failsafes that most devices employ, adversaries cannot cause traffic accidents directly by setting compromised signals to dangerous configurations. Nonetheless, an adversary could cause disastrous traffic congestion by changing the schedule of compromised traffic signals, thereby effectively crippling the transportation network. To provide theoretical foundations for the protection of transportation networks from these attacks, we introduce a game-theoretic model of launching, detecting, and mitigating attacks that tamper with traffic-signal schedules. We show that finding optimal strategies is a computationally challenging problem, and we propose efficient heuristic algorithms for finding near optimal strategies. We also introduce a Gaussian-process based anomaly detector, which can alert operators to ongoing attacks. Finally, we evaluate our algorithms and the proposed detector using numerical experiments based on the SUMO traffic simulator.
△ Less
Submitted 2 August, 2019; v1 submitted 24 August, 2018;
originally announced August 2018.
-
Soft Computing Techniques for Dependable Cyber-Physical Systems
Authors:
Muhammad Atif,
Siddique Latif,
Rizwan Ahmad,
Adnan Khalid Kiani,
Junaid Qadir,
Adeel Baig,
Hisao Ishibuchi,
Waseem Abbas
Abstract:
Cyber-Physical Systems (CPS) allow us to manipulate objects in the physical world by providing a communication bridge between computation and actuation elements. In the current scheme of things, this sought-after control is marred by limitations inherent in the underlying communication network(s) as well as by the uncertainty found in the physical world. These limitations hamper fine-grained contr…
▽ More
Cyber-Physical Systems (CPS) allow us to manipulate objects in the physical world by providing a communication bridge between computation and actuation elements. In the current scheme of things, this sought-after control is marred by limitations inherent in the underlying communication network(s) as well as by the uncertainty found in the physical world. These limitations hamper fine-grained control of elements that may be separated by large-scale distances. In this regard, soft computing is an emerging paradigm that can help to overcome the vulnerabilities, and unreliability of CPS by using techniques including fuzzy systems, neural network, evolutionary computation, probabilistic reasoning and rough sets. In this paper, we present a comprehensive contemporary review of soft computing techniques for CPS dependability modeling, analysis, and improvement. This paper provides an overview of CPS applications, explores the foundations of dependability engineering, and highlights the potential role of soft computing techniques for CPS dependability with various case studies, while identifying common pitfalls and future directions. In addition, this paper provides a comprehensive survey on the use of various soft computing techniques for making CPS dependable.
△ Less
Submitted 27 July, 2020; v1 submitted 25 January, 2018;
originally announced January 2018.
-
Bit Allocation for Increased Power Efficiency in 5G Receivers with Variable-Resolution ADCs
Authors:
Waqas bin Abbas,
Felipe Gomez-Cuba,
Michele Zorzi
Abstract:
In future high-capacity wireless systems based on mmWave or massive multiple input multiple output (MIMO), the power consumption of receiver Analog to Digital Converters (ADC) is a concern. Although hybrid or analog systems with fewer ADCs have been proposed, fully digital receivers with many lower resolution ADCs (and lower power) may be a more versatile solution. In this paper, focusing on an up…
▽ More
In future high-capacity wireless systems based on mmWave or massive multiple input multiple output (MIMO), the power consumption of receiver Analog to Digital Converters (ADC) is a concern. Although hybrid or analog systems with fewer ADCs have been proposed, fully digital receivers with many lower resolution ADCs (and lower power) may be a more versatile solution. In this paper, focusing on an uplink scenario, we propose to take the optimization of ADC resolution one step further by enabling variable resolutions in the ADCs that sample the signal received at each antenna. This allows to give more bits to the antennas that capture the strongest incoming signal and fewer bits to the antennas that capture little signal energy and mostly noise. Simulation results show that, depending on the unquantized link SNR, a power saving in the order of 20-80% can be obtained by our variable resolution proposal in comparison with a reference fully digital receiver with a fixed low number of bits in all its ADCs.
△ Less
Submitted 28 January, 2019; v1 submitted 29 October, 2016;
originally announced October 2016.
-
Scheduling Resource-Bounded Monitoring Devices for Event Detection and Isolation in Networks
Authors:
Waseem Abbas,
Aron Laszka,
Yevgeniy Vorobeychik,
Xenofon Koutsoukos
Abstract:
In networked systems, monitoring devices such as sensors are typically deployed to monitor various target locations. Targets are the points in the physical space at which events of some interest, such as random faults or attacks, can occur. Most often, these devices have limited energy supplies, and they can operate for a limited duration. As a result, energy-efficient monitoring of various target…
▽ More
In networked systems, monitoring devices such as sensors are typically deployed to monitor various target locations. Targets are the points in the physical space at which events of some interest, such as random faults or attacks, can occur. Most often, these devices have limited energy supplies, and they can operate for a limited duration. As a result, energy-efficient monitoring of various target locations through a set of monitoring devices with limited energy supplies is a crucial problem in networked systems. In this paper, we study optimal scheduling of monitoring devices to maximize network coverage for detecting and isolating events on targets for a given network lifetime. The monitoring devices considered could remain active only for a fraction of the overall network lifetime. We formulate the problem of scheduling of monitoring devices as a graph labeling problem, which unlike other existing solutions, allows us to directly utilize the underlying network structure to explore the trade-off between coverage and network lifetime. In this direction, first we propose a greedy heuristic to solve the graph labeling problem, and then provide a game-theoretic solution to achieve near optimal graph labeling. Moreover, the proposed setup can be used to simultaneously solve the scheduling and placement of monitoring devices, which yields improved performance as compared to separately solving the placement and scheduling problems. Finally, we illustrate our results on various networks, including real-world water distribution networks.
△ Less
Submitted 25 August, 2016;
originally announced August 2016.
-
Graph Distances and Controllability of Networks
Authors:
A. Yasin Yazicioglu,
Waseem Abbas,
Magnus Egerstedt
Abstract:
In this technical note, we study the controllability of diffusively coupled networks from a graph theoretic perspective. We consider leader-follower networks, where the external control inputs are injected to only some of the agents, namely the leaders. Our main result relates the controllability of such systems to the graph distances between the agents. More specifically, we present a graph topol…
▽ More
In this technical note, we study the controllability of diffusively coupled networks from a graph theoretic perspective. We consider leader-follower networks, where the external control inputs are injected to only some of the agents, namely the leaders. Our main result relates the controllability of such systems to the graph distances between the agents. More specifically, we present a graph topological lower bound on the rank of the controllability matrix. This lower bound is tight, and it is applicable to systems with arbitrary network topologies, coupling weights, and number of leaders. An algorithm for computing the lower bound is also provided. Furthermore, as a prominent application, we present how the proposed bound can be utilized to select a minimal set of leaders for achieving controllability, even when the coupling weights are unknown.
△ Less
Submitted 15 August, 2016;
originally announced August 2016.
-
Millimeter Wave Receiver Efficiency: A Comprehensive Comparison of Beamforming Schemes with Low Resolution ADCs
Authors:
Waqas bin Abbas,
Felipe Gomez-Cuba,
Michele Zorzi
Abstract:
In this work, we study the achievable rate and the energy efficiency of Analog, Hybrid and Digital Combining (AC, HC and DC) for millimeter wave (mmW) receivers. We take into account the power consumption of all receiver components, not just Analog-to-Digital Converters (ADC), determine some practical limitations of beamforming in each architecture, and develop performance analysis charts that ena…
▽ More
In this work, we study the achievable rate and the energy efficiency of Analog, Hybrid and Digital Combining (AC, HC and DC) for millimeter wave (mmW) receivers. We take into account the power consumption of all receiver components, not just Analog-to-Digital Converters (ADC), determine some practical limitations of beamforming in each architecture, and develop performance analysis charts that enable comparison of different receivers simultaneously in terms of two metrics, namely, Spectral Efficiency (SE) and Energy Efficiency (EE). We present a multi-objective utility optimization interpretation to find the best SE-EE weighted trade-off among AC, DC and HC schemes. We consider an Additive Quantization Noise Model (AQNM) to evaluate the achievable rates with low resolution ADCs. Our analysis shows that AC is only advantageous if the channel rank is strictly one, the link has very low SNR, or there is a very stringent low power constraint at the receiver. Otherwise, we show that the usual claim that DC requires the highest power is not universally valid. Rather, either DC or HC alternatively result in the better SE vs EE trade-off depending strongly on the considered power consumption characteristic values for each component of the mmW receiver.
△ Less
Submitted 20 February, 2020; v1 submitted 13 July, 2016;
originally announced July 2016.
-
Optimal Thresholds for Anomaly-Based Intrusion Detection in Dynamical Environments
Authors:
Amin Ghafouri,
Waseem Abbas,
Aron Laszka,
Yevgeniy Vorobeychik,
Xenofon Koutsoukos
Abstract:
In cyber-physical systems, malicious and resourceful attackers could penetrate the system through cyber means and cause significant physical damage. Consequently, detection of such attacks becomes integral towards making these systems resilient to attacks. To achieve this objective, intrusion detection systems (IDS) that are able to detect malicious behavior can be deployed. However, practical IDS…
▽ More
In cyber-physical systems, malicious and resourceful attackers could penetrate the system through cyber means and cause significant physical damage. Consequently, detection of such attacks becomes integral towards making these systems resilient to attacks. To achieve this objective, intrusion detection systems (IDS) that are able to detect malicious behavior can be deployed. However, practical IDS are imperfect and sometimes they may produce false alarms for a normal system behavior. Since alarms need to be investigated for any potential damage, a large number of false alarms may increase the operational costs significantly. Thus, IDS need to be configured properly, as oversensitive IDS could detect attacks early but at the cost of a higher number of false alarms. Similarly, IDS with low sensitivity could reduce the false alarms while increasing the time to detect the attacks. The configuration of IDS to strike the right balance between time to detecting attacks and the rate of false positives is a challenging task, especially in dynamic environments, in which the damage incurred by a successful attack is time-varying.
In this paper, we study the problem of finding optimal detection thresholds for anomaly-based detectors implemented in dynamical systems in the face of strategic attacks. We formulate the problem as an attacker-defender security game, and determine thresholds for the detector to achieve an optimal trade-off between the detection delay and the false positive rates. In this direction, first, we provide an algorithm that computes optimal fixed threshold that remains fixed throughout. Second, we allow detector's threshold to change with time to further minimize the defender's loss and provide an algorithm to compute time-varying thresholds, which we call adaptive thresholds. Finally, we numerically evaluate our results using a water distribution network as a case-study.
△ Less
Submitted 8 February, 2017; v1 submitted 21 June, 2016;
originally announced June 2016.
-
Vulnerability of Fixed-Time Control of Signalized Intersections to Cyber-Tampering
Authors:
Amin Ghafouri,
Waseem Abbas,
Yevgeniy Vorobeychik,
Xenofon Koutsoukos
Abstract:
Recent experimental studies have shown that traffic management systems are vulnerable to cyber-attacks on sensor data. This paper studies the vulnerability of fixed-time control of signalized intersections when sensors measuring traffic flow information are compromised and perturbed by an adversary. The problems are formulated by considering three malicious objectives: 1) worst-case network accumu…
▽ More
Recent experimental studies have shown that traffic management systems are vulnerable to cyber-attacks on sensor data. This paper studies the vulnerability of fixed-time control of signalized intersections when sensors measuring traffic flow information are compromised and perturbed by an adversary. The problems are formulated by considering three malicious objectives: 1) worst-case network accumulation, which aims to destabilize the overall network as much as possible; 2) worst-case lane accumulation, which aims to cause worst-case accumulation on some target lanes; and 3) risk-averse target accumulation, which aims to reach a target accumulation by making the minimum perturbation to sensor data. The problems are solved using bilevel programming optimization methods. Finally, a case study of a real network is used to illustrate the results.
△ Less
Submitted 8 February, 2017; v1 submitted 21 June, 2016;
originally announced June 2016.
-
Context Information Based Initial Cell Search for Millimeter Wave 5G Cellular Networks
Authors:
Waqas Bin Abbas,
Michele Zorzi
Abstract:
Millimeter wave (mmWave) communication is envisioned as a cornerstone to fulfill the data rate requirements for fifth generation (5G) cellular networks. In mmWave communication, beamforming is considered as a key technology to combat the high path-loss, and unlike in conventional microwave communication, beamforming may be necessary even during initial access/cell search. Among the proposed beamfo…
▽ More
Millimeter wave (mmWave) communication is envisioned as a cornerstone to fulfill the data rate requirements for fifth generation (5G) cellular networks. In mmWave communication, beamforming is considered as a key technology to combat the high path-loss, and unlike in conventional microwave communication, beamforming may be necessary even during initial access/cell search. Among the proposed beamforming schemes for initial cell search, analog beamforming is a power efficient approach but suffers from its inherent search delay during initial access. In this work, we argue that analog beamforming can still be a viable choice when context information about mmWave base stations (BS) is available at the mobile station (MS). We then study how the performance of analog beamforming degrades in case of angular errors in the available context information. Finally, we present an analog beamforming receiver architecture that uses multiple arrays of Phase Shifters and a single RF chain to combat the effect of angular errors, showing that it can achieve the same performance as hybrid beamforming.
△ Less
Submitted 6 May, 2016;
originally announced May 2016.
-
Towards an Appropriate Beamforming Scheme for Initial Cell Discovery in mmW 5G Cellular Networks
Authors:
Waqas bin Abbas,
Michele Zorzi
Abstract:
Beamforming is an essential requirement to combat high pathloss and to improve signal-to-noise ratio during initial cell discovery in future millimeter wave cellular networks. The choice of an appropriate beamforming is directly coupled with its energy consumption. The energy consumption is even of more concern at a battery limited mobile station (MS). In this work, we provide an energy consumptio…
▽ More
Beamforming is an essential requirement to combat high pathloss and to improve signal-to-noise ratio during initial cell discovery in future millimeter wave cellular networks. The choice of an appropriate beamforming is directly coupled with its energy consumption. The energy consumption is even of more concern at a battery limited mobile station (MS). In this work, we provide an energy consumption based comparison of different beamforming schemes while considering both a low power and a high power analog-to-digital converter (ADC) for a millimeter wave based receiver at the MS. We analyze both context information (CI) (GPS positioning based) and non context information based schemes, and show that analog beamforming with CI (where mobile station's positioning information is already available) can result in a lower energy consumption, while in all other scenarios digital beamforming has a lower energy consumption than analog and hybrid beamforming. We also show that under certain scenarios recently proposed phase shifters network architecture can result in a lower energy consumption than other beamforming schemes. Moreover, we show that the energy consumption trend among different beamforming schemes is valid irrespective of the number of ADC bits. Finally, we propose a new signaling structure which utilizes a relatively higher frequency sub-carrier for primary synchronization signals compared to other signaling, which allows a further reduction in initial cell search delay and energy consumption of the MS.
△ Less
Submitted 2 May, 2016;
originally announced May 2016.
-
Towards an Appropriate Receiver Beamforming Scheme for Millimeter Wave Communication: A Power Consumption Based Comparison
Authors:
Waqas Bin Abbas,
Michele Zorzi
Abstract:
At millimeter wave (mmW) frequencies, beamforming and large antenna arrays are an essential requirement to combat the high path loss for mmW communication. Moreover, at these frequencies, very large bandwidths are available to fulfill the data rate requirements of future wireless networks. However, utilization of these large bandwidths and of large antenna arrays can result in a high power consump…
▽ More
At millimeter wave (mmW) frequencies, beamforming and large antenna arrays are an essential requirement to combat the high path loss for mmW communication. Moreover, at these frequencies, very large bandwidths are available to fulfill the data rate requirements of future wireless networks. However, utilization of these large bandwidths and of large antenna arrays can result in a high power consumption which is an even bigger concern for mmW receiver design. In a mmW receiver, the analog-to-digital converter (ADC) is generally considered as the most power consuming block. In this paper, primarily focusing on the ADC power, we analyze and compare the total power consumption of the complete analog chain for Analog, Digital and Hybrid beamforming (ABF, DBF and HBF) based receiver design. We show how power consumption of these beamforming schemes varies with a change in the number of antennas, the number of ADC bits (b) and the bandwidth (B). Moreover, we compare low power (as in [1]) and high power (as in [2]) ADC models, and show that for a certain range of number of antennas, b and B, DBF may actually have a comparable and lower power consumption than ABF and HBF, respectively. In addition, we also show how the choice of an appropriate beamforming scheme depends on the signal-to-noise ratio regime.
△ Less
Submitted 18 April, 2016;
originally announced April 2016.
-
Guarding Networks Through Heterogeneous Mobile Guards
Authors:
Waseem Abbas,
Sajal Bhatia,
Xenofon Koutsoukos
Abstract:
In this article, the issue of guarding multi-agent systems against a sequence of intruder attacks through mobile heterogeneous guards (guards with different ranges) is discussed. The article makes use of graph theoretic abstractions of such systems in which agents are the nodes of a graph and edges represent interconnections between agents. Guards represent specialized mobile agents on specific no…
▽ More
In this article, the issue of guarding multi-agent systems against a sequence of intruder attacks through mobile heterogeneous guards (guards with different ranges) is discussed. The article makes use of graph theoretic abstractions of such systems in which agents are the nodes of a graph and edges represent interconnections between agents. Guards represent specialized mobile agents on specific nodes with capabilities to successfully detect and respond to an attack within their guarding range. Using this abstraction, the article addresses the problem in the context of eternal security problem in graphs. Eternal security refers to securing all the nodes in a graph against an infinite sequence of intruder attacks by a certain minimum number of guards. This paper makes use of heterogeneous guards and addresses all the components of the eternal security problem including the number of guards, their deployment and movement strategies. In the proposed solution, a graph is decomposed into clusters and a guard with appropriate range is then assigned to each cluster. These guards ensure that all nodes within their corresponding cluster are being protected at all times, thereby achieving the eternal security in the graph.
△ Less
Submitted 15 March, 2015;
originally announced March 2015.