diff --git a/hostsidetests/devicepolicy/app/DeviceAndProfileOwner/src/com/android/cts/deviceandprofileowner/AlwaysOnVpnMultiStageTest.java b/hostsidetests/devicepolicy/app/DeviceAndProfileOwner/src/com/android/cts/deviceandprofileowner/AlwaysOnVpnMultiStageTest.java
index 0b20c64..e445347c 100644
--- a/hostsidetests/devicepolicy/app/DeviceAndProfileOwner/src/com/android/cts/deviceandprofileowner/AlwaysOnVpnMultiStageTest.java
+++ b/hostsidetests/devicepolicy/app/DeviceAndProfileOwner/src/com/android/cts/deviceandprofileowner/AlwaysOnVpnMultiStageTest.java
@@ -16,15 +16,15 @@
 
 package com.android.cts.deviceandprofileowner;
 
+import static com.android.cts.deviceandprofileowner.vpn.VpnTestHelper.TEST_ADDRESS;
+import static com.android.cts.deviceandprofileowner.vpn.VpnTestHelper.VPN_PACKAGE;
+
 import android.content.pm.PackageManager;
 import android.system.ErrnoException;
 import android.system.OsConstants;
 
 import com.android.cts.deviceandprofileowner.vpn.VpnTestHelper;
 
-import static com.android.cts.deviceandprofileowner.vpn.VpnTestHelper.VPN_PACKAGE;
-import static com.android.cts.deviceandprofileowner.vpn.VpnTestHelper.TEST_ADDRESS;
-
 /**
  * Contains methods to test always-on VPN invoked by DeviceAndProfileOwnerTest
  */
@@ -32,11 +32,16 @@
 
     public void testAlwaysOnSet() throws Exception {
         // Setup always-on vpn
-        VpnTestHelper.setAndWaitForVpn(mContext, VPN_PACKAGE, /* usable */ true);
+        VpnTestHelper.waitForVpn(mContext, VPN_PACKAGE, /* usable */ true);
         assertTrue(VpnTestHelper.isNetworkVpn(mContext));
         VpnTestHelper.checkPing(TEST_ADDRESS);
     }
 
+    public void testAlwaysOnSetAfterReboot() throws Exception {
+        VpnTestHelper.waitForVpn(mContext, null, /* usable */ true);
+        VpnTestHelper.checkPing(TEST_ADDRESS);
+    }
+
     public void testNetworkBlocked() throws Exception {
         // After the vpn app being force-stop, expect that always-on package stays the same
         assertEquals(VPN_PACKAGE, mDevicePolicyManager.getAlwaysOnVpnPackage(
diff --git a/hostsidetests/devicepolicy/app/DeviceAndProfileOwner/src/com/android/cts/deviceandprofileowner/AlwaysOnVpnTest.java b/hostsidetests/devicepolicy/app/DeviceAndProfileOwner/src/com/android/cts/deviceandprofileowner/AlwaysOnVpnTest.java
index 84330ab..fff701e 100644
--- a/hostsidetests/devicepolicy/app/DeviceAndProfileOwner/src/com/android/cts/deviceandprofileowner/AlwaysOnVpnTest.java
+++ b/hostsidetests/devicepolicy/app/DeviceAndProfileOwner/src/com/android/cts/deviceandprofileowner/AlwaysOnVpnTest.java
@@ -62,7 +62,7 @@
         // test always-on is null by default
         assertNull(mDevicePolicyManager.getAlwaysOnVpnPackage(ADMIN_RECEIVER_COMPONENT));
 
-        VpnTestHelper.setAndWaitForVpn(mContext, VPN_PACKAGE, /* usable */ true);
+        VpnTestHelper.waitForVpn(mContext, VPN_PACKAGE, /* usable */ true);
         VpnTestHelper.checkPing(TEST_ADDRESS);
     }
 
@@ -83,7 +83,7 @@
         restrictions.putStringArray(RESTRICTION_ALLOWED, new String[] {mPackageName});
         mDevicePolicyManager.setApplicationRestrictions(ADMIN_RECEIVER_COMPONENT, VPN_PACKAGE,
                 restrictions);
-        VpnTestHelper.setAndWaitForVpn(mContext, VPN_PACKAGE, /* usable */ true);
+        VpnTestHelper.waitForVpn(mContext, VPN_PACKAGE, /* usable */ true);
         assertTrue(VpnTestHelper.isNetworkVpn(mContext));
     }
 
@@ -92,7 +92,7 @@
         restrictions.putStringArray(RESTRICTION_DISALLOWED, new String[] {mPackageName});
         mDevicePolicyManager.setApplicationRestrictions(ADMIN_RECEIVER_COMPONENT, VPN_PACKAGE,
                 restrictions);
-        VpnTestHelper.setAndWaitForVpn(mContext, VPN_PACKAGE, /* usable */ false);
+        VpnTestHelper.waitForVpn(mContext, VPN_PACKAGE, /* usable */ false);
         assertFalse(VpnTestHelper.isNetworkVpn(mContext));
     }
 
