FSAFlow: Lightweight and Fast Dynamic Path Tracking and Control for Privacy Protection on Android Using Hybrid Analysis with State-Reduction Strategy

Despite the demonstrated effectiveness of dynamic taint analysis (DTA) in a variety of security applications, the poor performance achieved by available DTA prototypes prevents their widespread adoption in production systems, especially the Android system with limited computation and storage resources. To overcome DTA’s overhead bottlenecks, recent research efforts aim to decouple taint tracking logic from program execution. Continuing this line of research, this work proposes FSAFlow, a novel hybrid taint tracking and control system, to reduce DTA overhead significantly while ensuring sound Android privacy protection. FSAFlow further separates the path tracking logic from the corresponding taint tracking logic and the control of the information flow path is optimized. Specifically, a classic static analysis algorithm is first modified to search target paths and their key branch information. Then, the potential paths that violate the user’s predefined privacy protection policy are chosen and encoded with a Finite State Automaton (FSA). A small amount of FSA-based state management code is inserted into the corresponding position in the program. Finally, it monitors the program’s state of path execution and prevents information leakage during runtime. The efficiency and correctness of FSAFlow are proved by theoretical analysis. The experimental results show that FSAFlow incurs lower overhead than several representative DTA optimization approaches, 2.06% for popular applications, and 5.41% on CaffeineMark 3.0. FSAFlow has fewer false negatives in implicit flow tracking than the Android DTA platform, TaintDroid, and achieves higher precision than the static analysis tool, FlowDroid, by verifying the paths that never occur and tracking in the complete execution stage of the loop body at runtime.