在没有分支操作码的情况下测试一个整数与 eBPF 中的其他两个整数不同

Question

我正在编写一个检查任务 UID 的 eBPF kprobe，也就是说，调用 execve 之间唯一允许的 UID 更改是 setuid()、seteuid() 和 setreuid() 调用所允许的。

由于探测器检查所有任务，它使用从 init_task 开始迭代的展开循环，并且它必须使用最多 1024 或 8192 个分支，具体取决于内核版本。

我的问题是，如果存在非法更改，如何实现 returns 非零的检查，定义为：

(new_ruid != old_euid && new_ruid != old_ruid) ||
(new_euid != old_euid && new_euid != old_ruid && new_euid != old_suid)

但不使用分支（clang 使用跳转来短路检查 && 之间的任何表达式是否为真）。

Answer 1

您应该能够使用按位或、异或、移位和整数乘法来执行此操作。我假设您的变量都是 __s32 或 __u32，在继续操作之前将它们转换为 __u64 以避免出现问题（否则将下面乘法的每个操作数转换为 __u64）。

很明显a != b可以变成a ^ b。 && 有点棘手，但可以转换为乘法（如果任何操作数是 0，则结果是 0）。您的条件的第一部分将变为：

// (new_ruid != old_euid && new_ruid != old_ruid)
__u64 x = (new_ruid ^ old_euid) * (new_ruid ^ old_euid);

然而，对于第二部分，我们遇到了溢出问题，因为有 3 个条件。您可以通过将前两个结果“压缩”到低 32 位来避免它，因为您并不真正关心乘法，只关心它的“真实性”：

// (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);

最后只需对结果的两部分进行或运算。如果你想要 __u32:

，你也可以再次“压缩”到低 32 位

__u64 res = x | y;
// or
__u64 tmp = x | y;
__u32 res = (tmp >> 32) | (tmp & 0xffffffff);

无论优化级别如何，以上所有组合编译对我来说都没有任何分支。

Answer 2

按照另一个答案，有比将高位折叠在低位上更好的缩减函数。

先从原来的问题开始，生成的代码其实还不错。

bool func0(uint64_t new_ruid,uint64_t old_euid, uint64_t old_ruid,
           uint64_t new_euid, uint64_t old_suid) {
   return
      (new_ruid != old_euid && new_ruid != old_ruid) ||
      (new_euid != old_euid && new_euid != old_ruid && new_euid != old_suid);
}

_Z5func0mmmmm:                          # @_Z5func0mmmmm
    cmpq    %rsi, %rdi
    je      .LBB0_2
    movb    , %al
    cmpq    %rdx, %rdi
    je      .LBB0_2
    retq
.LBB0_2:
    cmpq    %rsi, %rcx
    setne   %al
    cmpq    %rdx, %rcx
    setne   %dl
    andb    %al, %dl
    cmpq    %r8, %rcx
    setne   %al
    andb    %dl, %al
    retq

只有第一部分包含条件分支，而后一部分完全展开为 set_conditionals。

因此我们有大约三个减少的候选者：

uint32_t reduct1(uint64_t a, uint64_t b) {
    a ^= b;
    return (a >> 32) | (a & 0xffffffff);
}

    movq    %rdi, %rax
    xorq    %rsi, %rax
    movq    %rax, %rcx
    shrq    , %rcx
    orl     %ecx, %eax


uint8_t reduct2(uint64_t a, uint64_t b) {
   return __builtin_popcountl(a ^ b);
}
    xorq    %rsi, %rdi
    popcntq %rdi, %rax


uint8_t reduct3(uint64_t a, uint64_t b) {
    return a != b ? 1u : 0u;
}
    cmpq    %rsi, %rdi
    setne   %al

与其他两个版本相比，第一个变体相当臃肿，此外它还存在乘法溢出问题。如果输入变量不同，popcount 变体 returns 值在 1-64 范围内，这意味着乘法溢出已解决。

但是，第三个变体的强度降低到 logical-and，这比乘法快得多——而且 允许 non-destructive 比较操作数 ，这可能胜过 popcount 版本（OTOH 有更多的指令级并行性机会）。

bool func( uint64_t new_ruid, uint64_t old_euid, uint64_t old_ruid,
uint64_t new_euid, uint64_t old_suid) {
    auto a = reduct3(new_ruid, old_euid);
    auto b = reduct3(new_ruid, old_ruid);
    auto c = reduct3(new_euid, old_euid);
    auto d = reduct3(new_euid, old_ruid);
    auto e = reduct3(new_euid, old_suid);
   return (a * b) || (c * d * e);
}
    cmpq    %rsi, %rdi
    setne   %r9b
    cmpq    %rdx, %rdi
    setne   %dil
    cmpq    %rsi, %rcx
    setne   %sil
    cmpq    %rdx, %rcx
    setne   %al
    cmpq    %r8, %rcx
    setne   %cl
    andb    %r9b, %dil
    andb    %sil, %al
    andb    %cl, %al
    orb     %dil, %al

这个问题也可以在 SSE2 域中解决，仔细选择参数：

   XMM0 = new_ruid | new_euid
   XMM1 = old_euid | old_euid
   XMM2 = old_ruid | old_ruid
   XMM3 = old_ruid | old_suid <- we compare new_ruid twice to same value

   XMM1 = _mm_cmpeq_epi64(XMM1, XMM0);
   XMM2 = _mm_cmpeq_epi64(XMM2, XMM0);
   XMM3 = _mm_cmpeq_epi64(XMM3, XMM0);
   XMM1 = _mm_or_si128(XMM1, XMM2);
   XMM1 = _mm_or_si128(XMM1, XMM3);

SSE2上只有==，没有!=，所以我们需要申请几次De-Morgan，然后合并左右部分，movemask或movq结果出来了。（如果允许在 Linux 内核上使用 SSE2，则 IDK，因此这部分可能不符合要求。）

在没有分支操作码的情况下测试一个整数与 eBPF 中的其他两个整数不同

Test that an integer is different from two other integers in eBPF without branch opcodes

assembly

clang

linux-kernel

bpf

ebpf