Scaling k8s workload aware tracing policies

[Andreagit97]

Tetragon CFP available here

Hi all! We would like to use Tetragon to implement per-workload runtime security policies across a Kubernetes cluster. The goal is to establish a "fingerprint" of allowed behavior for every Kubernetes workload (Deployment, StatefulSet, DaemonSet), starting with the strict enforcement of which processes each workload is permitted to spawn.

Let's say in our cluster we have two deployments, my-deployment-1 and my-deployment-2, and we want to enforce the following policies:

apiVersion: cilium.io/v1alpha1
kind: TracingPolicy
metadata:
  name: "policy-1"
spec:
  podSelector:
    matchLabels:
      app: "my-deployment-1"
  kprobes:
  - call: "security_bprm_creds_for_exec"
    syscall: false
    args:
    - index: 0
      type: "linux_binprm"
    selectors:
    - matchArgs:
      - index: 0
        operator: "NotEqual"
        values:
        - "/usr/bin/sleep"
        - "/usr/bin/cat"
        - "/usr/bin/my-server-1"
      matchActions:
      - action: Override
        argError: -1
  options:
  - name: disable-kprobe-multi
    value: "1"
---
apiVersion: cilium.io/v1alpha1
kind: TracingPolicy
metadata:
  name: "policy-2"
spec:
  podSelector:
    matchLabels:
      app: "my-deployment-2"
  kprobes:
  - call: "security_bprm_creds_for_exec"
    syscall: false
    args:
    - index: 0
      type: "linux_binprm"
    selectors:
    - matchArgs:
      - index: 0
        operator: "NotEqual"
        values:
        - "/usr/bin/ls"
        - "/usr/bin/my-server-2"
      matchActions:
      - action: Override
        argError: -1
  options:
  - name: disable-kprobe-multi
    value: "1"

Let's see what Tetragon injects into the kernel today.

eBPF prog point of view

The above 2 policies will result in the following ebpf programs being attached to the security_bprm_creds_for_exec function:

• generic_kprobe_event (from policy-1) -> other generic kprobe called in tail call
• generic_kprobe_event (from policy-2) -> other generic kprobe called in tail call
• generic_fmodret_override (from policy-1)
• generic_fmodret_override (from policy-2)

Of course, the number of progs will grow linearly with the number of policies (and so k8s workloads in our use case). When the number of policies grows, we hit the following limits:

1. The first issue we face is the number of programs we can attach to the same hook. In particular, we have a limit of 38 progs if we use BPF_MODIFY_RETURN. This type of program relies on eBPF trampoline and is subject to the BPF_MAX_TRAMP_LINKS limit (38 on x86). https://elixir.bootlin.com/linux/v6.14.11/source/include/linux/bpf.h#L1138.
2. Let's say we overcome this issue using kprobes + sigkill, now we hit a second limit of 128 policies. This limit is hardcoded in tetragon code

   tetragon/bpf/process/policy_filter.h

   Line 23 in 47538a0

   __uint(max_entries, POLICY_FILTER_MAX_POLICIES);

   probably to take care of memory usage. We can probably overcome this limit as well by making the limit configurable.
3. Now, the third issue that I think we cannot overcome today is performance overhead. The list of attached programs grows linearly with the number of policies we create. If we have 500 workloads in the cluster, we will have 500 programs attached to the same function. This could lead to a noticeable system slowdown when a new process is created. The slowdown could be even more relevant if we extend this behavior to some other kernel subsystems (e.g., file system/network operations).

eBPF maps point of view

For each of the above policies, I see more or less 50 eBPF maps loaded. Most of them have just 1 entry because they are probably not used, but others can take a great amount of memory. The reported memlock for each policy is around 8 MB. The most memory-intensive maps seem to be:

// inner map for each loaded policy with pod selectors
721: hash  name policy_1_map  flags 0x0 
 key 8B  value 1B  max_entries 32768  memlock 2624000B
 pids tetragon(63603)

