diff --git a/tests/unit/Android.bp b/tests/unit/Android.bp
index 3ea27f7..a05ca92 100644
--- a/tests/unit/Android.bp
+++ b/tests/unit/Android.bp
@@ -63,6 +63,7 @@
         "java/com/android/internal/net/NetworkUtilsInternalTest.java",
         "java/com/android/internal/net/VpnProfileTest.java",
         "java/com/android/server/NetworkManagementServiceTest.java",
+        "java/com/android/server/VpnManagerServiceTest.java",
         "java/com/android/server/connectivity/IpConnectivityEventBuilderTest.java",
         "java/com/android/server/connectivity/IpConnectivityMetricsTest.java",
         "java/com/android/server/connectivity/MultipathPolicyTrackerTest.java",
diff --git a/tests/unit/java/com/android/server/VpnManagerServiceTest.java b/tests/unit/java/com/android/server/VpnManagerServiceTest.java
new file mode 100644
index 0000000..1f238bb
--- /dev/null
+++ b/tests/unit/java/com/android/server/VpnManagerServiceTest.java
@@ -0,0 +1,149 @@
+/*
+ * Copyright (C) 2022 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server;
+
+import static android.os.Build.VERSION_CODES.R;
+
+import static com.android.testutils.ContextUtils.mockService;
+import static com.android.testutils.DevSdkIgnoreRule.IgnoreUpTo;
+
+import static org.junit.Assert.assertNotNull;
+import static org.mockito.ArgumentMatchers.any;
+import static org.mockito.ArgumentMatchers.anyInt;
+import static org.mockito.ArgumentMatchers.eq;
+import static org.mockito.Mockito.doReturn;
+import static org.mockito.Mockito.never;
+import static org.mockito.Mockito.times;
+import static org.mockito.Mockito.verify;
+
+import android.annotation.UserIdInt;
+import android.content.Context;
+import android.content.Intent;
+import android.content.pm.PackageManager;
+import android.net.ConnectivityManager;
+import android.net.INetd;
+import android.os.Handler;
+import android.os.HandlerThread;
+import android.os.INetworkManagementService;
+import android.os.Looper;
+import android.os.UserManager;
+
+import androidx.test.filters.SmallTest;
+
+import com.android.server.connectivity.Vpn;
+import com.android.testutils.DevSdkIgnoreRule;
+import com.android.testutils.DevSdkIgnoreRunner;
+
+import org.junit.Before;
+import org.junit.Rule;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.mockito.Mock;
+import org.mockito.MockitoAnnotations;
+import org.mockito.Spy;
+
+@RunWith(DevSdkIgnoreRunner.class)
+@IgnoreUpTo(R) // VpnManagerService is not available before R
+@SmallTest
+public class VpnManagerServiceTest extends VpnTestBase {
+    @Rule
+    public final DevSdkIgnoreRule mIgnoreRule = new DevSdkIgnoreRule();
+
+    @Spy Context mContext;
+    private HandlerThread mHandlerThread;
+    @Mock private Handler mHandler;
+    @Mock private Vpn mVpn;
+    @Mock private INetworkManagementService mNms;
+    @Mock private ConnectivityManager mCm;
+    @Mock private UserManager mUserManager;
+    @Mock private INetd mNetd;
+    @Mock private PackageManager mPackageManager;
+    private VpnManagerServiceDependencies mDeps;
+    private VpnManagerService mService;
+
+    class VpnManagerServiceDependencies extends VpnManagerService.Dependencies {
+        @Override
+        public HandlerThread makeHandlerThread() {
+            return mHandlerThread;
+        }
+
+        @Override
+        public INetworkManagementService getINetworkManagementService() {
+            return mNms;
+        }
+
+        @Override
+        public INetd getNetd() {
+            return mNetd;
+        }
+
+        @Override
+        public Vpn createVpn(Looper looper, Context context, INetworkManagementService nms,
+                INetd netd, @UserIdInt int userId) {
+            return mVpn;
+        }
+    }
+
+    @Before
+    public void setUp() throws Exception {
+        MockitoAnnotations.initMocks(this);
+
+        mHandlerThread = new HandlerThread("TestVpnManagerService");
+        mDeps = new VpnManagerServiceDependencies();
+        doReturn(mContext).when(mContext).createContextAsUser(any(), anyInt());
+        doReturn(mPackageManager).when(mContext).getPackageManager();
+        setMockedPackages(mPackageManager, sPackages);
+
+        mockService(mContext, ConnectivityManager.class, Context.CONNECTIVITY_SERVICE, mCm);
+        mockService(mContext, UserManager.class, Context.USER_SERVICE, mUserManager);
+
+        doReturn(new Intent()).when(mContext).registerReceiver(
+                any() /* receiver */,
+                any() /* intentFilter */,
+                any() /* broadcastPermission */,
+                eq(mHandler) /* scheduler */);
+        doReturn(SYSTEM_USER).when(mUserManager).getUserInfo(eq(SYSTEM_USER_ID));
+        mService = new VpnManagerService(mContext, mDeps);
+    }
+
+    @Test
+    public void testUpdateAppExclusionList() {
+        // Add user to create vpn in mVpn
+        mService.onUserStarted(SYSTEM_USER_ID);
+        assertNotNull(mService.mVpns.get(SYSTEM_USER_ID));
+
+        // Start vpn
+        mService.startVpnProfile(TEST_VPN_PKG);
+        verify(mVpn).startVpnProfile(eq(TEST_VPN_PKG));
+
+        // Remove package due to package replaced.
+        mService.onPackageRemoved(PKGS[0], PKG_UIDS[0], true /* isReplacing */);
+        verify(mVpn, never()).refreshPlatformVpnAppExclusionList();
+
+        // Add package due to package replaced.
+        mService.onPackageAdded(PKGS[0], PKG_UIDS[0], true /* isReplacing */);
+        verify(mVpn, never()).refreshPlatformVpnAppExclusionList();
+
+        // Remove package
+        mService.onPackageRemoved(PKGS[0], PKG_UIDS[0], false /* isReplacing */);
+        verify(mVpn).refreshPlatformVpnAppExclusionList();
+
+        // Add the package back
+        mService.onPackageAdded(PKGS[0], PKG_UIDS[0], false /* isReplacing */);
+        verify(mVpn, times(2)).refreshPlatformVpnAppExclusionList();
+    }
+}
diff --git a/tests/unit/java/com/android/server/VpnTestBase.java b/tests/unit/java/com/android/server/VpnTestBase.java
index 3c62571..6113872 100644
--- a/tests/unit/java/com/android/server/VpnTestBase.java
+++ b/tests/unit/java/com/android/server/VpnTestBase.java
@@ -31,7 +31,10 @@
 import android.os.UserHandle;
 import android.util.ArrayMap;
 
