diff --git a/Android.mk b/Android.mk
index 5a35e22..5f2fe63 100644
--- a/Android.mk
+++ b/Android.mk
@@ -6,7 +6,7 @@
 LOCAL_CFLAGS := -Wall -Werror -Wunused-parameter
 LOCAL_C_INCLUDES := external/libnl/include bionic/libc/dns/include
 LOCAL_STATIC_LIBRARIES := libnl
-LOCAL_SHARED_LIBRARIES := libcutils liblog
+LOCAL_SHARED_LIBRARIES := libcutils liblog libnetutils
 
 # The clat daemon.
 LOCAL_MODULE := clatd
@@ -30,7 +30,7 @@
 
 LOCAL_MODULE := clatd_test
 LOCAL_CFLAGS := -Wall -Werror -Wunused-parameter
-LOCAL_SRC_FILES := clatd_test.cpp dump.c checksum.c translate.c icmp.c ipv4.c ipv6.c logging.c tun.c
+LOCAL_SRC_FILES := clatd_test.cpp checksum.c translate.c icmp.c ipv4.c ipv6.c logging.c config.c tun.c
 LOCAL_MODULE_TAGS := eng tests
 LOCAL_SHARED_LIBRARIES := liblog
 
diff --git a/checksum.h b/checksum.h
index 6195810..d0af88e 100644
--- a/checksum.h
+++ b/checksum.h
@@ -18,6 +18,10 @@
 #ifndef __CHECKSUM_H__
 #define __CHECKSUM_H__
 
+#include <stdint.h>
+#include <netinet/ip.h>
+#include <netinet/ip6.h>
+
 uint32_t ip_checksum_add(uint32_t current, const void *data, int len);
 uint16_t ip_checksum_finish(uint32_t temp_sum);
 uint16_t ip_checksum(const void *data, int len);
diff --git a/clatd.c b/clatd.c
index 5cbcc1e..94cb3b5 100644
--- a/clatd.c
+++ b/clatd.c
@@ -53,7 +53,7 @@
 #include "tun.h"
 #include "ring.h"
 
-#define DEVICENAME4 "clat4"
+#define DEVICEPREFIX "v4-"
 
 /* 40 bytes IPv6 header - 20 bytes IPv4 header + 8 bytes fragment header */
 #define MTU_DELTA 28
@@ -114,42 +114,6 @@
   return 1;
 }
 
