diff --git a/Tethering/src/com/android/networkstack/tethering/RequestTracker.java b/Tethering/src/com/android/networkstack/tethering/RequestTracker.java
index 37ad86a..9c61716 100644
--- a/Tethering/src/com/android/networkstack/tethering/RequestTracker.java
+++ b/Tethering/src/com/android/networkstack/tethering/RequestTracker.java
@@ -239,4 +239,21 @@
     public void removeAllServingRequests(final int type) {
         mServingRequests.entrySet().removeIf(e -> e.getValue().getTetheringType() == type);
     }
+
+    /**
+     * Returns an existing (pending or serving) request that fuzzy matches the given request.
+     * Optionally specify matchUid to only return requests with the same uid.
+     */
+    public TetheringRequest findFuzzyMatchedRequest(
+            @NonNull final TetheringRequest tetheringRequest, boolean matchUid) {
+        List<TetheringRequest> allRequests = new ArrayList<>();
+        allRequests.addAll(getPendingTetheringRequests());
+        allRequests.addAll(mServingRequests.values());
+        for (TetheringRequest request : allRequests) {
+            if (!request.fuzzyMatches(tetheringRequest)) continue;
+            if (matchUid && tetheringRequest.getUid() != request.getUid()) continue;
+            return request;
+        }
+        return null;
+    }
 }
diff --git a/Tethering/src/com/android/networkstack/tethering/Tethering.java b/Tethering/src/com/android/networkstack/tethering/Tethering.java
index 7b67095..59f05ed 100644
--- a/Tethering/src/com/android/networkstack/tethering/Tethering.java
+++ b/Tethering/src/com/android/networkstack/tethering/Tethering.java
@@ -737,26 +737,13 @@
         });
     }
 
