TALISMAN: Tamper Analysis for Reference Monitors

TALISMAN: Tamper Analysis for Reference Monitors

Speakers: Frank Capobianco

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=2SWhuyrEuxI

Overview

In this presentation, Frank Capobianco introduced TALISMAN, an automated analysis tool designed to detect subtle yet critical flaws that can compromise the tamper-proofing of reference monitor implementations. While the concept of a reference monitor—a security component that mediates all access to sensitive resources—has been a cornerstone of system security since the 1970s, prior research has predominantly focused on ensuring complete mediation, meaning all security-sensitive operations are checked. The equally vital requirement of the reference monitor itself being tamperproof has largely been overlooked, often with the assumption that a flaw in the host program was indistinguishable from one in the monitor.

However, as modern systems increasingly adopt defenses like ASLR and privilege separation, the ability to detect tampering within reference monitors becomes paramount. TALISMAN addresses this gap by employing a precise information flow integrity analysis to identify violations in the construction of authorization queries. It introduces a novel, relaxed variant of noninterference to overcome the limitations of strict noninterference, which frequently reports spurious implicit flow violations in complex systems. Furthermore, TALISMAN incorporates a mechanism for vetting expected uses of untrusted data through a process called endorsement.

The research applied TALISMAN to three prominent Linux Security Modules (LSMs): SELinux, AppArmor, and Tomoyo. The analysis successfully verified the integrity of 80% of arguments used in authorization queries generated by these LSMs. Crucially, TALISMAN also uncovered significant, previously unrecognized vulnerabilities in how pathnames are handled by Tomoyo and AppArmor, which could allow adversaries to circumvent authorization policies. These findings highlight the critical importance of automated tamper analysis in securing fundamental access control mechanisms.

Background

▶ Watch: Introduction to TALISMAN and problem of tamper analysis (0:00)

The concept of a reference monitor, first proposed in 1972, is foundational to data security. It mandates three core requirements for any access control mechanism: complete mediation (all security-sensitive operations must be checked), tamperproof operation (the monitor itself must be immune to unauthorized alteration), and verified correctness (its design and implementation must be provably correct). Historically, after a wave of Internet-scale worms in the early 2000s exposed weaknesses in operating system access control, significant research focused on achieving complete mediation, leading to the development of numerous reference monitor implementations for systems like Linux, the X Server, Postgres, and Apache.

However, the equally crucial requirement of tamper-proofing the reference monitor itself has often been neglected. The prevailing assumption was that if a reference monitor was integrated into a host program, any flaw in the host program that could affect the monitor was considered indistinguishable from a flaw in the monitor itself. This mindset has evolved with the advent of modern host program defenses, such as Address Space Layout Randomization (ASLR), designed to protect critical data, and a growing interest in privilege separation to isolate components even if one is compromised. These advancements make detecting whether reference monitor implementations can be tampered with increasingly vital for robust security.

The "tamper problem" for reference monitors can manifest in three primary ways:

1. Storing Security Identifiers in Host Program Structures: Reference monitors often store critical security identifiers directly within the host program's data structures. For example, SELinux embeds a security identifier in the i_security field of an inode object. While SELinux sets this data during inode creation, its storage within a widely used object makes it susceptible to illicit modification, potentially allowing an attacker to tamper with authorization if they can modify this field. The expectation is that such identifiers remain immutable after creation.
2. Incorrect Use of Operation Request Input: Client-provided inputs for operation requests can be misused. AppArmor, for instance, uses file->f_path as a security identifier for file objects. A critical issue arises when AppArmor's pathname canonicalization differs from that of the Linux file systems. If an attacker provides a pathname like FOO, which Ext4 resolves to foo, but AppArmor checks against FOO, authorization can be bypassed if the policy is case-sensitive and the file system is case-insensitive, or vice-versa. This was identified as a vulnerability in both AppArmor and Tomoyo.
3. Authorization Bypass: LSMs frequently use data from the object itself in conditional statements that can completely bypass authorization. An IS_PRIVATE check, for example, might authorize a request without invoking the main authorization function (avc_has_perm). Such conditions, which use hook function inputs to determine whether to perform authorization, pose a risk if users can manipulate the conditional's value to bypass checks.