-/* function: interface_poll
- * polls the uplink network interface for address changes
- * tunnel - tun device data
- */
-void interface_poll(const struct tun_data *tunnel) {
-  union anyip *interface_ip;
-
-  interface_ip = getinterface_ip(Global_Clatd_Config.default_pdp_interface, AF_INET6);
-  if(!interface_ip) {
-    logmsg(ANDROID_LOG_WARN,"unable to find an ipv6 ip on interface %s",
-           Global_Clatd_Config.default_pdp_interface);
-    return;
-  }
-
-  config_generate_local_ipv6_subnet(&interface_ip->ip6);
-
-  if(!IN6_ARE_ADDR_EQUAL(&interface_ip->ip6, &Global_Clatd_Config.ipv6_local_subnet)) {
-    char from_addr[INET6_ADDRSTRLEN], to_addr[INET6_ADDRSTRLEN];
-    inet_ntop(AF_INET6, &Global_Clatd_Config.ipv6_local_subnet, from_addr, sizeof(from_addr));
-    inet_ntop(AF_INET6, &interface_ip->ip6, to_addr, sizeof(to_addr));
-    logmsg(ANDROID_LOG_WARN, "clat subnet changed from %s to %s", from_addr, to_addr);
-
-    // Start translating packets to the new prefix.
-    memcpy(&Global_Clatd_Config.ipv6_local_subnet, &interface_ip->ip6, sizeof(struct in6_addr));
-
-    // Update our packet socket filter to reflect the new 464xlat IP address.
-    if (!configure_packet_socket(tunnel->read_fd6)) {
-        // Things aren't going to work. Bail out and hope we have better luck next time.
-        // We don't log an error here because configure_packet_socket has already done so.
-        exit(1);
-    }
-  }
-
-  free(interface_ip);
-}
-
 /* function: configure_tun_ip
  * configures the ipv4 and ipv6 addresses on the tunnel interface
  * tunnel - tun device data
@@ -157,6 +121,22 @@
 void configure_tun_ip(const struct tun_data *tunnel) {
   int status;
 
+  // Pick an IPv4 address to use by finding a free address in the configured prefix. Technically,
+  // there is a race here - if another clatd calls config_select_ipv4_address after we do, but
+  // before we call add_address, it can end up having the same IP address as we do. But the time
+  // window in which this can happen is extremely small, and even if we end up with a duplicate
+  // address, the only damage is that IPv4 TCP connections won't be reset until both interfaces go
+  // down.
+  in_addr_t localaddr = config_select_ipv4_address(&Global_Clatd_Config.ipv4_local_subnet,
+                                                   Global_Clatd_Config.ipv4_local_prefixlen);
+  if (localaddr == INADDR_NONE) {
+    logmsg(ANDROID_LOG_FATAL,"No free IPv4 address in %s/%d",
+           inet_ntoa(Global_Clatd_Config.ipv4_local_subnet),
+           Global_Clatd_Config.ipv4_local_prefixlen);
+    exit(1);
+  }
+  Global_Clatd_Config.ipv4_local_subnet.s_addr = localaddr;
+
   // Configure the interface before bringing it up. As soon as we bring the interface up, the
   // framework will be notified and will assume the interface's configuration has been finalized.
   status = add_address(tunnel->device4, AF_INET, &Global_Clatd_Config.ipv4_local_subnet,
@@ -166,6 +146,10 @@
     exit(1);
   }
 
+  char addrstr[INET_ADDRSTRLEN];
+  inet_ntop(AF_INET, &Global_Clatd_Config.ipv4_local_subnet, addrstr, sizeof(addrstr));
+  logmsg(ANDROID_LOG_INFO, "Using IPv4 address %s on %s", addrstr, tunnel->device4);
+
   if((status = if_up(tunnel->device4, Global_Clatd_Config.ipv4mtu)) < 0) {
     logmsg(ANDROID_LOG_FATAL,"configure_tun_ip/if_up(4) failed: %s",strerror(-status));
     exit(1);
@@ -236,6 +220,60 @@
   }
 }
 
+/* function: update_clat_ipv6_address
+ * picks the clat IPv6 address and configures packet translation to use it.
+ * tunnel - tun device data
+ * interface - uplink interface name
+ * returns: 1 on success, 0 on failure
+ */
+int update_clat_ipv6_address(const struct tun_data *tunnel, const char *interface) {
+  union anyip *interface_ip;
+  char addrstr[INET6_ADDRSTRLEN];
+
+  // TODO: check that the prefix length is /64.
+  interface_ip = getinterface_ip(interface, AF_INET6);
+  if (!interface_ip) {
+    logmsg(ANDROID_LOG_ERROR, "Unable to find an IPv6 address on interface %s", interface);
+    return 0;
+  }
+
+  // If our prefix hasn't changed, do nothing. (If this is the first time we configure an IPv6
+  // address, Global_Clatd_Config.ipv6_local_subnet will be ::, which won't match our new prefix.)
+  if (ipv6_prefix_equal(&interface_ip->ip6, &Global_Clatd_Config.ipv6_local_subnet)) {
+    free(interface_ip);
+    return 1;
+  }
+
+  // Generate an interface ID.
+  config_generate_local_ipv6_subnet(&interface_ip->ip6);
+  inet_ntop(AF_INET6, &interface_ip->ip6, addrstr, sizeof(addrstr));
+
+  if (IN6_IS_ADDR_UNSPECIFIED(&Global_Clatd_Config.ipv6_local_subnet)) {
+    // Startup.
+    logmsg(ANDROID_LOG_INFO, "Using IPv6 address %s on %s", addrstr, interface);
+  } else {
+    // Prefix change.
+    char from_addr[INET6_ADDRSTRLEN];
+    inet_ntop(AF_INET6, &Global_Clatd_Config.ipv6_local_subnet, from_addr, sizeof(from_addr));
+    logmsg(ANDROID_LOG_INFO, "clat IPv6 address changed from %s to %s", from_addr, addrstr);
+    del_anycast_address(tunnel->write_fd6, &Global_Clatd_Config.ipv6_local_subnet);
+  }
+
+  // Start translating packets to the new prefix.
+  Global_Clatd_Config.ipv6_local_subnet = interface_ip->ip6;
+  add_anycast_address(tunnel->write_fd6, &Global_Clatd_Config.ipv6_local_subnet, interface);
+  free(interface_ip);
+
+  // Update our packet socket filter to reflect the new 464xlat IP address.
+  if (!configure_packet_socket(tunnel->read_fd6)) {
+      // Things aren't going to work. Bail out and hope we have better luck next time.
+      // We don't log an error here because configure_packet_socket has already done so.
+      exit(1);
+  }
+
+  return 1;
+}
+
 /* function: configure_interface
  * reads the configuration and applies it to the interface
  * uplink_interface - network interface to use to reach the ipv6 internet
@@ -356,7 +394,7 @@
 
     time_t now = time(NULL);
     if(last_interface_poll < (now - INTERFACE_POLL_FREQUENCY)) {
-      interface_poll(tunnel);
+      update_clat_ipv6_address(tunnel, Global_Clatd_Config.default_pdp_interface);
       last_interface_poll = now;
     }
   }
@@ -393,8 +431,7 @@
   char *uplink_interface = NULL, *plat_prefix = NULL, *net_id_str = NULL, *mark_str = NULL;
   unsigned net_id = NETID_UNSET;
   uint32_t mark = MARK_UNSET;
-
-  strcpy(tunnel.device4, DEVICENAME4);
+  unsigned len;
 
   while((opt = getopt(argc, argv, "i:p:n:m:h")) != -1) {
     switch(opt) {
@@ -434,6 +471,12 @@
     exit(1);
   }
 
+  len = snprintf(tunnel.device4, sizeof(tunnel.device4), "%s%s", DEVICEPREFIX, uplink_interface);
+  if (len >= sizeof(tunnel.device4)) {
+    logmsg(ANDROID_LOG_FATAL, "interface name too long '%s'", tunnel.device4);
+    exit(1);
+  }
+
   logmsg(ANDROID_LOG_INFO, "Starting clat version %s on %s netid=%s mark=%s",
          CLATD_VERSION, uplink_interface,
          net_id_str ? net_id_str : "(none)",
@@ -458,19 +501,18 @@
 
   configure_interface(uplink_interface, plat_prefix, &tunnel, net_id);
 
-  if (!configure_packet_socket(tunnel.read_fd6)) {
-    // We've already logged an error.
-    exit(1);
-  }
+  update_clat_ipv6_address(&tunnel, uplink_interface);
 
   // Loop until someone sends us a signal or brings down the tun interface.
   if(signal(SIGTERM, stop_loop) == SIG_ERR) {
     logmsg(ANDROID_LOG_FATAL, "sigterm handler failed: %s", strerror(errno));
     exit(1);
   }
+
   event_loop(&tunnel);
 
   logmsg(ANDROID_LOG_INFO,"Shutting down clat on %s", uplink_interface);
+  del_anycast_address(tunnel.write_fd6, &Global_Clatd_Config.ipv6_local_subnet);
 
   return 0;
 }
diff --git a/clatd.conf b/clatd.conf
index b17b862..ff80975 100644
--- a/clatd.conf
+++ b/clatd.conf
@@ -1,9 +1,16 @@
-# host ID to use as the source of CLAT traffic
-# this is a /128 taken out of the /64 routed to the phone
-ipv6_host_id ::464
+# Host IID to use as the source of CLAT traffic.
+# This is a /128 taken out of the /64 on the parent interface.
+# A host IID of :: means to generate a checksum-neutral, random IID.
+ipv6_host_id ::
 
-# ipv4 subnet for the local traffic to use.  This is a /32 host address
+# IPv4 address configuration to use when selecting a host address. The first
+# clat daemon started will use the address specified by ipv4_local_subnet. If
+# more than one daemon is run at the same time, subsequent daemons will use
+# other addresses in the prefix of length ipv4_local prefixlen that contains
+# ipv4_local_subnet. The default is to use the IANA-assigned range 192.0.0.0/29,
+# which allows up to 8 clat daemons (.4, .5, .6, .7, .0, .1, .2, .3).
 ipv4_local_subnet 192.0.0.4
+ipv4_local_prefixlen 29
 
 # get the plat_subnet from dns lookups (requires DNS64)
 plat_from_dns64 yes
diff --git a/clatd.h b/clatd.h
index ca7ad74..f421f46 100644
--- a/clatd.h
+++ b/clatd.h
@@ -22,7 +22,7 @@
 
 #define MAXMTU 1500
 #define PACKETLEN (MAXMTU+sizeof(struct tun_pi))
-#define CLATD_VERSION "1.3"
+#define CLATD_VERSION "1.4"
 
 #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
 
diff --git a/clatd_test.cpp b/clatd_test.cpp
index b61da9f..7e218f0 100644
--- a/clatd_test.cpp
+++ b/clatd_test.cpp
@@ -20,6 +20,7 @@
 
 #include <stdio.h>
 #include <arpa/inet.h>
+#include <netinet/in6.h>
 #include <sys/uio.h>
 
 #include <gtest/gtest.h>
@@ -370,7 +371,7 @@
   *reassembled_len = total_length;
 }
 
-void check_data_matches(const uint8_t *expected, const uint8_t *actual, size_t len, const char *msg) {
+void check_data_matches(const void *expected, const void *actual, size_t len, const char *msg) {
   if (memcmp(expected, actual, len)) {
     // Hex dump, 20 bytes per line, one space between bytes (1 byte = 3 chars), indented by 4.
     int hexdump_len = len * 3 + (len / 20 + 1) * 5;
@@ -382,11 +383,11 @@
         sprintf(actual_hexdump + pos, "\n   ");
         pos += 4;
       }
-      sprintf(expected_hexdump + pos, " %02x", expected[i]);
-      sprintf(actual_hexdump + pos, " %02x", actual[i]);
+      sprintf(expected_hexdump + pos, " %02x", ((uint8_t *) expected)[i]);
+      sprintf(actual_hexdump + pos, " %02x", ((uint8_t *) actual)[i]);
       pos += 3;
     }
-    FAIL() << msg << ": Translated packet doesn't match"
+    FAIL() << msg << ": Data doesn't match"
            << "\n  Expected:" << (char *) expected_hexdump
            << "\n  Actual:" << (char *) actual_hexdump << "\n";
   }
@@ -457,6 +458,7 @@
 
   translate_packet(write_fd, (version == 4), original, original_len);
 
+  snprintf(foo, sizeof(foo), "%s: Invalid translated packet", msg);
   if (version == 6) {
     // Translating to IPv4. Expect a tun header.
     struct tun_pi new_tun_header;
@@ -469,13 +471,15 @@
       ASSERT_LT((size_t) len, *outlen) << msg << ": Translated packet buffer too small\n";
       EXPECT_EQ(expected_proto, new_tun_header.proto) << msg << "Unexpected tun proto\n";
       *outlen = len - sizeof(new_tun_header);
+      check_packet(out, *outlen, msg);
     } else {
-      FAIL() << msg << ": Packet was not translated";
+      FAIL() << msg << ": Packet was not translated: len=" << len;
       *outlen = 0;
     }
   } else {
     // Translating to IPv6. Expect raw packet.
     *outlen = read(read_fd, out, *outlen);
+    check_packet(out, *outlen, msg);
   }
 }
 
@@ -511,6 +515,44 @@
   check_packet(translated, translated_len, msg);
 }
 
+int get_transport_checksum(const uint8_t *packet) {
+  struct iphdr *ip;
+  struct ip6_hdr *ip6;
+  uint8_t protocol;
+  const void *payload;
+
+  int version = ip_version(packet);
+  switch (version) {
+    case 4:
+      ip = (struct iphdr *) packet;
+      if (is_ipv4_fragment(ip)) {
+          return -1;
+      }
+      protocol = ip->protocol;
+      payload = ip + 1;
+      break;
+    case 6:
+      ip6 = (struct ip6_hdr *) packet;
+      protocol = ip6->ip6_nxt;
+      payload = ip6 + 1;
+      break;
+    default:
+      return -1;
+  }
+
+  switch (protocol) {
+    case IPPROTO_UDP:
+      return ((struct udphdr *) payload)->check;
+
+    case IPPROTO_TCP:
+      return ((struct tcphdr *) payload)->check;
+
+    case IPPROTO_FRAGMENT:
+    default:
+      return -1;
+  }
+}
+
 struct clat_config Global_Clatd_Config;
 
 class ClatdTest : public ::testing::Test {
@@ -519,10 +561,185 @@
     inet_pton(AF_INET, kIPv4LocalAddr, &Global_Clatd_Config.ipv4_local_subnet);
     inet_pton(AF_INET6, kIPv6PlatSubnet, &Global_Clatd_Config.plat_subnet);
     inet_pton(AF_INET6, kIPv6LocalAddr, &Global_Clatd_Config.ipv6_local_subnet);
+    Global_Clatd_Config.ipv6_host_id = in6addr_any;
+    Global_Clatd_Config.use_dynamic_iid = 1;
   }
 };
 
-TEST_F(ClatdTest, Sanitycheck) {
+void expect_ipv6_addr_equal(struct in6_addr *expected, struct in6_addr *actual) {
+  if (!IN6_ARE_ADDR_EQUAL(expected, actual)) {
+    char expected_str[INET6_ADDRSTRLEN], actual_str[INET6_ADDRSTRLEN];
+    inet_ntop(AF_INET6, expected, expected_str, sizeof(expected_str));
+    inet_ntop(AF_INET6, actual, actual_str, sizeof(actual_str));
+    FAIL()
+        << "Unexpected IPv6 address:: "
+        << "\n  Expected: " << expected_str
+        << "\n  Actual:   " << actual_str
+        << "\n";
+  }
+}
+
+TEST_F(ClatdTest, TestIPv6PrefixEqual) {
+  EXPECT_TRUE(ipv6_prefix_equal(&Global_Clatd_Config.plat_subnet,
+                                &Global_Clatd_Config.plat_subnet));
+  EXPECT_FALSE(ipv6_prefix_equal(&Global_Clatd_Config.plat_subnet,
+                                 &Global_Clatd_Config.ipv6_local_subnet));
+
+  struct in6_addr subnet2 = Global_Clatd_Config.ipv6_local_subnet;
+  EXPECT_TRUE(ipv6_prefix_equal(&Global_Clatd_Config.ipv6_local_subnet, &subnet2));
+  EXPECT_TRUE(ipv6_prefix_equal(&subnet2, &Global_Clatd_Config.ipv6_local_subnet));
+
+  subnet2.s6_addr[6] = 0xff;
+  EXPECT_FALSE(ipv6_prefix_equal(&Global_Clatd_Config.ipv6_local_subnet, &subnet2));
+  EXPECT_FALSE(ipv6_prefix_equal(&subnet2, &Global_Clatd_Config.ipv6_local_subnet));
+}
+
+int count_onebits(const void *data, size_t size) {
+  int onebits = 0;
+  for (size_t pos = 0; pos < size; pos++) {
+    uint8_t *byte = ((uint8_t*) data) + pos;
+    for (int shift = 0; shift < 8; shift++) {
+      onebits += (*byte >> shift) & 1;
+    }
+  }
+  return onebits;
+}
+
+TEST_F(ClatdTest, TestCountOnebits) {
+  uint64_t i;
+  i = 1;
+  ASSERT_EQ(1, count_onebits(&i, sizeof(i)));
+  i <<= 61;
+  ASSERT_EQ(1, count_onebits(&i, sizeof(i)));
+  i |= ((uint64_t) 1 << 33);
+  ASSERT_EQ(2, count_onebits(&i, sizeof(i)));
+  i = 0xf1000202020000f0;
+  ASSERT_EQ(5 + 1 + 1 + 1 + 4, count_onebits(&i, sizeof(i)));
+}
+
+TEST_F(ClatdTest, TestGenIIDConfigured) {
+  struct in6_addr myaddr, expected;
+  Global_Clatd_Config.use_dynamic_iid = 0;
+  ASSERT_TRUE(inet_pton(AF_INET6, "::bad:ace:d00d", &Global_Clatd_Config.ipv6_host_id));
+  ASSERT_TRUE(inet_pton(AF_INET6, "2001:db8:1:2:0:bad:ace:d00d", &expected));
+  ASSERT_TRUE(inet_pton(AF_INET6, "2001:db8:1:2:f076:ae99:124e:aa54", &myaddr));
+  config_generate_local_ipv6_subnet(&myaddr);
+  expect_ipv6_addr_equal(&expected, &myaddr);
+
+  Global_Clatd_Config.use_dynamic_iid = 1;
+  config_generate_local_ipv6_subnet(&myaddr);
+  EXPECT_FALSE(IN6_ARE_ADDR_EQUAL(&expected, &myaddr));
+}
+
+TEST_F(ClatdTest, TestGenIIDRandom) {
+  struct in6_addr interface_ipv6;
+  ASSERT_TRUE(inet_pton(AF_INET6, "2001:db8:1:2:f076:ae99:124e:aa54", &interface_ipv6));
+  Global_Clatd_Config.ipv6_host_id = in6addr_any;
+
+  // Generate a boatload of random IIDs.
+  int onebits = 0;
+  uint64_t prev_iid = 0;
+  for (int i = 0; i < 100000; i++) {
+    struct in6_addr myaddr =  interface_ipv6;
+
+    config_generate_local_ipv6_subnet(&myaddr);
+
+    // Check the generated IP address is in the same prefix as the interface IPv6 address.
+    EXPECT_TRUE(ipv6_prefix_equal(&interface_ipv6, &myaddr));
+
+    // Check that consecutive IIDs are not the same.
+    uint64_t iid = * (uint64_t*) (&myaddr.s6_addr[8]);
+    ASSERT_TRUE(iid != prev_iid)
+        << "Two consecutive random IIDs are the same: "
+        << std::showbase << std::hex
+        << iid << "\n";
+    prev_iid = iid;
+
+    // Check that the IID is checksum-neutral with the NAT64 prefix and the
+    // local prefix.
+    struct in_addr *ipv4addr = &Global_Clatd_Config.ipv4_local_subnet;
+    struct in6_addr *plat_subnet = &Global_Clatd_Config.plat_subnet;
+
+    uint16_t c1 = ip_checksum_finish(ip_checksum_add(0, ipv4addr, sizeof(*ipv4addr)));
+    uint16_t c2 = ip_checksum_finish(ip_checksum_add(0, plat_subnet, sizeof(*plat_subnet)) +
+                                     ip_checksum_add(0, &myaddr, sizeof(myaddr)));
+
+    if (c1 != c2) {
+      char myaddr_str[INET6_ADDRSTRLEN], plat_str[INET6_ADDRSTRLEN], ipv4_str[INET6_ADDRSTRLEN];
+      inet_ntop(AF_INET6, &myaddr, myaddr_str, sizeof(myaddr_str));
+      inet_ntop(AF_INET6, plat_subnet, plat_str, sizeof(plat_str));
+      inet_ntop(AF_INET, ipv4addr, ipv4_str, sizeof(ipv4_str));
+      FAIL()
+          << "Bad IID: " << myaddr_str
+          << " not checksum-neutral with " << ipv4_str << " and " << plat_str
+          << std::showbase << std::hex
+          << "\n  IPv4 checksum: " << c1
+          << "\n  IPv6 checksum: " << c2
+          << "\n";
+    }
+
+    // Check that IIDs are roughly random and use all the bits by counting the
+    // total number of bits set to 1 in a random sample of 100000 generated IIDs.
+    onebits += count_onebits(&iid, sizeof(iid));
+  }
+  EXPECT_LE(3190000, onebits);
+  EXPECT_GE(3210000, onebits);
+}
+
+extern "C" addr_free_func config_is_ipv4_address_free;
+int never_free(in_addr_t /* addr */) { return 0; }
+int always_free(in_addr_t /* addr */) { return 1; }
+int only2_free(in_addr_t addr) { return (ntohl(addr) & 0xff) == 2; }
+int over6_free(in_addr_t addr) { return (ntohl(addr) & 0xff) >= 6; }
+int only10_free(in_addr_t addr) { return (ntohl(addr) & 0xff) == 10; }
+
+TEST_F(ClatdTest, SelectIPv4Address) {
+  struct in_addr addr;
+
+  inet_pton(AF_INET, kIPv4LocalAddr, &addr);
+
+  addr_free_func orig_config_is_ipv4_address_free = config_is_ipv4_address_free;
+
+  // If no addresses are free, return INADDR_NONE.
+  config_is_ipv4_address_free = never_free;
+  EXPECT_EQ(INADDR_NONE, config_select_ipv4_address(&addr, 29));
+  EXPECT_EQ(INADDR_NONE, config_select_ipv4_address(&addr, 16));
+
+  // If the configured address is free, pick that. But a prefix that's too big is invalid.
+  config_is_ipv4_address_free = always_free;
+  EXPECT_EQ(inet_addr(kIPv4LocalAddr), config_select_ipv4_address(&addr, 29));
+  EXPECT_EQ(inet_addr(kIPv4LocalAddr), config_select_ipv4_address(&addr, 20));
+  EXPECT_EQ(INADDR_NONE, config_select_ipv4_address(&addr, 15));
+
+  // A prefix length of 32 works, but anything above it is invalid.
+  EXPECT_EQ(inet_addr(kIPv4LocalAddr), config_select_ipv4_address(&addr, 32));
+  EXPECT_EQ(INADDR_NONE, config_select_ipv4_address(&addr, 33));
+
+  // If another address is free, pick it.
+  config_is_ipv4_address_free = over6_free;
+  EXPECT_EQ(inet_addr("192.0.0.6"), config_select_ipv4_address(&addr, 29));
+
+  // Check that we wrap around to addresses that are lower than the first address.
+  config_is_ipv4_address_free = only2_free;
+  EXPECT_EQ(inet_addr("192.0.0.2"), config_select_ipv4_address(&addr, 29));
+  EXPECT_EQ(INADDR_NONE, config_select_ipv4_address(&addr, 30));
+
+  // If a free address exists outside the prefix, we don't pick it.
+  config_is_ipv4_address_free = only10_free;
+  EXPECT_EQ(INADDR_NONE, config_select_ipv4_address(&addr, 29));
+  EXPECT_EQ(inet_addr("192.0.0.10"), config_select_ipv4_address(&addr, 24));
+
+  // Now try using the real function which sees if IP addresses are free using bind().
+  // Assume that the machine running the test has the address 127.0.0.1, but not 8.8.8.8.
+  config_is_ipv4_address_free = orig_config_is_ipv4_address_free;
+  addr.s_addr = inet_addr("8.8.8.8");
+  EXPECT_EQ(inet_addr("8.8.8.8"), config_select_ipv4_address(&addr, 29));
+
+  addr.s_addr = inet_addr("127.0.0.1");
+  EXPECT_EQ(inet_addr("127.0.0.2"), config_select_ipv4_address(&addr, 29));
+}
+
+TEST_F(ClatdTest, DataSanitycheck) {
   // Sanity checks the data.
   uint8_t v4_header[] = { IPV4_UDP_HEADER };
   ASSERT_EQ(sizeof(struct iphdr), sizeof(v4_header)) << "Test IPv4 header: incorrect length\n";
@@ -677,3 +894,43 @@
                              kIPv4Fragments, kIPv4FragLengths,
                              ARRAYSIZE(kIPv6Fragments), "IPv6->IPv4 fragment translation");
 }
