Landlock File System Composition Model

The semantics of Landlock’s file system policies should be clear from the documentation, but it can be easy to lose sight of the big picture when digging around in the implementation in the kernel. This page presents a more formal model for how Landlock’s file system access rights are determined, which an implementation can be checked against.

In Landlock, the effective file system access rights for a given file path /p1/p2/.../pn are composed at the time of resolving a specific path. p₀ denotes the root of the file system hierarchy, /.

At policy enablement time, it is infeasible for Landlock to walk the entire affected file system hierarchy and annotate every file. Instead, Landlock stores the association of specific inodes and their access rights which are applied to the file hierarchies beneath these inodes.

An additional problem is that inodes can technically change their position within the file hierarchy even after the ruleset is enforced. (This can happen, for instance, if they get moved around by more privileged processes.) Landlock must be able to deal with that situation as well and be able to adapt when the file hierarchy changes, while still enforcing the policy as intended.

Sets of access rights can only be interpreted in context

The sets of file system access rights (access_mask_t in the code) can only be interpreted in the context in which these sets are used. There are three variants that are helpful to distinguish:

An inode i’s access rights within a given layer l

Mathematical notation: a_l(p_i)

A set of access rights attached to an inode in a given layer, by means of adding a LANDLOCK_RULE_PATH_BENEATH rule (see LandlockFileSystemControl).

A path’s effective access rights within a given layer l

Mathematical notation: a_l(p_0…n)

A set of access rights that are allowed for a full file path p_0…n within a given layer.

This is calculated from the inode access rights of the path’s path components p₀, …, p_n

A path’s effective access rights across all of a processes’ layers

Mathematical notation: a_0…m(p_0…n)

A set of access rights that are allowed for a full file path p_0…n across all enforced policies in a process.

This is the definite set of access rights that finally determines for a given operation whether Landlock will allow or deny it when it is attempted by a process.

Inheritance of access rights along the file hierarchy

Without loss of generality, we will now look only at one single file path in the file hierarchy, with the path components p₀, p₁, …, p_n.

a_l(p_i) denotes the configured access rights in layer l for an individual path component p_i (identified by its inode).

Example: Access rights for a single inode

The access rights for a single inode like p₂ are modeled as a set of distinct access right elements:

a_l(p₂) = { WRITE_FILE, TRUNCATE }

In a given layer l, the effective access rights for a file path p₀, p₁, …, p_n are the union of the access rights of the individual path components in that layer:

a_l(p_1…n) = ⋃ _i=0ⁿ a_l(p_i)

Example: Access rights inherited from parent directories to children

An access right is allowed for the entire path whenever it is allowed for one of the path components:

Inode	`READ_FILE`	`WRITE_FILE`
a_l(p₀)	x
a_l(p₁)
a_l(p₂)		x
a_l(p₃)
Full path: a_l(p_0…3)	x	x

In this example, the READ_FILE access right is inherited from p₀, and WRITE_FILE is inherited from p₂. The EXECUTE_FILE access right is not allowed.

a_l(p_0...3)
= a_l(p₀) ∪ a_l(p₁) ∪ a_l(p₂) ∪ a_l(p₃)
= { READ_FILE } ∪ ∅ ∪ { WRITE_FILE } ∪ ∅
= { READ_FILE, WRITE_FILE }

How nested Landlock domains compose

A stack of nested Landlock policies is called layers in the implementation. It is a design goal that additional layers can only restrict the operations that are possible, or in other words, to perform a file operation that corresponds to an access right, that access right must be allowed for that file path in all of the layers. When modeling access rights as sets, the mathematical operation for that is the intersection.

Therefore:

Throughout all layers 0…m, the effective access rights for a file path p_0…n are the intersection of the access rights of that path in the individual layers l in [1…m]:

a_0…m(p_0…n)
= ⋂_l=0^m a_l(p_0…n)
= ⋂_l=0^m (⋃ _i=0ⁿ a_l(p_i))

What this means for Landlock’s implementation

In the implementation, Landlock can take all shortcuts as long as the above semantics are fulfilled.

Noteworthy: The implementation is tied to using inodes to identify path components and to store their associated access rights within layers. This association stays around even when these inodes change their positions in the file hierarchy (e.g. when a more privileged process moves them around).

Example: A wrong way to compose Landlock domains

It might be tempting to implement a Landlock layer like this (Go pseudocode):

type Layer struct {
  // A map from inode to a set of access rights.
  AccessRights map[Inode]AccessRightSet
}

and then to implement the stacking of new layers as a merge operation which intersects the access rights inode by inode:

func Merge(origl Layer, newl Layer) Layer {
  l := Layer{}
  for i := range origl.AccessRights {
    l.AccessRights[i] = intersect(origl.AccessRights[i], newl.AccessRights[i])
  }
  return l
}

A counterexample for this is a scenario where:

The original layer allows READ_FILE on / and WRITE_FILE on /home.
The new layer allows WRITE_FILE on / and READ_FILE on /home.

In both of these layers individually, both reading and writing will be permitted in /home and the files beneath.

However, when merging the layers with the faulty merging approach, the inode-wise intersections of the access rights for / and /home are both the empty set of access rights, and neither READ_FILE nor WRITE_FILE will be allowed for /home.

Example: A correct way to compose Landlock domains

A mathematically correct (but possibly slower) way to compose Landlock domains is to keep all the information around in a linked list of individual layers.

type Layer struct {
  // A map from inode to a set of access rights.
  AccessRights map[Inode]AccessRightSet

  // A link to the parent policy, if present.
  Parent *Layer
}

Merging can then be done by linking Layer objects through their Parent pointer. All of the real calculation only happens at evaluation time:

func EffectiveAccessRights(Layer *dom, Inode[] pathComponents) AccessRightSet {
  effective := ALL_KNOWN_ACCESS_RIGHTS
  for l := dom; l != nil; l = l.Parent {
    effectiveWithinLayer := NO_ACCESS_RIGHTS
    for _, inode := range pathComponents {
      effectiveWithinLayer = union(effectiveWithinLayer, l.AccessRights[inode])  // (1)
    }
    effective = intersection(effective, effectiveWithinLayer)                    // (2)
  }
}

Some interesting properties of this approach are:

EffectiveAccessRights() is a direct implementation of the formula from above: In (1), the union of inode access rights forms the effective access rights for a path within a layer. In (2), the effective access rights for a path globally is built as the intersection of access rights of that path within the layers.
Layer objects are immutable and can be shared across processes (with a refcount to free them when unused). While each individual task only has one linear linked list of layers, they form a tree when seen globally for a system.
The performance characteristics are different to what Landlock implements today.
- Specifically, the number of dictionary lookups is linear to the number of layers as well, where in the current implementation it is only linear to the number of walked inodes.

Comparison to real implementation: The actual current Landlock implementation is much more complex - it takes into account the access rights that are actually needed for the operation that is being attempted, and tries to stop the walk early as soon as these are fulfilled in every layer. It also merges the inode information for all layers into one RB-tree. This makes merging more expensive, but should make lookup cheaper. (I am personally critical of whether this effort is worth it though - the implementation does after all introduce more branches and the inodes whose walk we are skipping might already be in hot caches.)

Possibility of deny-listing

Landlock currently implements an allow-list model. – Only the access rights that are specifically listed for an inode will be allowed.

Occasionally, the topic comes up to maybe do the inverse and let users specify denied access rights for paths instead.

If that was needed, I believe the formula for the per-layer access rights would have to change, but we should still be able to build the intersection between the effective access rights for a given path across the different layers.