Bridging the Compliance Gap: Effective and Efficient Detection of Non-Compliant Behaviors in Android Applications

As mobile applications become increasingly complex and privacy regulations continue to evolve, the task of accurately identifying app violations in compliance detection has become a major challenge. Prior works mainly relied on taint analysis and dynamic monitoring to address this issue. However, taint analysis requires specifying sources and sinks for each violation, leading to multiple analysis rounds and inefficiency. Meanwhile, dynamic monitoring suffers from incomplete coverage, resulting in high false negatives. In this paper, we propose a novel graph structure, called Behavior Property Graph (BPG), for detecting non-compliant behaviors in Android applications. BPG integrates the features from various graph representations, including Abstract Syntax Tree (AST), Control Flow Graph (CFG), Call Graph (CG), Program Dependency Graph (PDG), and Pointer Assignment Graph (PAG), enabling comprehensive modeling of complex app behaviors. Violations are identified by querying the BPG using behavioral patterns extracted from real-world apps. We develop a prototype system called BPGᴇɴ to generate BPGs and evaluated its performance by testing seven types of non-compliant behaviors on a dataset of 200 real-world apps. Notably, BPGᴇɴ detects 14 violations within 13 previously unreported non-compliant applications. The results show that BPGᴇɴ can efficiently and effectively detect app compliance violations.