diff --git a/Tethering/src/android/net/dhcp/DhcpServingParamsParcelExt.java b/Tethering/src/android/net/dhcp/DhcpServingParamsParcelExt.java
index 4f8ad8a..4710a30 100644
--- a/Tethering/src/android/net/dhcp/DhcpServingParamsParcelExt.java
+++ b/Tethering/src/android/net/dhcp/DhcpServingParamsParcelExt.java
@@ -173,6 +173,18 @@
         return this;
     }
 
+    /**
+     * Set whether the DHCP server should request a new prefix from IpServer when receiving
+     * DHCPDECLINE message in certain particular link (e.g. there is only one downstream USB
+     * tethering client). If it's false, process DHCPDECLINE message as RFC2131#4.3.3 suggests.
+     *
+     * <p>If not set, the default value is false.
+     */
+    public DhcpServingParamsParcelExt setChangePrefixOnDecline(boolean changePrefixOnDecline) {
+        this.changePrefixOnDecline = changePrefixOnDecline;
+        return this;
+    }
+
     private static int[] toIntArray(@NonNull Collection<Inet4Address> addrs) {
         int[] res = new int[addrs.size()];
         int i = 0;
diff --git a/Tethering/src/android/net/ip/IpServer.java b/Tethering/src/android/net/ip/IpServer.java
index d993306..de53787 100644
--- a/Tethering/src/android/net/ip/IpServer.java
+++ b/Tethering/src/android/net/ip/IpServer.java
@@ -50,6 +50,7 @@
 import android.net.shared.RouteUtils;
 import android.net.util.InterfaceParams;
 import android.net.util.InterfaceSet;
+import android.net.util.PrefixUtils;
 import android.net.util.SharedLog;
 import android.os.Handler;
 import android.os.Looper;
@@ -60,6 +61,7 @@
 import android.util.SparseArray;
 
 import androidx.annotation.NonNull;
+import androidx.annotation.Nullable;
 
 import com.android.internal.util.MessageUtils;
 import com.android.internal.util.State;
@@ -115,6 +117,15 @@
     private static final String ETHERNET_IFACE_ADDR = "192.168.50.1";
     private static final int ETHERNET_IFACE_PREFIX_LENGTH = 24;
 
+    // TODO: remove this constant after introducing PrivateAddressCoordinator.
+    private static final List<IpPrefix> NCM_PREFIXES = Collections.unmodifiableList(
+            Arrays.asList(
+                    new IpPrefix("192.168.42.0/24"),
+                    new IpPrefix("192.168.51.0/24"),
+                    new IpPrefix("192.168.52.0/24"),
+                    new IpPrefix("192.168.53.0/24")
+    ));
+
     // TODO: have PanService use some visible version of this constant
     private static final String BLUETOOTH_IFACE_ADDR = "192.168.44.1";
     private static final int BLUETOOTH_DHCP_PREFIX_LENGTH = 24;
@@ -212,6 +223,8 @@
     public static final int CMD_IPV6_TETHER_UPDATE          = BASE_IPSERVER + 10;
     // new neighbor cache entry on our interface
     public static final int CMD_NEIGHBOR_EVENT              = BASE_IPSERVER + 11;
+    // request from DHCP server that it wants to have a new prefix
+    public static final int CMD_NEW_PREFIX_REQUEST          = BASE_IPSERVER + 12;
 
     private final State mInitialState;
     private final State mLocalHotspotState;
@@ -462,7 +475,7 @@
                                 handleError();
                             }
                         }
-                    }, new DhcpLeaseCallback());
+                    }, new DhcpEventCallback());
                 } catch (RemoteException e) {
                     throw new IllegalStateException(e);
                 }
@@ -475,7 +488,7 @@
         }
     }
 
-    private class DhcpLeaseCallback extends IDhcpEventCallbacks.Stub {
+    private class DhcpEventCallback extends IDhcpEventCallbacks.Stub {
         @Override
         public void onLeasesChanged(List<DhcpLeaseParcelable> leaseParcelables) {
             final ArrayList<TetheredClient> leases = new ArrayList<>();
@@ -509,8 +522,9 @@
         }
 
         @Override
-        public void onNewPrefixRequest(IpPrefix currentPrefix) {
-            //TODO: add specific implementation.
+        public void onNewPrefixRequest(@NonNull final IpPrefix currentPrefix) {
+            Objects.requireNonNull(currentPrefix);
+            sendMessage(CMD_NEW_PREFIX_REQUEST, currentPrefix);
         }
 
         @Override
@@ -524,26 +538,38 @@
         }
     }
 
+    private RouteInfo getDirectConnectedRoute(@NonNull final LinkAddress ipv4Address) {
+        Objects.requireNonNull(ipv4Address);
+        return new RouteInfo(PrefixUtils.asIpPrefix(ipv4Address), null, mIfaceName, RTN_UNICAST);
+    }
+
+    private DhcpServingParamsParcel makeServingParams(@NonNull final Inet4Address defaultRouter,
+            @NonNull final Inet4Address dnsServer, @NonNull LinkAddress serverAddr,
+            @Nullable Inet4Address clientAddr) {
+        final boolean changePrefixOnDecline =
+                (mInterfaceType == TetheringManager.TETHERING_NCM && clientAddr == null);
+        return new DhcpServingParamsParcelExt()
+            .setDefaultRouters(defaultRouter)
+            .setDhcpLeaseTimeSecs(DHCP_LEASE_TIME_SECS)
+            .setDnsServers(dnsServer)
+            .setServerAddr(serverAddr)
+            .setMetered(true)
+            .setSingleClientAddr(clientAddr)
+            .setChangePrefixOnDecline(changePrefixOnDecline);
+            // TODO: also advertise link MTU
+    }
+
     private boolean startDhcp(final LinkAddress serverLinkAddr, final LinkAddress clientLinkAddr) {
         if (mUsingLegacyDhcp) {
             return true;
         }
 
         final Inet4Address addr = (Inet4Address) serverLinkAddr.getAddress();
-        final int prefixLen = serverLinkAddr.getPrefixLength();
         final Inet4Address clientAddr = clientLinkAddr == null ? null :
                 (Inet4Address) clientLinkAddr.getAddress();
 
-        final DhcpServingParamsParcel params;
-        params = new DhcpServingParamsParcelExt()
-                .setDefaultRouters(addr)
-                .setDhcpLeaseTimeSecs(DHCP_LEASE_TIME_SECS)
-                .setDnsServers(addr)
-                .setServerAddr(serverLinkAddr)
-                .setMetered(true)
-                .setSingleClientAddr(clientAddr);
-        // TODO: also advertise link MTU
-
+        final DhcpServingParamsParcel params = makeServingParams(addr /* defaultRouter */,
+                addr /* dnsServer */, serverLinkAddr, clientAddr);
         mDhcpServerStartIndex++;
         mDeps.makeDhcpServer(
                 mIfaceName, params, new DhcpServerCallbacksImpl(mDhcpServerStartIndex));
@@ -570,7 +596,7 @@
                 });
                 mDhcpServer = null;
             } catch (RemoteException e) {
-                mLog.e("Error stopping DHCP", e);
+                mLog.e("Error stopping DHCP server", e);
                 // Not much more we can do here
             }
         }