+import java.util.Arrays;
+import java.util.List;
 import java.util.Map;
+import java.util.stream.Collectors;
 
 /** Common variables or methods shared between VpnTest and VpnManagerServiceTest. */
 public class VpnTestBase {
@@ -87,4 +90,8 @@
         } catch (Exception e) {
         }
     }
+
+    protected List<Integer> toList(int[] arr) {
+        return Arrays.stream(arr).boxed().collect(Collectors.toList());
+    }
 }
diff --git a/tests/unit/java/com/android/server/connectivity/VpnTest.java b/tests/unit/java/com/android/server/connectivity/VpnTest.java
index 75a4704..d24c59f 100644
--- a/tests/unit/java/com/android/server/connectivity/VpnTest.java
+++ b/tests/unit/java/com/android/server/connectivity/VpnTest.java
@@ -92,10 +92,8 @@
 import android.net.LocalSocket;
 import android.net.Network;
 import android.net.NetworkAgent;
-import android.net.NetworkAgentConfig;
 import android.net.NetworkCapabilities;
 import android.net.NetworkInfo.DetailedState;
-import android.net.NetworkProvider;
 import android.net.RouteInfo;
 import android.net.UidRangeParcel;
 import android.net.VpnManager;
@@ -117,7 +115,6 @@
 import android.os.Bundle;
 import android.os.ConditionVariable;
 import android.os.INetworkManagementService;
-import android.os.Looper;
 import android.os.ParcelFileDescriptor;
 import android.os.PowerWhitelistManager;
 import android.os.Process;
@@ -174,6 +171,8 @@
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
+import java.util.SortedSet;
+import java.util.TreeSet;
 import java.util.concurrent.CompletableFuture;
 import java.util.concurrent.ScheduledFuture;
 import java.util.concurrent.ScheduledThreadPoolExecutor;
@@ -188,7 +187,7 @@
  */
 @RunWith(DevSdkIgnoreRunner.class)
 @SmallTest
-@IgnoreUpTo(VERSION_CODES.S_V2)
+@IgnoreUpTo(S_V2)
 public class VpnTest extends VpnTestBase {
     private static final String TAG = "VpnTest";
 
@@ -848,14 +847,11 @@
 
         vpn.startVpnProfile(TEST_VPN_PKG);
         verify(mVpnProfileStore).get(eq(vpn.getProfileNameForPackage(TEST_VPN_PKG)));
-        vpn.mNetworkAgent = new NetworkAgent(mContext, Looper.getMainLooper(), TAG,
-                new NetworkCapabilities.Builder().build(), new LinkProperties(), 10 /* score */,
-                new NetworkAgentConfig.Builder().build(),
-                new NetworkProvider(mContext, Looper.getMainLooper(), TAG)) {};
+        vpn.mNetworkAgent = mMockNetworkAgent;
         return vpn;
     }
 
