GPU-Based Static Data-Flow Analysis for Fast and Scalable Android App Vetting

Xiaodong Yu, Fengguo Wei, Xinming Ou, Michela Becchi, Tekin Bicer, Danfeng Daphne Yao

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

9 Scopus citations

Abstract

Many popular vetting tools for Android applications use static code analysis techniques. In particular, Interprocedural Data-Flow Graph (IDFG) construction is the computation at the core of Android static data-flow analysis and consumes most of the analysis time. Many analysis tools use a worklist algorithm, an iterative fixed-point approach, to construct the IDFG. In this paper, we observe that a straightforward GPU parallelization of the worklist algorithm leads to significant underutilization of the GPU resources. We identify four performance bottlenecks, namely, frequent dynamic memory allocations, high branch divergence, workload imbalance, and irregular memory access patterns. Accordingly, we propose GDroid, a GPU-based worklist algorithm implementation with multiple fine-grained optimizations tailored to common characteristics of Android applications. The optimizations considered are: matrix-based data structure, memory access-based node grouping, and worklist merging. Our experimental evaluation, performed on 1000 Android applications, shows that the proposed optimizations are beneficial to performance, and GDroid can achieve up to 128X speedups against a plain GPU implementation.

Original languageEnglish
Title of host publicationProceedings - 2020 IEEE 34th International Parallel and Distributed Processing Symposium, IPDPS 2020
Pages274-284
Number of pages11
ISBN (Electronic)9781728168760
DOIs
StatePublished - May 2020
Event34th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2020 - New Orleans, United States
Duration: 18 May 202022 May 2020

Publication series

NameProceedings - 2020 IEEE 34th International Parallel and Distributed Processing Symposium, IPDPS 2020

Conference

Conference34th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2020
Country/TerritoryUnited States
CityNew Orleans
Period18/05/2022/05/20

Keywords

  • Android security
  • GPU
  • application-specific optimization
  • data-flow analysis
  • mobile application vetting
  • static program analysis
  • worklist algorithm

Fingerprint

Dive into the research topics of 'GPU-Based Static Data-Flow Analysis for Fast and Scalable Android App Vetting'. Together they form a unique fingerprint.

Cite this