Abstractly, modern reference monitors divide authorization into two parts: a hook function that transforms client operation requests into a monitor-specific authorization query, and an authorization function that compares this query against the monitor's access control policy. Tampering can occur if low-integrity client-provided inputs or ad-hoc program imports (like global variables) are used incorrectly or maliciously to construct authorization queries, thereby compromising authorization decisions. TALISMAN's threat model assumes the reference monitor code itself is of high integrity, but any data external to it—client inputs and program imports—is considered low integrity and untrusted. Tampering is possible if an authorization query is constructed using low-integrity data that has not been appropriately endorsed. The analysis also assumes type-safety, meaning memory errors in the kernel do not directly modify the reference monitor's data or execution.

Key Findings

▶ Watch: Tampering Case 1: Modifying stored security identifiers (2:15)

TALISMAN's application to real-world Linux Security Modules (SELinux, AppArmor, and Tomoyo) yielded several significant findings:

• High Verification Rate for Authorization Arguments: The tool successfully verified the integrity of 80% of the arguments passed to authorization queries across the analyzed LSMs (243 for SELinux, 13 for Tomoyo, and 25 for AppArmor). This demonstrates TALISMAN's effectiveness in systematically assessing argument integrity. A substantial portion of these verified arguments (188 for SELinux, 11 for Tomoyo, 12 for AppArmor) were successfully handled through the endorsement mechanism, which accounts for expected data transformations.
• Discovery of Critical Pathname Canonicalization Vulnerabilities: TALISMAN uncovered a significant security vulnerability in AppArmor and Tomoyo. Both LSMs use pathnames as security identifiers for objects, but their internal canonicalization rules differ from those of the Linux file systems (e.g., Ext4 with case-preserving naming). This discrepancy can lead to unauthorized access. For example, if AppArmor permits access to config but an attacker requests CONFIG, AppArmor might deny access based on its internal rules, while the file system canonicalizes CONFIG to config and grants access. This vulnerability was reported to Linux VFS, AppArmor, and Tomoyo maintainers and has been confirmed.
• Effectiveness of Relaxed Noninterference: The novel concept of relaxed noninterference proved crucial in making the analysis practical. When compared to strict noninterference, it significantly reduced the number of implicit flow violations, acting as a powerful false positive filter. Specifically, it achieved a 90.5% reduction in violations for Tomoyo, 89.8% for AppArmor, and 58.0% for SELinux. This demonstrates that by allowing the sequence of authorization queries to depend on untrusted operation requests (an intended behavior in reference monitors), the analysis becomes far more precise and actionable.
• Impact of Field-Sensitivity: The implementation of field-sensitive information flow analysis also played a vital role in reducing false positives. It led to a 90.6% reduction in violations for Tomoyo, 64.7% for SELinux, and 67.5% for AppArmor. Tomoyo, with its complex nested unions, benefited most from this precision, allowing for accurate tainting of corresponding fields.
• Performance Overhead of Dynamic Endorsement: While effective for tamper-proofing, dynamic endorsement introduces performance overhead. For SELinux (endorsing 16 bytes/4 fields), overhead ranged from 1.55% to 33.48%. For AppArmor (128+ bytes/14 fields), it ranged from 12.86% to 43.46%. Tomoyo (56+ bytes/11 fields) had lower overhead, from 0.53% to 9.45%. The highest overheads were observed for operations involving pathname endorsement and for SELinux when endorsing inode_permission (up to 53.93%), primarily due to redundant checks on frequently accessed inodes (e.g., the root directory). This highlights the need for optimization in endorsement mechanisms.
• Identification of Ambiguous Authorization Practices: TALISMAN identified numerous hook functions (29 in SELinux, 23 in Tomoyo, 12 in AppArmor) that return 0 (authorized) without invoking any explicit authorization function. While manual inspection didn't reveal immediate vulnerabilities, this practice introduces ambiguity and is flagged for vetting, with a recommendation to use specific error codes for different scenarios.

Technical Deep Dive

▶ Watch: Tampering Case 2: Misusing client-provided input for authorization (2:45)

TALISMAN's core methodology is rooted in a precise information flow integrity analysis, tailored to the unique challenges of reference monitor hook functions. Its architecture operates in three main steps: constructing an information-flow problem, applying relaxed noninterference to detect violations, and using endorsement to resolve expected flows.