+
+void check_translate_checksum_neutral(const uint8_t *original, size_t original_len,
+                                      size_t expected_len, const char *msg) {
+  uint8_t translated[MAXMTU];
+  size_t translated_len = sizeof(translated);
+  do_translate_packet(original, original_len, translated, &translated_len, msg);
+  EXPECT_EQ(expected_len, translated_len) << msg << ": Translated packet length incorrect\n";
+  // do_translate_packet already checks packets for validity and verifies the checksum.
+  int original_check = get_transport_checksum(original);
+  int translated_check = get_transport_checksum(translated);
+  ASSERT_NE(-1, original_check);
+  ASSERT_NE(-1, translated_check);
+  ASSERT_EQ(original_check, translated_check)
+      << "Not checksum neutral: original and translated checksums differ\n";
+}
+
+TEST_F(ClatdTest, TranslateChecksumNeutral) {
+  // Generate a random clat IPv6 address and check that translation is checksum-neutral.
+  Global_Clatd_Config.ipv6_host_id = in6addr_any;
+  ASSERT_TRUE(inet_pton(AF_INET6, "2001:db8:1:2:f076:ae99:124e:aa54",
+                        &Global_Clatd_Config.ipv6_local_subnet));
+  config_generate_local_ipv6_subnet(&Global_Clatd_Config.ipv6_local_subnet);
+  ASSERT_NE((uint32_t) 0x00000464, Global_Clatd_Config.ipv6_local_subnet.s6_addr32[3]);
+  ASSERT_NE((uint32_t) 0, Global_Clatd_Config.ipv6_local_subnet.s6_addr32[3]);
+
+  // Check that translating UDP packets is checksum-neutral. First, IPv4.
+  uint8_t udp_ipv4[] = { IPV4_UDP_HEADER UDP_HEADER PAYLOAD };
+  fix_udp_checksum(udp_ipv4);
+  check_translate_checksum_neutral(udp_ipv4, sizeof(udp_ipv4), sizeof(udp_ipv4) + 20,
+                                   "UDP/IPv4 -> UDP/IPv6 checksum neutral");
+
+  // Now try IPv6.
+  uint8_t udp_ipv6[] = { IPV6_UDP_HEADER UDP_HEADER PAYLOAD };
+  // The test packet uses the static IID, not the random IID. Fix up the source address.
+  struct ip6_hdr *ip6 = (struct ip6_hdr *) udp_ipv6;
+  memcpy(&ip6->ip6_src, &Global_Clatd_Config.ipv6_local_subnet, sizeof(ip6->ip6_src));
+  fix_udp_checksum(udp_ipv6);
+  check_translate_checksum_neutral(udp_ipv4, sizeof(udp_ipv4), sizeof(udp_ipv4) + 20,
+                                   "UDP/IPv4 -> UDP/IPv6 checksum neutral");
+}
diff --git a/config.c b/config.c
index 623a1b0..b147868 100644
--- a/config.c
+++ b/config.c
@@ -25,12 +25,14 @@
 #include <unistd.h>
 
 #include <cutils/config_utils.h>
