summaryrefslogtreecommitdiffstats
path: root/tools/testing/selftests/bpf/verifier/search_pruning.c
blob: d63fd8991b03aa9e9f3f2ec1b3f03419f8a1686c (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
{
	"pointer/scalar confusion in state equality check (way 1)",
	.insns = {
	BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
	BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
	BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
	BPF_LD_MAP_FD(BPF_REG_1, 0),
	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
	BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
	BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0, 0),
	BPF_JMP_A(1),
	BPF_MOV64_REG(BPF_REG_0, BPF_REG_10),
	BPF_JMP_A(0),
	BPF_EXIT_INSN(),
	},
	.fixup_map_hash_8b = { 3 },
	.result = ACCEPT,
	.retval = POINTER_VALUE,
	.result_unpriv = REJECT,
	.errstr_unpriv = "R0 leaks addr as return value"
},
{
	"pointer/scalar confusion in state equality check (way 2)",
	.insns = {
	BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
	BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
	BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
	BPF_LD_MAP_FD(BPF_REG_1, 0),
	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
	BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 2),
	BPF_MOV64_REG(BPF_REG_0, BPF_REG_10),
	BPF_JMP_A(1),
	BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0, 0),
	BPF_EXIT_INSN(),
	},
	.fixup_map_hash_8b = { 3 },
	.result = ACCEPT,
	.retval = POINTER_VALUE,
	.result_unpriv = REJECT,
	.errstr_unpriv = "R0 leaks addr as return value"
},
{
	"liveness pruning and write screening",
	.insns = {
	/* Get an unknown value */
	BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1, 0),
	/* branch conditions teach us nothing about R2 */
	BPF_JMP_IMM(BPF_JGE, BPF_REG_2, 0, 1),
	BPF_MOV64_IMM(BPF_REG_0, 0),
	BPF_JMP_IMM(BPF_JGE, BPF_REG_2, 0, 1),
	BPF_MOV64_IMM(BPF_REG_0, 0),
	BPF_EXIT_INSN(),
	},
	.errstr = "R0 !read_ok",
	.result = REJECT,
	.prog_type = BPF_PROG_TYPE_LWT_IN,
},
{
	"varlen_map_value_access pruning",
	.insns = {
	BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
	BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
	BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
	BPF_LD_MAP_FD(BPF_REG_1, 0),
	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
	BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 8),
	BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_0, 0),
	BPF_MOV32_IMM(BPF_REG_2, MAX_ENTRIES),
	BPF_JMP_REG(BPF_JSGT, BPF_REG_2, BPF_REG_1, 1),
	BPF_MOV32_IMM(BPF_REG_1, 0),
	BPF_ALU32_IMM(BPF_LSH, BPF_REG_1, 2),
	BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1),
	BPF_JMP_IMM(BPF_JA, 0, 0, 0),
	BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, offsetof(struct test_val, foo)),
	BPF_EXIT_INSN(),
	},
	.fixup_map_hash_48b = { 3 },
	.errstr_unpriv = "R0 leaks addr",
	.errstr = "R0 unbounded memory access",
	.result_unpriv = REJECT,
	.result = REJECT,
	.flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
},
{
	"search pruning: all branches should be verified (nop operation)",
	.insns = {
		BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
		BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
		BPF_ST_MEM(BPF_DW, BPF_REG_2, 0, 0),
		BPF_LD_MAP_FD(BPF_REG_1, 0),
		BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
		BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 11),
		BPF_LDX_MEM(BPF_DW, BPF_REG_3, BPF_REG_0, 0),
		BPF_JMP_IMM(BPF_JEQ, BPF_REG_3, 0xbeef, 2),
		BPF_MOV64_IMM(BPF_REG_4, 0),
		BPF_JMP_A(1),
		BPF_MOV64_IMM(BPF_REG_4, 1),
		BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_4, -16),
		BPF_EMIT_CALL(BPF_FUNC_ktime_get_ns),
		BPF_LDX_MEM(BPF_DW, BPF_REG_5, BPF_REG_10, -16),
		BPF_JMP_IMM(BPF_JEQ, BPF_REG_5, 0, 2),
		BPF_MOV64_IMM(BPF_REG_6, 0),
		BPF_ST_MEM(BPF_DW, BPF_REG_6, 0, 0xdead),
		BPF_EXIT_INSN(),
	},
	.fixup_map_hash_8b = { 3 },
	.errstr = "R6 invalid mem access 'scalar'",
	.result = REJECT,
	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
},
{
	"search pruning: all branches should be verified (invalid stack access)",
	.insns = {
		BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
		BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
		BPF_ST_MEM(BPF_DW, BPF_REG_2, 0, 0),
		BPF_LD_MAP_FD(BPF_REG_1, 0),
		BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
		BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 8),
		BPF_LDX_MEM(BPF_DW, BPF_REG_3, BPF_REG_0, 0),
		BPF_MOV64_IMM(BPF_REG_4, 0),
		BPF_JMP_IMM(BPF_JEQ, BPF_REG_3, 0xbeef, 2),
		BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_4, -16),
		BPF_JMP_A(1),
		BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_4, -24),
		BPF_EMIT_CALL(BPF_FUNC_ktime_get_ns),
		BPF_LDX_MEM(BPF_DW, BPF_REG_5, BPF_REG_10, -16),
		BPF_EXIT_INSN(),
	},
	.fixup_map_hash_8b = { 3 },
	.errstr = "invalid read from stack off -16+0 size 8",
	.result = REJECT,
	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
},
{
	"precision tracking for u32 spill/fill",
	.insns = {
		BPF_MOV64_REG(BPF_REG_7, BPF_REG_1),
		BPF_EMIT_CALL(BPF_FUNC_get_prandom_u32),
		BPF_MOV32_IMM(BPF_REG_6, 32),
		BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
		BPF_MOV32_IMM(BPF_REG_6, 4),
		/* Additional insns to introduce a pruning point. */
		BPF_EMIT_CALL(BPF_FUNC_get_prandom_u32),
		BPF_MOV64_IMM(BPF_REG_3, 0),
		BPF_MOV64_IMM(BPF_REG_3, 0),
		BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
		BPF_MOV64_IMM(BPF_REG_3, 0),
		/* u32 spill/fill */
		BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_6, -8),
		BPF_LDX_MEM(BPF_W, BPF_REG_8, BPF_REG_10, -8),
		/* out-of-bound map value access for r6=32 */
		BPF_ST_MEM(BPF_DW, BPF_REG_10, -16, 0),
		BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
		BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -16),
		BPF_LD_MAP_FD(BPF_REG_1, 0),
		BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
		BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
		BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_8),
		BPF_LDX_MEM(BPF_W, BPF_REG_1, BPF_REG_0, 0),
		BPF_MOV64_IMM(BPF_REG_0, 0),
		BPF_EXIT_INSN(),
	},
	.fixup_map_hash_8b = { 15 },
	.result = REJECT,
	.errstr = "R0 min value is outside of the allowed memory range",
	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
},
{
	"precision tracking for u32 spills, u64 fill",
	.insns = {
		BPF_EMIT_CALL(BPF_FUNC_get_prandom_u32),
		BPF_MOV64_REG(BPF_REG_6, BPF_REG_0),
		BPF_MOV32_IMM(BPF_REG_7, 0xffffffff),
		/* Additional insns to introduce a pruning point. */
		BPF_MOV64_IMM(BPF_REG_3, 1),
		BPF_MOV64_IMM(BPF_REG_3, 1),
		BPF_MOV64_IMM(BPF_REG_3, 1),
		BPF_MOV64_IMM(BPF_REG_3, 1),
		BPF_EMIT_CALL(BPF_FUNC_get_prandom_u32),
		BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
		BPF_MOV64_IMM(BPF_REG_3, 1),
		BPF_ALU32_IMM(BPF_DIV, BPF_REG_3, 0),
		/* u32 spills, u64 fill */
		BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_6, -4),
		BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_7, -8),
		BPF_LDX_MEM(BPF_DW, BPF_REG_8, BPF_REG_10, -8),
		/* if r8 != X goto pc+1  r8 known in fallthrough branch */
		BPF_JMP_IMM(BPF_JNE, BPF_REG_8, 0xffffffff, 1),
		BPF_MOV64_IMM(BPF_REG_3, 1),
		/* if r8 == X goto pc+1  condition always true on first
		 * traversal, so starts backtracking to mark r8 as requiring
		 * precision. r7 marked as needing precision. r6 not marked
		 * since it's not tracked.
		 */
		BPF_JMP_IMM(BPF_JEQ, BPF_REG_8, 0xffffffff, 1),
		/* fails if r8 correctly marked unknown after fill. */
		BPF_ALU32_IMM(BPF_DIV, BPF_REG_3, 0),
		BPF_MOV64_IMM(BPF_REG_0, 0),
		BPF_EXIT_INSN(),
	},
	.result = REJECT,
	.errstr = "div by zero",
	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
},
{
	"allocated_stack",
	.insns = {
		BPF_ALU64_REG(BPF_MOV, BPF_REG_6, BPF_REG_1),
		BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_get_prandom_u32),
		BPF_ALU64_REG(BPF_MOV, BPF_REG_7, BPF_REG_0),
		BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 5),
		BPF_MOV64_IMM(BPF_REG_0, 0),
		BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_6, -8),
		BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_10, -8),
		BPF_STX_MEM(BPF_B, BPF_REG_10, BPF_REG_7, -9),
		BPF_LDX_MEM(BPF_B, BPF_REG_7, BPF_REG_10, -9),
		BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 0),
		BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 0),
		BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 0),
		BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 0),
		BPF_EXIT_INSN(),
	},
	.result = ACCEPT,
	.result_unpriv = ACCEPT,
	.insn_processed = 15,
},
/* The test performs a conditional 64-bit write to a stack location
 * fp[-8], this is followed by an unconditional 8-bit write to fp[-8],
 * then data is read from fp[-8]. This sequence is unsafe.
 *
 * The test would be mistakenly marked as safe w/o dst register parent
 * preservation in verifier.c:copy_register_state() function.
 *
 * Note the usage of BPF_F_TEST_STATE_FREQ to force creation of the
 * checkpoint state after conditional 64-bit assignment.
 */
{
	"write tracking and register parent chain bug",
	.insns = {
	/* r6 = ktime_get_ns() */
	BPF_EMIT_CALL(BPF_FUNC_ktime_get_ns),
	BPF_MOV64_REG(BPF_REG_6, BPF_REG_0),
	/* r0 = ktime_get_ns() */
	BPF_EMIT_CALL(BPF_FUNC_ktime_get_ns),
	/* if r0 > r6 goto +1 */
	BPF_JMP_REG(BPF_JGT, BPF_REG_0, BPF_REG_6, 1),
	/* *(u64 *)(r10 - 8) = 0xdeadbeef */
	BPF_ST_MEM(BPF_DW, BPF_REG_FP, -8, 0xdeadbeef),
	/* r1 = 42 */
	BPF_MOV64_IMM(BPF_REG_1, 42),
	/* *(u8 *)(r10 - 8) = r1 */
	BPF_STX_MEM(BPF_B, BPF_REG_FP, BPF_REG_1, -8),
	/* r2 = *(u64 *)(r10 - 8) */
	BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_FP, -8),
	/* exit(0) */
	BPF_MOV64_IMM(BPF_REG_0, 0),
	BPF_EXIT_INSN(),
	},
	.flags = BPF_F_TEST_STATE_FREQ,
	.errstr = "invalid read from stack off -8+1 size 8",
	.result = REJECT,
},