Information Flow Integrity Analysis

The analysis begins by modeling a deterministic program, such as a hook function H, using small-step semantics. A trace T is defined as a finite sequence of all sink calls (calls to authorization functions) in their execution order. R(T) is the numerical return value of the hook function. For information integrity, a lattice-based model is used, where security levels are drawn from an integrity lattice L. A source-label map S(x) -> l assigns an integrity level l to data sources x, and a sink-label map I(s,i) -> l assigns l to the i-th parameter of a sink function s. Two memory states μ and μ' are l-equivalent if they share the same values for all data at or above security level l.

Strict Noninterference and Its Limitations

Traditionally, strict noninterference requires that if low-integrity inputs change, the high-integrity parameters of any called sink function must remain constant, and the sequence of sink calls must also remain identical. Formally, for any l-equivalent μ₀ and μ'₀, if (H, μ₀) -> T and (H, μ'₀) -> T', then T and T' must contain the same sequence of sink calls, and for any matching sink call callᵢ(s,v) in T and callᵢ(s,v') in T', all parameters vⱼ with integrity level l <= I(s,j) must be equal to v'ⱼ.

However, strict noninterference is overly conservative for security hooks. Consider apparmor_ptrace_traceme. An early return due to a failed check means no sink calls occur in one trace, while another trace proceeds to aa_ptrace. Strict noninterference would flag this as a violation because the sequence of sink calls is influenced by low-integrity data, even though this behavior is intended (an error means no further access control is needed). Security hooks often call different sink functions based on operation parameters, which also violates strict noninterference but is functionally correct.

Relaxed Noninterference (Definition V.2)

To address these limitations, TALISMAN introduces relaxed noninterference, which maintains strong integrity guarantees while accounting for intended variations in sink call sequences. The threat model focuses on an attacker controlling untrusted inputs to either tamper with sink function parameters or bypass all sink functions to return success when it shouldn't. Relaxed noninterference has two cases:

1. Case I: If (H, μ₀) -> T and (H, μ'₀) -> T', and T is empty (no sink calls) while T' is not, then R(T) (the return value of the hook function when no sinks are called) must not be SUCCESS. This rules out the unsafe scenario where untrusted input bypasses all authorization checks and the hook function returns success. It does allow bypassing all sink calls if authorization fails (e.g., returns an error code).
2. Case II: For any matching sink calls callᵢ(s,v) in T and callᵢ(s,v') in T', all high-integrity parameters vⱼ (where l <= I(s,j)) must be equal to v'ⱼ. This is identical to strict noninterference for matching calls but allows for different sequences of sink calls.

This relaxation allows the apparmor_ptrace_traceme example to satisfy Definition V.2 because different sink call sequences are permitted. While Case I violations (bypassing all sink calls and returning success) might sometimes be intentional, TALISMAN reports them as potential risks for further analysis.

Constructing Information Flow Problems and LSM Integrity Lattice

TALISMAN constructs information flow problems by identifying and labeling data sources that might influence authorization query arguments at sinks. This is achieved using backward static taint analysis on a Program Dependence Graph (PDG) representation of hook functions and their supporting functions. The analysis traverses PDGs from each sink argument until it reaches an input (hook function argument) or an import (e.g., a global variable or constant). Inputs are labeled based on their position, while imports are labeled based on their definition location.

A key insight is that authorization integrity depends on multiple perspectives, leading to a three-dimensional integrity lattice (Figure 7 in the original paper):

1. Location: monitor (LSM code, highest integrity), input (LSM authorization API arguments), and external (other kernel data).
2. Value: static (statically predictable, like constants, higher integrity) and dynamic (not statically predictable).
3. Purpose: subject, object, op (operation), and unknown (lowest integrity).

The integrity lattice L combines these dimensions with a partial ordering, where lB <= lA means datum A is more trusted than datum B. Sinks are expected to receive (monitor, static, purpose) labels for high-integrity parameters.

Field-Sensitive Information Flow Analysis

LSM hook functions often use single data structures with multiple fields for different purposes (e.g., tomoyo_request_info). To achieve precise analysis, TALISMAN implements field-sensitive information flow, tracking security labels at the granularity of data structure fields and array indices using type information. For union types, which pose challenges for field-sensitivity, the analysis leverages type casting instructions to identify the active variant, maintaining field-sensitivity and soundness.

Endorsing Information Flows

Since hook functions inherently transform low-integrity inputs into high-integrity authorization queries, many integrity violations are expected but legitimate. TALISMAN provides systematic approaches to endorse these:

• Explicit Flow Violations (Dynamic Endorsement): Security Identifiers: Reference monitors assign high-integrity security identifiers to kernel resources at creation time. These identifiers should be immutable. TALISMAN endorses explicit flows by recording the mapping between resources (e.g., tasks, inodes) and their assigned security identifiers. During authorization, it retrieves the expected security ID values based on the resource's unique identity (e.g., thread ID for tasks, device/inode number for inodes) and compares them against the security identifier being used. If they match, the endorsement passes. Examples include selinux_file_open verifying task and inode security states.
• Implicit Flow Violations (Static Endorsement): Authorization Bypass: LSMs often allow authorization bypass under specific, controlled conditions, typically by comparing low-integrity data to known constant values (e.g., an IS_PRIVATE check). TALISMAN statically adds endorsers to the information flow model for these cases, incurring no runtime overhead. Other bypasses, such as error checks where the kernel handles them by denying access, are also endorsed.

Implementation Details

TALISMAN is implemented in C++ and built upon the LLVM framework. Its information flow analysis is an extension of PIDGIN 41, which uses DSA 45 for its points-to analysis. TALISMAN added approximately 13,000 lines of code to PIDGIN for field-sensitivity and union type handling. The Backwards Taint Source Identifier is an LLVM 9.0 optimization pass (6,000 lines of C++ code), leveraging a PDG generated by PtrSplit 46. A Constant Value Analyzer (350 lines of Clang 9.0 AST analysis) identifies global integers and enumerations, using pp-trace for macro metadata. Dynamic Endorser Placement was prototyped with 700 lines of LLVM pass and 100 lines of Python. The analysis was performed on Linux kernel version 3.19, with an acknowledgment that structural changes to LSM hook functions between 3.19 and modern LTS versions (e.g., 5.15.119) were not substantial enough to invalidate core findings.

Demo / Proof of Concept

▶ Watch: Abstract authorization model and TALISMAN's threat model (4:00)

While the presentation did not feature a live exploit demonstration, TALISMAN's primary contribution lies in its capability to automatically discover critical vulnerabilities, which serves as a powerful proof of concept for its analytical prowess. The most significant finding, which exemplifies this, is the pathname canonicalization vulnerability identified in AppArmor and Tomoyo.

This vulnerability arises because both LSMs rely on pathnames as security identifiers but implement their own canonicalization logic that can diverge from the actual Linux file system's behavior. For instance, in a case-preserving but case-insensitive file system like Ext4, a directory might contain a file named config. If an AppArmor policy grants access to /path/to/config, but an attacker attempts to access /path/to/CONFIG, AppArmor's internal (potentially case-sensitive) canonicalization might deny access. However, the underlying Ext4 file system would resolve /path/to/CONFIG to the existing config file, effectively granting access and bypassing the security policy.

This discrepancy allows an attacker to craft a pathname that appears to be denied by the LSM's policy but is resolved to an authorized resource by the kernel's Virtual File System (VFS), leading to an authorization bypass. The researchers reported this confirmed vulnerability to the Linux VFS, AppArmor, and Tomoyo maintainers. Fixing this requires a non-trivial alignment of the LSMs' canonicalization logic with the physical file system's behavior, especially given the dynamic nature of case-sensitivity in file systems like Ext4. The discovery of such a fundamental flaw in widely used security modules underscores TALISMAN's ability to uncover severe, previously unnoticed integrity issues.

Defensive Implications

▶ Watch: TALISMAN's architecture: information flow, relaxed noninterference, endorsement (4:40)

The findings from TALISMAN offer crucial insights for both security module developers and system administrators seeking to harden their systems:

For Reference Monitor Developers and Maintainers:

• Align Canonicalization Logic: For LSMs like AppArmor and Tomoyo that use pathnames as security identifiers, it is imperative to align their internal pathname canonicalization rules with those of the underlying Linux file systems. Mismatches, as discovered, can lead to critical authorization bypasses. This may require deeper integration with VFS canonicalization mechanisms or a re-evaluation of pathname-based security models.
• Isolate High-Integrity State: Future reference monitor designs should strongly consider storing all their high-integrity state (e.g., security identifiers) within their own isolated memory regions. This would prevent illicit modification by a compromised host program, enhancing tamper verification and overall robustness.
• Refactor Complex Hook Functions: Functions performing multiple, distinct types of authorization within a single hook (e.g., "Multiple Authorizations" in SELinux and Tomoyo) should be refactored into independent, verifiable hooks. This simplifies analysis, reduces the likelihood of information flow violations, and improves the overall verifiability and maintainability of the security module.
• Improve Return Code Clarity: For hook functions that return 0 (authorized) without invoking explicit authorization checks (Case I violations), developers should adopt more specific error codes for different scenarios. This enhances transparency, reduces ambiguity, and facilitates better auditing and debugging of authorization decisions.
• Mechanism for Host Program Compliance: While TALISMAN assumes host program compliance post-authorization, future work should explore mechanisms to actively restrict the permissions of host programs after an authorization decision. This builds on efforts in privilege separation and ensures that the host program adheres to the monitor's decisions.
• Optimize Dynamic Endorsement: The performance overhead of dynamic endorsement, particularly for frequently accessed resources like the root directory inode or variable-length pathnames, highlights a need for optimization. Implementing fast paths for commonly authorized entities or caching endorsement results could significantly reduce runtime impact without compromising security.

For System Administrators and Security Practitioners:

• Awareness of Subtle Bypasses: Be aware that even mature security modules like AppArmor and Tomoyo can harbor subtle vulnerabilities related to their interaction with the underlying operating system. Systems relying heavily on pathname-based access control should be scrutinized for potential canonicalization mismatches.
• Demand Verifiable Implementations: Advocate for and prioritize the deployment of security modules that have undergone rigorous tamper analysis and verification. Tools like TALISMAN provide a means to assess the integrity of fundamental security mechanisms.
• Understand LSM Differences: Recognize that different LSMs employ varying approaches to security identifiers and authorization logic, leading to different vulnerability profiles. An understanding of these architectural differences can inform risk assessments and deployment strategies.
• Contribute to Security Research: Support and encourage research efforts aimed at improving the formal verification and automated analysis of core security components.

In essence, TALISMAN reinforces that the "tamperproof" requirement of reference monitors is not an automatically granted property but rather a complex challenge requiring dedicated, automated analysis to ensure robust system security.

Key Takeaways

• Tamper-proofing is Critical and Overlooked: The "tamperproof" requirement for reference monitors is as crucial as "complete mediation" but has historically received less attention, leading to subtle yet critical vulnerabilities in real-world implementations.
• TALISMAN Automates Tamper Analysis: TALISMAN is the first automated tool specifically designed to detect flaws that could tamper with the execution of reference monitor implementations, leveraging precise information flow integrity analysis.
• Novel Relaxed Noninterference Reduces False Positives: The introduction of relaxed noninterference significantly reduces the high false positive rates (58-91% reduction) caused by strict noninterference in complex systems, making automated analysis practical and effective for security hooks.
• Critical Pathname Vulnerabilities Discovered: TALISMAN uncovered a significant, previously unknown security vulnerability in AppArmor and Tomoyo related to discrepancies in pathname canonicalization, which could lead to authorization bypasses.
• Endorsement is Key, but Needs Optimization: A systematic endorsement mechanism allows TALISMAN to verify expected information flows, successfully verifying 80% of authorization arguments. However, dynamic endorsement introduces performance overhead, particularly for frequently accessed resources, indicating a need for optimization.
• Future Reference Monitors Need Isolated State and Better Design: The research highlights that future reference monitors should consider storing high-integrity state in isolated memory regions and refactoring complex hook functions into more verifiable, independent units to enhance security and ease analysis.

About the Speaker(s)

Frank Capobianco is a researcher who presented TALISMAN: Tamper Analysis for Reference Monitors at the NDSS Symposium. His work focuses on enhancing the security of fundamental system components, particularly reference monitors, through automated analysis techniques. This presentation showcases his expertise in information flow integrity, static analysis, and practical application of security research to real-world operating system security modules.