Date of Award
8-22-2025
Date Published
September 2025
Degree Type
Thesis
Degree Name
Master of Science (MS)
Department
Electrical Engineering and Computer Science
Advisor(s)
Sucheta Soundarajan
Subject Categories
Computer Sciences | Physical Sciences and Mathematics
Abstract
In many network applications, it is critical to protect sensitive nodes from discovery by malicious crawlers. This thesis addresses the network protection problem from the data protector’s perspective, focusing on strategically deleting edges to hide target nodes from entry-point attacks. Earlier work on this problem proposed node-level scores to identify key edges for deletion. We propose two novel edge-level scoring functions to identify critical edges for removal: the Shortest Path Change Score (SPCS), which quantifies the damage an edge’s removal causes to shortest paths, and the PageRank Edge Flow Score (PEFS), which estimates an edge’s usage in random walks from source to target nodes. SPCS is designed to be effective against expansion-based crawlers like breadth first search (BFS), while PEFS is suited for protection against random walk (RW) crawlers. A key limitation of existing methods is that edge scores become stale as the graph is modified. To address this, we introduce an adaptive and dynamic edge deletion strategy that periodically assesses its own performance. By using metrics such as Shortest Path Cut Congestion and Conductance, our algorithm recomputes edge scores only when it detects that the current strategy is no longer effective, improving both accuracy and efficiency. We conducted extensive experiments on four real-world graph datasets, comparing our methods against baselines. The results demonstrate that our proposed edge-level scoring functions and the adaptive deletion strategy significantly outperform existing methods in making it more difficult for crawlers to locate target nodes.
Access
Open Access
Recommended Citation
Mishra, Shivani, "Protecting Networks Against Entry-Point Attacks" (2025). Theses - ALL. 988.
https://surface.syr.edu/thesis/988
