1 /* 2 * Copyright (C) 2016 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.util.NetworkConstants.*; 20 import static android.system.OsConstants.*; 21 import static com.android.internal.util.BitUtils.bytesToBEInt; 22 import static com.android.internal.util.BitUtils.getUint16; 23 import static com.android.internal.util.BitUtils.getUint32; 24 import static com.android.internal.util.BitUtils.getUint8; 25 import static com.android.internal.util.BitUtils.uint32; 26 27 import android.annotation.Nullable; 28 import android.content.BroadcastReceiver; 29 import android.content.Context; 30 import android.content.Intent; 31 import android.content.IntentFilter; 32 import android.net.LinkAddress; 33 import android.net.LinkProperties; 34 import android.net.NetworkUtils; 35 import android.net.apf.ApfGenerator.IllegalInstructionException; 36 import android.net.apf.ApfGenerator.Register; 37 import android.net.ip.IpClient; 38 import android.net.metrics.ApfProgramEvent; 39 import android.net.metrics.ApfStats; 40 import android.net.metrics.IpConnectivityLog; 41 import android.net.metrics.RaEvent; 42 import android.net.util.InterfaceParams; 43 import android.os.PowerManager; 44 import android.os.SystemClock; 45 import android.system.ErrnoException; 46 import android.system.Os; 47 import android.system.PacketSocketAddress; 48 import android.text.format.DateUtils; 49 import android.util.Log; 50 import android.util.Pair; 51 import com.android.internal.annotations.GuardedBy; 52 import com.android.internal.annotations.VisibleForTesting; 53 import com.android.internal.util.HexDump; 54 import com.android.internal.util.IndentingPrintWriter; 55 import java.io.FileDescriptor; 56 import java.io.IOException; 57 import java.net.Inet4Address; 58 import java.net.Inet6Address; 59 import java.net.InetAddress; 60 import java.net.SocketException; 61 import java.net.UnknownHostException; 62 import java.nio.BufferUnderflowException; 63 import java.nio.ByteBuffer; 64 import java.util.ArrayList; 65 import java.util.Arrays; 66 import libcore.io.IoBridge; 67 68 /** 69 * For networks that support packet filtering via APF programs, {@code ApfFilter} 70 * listens for IPv6 ICMPv6 router advertisements (RAs) and generates APF programs to 71 * filter out redundant duplicate ones. 72 * 73 * Threading model: 74 * A collection of RAs we've received is kept in mRas. Generating APF programs uses mRas to 75 * know what RAs to filter for, thus generating APF programs is dependent on mRas. 76 * mRas can be accessed by multiple threads: 77 * - ReceiveThread, which listens for RAs and adds them to mRas, and generates APF programs. 78 * - callers of: 79 * - setMulticastFilter(), which can cause an APF program to be generated. 80 * - dump(), which dumps mRas among other things. 81 * - shutdown(), which clears mRas. 82 * So access to mRas is synchronized. 83 * 84 * @hide 85 */ 86 public class ApfFilter { 87 88 // Helper class for specifying functional filter parameters. 89 public static class ApfConfiguration { 90 public ApfCapabilities apfCapabilities; 91 public boolean multicastFilter; 92 public boolean ieee802_3Filter; 93 public int[] ethTypeBlackList; 94 } 95 96 // Enums describing the outcome of receiving an RA packet. 97 private static enum ProcessRaResult { 98 MATCH, // Received RA matched a known RA 99 DROPPED, // Received RA ignored due to MAX_RAS 100 PARSE_ERROR, // Received RA could not be parsed 101 ZERO_LIFETIME, // Received RA had 0 lifetime 102 UPDATE_NEW_RA, // APF program updated for new RA 103 UPDATE_EXPIRY // APF program updated for expiry 104 } 105 106 /** 107 * APF packet counters. 108 * 109 * Packet counters are 32bit big-endian values, and allocated near the end of the APF data 110 * buffer, using negative byte offsets, where -4 is equivalent to maximumApfProgramSize - 4, 111 * the last writable 32bit word. 112 */ 113 @VisibleForTesting 114 private static enum Counter { 115 RESERVED_OOB, // Points to offset 0 from the end of the buffer (out-of-bounds) 116 TOTAL_PACKETS, 117 PASSED_ARP, 118 PASSED_DHCP, 119 PASSED_IPV4, 120 PASSED_IPV6_NON_ICMP, 121 PASSED_IPV4_UNICAST, 122 PASSED_IPV6_ICMP, 123 PASSED_IPV6_UNICAST_NON_ICMP, 124 PASSED_ARP_NON_IPV4, 125 PASSED_ARP_UNKNOWN, 126 PASSED_ARP_UNICAST_REPLY, 127 PASSED_NON_IP_UNICAST, 128 DROPPED_ETH_BROADCAST, 129 DROPPED_RA, 130 DROPPED_GARP_REPLY, 131 DROPPED_ARP_OTHER_HOST, 132 DROPPED_IPV4_L2_BROADCAST, 133 DROPPED_IPV4_BROADCAST_ADDR, 134 DROPPED_IPV4_BROADCAST_NET, 135 DROPPED_IPV4_MULTICAST, 136 DROPPED_IPV6_ROUTER_SOLICITATION, 137 DROPPED_IPV6_MULTICAST_NA, 138 DROPPED_IPV6_MULTICAST, 139 DROPPED_IPV6_MULTICAST_PING, 140 DROPPED_IPV6_NON_ICMP_MULTICAST, 141 DROPPED_802_3_FRAME, 142 DROPPED_ETHERTYPE_BLACKLISTED; 143 144 // Returns the negative byte offset from the end of the APF data segment for 145 // a given counter. offset()146 public int offset() { 147 return - this.ordinal() * 4; // Currently, all counters are 32bit long. 148 } 149 150 // Returns the total size of the data segment in bytes. totalSize()151 public static int totalSize() { 152 return (Counter.class.getEnumConstants().length - 1) * 4; 153 } 154 } 155 156 /** 157 * When APFv4 is supported, loads R1 with the offset of the specified counter. 158 */ maybeSetCounter(ApfGenerator gen, Counter c)159 private void maybeSetCounter(ApfGenerator gen, Counter c) { 160 if (mApfCapabilities.hasDataAccess()) { 161 gen.addLoadImmediate(Register.R1, c.offset()); 162 } 163 } 164 165 // When APFv4 is supported, these point to the trampolines generated by emitEpilogue(). 166 // Otherwise, they're just aliases for PASS_LABEL and DROP_LABEL. 167 private final String mCountAndPassLabel; 168 private final String mCountAndDropLabel; 169 170 // Thread to listen for RAs. 171 @VisibleForTesting 172 class ReceiveThread extends Thread { 173 private final byte[] mPacket = new byte[1514]; 174 private final FileDescriptor mSocket; 175 private final long mStart = SystemClock.elapsedRealtime(); 176 private final ApfStats mStats = new ApfStats(); 177 178 private volatile boolean mStopped; 179 ReceiveThread(FileDescriptor socket)180 public ReceiveThread(FileDescriptor socket) { 181 mSocket = socket; 182 } 183 halt()184 public void halt() { 185 mStopped = true; 186 try { 187 // Interrupts the read() call the thread is blocked in. 188 IoBridge.closeAndSignalBlockedThreads(mSocket); 189 } catch (IOException ignored) {} 190 } 191 192 @Override run()193 public void run() { 194 log("begin monitoring"); 195 while (!mStopped) { 196 try { 197 int length = Os.read(mSocket, mPacket, 0, mPacket.length); 198 updateStats(processRa(mPacket, length)); 199 } catch (IOException|ErrnoException e) { 200 if (!mStopped) { 201 Log.e(TAG, "Read error", e); 202 } 203 } 204 } 205 logStats(); 206 } 207 updateStats(ProcessRaResult result)208 private void updateStats(ProcessRaResult result) { 209 mStats.receivedRas++; 210 switch(result) { 211 case MATCH: 212 mStats.matchingRas++; 213 return; 214 case DROPPED: 215 mStats.droppedRas++; 216 return; 217 case PARSE_ERROR: 218 mStats.parseErrors++; 219 return; 220 case ZERO_LIFETIME: 221 mStats.zeroLifetimeRas++; 222 return; 223 case UPDATE_EXPIRY: 224 mStats.matchingRas++; 225 mStats.programUpdates++; 226 return; 227 case UPDATE_NEW_RA: 228 mStats.programUpdates++; 229 return; 230 } 231 } 232 logStats()233 private void logStats() { 234 final long nowMs = SystemClock.elapsedRealtime(); 235 synchronized (this) { 236 mStats.durationMs = nowMs - mStart; 237 mStats.maxProgramSize = mApfCapabilities.maximumApfProgramSize; 238 mStats.programUpdatesAll = mNumProgramUpdates; 239 mStats.programUpdatesAllowingMulticast = mNumProgramUpdatesAllowingMulticast; 240 mMetricsLog.log(mStats); 241 logApfProgramEventLocked(nowMs / DateUtils.SECOND_IN_MILLIS); 242 } 243 } 244 } 245 246 private static final String TAG = "ApfFilter"; 247 private static final boolean DBG = true; 248 private static final boolean VDBG = false; 249 250 private static final int ETH_HEADER_LEN = 14; 251 private static final int ETH_DEST_ADDR_OFFSET = 0; 252 private static final int ETH_ETHERTYPE_OFFSET = 12; 253 private static final int ETH_TYPE_MIN = 0x0600; 254 private static final int ETH_TYPE_MAX = 0xFFFF; 255 private static final byte[] ETH_BROADCAST_MAC_ADDRESS = 256 {(byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff }; 257 // TODO: Make these offsets relative to end of link-layer header; don't include ETH_HEADER_LEN. 258 private static final int IPV4_FRAGMENT_OFFSET_OFFSET = ETH_HEADER_LEN + 6; 259 // Endianness is not an issue for this constant because the APF interpreter always operates in 260 // network byte order. 261 private static final int IPV4_FRAGMENT_OFFSET_MASK = 0x1fff; 262 private static final int IPV4_PROTOCOL_OFFSET = ETH_HEADER_LEN + 9; 263 private static final int IPV4_DEST_ADDR_OFFSET = ETH_HEADER_LEN + 16; 264 private static final int IPV4_ANY_HOST_ADDRESS = 0; 265 private static final int IPV4_BROADCAST_ADDRESS = -1; // 255.255.255.255 266 267 // Traffic class and Flow label are not byte aligned. Luckily we 268 // don't care about either value so we'll consider bytes 1-3 of the 269 // IPv6 header as don't care. 270 private static final int IPV6_FLOW_LABEL_OFFSET = ETH_HEADER_LEN + 1; 271 private static final int IPV6_FLOW_LABEL_LEN = 3; 272 private static final int IPV6_NEXT_HEADER_OFFSET = ETH_HEADER_LEN + 6; 273 private static final int IPV6_SRC_ADDR_OFFSET = ETH_HEADER_LEN + 8; 274 private static final int IPV6_DEST_ADDR_OFFSET = ETH_HEADER_LEN + 24; 275 private static final int IPV6_HEADER_LEN = 40; 276 // The IPv6 all nodes address ff02::1 277 private static final byte[] IPV6_ALL_NODES_ADDRESS = 278 { (byte) 0xff, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }; 279 280 private static final int ICMP6_TYPE_OFFSET = ETH_HEADER_LEN + IPV6_HEADER_LEN; 281 282 // NOTE: this must be added to the IPv4 header length in IPV4_HEADER_SIZE_MEMORY_SLOT 283 private static final int UDP_DESTINATION_PORT_OFFSET = ETH_HEADER_LEN + 2; 284 private static final int UDP_HEADER_LEN = 8; 285 286 private static final int DHCP_CLIENT_PORT = 68; 287 // NOTE: this must be added to the IPv4 header length in IPV4_HEADER_SIZE_MEMORY_SLOT 288 private static final int DHCP_CLIENT_MAC_OFFSET = ETH_HEADER_LEN + UDP_HEADER_LEN + 28; 289 290 private static final int ARP_HEADER_OFFSET = ETH_HEADER_LEN; 291 private static final int ARP_OPCODE_OFFSET = ARP_HEADER_OFFSET + 6; 292 private static final short ARP_OPCODE_REQUEST = 1; 293 private static final short ARP_OPCODE_REPLY = 2; 294 private static final byte[] ARP_IPV4_HEADER = { 295 0, 1, // Hardware type: Ethernet (1) 296 8, 0, // Protocol type: IP (0x0800) 297 6, // Hardware size: 6 298 4, // Protocol size: 4 299 }; 300 private static final int ARP_TARGET_IP_ADDRESS_OFFSET = ETH_HEADER_LEN + 24; 301 // Do not log ApfProgramEvents whose actual lifetimes was less than this. 302 private static final int APF_PROGRAM_EVENT_LIFETIME_THRESHOLD = 2; 303 // Limit on the Black List size to cap on program usage for this 304 // TODO: Select a proper max length 305 private static final int APF_MAX_ETH_TYPE_BLACK_LIST_LEN = 20; 306 307 private final ApfCapabilities mApfCapabilities; 308 private final IpClient.Callback mIpClientCallback; 309 private final InterfaceParams mInterfaceParams; 310 private final IpConnectivityLog mMetricsLog; 311 312 @VisibleForTesting 313 byte[] mHardwareAddress; 314 @VisibleForTesting 315 ReceiveThread mReceiveThread; 316 @GuardedBy("this") 317 private long mUniqueCounter; 318 @GuardedBy("this") 319 private boolean mMulticastFilter; 320 @GuardedBy("this") 321 private boolean mInDozeMode; 322 private final boolean mDrop802_3Frames; 323 private final int[] mEthTypeBlackList; 324 325 // Detects doze mode state transitions. 326 private final BroadcastReceiver mDeviceIdleReceiver = new BroadcastReceiver() { 327 @Override 328 public void onReceive(Context context, Intent intent) { 329 String action = intent.getAction(); 330 if (action.equals(PowerManager.ACTION_DEVICE_IDLE_MODE_CHANGED)) { 331 PowerManager powerManager = 332 (PowerManager) context.getSystemService(Context.POWER_SERVICE); 333 final boolean deviceIdle = powerManager.isDeviceIdleMode(); 334 setDozeMode(deviceIdle); 335 } 336 } 337 }; 338 private final Context mContext; 339 340 // Our IPv4 address, if we have just one, otherwise null. 341 @GuardedBy("this") 342 private byte[] mIPv4Address; 343 // The subnet prefix length of our IPv4 network. Only valid if mIPv4Address is not null. 344 @GuardedBy("this") 345 private int mIPv4PrefixLength; 346 347 @VisibleForTesting ApfFilter(Context context, ApfConfiguration config, InterfaceParams ifParams, IpClient.Callback ipClientCallback, IpConnectivityLog log)348 ApfFilter(Context context, ApfConfiguration config, InterfaceParams ifParams, 349 IpClient.Callback ipClientCallback, IpConnectivityLog log) { 350 mApfCapabilities = config.apfCapabilities; 351 mIpClientCallback = ipClientCallback; 352 mInterfaceParams = ifParams; 353 mMulticastFilter = config.multicastFilter; 354 mDrop802_3Frames = config.ieee802_3Filter; 355 mContext = context; 356 357 if (mApfCapabilities.hasDataAccess()) { 358 mCountAndPassLabel = "countAndPass"; 359 mCountAndDropLabel = "countAndDrop"; 360 } else { 361 // APFv4 unsupported: turn jumps to the counter trampolines to immediately PASS or DROP, 362 // preserving the original pre-APFv4 behavior. 363 mCountAndPassLabel = ApfGenerator.PASS_LABEL; 364 mCountAndDropLabel = ApfGenerator.DROP_LABEL; 365 } 366 367 // Now fill the black list from the passed array 368 mEthTypeBlackList = filterEthTypeBlackList(config.ethTypeBlackList); 369 370 mMetricsLog = log; 371 372 // TODO: ApfFilter should not generate programs until IpClient sends provisioning success. 373 maybeStartFilter(); 374 375 // Listen for doze-mode transition changes to enable/disable the IPv6 multicast filter. 376 mContext.registerReceiver(mDeviceIdleReceiver, 377 new IntentFilter(PowerManager.ACTION_DEVICE_IDLE_MODE_CHANGED)); 378 } 379 setDataSnapshot(byte[] data)380 public synchronized void setDataSnapshot(byte[] data) { 381 mDataSnapshot = data; 382 } 383 log(String s)384 private void log(String s) { 385 Log.d(TAG, "(" + mInterfaceParams.name + "): " + s); 386 } 387 388 @GuardedBy("this") getUniqueNumberLocked()389 private long getUniqueNumberLocked() { 390 return mUniqueCounter++; 391 } 392 393 @GuardedBy("this") filterEthTypeBlackList(int[] ethTypeBlackList)394 private static int[] filterEthTypeBlackList(int[] ethTypeBlackList) { 395 ArrayList<Integer> bl = new ArrayList<Integer>(); 396 397 for (int p : ethTypeBlackList) { 398 // Check if the protocol is a valid ether type 399 if ((p < ETH_TYPE_MIN) || (p > ETH_TYPE_MAX)) { 400 continue; 401 } 402 403 // Check if the protocol is not repeated in the passed array 404 if (bl.contains(p)) { 405 continue; 406 } 407 408 // Check if list reach its max size 409 if (bl.size() == APF_MAX_ETH_TYPE_BLACK_LIST_LEN) { 410 Log.w(TAG, "Passed EthType Black List size too large (" + bl.size() + 411 ") using top " + APF_MAX_ETH_TYPE_BLACK_LIST_LEN + " protocols"); 412 break; 413 } 414 415 // Now add the protocol to the list 416 bl.add(p); 417 } 418 419 return bl.stream().mapToInt(Integer::intValue).toArray(); 420 } 421 422 /** 423 * Attempt to start listening for RAs and, if RAs are received, generating and installing 424 * filters to ignore useless RAs. 425 */ 426 @VisibleForTesting maybeStartFilter()427 void maybeStartFilter() { 428 FileDescriptor socket; 429 try { 430 mHardwareAddress = mInterfaceParams.macAddr.toByteArray(); 431 synchronized(this) { 432 // Clear the APF memory to reset all counters upon connecting to the first AP 433 // in an SSID. This is limited to APFv4 devices because this large write triggers 434 // a crash on some older devices (b/78905546). 435 if (mApfCapabilities.hasDataAccess()) { 436 byte[] zeroes = new byte[mApfCapabilities.maximumApfProgramSize]; 437 mIpClientCallback.installPacketFilter(zeroes); 438 } 439 440 // Install basic filters 441 installNewProgramLocked(); 442 } 443 socket = Os.socket(AF_PACKET, SOCK_RAW, ETH_P_IPV6); 444 PacketSocketAddress addr = new PacketSocketAddress( 445 (short) ETH_P_IPV6, mInterfaceParams.index); 446 Os.bind(socket, addr); 447 NetworkUtils.attachRaFilter(socket, mApfCapabilities.apfPacketFormat); 448 } catch(SocketException|ErrnoException e) { 449 Log.e(TAG, "Error starting filter", e); 450 return; 451 } 452 mReceiveThread = new ReceiveThread(socket); 453 mReceiveThread.start(); 454 } 455 456 // Returns seconds since device boot. 457 @VisibleForTesting currentTimeSeconds()458 protected long currentTimeSeconds() { 459 return SystemClock.elapsedRealtime() / DateUtils.SECOND_IN_MILLIS; 460 } 461 462 public static class InvalidRaException extends Exception { InvalidRaException(String m)463 public InvalidRaException(String m) { 464 super(m); 465 } 466 } 467 468 // A class to hold information about an RA. 469 @VisibleForTesting 470 class Ra { 471 // From RFC4861: 472 private static final int ICMP6_RA_HEADER_LEN = 16; 473 private static final int ICMP6_RA_CHECKSUM_OFFSET = 474 ETH_HEADER_LEN + IPV6_HEADER_LEN + 2; 475 private static final int ICMP6_RA_CHECKSUM_LEN = 2; 476 private static final int ICMP6_RA_OPTION_OFFSET = 477 ETH_HEADER_LEN + IPV6_HEADER_LEN + ICMP6_RA_HEADER_LEN; 478 private static final int ICMP6_RA_ROUTER_LIFETIME_OFFSET = 479 ETH_HEADER_LEN + IPV6_HEADER_LEN + 6; 480 private static final int ICMP6_RA_ROUTER_LIFETIME_LEN = 2; 481 // Prefix information option. 482 private static final int ICMP6_PREFIX_OPTION_TYPE = 3; 483 private static final int ICMP6_PREFIX_OPTION_LEN = 32; 484 private static final int ICMP6_PREFIX_OPTION_VALID_LIFETIME_OFFSET = 4; 485 private static final int ICMP6_PREFIX_OPTION_VALID_LIFETIME_LEN = 4; 486 private static final int ICMP6_PREFIX_OPTION_PREFERRED_LIFETIME_OFFSET = 8; 487 private static final int ICMP6_PREFIX_OPTION_PREFERRED_LIFETIME_LEN = 4; 488 489 // From RFC6106: Recursive DNS Server option 490 private static final int ICMP6_RDNSS_OPTION_TYPE = 25; 491 // From RFC6106: DNS Search List option 492 private static final int ICMP6_DNSSL_OPTION_TYPE = 31; 493 494 // From RFC4191: Route Information option 495 private static final int ICMP6_ROUTE_INFO_OPTION_TYPE = 24; 496 // Above three options all have the same format: 497 private static final int ICMP6_4_BYTE_LIFETIME_OFFSET = 4; 498 private static final int ICMP6_4_BYTE_LIFETIME_LEN = 4; 499 500 // Note: mPacket's position() cannot be assumed to be reset. 501 private final ByteBuffer mPacket; 502 // List of binary ranges that include the whole packet except the lifetimes. 503 // Pairs consist of offset and length. 504 private final ArrayList<Pair<Integer, Integer>> mNonLifetimes = 505 new ArrayList<Pair<Integer, Integer>>(); 506 // Minimum lifetime in packet 507 long mMinLifetime; 508 // When the packet was last captured, in seconds since Unix Epoch 509 long mLastSeen; 510 511 // For debugging only. Offsets into the packet where PIOs are. 512 private final ArrayList<Integer> mPrefixOptionOffsets = new ArrayList<>(); 513 514 // For debugging only. Offsets into the packet where RDNSS options are. 515 private final ArrayList<Integer> mRdnssOptionOffsets = new ArrayList<>(); 516 517 // For debugging only. How many times this RA was seen. 518 int seenCount = 0; 519 520 // For debugging only. Returns the hex representation of the last matching packet. getLastMatchingPacket()521 String getLastMatchingPacket() { 522 return HexDump.toHexString(mPacket.array(), 0, mPacket.capacity(), 523 false /* lowercase */); 524 } 525 526 // For debugging only. Returns the string representation of the IPv6 address starting at 527 // position pos in the packet. IPv6AddresstoString(int pos)528 private String IPv6AddresstoString(int pos) { 529 try { 530 byte[] array = mPacket.array(); 531 // Can't just call copyOfRange() and see if it throws, because if it reads past the 532 // end it pads with zeros instead of throwing. 533 if (pos < 0 || pos + 16 > array.length || pos + 16 < pos) { 534 return "???"; 535 } 536 byte[] addressBytes = Arrays.copyOfRange(array, pos, pos + 16); 537 InetAddress address = (Inet6Address) InetAddress.getByAddress(addressBytes); 538 return address.getHostAddress(); 539 } catch (UnsupportedOperationException e) { 540 // array() failed. Cannot happen, mPacket is array-backed and read-write. 541 return "???"; 542 } catch (ClassCastException|UnknownHostException e) { 543 // Cannot happen. 544 return "???"; 545 } 546 } 547 548 // Can't be static because it's in a non-static inner class. 549 // TODO: Make this static once RA is its own class. prefixOptionToString(StringBuffer sb, int offset)550 private void prefixOptionToString(StringBuffer sb, int offset) { 551 String prefix = IPv6AddresstoString(offset + 16); 552 int length = getUint8(mPacket, offset + 2); 553 long valid = getUint32(mPacket, offset + 4); 554 long preferred = getUint32(mPacket, offset + 8); 555 sb.append(String.format("%s/%d %ds/%ds ", prefix, length, valid, preferred)); 556 } 557 rdnssOptionToString(StringBuffer sb, int offset)558 private void rdnssOptionToString(StringBuffer sb, int offset) { 559 int optLen = getUint8(mPacket, offset + 1) * 8; 560 if (optLen < 24) return; // Malformed or empty. 561 long lifetime = getUint32(mPacket, offset + 4); 562 int numServers = (optLen - 8) / 16; 563 sb.append("DNS ").append(lifetime).append("s"); 564 for (int server = 0; server < numServers; server++) { 565 sb.append(" ").append(IPv6AddresstoString(offset + 8 + 16 * server)); 566 } 567 } 568 toString()569 public String toString() { 570 try { 571 StringBuffer sb = new StringBuffer(); 572 sb.append(String.format("RA %s -> %s %ds ", 573 IPv6AddresstoString(IPV6_SRC_ADDR_OFFSET), 574 IPv6AddresstoString(IPV6_DEST_ADDR_OFFSET), 575 getUint16(mPacket, ICMP6_RA_ROUTER_LIFETIME_OFFSET))); 576 for (int i: mPrefixOptionOffsets) { 577 prefixOptionToString(sb, i); 578 } 579 for (int i: mRdnssOptionOffsets) { 580 rdnssOptionToString(sb, i); 581 } 582 return sb.toString(); 583 } catch (BufferUnderflowException|IndexOutOfBoundsException e) { 584 return "<Malformed RA>"; 585 } 586 } 587 588 /** 589 * Add a binary range of the packet that does not include a lifetime to mNonLifetimes. 590 * Assumes mPacket.position() is as far as we've parsed the packet. 591 * @param lastNonLifetimeStart offset within packet of where the last binary range of 592 * data not including a lifetime. 593 * @param lifetimeOffset offset from mPacket.position() to the next lifetime data. 594 * @param lifetimeLength length of the next lifetime data. 595 * @return offset within packet of where the next binary range of data not including 596 * a lifetime. This can be passed into the next invocation of this function 597 * via {@code lastNonLifetimeStart}. 598 */ addNonLifetime(int lastNonLifetimeStart, int lifetimeOffset, int lifetimeLength)599 private int addNonLifetime(int lastNonLifetimeStart, int lifetimeOffset, 600 int lifetimeLength) { 601 lifetimeOffset += mPacket.position(); 602 mNonLifetimes.add(new Pair<Integer, Integer>(lastNonLifetimeStart, 603 lifetimeOffset - lastNonLifetimeStart)); 604 return lifetimeOffset + lifetimeLength; 605 } 606 addNonLifetimeU32(int lastNonLifetimeStart)607 private int addNonLifetimeU32(int lastNonLifetimeStart) { 608 return addNonLifetime(lastNonLifetimeStart, 609 ICMP6_4_BYTE_LIFETIME_OFFSET, ICMP6_4_BYTE_LIFETIME_LEN); 610 } 611 612 // Note that this parses RA and may throw InvalidRaException (from 613 // Buffer.position(int) or due to an invalid-length option) or IndexOutOfBoundsException 614 // (from ByteBuffer.get(int) ) if parsing encounters something non-compliant with 615 // specifications. Ra(byte[] packet, int length)616 Ra(byte[] packet, int length) throws InvalidRaException { 617 if (length < ICMP6_RA_OPTION_OFFSET) { 618 throw new InvalidRaException("Not an ICMP6 router advertisement"); 619 } 620 621 mPacket = ByteBuffer.wrap(Arrays.copyOf(packet, length)); 622 mLastSeen = currentTimeSeconds(); 623 624 // Sanity check packet in case a packet arrives before we attach RA filter 625 // to our packet socket. b/29586253 626 if (getUint16(mPacket, ETH_ETHERTYPE_OFFSET) != ETH_P_IPV6 || 627 getUint8(mPacket, IPV6_NEXT_HEADER_OFFSET) != IPPROTO_ICMPV6 || 628 getUint8(mPacket, ICMP6_TYPE_OFFSET) != ICMPV6_ROUTER_ADVERTISEMENT) { 629 throw new InvalidRaException("Not an ICMP6 router advertisement"); 630 } 631 632 633 RaEvent.Builder builder = new RaEvent.Builder(); 634 635 // Ignore the flow label and low 4 bits of traffic class. 636 int lastNonLifetimeStart = addNonLifetime(0, 637 IPV6_FLOW_LABEL_OFFSET, 638 IPV6_FLOW_LABEL_LEN); 639 640 // Ignore the checksum. 641 lastNonLifetimeStart = addNonLifetime(lastNonLifetimeStart, 642 ICMP6_RA_CHECKSUM_OFFSET, 643 ICMP6_RA_CHECKSUM_LEN); 644 645 // Parse router lifetime 646 lastNonLifetimeStart = addNonLifetime(lastNonLifetimeStart, 647 ICMP6_RA_ROUTER_LIFETIME_OFFSET, 648 ICMP6_RA_ROUTER_LIFETIME_LEN); 649 builder.updateRouterLifetime(getUint16(mPacket, ICMP6_RA_ROUTER_LIFETIME_OFFSET)); 650 651 // Ensures that the RA is not truncated. 652 mPacket.position(ICMP6_RA_OPTION_OFFSET); 653 while (mPacket.hasRemaining()) { 654 final int position = mPacket.position(); 655 final int optionType = getUint8(mPacket, position); 656 final int optionLength = getUint8(mPacket, position + 1) * 8; 657 long lifetime; 658 switch (optionType) { 659 case ICMP6_PREFIX_OPTION_TYPE: 660 // Parse valid lifetime 661 lastNonLifetimeStart = addNonLifetime(lastNonLifetimeStart, 662 ICMP6_PREFIX_OPTION_VALID_LIFETIME_OFFSET, 663 ICMP6_PREFIX_OPTION_VALID_LIFETIME_LEN); 664 lifetime = getUint32(mPacket, 665 position + ICMP6_PREFIX_OPTION_VALID_LIFETIME_OFFSET); 666 builder.updatePrefixValidLifetime(lifetime); 667 // Parse preferred lifetime 668 lastNonLifetimeStart = addNonLifetime(lastNonLifetimeStart, 669 ICMP6_PREFIX_OPTION_PREFERRED_LIFETIME_OFFSET, 670 ICMP6_PREFIX_OPTION_PREFERRED_LIFETIME_LEN); 671 lifetime = getUint32(mPacket, 672 position + ICMP6_PREFIX_OPTION_PREFERRED_LIFETIME_OFFSET); 673 builder.updatePrefixPreferredLifetime(lifetime); 674 mPrefixOptionOffsets.add(position); 675 break; 676 // These three options have the same lifetime offset and size, and 677 // are processed with the same specialized addNonLifetimeU32: 678 case ICMP6_RDNSS_OPTION_TYPE: 679 mRdnssOptionOffsets.add(position); 680 lastNonLifetimeStart = addNonLifetimeU32(lastNonLifetimeStart); 681 lifetime = getUint32(mPacket, position + ICMP6_4_BYTE_LIFETIME_OFFSET); 682 builder.updateRdnssLifetime(lifetime); 683 break; 684 case ICMP6_ROUTE_INFO_OPTION_TYPE: 685 lastNonLifetimeStart = addNonLifetimeU32(lastNonLifetimeStart); 686 lifetime = getUint32(mPacket, position + ICMP6_4_BYTE_LIFETIME_OFFSET); 687 builder.updateRouteInfoLifetime(lifetime); 688 break; 689 case ICMP6_DNSSL_OPTION_TYPE: 690 lastNonLifetimeStart = addNonLifetimeU32(lastNonLifetimeStart); 691 lifetime = getUint32(mPacket, position + ICMP6_4_BYTE_LIFETIME_OFFSET); 692 builder.updateDnsslLifetime(lifetime); 693 break; 694 default: 695 // RFC4861 section 4.2 dictates we ignore unknown options for fowards 696 // compatibility. 697 break; 698 } 699 if (optionLength <= 0) { 700 throw new InvalidRaException(String.format( 701 "Invalid option length opt=%d len=%d", optionType, optionLength)); 702 } 703 mPacket.position(position + optionLength); 704 } 705 // Mark non-lifetime bytes since last lifetime. 706 addNonLifetime(lastNonLifetimeStart, 0, 0); 707 mMinLifetime = minLifetime(packet, length); 708 mMetricsLog.log(builder.build()); 709 } 710 711 // Ignoring lifetimes (which may change) does {@code packet} match this RA? matches(byte[] packet, int length)712 boolean matches(byte[] packet, int length) { 713 if (length != mPacket.capacity()) return false; 714 byte[] referencePacket = mPacket.array(); 715 for (Pair<Integer, Integer> nonLifetime : mNonLifetimes) { 716 for (int i = nonLifetime.first; i < (nonLifetime.first + nonLifetime.second); i++) { 717 if (packet[i] != referencePacket[i]) return false; 718 } 719 } 720 return true; 721 } 722 723 // What is the minimum of all lifetimes within {@code packet} in seconds? 724 // Precondition: matches(packet, length) already returned true. minLifetime(byte[] packet, int length)725 long minLifetime(byte[] packet, int length) { 726 long minLifetime = Long.MAX_VALUE; 727 // Wrap packet in ByteBuffer so we can read big-endian values easily 728 ByteBuffer byteBuffer = ByteBuffer.wrap(packet); 729 for (int i = 0; (i + 1) < mNonLifetimes.size(); i++) { 730 int offset = mNonLifetimes.get(i).first + mNonLifetimes.get(i).second; 731 732 // The flow label is in mNonLifetimes, but it's not a lifetime. 733 if (offset == IPV6_FLOW_LABEL_OFFSET) { 734 continue; 735 } 736 737 // The checksum is in mNonLifetimes, but it's not a lifetime. 738 if (offset == ICMP6_RA_CHECKSUM_OFFSET) { 739 continue; 740 } 741 742 final int lifetimeLength = mNonLifetimes.get(i+1).first - offset; 743 final long optionLifetime; 744 switch (lifetimeLength) { 745 case 2: 746 optionLifetime = getUint16(byteBuffer, offset); 747 break; 748 case 4: 749 optionLifetime = getUint32(byteBuffer, offset); 750 break; 751 default: 752 throw new IllegalStateException("bogus lifetime size " + lifetimeLength); 753 } 754 minLifetime = Math.min(minLifetime, optionLifetime); 755 } 756 return minLifetime; 757 } 758 759 // How many seconds does this RA's have to live, taking into account the fact 760 // that we might have seen it a while ago. currentLifetime()761 long currentLifetime() { 762 return mMinLifetime - (currentTimeSeconds() - mLastSeen); 763 } 764 isExpired()765 boolean isExpired() { 766 // TODO: We may want to handle 0 lifetime RAs differently, if they are common. We'll 767 // have to calculte the filter lifetime specially as a fraction of 0 is still 0. 768 return currentLifetime() <= 0; 769 } 770 771 // Append a filter for this RA to {@code gen}. Jump to DROP_LABEL if it should be dropped. 772 // Jump to the next filter if packet doesn't match this RA. 773 @GuardedBy("ApfFilter.this") generateFilterLocked(ApfGenerator gen)774 long generateFilterLocked(ApfGenerator gen) throws IllegalInstructionException { 775 String nextFilterLabel = "Ra" + getUniqueNumberLocked(); 776 // Skip if packet is not the right size 777 gen.addLoadFromMemory(Register.R0, gen.PACKET_SIZE_MEMORY_SLOT); 778 gen.addJumpIfR0NotEquals(mPacket.capacity(), nextFilterLabel); 779 int filterLifetime = (int)(currentLifetime() / FRACTION_OF_LIFETIME_TO_FILTER); 780 // Skip filter if expired 781 gen.addLoadFromMemory(Register.R0, gen.FILTER_AGE_MEMORY_SLOT); 782 gen.addJumpIfR0GreaterThan(filterLifetime, nextFilterLabel); 783 for (int i = 0; i < mNonLifetimes.size(); i++) { 784 // Generate code to match the packet bytes 785 Pair<Integer, Integer> nonLifetime = mNonLifetimes.get(i); 786 // Don't generate JNEBS instruction for 0 bytes as it always fails the 787 // ASSERT_FORWARD_IN_PROGRAM(pc + cmp_imm - 1) check where cmp_imm is 788 // the number of bytes to compare. nonLifetime is zero between the 789 // valid and preferred lifetimes in the prefix option. 790 if (nonLifetime.second != 0) { 791 gen.addLoadImmediate(Register.R0, nonLifetime.first); 792 gen.addJumpIfBytesNotEqual(Register.R0, 793 Arrays.copyOfRange(mPacket.array(), nonLifetime.first, 794 nonLifetime.first + nonLifetime.second), 795 nextFilterLabel); 796 } 797 // Generate code to test the lifetimes haven't gone down too far 798 if ((i + 1) < mNonLifetimes.size()) { 799 Pair<Integer, Integer> nextNonLifetime = mNonLifetimes.get(i + 1); 800 int offset = nonLifetime.first + nonLifetime.second; 801 802 // Skip the Flow label. 803 if (offset == IPV6_FLOW_LABEL_OFFSET) { 804 continue; 805 } 806 // Skip the checksum. 807 if (offset == ICMP6_RA_CHECKSUM_OFFSET) { 808 continue; 809 } 810 int length = nextNonLifetime.first - offset; 811 switch (length) { 812 case 4: gen.addLoad32(Register.R0, offset); break; 813 case 2: gen.addLoad16(Register.R0, offset); break; 814 default: throw new IllegalStateException("bogus lifetime size " + length); 815 } 816 gen.addJumpIfR0LessThan(filterLifetime, nextFilterLabel); 817 } 818 } 819 maybeSetCounter(gen, Counter.DROPPED_RA); 820 gen.addJump(mCountAndDropLabel); 821 gen.defineLabel(nextFilterLabel); 822 return filterLifetime; 823 } 824 } 825 826 // Maximum number of RAs to filter for. 827 private static final int MAX_RAS = 10; 828 829 @GuardedBy("this") 830 private ArrayList<Ra> mRas = new ArrayList<Ra>(); 831 832 // There is always some marginal benefit to updating the installed APF program when an RA is 833 // seen because we can extend the program's lifetime slightly, but there is some cost to 834 // updating the program, so don't bother unless the program is going to expire soon. This 835 // constant defines "soon" in seconds. 836 private static final long MAX_PROGRAM_LIFETIME_WORTH_REFRESHING = 30; 837 // We don't want to filter an RA for it's whole lifetime as it'll be expired by the time we ever 838 // see a refresh. Using half the lifetime might be a good idea except for the fact that 839 // packets may be dropped, so let's use 6. 840 private static final int FRACTION_OF_LIFETIME_TO_FILTER = 6; 841 842 // When did we last install a filter program? In seconds since Unix Epoch. 843 @GuardedBy("this") 844 private long mLastTimeInstalledProgram; 845 // How long should the last installed filter program live for? In seconds. 846 @GuardedBy("this") 847 private long mLastInstalledProgramMinLifetime; 848 @GuardedBy("this") 849 private ApfProgramEvent mLastInstallEvent; 850 851 // For debugging only. The last program installed. 852 @GuardedBy("this") 853 private byte[] mLastInstalledProgram; 854 855 /** 856 * For debugging only. Contains the latest APF buffer snapshot captured from the firmware. 857 * 858 * A typical size for this buffer is 4KB. It is present only if the WiFi HAL supports 859 * IWifiStaIface#readApfPacketFilterData(), and the APF interpreter advertised support for 860 * the opcodes to access the data buffer (LDDW and STDW). 861 */ 862 @GuardedBy("this") @Nullable 863 private byte[] mDataSnapshot; 864 865 // How many times the program was updated since we started. 866 @GuardedBy("this") 867 private int mNumProgramUpdates = 0; 868 // How many times the program was updated since we started for allowing multicast traffic. 869 @GuardedBy("this") 870 private int mNumProgramUpdatesAllowingMulticast = 0; 871 872 /** 873 * Generate filter code to process ARP packets. Execution of this code ends in either the 874 * DROP_LABEL or PASS_LABEL and does not fall off the end. 875 * Preconditions: 876 * - Packet being filtered is ARP 877 */ 878 @GuardedBy("this") generateArpFilterLocked(ApfGenerator gen)879 private void generateArpFilterLocked(ApfGenerator gen) throws IllegalInstructionException { 880 // Here's a basic summary of what the ARP filter program does: 881 // 882 // if not ARP IPv4 883 // pass 884 // if not ARP IPv4 reply or request 885 // pass 886 // if unicast ARP reply 887 // pass 888 // if interface has no IPv4 address 889 // if target ip is 0.0.0.0 890 // drop 891 // else 892 // if target ip is not the interface ip 893 // drop 894 // pass 895 896 final String checkTargetIPv4 = "checkTargetIPv4"; 897 898 // Pass if not ARP IPv4. 899 gen.addLoadImmediate(Register.R0, ARP_HEADER_OFFSET); 900 maybeSetCounter(gen, Counter.PASSED_ARP_NON_IPV4); 901 gen.addJumpIfBytesNotEqual(Register.R0, ARP_IPV4_HEADER, mCountAndPassLabel); 902 903 // Pass if unknown ARP opcode. 904 gen.addLoad16(Register.R0, ARP_OPCODE_OFFSET); 905 gen.addJumpIfR0Equals(ARP_OPCODE_REQUEST, checkTargetIPv4); // Skip to unicast check 906 maybeSetCounter(gen, Counter.PASSED_ARP_UNKNOWN); 907 gen.addJumpIfR0NotEquals(ARP_OPCODE_REPLY, mCountAndPassLabel); 908 909 // Pass if unicast reply. 910 gen.addLoadImmediate(Register.R0, ETH_DEST_ADDR_OFFSET); 911 maybeSetCounter(gen, Counter.PASSED_ARP_UNICAST_REPLY); 912 gen.addJumpIfBytesNotEqual(Register.R0, ETH_BROADCAST_MAC_ADDRESS, mCountAndPassLabel); 913 914 // Either a unicast request, a unicast reply, or a broadcast reply. 915 gen.defineLabel(checkTargetIPv4); 916 if (mIPv4Address == null) { 917 // When there is no IPv4 address, drop GARP replies (b/29404209). 918 gen.addLoad32(Register.R0, ARP_TARGET_IP_ADDRESS_OFFSET); 919 maybeSetCounter(gen, Counter.DROPPED_GARP_REPLY); 920 gen.addJumpIfR0Equals(IPV4_ANY_HOST_ADDRESS, mCountAndDropLabel); 921 } else { 922 // When there is an IPv4 address, drop unicast/broadcast requests 923 // and broadcast replies with a different target IPv4 address. 924 gen.addLoadImmediate(Register.R0, ARP_TARGET_IP_ADDRESS_OFFSET); 925 maybeSetCounter(gen, Counter.DROPPED_ARP_OTHER_HOST); 926 gen.addJumpIfBytesNotEqual(Register.R0, mIPv4Address, mCountAndDropLabel); 927 } 928 929 maybeSetCounter(gen, Counter.PASSED_ARP); 930 gen.addJump(mCountAndPassLabel); 931 } 932 933 /** 934 * Generate filter code to process IPv4 packets. Execution of this code ends in either the 935 * DROP_LABEL or PASS_LABEL and does not fall off the end. 936 * Preconditions: 937 * - Packet being filtered is IPv4 938 */ 939 @GuardedBy("this") generateIPv4FilterLocked(ApfGenerator gen)940 private void generateIPv4FilterLocked(ApfGenerator gen) throws IllegalInstructionException { 941 // Here's a basic summary of what the IPv4 filter program does: 942 // 943 // if filtering multicast (i.e. multicast lock not held): 944 // if it's DHCP destined to our MAC: 945 // pass 946 // if it's L2 broadcast: 947 // drop 948 // if it's IPv4 multicast: 949 // drop 950 // if it's IPv4 broadcast: 951 // drop 952 // pass 953 954 if (mMulticastFilter) { 955 final String skipDhcpv4Filter = "skip_dhcp_v4_filter"; 956 957 // Pass DHCP addressed to us. 958 // Check it's UDP. 959 gen.addLoad8(Register.R0, IPV4_PROTOCOL_OFFSET); 960 gen.addJumpIfR0NotEquals(IPPROTO_UDP, skipDhcpv4Filter); 961 // Check it's not a fragment. This matches the BPF filter installed by the DHCP client. 962 gen.addLoad16(Register.R0, IPV4_FRAGMENT_OFFSET_OFFSET); 963 gen.addJumpIfR0AnyBitsSet(IPV4_FRAGMENT_OFFSET_MASK, skipDhcpv4Filter); 964 // Check it's addressed to DHCP client port. 965 gen.addLoadFromMemory(Register.R1, gen.IPV4_HEADER_SIZE_MEMORY_SLOT); 966 gen.addLoad16Indexed(Register.R0, UDP_DESTINATION_PORT_OFFSET); 967 gen.addJumpIfR0NotEquals(DHCP_CLIENT_PORT, skipDhcpv4Filter); 968 // Check it's DHCP to our MAC address. 969 gen.addLoadImmediate(Register.R0, DHCP_CLIENT_MAC_OFFSET); 970 // NOTE: Relies on R1 containing IPv4 header offset. 971 gen.addAddR1(); 972 gen.addJumpIfBytesNotEqual(Register.R0, mHardwareAddress, skipDhcpv4Filter); 973 maybeSetCounter(gen, Counter.PASSED_DHCP); 974 gen.addJump(mCountAndPassLabel); 975 976 // Drop all multicasts/broadcasts. 977 gen.defineLabel(skipDhcpv4Filter); 978 979 // If IPv4 destination address is in multicast range, drop. 980 gen.addLoad8(Register.R0, IPV4_DEST_ADDR_OFFSET); 981 gen.addAnd(0xf0); 982 maybeSetCounter(gen, Counter.DROPPED_IPV4_MULTICAST); 983 gen.addJumpIfR0Equals(0xe0, mCountAndDropLabel); 984 985 // If IPv4 broadcast packet, drop regardless of L2 (b/30231088). 986 maybeSetCounter(gen, Counter.DROPPED_IPV4_BROADCAST_ADDR); 987 gen.addLoad32(Register.R0, IPV4_DEST_ADDR_OFFSET); 988 gen.addJumpIfR0Equals(IPV4_BROADCAST_ADDRESS, mCountAndDropLabel); 989 if (mIPv4Address != null && mIPv4PrefixLength < 31) { 990 maybeSetCounter(gen, Counter.DROPPED_IPV4_BROADCAST_NET); 991 int broadcastAddr = ipv4BroadcastAddress(mIPv4Address, mIPv4PrefixLength); 992 gen.addJumpIfR0Equals(broadcastAddr, mCountAndDropLabel); 993 } 994 995 // If L2 broadcast packet, drop. 996 // TODO: can we invert this condition to fall through to the common pass case below? 997 maybeSetCounter(gen, Counter.PASSED_IPV4_UNICAST); 998 gen.addLoadImmediate(Register.R0, ETH_DEST_ADDR_OFFSET); 999 gen.addJumpIfBytesNotEqual(Register.R0, ETH_BROADCAST_MAC_ADDRESS, mCountAndPassLabel); 1000 maybeSetCounter(gen, Counter.DROPPED_IPV4_L2_BROADCAST); 1001 gen.addJump(mCountAndDropLabel); 1002 } 1003 1004 // Otherwise, pass 1005 maybeSetCounter(gen, Counter.PASSED_IPV4); 1006 gen.addJump(mCountAndPassLabel); 1007 } 1008 1009 1010 /** 1011 * Generate filter code to process IPv6 packets. Execution of this code ends in either the 1012 * DROP_LABEL or PASS_LABEL, or falls off the end for ICMPv6 packets. 1013 * Preconditions: 1014 * - Packet being filtered is IPv6 1015 */ 1016 @GuardedBy("this") generateIPv6FilterLocked(ApfGenerator gen)1017 private void generateIPv6FilterLocked(ApfGenerator gen) throws IllegalInstructionException { 1018 // Here's a basic summary of what the IPv6 filter program does: 1019 // 1020 // if we're dropping multicast 1021 // if it's not IPCMv6 or it's ICMPv6 but we're in doze mode: 1022 // if it's multicast: 1023 // drop 1024 // pass 1025 // if it's ICMPv6 RS to any: 1026 // drop 1027 // if it's ICMPv6 NA to ff02::1: 1028 // drop 1029 1030 gen.addLoad8(Register.R0, IPV6_NEXT_HEADER_OFFSET); 1031 1032 // Drop multicast if the multicast filter is enabled. 1033 if (mMulticastFilter) { 1034 final String skipIPv6MulticastFilterLabel = "skipIPv6MulticastFilter"; 1035 final String dropAllIPv6MulticastsLabel = "dropAllIPv6Multicast"; 1036 1037 // While in doze mode, drop ICMPv6 multicast pings, let the others pass. 1038 // While awake, let all ICMPv6 multicasts through. 1039 if (mInDozeMode) { 1040 // Not ICMPv6? -> Proceed to multicast filtering 1041 gen.addJumpIfR0NotEquals(IPPROTO_ICMPV6, dropAllIPv6MulticastsLabel); 1042 1043 // ICMPv6 but not ECHO? -> Skip the multicast filter. 1044 // (ICMPv6 ECHO requests will go through the multicast filter below). 1045 gen.addLoad8(Register.R0, ICMP6_TYPE_OFFSET); 1046 gen.addJumpIfR0NotEquals(ICMPV6_ECHO_REQUEST_TYPE, skipIPv6MulticastFilterLabel); 1047 } else { 1048 gen.addJumpIfR0Equals(IPPROTO_ICMPV6, skipIPv6MulticastFilterLabel); 1049 } 1050 1051 // Drop all other packets sent to ff00::/8 (multicast prefix). 1052 gen.defineLabel(dropAllIPv6MulticastsLabel); 1053 maybeSetCounter(gen, Counter.DROPPED_IPV6_NON_ICMP_MULTICAST); 1054 gen.addLoad8(Register.R0, IPV6_DEST_ADDR_OFFSET); 1055 gen.addJumpIfR0Equals(0xff, mCountAndDropLabel); 1056 // Not multicast. Pass. 1057 maybeSetCounter(gen, Counter.PASSED_IPV6_UNICAST_NON_ICMP); 1058 gen.addJump(mCountAndPassLabel); 1059 gen.defineLabel(skipIPv6MulticastFilterLabel); 1060 } else { 1061 // If not ICMPv6, pass. 1062 maybeSetCounter(gen, Counter.PASSED_IPV6_NON_ICMP); 1063 gen.addJumpIfR0NotEquals(IPPROTO_ICMPV6, mCountAndPassLabel); 1064 } 1065 1066 // If we got this far, the packet is ICMPv6. Drop some specific types. 1067 1068 // Add unsolicited multicast neighbor announcements filter 1069 String skipUnsolicitedMulticastNALabel = "skipUnsolicitedMulticastNA"; 1070 gen.addLoad8(Register.R0, ICMP6_TYPE_OFFSET); 1071 // Drop all router solicitations (b/32833400) 1072 maybeSetCounter(gen, Counter.DROPPED_IPV6_ROUTER_SOLICITATION); 1073 gen.addJumpIfR0Equals(ICMPV6_ROUTER_SOLICITATION, mCountAndDropLabel); 1074 // If not neighbor announcements, skip filter. 1075 gen.addJumpIfR0NotEquals(ICMPV6_NEIGHBOR_ADVERTISEMENT, skipUnsolicitedMulticastNALabel); 1076 // If to ff02::1, drop. 1077 // TODO: Drop only if they don't contain the address of on-link neighbours. 1078 gen.addLoadImmediate(Register.R0, IPV6_DEST_ADDR_OFFSET); 1079 gen.addJumpIfBytesNotEqual(Register.R0, IPV6_ALL_NODES_ADDRESS, 1080 skipUnsolicitedMulticastNALabel); 1081 maybeSetCounter(gen, Counter.DROPPED_IPV6_MULTICAST_NA); 1082 gen.addJump(mCountAndDropLabel); 1083 gen.defineLabel(skipUnsolicitedMulticastNALabel); 1084 } 1085 1086 /** 1087 * Begin generating an APF program to: 1088 * <ul> 1089 * <li>Drop/Pass 802.3 frames (based on policy) 1090 * <li>Drop packets with EtherType within the Black List 1091 * <li>Drop ARP requests not for us, if mIPv4Address is set, 1092 * <li>Drop IPv4 broadcast packets, except DHCP destined to our MAC, 1093 * <li>Drop IPv4 multicast packets, if mMulticastFilter, 1094 * <li>Pass all other IPv4 packets, 1095 * <li>Drop all broadcast non-IP non-ARP packets. 1096 * <li>Pass all non-ICMPv6 IPv6 packets, 1097 * <li>Pass all non-IPv4 and non-IPv6 packets, 1098 * <li>Drop IPv6 ICMPv6 NAs to ff02::1. 1099 * <li>Drop IPv6 ICMPv6 RSs. 1100 * <li>Let execution continue off the end of the program for IPv6 ICMPv6 packets. This allows 1101 * insertion of RA filters here, or if there aren't any, just passes the packets. 1102 * </ul> 1103 */ 1104 @GuardedBy("this") emitPrologueLocked()1105 private ApfGenerator emitPrologueLocked() throws IllegalInstructionException { 1106 // This is guaranteed to succeed because of the check in maybeCreate. 1107 ApfGenerator gen = new ApfGenerator(mApfCapabilities.apfVersionSupported); 1108 1109 if (mApfCapabilities.hasDataAccess()) { 1110 // Increment TOTAL_PACKETS 1111 maybeSetCounter(gen, Counter.TOTAL_PACKETS); 1112 gen.addLoadData(Register.R0, 0); // load counter 1113 gen.addAdd(1); 1114 gen.addStoreData(Register.R0, 0); // write-back counter 1115 } 1116 1117 // Here's a basic summary of what the initial program does: 1118 // 1119 // if it's a 802.3 Frame (ethtype < 0x0600): 1120 // drop or pass based on configurations 1121 // if it has a ether-type that belongs to the black list 1122 // drop 1123 // if it's ARP: 1124 // insert ARP filter to drop or pass these appropriately 1125 // if it's IPv4: 1126 // insert IPv4 filter to drop or pass these appropriately 1127 // if it's not IPv6: 1128 // if it's broadcast: 1129 // drop 1130 // pass 1131 // insert IPv6 filter to drop, pass, or fall off the end for ICMPv6 packets 1132 1133 gen.addLoad16(Register.R0, ETH_ETHERTYPE_OFFSET); 1134 1135 if (mDrop802_3Frames) { 1136 // drop 802.3 frames (ethtype < 0x0600) 1137 maybeSetCounter(gen, Counter.DROPPED_802_3_FRAME); 1138 gen.addJumpIfR0LessThan(ETH_TYPE_MIN, mCountAndDropLabel); 1139 } 1140 1141 // Handle ether-type black list 1142 maybeSetCounter(gen, Counter.DROPPED_ETHERTYPE_BLACKLISTED); 1143 for (int p : mEthTypeBlackList) { 1144 gen.addJumpIfR0Equals(p, mCountAndDropLabel); 1145 } 1146 1147 // Add ARP filters: 1148 String skipArpFiltersLabel = "skipArpFilters"; 1149 gen.addJumpIfR0NotEquals(ETH_P_ARP, skipArpFiltersLabel); 1150 generateArpFilterLocked(gen); 1151 gen.defineLabel(skipArpFiltersLabel); 1152 1153 // Add IPv4 filters: 1154 String skipIPv4FiltersLabel = "skipIPv4Filters"; 1155 // NOTE: Relies on R0 containing ethertype. This is safe because if we got here, we did not 1156 // execute the ARP filter, since that filter does not fall through, but either drops or 1157 // passes. 1158 gen.addJumpIfR0NotEquals(ETH_P_IP, skipIPv4FiltersLabel); 1159 generateIPv4FilterLocked(gen); 1160 gen.defineLabel(skipIPv4FiltersLabel); 1161 1162 // Check for IPv6: 1163 // NOTE: Relies on R0 containing ethertype. This is safe because if we got here, we did not 1164 // execute the ARP or IPv4 filters, since those filters do not fall through, but either 1165 // drop or pass. 1166 String ipv6FilterLabel = "IPv6Filters"; 1167 gen.addJumpIfR0Equals(ETH_P_IPV6, ipv6FilterLabel); 1168 1169 // Drop non-IP non-ARP broadcasts, pass the rest 1170 gen.addLoadImmediate(Register.R0, ETH_DEST_ADDR_OFFSET); 1171 maybeSetCounter(gen, Counter.PASSED_NON_IP_UNICAST); 1172 gen.addJumpIfBytesNotEqual(Register.R0, ETH_BROADCAST_MAC_ADDRESS, mCountAndPassLabel); 1173 maybeSetCounter(gen, Counter.DROPPED_ETH_BROADCAST); 1174 gen.addJump(mCountAndDropLabel); 1175 1176 // Add IPv6 filters: 1177 gen.defineLabel(ipv6FilterLabel); 1178 generateIPv6FilterLocked(gen); 1179 return gen; 1180 } 1181 1182 /** 1183 * Append packet counting epilogue to the APF program. 1184 * 1185 * Currently, the epilogue consists of two trampolines which count passed and dropped packets 1186 * before jumping to the actual PASS and DROP labels. 1187 */ 1188 @GuardedBy("this") emitEpilogue(ApfGenerator gen)1189 private void emitEpilogue(ApfGenerator gen) throws IllegalInstructionException { 1190 // If APFv4 is unsupported, no epilogue is necessary: if execution reached this far, it 1191 // will just fall-through to the PASS label. 1192 if (!mApfCapabilities.hasDataAccess()) return; 1193 1194 // Execution will reach the bottom of the program if none of the filters match, 1195 // which will pass the packet to the application processor. 1196 maybeSetCounter(gen, Counter.PASSED_IPV6_ICMP); 1197 1198 // Append the count & pass trampoline, which increments the counter at the data address 1199 // pointed to by R1, then jumps to the pass label. This saves a few bytes over inserting 1200 // the entire sequence inline for every counter. 1201 gen.defineLabel(mCountAndPassLabel); 1202 gen.addLoadData(Register.R0, 0); // R0 = *(R1 + 0) 1203 gen.addAdd(1); // R0++ 1204 gen.addStoreData(Register.R0, 0); // *(R1 + 0) = R0 1205 gen.addJump(gen.PASS_LABEL); 1206 1207 // Same as above for the count & drop trampoline. 1208 gen.defineLabel(mCountAndDropLabel); 1209 gen.addLoadData(Register.R0, 0); // R0 = *(R1 + 0) 1210 gen.addAdd(1); // R0++ 1211 gen.addStoreData(Register.R0, 0); // *(R1 + 0) = R0 1212 gen.addJump(gen.DROP_LABEL); 1213 } 1214 1215 /** 1216 * Generate and install a new filter program. 1217 */ 1218 @GuardedBy("this") 1219 @VisibleForTesting installNewProgramLocked()1220 void installNewProgramLocked() { 1221 purgeExpiredRasLocked(); 1222 ArrayList<Ra> rasToFilter = new ArrayList<>(); 1223 final byte[] program; 1224 long programMinLifetime = Long.MAX_VALUE; 1225 long maximumApfProgramSize = mApfCapabilities.maximumApfProgramSize; 1226 if (mApfCapabilities.hasDataAccess()) { 1227 // Reserve space for the counters. 1228 maximumApfProgramSize -= Counter.totalSize(); 1229 } 1230 1231 try { 1232 // Step 1: Determine how many RA filters we can fit in the program. 1233 ApfGenerator gen = emitPrologueLocked(); 1234 1235 // The epilogue normally goes after the RA filters, but add it early to include its 1236 // length when estimating the total. 1237 emitEpilogue(gen); 1238 1239 // Can't fit the program even without any RA filters? 1240 if (gen.programLengthOverEstimate() > maximumApfProgramSize) { 1241 Log.e(TAG, "Program exceeds maximum size " + maximumApfProgramSize); 1242 return; 1243 } 1244 1245 for (Ra ra : mRas) { 1246 ra.generateFilterLocked(gen); 1247 // Stop if we get too big. 1248 if (gen.programLengthOverEstimate() > maximumApfProgramSize) break; 1249 rasToFilter.add(ra); 1250 } 1251 1252 // Step 2: Actually generate the program 1253 gen = emitPrologueLocked(); 1254 for (Ra ra : rasToFilter) { 1255 programMinLifetime = Math.min(programMinLifetime, ra.generateFilterLocked(gen)); 1256 } 1257 emitEpilogue(gen); 1258 program = gen.generate(); 1259 } catch (IllegalInstructionException|IllegalStateException e) { 1260 Log.e(TAG, "Failed to generate APF program.", e); 1261 return; 1262 } 1263 final long now = currentTimeSeconds(); 1264 mLastTimeInstalledProgram = now; 1265 mLastInstalledProgramMinLifetime = programMinLifetime; 1266 mLastInstalledProgram = program; 1267 mNumProgramUpdates++; 1268 1269 if (VDBG) { 1270 hexDump("Installing filter: ", program, program.length); 1271 } 1272 mIpClientCallback.installPacketFilter(program); 1273 logApfProgramEventLocked(now); 1274 mLastInstallEvent = new ApfProgramEvent(); 1275 mLastInstallEvent.lifetime = programMinLifetime; 1276 mLastInstallEvent.filteredRas = rasToFilter.size(); 1277 mLastInstallEvent.currentRas = mRas.size(); 1278 mLastInstallEvent.programLength = program.length; 1279 mLastInstallEvent.flags = ApfProgramEvent.flagsFor(mIPv4Address != null, mMulticastFilter); 1280 } 1281 1282 @GuardedBy("this") logApfProgramEventLocked(long now)1283 private void logApfProgramEventLocked(long now) { 1284 if (mLastInstallEvent == null) { 1285 return; 1286 } 1287 ApfProgramEvent ev = mLastInstallEvent; 1288 mLastInstallEvent = null; 1289 ev.actualLifetime = now - mLastTimeInstalledProgram; 1290 if (ev.actualLifetime < APF_PROGRAM_EVENT_LIFETIME_THRESHOLD) { 1291 return; 1292 } 1293 mMetricsLog.log(ev); 1294 } 1295 1296 /** 1297 * Returns {@code true} if a new program should be installed because the current one dies soon. 1298 */ shouldInstallnewProgram()1299 private boolean shouldInstallnewProgram() { 1300 long expiry = mLastTimeInstalledProgram + mLastInstalledProgramMinLifetime; 1301 return expiry < currentTimeSeconds() + MAX_PROGRAM_LIFETIME_WORTH_REFRESHING; 1302 } 1303 hexDump(String msg, byte[] packet, int length)1304 private void hexDump(String msg, byte[] packet, int length) { 1305 log(msg + HexDump.toHexString(packet, 0, length, false /* lowercase */)); 1306 } 1307 1308 @GuardedBy("this") purgeExpiredRasLocked()1309 private void purgeExpiredRasLocked() { 1310 for (int i = 0; i < mRas.size();) { 1311 if (mRas.get(i).isExpired()) { 1312 log("Expiring " + mRas.get(i)); 1313 mRas.remove(i); 1314 } else { 1315 i++; 1316 } 1317 } 1318 } 1319 1320 /** 1321 * Process an RA packet, updating the list of known RAs and installing a new APF program 1322 * if the current APF program should be updated. 1323 * @return a ProcessRaResult enum describing what action was performed. 1324 */ 1325 @VisibleForTesting processRa(byte[] packet, int length)1326 synchronized ProcessRaResult processRa(byte[] packet, int length) { 1327 if (VDBG) hexDump("Read packet = ", packet, length); 1328 1329 // Have we seen this RA before? 1330 for (int i = 0; i < mRas.size(); i++) { 1331 Ra ra = mRas.get(i); 1332 if (ra.matches(packet, length)) { 1333 if (VDBG) log("matched RA " + ra); 1334 // Update lifetimes. 1335 ra.mLastSeen = currentTimeSeconds(); 1336 ra.mMinLifetime = ra.minLifetime(packet, length); 1337 ra.seenCount++; 1338 1339 // Keep mRas in LRU order so as to prioritize generating filters for recently seen 1340 // RAs. LRU prioritizes this because RA filters are generated in order from mRas 1341 // until the filter program exceeds the maximum filter program size allowed by the 1342 // chipset, so RAs appearing earlier in mRas are more likely to make it into the 1343 // filter program. 1344 // TODO: consider sorting the RAs in order of increasing expiry time as well. 1345 // Swap to front of array. 1346 mRas.add(0, mRas.remove(i)); 1347 1348 // If the current program doesn't expire for a while, don't update. 1349 if (shouldInstallnewProgram()) { 1350 installNewProgramLocked(); 1351 return ProcessRaResult.UPDATE_EXPIRY; 1352 } 1353 return ProcessRaResult.MATCH; 1354 } 1355 } 1356 purgeExpiredRasLocked(); 1357 // TODO: figure out how to proceed when we've received more then MAX_RAS RAs. 1358 if (mRas.size() >= MAX_RAS) { 1359 return ProcessRaResult.DROPPED; 1360 } 1361 final Ra ra; 1362 try { 1363 ra = new Ra(packet, length); 1364 } catch (Exception e) { 1365 Log.e(TAG, "Error parsing RA", e); 1366 return ProcessRaResult.PARSE_ERROR; 1367 } 1368 // Ignore 0 lifetime RAs. 1369 if (ra.isExpired()) { 1370 return ProcessRaResult.ZERO_LIFETIME; 1371 } 1372 log("Adding " + ra); 1373 mRas.add(ra); 1374 installNewProgramLocked(); 1375 return ProcessRaResult.UPDATE_NEW_RA; 1376 } 1377 1378 /** 1379 * Create an {@link ApfFilter} if {@code apfCapabilities} indicates support for packet 1380 * filtering using APF programs. 1381 */ maybeCreate(Context context, ApfConfiguration config, InterfaceParams ifParams, IpClient.Callback ipClientCallback)1382 public static ApfFilter maybeCreate(Context context, ApfConfiguration config, 1383 InterfaceParams ifParams, IpClient.Callback ipClientCallback) { 1384 if (context == null || config == null || ifParams == null) return null; 1385 ApfCapabilities apfCapabilities = config.apfCapabilities; 1386 if (apfCapabilities == null) return null; 1387 if (apfCapabilities.apfVersionSupported == 0) return null; 1388 if (apfCapabilities.maximumApfProgramSize < 512) { 1389 Log.e(TAG, "Unacceptably small APF limit: " + apfCapabilities.maximumApfProgramSize); 1390 return null; 1391 } 1392 // For now only support generating programs for Ethernet frames. If this restriction is 1393 // lifted: 1394 // 1. the program generator will need its offsets adjusted. 1395 // 2. the packet filter attached to our packet socket will need its offset adjusted. 1396 if (apfCapabilities.apfPacketFormat != ARPHRD_ETHER) return null; 1397 if (!ApfGenerator.supportsVersion(apfCapabilities.apfVersionSupported)) { 1398 Log.e(TAG, "Unsupported APF version: " + apfCapabilities.apfVersionSupported); 1399 return null; 1400 } 1401 1402 return new ApfFilter(context, config, ifParams, ipClientCallback, new IpConnectivityLog()); 1403 } 1404 shutdown()1405 public synchronized void shutdown() { 1406 if (mReceiveThread != null) { 1407 log("shutting down"); 1408 mReceiveThread.halt(); // Also closes socket. 1409 mReceiveThread = null; 1410 } 1411 mRas.clear(); 1412 mContext.unregisterReceiver(mDeviceIdleReceiver); 1413 } 1414 setMulticastFilter(boolean isEnabled)1415 public synchronized void setMulticastFilter(boolean isEnabled) { 1416 if (mMulticastFilter == isEnabled) return; 1417 mMulticastFilter = isEnabled; 1418 if (!isEnabled) { 1419 mNumProgramUpdatesAllowingMulticast++; 1420 } 1421 installNewProgramLocked(); 1422 } 1423 1424 @VisibleForTesting setDozeMode(boolean isEnabled)1425 public synchronized void setDozeMode(boolean isEnabled) { 1426 if (mInDozeMode == isEnabled) return; 1427 mInDozeMode = isEnabled; 1428 installNewProgramLocked(); 1429 } 1430 1431 /** Find the single IPv4 LinkAddress if there is one, otherwise return null. */ findIPv4LinkAddress(LinkProperties lp)1432 private static LinkAddress findIPv4LinkAddress(LinkProperties lp) { 1433 LinkAddress ipv4Address = null; 1434 for (LinkAddress address : lp.getLinkAddresses()) { 1435 if (!(address.getAddress() instanceof Inet4Address)) { 1436 continue; 1437 } 1438 if (ipv4Address != null && !ipv4Address.isSameAddressAs(address)) { 1439 // More than one IPv4 address, abort. 1440 return null; 1441 } 1442 ipv4Address = address; 1443 } 1444 return ipv4Address; 1445 } 1446 setLinkProperties(LinkProperties lp)1447 public synchronized void setLinkProperties(LinkProperties lp) { 1448 // NOTE: Do not keep a copy of LinkProperties as it would further duplicate state. 1449 final LinkAddress ipv4Address = findIPv4LinkAddress(lp); 1450 final byte[] addr = (ipv4Address != null) ? ipv4Address.getAddress().getAddress() : null; 1451 final int prefix = (ipv4Address != null) ? ipv4Address.getPrefixLength() : 0; 1452 if ((prefix == mIPv4PrefixLength) && Arrays.equals(addr, mIPv4Address)) { 1453 return; 1454 } 1455 mIPv4Address = addr; 1456 mIPv4PrefixLength = prefix; 1457 installNewProgramLocked(); 1458 } 1459 counterValue(byte[] data, Counter counter)1460 static public long counterValue(byte[] data, Counter counter) 1461 throws ArrayIndexOutOfBoundsException { 1462 // Follow the same wrap-around addressing scheme of the interpreter. 1463 int offset = counter.offset(); 1464 if (offset < 0) { 1465 offset = data.length + offset; 1466 } 1467 1468 // Decode 32bit big-endian integer into a long so we can count up beyond 2^31. 1469 long value = 0; 1470 for (int i = 0; i < 4; i++) { 1471 value = value << 8 | (data[offset] & 0xFF); 1472 offset++; 1473 } 1474 return value; 1475 } 1476 dump(IndentingPrintWriter pw)1477 public synchronized void dump(IndentingPrintWriter pw) { 1478 pw.println("Capabilities: " + mApfCapabilities); 1479 pw.println("Receive thread: " + (mReceiveThread != null ? "RUNNING" : "STOPPED")); 1480 pw.println("Multicast: " + (mMulticastFilter ? "DROP" : "ALLOW")); 1481 try { 1482 pw.println("IPv4 address: " + InetAddress.getByAddress(mIPv4Address).getHostAddress()); 1483 } catch (UnknownHostException|NullPointerException e) {} 1484 1485 if (mLastTimeInstalledProgram == 0) { 1486 pw.println("No program installed."); 1487 return; 1488 } 1489 pw.println("Program updates: " + mNumProgramUpdates); 1490 pw.println(String.format( 1491 "Last program length %d, installed %ds ago, lifetime %ds", 1492 mLastInstalledProgram.length, currentTimeSeconds() - mLastTimeInstalledProgram, 1493 mLastInstalledProgramMinLifetime)); 1494 1495 pw.println("RA filters:"); 1496 pw.increaseIndent(); 1497 for (Ra ra: mRas) { 1498 pw.println(ra); 1499 pw.increaseIndent(); 1500 pw.println(String.format( 1501 "Seen: %d, last %ds ago", ra.seenCount, currentTimeSeconds() - ra.mLastSeen)); 1502 if (DBG) { 1503 pw.println("Last match:"); 1504 pw.increaseIndent(); 1505 pw.println(ra.getLastMatchingPacket()); 1506 pw.decreaseIndent(); 1507 } 1508 pw.decreaseIndent(); 1509 } 1510 pw.decreaseIndent(); 1511 1512 if (DBG) { 1513 pw.println("Last program:"); 1514 pw.increaseIndent(); 1515 pw.println(HexDump.toHexString(mLastInstalledProgram, false /* lowercase */)); 1516 pw.decreaseIndent(); 1517 } 1518 1519 pw.println("APF packet counters: "); 1520 pw.increaseIndent(); 1521 if (!mApfCapabilities.hasDataAccess()) { 1522 pw.println("APF counters not supported"); 1523 } else if (mDataSnapshot == null) { 1524 pw.println("No last snapshot."); 1525 } else { 1526 try { 1527 Counter[] counters = Counter.class.getEnumConstants(); 1528 for (Counter c : Arrays.asList(counters).subList(1, counters.length)) { 1529 long value = counterValue(mDataSnapshot, c); 1530 // Only print non-zero counters 1531 if (value != 0) { 1532 pw.println(c.toString() + ": " + value); 1533 } 1534 } 1535 } catch (ArrayIndexOutOfBoundsException e) { 1536 pw.println("Uh-oh: " + e); 1537 } 1538 if (VDBG) { 1539 pw.println("Raw data dump: "); 1540 pw.println(HexDump.dumpHexString(mDataSnapshot)); 1541 } 1542 } 1543 pw.decreaseIndent(); 1544 } 1545 1546 // TODO: move to android.net.NetworkUtils 1547 @VisibleForTesting ipv4BroadcastAddress(byte[] addrBytes, int prefixLength)1548 public static int ipv4BroadcastAddress(byte[] addrBytes, int prefixLength) { 1549 return bytesToBEInt(addrBytes) | (int) (uint32(-1) >>> prefixLength); 1550 } 1551 } 1552