// Still need to check if this is really needed (?)
764: lru_hash  name socktrack_map  flags 0x0
 key 8B  value 16B  max_entries 32000  memlock 2829696B
 btf_id 947
 pids tetragon(63603)

// map used for overriding the return value
766: hash  name override_tasks  flags 0x0
 key 8B  value 4B  max_entries 32768  memlock 2624000B
 btf_id 949
 pids tetragon(63603)

As you may imagine also in this case, having 500 deployments in the cluster could lead to a significant memory usage on the node (8 MB* 500 = 4 GB)

Summary

With this issue, we just want to highlight the current limitation in scalability that we are facing. I would love your feedback on this. Do you see any mistakes in this analysis? I'm pretty new to Tetragon, so maybe I missed something, and there is a way to overcome some of the above limitations that I didn't consider.
If you confirm these are real limitations and you are interested in supporting this use case, we can maybe discuss possible ideas to address them.

Thank you for your time!

[mtardy]

Hey 👋 thanks for opening this issue. Let me give you a first answer to some of the topics here.

On programs

Of course, the number of progs will grow linearly with the number of policies (and so k8s workloads in our use case). When the number of policies grows, we hit the following limits:

Indeed, because those are generic sensors, they are wired to be able to perform many different things. And thus you'll see them systematically attached to hooking points specified by policy. However, the generic programs should be written with in mind that the checks to see if the policy apply or not should be done early to minimize overhead on "non-matching events" (like workloads that doesn't match the k8s label for example). All of that to say that it's the downside of the program being generic and programmed by map values (but at the same time they provide great programmability).

We have debug commands that might help you there, check out tetra debug progs --help.

With more concrete analysis of a specific use case, we should be able to improve efficiency if we can spot "abnormal" overhead. Maybe also in the number of progs.

On maps

For each of the above policies, I see more or less 50 eBPF maps loaded. Most of them have just 1 entry because they are probably not used

Indeed, there's been an effort previously to correctly resize unused map before loading them (see for example #2546, #2551, #2555, #2563 or #2692, etc.). It is actually tricky to completely remove the unused maps, Cilium give it a go and found a way (see cilium/cilium#40416) but for Tetragon we mostly resize them to size 1, making them quite often negligible in memory use. We could eventually do like cilium/cilium but one can argue that we would mostly gain on reducing the number of map used by one program to avoid reaching the limit (64) than on actual memory used.

but others can take a great amount of memory.

We also have an equivalent command for map and their memory use that might help you there, check out tetra debug maps --help. I also did a bit of research on that to dig on BPF memory use that could be useful to you.

The reported memlock for each policy is around 8 MB.

Because the size of the map must be statically set at loading time, sometime we just use arbitrary constants that we think would fit most use cases. But many times it's impossible to find that fits all so the solution usually is to provide the ability to resize those with config flags. We also had the idea of proposing "sets of size" for maps fitting use cases for people running small/medium/large number of workloads/policies for example, that would avoid them to set each maps size one by one. Anyway, having users trying to scale Tetragon would greatly improve this area of fine tuning those numbers and reducing overall BPF map memory use and we could investigate on the specific maps you mentioned in a follow up.

[mtardy]

cc @kkourt as I know (with other people) he's been digging into scaling the number of policies recently as well.

[Andreagit97]

Thank you very much for the quick feedback!

I agree with you that the objective should be to reduce the number of eBPF maps and potentially the number of eBPF programs.

However, this raises a question about the current model: is using generic sensors truly the right way to model the use case of one distinct policy per workload?

Currently, we need to create a dedicated policy for each workload because each requires specifying different values (e.g., allowed binary paths), but the enforcement logic itself is identical across all these policies. The entire process would be significantly simpler if there was a way to define a common enforcement skeleton referenced by all workloads, where each individual workload only supplies the required configuration values.

A possible abstraction to achieve this separation could be as follows:

Note

Please note this is not a proposal, but just an easy way to explain the idea. For example, instead of using 2 new CRDs, we could use some fields in the existing TracingPolicy CR, like the options one

We could have two custom resources:

1. ForEachWorkloadPolicy: Defines the shared, unique enforcement logic (the "skeleton"). This resource is deployed once.

apiVersion: cilium.io/v1alpha1
kind: ForEachWorkloadPolicy
metadata:
  name: "block-not-allowed-process"
spec:
  # This is the hook we want to instrument once
  kprobes:
  - call: "security_bprm_creds_for_exec"
    syscall: false
    args:
    - index: 0
      type: "linux_binprm"
    selectors:
    - matchArgs:
      - index: 0 
        operator: "NotEqual" 
        values: [] # The actual values will be supplied by the 'Values' CRD
      matchActions:
      - action: Override
        argError: -1

2. ForEachWorkloadPolicyValues: Deploys the configuration values and selects the specific pods/cgroups to which they apply.

apiVersion: cilium.io/v1alpha1
kind: ForEachWorkloadPolicyValues
metadata:
  name: "block-not-allowed-process-my-deployment-1" 
spec:
  # Reference to the policy (a unique ID, not just name, should be used for robustness)
  refPolicy: "block-not-allowed-process" 
  # Select the pods in the workload
  podSelector:
    matchLabels:
      app: "my-deployment-1"
  values: 
    - "/usr/bin/sleep"
    - "/usr/bin/cat"
    - "/usr/bin/my-server-1"
---
apiVersion: cilium.io/v1alpha1
kind: ForEachWorkloadPolicyValues
metadata:
  name: "block-not-allowed-process-my-deployment-2" 
spec:
  refPolicy: "block-not-allowed-process" 
  podSelector:
    matchLabels:
      app: "my-deployment-2"
  values: 
    - "/usr/bin/ls"
    - "/usr/bin/my-server-2"

On the eBPF side, the ForEachWorkloadPolicy would be responsible for loading and attaching a unique eBPF program. Each ForEachWorkloadPolicyValues resource would then populate a map to associate a given cgroup ID with its unique set of filters.

__attribute__((section("fmod_ret/security_bprm_creds_for_exec"), used)) long
per_workload_fmodret_override(void *ctx)
{
    // pseudo code to explain the idea

    // 1. Get the cgroup ID of the current process
    cgroupid = tg_get_current_cgroup_id();

    // 2. Retrieve filters associated with that cgroup ID
    // The map will be populated by each new `ForEachWorkloadPolicyValue`
    // map[cgroupid] -> filters_map_id

    // 3. Perform the enforcement based on the retrieved filters
    if (match){
      return 0;
    }
    // The error is defined once in the policy definition CRD
    return error; 
}

While I would prefer to leverage the existing generic sensors model, I believe it would be genuinely difficult to achieve this level of logic/value separation and resource optimization using that model. I'm very curious to hear your opinions on this. Do you think it is possible to achieve something similar with the current generic sensors model?

[dwindsor]

The entire process would be significantly simpler if there was a way to define a common enforcement skeleton referenced by all workloads, where each individual workload only supplies the required configuration values.

We could probably do this by extending the existing policy filter, which already stores cgroup->policy mappings, to include another mapping for cgroupid->values?

[holyspectral]

For the memory utilization, bpf.BPF_F_NO_PREALLOC option should reduce the memory utilization a lot from ebpf maps, but apparently Tetragon only enabled bpf.BPF_F_NO_PREALLOC on some of maps. I wonder if this is on purpose?

I understand that bpf.BPF_F_NO_PREALLOC might not be ideal due to torvalds/linux@94dacdbd5d2d , but it doesn't explain why those flags are still there.

@kkourt @mtardy not sure if you know some background?

[mtardy]

For the memory utilization, bpf.BPF_F_NO_PREALLOC option should reduce the memory utilization a lot from ebpf maps, but apparently Tetragon only enabled bpf.BPF_F_NO_PREALLOC on some of maps. I wonder if this is on purpose?

I understand that bpf.BPF_F_NO_PREALLOC might not be ideal due to torvalds/linux@94dacdbd5d2d , but it doesn't explain why those flags are still there.

@kkourt @mtardy not sure if you know some background?

