Issue
I'm writing an eBPF kprobe that checks task UIDs, namely that the only permitted UID changes between calls to execve are those allowed by setuid(), seteuid() and setreuid() calls.
Since the probe checks all tasks, it uses an unrolled loop that iterates starting from init_task, and it has to use at most 1024 or 8192 branches, depending on kernel version.
My question is, how to implement a check that returns nonzero if there is an illegal change, defined by:
(new_ruid != old_euid && new_ruid != old_ruid) ||
(new_euid != old_euid && new_euid != old_ruid && new_euid != old_suid)
but without using branches (clang uses jumps to short-circuit the check if any of the expressions between && evaluates to true).
Solution
You should be able to do this using bitwise OR, XOR, shifts and integer multiplication. Let's just assume the following types to make things easier (you probably have __i32, but you can just cast them to __u64 if needed):
__u64 new_ruid, new_euid, old_euid, old_ruid, old_suid;
Clearly a != b can become a ^ b. The && is a bit trickier, but can be translated into a multiplication (where if any operand is 0 the result is 0). The first part of your condition then becomes:
// (new_ruid != old_euid && new_ruid != old_ruid)
__u64 x = (new_ruid ^ old_euid) * (new_ruid ^ old_euid);
However for the second part we have an overflow problem since there are 3 conditions. You can avoid it by "compressing" the result of the first two into the lower 32 bits, since you don't really care about the multiplication, just about its "truthiness":
// (new_euid != old_euid && new_euid != old_ruid && new_euid != old_suid)
__u64 y = (new_euid ^ old_euid) * (new_euid ^ old_ruid);
y = (y >> 32) | (y & 0xffffffff);
y *= (new_euid ^ old_suid);
And finally just OR the two parts for the result. You can also "compress" again to the lower 32 bits if you want a __u32:
__u64 res = x | y;
// or
__u64 tmp = x | y;
__u32 res = (tmp >> 32) | (tmp & 0xffffffff);
All of the above combined compiles without any branch for me regardless of optimization level.
Answered By - Marco Bonelli Answer Checked By - Marie Seifert (WPSolving Admin)