@@ -652,31 +678,33 @@
             return false;
         }
 
-        // Directly-connected route.
-        final IpPrefix ipv4Prefix = new IpPrefix(mIpv4Address.getAddress(),
-                mIpv4Address.getPrefixLength());
-        final RouteInfo route = new RouteInfo(ipv4Prefix, null, null, RTN_UNICAST);
         if (enabled) {
             mLinkProperties.addLinkAddress(mIpv4Address);
-            mLinkProperties.addRoute(route);
+            mLinkProperties.addRoute(getDirectConnectedRoute(mIpv4Address));
         } else {
             mLinkProperties.removeLinkAddress(mIpv4Address);
-            mLinkProperties.removeRoute(route);
+            mLinkProperties.removeRoute(getDirectConnectedRoute(mIpv4Address));
         }
-
         return configureDhcp(enabled, mIpv4Address, mStaticIpv4ClientAddr);
     }
 
-    private String getRandomWifiIPv4Address() {
+    private Inet4Address getRandomIPv4Address(@NonNull final byte[] rawAddr) {
+        final byte[] ipv4Addr = rawAddr;
+        ipv4Addr[3] = getRandomSanitizedByte(DOUG_ADAMS, asByte(0), asByte(1), FF);
         try {
-            byte[] bytes = parseNumericAddress(WIFI_HOST_IFACE_ADDR).getAddress();
-            bytes[3] = getRandomSanitizedByte(DOUG_ADAMS, asByte(0), asByte(1), FF);
-            return InetAddress.getByAddress(bytes).getHostAddress();
-        } catch (Exception e) {
-            return WIFI_HOST_IFACE_ADDR;
+            return (Inet4Address) InetAddress.getByAddress(ipv4Addr);
+        } catch (UnknownHostException e) {
+            mLog.e("Failed to construct Inet4Address from raw IPv4 addr");
+            return null;
         }
     }
 
+    private String getRandomWifiIPv4Address() {
+        final Inet4Address ipv4Addr =
+                getRandomIPv4Address(parseNumericAddress(WIFI_HOST_IFACE_ADDR).getAddress());
+        return ipv4Addr != null ? ipv4Addr.getHostAddress() : WIFI_HOST_IFACE_ADDR;
+    }
+
     private boolean startIPv6() {
         mInterfaceParams = mDeps.getInterfaceParams(mIfaceName);
         if (mInterfaceParams == null) {
@@ -761,21 +789,43 @@
         mLastIPv6UpstreamIfindex = upstreamIfindex;
     }
 
+    private void removeRoutesFromLocalNetwork(@NonNull final List<RouteInfo> toBeRemoved) {
+        final int removalFailures = RouteUtils.removeRoutesFromLocalNetwork(
+                mNetd, toBeRemoved);
+        if (removalFailures > 0) {
+            mLog.e(String.format("Failed to remove %d IPv6 routes from local table.",
+                    removalFailures));
+        }
+
+        for (RouteInfo route : toBeRemoved) mLinkProperties.removeRoute(route);
+    }
+
+    private void addRoutesToLocalNetwork(@NonNull final List<RouteInfo> toBeAdded) {
+        try {
+            // It's safe to call networkAddInterface() even if
+            // the interface is already in the local_network.
+            mNetd.networkAddInterface(INetd.LOCAL_NET_ID, mIfaceName);
+            try {
+                // Add routes from local network. Note that adding routes that
+                // already exist does not cause an error (EEXIST is silently ignored).
+                RouteUtils.addRoutesToLocalNetwork(mNetd, mIfaceName, toBeAdded);
+            } catch (IllegalStateException e) {
+                mLog.e("Failed to add IPv4/v6 routes to local table: " + e);
+                return;
+            }
+        } catch (ServiceSpecificException | RemoteException e) {
+            mLog.e("Failed to add " + mIfaceName + " to local table: ", e);
+            return;
+        }
+
+        for (RouteInfo route : toBeAdded) mLinkProperties.addRoute(route);
+    }
+
     private void configureLocalIPv6Routes(
             HashSet<IpPrefix> deprecatedPrefixes, HashSet<IpPrefix> newPrefixes) {
         // [1] Remove the routes that are deprecated.
         if (!deprecatedPrefixes.isEmpty()) {
-            final ArrayList<RouteInfo> toBeRemoved =
-                    getLocalRoutesFor(mIfaceName, deprecatedPrefixes);
-            // Remove routes from local network.
-            final int removalFailures = RouteUtils.removeRoutesFromLocalNetwork(
-                    mNetd, toBeRemoved);
-            if (removalFailures > 0) {
-                mLog.e(String.format("Failed to remove %d IPv6 routes from local table.",
-                        removalFailures));
-            }
-
-            for (RouteInfo route : toBeRemoved) mLinkProperties.removeRoute(route);
+            removeRoutesFromLocalNetwork(getLocalRoutesFor(mIfaceName, deprecatedPrefixes));
         }
 
         // [2] Add only the routes that have not previously been added.
@@ -786,24 +836,7 @@
             }
 
             if (!addedPrefixes.isEmpty()) {
-                final ArrayList<RouteInfo> toBeAdded =
-                        getLocalRoutesFor(mIfaceName, addedPrefixes);
-                try {
-                    // It's safe to call networkAddInterface() even if
-                    // the interface is already in the local_network.
-                    mNetd.networkAddInterface(INetd.LOCAL_NET_ID, mIfaceName);
-                    try {
-                        // Add routes from local network. Note that adding routes that
-                        // already exist does not cause an error (EEXIST is silently ignored).
-                        RouteUtils.addRoutesToLocalNetwork(mNetd, mIfaceName, toBeAdded);
-                    } catch (IllegalStateException e) {
-                        mLog.e("Failed to add IPv6 routes to local table: " + e);
-                    }
-                } catch (ServiceSpecificException | RemoteException e) {
-                    mLog.e("Failed to add " + mIfaceName + " to local table: ", e);
-                }
-
-                for (RouteInfo route : toBeAdded) mLinkProperties.addRoute(route);
+                addRoutesToLocalNetwork(getLocalRoutesFor(mIfaceName, addedPrefixes));
             }
         }
     }