+#include <netutils/ifc.h>
 
 #include "config.h"
 #include "dns64.h"
 #include "logging.h"
 #include "getaddr.h"
 #include "clatd.h"
+#include "checksum.h"
 
 struct clat_config Global_Clatd_Config;
 
@@ -149,6 +151,16 @@
   }
 }
 
+/* function: ipv6_prefix_equal
+ * compares the prefixes two ipv6 addresses. assumes the prefix lengths are both /64.
+ * a1 - first address
+ * a2 - second address
+ * returns: 0 if the subnets are different, 1 if they are the same.
+ */
+int ipv6_prefix_equal(struct in6_addr *a1, struct in6_addr *a2) {
+    return !memcmp(a1, a2, 8);
+}
+
 /* function: dns64_detection
  * does dns lookups to set the plat subnet or exits on failure, waits forever for a dns response with a query backoff timer
  * net_id - (optional) netId to use, NETID_UNSET indicates use of default network
@@ -174,6 +186,88 @@
   }
 }
 
+/* function: gen_random_iid
+ * picks a random interface ID that is checksum neutral with the IPv4 address and the NAT64 prefix
+ * myaddr            - IPv6 address to write to
+ * ipv4_local_subnet - clat IPv4 address
+ * plat_subnet       - NAT64 prefix
+ */
+void gen_random_iid(struct in6_addr *myaddr, struct in_addr *ipv4_local_subnet,
+                    struct in6_addr *plat_subnet) {
+  // Fill last 8 bytes of IPv6 address with random bits.
+  arc4random_buf(&myaddr->s6_addr[8], 8);
+
+  // Make the IID checksum-neutral. That is, make it so that:
+  //   checksum(Local IPv4 | Remote IPv4) = checksum(Local IPv6 | Remote IPv6)
+  // in other words (because remote IPv6 = NAT64 prefix | Remote IPv4):
+  //   checksum(Local IPv4) = checksum(Local IPv6 | NAT64 prefix)
+  // Do this by adjusting the two bytes in the middle of the IID.
+
+  uint16_t middlebytes = (myaddr->s6_addr[11] << 8) + myaddr->s6_addr[12];
+
+  uint32_t c1 = ip_checksum_add(0, ipv4_local_subnet, sizeof(*ipv4_local_subnet));
+  uint32_t c2 = ip_checksum_add(0, plat_subnet, sizeof(*plat_subnet)) +
+                ip_checksum_add(0, myaddr, sizeof(*myaddr));
+
+  uint16_t delta = ip_checksum_adjust(middlebytes, c1, c2);
+  myaddr->s6_addr[11] = delta >> 8;
+  myaddr->s6_addr[12] = delta & 0xff;
+}
+
+// Factored out to a separate function for testability.
+int connect_is_ipv4_address_free(in_addr_t addr) {
+  int s = socket(AF_INET, SOCK_DGRAM, 0);
+  if (s == -1) {
+    return 0;
+  }
+
+  // Attempt to connect to the address. If the connection succeeds and getsockname returns the same
+  // the address then the address is already assigned to the system and we can't use it.
+  struct sockaddr_in sin = { .sin_family = AF_INET, .sin_addr = { addr }, .sin_port = 53 };
+  socklen_t len = sizeof(sin);
+  int inuse = connect(s, (struct sockaddr *) &sin, sizeof(sin)) == 0 &&
+              getsockname(s, (struct sockaddr *) &sin, &len) == 0 &&
+              (size_t) len >= sizeof(sin) &&
+              sin.sin_addr.s_addr == addr;
+
+  close(s);
+  return !inuse;
+}
+
+addr_free_func config_is_ipv4_address_free = connect_is_ipv4_address_free;
+
+/* function: config_select_ipv4_address
+ * picks a free IPv4 address, starting from ip and trying all addresses in the prefix in order
+ * ip        - the IP address from the configuration file
+ * prefixlen - the length of the prefix from which addresses may be selected.
+ * returns: the IPv4 address, or INADDR_NONE if no addresses were available
+ */
+in_addr_t config_select_ipv4_address(const struct in_addr *ip, int16_t prefixlen) {
+  in_addr_t chosen = INADDR_NONE;
+
+  // Don't accept prefixes that are too large because we scan addresses one by one.
+  if (prefixlen < 16 || prefixlen > 32) {
+      return chosen;
+  }
+
+  // All these are in host byte order.
+  in_addr_t mask = 0xffffffff >> (32 - prefixlen) << (32 - prefixlen);
+  in_addr_t ipv4 = ntohl(ip->s_addr);
+  in_addr_t first_ipv4 = ipv4;
+  in_addr_t prefix = ipv4 & mask;
+
+  // Pick the first IPv4 address in the pool, wrapping around if necessary.
+  // So, for example, 192.0.0.4 -> 192.0.0.5 -> 192.0.0.6 -> 192.0.0.7 -> 192.0.0.0.
+  do {
+     if (config_is_ipv4_address_free(htonl(ipv4))) {
+       chosen = htonl(ipv4);
+       break;
+     }
+     ipv4 = prefix | ((ipv4 + 1) & ~mask);
+  } while (ipv4 != first_ipv4);
+
+  return chosen;
+}
 
 /* function: config_generate_local_ipv6_subnet
  * generates the local ipv6 subnet when given the interface ip
@@ -183,36 +277,19 @@
 void config_generate_local_ipv6_subnet(struct in6_addr *interface_ip) {
   int i;
 
-  for(i = 2; i < 4; i++) {
-    interface_ip->s6_addr32[i] = Global_Clatd_Config.ipv6_host_id.s6_addr32[i];
+  if (Global_Clatd_Config.use_dynamic_iid) {
+    /* Generate a random interface ID. */
+    gen_random_iid(interface_ip,
+                   &Global_Clatd_Config.ipv4_local_subnet,
+                   &Global_Clatd_Config.plat_subnet);
+  } else {
+    /* Use the specified interface ID. */
+    for(i = 2; i < 4; i++) {
+      interface_ip->s6_addr32[i] = Global_Clatd_Config.ipv6_host_id.s6_addr32[i];
+    }
   }
 }
 
