TOMOYO Linux: A Mandatory Access Control Method Based on Application Execution State

This paper introduces TOMOYO Linux, a novel Mandatory Access Control method that enhances system security by evaluating application execution history and intents rather than relying solely on traditional application-file combinations, thereby reducing risks from malicious access and operational errors.

The Gist

Imagine your computer is a massive, bustling office building. In this building, there are thousands of employees (applications) who need to do their jobs. Some need to read files, some need to write reports, and some need to make phone calls (network connections).

The Old Way: The "Who Are You?" Security Guard

For a long time, computer security worked like a very simple, slightly confused security guard at the front door. This guard only asked two questions:

1. "Who are you?" (Which application are you?)
2. "What door are you trying to open?" (Which file do you want to access?)

If the guard saw a "Web Browser" employee trying to open the "Secret Passwords" file, he would check a list. If the list said "Web Browsers can open Password files," he let them in. If not, he stopped them.

The Problem: This system is too blunt. It doesn't care why the Web Browser is opening the file.

• Scenario A: The browser is just loading a normal webpage. (Safe)
• Scenario B: The browser has been tricked by a hacker into trying to steal your password file. (Dangerous!)

The old guard sees the same employee (Web Browser) and the same door (Password file) in both cases. He can't tell the difference between a safe visit and a theft, so he either lets everyone in (risky) or locks everyone out (impractical).

The New Way: TOMOYO Linux (The "Storytelling" Security Guard)

The authors of this paper propose a new kind of security guard for Linux computers, called TOMOYO. This guard doesn't just ask "Who are you?"; he asks, "How did you get here, and what is your story?"

The Magic of "Execution History"

Imagine that every time an employee in the office is hired or starts a new task, they are given a passport stamp.

• If you logged in from the main lobby, you get a stamp: Lobby -> Reception -> Your Desk.
• If you were hacked and forced into the system through a back window, your stamp might look different: Back Window -> Ventilation Shaft -> Your Desk.

TOMOYO tracks this entire history for every single program running on the computer. It knows exactly which path the application took to get to its current state.

How It Works in Practice

Let's look at a Shell (a command-line tool that lets you type commands). In the old system, a Shell is just a Shell. But in TOMOYO, the guard looks at the passport:

1. The Safe Shell: You logged in from your own computer console.
   • History: Kernel -> Login Screen -> Your Shell.
   • Guard's Decision: "Okay, this is a trusted user. You can run almost any program you need."
2. The Suspicious Shell: The Apache web server (which runs a website) was hacked, and it spawned a Shell to try and break in.
   • History: Kernel -> Web Server -> Hacked Shell.
   • Guard's Decision: "Wait a minute! A Shell coming from a Web Server is suspicious. You are only allowed to do very specific things, like reading a log file. You are not allowed to run dangerous programs or delete files."

Even though both are the exact same program file (/bin/bash), TOMOYO treats them completely differently because their stories are different.

The "Whitelist" Approach

TOMOYO works like a strict Whitelist.

• Old System (Blacklist): "I will stop you if I know you are bad." (But hackers are always inventing new ways to be bad).
• TOMOYO (Whitelist): "I will only let you do exactly what I have written down in your specific story."

If a program tries to do something that isn't on its specific "story list," the guard stops it immediately. Even if the program is running with "Super User" (Administrator) powers, the guard doesn't care. The rules apply to everyone.

