1 #include "sandboxed_api/sandbox2/bpf_evaluator.h"
2
3 #include <linux/bpf_common.h>
4 #include <linux/filter.h>
5 #include <linux/seccomp.h>
6
7 #include <cstdint>
8 #include <cstring>
9 #include <limits>
10 #include <optional>
11
12 #include "absl/status/status.h"
13 #include "absl/status/statusor.h"
14 #include "absl/strings/str_cat.h"
15 #include "absl/types/span.h"
16 #include "sandboxed_api/util/status_macros.h"
17
18 namespace sandbox2::bpf {
19 namespace {
20
EvaluateAlu(uint16_t op,uint32_t a,uint32_t b)21 absl::StatusOr<uint32_t> EvaluateAlu(uint16_t op, uint32_t a, uint32_t b) {
22 switch (op) {
23 case BPF_ADD:
24 return a + b;
25 case BPF_SUB:
26 return a - b;
27 case BPF_MUL:
28 return a * b;
29 case BPF_DIV:
30 if (b == 0) {
31 return absl::InvalidArgumentError("Division by zero");
32 }
33 return a / b;
34 case BPF_OR:
35 return a | b;
36 case BPF_AND:
37 return a & b;
38 case BPF_XOR:
39 return a ^ b;
40 case BPF_LSH:
41 return a << b;
42 case BPF_RSH:
43 return a >> b;
44 case BPF_NEG:
45 return -a;
46 default:
47 return absl::InvalidArgumentError("Invalid ALU operation");
48 }
49 }
50
EvaluateCmp(uint16_t cmp,uint32_t a,uint32_t b)51 absl::StatusOr<bool> EvaluateCmp(uint16_t cmp, uint32_t a, uint32_t b) {
52 switch (cmp) {
53 case BPF_JEQ:
54 return a == b;
55 case BPF_JGT:
56 return a > b;
57 case BPF_JGE:
58 return a >= b;
59 case BPF_JSET:
60 return (a & b) != 0;
61 default:
62 return absl::InvalidArgumentError("Invalid jump operation");
63 }
64 }
65
66 class Interpreter {
67 public:
Interpreter(absl::Span<const sock_filter> prog,const struct seccomp_data & data)68 Interpreter(absl::Span<const sock_filter> prog,
69 const struct seccomp_data& data)
70 : prog_(prog), data_(data) {}
71 absl::StatusOr<uint32_t> Evaluate();
72
73 private:
74 absl::Status EvaluateSingleInstruction();
75
76 absl::Span<const sock_filter> prog_;
77 const struct seccomp_data& data_;
78 uint32_t pc_;
79 uint32_t accumulator_;
80 uint32_t x_reg_;
81 uint32_t mem_[16];
82 std::optional<uint32_t> result_;
83 };
84
EvaluateSingleInstruction()85 absl::Status Interpreter::EvaluateSingleInstruction() {
86 if (pc_ >= prog_.size()) {
87 return absl::InvalidArgumentError("Out of bounds execution");
88 }
89 const sock_filter& inst = prog_[pc_];
90 uint32_t offset = 0;
91 switch (inst.code) {
92 case BPF_LD | BPF_W | BPF_ABS: {
93 constexpr uint32_t kAlignmentMask = 3;
94 if (inst.k & kAlignmentMask) {
95 return absl::InvalidArgumentError(
96 absl::StrCat("Misaligned read (", inst.k, ")"));
97 }
98 if (inst.k + sizeof(accumulator_) > sizeof(data_)) {
99 return absl::InvalidArgumentError(
100 absl::StrCat("Out of bounds read (", inst.k, ")"));
101 }
102 memcpy(&accumulator_, &(reinterpret_cast<const char*>(&data_)[inst.k]),
103 sizeof(accumulator_));
104 break;
105 }
106 case BPF_LD | BPF_W | BPF_LEN:
107 accumulator_ = sizeof(struct seccomp_data);
108 break;
109 case BPF_LDX | BPF_W | BPF_LEN:
110 x_reg_ = sizeof(struct seccomp_data);
111 break;
112 case BPF_LD | BPF_IMM:
113 accumulator_ = inst.k;
114 break;
115 case BPF_LDX | BPF_IMM:
116 x_reg_ = inst.k;
117 break;
118 case BPF_MISC | BPF_TAX:
119 x_reg_ = accumulator_;
120 break;
121 case BPF_MISC | BPF_TXA:
122 accumulator_ = x_reg_;
123 break;
124 case BPF_LD | BPF_MEM:
125 if (inst.k >= sizeof(mem_) / sizeof(mem_[0])) {
126 return absl::InvalidArgumentError(
127 absl::StrCat("Out of bounds memory load (", inst.k, " >= 16)"));
128 }
129 accumulator_ = mem_[inst.k];
130 break;
131 case BPF_LDX | BPF_MEM:
132 if (inst.k >= sizeof(mem_) / sizeof(mem_[0])) {
133 return absl::InvalidArgumentError(
134 absl::StrCat("Out of bounds memory load (", inst.k, " >= 16)"));
135 }
136 x_reg_ = mem_[inst.k];
137 break;
138 case BPF_ST:
139 if (inst.k >= sizeof(mem_) / sizeof(mem_[0])) {
140 return absl::InvalidArgumentError(
141 absl::StrCat("Out of bounds memory store (", inst.k, " >= 16)"));
142 }
143 mem_[inst.k] = accumulator_;
144 break;
145 case BPF_STX:
146 if (inst.k >= sizeof(mem_) / sizeof(mem_[0])) {
147 return absl::InvalidArgumentError(
148 absl::StrCat("Out of bounds memory store (", inst.k, " >= 16)"));
149 }
150 mem_[inst.k] = x_reg_;
151 break;
152 case BPF_RET | BPF_K:
153 result_ = inst.k;
154 return absl::OkStatus();
155 case BPF_RET | BPF_A:
156 result_ = accumulator_;
157 return absl::OkStatus();
158 case BPF_ALU | BPF_ADD | BPF_K:
159 case BPF_ALU | BPF_SUB | BPF_K:
160 case BPF_ALU | BPF_MUL | BPF_K:
161 case BPF_ALU | BPF_DIV | BPF_K:
162 case BPF_ALU | BPF_AND | BPF_K:
163 case BPF_ALU | BPF_OR | BPF_K:
164 case BPF_ALU | BPF_XOR | BPF_K:
165 case BPF_ALU | BPF_LSH | BPF_K:
166 case BPF_ALU | BPF_RSH | BPF_K:
167 case BPF_ALU | BPF_ADD | BPF_X:
168 case BPF_ALU | BPF_SUB | BPF_X:
169 case BPF_ALU | BPF_MUL | BPF_X:
170 case BPF_ALU | BPF_DIV | BPF_X:
171 case BPF_ALU | BPF_AND | BPF_X:
172 case BPF_ALU | BPF_OR | BPF_X:
173 case BPF_ALU | BPF_XOR | BPF_X:
174 case BPF_ALU | BPF_LSH | BPF_X:
175 case BPF_ALU | BPF_RSH | BPF_X:
176 case BPF_ALU | BPF_NEG: {
177 uint32_t val = BPF_SRC(inst.code) == BPF_K ? inst.k : x_reg_;
178 SAPI_ASSIGN_OR_RETURN(accumulator_,
179 EvaluateAlu(BPF_OP(inst.code), accumulator_, val));
180 break;
181 }
182 case BPF_JMP | BPF_JA:
183 offset = inst.k;
184 break;
185 case BPF_JMP | BPF_JEQ | BPF_K:
186 case BPF_JMP | BPF_JGE | BPF_K:
187 case BPF_JMP | BPF_JGT | BPF_K:
188 case BPF_JMP | BPF_JSET | BPF_K:
189 case BPF_JMP | BPF_JEQ | BPF_X:
190 case BPF_JMP | BPF_JGE | BPF_X:
191 case BPF_JMP | BPF_JGT | BPF_X:
192 case BPF_JMP | BPF_JSET | BPF_X: {
193 uint32_t val = BPF_SRC(inst.code) == BPF_K ? inst.k : x_reg_;
194 SAPI_ASSIGN_OR_RETURN(bool cond,
195 EvaluateCmp(BPF_OP(inst.code), accumulator_, val));
196 offset = cond ? inst.jt : inst.jf;
197 break;
198 }
199 default:
200 return absl::InvalidArgumentError(
201 absl::StrCat("Invalid instruction ", inst.code));
202 }
203 if (pc_ > std::numeric_limits<uint32_t>::max() - 1 ||
204 pc_ + 1 >= prog_.size()) {
205 return absl::InvalidArgumentError(
206 "Fall through to out of bounds execution");
207 }
208 pc_ += 1;
209 if (offset != 0 && (pc_ > std::numeric_limits<uint32_t>::max() - offset ||
210 pc_ + offset >= prog_.size())) {
211 return absl::InvalidArgumentError("Out of bounds jump");
212 }
213 pc_ += offset;
214 return absl::OkStatus();
215 }
216
Evaluate()217 absl::StatusOr<uint32_t> Interpreter::Evaluate() {
218 pc_ = 0;
219 result_ = std::nullopt;
220 while (!result_.has_value()) {
221 SAPI_RETURN_IF_ERROR(EvaluateSingleInstruction());
222 }
223 return *result_;
224 }
225
226 } // namespace
227
Evaluate(absl::Span<const sock_filter> prog,const struct seccomp_data & data)228 absl::StatusOr<uint32_t> Evaluate(absl::Span<const sock_filter> prog,
229 const struct seccomp_data& data) {
230 Interpreter interpreter(prog, data);
231 return interpreter.Evaluate();
232 }
233
234 } // namespace sandbox2::bpf
235