-    private boolean isTetheringTypePendingOrServing(final int type) {
-        if (mRequestTracker.getNextPendingRequest(type) != null) return true;
-        for (TetherState state : mTetherStates.values()) {
-            // TODO: isCurrentlyServing only starts returning true once the IpServer has processed
-            // the CMD_TETHER_REQUESTED. Ensure that we consider the request to be serving even when
-            // that has not happened yet. This already works if the sync state machine is enabled
-            // (which includes all B+ devices).
-            if (state.isCurrentlyServing() && state.ipServer.interfaceType() == type) return true;
-        }
-        return false;
-    }
-
     void stopTetheringRequest(@NonNull final TetheringRequest request,
             @NonNull final IIntResultListener listener) {
         if (!isTetheringWithSoftApConfigEnabled()) return;
+        final boolean hasNetworkSettings = hasCallingPermission(NETWORK_SETTINGS);
         mHandler.post(() -> {
-            final int type = request.getTetheringType();
-            // TODO: when fuzzy-matching is enabled, check whether any pending request
-            // fuzzy-matches this request instead of just checking the type.
-            if (isTetheringTypePendingOrServing(type)) {
+            if (mRequestTracker.findFuzzyMatchedRequest(request, !hasNetworkSettings) != null) {
+                final int type = request.getTetheringType();
                 stopTetheringInternal(type);
                 // TODO: We should send the success result after the waiting for tethering to
                 //       actually stop.
diff --git a/Tethering/tests/unit/src/com/android/networkstack/tethering/TetheringTest.java b/Tethering/tests/unit/src/com/android/networkstack/tethering/TetheringTest.java
index 74bfec7..103d273 100644
--- a/Tethering/tests/unit/src/com/android/networkstack/tethering/TetheringTest.java
+++ b/Tethering/tests/unit/src/com/android/networkstack/tethering/TetheringTest.java
@@ -56,6 +56,7 @@
 import static android.net.TetheringManager.TETHER_ERROR_NO_ERROR;
 import static android.net.TetheringManager.TETHER_ERROR_SERVICE_UNAVAIL;
 import static android.net.TetheringManager.TETHER_ERROR_UNKNOWN_IFACE;
+import static android.net.TetheringManager.TETHER_ERROR_UNKNOWN_REQUEST;
 import static android.net.TetheringManager.TETHER_HARDWARE_OFFLOAD_FAILED;
 import static android.net.TetheringManager.TETHER_HARDWARE_OFFLOAD_STARTED;
 import static android.net.TetheringManager.TETHER_HARDWARE_OFFLOAD_STOPPED;
@@ -2780,6 +2781,85 @@
     }
 
     @Test
+    public void testStopTetheringWithMatchingRequest() throws Exception {
+        assumeTrue(isTetheringWithSoftApConfigEnabled());
+        when(mContext.checkCallingOrSelfPermission(NETWORK_SETTINGS)).thenReturn(PERMISSION_DENIED);
+        initTetheringOnTestThread();
+        UpstreamNetworkState upstreamState = buildMobileDualStackUpstreamState();
+        initTetheringUpstream(upstreamState);
+        when(mWifiManager.startTetheredHotspot(null)).thenReturn(true);
+
+        // Enable wifi tethering.
+        SoftApConfiguration softApConfig = new SoftApConfiguration.Builder()
+                .setSsid("SoftApConfig")
+                .build();
+        final TetheringRequest tetheringRequest = new TetheringRequest.Builder(TETHERING_WIFI)
+                .setSoftApConfiguration(softApConfig).build();
+        tetheringRequest.setUid(TEST_CALLER_UID);
+        mTethering.startTethering(tetheringRequest, TEST_CALLER_PKG, null);
+        mLooper.dispatchAll();
+
+        // Stop tethering with non-matching config. Should fail with TETHER_ERROR_UNKNOWN_REQUEST.
+        SoftApConfiguration softApConfig2 = new SoftApConfiguration.Builder()
+                .setSsid("SoftApConfig2")
+                .build();
+        IIntResultListener differentConfigListener = mock(IIntResultListener.class);
+        mTethering.stopTetheringRequest(new TetheringRequest.Builder(TETHERING_WIFI)
+                .setSoftApConfiguration(softApConfig2).build(), differentConfigListener);
+        mLooper.dispatchAll();
+        verify(differentConfigListener).onResult(eq(TETHER_ERROR_UNKNOWN_REQUEST));
+        verify(mWifiManager, never()).stopSoftAp();
+
+        // Stop tethering with non-matching UID. Should fail with TETHER_ERROR_UNKNOWN_REQUEST.
+        final TetheringRequest nonMatchingUid = new TetheringRequest.Builder(TETHERING_WIFI)
+                .setSoftApConfiguration(softApConfig).build();
+        IIntResultListener nonMatchingUidListener = mock(IIntResultListener.class);
+        nonMatchingUid.setUid(TEST_CALLER_UID_2);
+        mTethering.stopTetheringRequest(nonMatchingUid, nonMatchingUidListener);
+        mLooper.dispatchAll();
+        verify(nonMatchingUidListener).onResult(eq(TETHER_ERROR_UNKNOWN_REQUEST));
+        verify(mWifiManager, never()).stopSoftAp();
+
+        // Stop tethering with matching request. Should succeed now.
+        IIntResultListener matchingListener = mock(IIntResultListener.class);
+        mTethering.stopTetheringRequest(tetheringRequest, matchingListener);
+        mLooper.dispatchAll();
+        verify(matchingListener).onResult(eq(TETHER_ERROR_NO_ERROR));
+        verify(mWifiManager).stopSoftAp();
+    }
+
+    @Test
+    public void testStopTetheringWithSettingsPermission() throws Exception {
+        assumeTrue(isTetheringWithSoftApConfigEnabled());
+        initTetheringOnTestThread();
+        UpstreamNetworkState upstreamState = buildMobileDualStackUpstreamState();
+        initTetheringUpstream(upstreamState);
+        when(mWifiManager.startTetheredHotspot(null)).thenReturn(true);
+
+        // Enable wifi tethering.
+        SoftApConfiguration softApConfig = new SoftApConfiguration.Builder()
+                .setSsid("SoftApConfig")
+                .build();
+        final TetheringRequest tetheringRequest = new TetheringRequest.Builder(TETHERING_WIFI)
+                .setSoftApConfiguration(softApConfig).build();
+        tetheringRequest.setUid(TEST_CALLER_UID);
+        mTethering.startTethering(tetheringRequest, TEST_CALLER_PKG, null);
+        mLooper.dispatchAll();
+
+        // Stop tethering with non-matching UID and Settings permission. Should succeed.
+        final TetheringRequest nonMatchingUid = new TetheringRequest.Builder(TETHERING_WIFI)
+                .setSoftApConfiguration(softApConfig).build();
+        IIntResultListener nonMatchingUidListener = mock(IIntResultListener.class);
+        nonMatchingUid.setUid(TEST_CALLER_UID_2);
+        when(mContext.checkCallingOrSelfPermission(NETWORK_SETTINGS))
+                .thenReturn(PERMISSION_GRANTED);
+        mTethering.stopTetheringRequest(nonMatchingUid, nonMatchingUidListener);
+        mLooper.dispatchAll();
+        verify(nonMatchingUidListener).onResult(eq(TETHER_ERROR_NO_ERROR));
+        verify(mWifiManager).stopSoftAp();
+    }
+
+    @Test
     public void testReportFailCallbackIfOffloadNotSupported() throws Exception {
         initTetheringOnTestThread();
         final UpstreamNetworkState upstreamState = buildMobileDualStackUpstreamState();
diff --git a/tests/cts/tethering/src/android/tethering/cts/TetheringManagerTest.java b/tests/cts/tethering/src/android/tethering/cts/TetheringManagerTest.java
index 52799ab..ed6107b 100644
--- a/tests/cts/tethering/src/android/tethering/cts/TetheringManagerTest.java
+++ b/tests/cts/tethering/src/android/tethering/cts/TetheringManagerTest.java
@@ -483,25 +483,73 @@
     }
 
     @Test
-    public void testStopTetheringRequest() throws Exception {
+    public void testStopTetheringRequestNoMatchFailure() throws Exception {
+        assumeTrue(isTetheringWithSoftApConfigEnabled());
+        final TestTetheringEventCallback tetherEventCallback =
+                mCtsTetheringUtils.registerTetheringEventCallback();
+        try {
+            final StartTetheringCallback startTetheringCallback = new StartTetheringCallback();
+            mTM.startTethering(new TetheringRequest.Builder(TETHERING_VIRTUAL).build(),
+                    c -> c.run(), startTetheringCallback);
+
+            // Stopping a non-matching request should have no effect
+            TetheringRequest nonMatchingRequest = new TetheringRequest.Builder(TETHERING_VIRTUAL)
+                    .setInterfaceName("iface")
+                    .build();
+            mCtsTetheringUtils.stopTethering(nonMatchingRequest, false /* success */);
+        } finally {
+            mCtsTetheringUtils.unregisterTetheringEventCallback(tetherEventCallback);
+        }
+    }
+
+    @Test
+    public void testStopTetheringRequestMatchSuccess() throws Exception {
         assumeTrue(isTetheringWithSoftApConfigEnabled());
         final TestTetheringEventCallback tetherEventCallback =
                 mCtsTetheringUtils.registerTetheringEventCallback();
         try {
             tetherEventCallback.assumeWifiTetheringSupported(mContext);
 
-            // stopTethering without any tethering active should fail.
-            TetheringRequest request = new TetheringRequest.Builder(TETHERING_WIFI).build();
-            mCtsTetheringUtils.stopTethering(request, false /* expectSuccess */);
+            SoftApConfiguration softApConfig = new SoftApConfiguration.Builder()
+                    .setWifiSsid(WifiSsid.fromBytes("This is one config"
+                            .getBytes(StandardCharsets.UTF_8))).build();
+            mCtsTetheringUtils.startWifiTethering(tetherEventCallback, softApConfig);
 
-            // Start wifi tethering
-            mCtsTetheringUtils.startWifiTethering(tetherEventCallback);
-
-            // stopTethering should succeed now that there's a request.
-            mCtsTetheringUtils.stopTethering(request, true /* expectSuccess */);
+            // Stopping the active request should stop tethering.
+            TetheringRequest request = new TetheringRequest.Builder(TETHERING_WIFI)
+                    .setSoftApConfiguration(softApConfig)
+                    .build();
+            mCtsTetheringUtils.stopTethering(request, true /* success */);
             tetherEventCallback.expectNoTetheringActive();
         } finally {
-            mCtsTetheringUtils.stopAllTethering();
+            mCtsTetheringUtils.unregisterTetheringEventCallback(tetherEventCallback);
+        }
+    }
+
+    @Test
+    public void testStopTetheringRequestFuzzyMatchSuccess() throws Exception {
+        assumeTrue(isTetheringWithSoftApConfigEnabled());
+        final TestTetheringEventCallback tetherEventCallback =
+                mCtsTetheringUtils.registerTetheringEventCallback();
+        try {
+            tetherEventCallback.assumeWifiTetheringSupported(mContext);
+
+            SoftApConfiguration softApConfig = new SoftApConfiguration.Builder()
+                    .setWifiSsid(WifiSsid.fromBytes("This is one config"
+                            .getBytes(StandardCharsets.UTF_8))).build();
+            mCtsTetheringUtils.startWifiTethering(tetherEventCallback, softApConfig);
+
+            // Stopping with a fuzzy matching request should stop tethering.
+            final LinkAddress localAddr = new LinkAddress("192.168.24.5/24");
+            final LinkAddress clientAddr = new LinkAddress("192.168.24.100/24");
+            TetheringRequest fuzzyMatchingRequest = new TetheringRequest.Builder(TETHERING_WIFI)
+                    .setSoftApConfiguration(softApConfig)
+                    .setShouldShowEntitlementUi(true)
+                    .setStaticIpv4Addresses(localAddr, clientAddr)
+                    .build();
+            mCtsTetheringUtils.stopTethering(fuzzyMatchingRequest, true /* success */);
+            tetherEventCallback.expectNoTetheringActive();
+        } finally {
             mCtsTetheringUtils.unregisterTetheringEventCallback(tetherEventCallback);
         }
     }