Why This is Better (The Paper's Claims)

The paper claims this method solves problems the old system couldn't:

• It stops "Disguised" attacks: If a hacker renames a dangerous file to look like a safe one, the old guard might be fooled. TOMOYO looks at the history and the arguments (the specific instructions given to the program) to see if the action makes sense.
• It's easier to manage: Instead of guessing complex rules for the whole building, administrators can watch the "learning mode." The system records what the employees actually do when everything is working correctly, and then locks down everything else. It's like taking a photo of the office during a normal day and then only allowing those exact movements.
• It's fast: The authors tested this and found that while it adds a tiny bit of work for the computer (like a guard checking a passport takes a second), it doesn't slow down the office significantly. For most tasks, the delay is invisible to the user.

The Bottom Line

TOMOYO Linux changes security from a static "ID Check" to a dynamic "Story Check." It understands that context matters. A program doing one thing in one situation might be safe, but doing the exact same thing in a different situation (like after being hijacked by a hacker) is dangerous. By tracking the journey of every application, TOMOYO can stop attacks that traditional security guards simply couldn't see coming.

Technical Summary

Technical Summary: TOMOYO Linux – A Mandatory Access Control Method Based on Application Execution State

1. Problem Statement

Conventional access control methods, including Discretionary Access Control (DAC) and standard Mandatory Access Control (MAC) implementations (both label-based and pathname-based), make access decisions based primarily on the combination of a subject (application/process) and an object (file/resource). These methods fail to account for the execution state of the application or the intent behind a specific access request.

The paper identifies two critical limitations in existing systems:

1. Lack of Contextual Awareness: Conventional methods do not consider how an application was launched or what processing it is about to perform. For example, a web browser (HTTP client) should have different access permissions depending on whether it is running as a user application or as a CGI script invoked by a web server. Similarly, an application's behavior can change based on command-line arguments or environment variables (e.g., sshd displaying a banner file that contains sensitive data if misconfigured).
2. Coarse-Grained Sandboxing: Because execution state is ignored, sandboxes based on conventional MAC are often too coarse. They cannot restrict specific operations (like renaming a configuration file to a content file) without blocking the entire application, leading to insufficient damage localization.

The core issue is that conventional access control cannot distinguish between the same executable file running in different contexts (e.g., a shell logged in via SSH vs. a shell logged in via a console vs. a shell spawned by a web server), nor can it evaluate the potential effects of granting a specific access request.

2. Methodology

The authors propose a new access control method that incorporates application execution history and processing intent into the decision-making process. This methodology is implemented in TOMOYO Linux, a Linux Security Module (LSM).

2.1 Program Execution History

The system tracks the "program execution history" for every process. This history is a list of the path names of all applications executed from system startup (<kernel>) up to the creation of the current process.

• Mechanism: When a process forks and executes a new application (via execve), the child process inherits the parent's history and appends its own program name.
• Result: Even if two processes are running the same binary (e.g., /bin/bash), they possess different execution histories if they were launched via different chains (e.g., init $\to$ agetty $\to$ login $\to$ bash vs. init $\to$ sshd $\to$ bash).

2.2 Domain-Based Classification

Based on the execution history, the system defines Domains.

• A domain is a unique identifier representing a specific execution state, starting from <kernel> and following the chain of execution.
• Access control policies are defined per domain, not per binary. This allows the system administrator to grant different permissions to the same application depending on how it was launched.
• The domain structure forms a tree, allowing for Role-Based Access Control (RBAC) capabilities where nested shells or privilege escalations (e.g., su) create new, distinct domains with specific, limited permissions.

2.3 Condition-Based Access Decisions

The policy language allows access decisions to be conditioned on various parameters managed within the kernel, including:

• Command-line arguments: Restricting execution based on specific flags (e.g., exec.argv[0]="passwd").
• Environment variables: Filtering based on proxy settings or search paths.
• File attributes: Checking file permissions, ownership, or specific file contents.
• User IDs: Restricting access based on the effective or real user ID.

By using these factors as conditions, the system can infer the "intent" of the application. For instance, it can permit a file read operation only if the application is running with specific arguments that indicate a legitimate administrative task, rather than a generic read.

2.4 Implementation via Reference Monitor

TOMOYO Linux implements a reference monitor within the Linux kernel using the LSM framework.

• Interception: System calls are hooked to intercept access requests.
• Decision: The kernel checks the request against the policy defined for the process's current domain.
• Enforcement: If the request matches the policy (including all mandatory and optional conditions), it is allowed; otherwise, it is rejected.
• Whitelist Approach: The system operates on a whitelist basis; anything not explicitly permitted is denied.

3. Key Contributions

1. Execution State Awareness: The paper introduces a method to uniquely identify an application's execution state using a chain of program execution histories, enabling fine-grained access control that conventional MAC cannot achieve.
2. Intent-Based Policy: The methodology allows policies to be defined based on the processing an application is about to perform (inferred from arguments, environment, and history), rather than just the identity of the subject and object.
3. TOMOYO Linux Implementation: The authors provide a full implementation of this method in the Linux kernel, including:
   • A policy editor (CUI) for defining and managing domains.
   • A "Learning Mode" that automatically generates policies by observing system behavior, facilitating easier deployment.
   • Support for wildcards and complex conditional expressions in policy definitions.
4. RBAC Integration: The domain structure naturally supports Role-Based Access Control, allowing administrators to define roles based on the hierarchy of process execution (e.g., a shell spawned by su has different permissions than the original login shell).

4. Results and Evaluation

The paper presents an evaluation of TOMOYO Linux based on a demonstration experiment and performance benchmarks.

4.1 Usability and Management

• Policy Formulation: The "Learning Mode" allows administrators to observe the system for a period (e.g., two weeks for a web server) to collect execution histories and access patterns. This significantly reduces the manual effort required to define policies compared to label-based MAC (like SELinux), where administrators must manually map complex label transitions.
• Demonstration: In a 2007 experiment on a web server, participants were able to understand the principles and edit policies quickly. The use of path names and execution history made the system's behavior transparent to administrators.
• Comparison with SELinux: Unlike SELinux, which requires understanding complex label transitions and standard policies that may not match the specific environment, TOMOYO allows policies to be defined independently per domain, making management more intuitive.

4.2 Security Effectiveness

The method is shown to be effective against:

• Unauthorized Application Execution: Preventing the execution of shells or unauthorized tools even if a vulnerable application is compromised, by restricting the specific domain's permissions.
• Path Traversal: Nullifying attacks by computing absolute paths based on kernel data structures.
• Symbolic Link Attacks: Restricting the creation of symbolic links unless explicitly permitted for the specific directory and target.

4.3 Performance Impact

Performance was measured using LMBench on an Ubuntu 10.04 system (Core 2 Duo, 2GB RAM).

• Non-Hooked System Calls: System calls not intercepted by TOMOYO showed negligible impact (within ±5%, attributed to measurement variance).
• Hooked System Calls:
  • File Operations: Significant overhead was observed for operations involving file creation and metadata (e.g., stat, open/close, 0K File Create), with delays ranging from ~60% to ~128%. This is due to the overhead of checking path names and permissions.
  • Process Creation: fork and execve operations showed a delay of approximately 5-15%, attributed to the processing of execution history inheritance.
  • Network: TCP operations showed minimal overhead (~1%), while UDP showed ~28% overhead.
• Policy Scale: The paper notes that as the number of domains and access permissions increases, search times increase. However, empirical data suggests that in typical deployments, the number of domains and rules per domain remains under 2,000, keeping performance degradation within acceptable limits for ordinary use.

5. Significance and Claims

The paper claims that TOMOYO Linux represents a significant advancement in Mandatory Access Control by shifting the focus from static subject-object pairs to dynamic execution states.

• Complementarity: The authors position this method not as a replacement for label-based MAC, but as a complement. While label-based MAC excels at preventing information leakage through robust isolation, TOMOYO excels at maintaining the correct state of an information system and preventing applications from performing unintended operations.
• Practicality: By utilizing existing kernel information (execution history, arguments, environment) rather than requiring application modifications or complex label assignments, the method offers a practical path to fine-grained security.
• Usability: The ability to generate policies through observation (Learning Mode) and the intuitive nature of execution history addresses the high barrier to entry often associated with MAC systems.

The paper concludes that by rejecting unauthorized and unnecessary access requests that conventional methods cannot identify, TOMOYO Linux enhances information security while remaining manageable for system administrators. Future work is suggested to combine this method with application declarations to further refine execution state accuracy.