diff options
author | Paul Jensen <pauljensen@google.com> | 2016-05-19 14:56:47 +0000 |
---|---|---|
committer | android-build-merger <android-build-merger@google.com> | 2016-05-19 14:56:47 +0000 |
commit | 4adcbdf494d8d85a5a1a3cf4bafd26201503e692 (patch) | |
tree | a0defb8950dfa694ca90f8c203f51da8924544b4 | |
parent | 8b1dd50bcf427b246ca83a1b022db32b9df28a3c (diff) | |
parent | 63269f85d445700a637be6297e7083259189a460 (diff) | |
download | apf-4adcbdf494d8d85a5a1a3cf4bafd26201503e692.tar.gz |
Add APF disassembler for testing purposes. am: 497d4ee96c
am: 63269f85d4
* commit '63269f85d445700a637be6297e7083259189a460':
Add APF disassembler for testing purposes.
Change-Id: I7bbed949782ebdc4e83c34b9b713bd9706a8620a
-rw-r--r-- | apf.h | 161 | ||||
-rw-r--r-- | apf_disassembler.c | 216 | ||||
-rw-r--r-- | apf_interpreter.c | 146 |
3 files changed, 378 insertions, 145 deletions
@@ -0,0 +1,161 @@ +/* + * Copyright 2016, The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +// A brief overview of APF: +// +// APF machine is composed of: +// 1. A read-only program consisting of bytecodes as described below. +// 2. Two 32-bit registers, called R0 and R1. +// 3. Sixteen 32-bit memory slots. +// 4. A read-only packet. +// The program is executed by the interpreter below and parses the packet +// to determine if the application processor (AP) should be woken up to +// handle the packet or if can be dropped. +// +// APF bytecode description: +// +// The APF interpreter uses big-endian byte order for loads from the packet +// and for storing immediates in instructions. +// +// Each instruction starts with a byte composed of: +// Top 5 bits form "opcode" field, see *_OPCODE defines below. +// Next 2 bits form "size field", which indicate the length of an immediate +// value which follows the first byte. Values in this field: +// 0 => immediate value is 0 and no bytes follow. +// 1 => immediate value is 1 byte big. +// 2 => immediate value is 2 bytes big. +// 3 => immediate value is 4 bytes big. +// Bottom bit forms "register" field, which indicates which register this +// instruction operates on. +// +// There are three main categories of instructions: +// Load instructions +// These instructions load byte(s) of the packet into a register. +// They load either 1, 2 or 4 bytes, as determined by the "opcode" field. +// They load into the register specified by the "register" field. +// The immediate value that follows the first byte of the instruction is +// the byte offset from the begining of the packet to load from. +// There are "indexing" loads which add the value in R1 to the byte offset +// to load from. The "opcode" field determines which loads are "indexing". +// Arithmetic instructions +// These instructions perform simple operations, like addition, on register +// values. The result of these instructions is always written into R0. One +// argument of the arithmetic operation is R0's value. The other argument +// of the arithmetic operation is determined by the "register" field: +// If the "register" field is 0 then the immediate value following +// the first byte of the instruction is used as the other argument +// to the arithmetic operation. +// If the "register" field is 1 then R1's value is used as the other +// argument to the arithmetic operation. +// Conditional jump instructions +// These instructions compare register R0's value with another value, and if +// the comparison succeeds, jump (i.e. adjust the program counter). The +// immediate value that follows the first byte of the instruction +// represents the jump target offset, i.e. the value added to the program +// counter if the comparison succeeds. The other value compared is +// determined by the "register" field: +// If the "register" field is 0 then another immediate value +// follows the jump target offset. This immediate value is of the +// same size as the jump target offset, and represents the value +// to compare against. +// If the "register" field is 1 then register R1's value is +// compared against. +// The type of comparison (e.g. equal to, greater than etc) is determined +// by the "opcode" field. The comparison interprets both values being +// compared as unsigned values. +// +// Miscellaneous details: +// +// Pre-filled memory slot values +// When the APF program begins execution, three of the sixteen memory slots +// are pre-filled by the interpreter with values that may be useful for +// programs: +// Slot #13 is filled with the IPv4 header length. This value is calculated +// by loading the first byte of the IPv4 header and taking the +// bottom 4 bits and multiplying their value by 4. This value is +// set to zero if the first 4 bits after the link layer header are +// not 4, indicating not IPv4. +// Slot #14 is filled with size of the packet in bytes, including the +// link-layer header if any. +// Slot #15 is filled with the filter age in seconds. This is the number of +// seconds since the AP send the program to the chipset. This may +// be used by filters that should have a particular lifetime. For +// example, it can be used to rate-limit particular packets to one +// every N seconds. +// Special jump targets: +// When an APF program executes a jump to the byte immediately after the last +// byte of the progam (i.e., one byte past the end of the program), this +// signals the program has completed and determined the packet should be +// passed to the AP. +// When an APF program executes a jump two bytes past the end of the program, +// this signals the program has completed and determined the packet should +// be dropped. +// Jump if byte sequence doesn't match: +// This is a special instruction to facilitate matching long sequences of +// bytes in the packet. Initially it is encoded like a conditional jump +// instruction with two exceptions: +// The first byte of the instruction is always followed by two immediate +// fields: The first immediate field is the jump target offset like other +// conditional jump instructions. The second immediate field specifies the +// number of bytes to compare. +// These two immediate fields are followed by a sequence of bytes. These +// bytes are compared with the bytes in the packet starting from the +// position specified by the value of the register specified by the +// "register" field of the instruction. + +// Number of memory slots, see ldm/stm instructions. +#define MEMORY_ITEMS 16 +// Upon program execution starting some memory slots are prefilled: +#define MEMORY_OFFSET_IPV4_HEADER_SIZE 13 // 4*([APF_FRAME_HEADER_SIZE]&15) +#define MEMORY_OFFSET_PACKET_SIZE 14 // Size of packet in bytes. +#define MEMORY_OFFSET_FILTER_AGE 15 // Age since filter installed in seconds. + +// Leave 0 opcode unused as it's a good indicator of accidental incorrect execution (e.g. data). +#define LDB_OPCODE 1 // Load 1 byte from immediate offset, e.g. "ldb R0, [5]" +#define LDH_OPCODE 2 // Load 2 bytes from immediate offset, e.g. "ldh R0, [5]" +#define LDW_OPCODE 3 // Load 4 bytes from immediate offset, e.g. "ldw R0, [5]" +#define LDBX_OPCODE 4 // Load 1 byte from immediate offset plus register, e.g. "ldbx R0, [5]R0" +#define LDHX_OPCODE 5 // Load 2 byte from immediate offset plus register, e.g. "ldhx R0, [5]R0" +#define LDWX_OPCODE 6 // Load 4 byte from immediate offset plus register, e.g. "ldwx R0, [5]R0" +#define ADD_OPCODE 7 // Add, e.g. "add R0,5" +#define MUL_OPCODE 8 // Multiply, e.g. "mul R0,5" +#define DIV_OPCODE 9 // Divide, e.g. "div R0,5" +#define AND_OPCODE 10 // And, e.g. "and R0,5" +#define OR_OPCODE 11 // Or, e.g. "or R0,5" +#define SH_OPCODE 12 // Left shift, e.g, "sh R0, 5" or "sh R0, -5" (shifts right) +#define LI_OPCODE 13 // Load immediate, e.g. "li R0,5" (immediate encoded as signed value) +#define JMP_OPCODE 14 // Unconditional jump, e.g. "jmp label" +#define JEQ_OPCODE 15 // Compare equal and branch, e.g. "jeq R0,5,label" +#define JNE_OPCODE 16 // Compare not equal and branch, e.g. "jne R0,5,label" +#define JGT_OPCODE 17 // Compare greater than and branch, e.g. "jgt R0,5,label" +#define JLT_OPCODE 18 // Compare less than and branch, e.g. "jlt R0,5,label" +#define JSET_OPCODE 19 // Compare any bits set and branch, e.g. "jset R0,5,label" +#define JNEBS_OPCODE 20 // Compare not equal byte sequence, e.g. "jnebs R0,5,label,0x1122334455" +#define EXT_OPCODE 21 // Immediate value is one of *_EXT_OPCODE +// Extended opcodes. These all have an opcode of EXT_OPCODE +// and specify the actual opcode in the immediate field. +#define LDM_EXT_OPCODE 0 // Load from memory, e.g. "ldm R0,5" + // Values 0-15 represent loading the different memory slots. +#define STM_EXT_OPCODE 16 // Store to memory, e.g. "stm R0,5" + // Values 16-31 represent storing to the different memory slots. +#define NOT_EXT_OPCODE 32 // Not, e.g. "not R0" +#define NEG_EXT_OPCODE 33 // Negate, e.g. "neg R0" +#define SWAP_EXT_OPCODE 34 // Swap, e.g. "swap R0,R1" +#define MOV_EXT_OPCODE 35 // Move, e.g. "move R0,R1" + +#define EXTRACT_OPCODE(i) (((i) >> 3) & 31) +#define EXTRACT_REGISTER(i) ((i) & 1) +#define EXTRACT_IMM_LENGTH(i) (((i) >> 1) & 3) diff --git a/apf_disassembler.c b/apf_disassembler.c new file mode 100644 index 0000000..7f47b6d --- /dev/null +++ b/apf_disassembler.c @@ -0,0 +1,216 @@ +/* + * Copyright 2016, The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <stdint.h> +#include <stdio.h> + +#include "apf.h" + +// If "c" is of an unsigned type, generate a compile warning that gets promoted to an error. +// This makes bounds checking simpler because ">= 0" can be avoided. Otherwise adding +// superfluous ">= 0" with unsigned expressions generates compile warnings. +#define ENFORCE_UNSIGNED(c) ((c)==(uint32_t)(c)) + +static void print_opcode(const char* opcode) { + printf("%-6s", opcode); +} + +// Mapping from opcode number to opcode name. +static const char* opcode_names [] = { + [LDB_OPCODE] = "ldb", + [LDH_OPCODE] = "ldh", + [LDW_OPCODE] = "ldw", + [LDBX_OPCODE] = "ldb", + [LDHX_OPCODE] = "ldh", + [LDWX_OPCODE] = "ldw", + [ADD_OPCODE] = "add", + [MUL_OPCODE] = "mul", + [DIV_OPCODE] = "div", + [AND_OPCODE] = "and", + [OR_OPCODE] = "or", + [SH_OPCODE] = "sh", + [LI_OPCODE] = "li", + [JMP_OPCODE] = "jmp", + [JEQ_OPCODE] = "jeq", + [JNE_OPCODE] = "jne", + [JGT_OPCODE] = "jgt", + [JLT_OPCODE] = "jlt", + [JSET_OPCODE] = "jset", + [JNEBS_OPCODE] = "jnebs", +}; + +// Disassembles an APF program. A hex dump of the program is supplied on stdin. +// +// NOTE: This is a simple debugging tool not meant for shipping or production use. It is by no +// means hardened against malicious input and contains known vulnerabilities. +// +// Example usage: +// cc apf_disassemlber.c +// adb shell dumpsys wifi ipmanager | sed '/Last program:/,+1!d;/Last program:/d;s/[ ]*//' | ./a.out +int main(int argc, char* argv[]) { + uint32_t program_len = 0; + uint8_t program[10000]; + + // Read in hex program bytes + int byte; + while (scanf("%2x", &byte) == 1 && program_len < sizeof(program)) { + program[program_len++] = byte; + } + + // Program counter. + uint32_t pc = 0; + while (pc < program_len + 2) { + printf("%8u: ", pc); + const uint8_t bytecode = program[pc++]; + if (pc == (program_len + 1)) { + printf("pass\n"); + continue; + } else if (pc == (program_len + 2)) { + printf("drop\n"); + continue; + } + const uint32_t opcode = EXTRACT_OPCODE(bytecode); +#define PRINT_OPCODE() print_opcode(opcode_names[opcode]) + const uint32_t reg_num = EXTRACT_REGISTER(bytecode); + // All instructions have immediate fields, so load them now. + const uint32_t len_field = EXTRACT_IMM_LENGTH(bytecode); + uint32_t imm = 0; + int32_t signed_imm = 0; + if (len_field != 0) { + const uint32_t imm_len = 1 << (len_field - 1); + uint32_t i; + for (i = 0; i < imm_len; i++) + imm = (imm << 8) | program[pc++]; + // Sign extend imm into signed_imm. + signed_imm = imm << ((4 - imm_len) * 8); + signed_imm >>= (4 - imm_len) * 8; + } + switch (opcode) { + case LDB_OPCODE: + case LDH_OPCODE: + case LDW_OPCODE: + PRINT_OPCODE(); + printf("r%d, [%u]", reg_num, imm); + break; + case LDBX_OPCODE: + case LDHX_OPCODE: + case LDWX_OPCODE: + PRINT_OPCODE(); + printf("r%d, [%u+r1]", reg_num, imm); + break; + case JMP_OPCODE: + PRINT_OPCODE(); + printf("%u", pc + imm); + break; + case JEQ_OPCODE: + case JNE_OPCODE: + case JGT_OPCODE: + case JLT_OPCODE: + case JSET_OPCODE: + case JNEBS_OPCODE: { + PRINT_OPCODE(); + printf("r0, "); + // Load second immediate field. + uint32_t cmp_imm = 0; + if (reg_num == 1) { + printf("r1"); + } else if (len_field == 0) { + printf("0"); + } else { + uint32_t cmp_imm_len = 1 << (len_field - 1); + uint32_t i; + for (i = 0; i < cmp_imm_len; i++) + cmp_imm = (cmp_imm << 8) | program[pc++]; + printf("0x%x", cmp_imm); + } + if (opcode == JNEBS_OPCODE) { + printf(", %u, ", pc + imm + cmp_imm); + while (cmp_imm--) + printf("%02x", program[pc++]); + } else { + printf(", %u", pc + imm); + } + break; + } + case ADD_OPCODE: + case SH_OPCODE: + PRINT_OPCODE(); + if (reg_num) { + printf("r0, r1"); + } else { + printf("r0, %d", signed_imm); + } + break; + case MUL_OPCODE: + case DIV_OPCODE: + case AND_OPCODE: + case OR_OPCODE: + PRINT_OPCODE(); + if (reg_num) { + printf("r0, r1"); + } else { + printf("r0, %u", imm); + } + break; + case LI_OPCODE: + PRINT_OPCODE(); + printf("r%d, %d", reg_num, signed_imm); + break; + case EXT_OPCODE: + if ( +// If LDM_EXT_OPCODE is 0 and imm is compared with it, a compiler error will result, +// instead just enforce that imm is unsigned (so it's always greater or equal to 0). +#if LDM_EXT_OPCODE == 0 + ENFORCE_UNSIGNED(imm) && +#else + imm >= LDM_EXT_OPCODE && +#endif + imm < (LDM_EXT_OPCODE + MEMORY_ITEMS)) { + print_opcode("ldm"); + printf("r%d, m[%u]", reg_num, imm - LDM_EXT_OPCODE); + } else if (imm >= STM_EXT_OPCODE && imm < (STM_EXT_OPCODE + MEMORY_ITEMS)) { + print_opcode("stm"); + printf("r%d, m[%u]", reg_num, imm - STM_EXT_OPCODE); + } else switch (imm) { + case NOT_EXT_OPCODE: + print_opcode("not"); + printf("r%d", reg_num); + break; + case NEG_EXT_OPCODE: + print_opcode("neg"); + printf("r%d", reg_num); + break; + case SWAP_EXT_OPCODE: + print_opcode("swap"); + break; + case MOV_EXT_OPCODE: + print_opcode("mov"); + printf("r%d, r%d", reg_num, reg_num ^ 1); + break; + default: + printf("unknown_ext %u", imm); + break; + } + break; + // Unknown opcode + default: + printf("unknown %u", opcode); + break; + } + printf("\n"); + } + return 0; +} diff --git a/apf_interpreter.c b/apf_interpreter.c index abe4c5e..924b23e 100644 --- a/apf_interpreter.c +++ b/apf_interpreter.c @@ -18,151 +18,7 @@ #include <string.h> // For memcmp -// A brief overview of APF: -// -// APF machine is composed of: -// 1. A read-only program consisting of bytecodes as described below. -// 2. Two 32-bit registers, called R0 and R1. -// 3. Sixteen 32-bit memory slots. -// 4. A read-only packet. -// The program is executed by the interpreter below and parses the packet -// to determine if the application processor (AP) should be woken up to -// handle the packet or if can be dropped. -// -// APF bytecode description: -// -// The APF interpreter uses big-endian byte order for loads from the packet -// and for storing immediates in instructions. -// -// Each instruction starts with a byte composed of: -// Top 5 bits form "opcode" field, see *_OPCODE defines below. -// Next 2 bits form "size field", which indicate the length of an immediate -// value which follows the first byte. Values in this field: -// 0 => immediate value is 0 and no bytes follow. -// 1 => immediate value is 1 byte big. -// 2 => immediate value is 2 bytes big. -// 3 => immediate value is 4 bytes big. -// Bottom bit forms "register" field, which indicates which register this -// instruction operates on. -// -// There are three main categories of instructions: -// Load instructions -// These instructions load byte(s) of the packet into a register. -// They load either 1, 2 or 4 bytes, as determined by the "opcode" field. -// They load into the register specified by the "register" field. -// The immediate value that follows the first byte of the instruction is -// the byte offset from the begining of the packet to load from. -// There are "indexing" loads which add the value in R1 to the byte offset -// to load from. The "opcode" field determines which loads are "indexing". -// Arithmetic instructions -// These instructions perform simple operations, like addition, on register -// values. The result of these instructions is always written into R0. One -// argument of the arithmetic operation is R0's value. The other argument -// of the arithmetic operation is determined by the "register" field: -// If the "register" field is 0 then the immediate value following -// the first byte of the instruction is used as the other argument -// to the arithmetic operation. -// If the "register" field is 1 then R1's value is used as the other -// argument to the arithmetic operation. -// Conditional jump instructions -// These instructions compare register R0's value with another value, and if -// the comparison succeeds, jump (i.e. adjust the program counter). The -// immediate value that follows the first byte of the instruction -// represents the jump target offset, i.e. the value added to the program -// counter if the comparison succeeds. The other value compared is -// determined by the "register" field: -// If the "register" field is 0 then another immediate value -// follows the jump target offset. This immediate value is of the -// same size as the jump target offset, and represents the value -// to compare against. -// If the "register" field is 1 then register R1's value is -// compared against. -// The type of comparison (e.g. equal to, greater than etc) is determined -// by the "opcode" field. The comparison interprets both values being -// compared as unsigned values. -// -// Miscellaneous details: -// -// Pre-filled memory slot values -// When the APF program begins execution, three of the sixteen memory slots -// are pre-filled by the interpreter with values that may be useful for -// programs: -// Slot #13 is filled with the IPv4 header length. This value is calculated -// by loading the first byte of the IPv4 header and taking the -// bottom 4 bits and multiplying their value by 4. This value is -// set to zero if the first 4 bits after the link layer header are -// not 4, indicating not IPv4. -// Slot #14 is filled with size of the packet in bytes, including the -// link-layer header if any. -// Slot #15 is filled with the filter age in seconds. This is the number of -// seconds since the AP send the program to the chipset. This may -// be used by filters that should have a particular lifetime. For -// example, it can be used to rate-limit particular packets to one -// every N seconds. -// Special jump targets: -// When an APF program executes a jump to the byte immediately after the last -// byte of the progam (i.e., one byte past the end of the program), this -// signals the program has completed and determined the packet should be -// passed to the AP. -// When an APF program executes a jump two bytes past the end of the program, -// this signals the program has completed and determined the packet should -// be dropped. -// Jump if byte sequence doesn't match: -// This is a special instruction to facilitate matching long sequences of -// bytes in the packet. Initially it is encoded like a conditional jump -// instruction with two exceptions: -// The first byte of the instruction is always followed by two immediate -// fields: The first immediate field is the jump target offset like other -// conditional jump instructions. The second immediate field specifies the -// number of bytes to compare. -// These two immediate fields are followed by a sequence of bytes. These -// bytes are compared with the bytes in the packet starting from the -// position specified by the value of the register specified by the -// "register" field of the instruction. - -// Number of memory slots, see ldm/stm instructions. -#define MEMORY_ITEMS 16 -// Upon program execution starting some memory slots are prefilled: -#define MEMORY_OFFSET_IPV4_HEADER_SIZE 13 // 4*([APF_FRAME_HEADER_SIZE]&15) -#define MEMORY_OFFSET_PACKET_SIZE 14 // Size of packet in bytes. -#define MEMORY_OFFSET_FILTER_AGE 15 // Age since filter installed in seconds. - -// Leave 0 opcode unused as it's a good indicator of accidental incorrect execution (e.g. data). -#define LDB_OPCODE 1 // Load 1 byte from immediate offset, e.g. "ldb R0, [5]" -#define LDH_OPCODE 2 // Load 2 bytes from immediate offset, e.g. "ldh R0, [5]" -#define LDW_OPCODE 3 // Load 4 bytes from immediate offset, e.g. "ldw R0, [5]" -#define LDBX_OPCODE 4 // Load 1 byte from immediate offset plus register, e.g. "ldbx R0, [5]R0" -#define LDHX_OPCODE 5 // Load 2 byte from immediate offset plus register, e.g. "ldhx R0, [5]R0" -#define LDWX_OPCODE 6 // Load 4 byte from immediate offset plus register, e.g. "ldwx R0, [5]R0" -#define ADD_OPCODE 7 // Add, e.g. "add R0,5" -#define MUL_OPCODE 8 // Multiply, e.g. "mul R0,5" -#define DIV_OPCODE 9 // Divide, e.g. "div R0,5" -#define AND_OPCODE 10 // And, e.g. "and R0,5" -#define OR_OPCODE 11 // Or, e.g. "or R0,5" -#define SH_OPCODE 12 // Left shift, e.g, "sh R0, 5" or "sh R0, -5" (shifts right) -#define LI_OPCODE 13 // Load immediate, e.g. "li R0,5" (immediate encoded as signed value) -#define JMP_OPCODE 14 // Unconditional jump, e.g. "jmp label" -#define JEQ_OPCODE 15 // Compare equal and branch, e.g. "jeq R0,5,label" -#define JNE_OPCODE 16 // Compare not equal and branch, e.g. "jne R0,5,label" -#define JGT_OPCODE 17 // Compare greater than and branch, e.g. "jgt R0,5,label" -#define JLT_OPCODE 18 // Compare less than and branch, e.g. "jlt R0,5,label" -#define JSET_OPCODE 19 // Compare any bits set and branch, e.g. "jset R0,5,label" -#define JNEBS_OPCODE 20 // Compare not equal byte sequence, e.g. "jnebs R0,5,label,0x1122334455" -#define EXT_OPCODE 21 // Immediate value is one of *_EXT_OPCODE -// Extended opcodes. These all have an opcode of EXT_OPCODE -// and specify the actual opcode in the immediate field. -#define LDM_EXT_OPCODE 0 // Load from memory, e.g. "ldm R0,5" - // Values 0-15 represent loading the different memory slots. -#define STM_EXT_OPCODE 16 // Store to memory, e.g. "stm R0,5" - // Values 16-31 represent storing to the different memory slots. -#define NOT_EXT_OPCODE 32 // Not, e.g. "not R0" -#define NEG_EXT_OPCODE 33 // Negate, e.g. "neg R0" -#define SWAP_EXT_OPCODE 34 // Swap, e.g. "swap R0,R1" -#define MOV_EXT_OPCODE 35 // Move, e.g. "move R0,R1" - -#define EXTRACT_OPCODE(i) (((i) >> 3) & 31) -#define EXTRACT_REGISTER(i) ((i) & 1) -#define EXTRACT_IMM_LENGTH(i) (((i) >> 1) & 3) +#include "apf.h" // Return code indicating "packet" should accepted. #define PASS_PACKET 1 |