FlowMatrix: GPU-Assisted Information-Flow Analysis through Matrix-Based Representation


Kaihang Ji, Jun Zeng, Yuancheng Jiang, and Zhenkai Liang, National University of Singapore; Zheng Leong Chua, Independent Researcher; Prateek Saxena and Abhik Roychoudhury, National University of Singapore


Dynamic Information Flow Tracking (DIFT) forms the foundation of a wide range of security and privacy analyses. The main challenges faced by DIFT techniques are performance and scalability. Due to the large number of states in a program, the number of data flows can be prohibitively large and efficiently performing interactive data flow analysis queries using existing approaches is challenging. In this paper, we identify that DIFT under dependency-based information flow rules can be cast as linear transformations over taint state. This enables a novel matrix-based representation, which we call FlowMatrix, to represent DIFT operations concisely and makes it practical to adopt GPUs as co-processors for DIFT analysis. FlowMatrix provides efficient support for interactive DIFT query operations. We design a DIFT query system and prototype it on commodity GPUs. Our evaluation shows that our prototype outperforms CPU-based baseline by 5.6 times and enables rapid response to a DIFT queries. It has two to three orders of magnitude higher throughput compared to typical DIFT analysis solutions. We also demonstrate the efficiency and efficacy of new DIFT query operations.

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.

@inproceedings {281418,
author = {Kaihang Ji and Jun Zeng and Yuancheng Jiang and Zhenkai Liang and Zheng Leong Chua and Prateek Saxena and Abhik Roychoudhury},
title = {{FlowMatrix}: {GPU-Assisted} {Information-Flow} Analysis through {Matrix-Based} Representation},
booktitle = {31st USENIX Security Symposium (USENIX Security 22)},
year = {2022},
isbn = {978-1-939133-31-1},
address = {Boston, MA},
pages = {2567--2584},
url = {https://www.usenix.org/conference/usenixsecurity22/presentation/ji},
publisher = {USENIX Association},
month = aug

Presentation Video