diff --git a/hostsidetests/devicepolicy/app/DeviceAndProfileOwner/src/com/android/cts/deviceandprofileowner/vpn/VpnTestHelper.java b/hostsidetests/devicepolicy/app/DeviceAndProfileOwner/src/com/android/cts/deviceandprofileowner/vpn/VpnTestHelper.java
index 91b710e..6aeff7b 100644
--- a/hostsidetests/devicepolicy/app/DeviceAndProfileOwner/src/com/android/cts/deviceandprofileowner/vpn/VpnTestHelper.java
+++ b/hostsidetests/devicepolicy/app/DeviceAndProfileOwner/src/com/android/cts/deviceandprofileowner/vpn/VpnTestHelper.java
@@ -16,6 +16,16 @@
 
 package com.android.cts.deviceandprofileowner.vpn;
 
+import static android.system.OsConstants.AF_INET;
+import static android.system.OsConstants.IPPROTO_ICMP;
+import static android.system.OsConstants.POLLIN;
+import static android.system.OsConstants.SOCK_DGRAM;
+
+import static junit.framework.Assert.assertEquals;
+import static junit.framework.Assert.assertNotNull;
+import static junit.framework.Assert.assertTrue;
+import static junit.framework.Assert.fail;
+
 import android.annotation.TargetApi;
 import android.app.admin.DevicePolicyManager;
 import android.content.ComponentName;
@@ -43,14 +53,6 @@
 import java.util.concurrent.CountDownLatch;
 import java.util.concurrent.TimeUnit;
 
-import static android.system.OsConstants.AF_INET;
-import static android.system.OsConstants.IPPROTO_ICMP;
-import static android.system.OsConstants.POLLIN;
-import static android.system.OsConstants.SOCK_DGRAM;
-import static junit.framework.Assert.assertEquals;
-import static junit.framework.Assert.assertTrue;
-import static junit.framework.Assert.fail;
-
 /**
  * Helper class to test vpn status
  */
@@ -70,47 +72,62 @@
     private static final int NETWORK_TIMEOUT_MS = 5000;
     private static final ComponentName ADMIN_RECEIVER_COMPONENT =
             BaseDeviceAdminTest.ADMIN_RECEIVER_COMPONENT;
+    private static final NetworkRequest VPN_NETWORK_REQUEST = new NetworkRequest.Builder()
+            .addTransportType(NetworkCapabilities.TRANSPORT_VPN)
+            .removeCapability(NetworkCapabilities.NET_CAPABILITY_NOT_VPN)
+            .removeCapability(NetworkCapabilities.NET_CAPABILITY_INTERNET)
+            .build();
 
