| OLD | NEW |
| 1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #include "sandbox/linux/seccomp-bpf/codegen.h" | 5 #include "sandbox/linux/seccomp-bpf/codegen.h" |
| 6 | 6 |
| 7 #include <errno.h> | 7 #include <errno.h> |
| 8 #include <linux/filter.h> | 8 #include <linux/filter.h> |
| 9 | 9 |
| 10 #include <set> | 10 #include <set> |
| (...skipping 28 matching lines...) Expand all Loading... |
| 39 return CodeGen::CutGraphIntoBasicBlocks(insns, branch_targets, blocks); | 39 return CodeGen::CutGraphIntoBasicBlocks(insns, branch_targets, blocks); |
| 40 } | 40 } |
| 41 | 41 |
| 42 void MergeTails(TargetsToBlocks* blocks) { CodeGen::MergeTails(blocks); } | 42 void MergeTails(TargetsToBlocks* blocks) { CodeGen::MergeTails(blocks); } |
| 43 }; | 43 }; |
| 44 | 44 |
| 45 enum { NO_FLAGS = 0x0000, HAS_MERGEABLE_TAILS = 0x0001, }; | 45 enum { NO_FLAGS = 0x0000, HAS_MERGEABLE_TAILS = 0x0001, }; |
| 46 | 46 |
| 47 Instruction* SampleProgramOneInstruction(CodeGen* codegen, int* flags) { | 47 Instruction* SampleProgramOneInstruction(CodeGen* codegen, int* flags) { |
| 48 // Create the most basic valid BPF program: | 48 // Create the most basic valid BPF program: |
| 49 // RET ERR_ALLOWED | 49 // RET 0 |
| 50 *flags = NO_FLAGS; | 50 *flags = NO_FLAGS; |
| 51 return codegen->MakeInstruction(BPF_RET + BPF_K, | 51 return codegen->MakeInstruction(BPF_RET + BPF_K, 0); |
| 52 ErrorCode(ErrorCode::ERR_ALLOWED)); | |
| 53 } | 52 } |
| 54 | 53 |
| 55 Instruction* SampleProgramSimpleBranch(CodeGen* codegen, int* flags) { | 54 Instruction* SampleProgramSimpleBranch(CodeGen* codegen, int* flags) { |
| 56 // Create a program with a single branch: | 55 // Create a program with a single branch: |
| 57 // JUMP if eq 42 then $0 else $1 | 56 // JUMP if eq 42 then $0 else $1 |
| 58 // 0: RET EPERM | 57 // 0: RET 1 |
| 59 // 1: RET ERR_ALLOWED | 58 // 1: RET 0 |
| 60 *flags = NO_FLAGS; | 59 *flags = NO_FLAGS; |
| 61 return codegen->MakeInstruction( | 60 return codegen->MakeInstruction( |
| 62 BPF_JMP + BPF_JEQ + BPF_K, | 61 BPF_JMP + BPF_JEQ + BPF_K, |
| 63 42, | 62 42, |
| 64 codegen->MakeInstruction(BPF_RET + BPF_K, ErrorCode(EPERM)), | 63 codegen->MakeInstruction(BPF_RET + BPF_K, 1), |
| 65 codegen->MakeInstruction(BPF_RET + BPF_K, | 64 codegen->MakeInstruction(BPF_RET + BPF_K, 0)); |
| 66 ErrorCode(ErrorCode::ERR_ALLOWED))); | |
| 67 } | 65 } |
| 68 | 66 |
| 69 Instruction* SampleProgramAtypicalBranch(CodeGen* codegen, int* flags) { | 67 Instruction* SampleProgramAtypicalBranch(CodeGen* codegen, int* flags) { |
| 70 // Create a program with a single branch: | 68 // Create a program with a single branch: |
| 71 // JUMP if eq 42 then $0 else $0 | 69 // JUMP if eq 42 then $0 else $0 |
| 72 // 0: RET ERR_ALLOWED | 70 // 0: RET 0 |
| 73 | 71 |
| 74 // N.B.: As the instructions in both sides of the branch are already | 72 // N.B.: As the instructions in both sides of the branch are already |
| 75 // the same object, we do not actually have any "mergeable" branches. | 73 // the same object, we do not actually have any "mergeable" branches. |
| 76 // This needs to be reflected in our choice of "flags". | 74 // This needs to be reflected in our choice of "flags". |
| 77 *flags = NO_FLAGS; | 75 *flags = NO_FLAGS; |
| 78 | 76 |
| 79 Instruction* ret = codegen->MakeInstruction( | 77 Instruction* ret = codegen->MakeInstruction( |
| 80 BPF_RET + BPF_K, ErrorCode(ErrorCode::ERR_ALLOWED)); | 78 BPF_RET + BPF_K, 0); |
| 81 return codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 42, ret, ret); | 79 return codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 42, ret, ret); |
| 82 } | 80 } |
| 83 | 81 |
| 84 Instruction* SampleProgramComplex(CodeGen* codegen, int* flags) { | 82 Instruction* SampleProgramComplex(CodeGen* codegen, int* flags) { |
| 85 // Creates a basic BPF program that we'll use to test some of the code: | 83 // Creates a basic BPF program that we'll use to test some of the code: |
| 86 // JUMP if eq 42 the $0 else $1 (insn6) | 84 // JUMP if eq 42 the $0 else $1 (insn6) |
| 87 // 0: LD 23 (insn5) | 85 // 0: LD 23 (insn5) |
| 88 // 1: JUMP if eq 42 then $2 else $4 (insn4) | 86 // 1: JUMP if eq 42 then $2 else $4 (insn4) |
| 89 // 2: JUMP to $3 (insn1) | 87 // 2: JUMP to $3 (insn1) |
| 90 // 3: LD 42 (insn0) | 88 // 3: LD 42 (insn0) |
| 91 // RET ErrorCode(42) (insn2) | 89 // RET 42 (insn2) |
| 92 // 4: LD 42 (insn3) | 90 // 4: LD 42 (insn3) |
| 93 // RET ErrorCode(42) (insn3+) | 91 // RET 42 (insn3+) |
| 94 *flags = HAS_MERGEABLE_TAILS; | 92 *flags = HAS_MERGEABLE_TAILS; |
| 95 | 93 |
| 96 Instruction* insn0 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 42); | 94 Instruction* insn0 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 42); |
| 97 SANDBOX_ASSERT(insn0); | 95 SANDBOX_ASSERT(insn0); |
| 98 SANDBOX_ASSERT(insn0->code == BPF_LD + BPF_W + BPF_ABS); | 96 SANDBOX_ASSERT(insn0->code == BPF_LD + BPF_W + BPF_ABS); |
| 99 SANDBOX_ASSERT(insn0->k == 42); | 97 SANDBOX_ASSERT(insn0->k == 42); |
| 100 SANDBOX_ASSERT(insn0->next == NULL); | 98 SANDBOX_ASSERT(insn0->next == NULL); |
| 101 | 99 |
| 102 Instruction* insn1 = codegen->MakeInstruction(BPF_JMP + BPF_JA, 0, insn0); | 100 Instruction* insn1 = codegen->MakeInstruction(BPF_JMP + BPF_JA, 0, insn0); |
| 103 SANDBOX_ASSERT(insn1); | 101 SANDBOX_ASSERT(insn1); |
| 104 SANDBOX_ASSERT(insn1->code == BPF_JMP + BPF_JA); | 102 SANDBOX_ASSERT(insn1->code == BPF_JMP + BPF_JA); |
| 105 SANDBOX_ASSERT(insn1->jt_ptr == insn0); | 103 SANDBOX_ASSERT(insn1->jt_ptr == insn0); |
| 106 | 104 |
| 107 Instruction* insn2 = codegen->MakeInstruction(BPF_RET + BPF_K, ErrorCode(42)); | 105 Instruction* insn2 = codegen->MakeInstruction(BPF_RET + BPF_K, 42); |
| 108 SANDBOX_ASSERT(insn2); | 106 SANDBOX_ASSERT(insn2); |
| 109 SANDBOX_ASSERT(insn2->code == BPF_RET + BPF_K); | 107 SANDBOX_ASSERT(insn2->code == BPF_RET + BPF_K); |
| 110 SANDBOX_ASSERT(insn2->next == NULL); | 108 SANDBOX_ASSERT(insn2->next == NULL); |
| 111 | 109 |
| 112 // We explicitly duplicate instructions so that MergeTails() can coalesce | 110 // We explicitly duplicate instructions so that MergeTails() can coalesce |
| 113 // them later. | 111 // them later. |
| 114 Instruction* insn3 = codegen->MakeInstruction( | 112 Instruction* insn3 = codegen->MakeInstruction( |
| 115 BPF_LD + BPF_W + BPF_ABS, | 113 BPF_LD + BPF_W + BPF_ABS, |
| 116 42, | 114 42, |
| 117 codegen->MakeInstruction(BPF_RET + BPF_K, ErrorCode(42))); | 115 codegen->MakeInstruction(BPF_RET + BPF_K, 42)); |
| 118 | 116 |
| 119 Instruction* insn4 = | 117 Instruction* insn4 = |
| 120 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 42, insn1, insn3); | 118 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 42, insn1, insn3); |
| 121 SANDBOX_ASSERT(insn4); | 119 SANDBOX_ASSERT(insn4); |
| 122 SANDBOX_ASSERT(insn4->code == BPF_JMP + BPF_JEQ + BPF_K); | 120 SANDBOX_ASSERT(insn4->code == BPF_JMP + BPF_JEQ + BPF_K); |
| 123 SANDBOX_ASSERT(insn4->k == 42); | 121 SANDBOX_ASSERT(insn4->k == 42); |
| 124 SANDBOX_ASSERT(insn4->jt_ptr == insn1); | 122 SANDBOX_ASSERT(insn4->jt_ptr == insn1); |
| 125 SANDBOX_ASSERT(insn4->jf_ptr == insn3); | 123 SANDBOX_ASSERT(insn4->jf_ptr == insn3); |
| 126 | 124 |
| 127 codegen->JoinInstructions(insn0, insn2); | 125 codegen->JoinInstructions(insn0, insn2); |
| (...skipping 27 matching lines...) Expand all Loading... |
| 155 // Without the fix for this bug, this program should trigger the check in | 153 // Without the fix for this bug, this program should trigger the check in |
| 156 // CompileAndCompare: the serialized graphs from the program and its compiled | 154 // CompileAndCompare: the serialized graphs from the program and its compiled |
| 157 // version will differ. | 155 // version will differ. |
| 158 // | 156 // |
| 159 // 0) LOAD 1 // ??? | 157 // 0) LOAD 1 // ??? |
| 160 // 1) if A == 0x1; then JMP 2 else JMP 3 | 158 // 1) if A == 0x1; then JMP 2 else JMP 3 |
| 161 // 2) LOAD 0 // System call number | 159 // 2) LOAD 0 // System call number |
| 162 // 3) if A == 0x2; then JMP 4 else JMP 5 | 160 // 3) if A == 0x2; then JMP 4 else JMP 5 |
| 163 // 4) LOAD 0 // System call number | 161 // 4) LOAD 0 // System call number |
| 164 // 5) if A == 0x1; then JMP 6 else JMP 7 | 162 // 5) if A == 0x1; then JMP 6 else JMP 7 |
| 165 // 6) RET 0x50000 // errno = 0 | 163 // 6) RET 0 |
| 166 // 7) RET 0x50001 // errno = 1 | 164 // 7) RET 1 |
| 167 *flags = NO_FLAGS; | 165 *flags = NO_FLAGS; |
| 168 | 166 |
| 169 Instruction* i7 = codegen->MakeInstruction(BPF_RET, ErrorCode(1)); | 167 Instruction* i7 = codegen->MakeInstruction(BPF_RET + BPF_K, 1); |
| 170 Instruction* i6 = codegen->MakeInstruction(BPF_RET, ErrorCode(0)); | 168 Instruction* i6 = codegen->MakeInstruction(BPF_RET + BPF_K, 0); |
| 171 Instruction* i5 = | 169 Instruction* i5 = |
| 172 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i6, i7); | 170 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i6, i7); |
| 173 Instruction* i4 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 0, i5); | 171 Instruction* i4 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 0, i5); |
| 174 Instruction* i3 = | 172 Instruction* i3 = |
| 175 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 2, i4, i5); | 173 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 2, i4, i5); |
| 176 Instruction* i2 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 0, i3); | 174 Instruction* i2 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 0, i3); |
| 177 Instruction* i1 = | 175 Instruction* i1 = |
| 178 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i2, i3); | 176 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i2, i3); |
| 179 Instruction* i0 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 1, i1); | 177 Instruction* i0 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 1, i1); |
| 180 | 178 |
| 181 return i0; | 179 return i0; |
| 182 } | 180 } |
| 183 | 181 |
| 184 Instruction* SampleProgramConfusingTailsBasic(CodeGen* codegen, int* flags) { | 182 Instruction* SampleProgramConfusingTailsBasic(CodeGen* codegen, int* flags) { |
| 185 // Without the fix for https://crbug.com/351103/, (see | 183 // Without the fix for https://crbug.com/351103/, (see |
| 186 // SampleProgramConfusingTails()), this would generate a cyclic graph and | 184 // SampleProgramConfusingTails()), this would generate a cyclic graph and |
| 187 // crash as the two "LOAD 0" instructions would get merged. | 185 // crash as the two "LOAD 0" instructions would get merged. |
| 188 // | 186 // |
| 189 // 0) LOAD 1 // ??? | 187 // 0) LOAD 1 // ??? |
| 190 // 1) if A == 0x1; then JMP 2 else JMP 3 | 188 // 1) if A == 0x1; then JMP 2 else JMP 3 |
| 191 // 2) LOAD 0 // System call number | 189 // 2) LOAD 0 // System call number |
| 192 // 3) if A == 0x2; then JMP 4 else JMP 5 | 190 // 3) if A == 0x2; then JMP 4 else JMP 5 |
| 193 // 4) LOAD 0 // System call number | 191 // 4) LOAD 0 // System call number |
| 194 // 5) RET 0x50001 // errno = 1 | 192 // 5) RET 1 |
| 195 *flags = NO_FLAGS; | 193 *flags = NO_FLAGS; |
| 196 | 194 |
| 197 Instruction* i5 = codegen->MakeInstruction(BPF_RET, ErrorCode(1)); | 195 Instruction* i5 = codegen->MakeInstruction(BPF_RET + BPF_K, 1); |
| 198 Instruction* i4 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 0, i5); | 196 Instruction* i4 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 0, i5); |
| 199 Instruction* i3 = | 197 Instruction* i3 = |
| 200 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 2, i4, i5); | 198 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 2, i4, i5); |
| 201 Instruction* i2 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 0, i3); | 199 Instruction* i2 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 0, i3); |
| 202 Instruction* i1 = | 200 Instruction* i1 = |
| 203 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i2, i3); | 201 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i2, i3); |
| 204 Instruction* i0 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 1, i1); | 202 Instruction* i0 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 1, i1); |
| 205 | 203 |
| 206 return i0; | 204 return i0; |
| 207 } | 205 } |
| 208 | 206 |
| 209 Instruction* SampleProgramConfusingTailsMergeable(CodeGen* codegen, | 207 Instruction* SampleProgramConfusingTailsMergeable(CodeGen* codegen, |
| 210 int* flags) { | 208 int* flags) { |
| 211 // This is similar to SampleProgramConfusingTails(), except that | 209 // This is similar to SampleProgramConfusingTails(), except that |
| 212 // instructions 2 and 4 are now RET instructions. | 210 // instructions 2 and 4 are now RET instructions. |
| 213 // In PointerCompare(), this exercises the path where two blocks are of the | 211 // In PointerCompare(), this exercises the path where two blocks are of the |
| 214 // same length and identical and the last instruction is a JMP or RET, so the | 212 // same length and identical and the last instruction is a JMP or RET, so the |
| 215 // following blocks don't need to be looked at and the blocks are mergeable. | 213 // following blocks don't need to be looked at and the blocks are mergeable. |
| 216 // | 214 // |
| 217 // 0) LOAD 1 // ??? | 215 // 0) LOAD 1 // ??? |
| 218 // 1) if A == 0x1; then JMP 2 else JMP 3 | 216 // 1) if A == 0x1; then JMP 2 else JMP 3 |
| 219 // 2) RET 0x5002a // errno = 42 | 217 // 2) RET 42 |
| 220 // 3) if A == 0x2; then JMP 4 else JMP 5 | 218 // 3) if A == 0x2; then JMP 4 else JMP 5 |
| 221 // 4) RET 0x5002a // errno = 42 | 219 // 4) RET 42 |
| 222 // 5) if A == 0x1; then JMP 6 else JMP 7 | 220 // 5) if A == 0x1; then JMP 6 else JMP 7 |
| 223 // 6) RET 0x50000 // errno = 0 | 221 // 6) RET 0 |
| 224 // 7) RET 0x50001 // errno = 1 | 222 // 7) RET 1 |
| 225 *flags = HAS_MERGEABLE_TAILS; | 223 *flags = HAS_MERGEABLE_TAILS; |
| 226 | 224 |
| 227 Instruction* i7 = codegen->MakeInstruction(BPF_RET, ErrorCode(1)); | 225 Instruction* i7 = codegen->MakeInstruction(BPF_RET + BPF_K, 1); |
| 228 Instruction* i6 = codegen->MakeInstruction(BPF_RET, ErrorCode(0)); | 226 Instruction* i6 = codegen->MakeInstruction(BPF_RET + BPF_K, 0); |
| 229 Instruction* i5 = | 227 Instruction* i5 = |
| 230 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i6, i7); | 228 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i6, i7); |
| 231 Instruction* i4 = codegen->MakeInstruction(BPF_RET, ErrorCode(42)); | 229 Instruction* i4 = codegen->MakeInstruction(BPF_RET + BPF_K, 42); |
| 232 Instruction* i3 = | 230 Instruction* i3 = |
| 233 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 2, i4, i5); | 231 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 2, i4, i5); |
| 234 Instruction* i2 = codegen->MakeInstruction(BPF_RET, ErrorCode(42)); | 232 Instruction* i2 = codegen->MakeInstruction(BPF_RET + BPF_K, 42); |
| 235 Instruction* i1 = | 233 Instruction* i1 = |
| 236 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i2, i3); | 234 codegen->MakeInstruction(BPF_JMP + BPF_JEQ + BPF_K, 1, i2, i3); |
| 237 Instruction* i0 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 1, i1); | 235 Instruction* i0 = codegen->MakeInstruction(BPF_LD + BPF_W + BPF_ABS, 1, i1); |
| 238 | 236 |
| 239 return i0; | 237 return i0; |
| 240 } | 238 } |
| 241 void ForAllPrograms(void (*test)(CodeGenUnittestHelper*, Instruction*, int)) { | 239 void ForAllPrograms(void (*test)(CodeGenUnittestHelper*, Instruction*, int)) { |
| 242 Instruction* (*function_table[])(CodeGen* codegen, int* flags) = { | 240 Instruction* (*function_table[])(CodeGen* codegen, int* flags) = { |
| 243 SampleProgramOneInstruction, | 241 SampleProgramOneInstruction, |
| 244 SampleProgramSimpleBranch, | 242 SampleProgramSimpleBranch, |
| (...skipping 289 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 534 assembly.append(reinterpret_cast<char*>(&insn.k), sizeof(insn.k)); | 532 assembly.append(reinterpret_cast<char*>(&insn.k), sizeof(insn.k)); |
| 535 } | 533 } |
| 536 SANDBOX_ASSERT(source == assembly); | 534 SANDBOX_ASSERT(source == assembly); |
| 537 } | 535 } |
| 538 | 536 |
| 539 SANDBOX_TEST(CodeGen, All) { | 537 SANDBOX_TEST(CodeGen, All) { |
| 540 ForAllPrograms(CompileAndCompare); | 538 ForAllPrograms(CompileAndCompare); |
| 541 } | 539 } |
| 542 | 540 |
| 543 } // namespace sandbox | 541 } // namespace sandbox |
| OLD | NEW |