Introduction
Android utilizes Security Enhancements for Android (SEAndroid), a mandatory access control (MAC) system based on SELinux, to enforce process isolation and protect system resources. While SEAndroid is foundational to Android security, its policies have grown increasingly opaque. The policy language employs high-level abstractions—such as macros, attributes, and groups—that allow a single source rule to expand into thousands of kernel-level permission checks. This "hidden" complexity complicates security auditing and policy management. This paper analyzes the evolution of SEAndroid policies over seven years, introducing a new metric to quantify true system complexity.
The "Box" Metric and Methodology
To move beyond simple rule counts, we define the "box" metric: an atomic unit of access control represented as a quadruple (subject type, object type, class, permission). By expanding all macros and attributes in the Android Open Source Project (AOSP) Git repository, we can measure the total number of boxes—the actual state space of the security policy. Our analysis spans over 16,000 commits from January 2012 to August 2018, covering Android versions 4.3 through 9.0. This automated approach allows us to correlate policy changes with historical events and organizational contributions.
Historical Evolution of Complexity
Our analysis reveals that while the number of written rules has grown steadily, the number of "boxes" has increased at a super-exponential rate during certain periods. This divergence suggests that the policy is becoming significantly harder to maintain and audit over time.
As shown in the figure above, there is a significant gap between rule counts and box counts. A notable spike occurred during the transition to Android 4.4 (Point A), where the number of boxes increased tenfold despite a decrease in written rules. This was largely due to the introduction of "unconfined domains," a strategic shortcut used to prevent system denials during rapid development by granting broad permissions that were only gradually tightened in subsequent releases.
Strategic Policy Shifts and Hardening
Policy evolution is often reactive to major security threats. For instance, the discovery of the Stagefright vulnerability in 2015 prompted a significant restructuring of the media framework. Google utilized SEAndroid to implement privilege separation, breaking the monolithic mediaserver into smaller, sandboxed services. These architectural changes are reflected in the box metrics, which track the increasing granularity of permissions required to isolate these new services. Furthermore, the data shows that Google dominates the ecosystem; despite Android's open-source nature, the vast majority of core policy engineering is performed by Google, with other OEMs maintaining private forks.
The Maintainability Crisis
The increasing abstraction of SEAndroid policies presents a growing challenge for human engineers. The "box-per-rule" ratio indicates that individual rules are becoming more powerful and their effects harder to predict.
In Android 9.0, we identified instances where just four rules impacted over 110,000 boxes. As illustrated in the distribution chart, the number of rules impacting large ranges of boxes (e.g., <10^2 or <10^3) has grown across versions. This high density means that minor source code changes can have massive, unintended ripple effects on the system's security posture. We may be approaching a "maintainability brick wall" where traditional manual auditing becomes impossible without advanced automated tools.
Conclusion
The evolution of SEAndroid is characterized by a shift toward extreme abstraction. While this allows for more concise policy files, it hides a massive increase in underlying complexity. The "box" metric provides a necessary lens for understanding this growth and highlights the need for better tooling to manage the future of Android security.
Summary updated