@@ -945,6 +978,80 @@
         }
     }
 
+    // TODO: call PrivateAddressCoordinator.requestDownstreamAddress instead of this temporary
+    // logic.
+    private Inet4Address requestDownstreamAddress(@NonNull final IpPrefix currentPrefix) {
+        final int oldIndex = NCM_PREFIXES.indexOf(currentPrefix);
+        if (oldIndex == -1) {
+            mLog.e("current prefix isn't supported for NCM link: " + currentPrefix);
+            return null;
+        }
+
+        final IpPrefix newPrefix = NCM_PREFIXES.get((oldIndex + 1) % NCM_PREFIXES.size());
+        return getRandomIPv4Address(newPrefix.getRawAddress());
+    }
+
+    private void handleNewPrefixRequest(@NonNull final IpPrefix currentPrefix) {
+        if (!currentPrefix.contains(mIpv4Address.getAddress())
+                || currentPrefix.getPrefixLength() != mIpv4Address.getPrefixLength()) {
+            Log.e(TAG, "Invalid prefix: " + currentPrefix);
+            return;
+        }
+
+        final LinkAddress deprecatedLinkAddress = mIpv4Address;
+        final Inet4Address srvAddr = requestDownstreamAddress(currentPrefix);
+        if (srvAddr == null) {
+            mLog.e("Fail to request a new downstream prefix");
+            return;
+        }
+        mIpv4Address = new LinkAddress(srvAddr, currentPrefix.getPrefixLength());
+
+        // Add new IPv4 address on the interface.
+        if (!mInterfaceCtrl.addAddress(srvAddr, currentPrefix.getPrefixLength())) {
+            mLog.e("Failed to add new IP " + srvAddr);
+            return;
+        }
+
+        // Remove deprecated routes from local network.
+        removeRoutesFromLocalNetwork(
+                Collections.singletonList(getDirectConnectedRoute(deprecatedLinkAddress)));
+        mLinkProperties.removeLinkAddress(deprecatedLinkAddress);
+
+        // Add new routes to local network.
+        addRoutesToLocalNetwork(
+                Collections.singletonList(getDirectConnectedRoute(mIpv4Address)));
+        mLinkProperties.addLinkAddress(mIpv4Address);
+
+        // Update local DNS caching server with new IPv4 address, otherwise, dnsmasq doesn't
+        // listen on the interface configured with new IPv4 address, that results DNS validation
+        // failure of downstream client even if appropriate routes have been configured.
+        try {
+            mNetd.tetherApplyDnsInterfaces();
+        } catch (ServiceSpecificException | RemoteException e) {
+            mLog.e("Failed to update local DNS caching server");
+            return;
+        }
+        sendLinkProperties();
+
+        // Notify DHCP server that new prefix/route has been applied on IpServer.
+        final Inet4Address clientAddr = mStaticIpv4ClientAddr == null ? null :
+                (Inet4Address) mStaticIpv4ClientAddr.getAddress();
+        final DhcpServingParamsParcel params = makeServingParams(srvAddr /* defaultRouter */,
+                srvAddr /* dnsServer */, mIpv4Address /* serverLinkAddress */, clientAddr);
+        try {
+            mDhcpServer.updateParams(params, new OnHandlerStatusCallback() {
+                    @Override
+                    public void callback(int statusCode) {
+                        if (statusCode != STATUS_SUCCESS) {
+                            mLog.e("Error updating DHCP serving params: " + statusCode);
+                        }
+                    }
+            });
+        } catch (RemoteException e) {
+            mLog.e("Error updating DHCP serving params", e);
+        }
+    }
+
     private byte getHopLimit(String upstreamIface) {
         try {
             int upstreamHopLimit = Integer.parseUnsignedInt(
@@ -1056,11 +1163,9 @@
             }
 
             try {
-                final IpPrefix ipv4Prefix = new IpPrefix(mIpv4Address.getAddress(),
-                        mIpv4Address.getPrefixLength());
-                NetdUtils.tetherInterface(mNetd, mIfaceName, ipv4Prefix);
+                NetdUtils.tetherInterface(mNetd, mIfaceName, PrefixUtils.asIpPrefix(mIpv4Address));
             } catch (RemoteException | ServiceSpecificException | IllegalStateException e) {
-                mLog.e("Error Tethering: " + e);
+                mLog.e("Error Tethering", e);
                 mLastError = TetheringManager.TETHER_ERROR_TETHER_IFACE_ERROR;
                 return;
             }
@@ -1115,6 +1220,9 @@
                     mLastError = TetheringManager.TETHER_ERROR_INTERNAL_ERROR;
                     transitionTo(mInitialState);
                     break;
+                case CMD_NEW_PREFIX_REQUEST:
+                    handleNewPrefixRequest((IpPrefix) message.obj);
+                    break;
                 default:
                     return false;
             }
diff --git a/Tethering/src/com/android/networkstack/tethering/TetheringService.java b/Tethering/src/com/android/networkstack/tethering/TetheringService.java
index bf7fb04..e095afe 100644
--- a/Tethering/src/com/android/networkstack/tethering/TetheringService.java
+++ b/Tethering/src/com/android/networkstack/tethering/TetheringService.java
@@ -254,8 +254,8 @@
             // If callerPkg's uid is not same as Binder.getCallingUid(),
             // checkAndNoteWriteSettingsOperation will return false and the operation will be
             // denied.
-            return Settings.checkAndNoteWriteSettingsOperation(mService, uid, callerPkg,
-                false /* throwException */);
+            return mService.checkAndNoteWriteSettingsOperation(mService, uid, callerPkg,
+                    false /* throwException */);
         }
 
         private boolean hasTetherAccessPermission() {
@@ -267,6 +267,19 @@
     }
 
     /**
+     * Check if the package is a allowed to write settings. This also accounts that such an access
+     * happened.
+     *
+     * @return {@code true} iff the package is allowed to write settings.
+     */
+    @VisibleForTesting
+    boolean checkAndNoteWriteSettingsOperation(@NonNull Context context, int uid,
+            @NonNull String callingPackage, boolean throwException) {
+        return Settings.checkAndNoteWriteSettingsOperation(context, uid, callingPackage,
+                throwException);
+    }
+
+    /**
      * An injection method for testing.
      */
     @VisibleForTesting
