Function `eval_neg` did not treat values of INT64_MIN and 0 specially
when calculating negation ranges (e.g. negated unsigned range 0..2
should turn into 0..UINT64_MAX) producing incorrect results. On top of
this negating signed INT64_MIN caused undefined behaviour.
E.g. consider the following program with the current validation code:
Tested program:
0: mov r0, #0x0
1: ldxdw r2, [r1 + 0]
2: lddw r4, #0x8000000000000000
4: jgt r2, r4, L7
5: neg r2, #0x0 ; tested instruction
6: mov r0, #0x1
7: exit
Pre-state:
r2: 0..0x8000000000000000
Post-state:
r2: INT64_MIN..INT64_MIN+1 INTERSECT 0..0x8000000000000000 (!)
After the tested instruction validator considers r2 to be within
INT64_MIN..INT64_MIN+1 if viewed as signed, or within
0..0x8000000000000000 if viewed as unsigned, however if 1 was loaded on
step 1 into r2 it is possible for it to become -1 after the tested
instruction which satisfies neither of the ranges.
With sanitizer the following diagnostic is generated:
lib/bpf/bpf_validate.c:1120:7: runtime error: negation of
-9223372036854775808 cannot be represented in type 'long int'; cast
to an unsigned type to negate
#0 0x000002747230 in eval_neg lib/bpf/bpf_validate.c:1120
#1 0x000002748fb6 in eval_alu lib/bpf/bpf_validate.c:1251
#2 0x000002759dd3 in evaluate lib/bpf/bpf_validate.c:3161
...
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior
lib/bpf/bpf_validate.c:1120:7
Add missing handling of special cases, add tests.
Fixes: 8021917293d0 ("bpf: add extra validation for input BPF program")
Cc: [email protected]
Signed-off-by: Marat Khalili <[email protected]>
---
app/test/test_bpf_validate.c | 126 +++++++++++++++++++++++++++++++++++
lib/bpf/bpf_validate.c | 55 ++++++++++++---
2 files changed, 173 insertions(+), 8 deletions(-)
diff --git a/app/test/test_bpf_validate.c b/app/test/test_bpf_validate.c
index d7396a88beb8..995f7363b80f 100644
--- a/app/test/test_bpf_validate.c
+++ b/app/test/test_bpf_validate.c
@@ -1154,6 +1154,132 @@ test_alu64_add_x_scalar_scalar(void)
REGISTER_FAST_TEST(bpf_validate_alu64_add_x_scalar_scalar_autotest, NOHUGE_OK,
ASAN_OK,
test_alu64_add_x_scalar_scalar);
+/* 64-bit negation when interval first element is INT64_MIN. */
+static int
+test_alu64_neg_int64min_first(void)
+{
+ static const int64_t other_values[] = {
+ INT64_MIN,
+ INT64_MIN + 1,
+ INT64_MIN + 13,
+ -17,
+ -1,
+ 0,
+ 1,
+ 19,
+ INT64_MAX - 23,
+ INT64_MAX - 1,
+ INT64_MAX,
+ };
+ for (int other_index = 0; other_index != RTE_DIM(other_values);
++other_index) {
+ const int64_t other_value = other_values[other_index];
+ TEST_ASSERT_SUCCESS(verify_instruction((struct
verify_instruction_param){
+ .tested_instruction = {
+ .code = (EBPF_ALU64 | BPF_NEG),
+ },
+ .pre.dst = make_signed_domain(INT64_MIN, other_value),
+ .post.dst = other_value > 0 ? unknown :
+ make_unsigned_domain(-(uint64_t)other_value,
INT64_MIN),
+ }), "other_index=%d", other_index);
+ }
+ return TEST_SUCCESS;
+}
+
+REGISTER_FAST_TEST(bpf_validate_alu64_neg_int64min_first_autotest, NOHUGE_OK,
ASAN_OK,
+ test_alu64_neg_int64min_first);
+
+/* 64-bit negation when interval last element is INT64_MIN. */
+static int
+test_alu64_neg_int64min_last(void)
+{
+ static const uint64_t other_values[] = {
+ 0,
+ 1,
+ 19,
+ INT64_MAX - 23,
+ INT64_MAX - 1,
+ INT64_MAX,
+ INT64_MIN,
+ };
+ for (int other_index = 0; other_index != RTE_DIM(other_values);
++other_index) {
+ const int64_t other_value = other_values[other_index];
+ TEST_ASSERT_SUCCESS(verify_instruction((struct
verify_instruction_param){
+ .tested_instruction = {
+ .code = (EBPF_ALU64 | BPF_NEG),
+ },
+ .pre.dst = make_unsigned_domain(other_value, INT64_MIN),
+ .post.dst = make_signed_domain(INT64_MIN,
-(uint64_t)other_value),
+ }), "other_index=%d", other_index);
+ }
+ return TEST_SUCCESS;
+}
+
+REGISTER_FAST_TEST(bpf_validate_alu64_neg_int64min_last_autotest, NOHUGE_OK,
ASAN_OK,
+ test_alu64_neg_int64min_last);
+
+/* 64-bit negation when interval first element is zero. */
+static int
+test_alu64_neg_zero_first(void)
+{
+ static const uint64_t other_values[] = {
+ 0,
+ 1,
+ 19,
+ INT64_MAX - 23,
+ INT64_MAX - 1,
+ INT64_MAX,
+ INT64_MIN,
+ INT64_MIN + 1,
+ INT64_MIN + 13,
+ -17,
+ -1,
+ };
+ for (int other_index = 0; other_index != RTE_DIM(other_values);
++other_index) {
+ const uint64_t other_value = other_values[other_index];
+ TEST_ASSERT_SUCCESS(verify_instruction((struct
verify_instruction_param){
+ .tested_instruction = {
+ .code = (EBPF_ALU64 | BPF_NEG),
+ },
+ .pre.dst = make_unsigned_domain(0, other_value),
+ .post.dst = other_value > (uint64_t)INT64_MIN ? unknown
:
+ make_signed_domain(-(uint64_t)other_value, 0),
+ }), "other_index=%d", other_index);
+ }
+ return TEST_SUCCESS;
+}
+
+REGISTER_FAST_TEST(bpf_validate_alu64_neg_zero_first_autotest, NOHUGE_OK,
ASAN_OK,
+ test_alu64_neg_zero_first);
+
+/* 64-bit negation when interval last element is zero. */
+static int
+test_alu64_neg_zero_last(void)
+{
+ static const int64_t other_values[] = {
+ INT64_MIN,
+ INT64_MIN + 1,
+ INT64_MIN + 13,
+ -17,
+ -1,
+ 0,
+ };
+ for (int other_index = 0; other_index != RTE_DIM(other_values);
++other_index) {
+ const int64_t other_value = other_values[other_index];
+ TEST_ASSERT_SUCCESS(verify_instruction((struct
verify_instruction_param){
+ .tested_instruction = {
+ .code = (EBPF_ALU64 | BPF_NEG),
+ },
+ .pre.dst = make_signed_domain(other_value, 0),
+ .post.dst = make_unsigned_domain(0,
-(uint64_t)other_value),
+ }), "other_index=%d", other_index);
+ }
+
+ return TEST_SUCCESS;
+}
+
+REGISTER_FAST_TEST(bpf_validate_alu64_neg_zero_last_autotest, NOHUGE_OK,
ASAN_OK,
+ test_alu64_neg_zero_last);
+
/* Jump if greater than immediate. */
static int
test_jmp64_jeq_k(void)
diff --git a/lib/bpf/bpf_validate.c b/lib/bpf/bpf_validate.c
index b0d88fe7d273..79c8679ac535 100644
--- a/lib/bpf/bpf_validate.c
+++ b/lib/bpf/bpf_validate.c
@@ -990,6 +990,11 @@ eval_neg(struct bpf_reg_val *rd, size_t opsz, uint64_t msk)
{
uint64_t ux, uy;
int64_t sx, sy;
+ /* additional limits imposed by signed on unsigned and back */
+ struct bpf_reg_val cross_limits = {
+ .s = { INT64_MIN, INT64_MAX },
+ .u = { 0, UINT64_MAX },
+ };
/* if we have 32-bit values - extend them to 64-bit */
if (opsz == sizeof(uint32_t) * CHAR_BIT) {
@@ -997,11 +1002,29 @@ eval_neg(struct bpf_reg_val *rd, size_t opsz, uint64_t
msk)
rd->u.max = (int32_t)rd->u.max;
}
- ux = -(int64_t)rd->u.min & msk;
- uy = -(int64_t)rd->u.max & msk;
+ if (rd->u.min == 0) {
+ /* special case: ranges that include 0 and, possibly, 1 */
+
+ /*
+ * Calculate requirements on the signed range of negation.
+ * It is only possible when negated range does not cross from
+ * INT64_MIN to INT64_MAX, which means our original range does
+ * not reach (uint64_t)-INT64_MAX.
+ */
+ if (rd->u.max < (uint64_t)-INT64_MAX) {
+ cross_limits.s.min = -rd->u.max;
+ cross_limits.s.max = -rd->u.min;
+ }
+
+ if (rd->u.max != 0)
+ rd->u.max = UINT64_MAX;
+ } else {
+ ux = -rd->u.min & msk;
+ uy = -rd->u.max & msk;
- rd->u.max = RTE_MAX(ux, uy);
- rd->u.min = RTE_MIN(ux, uy);
+ rd->u.max = RTE_MAX(ux, uy);
+ rd->u.min = RTE_MIN(ux, uy);
+ }
/* if we have 32-bit values - extend them to 64-bit */
if (opsz == sizeof(uint32_t) * CHAR_BIT) {
@@ -1009,11 +1032,27 @@ eval_neg(struct bpf_reg_val *rd, size_t opsz, uint64_t
msk)
rd->s.max = (int32_t)rd->s.max;
}
- sx = -rd->s.min & msk;
- sy = -rd->s.max & msk;
+ if (rd->s.min == INT64_MIN) {
+ /* special case: negation of INT64_MIN is INT64_MIN */
+ if (rd->s.max <= 0) {
+ cross_limits.u.min = -(uint64_t)rd->s.max;
+ cross_limits.u.max = -(uint64_t)rd->s.min;
+ }
+ if (rd->s.max != INT64_MIN)
+ rd->s.max = INT64_MAX;
+ } else {
+ /* since max >= min, neither can be INT64_MIN here */
+ sx = -rd->s.min & msk;
+ sy = -rd->s.max & msk;
+
+ rd->s.max = RTE_MAX(sx, sy);
+ rd->s.min = RTE_MIN(sx, sy);
+ }
- rd->s.max = RTE_MAX(sx, sy);
- rd->s.min = RTE_MIN(sx, sy);
+ rd->s.min = RTE_MAX(rd->s.min, cross_limits.s.min) & msk;
+ rd->s.max = RTE_MIN(rd->s.max, cross_limits.s.max) & msk;
+ rd->u.min = RTE_MAX(rd->u.min, cross_limits.u.min) & msk;
+ rd->u.max = RTE_MIN(rd->u.max, cross_limits.u.max) & msk;
}
static const char *
--
2.43.0