-/* function: subnet_from_interface
- * finds the ipv6 subnet configured on the specified interface
- * root      - parsed configuration
- * interface - network interface name
- */
-int subnet_from_interface(cnode *root, const char *interface) {
-  union anyip *interface_ip;
-
-  if(!config_item_ip6(root, "ipv6_host_id", "::464", &Global_Clatd_Config.ipv6_host_id))
-    return 0;
-
-  interface_ip = getinterface_ip(interface, AF_INET6);
-  if(!interface_ip) {
-    logmsg(ANDROID_LOG_FATAL,"unable to find an ipv6 ip on interface %s",interface);
-    return 0;
-  }
-
-  memcpy(&Global_Clatd_Config.ipv6_local_subnet, &interface_ip->ip6, sizeof(struct in6_addr));
-  free(interface_ip);
-
-  config_generate_local_ipv6_subnet(&Global_Clatd_Config.ipv6_local_subnet);
-
-  return 1;
-}
-
 /* function: read_config
  * reads the config file and parses it into the global variable Global_Clatd_Config. returns 0 on failure, 1 on success
  * file             - filename to parse
@@ -224,6 +301,7 @@
         unsigned net_id) {
   cnode *root = config_node("", "");
   void *tmp_ptr = NULL;
+  unsigned flags;
 
   if(!root) {
     logmsg(ANDROID_LOG_FATAL,"out of memory");
@@ -238,9 +316,8 @@
     goto failed;
   }
 
-  strncpy(Global_Clatd_Config.default_pdp_interface, uplink_interface, sizeof(Global_Clatd_Config.default_pdp_interface));
-
-  if(!subnet_from_interface(root,Global_Clatd_Config.default_pdp_interface))
+  Global_Clatd_Config.default_pdp_interface = strdup(uplink_interface);
+  if (!Global_Clatd_Config.default_pdp_interface)
     goto failed;
 
   if(!config_item_int16_t(root, "mtu", "-1", &Global_Clatd_Config.mtu))
@@ -249,7 +326,12 @@
   if(!config_item_int16_t(root, "ipv4mtu", "-1", &Global_Clatd_Config.ipv4mtu))
     goto failed;
 
-  if(!config_item_ip(root, "ipv4_local_subnet", DEFAULT_IPV4_LOCAL_SUBNET, &Global_Clatd_Config.ipv4_local_subnet))
+  if(!config_item_ip(root, "ipv4_local_subnet", DEFAULT_IPV4_LOCAL_SUBNET,
+                     &Global_Clatd_Config.ipv4_local_subnet))
+    goto failed;
+
+  if(!config_item_int16_t(root, "ipv4_local_prefixlen", DEFAULT_IPV4_LOCAL_PREFIXLEN,
+                          &Global_Clatd_Config.ipv4_local_prefixlen))
     goto failed;
 
   if(plat_prefix) { // plat subnet is coming from the command line
@@ -275,6 +357,19 @@
     }
   }
 
+  if (!config_item_ip6(root, "ipv6_host_id", "::", &Global_Clatd_Config.ipv6_host_id))
+    goto failed;
+
+  /* In order to prevent multiple devices attempting to use the same clat address, never use a
+     statically-configured interface ID on a broadcast interface such as wifi. */
+  if (!IN6_IS_ADDR_UNSPECIFIED(&Global_Clatd_Config.ipv6_host_id)) {
+    ifc_init();
+    ifc_get_info(Global_Clatd_Config.default_pdp_interface, NULL, NULL, &flags);
+    ifc_close();
+    Global_Clatd_Config.use_dynamic_iid = (flags & IFF_BROADCAST) != 0;
+  } else {
+    Global_Clatd_Config.use_dynamic_iid = 1;
+  }
 
   return 1;
 
