363 lines · c
1// SPDX-License-Identifier: GPL-2.02/* Converted from tools/testing/selftests/bpf/verifier/search_pruning.c */3 4#include <linux/bpf.h>5#include <../../../include/linux/filter.h>6#include <bpf/bpf_helpers.h>7#include "bpf_misc.h"8 9#define MAX_ENTRIES 1110 11struct test_val {12 unsigned int index;13 int foo[MAX_ENTRIES];14};15 16struct {17 __uint(type, BPF_MAP_TYPE_HASH);18 __uint(max_entries, 1);19 __type(key, long long);20 __type(value, struct test_val);21} map_hash_48b SEC(".maps");22 23struct {24 __uint(type, BPF_MAP_TYPE_HASH);25 __uint(max_entries, 1);26 __type(key, long long);27 __type(value, long long);28} map_hash_8b SEC(".maps");29 30SEC("socket")31__description("pointer/scalar confusion in state equality check (way 1)")32__success __failure_unpriv __msg_unpriv("R0 leaks addr as return value")33__retval(POINTER_VALUE)34__naked void state_equality_check_way_1(void)35{36 asm volatile (" \37 r1 = 0; \38 *(u64*)(r10 - 8) = r1; \39 r2 = r10; \40 r2 += -8; \41 r1 = %[map_hash_8b] ll; \42 call %[bpf_map_lookup_elem]; \43 if r0 == 0 goto l0_%=; \44 r0 = *(u64*)(r0 + 0); \45 goto l1_%=; \46l0_%=: r0 = r10; \47l1_%=: goto l2_%=; \48l2_%=: exit; \49" :50 : __imm(bpf_map_lookup_elem),51 __imm_addr(map_hash_8b)52 : __clobber_all);53}54 55SEC("socket")56__description("pointer/scalar confusion in state equality check (way 2)")57__success __failure_unpriv __msg_unpriv("R0 leaks addr as return value")58__retval(POINTER_VALUE)59__naked void state_equality_check_way_2(void)60{61 asm volatile (" \62 r1 = 0; \63 *(u64*)(r10 - 8) = r1; \64 r2 = r10; \65 r2 += -8; \66 r1 = %[map_hash_8b] ll; \67 call %[bpf_map_lookup_elem]; \68 if r0 != 0 goto l0_%=; \69 r0 = r10; \70 goto l1_%=; \71l0_%=: r0 = *(u64*)(r0 + 0); \72l1_%=: exit; \73" :74 : __imm(bpf_map_lookup_elem),75 __imm_addr(map_hash_8b)76 : __clobber_all);77}78 79SEC("lwt_in")80__description("liveness pruning and write screening")81__failure __msg("R0 !read_ok")82__naked void liveness_pruning_and_write_screening(void)83{84 asm volatile (" \85 /* Get an unknown value */ \86 r2 = *(u32*)(r1 + 0); \87 /* branch conditions teach us nothing about R2 */\88 if r2 >= 0 goto l0_%=; \89 r0 = 0; \90l0_%=: if r2 >= 0 goto l1_%=; \91 r0 = 0; \92l1_%=: exit; \93" ::: __clobber_all);94}95 96SEC("socket")97__description("varlen_map_value_access pruning")98__failure __msg("R0 unbounded memory access")99__failure_unpriv __msg_unpriv("R0 leaks addr")100__flag(BPF_F_ANY_ALIGNMENT)101__naked void varlen_map_value_access_pruning(void)102{103 asm volatile (" \104 r1 = 0; \105 *(u64*)(r10 - 8) = r1; \106 r2 = r10; \107 r2 += -8; \108 r1 = %[map_hash_48b] ll; \109 call %[bpf_map_lookup_elem]; \110 if r0 == 0 goto l0_%=; \111 r1 = *(u64*)(r0 + 0); \112 w2 = %[max_entries]; \113 if r2 s> r1 goto l1_%=; \114 w1 = 0; \115l1_%=: w1 <<= 2; \116 r0 += r1; \117 goto l2_%=; \118l2_%=: r1 = %[test_val_foo]; \119 *(u64*)(r0 + 0) = r1; \120l0_%=: exit; \121" :122 : __imm(bpf_map_lookup_elem),123 __imm_addr(map_hash_48b),124 __imm_const(max_entries, MAX_ENTRIES),125 __imm_const(test_val_foo, offsetof(struct test_val, foo))126 : __clobber_all);127}128 129SEC("tracepoint")130__description("search pruning: all branches should be verified (nop operation)")131__failure __msg("R6 invalid mem access 'scalar'")132__naked void should_be_verified_nop_operation(void)133{134 asm volatile (" \135 r2 = r10; \136 r2 += -8; \137 r1 = 0; \138 *(u64*)(r2 + 0) = r1; \139 r1 = %[map_hash_8b] ll; \140 call %[bpf_map_lookup_elem]; \141 if r0 == 0 goto l0_%=; \142 r3 = *(u64*)(r0 + 0); \143 if r3 == 0xbeef goto l1_%=; \144 r4 = 0; \145 goto l2_%=; \146l1_%=: r4 = 1; \147l2_%=: *(u64*)(r10 - 16) = r4; \148 call %[bpf_ktime_get_ns]; \149 r5 = *(u64*)(r10 - 16); \150 if r5 == 0 goto l0_%=; \151 r6 = 0; \152 r1 = 0xdead; \153 *(u64*)(r6 + 0) = r1; \154l0_%=: exit; \155" :156 : __imm(bpf_ktime_get_ns),157 __imm(bpf_map_lookup_elem),158 __imm_addr(map_hash_8b)159 : __clobber_all);160}161 162SEC("socket")163__description("search pruning: all branches should be verified (invalid stack access)")164/* in privileged mode reads from uninitialized stack locations are permitted */165__success __failure_unpriv166__msg_unpriv("invalid read from stack off -16+0 size 8")167__retval(0)168__naked void be_verified_invalid_stack_access(void)169{170 asm volatile (" \171 r2 = r10; \172 r2 += -8; \173 r1 = 0; \174 *(u64*)(r2 + 0) = r1; \175 r1 = %[map_hash_8b] ll; \176 call %[bpf_map_lookup_elem]; \177 if r0 == 0 goto l0_%=; \178 r3 = *(u64*)(r0 + 0); \179 r4 = 0; \180 if r3 == 0xbeef goto l1_%=; \181 *(u64*)(r10 - 16) = r4; \182 goto l2_%=; \183l1_%=: *(u64*)(r10 - 24) = r4; \184l2_%=: call %[bpf_ktime_get_ns]; \185 r5 = *(u64*)(r10 - 16); \186l0_%=: exit; \187" :188 : __imm(bpf_ktime_get_ns),189 __imm(bpf_map_lookup_elem),190 __imm_addr(map_hash_8b)191 : __clobber_all);192}193 194SEC("tracepoint")195__description("precision tracking for u32 spill/fill")196__failure __msg("R0 min value is outside of the allowed memory range")197__naked void tracking_for_u32_spill_fill(void)198{199 asm volatile (" \200 r7 = r1; \201 call %[bpf_get_prandom_u32]; \202 w6 = 32; \203 if r0 == 0 goto l0_%=; \204 w6 = 4; \205l0_%=: /* Additional insns to introduce a pruning point. */\206 call %[bpf_get_prandom_u32]; \207 r3 = 0; \208 r3 = 0; \209 if r0 == 0 goto l1_%=; \210 r3 = 0; \211l1_%=: /* u32 spill/fill */ \212 *(u32*)(r10 - 8) = r6; \213 r8 = *(u32*)(r10 - 8); \214 /* out-of-bound map value access for r6=32 */ \215 r1 = 0; \216 *(u64*)(r10 - 16) = r1; \217 r2 = r10; \218 r2 += -16; \219 r1 = %[map_hash_8b] ll; \220 call %[bpf_map_lookup_elem]; \221 if r0 == 0 goto l2_%=; \222 r0 += r8; \223 r1 = *(u32*)(r0 + 0); \224l2_%=: r0 = 0; \225 exit; \226" :227 : __imm(bpf_get_prandom_u32),228 __imm(bpf_map_lookup_elem),229 __imm_addr(map_hash_8b)230 : __clobber_all);231}232 233SEC("tracepoint")234__description("precision tracking for u32 spills, u64 fill")235__failure __msg("div by zero")236__naked void for_u32_spills_u64_fill(void)237{238 asm volatile (" \239 call %[bpf_get_prandom_u32]; \240 r6 = r0; \241 w7 = 0xffffffff; \242 /* Additional insns to introduce a pruning point. */\243 r3 = 1; \244 r3 = 1; \245 r3 = 1; \246 r3 = 1; \247 call %[bpf_get_prandom_u32]; \248 if r0 == 0 goto l0_%=; \249 r3 = 1; \250l0_%=: w3 /= 0; \251 /* u32 spills, u64 fill */ \252 *(u32*)(r10 - 4) = r6; \253 *(u32*)(r10 - 8) = r7; \254 r8 = *(u64*)(r10 - 8); \255 /* if r8 != X goto pc+1 r8 known in fallthrough branch */\256 if r8 != 0xffffffff goto l1_%=; \257 r3 = 1; \258l1_%=: /* if r8 == X goto pc+1 condition always true on first\259 * traversal, so starts backtracking to mark r8 as requiring\260 * precision. r7 marked as needing precision. r6 not marked\261 * since it's not tracked. \262 */ \263 if r8 == 0xffffffff goto l2_%=; \264 /* fails if r8 correctly marked unknown after fill. */\265 w3 /= 0; \266l2_%=: r0 = 0; \267 exit; \268" :269 : __imm(bpf_get_prandom_u32)270 : __clobber_all);271}272 273SEC("socket")274__description("allocated_stack")275__success __msg("processed 15 insns")276__success_unpriv __msg_unpriv("") __log_level(1) __retval(0)277__naked void allocated_stack(void)278{279 asm volatile (" \280 r6 = r1; \281 call %[bpf_get_prandom_u32]; \282 r7 = r0; \283 if r0 == 0 goto l0_%=; \284 r0 = 0; \285 *(u64*)(r10 - 8) = r6; \286 r6 = *(u64*)(r10 - 8); \287 *(u8*)(r10 - 9) = r7; \288 r7 = *(u8*)(r10 - 9); \289l0_%=: if r0 != 0 goto l1_%=; \290l1_%=: if r0 != 0 goto l2_%=; \291l2_%=: if r0 != 0 goto l3_%=; \292l3_%=: if r0 != 0 goto l4_%=; \293l4_%=: exit; \294" :295 : __imm(bpf_get_prandom_u32)296 : __clobber_all);297}298 299/* The test performs a conditional 64-bit write to a stack location300 * fp[-8], this is followed by an unconditional 8-bit write to fp[-8],301 * then data is read from fp[-8]. This sequence is unsafe.302 *303 * The test would be mistakenly marked as safe w/o dst register parent304 * preservation in verifier.c:copy_register_state() function.305 *306 * Note the usage of BPF_F_TEST_STATE_FREQ to force creation of the307 * checkpoint state after conditional 64-bit assignment.308 */309 310SEC("socket")311__description("write tracking and register parent chain bug")312/* in privileged mode reads from uninitialized stack locations are permitted */313__success __failure_unpriv314__msg_unpriv("invalid read from stack off -8+1 size 8")315__retval(0) __flag(BPF_F_TEST_STATE_FREQ)316__naked void and_register_parent_chain_bug(void)317{318 asm volatile (" \319 /* r6 = ktime_get_ns() */ \320 call %[bpf_ktime_get_ns]; \321 r6 = r0; \322 /* r0 = ktime_get_ns() */ \323 call %[bpf_ktime_get_ns]; \324 /* if r0 > r6 goto +1 */ \325 if r0 > r6 goto l0_%=; \326 /* *(u64 *)(r10 - 8) = 0xdeadbeef */ \327 r0 = 0xdeadbeef; \328 *(u64*)(r10 - 8) = r0; \329l0_%=: r1 = 42; \330 *(u8*)(r10 - 8) = r1; \331 r2 = *(u64*)(r10 - 8); \332 /* exit(0) */ \333 r0 = 0; \334 exit; \335" :336 : __imm(bpf_ktime_get_ns)337 : __clobber_all);338}339 340/* Without checkpoint forcibly inserted at the back-edge a loop this341 * test would take a very long time to verify.342 */343SEC("kprobe")344__failure __log_level(4)345__msg("BPF program is too large.")346__naked void short_loop1(void)347{348 asm volatile (349 " r7 = *(u16 *)(r1 +0);"350 "1: r7 += 0x1ab064b9;"351 " .8byte %[jset];" /* same as 'if r7 & 0x702000 goto 1b;' */352 " r7 &= 0x1ee60e;"353 " r7 += r1;"354 " if r7 s> 0x37d2 goto +0;"355 " r0 = 0;"356 " exit;"357 :358 : __imm_insn(jset, BPF_JMP_IMM(BPF_JSET, BPF_REG_7, 0x702000, -2))359 : __clobber_all);360}361 362char _license[] SEC("license") = "GPL";363