RFD 116 - RBAC Label Expressions

Required Approvers

• Engineering: @rosstimothy || @codingllama || @fspmarshall
• Security: @reed || @jentfoo
• Product: @xinding33 || @klizhentas

What

This RFD proposes an addition to the Teleport Role spec to enable granular matching on resource labels.

Roles currently support the following "label matchers" in the allow and deny sections of the spec:

• node_labels
• app_labels
• cluster_labels
• kubernetes_labels
• db_labels
• db_service_labels
• windows_desktop_labels

These would be supplemented by new fields supporting predicate expressions that can match resource labels:

• node_labels_expression
• app_labels_expression
• cluster_labels_expression
• kubernetes_labels_expression
• db_labels_expression
• db_service_labels_expression
• windows_desktop_labels_expression

An example role spec allowing access to all nodes except those in the production environment would look like:

kind: role
version: v6
metadata:
  name: "all_except_prod"
spec:
  allow:
    node_labels_expression: 'labels["env"] != "production"'
    logins: ["root"]

Why

This feature will allow Teleport admins to write fewer roles than what is necessary today, and unlocks new usecases that are difficult or impossible to support with the current implementation.

For example, the above all_except_prod role is impossible to write with the current role spec. The closest option would look like:

kind: role
version: v6
metadata:
  name: "all_except_prod_legacy"
spec:
  allow:
    node_labels:
      '*': '*'
    logins: ["root"]
  deny:
    node_labels:
      'env': 'production'

But this has one major drawback: the deny rule prevents all users with this role from ever accessing production nodes via access request or even another role granting limited access.

Take the following auditor role for example:

kind: role
version: v6
metadata:
  name: "auditor"
spec:
  allow:
    node_labels:
      '*': '*'
    logins: ["auditor"]

If a user alice had both roles [all_except_prod, auditor] then she would be able to access production nodes with the auditor login and all other nodes with either the root or auditor login. But if another user bob had both roles [all_except_prod_legacy, auditor] then he would not be able to access any production nodes due to the matched deny rule. This is one of the most basic examples, demonstrating the value of a simple negative match (feature request).

Another popular ask is for label matchers to support logical "OR" matches, where a node can match any one of a set of possibly allowed labels. Currently this is not possible without creating multiple roles. Label expressions will be able to support this:

kind: role
version: v6
metadata:
  name: example
spec:
  allow:
    logins: ["example"]

    # This label expression would grant access to nodes in one of many allowed
    # environments
    node_labels_expression: |
      labels["env"] == "dev" ||
      labels["env"] == "qa" ||
      labels["env"] == "staging"

Details

Expression Syntax

Every label expression has access to the "evaluation context" as its input and must evaluate to a Boolean true/false to indicate a match of the given resource. Label expressions can appear in allow or deny role conditions.

Evaluation Context

Label expressions will have access to the following context:

Helper functions

Supported helper functions are a subset of those already supported in role templates, where expressions, and login rules.

Below, any variable named list can contain a list of items (like the list of values for a specific user trait) or a single value (like the value of a resource label or a string literal).

Operators

Templates vs Expressions

The existing label matchers support role "templating": user traits are substituted into the role spec with a special {{}} syntax, e.g.:

node_labels:
  env: `{{external.access-env}}`

These templates are "rendered" for the user with their current traits exactly once for each RPC. The rendered template is then held in the request context and can be used for multiple access checks. For example, when calling the ListResources RPC, all the user's role templates are rendered with their current traits once, and then used to check access to each requested resource in the cluster.

The new expression matchers will not support templating. Instead, user traits can be referenced directly in the expression without any special template syntax, e.g.:

node_labels_expression: 'contains(user.spec.traits["access-env"], labels["env"])'

Pros:

• No confusing mix of expression/template syntax.
• Parsed expressions can be cached across all users and roles, keyed by the expression string only. If individual user traits were templated into every expression, cache size would explode.
• Disallowing templates within expressions prevents any possibility of injection attacks.

Cons:

• User traits are not rendered once per RPC, but can be referenced in any expression in each access check, which may hurt evaluation performance.

Performance

Since predicate expressions can require more complex parsing than role templates, it's reasonable to be concerned that this could negatively impact the performance of the Teleport cluster. However, I believe it is feasible for this feature to offer performance no worse than our existing implementation.

Three reasons to believe that label expressions will not lead to significantly worse performance:

1. Label expressions make it possible to configure the same RBAC rules with fewer roles. This means fewer roles to read, cache, render, and evaluate.
2. Expressions can be parsed once and cached for the lifetime of the instance. This is explained in the following subsection on caching.
3. Role templates already use (limited) predicate expressions in label matchers. These are not cached, meaning the expression is parsed on each RPC.

Ultimately, performance will be benchmarked for multiple scenarios with the goal of staying within 10% of the performance of the existing implementation. Benchmarks will be written comparing similar RBAC constraints written with both the existing label matchers and the new label expressions. Benchmarks will run ListResources with 50k unique (simulated) nodes and 32 unique roles.

Benchmark results:

$ go test ./lib/auth -bench=. -run=^$ -v -benchtime 1x
goos: darwin
goarch: amd64
pkg: github.com/gravitational/teleport/lib/auth
cpu: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz
BenchmarkListNodes
BenchmarkListNodes/simple_labels
BenchmarkListNodes/simple_labels-16                    1        1079886286 ns/op        525128104 B/op   8831939 allocs/op
BenchmarkListNodes/simple_expression
BenchmarkListNodes/simple_expression-16                1         770118479 ns/op        432667432 B/op   6514790 allocs/op
BenchmarkListNodes/labels
BenchmarkListNodes/labels-16                           1        1931843502 ns/op        741444360 B/op  15159333 allocs/op
BenchmarkListNodes/expression
BenchmarkListNodes/expression-16                       1        1040855282 ns/op        509643128 B/op   8120970 allocs/op
BenchmarkListNodes/complex_labels
BenchmarkListNodes/complex_labels-16                   1        2274376396 ns/op        792948904 B/op  17084107 allocs/op
BenchmarkListNodes/complex_expression
BenchmarkListNodes/complex_expression-16               1        1518800599 ns/op        738532920 B/op  12483748 allocs/op
PASS
ok      github.com/gravitational/teleport/lib/auth      11.679s