@@ -294,6 +389,7 @@
   logmsg(ANDROID_LOG_DEBUG,"ipv4mtu = %d",Global_Clatd_Config.ipv4mtu);
   logmsg(ANDROID_LOG_DEBUG,"ipv6_local_subnet = %s",inet_ntop(AF_INET6, &Global_Clatd_Config.ipv6_local_subnet, charbuffer, sizeof(charbuffer)));
   logmsg(ANDROID_LOG_DEBUG,"ipv4_local_subnet = %s",inet_ntop(AF_INET, &Global_Clatd_Config.ipv4_local_subnet, charbuffer, sizeof(charbuffer)));
+  logmsg(ANDROID_LOG_DEBUG,"ipv4_local_prefixlen = %d", Global_Clatd_Config.ipv4_local_prefixlen);
   logmsg(ANDROID_LOG_DEBUG,"plat_subnet = %s",inet_ntop(AF_INET6, &Global_Clatd_Config.plat_subnet, charbuffer, sizeof(charbuffer)));
   logmsg(ANDROID_LOG_DEBUG,"default_pdp_interface = %s",Global_Clatd_Config.default_pdp_interface);
 }
diff --git a/config.h b/config.h
index da7446e..e31a81d 100644
--- a/config.h
+++ b/config.h
@@ -19,10 +19,10 @@
 #define __CONFIG_H__
 
 #include <netinet/in.h>
