[PATCH bpf-next v3 07/11] bpf: Fix a false rejection caused by AND operation
Eduard Zingerman
eddyz87 at gmail.com
Mon Apr 29 21:56:29 UTC 2024
On Sun, 2024-04-28 at 23:15 +0800, Xu Kuohai wrote:
[...]
> diff --git a/kernel/bpf/tnum.c b/kernel/bpf/tnum.c
> index 9dbc31b25e3d..9d4480a683ca 100644
> --- a/kernel/bpf/tnum.c
> +++ b/kernel/bpf/tnum.c
> @@ -150,6 +150,29 @@ struct tnum tnum_intersect(struct tnum a, struct tnum b)
> return TNUM(v & ~mu, mu);
> }
>
> +/*
> + * Each bit has 3 states: unkown, known 0, known 1. If using x to represent
> + * unknown state, the result of the union of two bits is as follows:
> + *
> + * | x 0 1
> + * -----+------------
> + * x | x x x
> + * 0 | x 0 x
> + * 1 | x x 1
> + *
> + * For tnum a and b, only the bits that are both known 0 or known 1 in a
> + * and b are known in the result of union a and b.
> + */
> +struct tnum tnum_union(struct tnum a, struct tnum b)
> +{
> + u64 v0, v1, mu;
> +
> + mu = a.mask | b.mask; // unkown bits either in a or b
> + v1 = (a.value & b.value) & ~mu; // "known 1" bits in both a and b
> + v0 = (~a.value & ~b.value) & ~mu; // "known 0" bits in both a and b
> + return TNUM(v1, mu | ~(v0 | v1));
> +}
> +
Zero would be represented as {.value=0,.mask=0}, suppose 'b' is zero:
1. mu = a.mask | 0; 2. mu = a.mask;
v1 = (a.value & 0) & ~mu; v1 = 0;
v0 = (~a.value & ~0) & ~mu; v0 = ~a.value & ~mu;
return TNUM(v1, mu | ~(v0 | v1)); return TNUM(v1, mu | ~(v0 | v1));
3. v1 = 0; 4. v1 = 0;
v0 = ~a.value & ~a.mask; v0 = ~a.value & ~a.mask;
return TNUM(v1, a.mask | ~(v0 | v1)); return TNUM(0, a.mask | ~(~a.value & ~a.mask));
5. return TNUM(0, a.mask | a.value)
So ultimately this says that for 1's that we knew
we no longer know if those are 1's.
Which seems to make sense.
More information about the Linux-security-module-archive
mailing list