Caching

Predicate expressions are parsed and evaluated in two distinct stages.

The first stage takes the raw string expression as input, parses the syntax, and returns a closure which is essentially a plain Go function.

The second stage takes closure from the first stage and invokes it with the evaluation context (resource labels, user traits) as input to produce a result. For label expressions, the result will be a Boolean true/false to indicate whether the expression matched the resource.

The first (parse) stage can be easily cached. It takes as input the literal string expression which is written in the role, and returns a closure that can be invoked repeatedly for each access check with the specific inputs for the current user and resource. The important part is that is always produces the exact same output for each input, and the total number of inputs is relatively small.

The size of the cache is bounded linearly by the number of unique expressions in all roles in the cluster. These expressions will almost always be hand-written, and I estimate there will usually be tens to (possibly) hundreds of unique expressions in any given cluster. In the rare case that someone writes or generates thousands of label expressions that are all actually used, performance can degrade gracefully by using an LRU cache.

The cache will be held in-memory of each Teleport process which does access checks. It will not be shared across nodes, it should be sufficient for each node to have to parse each expression once and all future uses can be cached. Cache entries will be populated on-demand the first time the are required. github.com/hashicorp/golang-lru/v2 implements a fixed-size thread safe LRU cache and is already used for similar purposes (regex caching) within teleport, so it will also be used here. The default maximum cache size will be 1000, and this can be overridden by an environment variable in case it causes problems.

Cache entries never need to be invalidated, updated, or expired, the value for each input is valid for the entire lifetime of the process. The only thing that could change the parse output is a new version of Teleport with a different parsing algorithm, conveniently this will always run in a new process with a fresh/empty cache.

Note: an App service will never need to parse or evaluate a db_labels_expression, it will only cache app_labels_expressions, and similarly each service will only need to cache the expressions actually relevant to that service. The only service that will need to parse/cache all expressions is Auth.

Security

Label expressions, as part of the Role specification, will be editable by any users with write/update permissions for Role resources, and readable by any user with read permissions for Roles.

This design avoids the possibility of any expression injection attacks. No untrusted input will be parsed as an expression, user traits and resource labels are only available during evaluation of the already-parsed expression. Regular expressions can only be built from static strings configured as part of the expression by the admin, labels and traits will not be compiled into regular expressions.

It's possible that a diabolical expression could cause terrible enough performance to threaten a DOS, but expressions can only be written by Teleport admins who already have permission to edit roles.

UX

Label expressions are a regular string field within the Teleport role specification. Users regularly interact with Teleport Roles via YAML files that can be edited with tctl or within the Web UI. Roles can also be edited with IaC workflows based on the Teleport Terraform provider or Kubernetes operator.

Verbose logging will be printed at the TRACE level for all access decisions involving label expressions, to aid users in debugging any issues.

Proto Specification

The following new fields will be added to the RoleConditions proto message:

  // NodeLabelsExpression is a predicate expression used to allow/deny access to
  // SSH nodes.
  string node_labels_expression = 27;
  // AppLabelsExpression is a predicate expression used to allow/deny access to
  // Apps.
  string app_labels_expression = 28;
  // ClusterLabelsExpression is a predicate expression used to allow/deny access to
  // remote Teleport clusters.
  string cluster_labels_expression = 29;
  // KubernetesLabelsExpression is a predicate expression used to allow/deny access to
  // kubernetes clusters.
  string kubernetes_labels_expression = 30;
  // DatabaseLabelsExpression is a predicate expression used to allow/deny access to
  // Databases.
  string db_labels_expression = 31;
  // DatabaseServiceLabelsExpression is a predicate expression used to allow/deny access to
  // Database Services.
  string db_service_labels_expression = 32;
  // WindowsDesktopLabelsExpression is a predicate expression used to allow/deny access to
  // Database Services.
  string windows_desktop_labels_expression = 33;

Backward Compatibility

Label expressions will be a set of brand new fields within the Role spec. They do not replace or supercede the existing label matchers. A single role may contain both node_labels and node_labels_expression, both will be considered independently.

Teleport instances running older versions of Teleport will not "see" or be aware of any label expressions. Before introducing label expressions to your cluster, you will be expected to upgrade relevant teleport instances to a version which supports label expressions, or else they will not be considered during access decisions.

If a Teleport downgrade is necessary, and no label expressions are currently used in any roles, there a no consequences. If label expressions are already being used and Teleport is downgraded to a version which does not support them, access decisions will not consider the label expressions.

Audit Events

No new audit events will be created, nor will any by changed.

Test Plan

The implementation of this feature will include automated unit and integration tests, as well as benchmarks. Running the benchmarks and comparing with past results will be added to the test plan to make sure performance does not regress too far.

Extra Examples

Conditional logic with user traits:

kind: role
version: v6
metadata:
  name: example
spec:
  allow:
    logins: [example]
    # This label expression would grant access to all non-production nodes
    # owned by one of the user's teams or the qa team.
    node_labels_expression: |
      labels["env"] != "production" &&
        (contains(user.spec.traits["teams"], labels["team"]) || labels["team"] == "qa")