-    @Test @IgnoreUpTo(S_V2)
+    @Test
     public void testSetAndGetAppExclusionList() throws Exception {
         final Vpn vpn = prepareVpnForVerifyAppExclusionList();
         verify(mVpnProfileStore, never()).put(eq(PRIMARY_USER_APP_EXCLUDE_KEY), any());
@@ -869,7 +865,81 @@
         assertEquals(Arrays.asList(PKGS), vpn.getAppExclusionList(TEST_VPN_PKG));
     }
 
-    @Test @IgnoreUpTo(S_V2)
+    @Test
+    public void testRefreshPlatformVpnAppExclusionList_updatesExcludedUids() throws Exception {
+        final Vpn vpn = prepareVpnForVerifyAppExclusionList();
+        vpn.setAppExclusionList(TEST_VPN_PKG, Arrays.asList(PKGS));
+        verify(mMockNetworkAgent).sendNetworkCapabilities(any());
+        assertEquals(Arrays.asList(PKGS), vpn.getAppExclusionList(TEST_VPN_PKG));
+
+        reset(mMockNetworkAgent);
+
+        // Remove one of the package
+        List<Integer> newExcludedUids = toList(PKG_UIDS);
+        newExcludedUids.remove((Integer) PKG_UIDS[0]);
+        sPackages.remove(PKGS[0]);
+        vpn.refreshPlatformVpnAppExclusionList();
+
+        // List in keystore is not changed, but UID for the removed packages is no longer exempted.
+        assertEquals(Arrays.asList(PKGS), vpn.getAppExclusionList(TEST_VPN_PKG));
+        assertEquals(makeVpnUidRange(PRIMARY_USER.id, newExcludedUids),
+                vpn.mNetworkCapabilities.getUids());
+        ArgumentCaptor<NetworkCapabilities> ncCaptor =
+                ArgumentCaptor.forClass(NetworkCapabilities.class);
+        verify(mMockNetworkAgent).sendNetworkCapabilities(ncCaptor.capture());
+        assertEquals(makeVpnUidRange(PRIMARY_USER.id, newExcludedUids),
+                ncCaptor.getValue().getUids());
+
+        reset(mMockNetworkAgent);
+
+        // Add the package back
+        newExcludedUids.add(PKG_UIDS[0]);
+        sPackages.put(PKGS[0], PKG_UIDS[0]);
+        vpn.refreshPlatformVpnAppExclusionList();
+
+        // List in keystore is not changed and the uid list should be updated in the net cap.
+        assertEquals(Arrays.asList(PKGS), vpn.getAppExclusionList(TEST_VPN_PKG));
+        assertEquals(makeVpnUidRange(PRIMARY_USER.id, newExcludedUids),
+                vpn.mNetworkCapabilities.getUids());
+        verify(mMockNetworkAgent).sendNetworkCapabilities(ncCaptor.capture());
+        assertEquals(makeVpnUidRange(PRIMARY_USER.id, newExcludedUids),
+                ncCaptor.getValue().getUids());
+    }
+
+    private Set<Range<Integer>> makeVpnUidRange(int userId, List<Integer> excludedList) {
+        final SortedSet<Integer> list = new TreeSet<>();
+
+        final int userBase = userId * UserHandle.PER_USER_RANGE;
+        for (int uid : excludedList) {
+            final int applicationUid = UserHandle.getUid(userId, uid);
+            list.add(applicationUid);
+            list.add(Process.toSdkSandboxUid(applicationUid)); // Add Sdk Sandbox UID
+        }
+
+        final int minUid = userBase;
+        final int maxUid = userBase + UserHandle.PER_USER_RANGE - 1;
+        final Set<Range<Integer>> ranges = new ArraySet<>();
+
+        // Iterate the list to create the ranges between each uid.
+        int start = minUid;
+        for (int uid : list) {
+            if (uid == start) {
+                start++;
+            } else {
+                ranges.add(new Range<>(start, uid - 1));
+                start = uid + 1;
+            }
+        }
+
+        // Create the range between last uid and max uid.
+        if (start <= maxUid) {
+            ranges.add(new Range<>(start, maxUid));
+        }
+
+        return ranges;
+    }
+
+    @Test
     public void testSetAndGetAppExclusionListRestrictedUser() throws Exception {
         final Vpn vpn = prepareVpnForVerifyAppExclusionList();
         // Mock it to restricted profile