This is a tool that can be leveraged for reducing memory use of maps but:

1. It doesn't apply on all the maps
2. We could argue that it mostly delays memory consumption instead of reducing it

I would use it in the last steps of trying to tune memory use of those tbh. If you think you will gain memory long term by having NO_PREALLOC, your map is certainly just too large and could be resized.

I think if we want to tackle the BPF map memory use problem again we should:

1. Verify if it's an actual issue.
2. Check which maps are the biggest consumers.
3. (hopefully we already fix this) If the map is not used because the feature is not enabled, resize it to 1 to minimize impact.
4. Resize the maps to a better size, add a flag for resizing or group that size along other maps.
5. Then consider using NO_PREALLOC to optimize startup memory / situations in which we don't want to scale.

[holyspectral]

@mtardy thanks for the prompt and detailed response! Yes it probably doesn't fit all the maps. Our focus for now is the policy_filter_maps and its inner map.

In our use case, we would like to have policies defined via TracingPolicyNamespaced and TracingPolicy CRs. The problem is that, we don't really know how many there will be because it varies in different clusters, until those CRs are created. Without the policy_filter_maps dynamically allocatable, we would end up with many rounds of tuning in order to find a good maximum size of the map and over-provisioning.

That's why I think BPF_F_NO_PREALLOC might be a good fit here. I hope this makes sense and we would love to contribute to improve the scalability of the policy_filter_maps.

[kkourt]

@Andreagit97 thanks for posting this issue! The scalability problem that you are describing is definitely something we are aware of, and have been thinking about :)

I'll try to find some time to write more of my thoughts down, but before that I wanted to note two things.

