Songlei Wang and Yifeng Zheng, Harbin Institute of Technology; Xiaohua Jia, Harbin Institute of Technology and City University of Hong Kong
Streaming graphs have seen wide adoption in diverse scenarios due to their superior ability to capture temporal interactions among entities. With the proliferation of cloud computing, it has become increasingly common to utilize the cloud for storing and querying streaming graphs. Among others, streaming graphs-based time-constrained pattern detection, which aims to continuously detect subgraphs matching a given query pattern within a sliding time window, benefits various applications such as credit card fraud detection and cyber-attack detection. Deploying such services on the cloud, however, entails severe security and privacy risks. This paper presents GraphGuard, the first system for privacy-preserving outsourcing of time-constrained pattern detection over streaming graphs. GraphGuard is constructed from a customized synergy of insights on graph modeling, lightweight secret sharing, edge differential privacy, and data encoding and padding, safeguarding the confidentiality of edge/vertex labels and the connections between vertices in the streaming graph and query patterns. We implement and evaluate GraphGuard on several real-world graph datasets. The evaluation results show that GraphGuard takes only a few seconds to securely process an encrypted query pattern over an encrypted snapshot of streaming graphs within a time window of size 50,000. Compared to a baseline built on generic secure multiparty computation, GraphGuard achieves up to 60× improvement in query latency and up to 98% savings in communication.
Open Access Media
USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.
![](https://www.usenix.org/sites/all/modules/usenix/usenix_files/images/usenix-locked.png)
author = {Songlei Wang and Yifeng Zheng and Xiaohua Jia},
title = {{GraphGuard}: Private {Time-Constrained} Pattern Detection Over Streaming Graphs in the Cloud},
booktitle = {33rd USENIX Security Symposium (USENIX Security 24)},
year = {2024},
isbn = {978-1-939133-44-1},
address = {Philadelphia, PA},
pages = {3495--3512},
url = {https://www.usenix.org/conference/usenixsecurity24/presentation/wang-songlei},
publisher = {USENIX Association},
month = aug
}