-#include <sys/system_properties.h>
+#include <linux/if.h>
 
 #define DEFAULT_IPV4_LOCAL_SUBNET "192.0.0.4"
-
+#define DEFAULT_IPV4_LOCAL_PREFIXLEN "29"
 #define DEFAULT_DNS64_DETECTION_HOSTNAME "ipv4only.arpa"
 
 struct clat_config {
@@ -30,9 +30,11 @@
   struct in6_addr ipv6_local_subnet;
   struct in6_addr ipv6_host_id;
   struct in_addr ipv4_local_subnet;
+  int16_t ipv4_local_prefixlen;
   struct in6_addr plat_subnet;
-  char default_pdp_interface[PROP_VALUE_MAX];
+  char *default_pdp_interface;
   char *plat_from_dns64_hostname;
+  int use_dynamic_iid;
 };
 
 extern struct clat_config Global_Clatd_Config;
@@ -40,5 +42,9 @@
 int read_config(const char *file, const char *uplink_interface, const char *plat_prefix,
         unsigned net_id);
 void config_generate_local_ipv6_subnet(struct in6_addr *interface_ip);
+in_addr_t config_select_ipv4_address(const struct in_addr *ip, int16_t prefixlen);
+int ipv6_prefix_equal(struct in6_addr *a1, struct in6_addr *a2);
+
+typedef int (*addr_free_func)(in_addr_t addr);
 
 #endif /* __CONFIG_H__ */
