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

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.