diff --git a/Tethering/tests/unit/AndroidManifest.xml b/Tethering/tests/unit/AndroidManifest.xml
index 31eaabf..355342f 100644
--- a/Tethering/tests/unit/AndroidManifest.xml
+++ b/Tethering/tests/unit/AndroidManifest.xml
@@ -16,9 +16,6 @@
 <manifest xmlns:android="http://schemas.android.com/apk/res/android"
           package="com.android.networkstack.tethering.tests.unit">
 
-    <uses-permission android:name="android.permission.READ_PHONE_STATE"/>
-    <uses-permission android:name="android.permission.TETHER_PRIVILEGED"/>
-
     <application android:debuggable="true">
         <uses-library android:name="android.test.runner" />
         <service
diff --git a/Tethering/tests/unit/src/android/net/ip/IpServerTest.java b/Tethering/tests/unit/src/android/net/ip/IpServerTest.java
index b9622da..cd1ff60 100644
--- a/Tethering/tests/unit/src/android/net/ip/IpServerTest.java
+++ b/Tethering/tests/unit/src/android/net/ip/IpServerTest.java
@@ -18,6 +18,7 @@
 
 import static android.net.INetd.IF_STATE_UP;
 import static android.net.TetheringManager.TETHERING_BLUETOOTH;
+import static android.net.TetheringManager.TETHERING_NCM;
 import static android.net.TetheringManager.TETHERING_USB;
 import static android.net.TetheringManager.TETHERING_WIFI;
 import static android.net.TetheringManager.TETHERING_WIFI_P2P;
@@ -38,6 +39,7 @@
 
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotEquals;
 import static org.junit.Assert.assertNotNull;
 import static org.junit.Assert.assertTrue;
 import static org.junit.Assert.fail;
@@ -67,6 +69,7 @@
 import android.net.RouteInfo;
 import android.net.TetherOffloadRuleParcel;
 import android.net.dhcp.DhcpServingParamsParcel;
+import android.net.dhcp.IDhcpEventCallbacks;
 import android.net.dhcp.IDhcpServer;
 import android.net.dhcp.IDhcpServerCallbacks;
 import android.net.ip.IpNeighborMonitor.NeighborEvent;
@@ -94,6 +97,7 @@
 import java.net.Inet4Address;
 import java.net.InetAddress;
 import java.util.Arrays;
+import java.util.List;
 
 @RunWith(AndroidJUnit4.class)
 @SmallTest
@@ -497,6 +501,59 @@
     }
 
     @Test
+    public void startsDhcpServerOnNcm() throws Exception {
+        initStateMachine(TETHERING_NCM);
+        dispatchCommand(IpServer.CMD_TETHER_REQUESTED, STATE_LOCAL_ONLY);
+        dispatchTetherConnectionChanged(UPSTREAM_IFACE);
+
+        assertDhcpStarted(new IpPrefix("192.168.42.0/24"));
+    }
+
+    @Test
+    public void testOnNewPrefixRequest() throws Exception {
+        initStateMachine(TETHERING_NCM);
+        dispatchCommand(IpServer.CMD_TETHER_REQUESTED, STATE_LOCAL_ONLY);
+
+        final IDhcpEventCallbacks eventCallbacks;
+        final ArgumentCaptor<IDhcpEventCallbacks> dhcpEventCbsCaptor =
+                 ArgumentCaptor.forClass(IDhcpEventCallbacks.class);
+        verify(mDhcpServer, timeout(MAKE_DHCPSERVER_TIMEOUT_MS).times(1)).startWithCallbacks(
+                any(), dhcpEventCbsCaptor.capture());
+        eventCallbacks = dhcpEventCbsCaptor.getValue();
+        assertDhcpStarted(new IpPrefix("192.168.42.0/24"));
+
+        // Simulate the DHCP server receives DHCPDECLINE on MirrorLink and then signals
+        // onNewPrefixRequest callback.
+        eventCallbacks.onNewPrefixRequest(new IpPrefix("192.168.42.0/24"));
+        mLooper.dispatchAll();
+
+        final ArgumentCaptor<LinkProperties> lpCaptor =
+                ArgumentCaptor.forClass(LinkProperties.class);
+        InOrder inOrder = inOrder(mNetd, mCallback);
+        inOrder.verify(mCallback).updateInterfaceState(
+                mIpServer, STATE_LOCAL_ONLY, TETHER_ERROR_NO_ERROR);
+        inOrder.verify(mCallback).updateLinkProperties(eq(mIpServer), lpCaptor.capture());
+        inOrder.verify(mNetd).networkAddInterface(INetd.LOCAL_NET_ID, IFACE_NAME);
+        // One for ipv4 route, one for ipv6 link local route.
+        inOrder.verify(mNetd, times(2)).networkAddRoute(eq(INetd.LOCAL_NET_ID), eq(IFACE_NAME),
+                any(), any());
+        inOrder.verify(mNetd).tetherApplyDnsInterfaces();
+        inOrder.verify(mCallback).updateLinkProperties(eq(mIpServer), lpCaptor.capture());
+        verifyNoMoreInteractions(mCallback);
+
+        final LinkProperties linkProperties = lpCaptor.getValue();
+        final List<LinkAddress> linkAddresses = linkProperties.getLinkAddresses();
+        assertEquals(1, linkProperties.getLinkAddresses().size());
+        assertEquals(1, linkProperties.getRoutes().size());
+        final IpPrefix prefix = new IpPrefix(linkAddresses.get(0).getAddress(),
+                linkAddresses.get(0).getPrefixLength());
+        assertNotEquals(prefix, new IpPrefix("192.168.42.0/24"));
+
+        verify(mDhcpServer).updateParams(mDhcpParamsCaptor.capture(), any());
+        assertDhcpServingParams(mDhcpParamsCaptor.getValue(), prefix);
+    }
+
+    @Test
     public void doesNotStartDhcpServerIfDisabled() throws Exception {
         initTetheredStateMachine(TETHERING_WIFI, UPSTREAM_IFACE, true /* usingLegacyDhcp */,
                 DEFAULT_USING_BPF_OFFLOAD);
@@ -731,19 +788,26 @@
         verify(mIpNeighborMonitor, never()).start();
     }
 