diff --git a/setif.c b/setif.c
index 5ee00bc..359ed24 100644
--- a/setif.c
+++ b/setif.c
@@ -23,8 +23,11 @@
 #include <netlink/handlers.h>
 #include <netlink/msg.h>
 
+#include "logging.h"
 #include "netlink_msg.h"
 
+#define DEBUG_OPTNAME(a) case (a): { optname = #a; break; }
+
 /* function: add_address
  * adds an IP address to/from an interface, returns 0 on success and <0 on failure
  * ifname    - name of interface to change
@@ -127,3 +130,51 @@
 
   return retval;
 }
+
+static int do_anycast_setsockopt(int sock, int what, struct in6_addr *addr, int ifindex) {
+  struct ipv6_mreq mreq = { *addr, ifindex };
+  char *optname;
+  int ret;
+
+  switch (what) {
+    DEBUG_OPTNAME(IPV6_JOIN_ANYCAST)
+    DEBUG_OPTNAME(IPV6_LEAVE_ANYCAST)
+    default:
+      optname = "???";
+      break;
+  }
+
+  ret = setsockopt(sock, SOL_IPV6, what, &mreq, sizeof(mreq));
+  if (ret) {
+    logmsg(ANDROID_LOG_ERROR, "%s: setsockopt(%s): %s", __func__, optname, strerror(errno));
+  }
+
+  return ret;
+}
+
+/* function: add_anycast_address
+ * adds an anycast IPv6 address to an interface, returns 0 on success and <0 on failure
+ * sock      - the socket to add the address to
+ * addr      - the IP address to add
+ * ifname    - name of interface to add the address to
+ */
+int add_anycast_address(int sock, struct in6_addr *addr, const char *ifname) {
+  int ifindex, s, ret;
+
+  ifindex = if_nametoindex(ifname);
+  if (!ifindex) {
+    logmsg(ANDROID_LOG_ERROR, "%s: unknown ifindex for interface %s", __func__, ifname);
+    return -ENODEV;
+  }
+
+  return do_anycast_setsockopt(sock, IPV6_JOIN_ANYCAST, addr, ifindex);
+}
+
+/* function: del_anycast_address
+ * removes an anycast IPv6 address from the system, returns 0 on success and <0 on failure
+ * sock      - the socket to remove from, must have had the address added via add_anycast_address
+ * addr      - the IP address to remove
+ */
+int del_anycast_address(int sock, struct in6_addr *addr) {
+  return do_anycast_setsockopt(sock, IPV6_LEAVE_ANYCAST, addr, 0);
+}
diff --git a/setif.h b/setif.h
index 7f83f73..d31eed5 100644
--- a/setif.h
+++ b/setif.h
@@ -21,4 +21,7 @@
 int add_address(const char *ifname, int family, const void *address, int cidr, const void *broadcast);
 int if_up(const char *ifname, int mtu);
 
+int add_anycast_address(int sock, const struct in6_addr *addr, const char *interface);
+int del_anycast_address(int sock, const struct in6_addr *addr);
+
 #endif