diff --git a/service/src/com/android/server/connectivity/PermissionMonitor.java b/service/src/com/android/server/connectivity/PermissionMonitor.java
index 2885ba7..62b3add 100755
--- a/service/src/com/android/server/connectivity/PermissionMonitor.java
+++ b/service/src/com/android/server/connectivity/PermissionMonitor.java
@@ -127,9 +127,17 @@
     @GuardedBy("this")
     private final Set<Integer> mUidsAllowedOnRestrictedNetworks = new ArraySet<>();
 
+    // Store PackageManager for each user.
+    // Keys are users, Values are PackageManagers which get from each user.
     @GuardedBy("this")
     private final Map<UserHandle, PackageManager> mUsersPackageManager = new ArrayMap<>();
 
+    // Store appIds traffic permissions for each user.
+    // Keys are users, Values are SparseArrays where each entry maps an appId to the permissions
+    // that appId has within that user.
+    @GuardedBy("this")
+    private final Map<UserHandle, SparseIntArray> mUsersTrafficPermissions = new ArrayMap<>();
+
     private static final int SYSTEM_APPID = SYSTEM_UID;
 
     private static final int MAX_PERMISSION_UPDATE_LOGS = 40;
@@ -292,14 +300,24 @@
         sendUidsNetworkPermission(uids, true /* add */);
     }
 