First, we can decouple the policy specification from the underlying implementation of the BPF programs. For what it's worth, the current policies are very close to the BPF code, but they don't have to be. So, in principle, the implementation you are describing could happen with the existing policy scheme (unless I'm missing something).

Second, if we assume generic pod selectors, multiple policies might match the same workload. This means, that if we maintain per-workloads maps we would need to combine multiple policies to determine their contents, and we would need to figure out what means for the map contents when a policy is deleted or added.

[Andreagit97]

Thank you for the quick feedback!

First, we can decouple the policy specification from the underlying implementation of the BPF programs. For what it's worth, the current policies are very close to the BPF code, but they don't have to be. So, in principle, the implementation you are describing could happen with the existing policy scheme (unless I'm missing something).

Yeah, I agree, if we can reuse the current policy scheme to generate a slightly different eBPF instrumentation that would be great.

Second, if we assume generic pod selectors, multiple policies might match the same workload. This means, that if we maintain per-workloads maps we would need to combine multiple policies to determine their contents, and we would need to figure out what means for the map contents when a policy is deleted or added.

In my above example, I imagine a shared tracing policy (a sort of security profile) where podSelector are mutually exclusive. So each workload take advantage of the shared skeleton to just adding the values.
So the ebpf map belongs to the profile (what i called ForEachWorkloadPolicy) rather than single workloads.

{key: cgroupid, value: "hashset of allowed values"} 
# here each cgroupid has a unique entry because podSelectors are mutually exclusive

So if in my cluster I enforce 3 security profiles (e.g., allowed processes, allowed network connections, allowed file accesses, etc), I imagine the following scenario:

• [allowed processes] a unique fmod_ret eBPF prog attached on security_bprm_creds_for_exec that does the dispatching according to the groupid of the current process

{key: cgroupid-1, value: "/usr/bin/sleep,/usr/bin/cat"}
{key: cgroupid-2, value: "/usr/bin/ls"}
...

• [allowed file accesses] a unique fmod_ret eBPF prog attached on security_file_open that does the dispatching according to the groupid of the current process
• same for the networking use case

Of course, this is again a high-level picture of the ideal scenario I imagine. Instructing Tetragon to do that is far from easy.
But maybe you have something different in mind, where a per-workload policy fits better with the use case.

[kkourt]

In my above example, I imagine a shared tracing policy (a sort of security profile) where podSelector are mutually exclusive.

I guess my point was that that's not how pod selectors typically work (both from a semantics perspective and also from a user perspective). So if have this as a requirement, it should be explicit and, IMO, reflected in the syntax.

[Andreagit97]

Hi all, just a quick update!
We are making efforts to minimize the memory footprint per policy (see #4210, #4204, and others coming soon).

The point is that even if we might reach an acceptable level of memory for each policy (1/2 MB), there is still the open question on the number of ebpf progs attached to the same kernel function. I might be overestimating the issue, but I’m concerned that placing more than 200 programs on a kernel function in the hot path could lead to a system slowdown.

One idea we had to use just one ebpf prog could be the following.

We can introduce a new operator or a new way to express the the ForEachCgroup constraint in the policy filter.

    - matchArgs:
      - index: 0 
        operator: "EqForEachCgroup" 
        values: [] 
    # Or
    - matchArgs:
      - index: 0 
        forEachCgroup: true
        operator: "Eq" 
        values: [] 
    # Or
    - matchArgs:
      - index: 0 
        operator: "Eq" 
        values: ["*"] 
    # Or whatever...

Let's say we create a policy like this:

apiVersion: cilium.io/v1alpha1
kind: TracingPolicy
metadata:
  name: "block-not-allowed-process"
spec:
  kprobes:
  - call: "security_bprm_creds_for_exec"
    syscall: false
    args:
    - index: 0
      type: "linux_binprm"
    selectors:
    - matchArgs:
      - index: 0
        operator: "EqForEachCgroup"
        values: [] # The actual values will be supplied by other policies deployed later
      matchActions:
      - action: Override
        argError: -1

Let's consider, for now, the case of a linux_binprm arg type. When we evaluate the EqForEachCgroup operator instead of putting string values into BPF_MAP_TYPE_ARRAY_OF_MAPS like we do here

tetragon/bpf/process/string_maps.h

Line 66 in 27c9abe

__uint(type, BPF_MAP_TYPE_ARRAY_OF_MAPS);

we could create string_maps_0,string_maps_1, ... as BPF_MAP_TYPE_HASH_OF_MAPS. This would allow us to use the cgroup id as a key and as a value the hashset of strings associated with that cgroup.

{
  outer_key: cgroup_id, 
  outer_value: {
    "/usr/bin/ls": ""
    "/usr/bin/sleep": ""
  }
}

Ideally the outer_key should be a sort_of "workload_id" since multiple cgroups will have the same set of strings to match (e.g. all the pods that belongs to the same deployment). So ideally we should have a first map cgroup_id -> workload_id and then the BPF_MAP_TYPE_HASH_OF_MAPS where the outer_key is "workload_id".

When we evaluate this filter at runtime instead of using fixed indexes

tetragon/bpf/process/types/basic.h

Line 725 in 27c9abe

index = string_map_index(padded_len);

we get the cgroupid like we do here

tetragon/bpf/process/policy_filter.h

Line 62 in 27c9abe

policy_map = map_lookup_elem(&policy_filter_maps, &policy_id);

and we obtain the correct hashset to use for the comparison using our BPF_MAP_TYPE_HASH_OF_MAPS map.

This first tracing policy only sets up the "skeleton; at the beginning, the BPF_MAP_TYPE_HASH_OF_MAPS will be completely empty.

We now have to provide values. At the moment, we haven't found a better way to do that, so the idea is still to use a custom CR to do that

apiVersion: cilium.io/v1alpha1
kind: ForEachWorkloadPolicyValues
metadata:
  name: "block-not-allowed-process-my-deployment-1" 
spec:
  refPolicy: "block-not-allowed-process" 
  selector:
    matchLabels:
      app: "my-deployment-1"
  values: 
    - "/usr/bin/sleep"
    - "/usr/bin/cat"
    - "/usr/bin/my-server-1"

When this CR is deployed, the BPF_MAP_TYPE_HASH_OF_MAPS will be populated with the right entries cgroup_id -> hash_set. To do that, we should probably reuse the logic of the policyState.

WDYT about this idea? Any idea/suggestion?