-    public static void setAndWaitForVpn(Context context, String packageName, boolean usable) {
-        ConnectivityManager connectivityManager =
-                context.getSystemService(ConnectivityManager.class);
+    /**
+     * Wait for a VPN app to establish VPN.
+     *
+     * @param context Caller's context.
+     * @param packageName {@code null} if waiting for the existing VPN to connect. Otherwise we set
+     *         this package as the new always-on VPN app and wait for it to connect.
+     * @param usable Whether the resulting VPN tunnel is expected to be usable.
+     */
+    public static void waitForVpn(Context context, String packageName, boolean usable) {
         DevicePolicyManager dpm = context.getSystemService(DevicePolicyManager.class);
+        if (packageName == null) {
+            assertNotNull(dpm.getAlwaysOnVpnPackage(ADMIN_RECEIVER_COMPONENT));
+        }
+
+        ConnectivityManager cm = context.getSystemService(ConnectivityManager.class);
         final CountDownLatch vpnLatch = new CountDownLatch(1);
-        final NetworkRequest request = new NetworkRequest.Builder()
-                .addTransportType(NetworkCapabilities.TRANSPORT_VPN)
-                .removeCapability(NetworkCapabilities.NET_CAPABILITY_NOT_VPN)
-                .removeCapability(NetworkCapabilities.NET_CAPABILITY_INTERNET)
-                .build();
-        final ConnectivityManager.NetworkCallback callback
-                = new ConnectivityManager.NetworkCallback() {
-            @Override
-            public void onAvailable(Network net) {
-                vpnLatch.countDown();
-            }
-        };
-        connectivityManager.registerNetworkCallback(request, callback);
+        final ConnectivityManager.NetworkCallback callback =
+                new ConnectivityManager.NetworkCallback() {
+                    @Override
+                    public void onAvailable(Network net) {
+                        vpnLatch.countDown();
+                    }
+                };
+        cm.registerNetworkCallback(VPN_NETWORK_REQUEST, callback);
+
         try {
-            dpm.setAlwaysOnVpnPackage(ADMIN_RECEIVER_COMPONENT, packageName, true);
-            assertEquals(packageName, dpm.getAlwaysOnVpnPackage(ADMIN_RECEIVER_COMPONENT));
+            if (packageName != null) {
+                dpm.setAlwaysOnVpnPackage(ADMIN_RECEIVER_COMPONENT, packageName, true);
+                assertEquals(packageName, dpm.getAlwaysOnVpnPackage(ADMIN_RECEIVER_COMPONENT));
+            }
             if (!vpnLatch.await(NETWORK_TIMEOUT_MS, TimeUnit.MILLISECONDS)) {
-                fail("Took too long waiting to establish a VPN-backed connection");
+                if (!isNetworkVpn(context)) {
+                    fail("Took too long waiting to establish a VPN-backed connection");
+                }
             }
             Thread.sleep(NETWORK_SETTLE_GRACE_MS);
         } catch (InterruptedException | PackageManager.NameNotFoundException e) {
-            fail("Failed to send ping: " + e);
+            fail("Failed while waiting for VPN: " + e);
         } finally {
-            connectivityManager.unregisterNetworkCallback(callback);
+            cm.unregisterNetworkCallback(callback);
         }
 
         // Do we have a network?
-        NetworkInfo vpnInfo = connectivityManager.getNetworkInfo(ConnectivityManager.TYPE_VPN);
-        assertTrue(vpnInfo != null);
+        NetworkInfo vpnInfo = cm.getNetworkInfo(ConnectivityManager.TYPE_VPN);
+        assertNotNull(vpnInfo);
 
         // Is it usable?
         assertEquals(usable, vpnInfo.isConnected());
     }
 
-
     public static boolean isNetworkVpn(Context context) {
         ConnectivityManager connectivityManager =
                 (ConnectivityManager) context.getSystemService(Context.CONNECTIVITY_SERVICE);
diff --git a/hostsidetests/devicepolicy/src/com/android/cts/devicepolicy/BaseDevicePolicyTest.java b/hostsidetests/devicepolicy/src/com/android/cts/devicepolicy/BaseDevicePolicyTest.java
index 2063104..31e90c3 100644
--- a/hostsidetests/devicepolicy/src/com/android/cts/devicepolicy/BaseDevicePolicyTest.java
+++ b/hostsidetests/devicepolicy/src/com/android/cts/devicepolicy/BaseDevicePolicyTest.java
@@ -769,6 +769,23 @@
         }
     }
 