-    private void updateAppIdsTrafficPermission(final SparseIntArray appIds,
-            final SparseIntArray extraAppIds) {
-        for (int i = 0; i < extraAppIds.size(); i++) {
-            final int appId = extraAppIds.keyAt(i);
-            final int permission = extraAppIds.valueAt(i);
-            appIds.put(appId, appIds.get(appId) | permission);
+    /**
+     * Calculates permissions for appIds.
+     * Maps each appId to the union of all traffic permissions that the appId has in all users.
+     *
+     * @return The appIds traffic permissions.
+     */
+    private synchronized SparseIntArray makeAppIdsTrafficPermForAllUsers() {
+        final SparseIntArray appIds = new SparseIntArray();
+        // Check appIds permissions from each user.
+        for (UserHandle user : mUsersTrafficPermissions.keySet()) {
+            final SparseIntArray userAppIds = mUsersTrafficPermissions.get(user);
+            for (int i = 0; i < userAppIds.size(); i++) {
+                final int appId = userAppIds.keyAt(i);
+                final int permission = userAppIds.valueAt(i);
+                appIds.put(appId, appIds.get(appId) | permission);
+            }
         }
-        sendAppIdsTrafficPermission(appIds);
+        return appIds;
     }
 
     private SparseIntArray getSystemTrafficPerm() {
@@ -363,6 +381,10 @@
         // mUidsAllowedOnRestrictedNetworks.
         updateUidsAllowedOnRestrictedNetworks(mDeps.getUidsAllowedOnRestrictedNetworks(mContext));
 
+        // Read system traffic permissions when a user removed and put them to USER_ALL because they
+        // are not specific to any particular user.
+        mUsersTrafficPermissions.put(UserHandle.ALL, getSystemTrafficPerm());
+
         final List<UserHandle> usrs = mUserManager.getUserHandles(true /* excludeDying */);
         // Update netd permissions for all users.
         for (UserHandle user : usrs) {
@@ -487,9 +509,16 @@
         final SparseIntArray uids = makeUidsNetworkPerm(apps);
         updateUidsNetworkPermission(uids);
 
-        // App ids traffic permission
-        final SparseIntArray appIds = makeAppIdsTrafficPerm(apps);
-        updateAppIdsTrafficPermission(appIds, getSystemTrafficPerm());
+        // Add new user appIds permissions.
+        final SparseIntArray addedUserAppIds = makeAppIdsTrafficPerm(apps);
+        mUsersTrafficPermissions.put(user, addedUserAppIds);
+        // Generate appIds from all users and send result to netd.
+        final SparseIntArray appIds = makeAppIdsTrafficPermForAllUsers();
+        sendAppIdsTrafficPermission(appIds);
+
+        // Log user added
+        mPermissionUpdateLogs.log("New user(" + user.getIdentifier() + ") added: nPerm uids="
+                + uids + ", tPerm appIds=" + addedUserAppIds);
     }
 
     /**
@@ -502,6 +531,7 @@
     public synchronized void onUserRemoved(@NonNull UserHandle user) {
         mUsers.remove(user);
 
+        // Remove uids network permissions that belongs to the user.
         final SparseIntArray removedUids = new SparseIntArray();
         final SparseIntArray allUids = mUidToNetworkPerm.clone();
         for (int i = 0; i < allUids.size(); i++) {
@@ -512,6 +542,27 @@
             }
         }
         sendUidsNetworkPermission(removedUids, false /* add */);
+
+        // Remove appIds traffic permission that belongs to the user
+        final SparseIntArray removedUserAppIds = mUsersTrafficPermissions.remove(user);
+        // Generate appIds from left users.
+        final SparseIntArray appIds = makeAppIdsTrafficPermForAllUsers();
+        // Clear permission on those appIds belong to this user only, set the permission to
+        // PERMISSION_UNINSTALLED.
+        if (removedUserAppIds != null) {
+            for (int i = 0; i < removedUserAppIds.size(); i++) {
+                final int appId = removedUserAppIds.keyAt(i);
+                // Need to clear permission if the removed appId is not found in the array.
+                if (appIds.indexOfKey(appId) < 0) {
+                    appIds.put(appId, PERMISSION_UNINSTALLED);
+                }
+            }
+        }
+        sendAppIdsTrafficPermission(appIds);
+
+        // Log user removed
+        mPermissionUpdateLogs.log("User(" + user.getIdentifier() + ") removed: nPerm uids="
+                + removedUids + ", tPerm appIds=" + removedUserAppIds);
     }
 
     /**
@@ -598,6 +649,39 @@
         }
     }
 
+    private synchronized void updateAppIdTrafficPermission(int uid) {
+        final int appId = UserHandle.getAppId(uid);
+        final int uidTrafficPerm = getTrafficPermissionForUid(uid);
+        final SparseIntArray userTrafficPerms =
+                mUsersTrafficPermissions.get(UserHandle.getUserHandleForUid(uid));
+        if (userTrafficPerms == null) {
+            Log.wtf(TAG, "Can't get user traffic permission from uid=" + uid);
+            return;
+        }
+        // Do not put PERMISSION_UNINSTALLED into the array. If no package left on the uid
+        // (PERMISSION_UNINSTALLED), remove the appId from the array. Otherwise, update the latest
+        // permission to the appId.
+        if (uidTrafficPerm == PERMISSION_UNINSTALLED) {
+            userTrafficPerms.delete(appId);
+        } else {
+            userTrafficPerms.put(appId, uidTrafficPerm);
+        }
+    }
+
+    private synchronized int getAppIdTrafficPermission(int appId) {
+        int permission = PERMISSION_NONE;
+        boolean installed = false;
+        for (UserHandle user : mUsersTrafficPermissions.keySet()) {
+            final SparseIntArray userApps = mUsersTrafficPermissions.get(user);
+            final int appIdx = userApps.indexOfKey(appId);
+            if (appIdx >= 0) {
+                permission |= userApps.valueAt(appIdx);
+                installed = true;
+            }
+        }
+        return installed ? permission : PERMISSION_UNINSTALLED;
+    }
+
     /**
      * Called when a package is added.
      *
@@ -607,9 +691,12 @@
      * @hide
      */
     public synchronized void onPackageAdded(@NonNull final String packageName, final int uid) {
+        // Update uid permission.
+        updateAppIdTrafficPermission(uid);
+        // Get the appId permission from all users then send the latest permission to netd.
         final int appId = UserHandle.getAppId(uid);
-        final int trafficPerm = getTrafficPermissionForUid(uid);
-        sendPackagePermissionsForAppId(appId, trafficPerm);
+        final int appIdTrafficPerm = getAppIdTrafficPermission(appId);
+        sendPackagePermissionsForAppId(appId, appIdTrafficPerm);
 
         final int currentPermission = mUidToNetworkPerm.get(uid, PERMISSION_NONE);
         final int permission = highestPermissionForUid(uid, currentPermission, packageName);
@@ -633,10 +720,12 @@
         // package can bypass VPN.
         updateVpnUid(uid, true /* add */);
         mAllApps.add(appId);
+
+        // Log package added.
         mPermissionUpdateLogs.log("Package add: name=" + packageName + ", uid=" + uid
                 + ", nPerm=(" + permissionToString(permission) + "/"
                 + permissionToString(currentPermission) + ")"
-                + ", tPerm=" + permissionToString(trafficPerm));
+                + ", tPerm=" + permissionToString(appIdTrafficPerm));
     }
 
     private int highestUidNetworkPermission(int uid) {
@@ -664,9 +753,12 @@
      * @hide
      */
     public synchronized void onPackageRemoved(@NonNull final String packageName, final int uid) {
+        // Update uid permission.
+        updateAppIdTrafficPermission(uid);
+        // Get the appId permission from all users then send the latest permission to netd.
         final int appId = UserHandle.getAppId(uid);
-        final int trafficPerm = getTrafficPermissionForUid(uid);
-        sendPackagePermissionsForAppId(appId, trafficPerm);
+        final int appIdTrafficPerm = getAppIdTrafficPermission(appId);
+        sendPackagePermissionsForAppId(appId, appIdTrafficPerm);
 
         // If the newly-removed package falls within some VPN's uid range, update Netd with it.
         // This needs to happen before the mUidToNetworkPerm update below, since
@@ -680,10 +772,13 @@
 
         final int currentPermission = mUidToNetworkPerm.get(uid, PERMISSION_NONE);
         final int permission = highestUidNetworkPermission(uid);
+
+        // Log package removed.
         mPermissionUpdateLogs.log("Package remove: name=" + packageName + ", uid=" + uid
                 + ", nPerm=(" + permissionToString(permission) + "/"
                 + permissionToString(currentPermission) + ")"
-                + ", tPerm=" + permissionToString(trafficPerm));
+                + ", tPerm=" + permissionToString(appIdTrafficPerm));
+
         if (permission != currentPermission) {
             final SparseIntArray apps = new SparseIntArray();
             int sdkSandboxUid = -1;
diff --git a/tests/unit/java/com/android/server/connectivity/PermissionMonitorTest.java b/tests/unit/java/com/android/server/connectivity/PermissionMonitorTest.java
index 6b379e8..fb821c3 100644
--- a/tests/unit/java/com/android/server/connectivity/PermissionMonitorTest.java
+++ b/tests/unit/java/com/android/server/connectivity/PermissionMonitorTest.java
@@ -117,23 +117,32 @@
 public class PermissionMonitorTest {
     private static final int MOCK_USER_ID1 = 0;
     private static final int MOCK_USER_ID2 = 1;
+    private static final int MOCK_USER_ID3 = 2;
     private static final UserHandle MOCK_USER1 = UserHandle.of(MOCK_USER_ID1);
     private static final UserHandle MOCK_USER2 = UserHandle.of(MOCK_USER_ID2);
+    private static final UserHandle MOCK_USER3 = UserHandle.of(MOCK_USER_ID3);
     private static final int MOCK_APPID1 = 10001;
     private static final int MOCK_APPID2 = 10086;
+    private static final int MOCK_APPID3 = 10110;
     private static final int SYSTEM_APPID1 = 1100;
     private static final int SYSTEM_APPID2 = 1108;
     private static final int VPN_APPID = 10002;
     private static final int MOCK_UID11 = MOCK_USER1.getUid(MOCK_APPID1);
     private static final int MOCK_UID12 = MOCK_USER1.getUid(MOCK_APPID2);
+    private static final int MOCK_UID13 = MOCK_USER1.getUid(MOCK_APPID3);
     private static final int SYSTEM_APP_UID11 = MOCK_USER1.getUid(SYSTEM_APPID1);
     private static final int VPN_UID = MOCK_USER1.getUid(VPN_APPID);
     private static final int MOCK_UID21 = MOCK_USER2.getUid(MOCK_APPID1);
     private static final int MOCK_UID22 = MOCK_USER2.getUid(MOCK_APPID2);
+    private static final int MOCK_UID23 = MOCK_USER2.getUid(MOCK_APPID3);
     private static final int SYSTEM_APP_UID21 = MOCK_USER2.getUid(SYSTEM_APPID1);
+    private static final int MOCK_UID31 = MOCK_USER3.getUid(MOCK_APPID1);
+    private static final int MOCK_UID32 = MOCK_USER3.getUid(MOCK_APPID2);
+    private static final int MOCK_UID33 = MOCK_USER3.getUid(MOCK_APPID3);
     private static final String REAL_SYSTEM_PACKAGE_NAME = "android";
     private static final String MOCK_PACKAGE1 = "appName1";
     private static final String MOCK_PACKAGE2 = "appName2";
+    private static final String MOCK_PACKAGE3 = "appName3";
     private static final String SYSTEM_PACKAGE1 = "sysName1";
     private static final String SYSTEM_PACKAGE2 = "sysName2";
     private static final String PARTITION_SYSTEM = "system";
@@ -191,6 +200,7 @@
         mBpfMapMonitor = new BpfMapMonitor(mBpfNetMaps);
 
         doReturn(List.of()).when(mPackageManager).getInstalledPackagesAsUser(anyInt(), anyInt());
+        mPermissionMonitor.onUserAdded(MOCK_USER1);
     }
 
     private boolean hasRestrictedNetworkPermission(String partition, int targetSdkVersion,
@@ -283,6 +293,18 @@
         mPermissionMonitor.onPackageAdded(packageName, uid);
     }
 
+    private void removePackage(String packageName, int uid) {
+        final String[] oldPackages = mPackageManager.getPackagesForUid(uid);
+        // If the package isn't existed, no need to remove it.
+        if (!CollectionUtils.contains(oldPackages, packageName)) return;
+
+        // Remove the package if this uid is shared with other packages.
+        final String[] newPackages = Arrays.stream(oldPackages).filter(e -> !e.equals(packageName))
+                .toArray(String[]::new);
+        doReturn(newPackages).when(mPackageManager).getPackagesForUid(eq(uid));
+        mPermissionMonitor.onPackageRemoved(packageName, uid);
+    }
+
     @Test
     public void testHasPermission() {
         PackageInfo app = systemPackageInfoWithPermissions();
@@ -791,6 +813,7 @@
                 buildPackageInfo(SYSTEM_PACKAGE2, VPN_UID)))
                 .when(mPackageManager).getInstalledPackagesAsUser(eq(GET_PERMISSIONS), anyInt());
         buildAndMockPackageInfoWithPermissions(MOCK_PACKAGE1, MOCK_UID11);
+        doReturn(List.of(MOCK_USER1, MOCK_USER2)).when(mUserManager).getUserHandles(eq(true));
 
         mPermissionMonitor.startMonitoring();
         final Set<UidRange> vpnRange = Set.of(UidRange.createForUser(MOCK_USER1),
@@ -881,7 +904,7 @@
         addPackage(MOCK_PACKAGE1, MOCK_UID11, INTERNET, UPDATE_DEVICE_STATS);
         mBpfMapMonitor.expectTrafficPerm(PERMISSION_TRAFFIC_ALL, MOCK_APPID1);
 
-        // Install another package with the same uid and no permissions should not cause the app id
+        // Install another package with the same uid and no permissions should not cause the appId
         // to lose permissions.
         addPackage(MOCK_PACKAGE2, MOCK_UID11);
         mBpfMapMonitor.expectTrafficPerm(PERMISSION_TRAFFIC_ALL, MOCK_APPID1);
@@ -1249,4 +1272,211 @@
         assertTrue(isHigherNetworkPermission(PERMISSION_SYSTEM, PERMISSION_NETWORK));
         assertFalse(isHigherNetworkPermission(PERMISSION_SYSTEM, PERMISSION_SYSTEM));
     }
+
+    private void prepareMultiUserPackages() {
+        // MOCK_USER1 has installed 3 packages
+        // mockApp1 has no permission and share MOCK_APPID1.
+        // mockApp2 has INTERNET permission and share MOCK_APPID2.
+        // mockApp3 has UPDATE_DEVICE_STATS permission and share MOCK_APPID3.
+        final List<PackageInfo> pkgs1 = List.of(
+                buildPackageInfo("mockApp1", MOCK_UID11),
+                buildPackageInfo("mockApp2", MOCK_UID12, INTERNET),
+                buildPackageInfo("mockApp3", MOCK_UID13, UPDATE_DEVICE_STATS));
+
+        // MOCK_USER2 has installed 2 packages
+        // mockApp4 has UPDATE_DEVICE_STATS permission and share MOCK_APPID1.
+        // mockApp5 has INTERNET permission and share MOCK_APPID2.
+        final List<PackageInfo> pkgs2 = List.of(
+                buildPackageInfo("mockApp4", MOCK_UID21, UPDATE_DEVICE_STATS),
+                buildPackageInfo("mockApp5", MOCK_UID23, INTERNET));
+
+        // MOCK_USER3 has installed 1 packages
+        // mockApp6 has UPDATE_DEVICE_STATS permission and share MOCK_APPID2.
+        final List<PackageInfo> pkgs3 = List.of(
+                buildPackageInfo("mockApp6", MOCK_UID32, UPDATE_DEVICE_STATS));
+
+        doReturn(pkgs1).when(mPackageManager).getInstalledPackagesAsUser(eq(GET_PERMISSIONS),
+                eq(MOCK_USER_ID1));
+        doReturn(pkgs2).when(mPackageManager).getInstalledPackagesAsUser(eq(GET_PERMISSIONS),
+                eq(MOCK_USER_ID2));
+        doReturn(pkgs3).when(mPackageManager).getInstalledPackagesAsUser(eq(GET_PERMISSIONS),
+                eq(MOCK_USER_ID3));
+    }
+
+    private void addUserAndVerifyAppIdsPermissions(UserHandle user, int appId1Perm,
+            int appId2Perm, int appId3Perm) {
+        mPermissionMonitor.onUserAdded(user);
+        mBpfMapMonitor.expectTrafficPerm(appId1Perm, MOCK_APPID1);
+        mBpfMapMonitor.expectTrafficPerm(appId2Perm, MOCK_APPID2);
+        mBpfMapMonitor.expectTrafficPerm(appId3Perm, MOCK_APPID3);
+    }
+
+    private void removeUserAndVerifyAppIdsPermissions(UserHandle user, int appId1Perm,
+            int appId2Perm, int appId3Perm) {
+        mPermissionMonitor.onUserRemoved(user);
+        mBpfMapMonitor.expectTrafficPerm(appId1Perm, MOCK_APPID1);
+        mBpfMapMonitor.expectTrafficPerm(appId2Perm, MOCK_APPID2);
+        mBpfMapMonitor.expectTrafficPerm(appId3Perm, MOCK_APPID3);
+    }
+
+    @Test
+    public void testAppIdsTrafficPermission_UserAddedRemoved() {
+        prepareMultiUserPackages();
+
+        // Add MOCK_USER1 and verify the permissions with each appIds.
+        addUserAndVerifyAppIdsPermissions(MOCK_USER1, PERMISSION_NONE, PERMISSION_INTERNET,
+                PERMISSION_UPDATE_DEVICE_STATS);
+
+        // Add MOCK_USER2 and verify the permissions upgrade on MOCK_APPID1 & MOCK_APPID3.
+        addUserAndVerifyAppIdsPermissions(MOCK_USER2, PERMISSION_UPDATE_DEVICE_STATS,
+                PERMISSION_INTERNET, PERMISSION_TRAFFIC_ALL);
+
+        // Add MOCK_USER3 and verify the permissions upgrade on MOCK_APPID2.
+        addUserAndVerifyAppIdsPermissions(MOCK_USER3, PERMISSION_UPDATE_DEVICE_STATS,
+                PERMISSION_TRAFFIC_ALL, PERMISSION_TRAFFIC_ALL);
+
+        // Remove MOCK_USER2 and verify the permissions downgrade on MOCK_APPID1 & MOCK_APPID3.
+        removeUserAndVerifyAppIdsPermissions(MOCK_USER2, PERMISSION_NONE, PERMISSION_TRAFFIC_ALL,
+                PERMISSION_UPDATE_DEVICE_STATS);
+
+        // Remove MOCK_USER1 and verify the permissions downgrade on all appIds.
+        removeUserAndVerifyAppIdsPermissions(MOCK_USER1, PERMISSION_UNINSTALLED,
+                PERMISSION_UPDATE_DEVICE_STATS, PERMISSION_UNINSTALLED);
+
+        // Add MOCK_USER2 back and verify the permissions upgrade on MOCK_APPID1 & MOCK_APPID3.
+        addUserAndVerifyAppIdsPermissions(MOCK_USER2, PERMISSION_UPDATE_DEVICE_STATS,
+                PERMISSION_UPDATE_DEVICE_STATS, PERMISSION_INTERNET);
+
+        // Remove MOCK_USER3 and verify the permissions downgrade on MOCK_APPID2.
+        removeUserAndVerifyAppIdsPermissions(MOCK_USER3, PERMISSION_UPDATE_DEVICE_STATS,
+                PERMISSION_UNINSTALLED, PERMISSION_INTERNET);
+    }
+
+    @Test
+    public void testAppIdsTrafficPermission_Multiuser_PackageAdded() throws Exception {
+        // Add two users with empty package list.
+        mPermissionMonitor.onUserAdded(MOCK_USER1);
+        mPermissionMonitor.onUserAdded(MOCK_USER2);
+
+        final int[] netdPermissions = {PERMISSION_NONE, PERMISSION_INTERNET,
+                PERMISSION_UPDATE_DEVICE_STATS, PERMISSION_TRAFFIC_ALL};
+        final String[][] grantPermissions = {new String[]{}, new String[]{INTERNET},
+                new String[]{UPDATE_DEVICE_STATS}, new String[]{INTERNET, UPDATE_DEVICE_STATS}};
+
+        // Verify that the permission combination is expected when same appId package is installed
+        // on another user. List the expected permissions below.
+        // NONE                + NONE                = NONE
+        // NONE                + INTERNET            = INTERNET
+        // NONE                + UPDATE_DEVICE_STATS = UPDATE_DEVICE_STATS
+        // NONE                + ALL                 = ALL
+        // INTERNET            + NONE                = INTERNET
+        // INTERNET            + INTERNET            = INTERNET
+        // INTERNET            + UPDATE_DEVICE_STATS = ALL
+        // INTERNET            + ALL                 = ALL
+        // UPDATE_DEVICE_STATS + NONE                = UPDATE_DEVICE_STATS
+        // UPDATE_DEVICE_STATS + INTERNET            = ALL
+        // UPDATE_DEVICE_STATS + UPDATE_DEVICE_STATS = UPDATE_DEVICE_STATS
+        // UPDATE_DEVICE_STATS + ALL                 = ALL
+        // ALL                 + NONE                = ALL
+        // ALL                 + INTERNET            = ALL
+        // ALL                 + UPDATE_DEVICE_STATS = ALL
+        // ALL                 + ALL                 = ALL
+        for (int i = 0, num = 0; i < netdPermissions.length; i++) {
+            final int current = netdPermissions[i];
+            final String[] user1Perm = grantPermissions[i];
+            for (int j = 0; j < netdPermissions.length; j++) {
+                final int appId = MOCK_APPID1 + num;
+                final int added = netdPermissions[j];
+                final String[] user2Perm = grantPermissions[j];
+                // Add package on MOCK_USER1 and verify the permission is same as package granted.
+                addPackage(MOCK_PACKAGE1, MOCK_USER1.getUid(appId), user1Perm);
+                mBpfMapMonitor.expectTrafficPerm(current, appId);
+
+                // Add package which share the same appId on MOCK_USER2, and verify the permission
+                // has combined.
+                addPackage(MOCK_PACKAGE2, MOCK_USER2.getUid(appId), user2Perm);
+                mBpfMapMonitor.expectTrafficPerm((current | added), appId);
+                num++;
+            }
+        }
+    }
+
+    private void verifyAppIdPermissionsAfterPackageRemoved(int appId, int expectedPerm,
+            String[] user1Perm, String[] user2Perm) throws Exception {
+        // Add package on MOCK_USER1 and verify the permission is same as package granted.
+        addPackage(MOCK_PACKAGE1, MOCK_USER1.getUid(appId), user1Perm);
+        mBpfMapMonitor.expectTrafficPerm(expectedPerm, appId);
+
+        // Add two packages which share the same appId and don't declare permission on
+        // MOCK_USER2. Verify the permission has no change.
+        addPackage(MOCK_PACKAGE2, MOCK_USER2.getUid(appId));
+        addPackage(MOCK_PACKAGE3, MOCK_USER2.getUid(appId), user2Perm);
+        mBpfMapMonitor.expectTrafficPerm(expectedPerm, appId);
+
+        // Remove one packages from MOCK_USER2. Verify the permission has no change too.
+        removePackage(MOCK_PACKAGE2, MOCK_USER2.getUid(appId));
+        mBpfMapMonitor.expectTrafficPerm(expectedPerm, appId);
+
+        // Remove last packages from MOCK_USER2. Verify the permission has still no change.
+        removePackage(MOCK_PACKAGE3, MOCK_USER2.getUid(appId));
+        mBpfMapMonitor.expectTrafficPerm(expectedPerm, appId);
+    }
+
+    @Test
+    public void testAppIdsTrafficPermission_Multiuser_PackageRemoved() throws Exception {
+        // Add two users with empty package list.
+        mPermissionMonitor.onUserAdded(MOCK_USER1);
+        mPermissionMonitor.onUserAdded(MOCK_USER2);
+
+        int appId = MOCK_APPID1;
+        // Verify that the permission combination is expected when same appId package is removed on
+        // another user. List the expected permissions below.
+        /***** NONE *****/
+        // NONE + NONE = NONE
+        verifyAppIdPermissionsAfterPackageRemoved(
+                appId++, PERMISSION_NONE, new String[]{}, new String[]{});
+
+        /***** INTERNET *****/
+        // INTERNET + NONE = INTERNET
+        verifyAppIdPermissionsAfterPackageRemoved(
+                appId++, PERMISSION_INTERNET, new String[]{INTERNET}, new String[]{});
+
+        // INTERNET + INTERNET = INTERNET
+        verifyAppIdPermissionsAfterPackageRemoved(
+                appId++, PERMISSION_INTERNET, new String[]{INTERNET}, new String[]{INTERNET});
+
+        /***** UPDATE_DEVICE_STATS *****/
+        // UPDATE_DEVICE_STATS + NONE = UPDATE_DEVICE_STATS
+        verifyAppIdPermissionsAfterPackageRemoved(appId++, PERMISSION_UPDATE_DEVICE_STATS,
+                new String[]{UPDATE_DEVICE_STATS}, new String[]{});
+
+        // UPDATE_DEVICE_STATS + UPDATE_DEVICE_STATS = UPDATE_DEVICE_STATS
+        verifyAppIdPermissionsAfterPackageRemoved(appId++, PERMISSION_UPDATE_DEVICE_STATS,
+                new String[]{UPDATE_DEVICE_STATS}, new String[]{UPDATE_DEVICE_STATS});
+
+        /***** ALL *****/
+        // ALL + NONE = ALL
+        verifyAppIdPermissionsAfterPackageRemoved(appId++, PERMISSION_TRAFFIC_ALL,
+                new String[]{INTERNET, UPDATE_DEVICE_STATS}, new String[]{});
+
+        // ALL + INTERNET = ALL
+        verifyAppIdPermissionsAfterPackageRemoved(appId++, PERMISSION_TRAFFIC_ALL,
+                new String[]{INTERNET, UPDATE_DEVICE_STATS}, new String[]{INTERNET});
+
+        // ALL + UPDATE_DEVICE_STATS = ALL
+        verifyAppIdPermissionsAfterPackageRemoved(appId++, PERMISSION_TRAFFIC_ALL,
+                new String[]{INTERNET, UPDATE_DEVICE_STATS}, new String[]{UPDATE_DEVICE_STATS});
+
+        // ALL + ALL = ALL
+        verifyAppIdPermissionsAfterPackageRemoved(appId++, PERMISSION_TRAFFIC_ALL,
+                new String[]{INTERNET, UPDATE_DEVICE_STATS},
+                new String[]{INTERNET, UPDATE_DEVICE_STATS});
+
+        /***** UNINSTALL *****/
+        // UNINSTALL + UNINSTALL = UNINSTALL
+        verifyAppIdPermissionsAfterPackageRemoved(
+                appId, PERMISSION_NONE, new String[]{}, new String[]{});
+        removePackage(MOCK_PACKAGE1, MOCK_USER1.getUid(appId));
+        mBpfMapMonitor.expectTrafficPerm(PERMISSION_UNINSTALLED, appId);
+    }
 }