Abstract
Modern security architectures rely on the principle of complete mediation to protect sensitive resources. However, the non-orthogonality of application programming interfaces (APIs) allows attackers to construct "API proxies"—sets of seemingly benign APIs that, when combined, can reconstruct sensitive information. This paper formalizes the API Proxy Problem (ApiPP), demonstrates its NP-completeness, and introduces a practical greedy heuristic based on mutual information to identify these vulnerabilities in complex systems like Android and iOS.
Introduction: The Challenge of Semantic Orthogonality
In modern operating systems, security is typically enforced by checking every access to a sensitive resource. For example, an application requires explicit user permission to access GPS coordinates. This approach assumes that APIs are "semantically orthogonal," meaning they provide distinct, non-overlapping functionality.
In practice, APIs are rarely orthogonal. Multiple APIs often provide overlapping data, allowing an attacker to bypass security checks on a "primary" API by using a combination of other APIs that act as a proxy. For instance, even if an app is blocked from accessing GPS, it might reconstruct a user's location by scanning nearby WiFi access points and cell towers. Currently, security mechanisms handle these proxies in an ad-hoc, reactive manner, patching leaks only after they are discovered. There has been no formal, scalable way to automatically discover these proxy relationships across the tens of thousands of APIs present in modern systems.
Formalizing the API Proxy Problem (ApiPP)
The authors define the API Proxy Problem (ApiPP) as a formal computational challenge. Given a sensitive attribute (such as a unique user ID), a set of available functions (APIs), and a distribution of real-world data, the goal is to identify a subset of APIs that reduces the "uncertainty" of the sensitive attribute below a specific threshold.
Through complexity analysis, the paper proves that ApiPP is NP-complete by reducing it from the classic "Vertex Cover" problem. This finding is significant because it explains why manual, ad-hoc security updates have been the norm; for a system with over 35,000 APIs (like Android), finding the exact set of all possible proxies is computationally prohibitive.
Algorithmic Solution: A Greedy Heuristic
Since an exact solution is computationally infeasible, the authors propose a greedy algorithm to identify proxies. This algorithm utilizes Mutual Information to iteratively select the API that provides the most new information about the target sensitive attribute, given the APIs already selected.
This approach results in an "over-approximation"—a set that might be slightly larger than necessary but is "safe" for security enforcement. In the context of security, an under-approximation (missing a proxy) is dangerous because it leaves a hole for attackers, whereas an over-approximation (blocking more APIs than strictly necessary) preserves safety at the potential cost of some application utility. The proposed greedy heuristic runs in $O(n^2)$ time, making it practical for modern software surfaces.
Real-World Case Studies
To ground the theoretical framework, the authors examine common architectural patterns in mobile operating systems. One notable example in Android involves display metrics. While Display.getMetrics is the primary API for retrieving screen dimensions, a combination of window-related and view-related APIs can reconstruct this information without the specific permission required for the primary call.
A more critical example involves user location. Even if an application is denied access to GPS via LocationManager.getCurrentLocation, it can often infer the user's position by aggregating data from WiFi scans, cell tower information, and network interface addresses.
Beyond Android, the paper references studies on iOS where apps evaded Apple’s App Tracking Transparency (ATT) by using disk space, carrier name, and device model as proxies for a unique user ID. These examples highlight the "Confounding Attribute" problem, where proxies exist either because different APIs point to the same internal object or because different attributes are correlated in the real world (e.g., timezone and carrier both hinting at location).
Discussion and Future Work
The formalization of ApiPP reveals a deep link between system security and "fairness in machine learning," where models accidentally learn sensitive attributes (like race or gender) through proxy features (like zip code).
However, several challenges remain. The current research primarily focuses on finding proxies for one sensitive attribute at a time; a "Global ApiPP"—finding proxies for all sensitive attributes simultaneously—remains an open, even harder problem. Furthermore, because API proxies depend on the distribution of real-world data, these relationships may change as user behavior or device demographics evolve. The authors suggest that future systems should be co-designed to ensure APIs are more orthogonal from the start, preventing proxy issues by design rather than through reactive patching.
Summary updated