FSAFlow

Lightweight and Fast Dynamic Path Tracking and Control for Privacy Protection on Android

A hybrid taint analysis system using Finite State Automaton (FSA) based path tracking for efficient Android privacy protection.

---

Overview

FSAFlow is a novel hybrid taint tracking and control system designed to significantly reduce Dynamic Taint Analysis (DTA) overhead while ensuring sound Android privacy protection. Unlike traditional DTA approaches that track taint propagation instruction-by-instruction, FSAFlow separates path tracking logic from taint tracking logic and monitors path state changes instead of taint state changes at runtime.

The core idea: instead of asking "how is information spread between variables?", FSAFlow asks "has the information flow path occurred, has it reached the sink, and does the policy allow it?"

Key Features

• Path Tracking over Taint Tracking: Monitors program path execution states rather than per-instruction taint propagation, drastically reducing runtime overhead.
• FSA-based Runtime Control: Encodes potential leakage paths into a Finite State Automaton (pushdown automaton) for efficient state management at runtime.
• Hybrid Analysis: Combines static analysis (modified IFDS/FlowDroid) for path discovery with lightweight dynamic monitoring for path verification.
• Loop Stable Period Monitoring: Addresses the IFDS algorithm's limitation in loop analysis by continuing to monitor the loop stable period, reducing false negatives.
• User-defined Flow Policies: Supports customizable privacy policies (e.g., whether location data can be sent over the network or written to files).
• Low Overhead: Incurs only 2.06% overhead for popular applications and 5.41% on CaffeineMark 3.0.

Architecture

FSAFlow consists of a mobile client and a cloud server, with the following workflow:

1. Flow Policy Management — User customizes information flow policies on the client.
2. Upload — The policy file and APK are uploaded to the cloud server.
3. Static Analysis — All potential paths violating the policy are discovered; key branch node information is recorded.
4. Static Instrumentation — Lightweight FSA-based monitoring code is inserted at source, branch, and sink nodes.
5. Repackaging — The instrumented code is repackaged into a new APK and returned to the client.
6. Runtime Control — The security-enhanced app runs on the device with efficient path-state monitoring.

How It Works

FSA-based Path Control

Each potential leakage path is encoded as a pushdown automaton M = (Q, Σ, Γ, δ, q₀, F):

• States (Q): Each key node on the path corresponds to a state.
• Input (Σ): Monitoring point execution events.
• Stack (Γ): Records the current execution period (Forward/Loop Propagation/Loop Stable) for handling nested loops.
• Transitions (δ): State updates occur only at branch statements, keeping overhead minimal.

Three execution periods are distinguished:

• Forward Propagation (N): Execution outside loop bodies.
• Loop Propagation (P): New taint nodes are still being discovered in the loop.
• Loop Stable (S): No new taint extensions; FSAFlow continues monitoring key branches to avoid false negatives.

Getting Started

Requirements

• Java: JDK 1.8+
• Android: Compatible with Android 4.0+ (downward compatible), tested on Android 10.0 (API 29)
• Dependencies: Built on SOOT, FlowDroid, Dexpler, and Heros framework

Installation

# Clone the repository
git clone https://github.com/FSAFlow/FSAFlow.git
cd FSAFlow

# Build the project (ensure JDK 1.8 is configured)
# Follow project-specific build instructions below

Usage

1. Define a Flow Policy

Use the mobile client to define information flow policies for the target application. Policies specify which source-to-sink paths should be prohibited, e.g.:

• Deny: GPS Location → Network Output
• Deny: Contacts → File Write
• Allow: User Input → Display

2. Process the APK

Upload the original APK along with the policy file to the cloud server for static analysis and instrumentation:

# Example: analyze and instrument the target APK
java -jar FSAFlow.jar --apk <target.apk> --policy <policy.txt> --output <output.apk>

3. Install and Run

Install the instrumented APK on the Android device. FSAFlow will automatically:

• Monitor path execution states at runtime
• Intercept information leakage when a prohibited path reaches a sink
• Notify the user with details of the intercepted leakage path

Citation

If you use FSAFlow in your research, please cite our paper:

@inproceedings{yang2022fsaflow,
  title={FSAFlow: Lightweight and Fast Dynamic Path Tracking and Control for Privacy Protection on Android Using Hybrid Analysis with State-Reduction Strategy},
  author={Yang, Zhi and Yuan, Zhanhui and Jin, Shuyuan and Chen, Xingyuan and Sun, Lei and Du, Xuehui and Li, Wenfa and Zhang, Hongqi},
  booktitle={2022 IEEE Symposium on Security and Privacy (SP)},
  pages={2114--2129},
  year={2022},
  organization={IEEE},
  doi={10.1109/SP46214.2022.00042}
}

License

This project is open-sourced. Please refer to the LICENSE file for details.