-    private void assertDhcpStarted(IpPrefix expectedPrefix) throws Exception {
-        verify(mDependencies, times(1)).makeDhcpServer(eq(IFACE_NAME), any(), any());
-        verify(mDhcpServer, timeout(MAKE_DHCPSERVER_TIMEOUT_MS).times(1)).startWithCallbacks(
-                any(), any());
-        final DhcpServingParamsParcel params = mDhcpParamsCaptor.getValue();
+    private void assertDhcpServingParams(final DhcpServingParamsParcel params,
+            final IpPrefix prefix) {
         // Last address byte is random
-        assertTrue(expectedPrefix.contains(intToInet4AddressHTH(params.serverAddr)));
-        assertEquals(expectedPrefix.getPrefixLength(), params.serverAddrPrefixLength);
+        assertTrue(prefix.contains(intToInet4AddressHTH(params.serverAddr)));
+        assertEquals(prefix.getPrefixLength(), params.serverAddrPrefixLength);
         assertEquals(1, params.defaultRouters.length);
         assertEquals(params.serverAddr, params.defaultRouters[0]);
         assertEquals(1, params.dnsServers.length);
         assertEquals(params.serverAddr, params.dnsServers[0]);
         assertEquals(DHCP_LEASE_TIME_SECS, params.dhcpLeaseTimeSecs);
+        if (mIpServer.interfaceType() == TETHERING_NCM) {
+            assertTrue(params.changePrefixOnDecline);
+        }
+    }
+
+    private void assertDhcpStarted(IpPrefix expectedPrefix) throws Exception {
+        verify(mDependencies, times(1)).makeDhcpServer(eq(IFACE_NAME), any(), any());
+        verify(mDhcpServer, timeout(MAKE_DHCPSERVER_TIMEOUT_MS).times(1)).startWithCallbacks(
+                any(), any());
+        assertDhcpServingParams(mDhcpParamsCaptor.getValue(), expectedPrefix);
     }
 
     /**
diff --git a/Tethering/tests/unit/src/com/android/networkstack/tethering/MockTetheringService.java b/Tethering/tests/unit/src/com/android/networkstack/tethering/MockTetheringService.java
index 1c81c12..f4d2489 100644
--- a/Tethering/tests/unit/src/com/android/networkstack/tethering/MockTetheringService.java
+++ b/Tethering/tests/unit/src/com/android/networkstack/tethering/MockTetheringService.java
@@ -15,13 +15,19 @@
  */
 package com.android.networkstack.tethering;
 
+import static android.Manifest.permission.WRITE_SETTINGS;
+import static android.content.pm.PackageManager.PERMISSION_GRANTED;
+
 import static org.mockito.Mockito.mock;
 
+import android.content.Context;
 import android.content.Intent;
 import android.net.ITetheringConnector;
 import android.os.Binder;
 import android.os.IBinder;
 
+import androidx.annotation.NonNull;
+
 public class MockTetheringService extends TetheringService {
     private final Tethering mTethering = mock(Tethering.class);
 
@@ -35,6 +41,14 @@
         return mTethering;
     }
 
+    @Override
+    boolean checkAndNoteWriteSettingsOperation(@NonNull Context context, int uid,
+            @NonNull String callingPackage, boolean throwException) {
+        // Test this does not verify the calling package / UID, as calling package could be shell
+        // and not match the UID.
+        return context.checkCallingOrSelfPermission(WRITE_SETTINGS) == PERMISSION_GRANTED;
+    }
+
     public Tethering getTethering() {
         return mTethering;
     }
diff --git a/Tethering/tests/unit/src/com/android/networkstack/tethering/TetheringServiceTest.java b/Tethering/tests/unit/src/com/android/networkstack/tethering/TetheringServiceTest.java
index 4a667b1..f4a5666 100644
--- a/Tethering/tests/unit/src/com/android/networkstack/tethering/TetheringServiceTest.java
+++ b/Tethering/tests/unit/src/com/android/networkstack/tethering/TetheringServiceTest.java
@@ -16,20 +16,30 @@
 
 package com.android.networkstack.tethering;
 
+import static android.Manifest.permission.ACCESS_NETWORK_STATE;
+import static android.Manifest.permission.TETHER_PRIVILEGED;
+import static android.Manifest.permission.UPDATE_APP_OPS_STATS;
+import static android.Manifest.permission.WRITE_SETTINGS;
 import static android.net.TetheringManager.TETHERING_WIFI;
+import static android.net.TetheringManager.TETHER_ERROR_NO_ACCESS_TETHERING_PERMISSION;
+import static android.net.TetheringManager.TETHER_ERROR_NO_CHANGE_TETHERING_PERMISSION;
 import static android.net.TetheringManager.TETHER_ERROR_NO_ERROR;
 
 import static org.junit.Assert.assertEquals;
 import static org.mockito.ArgumentMatchers.eq;
+import static org.mockito.Mockito.reset;
 import static org.mockito.Mockito.verify;
 import static org.mockito.Mockito.verifyNoMoreInteractions;
 import static org.mockito.Mockito.when;
 
+import android.app.UiAutomation;
 import android.content.Intent;
 import android.net.IIntResultListener;
 import android.net.ITetheringConnector;
 import android.net.ITetheringEventCallback;
 import android.net.TetheringRequestParcel;
+import android.os.Bundle;
+import android.os.Handler;
 import android.os.ResultReceiver;
 
 import androidx.test.InstrumentationRegistry;
@@ -51,12 +61,13 @@
 @SmallTest
 public final class TetheringServiceTest {
     private static final String TEST_IFACE_NAME = "test_wlan0";
-    private static final String TEST_CALLER_PKG = "test_pkg";
+    private static final String TEST_CALLER_PKG = "com.android.shell";
     @Mock private ITetheringEventCallback mITetheringEventCallback;
     @Rule public ServiceTestRule mServiceTestRule;
     private Tethering mTethering;
     private Intent mMockServiceIntent;
     private ITetheringConnector mTetheringConnector;
+    private UiAutomation mUiAutomation;
 
     private class TestTetheringResult extends IIntResultListener.Stub {
         private int mResult = -1; // Default value that does not match any result code.
@@ -70,9 +81,26 @@
         }
     }
 
+    private class MyResultReceiver extends ResultReceiver {
+        MyResultReceiver(Handler handler) {
+            super(handler);
+        }
+        private int mResult = -1; // Default value that does not match any result code.
+        @Override
+        protected void onReceiveResult(int resultCode, Bundle resultData) {
+            mResult = resultCode;
+        }
+
+        public void assertResult(int expected) {
+            assertEquals(expected, mResult);
+        }
+    }
+
     @Before
     public void setUp() throws Exception {
         MockitoAnnotations.initMocks(this);
+        mUiAutomation =
+            InstrumentationRegistry.getInstrumentation().getUiAutomation();
         mServiceTestRule = new ServiceTestRule();
         mMockServiceIntent = new Intent(
                 InstrumentationRegistry.getTargetContext(),
@@ -82,112 +110,353 @@
         mTetheringConnector = mockConnector.getTetheringConnector();
         final MockTetheringService service = mockConnector.getService();
         mTethering = service.getTethering();
-        when(mTethering.isTetheringSupported()).thenReturn(true);
     }
 
     @After
     public void tearDown() throws Exception {
         mServiceTestRule.unbindService();
+        mUiAutomation.dropShellPermissionIdentity();
+    }
+
+    private interface TestTetheringCall {
+        void runTetheringCall(TestTetheringResult result) throws Exception;
+    }
+
+    private void runAsNoPermission(final TestTetheringCall test) throws Exception {
+        runTetheringCall(test, new String[0]);
+    }
+
+    private void runAsTetherPrivileged(final TestTetheringCall test) throws Exception {
+        runTetheringCall(test, TETHER_PRIVILEGED);
+    }
+
+    private void runAsAccessNetworkState(final TestTetheringCall test) throws Exception {
+        runTetheringCall(test, ACCESS_NETWORK_STATE);
+    }
+
+    private void runAsWriteSettings(final TestTetheringCall test) throws Exception {
+        runTetheringCall(test, WRITE_SETTINGS, UPDATE_APP_OPS_STATS);
+    }
+
+    private void runTetheringCall(final TestTetheringCall test, String... permissions)
+            throws Exception {
+        if (permissions.length > 0) mUiAutomation.adoptShellPermissionIdentity(permissions);
+        try {
+            when(mTethering.isTetheringSupported()).thenReturn(true);
+            test.runTetheringCall(new TestTetheringResult());
+        } finally {
+            mUiAutomation.dropShellPermissionIdentity();
+        }
+    }
+
+    private void verifyNoMoreInteractionsForTethering() {
+        verifyNoMoreInteractions(mTethering);
+        verifyNoMoreInteractions(mITetheringEventCallback);
+        reset(mTethering, mITetheringEventCallback);
+    }
+
+    private void runTether(final TestTetheringResult result) throws Exception {
+        when(mTethering.tether(TEST_IFACE_NAME)).thenReturn(TETHER_ERROR_NO_ERROR);
+        mTetheringConnector.tether(TEST_IFACE_NAME, TEST_CALLER_PKG, result);
+        verify(mTethering).isTetheringSupported();
+        verify(mTethering).tether(TEST_IFACE_NAME);
+        result.assertResult(TETHER_ERROR_NO_ERROR);
     }
 
     @Test
     public void testTether() throws Exception {
-        when(mTethering.tether(TEST_IFACE_NAME)).thenReturn(TETHER_ERROR_NO_ERROR);
-        final TestTetheringResult result = new TestTetheringResult();
-        mTetheringConnector.tether(TEST_IFACE_NAME, TEST_CALLER_PKG, result);
+        runAsNoPermission((result) -> {
+            mTetheringConnector.tether(TEST_IFACE_NAME, TEST_CALLER_PKG, result);
+            verify(mTethering).isTetherProvisioningRequired();
+            result.assertResult(TETHER_ERROR_NO_CHANGE_TETHERING_PERMISSION);
+            verifyNoMoreInteractionsForTethering();
+        });
+
+        runAsTetherPrivileged((result) -> {
+            runTether(result);
+            verifyNoMoreInteractionsForTethering();
+        });
+
+        runAsWriteSettings((result) -> {
+            runTether(result);
+            verify(mTethering).isTetherProvisioningRequired();
+            verifyNoMoreInteractionsForTethering();
+        });
+    }
+
+    private void runUnTether(final TestTetheringResult result) throws Exception {
+        when(mTethering.untether(TEST_IFACE_NAME)).thenReturn(TETHER_ERROR_NO_ERROR);
+        mTetheringConnector.untether(TEST_IFACE_NAME, TEST_CALLER_PKG, result);
         verify(mTethering).isTetheringSupported();
-        verify(mTethering).tether(TEST_IFACE_NAME);
-        verifyNoMoreInteractions(mTethering);
+        verify(mTethering).untether(TEST_IFACE_NAME);
         result.assertResult(TETHER_ERROR_NO_ERROR);
     }
 
     @Test
     public void testUntether() throws Exception {
-        when(mTethering.untether(TEST_IFACE_NAME)).thenReturn(TETHER_ERROR_NO_ERROR);
-        final TestTetheringResult result = new TestTetheringResult();
-        mTetheringConnector.untether(TEST_IFACE_NAME, TEST_CALLER_PKG, result);
+        runAsNoPermission((result) -> {
+            mTetheringConnector.untether(TEST_IFACE_NAME, TEST_CALLER_PKG, result);
+            verify(mTethering).isTetherProvisioningRequired();
+            result.assertResult(TETHER_ERROR_NO_CHANGE_TETHERING_PERMISSION);
+            verifyNoMoreInteractionsForTethering();
+        });
+
+        runAsTetherPrivileged((result) -> {
+            runUnTether(result);
+            verifyNoMoreInteractionsForTethering();
+        });
+
+        runAsWriteSettings((result) -> {
+            runUnTether(result);
+            verify(mTethering).isTetherProvisioningRequired();
+            verifyNoMoreInteractionsForTethering();
+        });
+    }
+
+    private void runSetUsbTethering(final TestTetheringResult result) throws Exception {
+        when(mTethering.setUsbTethering(true /* enable */)).thenReturn(TETHER_ERROR_NO_ERROR);
+        mTetheringConnector.setUsbTethering(true /* enable */, TEST_CALLER_PKG, result);
         verify(mTethering).isTetheringSupported();
-        verify(mTethering).untether(TEST_IFACE_NAME);
-        verifyNoMoreInteractions(mTethering);
+        verify(mTethering).setUsbTethering(true /* enable */);
         result.assertResult(TETHER_ERROR_NO_ERROR);
     }
 
     @Test
     public void testSetUsbTethering() throws Exception {
-        when(mTethering.setUsbTethering(true /* enable */)).thenReturn(TETHER_ERROR_NO_ERROR);
-        final TestTetheringResult result = new TestTetheringResult();
-        mTetheringConnector.setUsbTethering(true /* enable */, TEST_CALLER_PKG, result);
+        runAsNoPermission((result) -> {
+            mTetheringConnector.setUsbTethering(true /* enable */, TEST_CALLER_PKG, result);
+            verify(mTethering).isTetherProvisioningRequired();
+            result.assertResult(TETHER_ERROR_NO_CHANGE_TETHERING_PERMISSION);
+            verifyNoMoreInteractionsForTethering();
+        });
+
+        runAsTetherPrivileged((result) -> {
+            runSetUsbTethering(result);
+            verifyNoMoreInteractionsForTethering();
+        });
+
+        runAsWriteSettings((result) -> {
+            runSetUsbTethering(result);
+            verify(mTethering).isTetherProvisioningRequired();
+            verifyNoMoreInteractionsForTethering();
+        });
+
+    }
+
+    private void runStartTethering(final TestTetheringResult result,
+            final TetheringRequestParcel request) throws Exception {
+        mTetheringConnector.startTethering(request, TEST_CALLER_PKG, result);
         verify(mTethering).isTetheringSupported();
-        verify(mTethering).setUsbTethering(true /* enable */);
-        verifyNoMoreInteractions(mTethering);
-        result.assertResult(TETHER_ERROR_NO_ERROR);
+        verify(mTethering).startTethering(eq(request), eq(result));
     }
 
     @Test
     public void testStartTethering() throws Exception {
-        final TestTetheringResult result = new TestTetheringResult();
         final TetheringRequestParcel request = new TetheringRequestParcel();
         request.tetheringType = TETHERING_WIFI;
-        mTetheringConnector.startTethering(request, TEST_CALLER_PKG, result);
-        verify(mTethering).isTetheringSupported();
-        verify(mTethering).startTethering(eq(request), eq(result));
-        verifyNoMoreInteractions(mTethering);
+
+        runAsNoPermission((result) -> {
+            mTetheringConnector.startTethering(request, TEST_CALLER_PKG, result);
+            verify(mTethering).isTetherProvisioningRequired();
+            result.assertResult(TETHER_ERROR_NO_CHANGE_TETHERING_PERMISSION);
+            verifyNoMoreInteractionsForTethering();
+        });
+
+        runAsTetherPrivileged((result) -> {
+            runStartTethering(result, request);
+            verifyNoMoreInteractionsForTethering();
+        });
+
+        runAsWriteSettings((result) -> {
+            runStartTethering(result, request);
+            verify(mTethering).isTetherProvisioningRequired();
+            verifyNoMoreInteractionsForTethering();
+        });
     }
 
     @Test
-    public void testStopTethering() throws Exception {
-        final TestTetheringResult result = new TestTetheringResult();
+    public void testStartTetheringWithExemptFromEntitlementCheck() throws Exception {
+        final TetheringRequestParcel request = new TetheringRequestParcel();
+        request.tetheringType = TETHERING_WIFI;
+        request.exemptFromEntitlementCheck = true;
+
+        runAsTetherPrivileged((result) -> {
+            runStartTethering(result, request);
+            verifyNoMoreInteractionsForTethering();
+        });
+
+        runAsWriteSettings((result) -> {
+            mTetheringConnector.startTethering(request, TEST_CALLER_PKG, result);
+            result.assertResult(TETHER_ERROR_NO_CHANGE_TETHERING_PERMISSION);
+            verifyNoMoreInteractionsForTethering();
+        });
+    }
+
+    private void runStopTethering(final TestTetheringResult result) throws Exception {
         mTetheringConnector.stopTethering(TETHERING_WIFI, TEST_CALLER_PKG, result);
         verify(mTethering).isTetheringSupported();
         verify(mTethering).stopTethering(TETHERING_WIFI);
-        verifyNoMoreInteractions(mTethering);
         result.assertResult(TETHER_ERROR_NO_ERROR);
     }
 
     @Test
-    public void testRequestLatestTetheringEntitlementResult() throws Exception {
-        final ResultReceiver result = new ResultReceiver(null);
+    public void testStopTethering() throws Exception {
+        runAsNoPermission((result) -> {
+            mTetheringConnector.stopTethering(TETHERING_WIFI, TEST_CALLER_PKG, result);
+            verify(mTethering).isTetherProvisioningRequired();
+            result.assertResult(TETHER_ERROR_NO_CHANGE_TETHERING_PERMISSION);
+            verifyNoMoreInteractionsForTethering();
+        });
+
+        runAsTetherPrivileged((result) -> {
+            runStopTethering(result);
+            verifyNoMoreInteractionsForTethering();
+        });
+
+        runAsWriteSettings((result) -> {
+            runStopTethering(result);
+            verify(mTethering).isTetherProvisioningRequired();
+            verifyNoMoreInteractionsForTethering();
+        });
+    }
+
+    private void runRequestLatestTetheringEntitlementResult() throws Exception {
+        final MyResultReceiver result = new MyResultReceiver(null);
         mTetheringConnector.requestLatestTetheringEntitlementResult(TETHERING_WIFI, result,
                 true /* showEntitlementUi */, TEST_CALLER_PKG);
         verify(mTethering).isTetheringSupported();
         verify(mTethering).requestLatestTetheringEntitlementResult(eq(TETHERING_WIFI),
                 eq(result), eq(true) /* showEntitlementUi */);
+    }
+
+    @Test
+    public void testRequestLatestTetheringEntitlementResult() throws Exception {
+        // Run as no permission.
+        final MyResultReceiver result = new MyResultReceiver(null);
+        mTetheringConnector.requestLatestTetheringEntitlementResult(TETHERING_WIFI, result,
+                true /* showEntitlementUi */, TEST_CALLER_PKG);
+        verify(mTethering).isTetherProvisioningRequired();
+        result.assertResult(TETHER_ERROR_NO_CHANGE_TETHERING_PERMISSION);
         verifyNoMoreInteractions(mTethering);
+
+        runAsTetherPrivileged((none) -> {
+            runRequestLatestTetheringEntitlementResult();
+            verifyNoMoreInteractionsForTethering();
+        });
+
+        runAsWriteSettings((none) -> {
+            runRequestLatestTetheringEntitlementResult();
+            verify(mTethering).isTetherProvisioningRequired();
+            verifyNoMoreInteractionsForTethering();
+        });
+    }
+
+    private void runRegisterTetheringEventCallback() throws Exception {
+        mTetheringConnector.registerTetheringEventCallback(mITetheringEventCallback,
+                TEST_CALLER_PKG);
+        verify(mTethering).registerTetheringEventCallback(eq(mITetheringEventCallback));
     }
 
     @Test
     public void testRegisterTetheringEventCallback() throws Exception {
-        mTetheringConnector.registerTetheringEventCallback(mITetheringEventCallback,
+        runAsNoPermission((result) -> {
+            mTetheringConnector.registerTetheringEventCallback(mITetheringEventCallback,
+                    TEST_CALLER_PKG);
+            verify(mITetheringEventCallback).onCallbackStopped(
+                    TETHER_ERROR_NO_ACCESS_TETHERING_PERMISSION);
+            verifyNoMoreInteractionsForTethering();
+        });
+
+        runAsTetherPrivileged((none) -> {
+            runRegisterTetheringEventCallback();
+            verifyNoMoreInteractionsForTethering();
+        });
+
+        runAsAccessNetworkState((none) -> {
+            runRegisterTetheringEventCallback();
+            verifyNoMoreInteractionsForTethering();
+        });
+    }
+
+    private void runUnregisterTetheringEventCallback() throws Exception {
+        mTetheringConnector.unregisterTetheringEventCallback(mITetheringEventCallback,
                 TEST_CALLER_PKG);
-        verify(mTethering).registerTetheringEventCallback(eq(mITetheringEventCallback));
-        verifyNoMoreInteractions(mTethering);
+        verify(mTethering).unregisterTetheringEventCallback(eq(mITetheringEventCallback));
     }
 
     @Test
     public void testUnregisterTetheringEventCallback() throws Exception {
-        mTetheringConnector.unregisterTetheringEventCallback(mITetheringEventCallback,
-                TEST_CALLER_PKG);
-        verify(mTethering).unregisterTetheringEventCallback(
-                eq(mITetheringEventCallback));
-        verifyNoMoreInteractions(mTethering);
+        runAsNoPermission((result) -> {
+            mTetheringConnector.unregisterTetheringEventCallback(mITetheringEventCallback,
+                    TEST_CALLER_PKG);
+            verify(mITetheringEventCallback).onCallbackStopped(
+                    TETHER_ERROR_NO_ACCESS_TETHERING_PERMISSION);
+            verifyNoMoreInteractionsForTethering();
+        });
+
+        runAsTetherPrivileged((none) -> {
+            runUnregisterTetheringEventCallback();
+            verifyNoMoreInteractionsForTethering();
+        });
+
+        runAsAccessNetworkState((none) -> {
+            runUnregisterTetheringEventCallback();
+            verifyNoMoreInteractionsForTethering();
+        });
+    }
+
+    private void runStopAllTethering(final TestTetheringResult result) throws Exception {
+        mTetheringConnector.stopAllTethering(TEST_CALLER_PKG, result);
+        verify(mTethering).isTetheringSupported();
+        verify(mTethering).untetherAll();
+        result.assertResult(TETHER_ERROR_NO_ERROR);
     }
 
     @Test
     public void testStopAllTethering() throws Exception {
-        final TestTetheringResult result = new TestTetheringResult();
-        mTetheringConnector.stopAllTethering(TEST_CALLER_PKG, result);
+        runAsNoPermission((result) -> {
+            mTetheringConnector.stopAllTethering(TEST_CALLER_PKG, result);
+            verify(mTethering).isTetherProvisioningRequired();
+            result.assertResult(TETHER_ERROR_NO_CHANGE_TETHERING_PERMISSION);
+            verifyNoMoreInteractionsForTethering();
+        });
+
+        runAsTetherPrivileged((result) -> {
+            runStopAllTethering(result);
+            verifyNoMoreInteractionsForTethering();
+        });
+
+        runAsWriteSettings((result) -> {
+            runStopAllTethering(result);
+            verify(mTethering).isTetherProvisioningRequired();
+            verifyNoMoreInteractionsForTethering();
+        });
+    }
+
+    private void runIsTetheringSupported(final TestTetheringResult result) throws Exception {
+        mTetheringConnector.isTetheringSupported(TEST_CALLER_PKG, result);
         verify(mTethering).isTetheringSupported();
-        verify(mTethering).untetherAll();
-        verifyNoMoreInteractions(mTethering);
         result.assertResult(TETHER_ERROR_NO_ERROR);
     }
 
     @Test
     public void testIsTetheringSupported() throws Exception {
-        final TestTetheringResult result = new TestTetheringResult();
-        mTetheringConnector.isTetheringSupported(TEST_CALLER_PKG, result);
-        verify(mTethering).isTetheringSupported();
-        verifyNoMoreInteractions(mTethering);
-        result.assertResult(TETHER_ERROR_NO_ERROR);
+        runAsNoPermission((result) -> {
+            mTetheringConnector.isTetheringSupported(TEST_CALLER_PKG, result);
+            verify(mTethering).isTetherProvisioningRequired();
+            result.assertResult(TETHER_ERROR_NO_CHANGE_TETHERING_PERMISSION);
+            verifyNoMoreInteractionsForTethering();
+        });
+
+        runAsTetherPrivileged((result) -> {
+            runIsTetheringSupported(result);
+            verifyNoMoreInteractionsForTethering();
+        });
+
+        runAsWriteSettings((result) -> {
+            runIsTetheringSupported(result);
+            verify(mTethering).isTetherProvisioningRequired();
+            verifyNoMoreInteractionsForTethering();
+        });
     }
 }