Enhancing Network Security and Privacy Using Graph-Theoretic Characteristics

Abstract

Today, governments, businesses, and the critical infrastructure are facing cyberattacks of increasing frequency, intensity, and complexity. With the widespread use of sensitive data in applications such as social network based systems and enterprise systems, the chances of breaching the privacy of individuals and corporations have increased. It has thus become essential to protect networks and data from security threats and privacy leakage. Towards this end, an important line of research has focused on enhancing security and privacy using the analysis of graphs, such as social graphs in reputation systems and anonymous communication systems, and causal dependency graphs in enterprise forensic systems. In this thesis, we explore solutions to the limitations of two widely adopted graph analytics techniques in security and privacy applications, i.e., analysis of trust relationships in social graphs and causal relationships in dependency graphs. We observe that classical paradigms for graph analytics, such as the use of random walks on social graphs and the use of breadth-rst search on dependency graphs, have induced poor trade-offs between security/privacy and functionality due to the lack of exibility. Our insight is that leveraging graph-theoretic characteristics and machine learning techniques, we can make the conventional paradigms adaptive to improve the security/privacy without harming the utility. We present three systems for network security and privacy based on our advanced graph analytics: i) we introduce an adaptive random walk algorithm that uses a heterogeneous random walk length across nodes in a graph based on their local structural characteristics. Based on this algorithm, we propose SmartWalk, a security enhancing system which incorporates adaptive random walks in social network security applications. ii) We introduce a prioritized search algorithm that considers the topological properties of nodes in a graph to accelerate the search. Based on this algorithm, we propose PrioTracker, a backward and forward causality tracker that automatically prioritizes the search for abnormal causal dependencies within a time constraint. iii) We introduce an interruptible context-based prioritized search algorithm that propagates and re-assesses node priorities by uncovering the paths between nodes on a graph. Based on this algorithm, we propose RAPID, an automated real-time alert triage system that helps scale up the alarm processing capability in enterprises. Using multiple real-world datasets, we show that these three systems are able to improve the trade-off between security/privacy and utility by at least one order of magnitude. Two of our proposed systems, PrioTracker and RAPID, have been deployed in real-world enterprises.