+    /**
+     * Verifies the lock credential for the given user, which unlocks the user.
+     *
+     * @param credential The credential to verify.
+     * @param userId The id of the user.
+     */
+    protected void verifyUserCredential(String credential, int userId)
+            throws DeviceNotAvailableException {
+        final String credentialArgument = (credential == null || credential.isEmpty())
+                ? "" : ("--old " + credential);
+        String commandOutput = getDevice().executeShellCommand(String.format(
+                "cmd lock_settings verify --user %d %s", userId, credentialArgument));
+        if (!commandOutput.startsWith("Lock credential verified")) {
+            fail("Failed to verify user credential: " + commandOutput);
+        }
+    }
+
     protected void wakeupAndDismissKeyguard() throws Exception {
         executeShellCommand("input keyevent KEYCODE_WAKEUP");
         executeShellCommand("wm dismiss-keyguard");
diff --git a/hostsidetests/devicepolicy/src/com/android/cts/devicepolicy/DeviceAndProfileOwnerTest.java b/hostsidetests/devicepolicy/src/com/android/cts/devicepolicy/DeviceAndProfileOwnerTest.java
index 54c86f6..4b4a575 100644
--- a/hostsidetests/devicepolicy/src/com/android/cts/devicepolicy/DeviceAndProfileOwnerTest.java
+++ b/hostsidetests/devicepolicy/src/com/android/cts/devicepolicy/DeviceAndProfileOwnerTest.java
@@ -284,6 +284,32 @@
     }
 
     @RequiresDevice
+    public void testAlwaysOnVpnAcrossReboot() throws Exception {
+        // Note: Always-on VPN is supported on non-FBE devices as well, and the behavior should be
+        // the same. However we're only testing the FBE case here as we need to set a device
+        // password during the test. This would cause FDE devices (e.g. angler) to prompt for the
+        // password during reboot, which we can't handle easily.
+        if (!mHasFeature || !mSupportsFbe) {
+            return;
+        }
+
+        // Set a password to encrypt the user
+        final String testPassword = "1234";
+        changeUserCredential(testPassword, null /*oldCredential*/, mUserId);
+
+        try {
+            installAppAsUser(VPN_APP_APK, mUserId);
+            executeDeviceTestMethod(".AlwaysOnVpnMultiStageTest", "testAlwaysOnSet");
+            rebootAndWaitUntilReady();
+            verifyUserCredential(testPassword, mUserId);
+            executeDeviceTestMethod(".AlwaysOnVpnMultiStageTest", "testAlwaysOnSetAfterReboot");
+        } finally {
+            changeUserCredential(null /*newCredential*/, testPassword, mUserId);
+            executeDeviceTestMethod(".AlwaysOnVpnMultiStageTest", "testCleanup");
+        }
+    }
+
+    @RequiresDevice
     public void testAlwaysOnVpnPackageUninstalled() throws Exception {
         if (!mHasFeature) {
             return;
diff --git a/hostsidetests/devicepolicy/src/com/android/cts/devicepolicy/MixedManagedProfileOwnerTest.java b/hostsidetests/devicepolicy/src/com/android/cts/devicepolicy/MixedManagedProfileOwnerTest.java
index 4bdeae9..730592a 100644
--- a/hostsidetests/devicepolicy/src/com/android/cts/devicepolicy/MixedManagedProfileOwnerTest.java
+++ b/hostsidetests/devicepolicy/src/com/android/cts/devicepolicy/MixedManagedProfileOwnerTest.java
@@ -119,29 +119,37 @@
         // and profile owners on the primary user.
     }
 
-    /**
-     * Don't require a device for tests that use the network stack on secondary users.
-     */
+    /** VPN tests don't require physical device for managed profile, thus overriding. */
     @Override
     public void testAlwaysOnVpn() throws Exception {
         super.testAlwaysOnVpn();
     }
 
+    /** VPN tests don't require physical device for managed profile, thus overriding. */
     @Override
     public void testAlwaysOnVpnLockDown() throws Exception {
         super.testAlwaysOnVpnLockDown();
     }
 
+    /** VPN tests don't require physical device for managed profile, thus overriding. */
+    @Override
+    public void testAlwaysOnVpnAcrossReboot() throws Exception {
+        super.testAlwaysOnVpnAcrossReboot();
+    }
+
+    /** VPN tests don't require physical device for managed profile, thus overriding. */
     @Override
     public void testAlwaysOnVpnPackageUninstalled() throws Exception {
         super.testAlwaysOnVpnPackageUninstalled();
     }
 
+    /** VPN tests don't require physical device for managed profile, thus overriding. */
     @Override
     public void testAlwaysOnVpnUnsupportedPackage() throws Exception {
         super.testAlwaysOnVpnUnsupportedPackage();
     }
 
+    /** VPN tests don't require physical device for managed profile, thus overriding. */
     @Override
     public void testAlwaysOnVpnUnsupportedPackageReplaced() throws Exception {
         super.testAlwaysOnVpnUnsupportedPackageReplaced();