1 /* 2 * Copyright (C) 2023 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package android.net.apf; 18 19 import static android.net.apf.ApfGenerator.Register.R0; 20 import static android.net.apf.ApfGenerator.Register.R1; 21 22 import static com.android.net.module.util.NetworkStackConstants.ETHER_HEADER_LEN; 23 import static com.android.net.module.util.NetworkStackConstants.UDP_HEADER_LEN; 24 25 import androidx.annotation.NonNull; 26 27 /** 28 * Utility class that generates generating APF filters for DNS packets. 29 */ 30 public class DnsUtils { 31 32 /** Length of the DNS header. */ 33 private static final int DNS_HEADER_LEN = 12; 34 /** Offset of the qdcount field within the DNS header. */ 35 private static final int DNS_QDCOUNT_OFFSET = 4; 36 37 // Static labels 38 private static final String LABEL_START_MATCH = "start_match"; 39 private static final String LABEL_PARSE_DNS_LABEL = "parse_dns_label"; 40 private static final String LABEL_FIND_NEXT_DNS_QUESTION = "find_next_dns_question"; 41 42 // Length of the pointers used by compressed names. 43 private static final int LABEL_SIZE = Byte.BYTES; 44 private static final int POINTER_SIZE = Short.BYTES; 45 private static final int QUESTION_HEADER_SIZE = Short.BYTES + Short.BYTES; 46 private static final int LABEL_AND_QUESTION_HEADER_SIZE = LABEL_SIZE + QUESTION_HEADER_SIZE; 47 private static final int POINTER_AND_QUESTION_HEADER_SIZE = POINTER_SIZE + QUESTION_HEADER_SIZE; 48 49 /** Memory slot that stores the offset within the packet of the DNS header. */ 50 private static final int SLOT_DNS_HEADER_OFFSET = 1; 51 /** Memory slot that stores the current parsing offset. */ 52 private static final int SLOT_CURRENT_PARSE_OFFSET = 2; 53 /** 54 * Memory slot that stores the offset after the current question, if the code is currently 55 * parsing a pointer, or 0 if it is not. 56 */ 57 private static final int SLOT_AFTER_POINTER_OFFSET = 3; 58 /** 59 * Contains qdcount remaining, as a negative number. For example, will be -1 when starting to 60 * parse a DNS packet with one question in it. It's stored as a negative number because adding 1 61 * is much easier than subtracting 1 (which can't be done just by adding -1, because that just 62 * adds 254). 63 */ 64 private static final int SLOT_NEGATIVE_QDCOUNT_REMAINING = 6; 65 /** Memory slot used by the jump table. */ 66 private static final int SLOT_RETURN_VALUE_INDEX = 10; 67 68 /** 69 * APF function: parse_dns_label 70 * 71 * Parses a label potentially containing a pointer, and calculates the label length and the 72 * offset of the label data. 73 * 74 * Inputs: 75 * - m[SLOT_DNS_HEADER_OFFSET]: offset of DNS header 76 * - m[SLOT_CURRENT_PARSE_OFFSET]: current parsing offset 77 * - m[SLOT_AFTER_POINTER_OFFSET]: offset after the question (e.g., offset of the next question, 78 * or offset of the answer section) if a pointer is being chased, 0 otherwise 79 * - m[SLOT_RETURN_VALUE_INDEX]: index into return jump table 80 * 81 * Outputs: 82 * - R1: label length 83 * - m[SLOT_CURRENT_PARSE_OFFSET]: offset of label text 84 */ genParseDnsLabel(ApfGenerator gen, JumpTable jumpTable)85 private static void genParseDnsLabel(ApfGenerator gen, JumpTable jumpTable) throws Exception { 86 final String labelParseDnsLabelReal = "parse_dns_label_real"; 87 final String labelPointerOffsetStored = "pointer_offset_stored"; 88 89 /** 90 * :parse_dns_label 91 * // Load parsing offset. 92 * LDM R1, 2 // R1 = parsing offset. (All indexed loads use R1.) 93 */ 94 gen.defineLabel(LABEL_PARSE_DNS_LABEL); 95 gen.addLoadFromMemory(R1, SLOT_CURRENT_PARSE_OFFSET); 96 97 98 /** 99 * // Check that we’re in the DNS packet, i.e., that R1 >= m[SLOT_DNS_HEADER_OFFSET]. 100 * LDM R0, 1 // R0 = DNS header offset 101 * JGT R0, R1, DROP // Bad pointer. Drop. 102 */ 103 gen.addLoadFromMemory(R0, SLOT_DNS_HEADER_OFFSET); 104 gen.addJumpIfR0GreaterThanR1(ApfGenerator.DROP_LABEL); 105 106 /** 107 * // Now parse the label. 108 * LDBX R0, [R1+0] // R0 = label length, R1 = parsing offset 109 * AND R0, 0xc0 // Is this a pointer? 110 * 111 * JEQ R0, 0, :parse_dns_label_real 112 */ 113 gen.addLoad8Indexed(R0, 0); 114 gen.addAnd(0xc0); 115 gen.addJumpIfR0Equals(0, labelParseDnsLabelReal); 116 117 118 /** 119 * // If we’re not already chasing a pointer, store offset after pointer into 120 * // m[SLOT_AFTER_POINTER_OFFSET]. 121 * LDM R0, 3 // R0 = previous offset after pointer 122 * JNE 0, :pointer_offset_stored 123 * MOV R0, R1 // R0 = R1 124 * ADD R0, 6 // R0 = offset after pointer and record 125 * STM R0, 3 // Store offset after pointer 126 */ 127 gen.addLoadFromMemory(R0, SLOT_AFTER_POINTER_OFFSET); 128 gen.addJumpIfR0NotEquals(0, labelPointerOffsetStored); 129 gen.addMove(R0); 130 gen.addAdd(POINTER_AND_QUESTION_HEADER_SIZE); 131 gen.addStoreToMemory(R0, SLOT_AFTER_POINTER_OFFSET); 132 133 /** 134 * :pointer_offset_stored 135 * LDHX R0, [R1+0] // R0 = 2-byte pointer value 136 * AND R0, 0x3ff // R0 = pointer destination offset (from DNS header) 137 * LDM R1, 1 // R1 = offset in packet of DNS header 138 * ADD R0, R1 // R0 = pointer destination offset 139 * LDM R1, 2 // R1 = current parsing offset 140 * JEQ R0, R1, DROP // Drop if pointer points here... 141 * JGT R0, R1, DROP // ... or after here (must point backwards) 142 * STM R0, 2 // Set next parsing offset to pointer destination 143 */ 144 gen.defineLabel(labelPointerOffsetStored); 145 gen.addLoad16Indexed(R0, 0); 146 gen.addAnd(0x3ff); 147 gen.addLoadFromMemory(R1, SLOT_DNS_HEADER_OFFSET); 148 gen.addAddR1(); 149 gen.addLoadFromMemory(R1, SLOT_CURRENT_PARSE_OFFSET); 150 gen.addJumpIfR0EqualsR1(ApfGenerator.DROP_LABEL); 151 gen.addJumpIfR0GreaterThanR1(ApfGenerator.DROP_LABEL); 152 gen.addStoreToMemory(R0, SLOT_CURRENT_PARSE_OFFSET); 153 154 /** // Pointer chased. Parse starting from the pointer destination (which may also be a 155 * pointer). 156 * JMP :parse_dns_label 157 */ 158 gen.addJump(LABEL_PARSE_DNS_LABEL); 159 160 /** 161 * :parse_real_label 162 * // This is where the real (non-pointer) label starts. 163 * // Load label length into R1, and return to caller. 164 * // m[SLOT_CURRENT_PARSE_OFFSET] already contains label offset. 165 * LDHX R1 [R1+0] // R1 = label length 166 */ 167 gen.defineLabel(labelParseDnsLabelReal); 168 gen.addLoad8Indexed(R1, 0); 169 170 /** // Return 171 * LDM R0, 10 172 * JMP :jump_table 173 */ 174 gen.addLoadFromMemory(R0, SLOT_RETURN_VALUE_INDEX); 175 gen.addJump(jumpTable.getStartLabel()); 176 } 177 178 /** 179 * APF function: find_next_dns_question 180 * 181 * Finds the next question in the question section, or drops the packet if there is none. 182 * 183 * Inputs: 184 * - m[SLOT_CURRENT_PARSE_OFFSET]: current parsing offset 185 * - m[SLOT_AFTER_POINTER_OFFSET]: offset after first pointer in name, or 0 if not chasing a 186 * pointer 187 * - m[SLOT_NEGATIVE_QDCOUNT_REMAINING]: qdcount remaining, as a negative number. This is 188 * because adding 1 is much easier than subtracting 1 (which can't be done just by 189 * adding -1, because that just adds 254) 190 * - m[SLOT_RETURN_VALUE_INDEX]: index into return jump table 191 * 192 * Outputs: 193 * None 194 */ genFindNextDnsQuestion(ApfGenerator gen, JumpTable jumpTable)195 private static void genFindNextDnsQuestion(ApfGenerator gen, JumpTable jumpTable) 196 throws Exception { 197 final String labelFindNextDnsQuestionFollow = "find_next_dns_question_follow"; 198 final String labelFindNextDnsQuestionLabel = "find_next_dns_question_label"; 199 final String labelFindNextDnsQuestionLoop = "find_next_dns_question_loop"; 200 final String labelFindNextDnsQuestionNoPointer = "find_next_dns_question_no_pointer"; 201 final String labelFindNextDnsQuestionReturn = "find_next_dns_question_return"; 202 203 // Function entry point. 204 gen.defineLabel(LABEL_FIND_NEXT_DNS_QUESTION); 205 206 // Are we chasing a pointer? 207 gen.addLoadFromMemory(R0, SLOT_AFTER_POINTER_OFFSET); 208 gen.addJumpIfR0Equals(0, labelFindNextDnsQuestionFollow); 209 210 // If so, offset after the pointer and question is stored in m[SLOT_AFTER_POINTER_OFFSET]. 211 // Move parsing offset there, clear m[SLOT_AFTER_POINTER_OFFSET], and return. 212 gen.addStoreToMemory(R0, SLOT_CURRENT_PARSE_OFFSET); 213 gen.addLoadImmediate(R0, 0); 214 gen.addStoreToMemory(R0, SLOT_AFTER_POINTER_OFFSET); 215 gen.addJump(labelFindNextDnsQuestionReturn); 216 217 // We weren't chasing a pointer. Loop, following the label chain, until we reach a 218 // zero-length label or a pointer. At the beginning of the loop, the current parsing offset 219 // is m[SLOT_CURRENT_PARSE_OFFSET]. Move it to R1 and keep it in R1 throughout the loop. 220 gen.defineLabel(labelFindNextDnsQuestionFollow); 221 gen.addLoadFromMemory(R1, SLOT_CURRENT_PARSE_OFFSET); 222 223 // Load label length. 224 gen.defineLabel(labelFindNextDnsQuestionLoop); 225 gen.addLoad8Indexed(R0, 0); 226 // Is it a pointer? 227 gen.addAnd(0xc0); 228 gen.addJumpIfR0Equals(0, labelFindNextDnsQuestionNoPointer); 229 // It's a pointer. Skip the pointer and question, and return. 230 gen.addLoadImmediate(R0, POINTER_AND_QUESTION_HEADER_SIZE); 231 gen.addAddR1(); 232 gen.addStoreToMemory(R0, SLOT_CURRENT_PARSE_OFFSET); 233 gen.addJump(labelFindNextDnsQuestionReturn); 234 235 // R1 still contains parsing offset. 236 gen.defineLabel(labelFindNextDnsQuestionNoPointer); 237 gen.addLoad8Indexed(R0, 0); 238 239 // Zero-length label? We're done. 240 // Skip the label (1 byte) and query (2 bytes qtype, 2 bytes qclass) and return. 241 gen.addJumpIfR0NotEquals(0, labelFindNextDnsQuestionLabel); 242 gen.addLoadImmediate(R0, LABEL_AND_QUESTION_HEADER_SIZE); 243 gen.addAddR1(); 244 gen.addStoreToMemory(R0, SLOT_CURRENT_PARSE_OFFSET); 245 gen.addJump(labelFindNextDnsQuestionReturn); 246 247 // Non-zero length label. Consume it and continue. 248 gen.defineLabel(labelFindNextDnsQuestionLabel); 249 gen.addAdd(1); 250 gen.addAddR1(); 251 gen.addMove(R1); 252 gen.addJump(labelFindNextDnsQuestionLoop); 253 254 gen.defineLabel(labelFindNextDnsQuestionReturn); 255 256 // Is this the last question? If so, drop. 257 gen.addLoadFromMemory(R0, SLOT_NEGATIVE_QDCOUNT_REMAINING); 258 gen.addAdd(1); 259 gen.addStoreToMemory(R0, SLOT_NEGATIVE_QDCOUNT_REMAINING); 260 gen.addJumpIfR0Equals(0, ApfGenerator.DROP_LABEL); 261 262 // If not, return. 263 gen.addJump(jumpTable.getStartLabel()); 264 } 265 266 /** @return jump label that points to the start of a DNS label's parsing code. */ getStartMatchLabel(int labelIndex)267 private static String getStartMatchLabel(int labelIndex) { 268 return "dns_parse_" + labelIndex; 269 } 270 271 /** @return jump label used while parsing the specified DNS label. */ getPostMatchJumpTargetForLabel(int labelIndex)272 private static String getPostMatchJumpTargetForLabel(int labelIndex) { 273 return "dns_parsed_" + labelIndex; 274 } 275 276 /** @return jump label used when the match for the specified DNS label fails. */ getNoMatchLabel(int labelIndex)277 private static String getNoMatchLabel(int labelIndex) { 278 return "dns_nomatch_" + labelIndex; 279 } 280 addMatchLabel(@onNull ApfGenerator gen, @NonNull JumpTable jumpTable, int labelIndex, @NonNull String label, @NonNull String nextLabel)281 private static void addMatchLabel(@NonNull ApfGenerator gen, @NonNull JumpTable jumpTable, 282 int labelIndex, @NonNull String label, @NonNull String nextLabel) throws Exception { 283 final String parsedLabel = getPostMatchJumpTargetForLabel(labelIndex); 284 final String noMatchLabel = getNoMatchLabel(labelIndex); 285 gen.defineLabel(getStartMatchLabel(labelIndex)); 286 287 // Store return address. 288 gen.addLoadImmediate(R0, jumpTable.getIndex(parsedLabel)); 289 gen.addStoreToMemory(R0, SLOT_RETURN_VALUE_INDEX); 290 291 // Call the parse_label function. 292 gen.addJump(LABEL_PARSE_DNS_LABEL); 293 294 gen.defineLabel(parsedLabel); 295 296 // If label length is 0, this is the end of the name and the match failed. 297 gen.addSwap(); // Move label length from R1 to R0 298 gen.addJumpIfR0Equals(0, noMatchLabel); 299 300 // Label parsed, check it matches what we're looking for. 301 gen.addJumpIfR0NotEquals(label.length(), noMatchLabel); 302 gen.addLoadFromMemory(R0, SLOT_CURRENT_PARSE_OFFSET); 303 gen.addAdd(1); 304 gen.addJumpIfBytesNotEqual(R0, label.getBytes(), noMatchLabel); 305 306 // Prep offset of next label. 307 gen.addAdd(label.length()); 308 gen.addStoreToMemory(R0, SLOT_CURRENT_PARSE_OFFSET); 309 310 // Match, go to next label. 311 gen.addJump(nextLabel); 312 313 // Match failed. Go to next name, and restart from the first match. 314 gen.defineLabel(noMatchLabel); 315 gen.addLoadImmediate(R1, jumpTable.getIndex(LABEL_START_MATCH)); 316 gen.addStoreToMemory(R1, SLOT_RETURN_VALUE_INDEX); 317 gen.addJump(LABEL_FIND_NEXT_DNS_QUESTION); 318 } 319 320 /** 321 * Generates a filter that accepts DNS packet that ask for the specified name. 322 * 323 * The filter supports compressed DNS names and scanning through multiple questions in the same 324 * packet, e.g., as used by MDNS. However, it currently only supports one DNS name. 325 * 326 * Limitations: 327 * <ul> 328 * <li>Filter size is just under 300 bytes for a typical question. 329 * <li>Because the bytecode extensively uses backwards jumps, it can hit the APF interpreter 330 * instruction limit. This limit causes the APF interpreter to accept the packet once it has 331 * executed a number of instructions equal to the program length in bytes. 332 * A program that consists *only* of this filter will be able to execute just under 300 333 * instructions, and will be able to correctly drop packets with two questions but not three 334 * questions. In a real APF setup, there will be other code (e.g., RA filtering) which counts 335 * against the limit, so the filter should be able to parse packets with more questions. 336 * <li>Matches are case-sensitive. This is due to the use of JNEBS to match DNS labels and is 337 * likely impossible to overcome without interpreter changes. 338 * </ul> 339 * 340 * TODO: 341 * <ul> 342 * <li>Add unit tests for the parse_dns_label and find_next_dns_question functions. 343 * <li>Support accepting more than one name. 344 * <li>For devices where power saving is a priority (e.g., flat panel TVs), add support for 345 * dropping packets with more than X queries, to ensure the filter will drop the packet rather 346 * than hit the instruction limit. 347 * </ul> 348 */ generateFilter(ApfGenerator gen, String[] labels)349 public static void generateFilter(ApfGenerator gen, String[] labels) throws Exception { 350 final int etherPlusUdpLen = ETHER_HEADER_LEN + UDP_HEADER_LEN; 351 352 final String labelJumpTable = "jump_table"; 353 354 // Initialize parsing 355 /** 356 * - R1: length of IP header. 357 * - m[SLOT_DNS_HEADER_OFFSET]: offset of DNS header 358 * - m[SLOT_CURRENT_PARSE_OFFSET]: current parsing offset (start of question section) 359 * - m[SLOT_AFTER_POINTER_OFFSET]: offset after first pointer in name, must be 0 when 360 * starting a new name 361 * - m[SLOT_NEGATIVE_QDCOUNT_REMAINING]: negative qdcount 362 */ 363 // Move IP header length to R0 and use it to find the DNS header offset. 364 // TODO: this uses R1 for consistency with ApfFilter#generateMdnsFilterLocked. Evaluate 365 // using R0 instead. 366 gen.addMove(R0); 367 gen.addAdd(etherPlusUdpLen); 368 gen.addStoreToMemory(R0, SLOT_DNS_HEADER_OFFSET); 369 370 gen.addAdd(DNS_QDCOUNT_OFFSET); 371 gen.addMove(R1); 372 gen.addLoad16Indexed(R1, 0); 373 gen.addNeg(R1); 374 gen.addStoreToMemory(R1, SLOT_NEGATIVE_QDCOUNT_REMAINING); 375 376 gen.addAdd(DNS_HEADER_LEN - DNS_QDCOUNT_OFFSET); 377 gen.addStoreToMemory(R0, SLOT_CURRENT_PARSE_OFFSET); 378 379 gen.addLoadImmediate(R0, 0); 380 gen.addStoreToMemory(R0, SLOT_AFTER_POINTER_OFFSET); 381 382 gen.addJump(LABEL_START_MATCH); 383 384 // Create JumpTable but 385 final JumpTable table = new JumpTable(labelJumpTable, SLOT_RETURN_VALUE_INDEX); 386 387 // Generate bytecode for parse_label function. 388 genParseDnsLabel(gen, table); 389 genFindNextDnsQuestion(gen, table); 390 391 // Populate jump table. Should be before the code that calls to it (i.e., the addMatchLabel 392 // calls below) because otherwise all the jumps are backwards, and backwards jumps are more 393 // expensive (5 bytes of bytecode) 394 for (int i = 0; i < labels.length; i++) { 395 table.addLabel(getPostMatchJumpTargetForLabel(i)); 396 } 397 table.addLabel(LABEL_START_MATCH); 398 table.generate(gen); 399 400 // Add match statements for name. 401 gen.defineLabel(LABEL_START_MATCH); 402 for (int i = 0; i < labels.length; i++) { 403 final String nextLabel = (i == labels.length - 1) 404 ? ApfGenerator.PASS_LABEL 405 : getStartMatchLabel(i + 1); 406 addMatchLabel(gen, table, i, labels[i], nextLabel); 407 } 408 gen.addJump(ApfGenerator.DROP_LABEL); 409 } 410 DnsUtils()411 private DnsUtils() { 412 } 413 } 414