diff --git a/tests/testapk/Android.bp b/tests/testapk/Android.bp
index 806592d..0ffab5d 100644
--- a/tests/testapk/Android.bp
+++ b/tests/testapk/Android.bp
@@ -64,6 +64,8 @@
 DATA = [
     ":MicrodroidTestAppUpdated",
     ":MicrodroidTestHelperAppRelaxedRollbackProtection_correct_V5",
+    ":MicrodroidTestHelperAppRelaxedRollbackProtection_no_permission",
+    ":MicrodroidTestHelperAppRelaxedRollbackProtection_no_rollback_index",
     ":MicrodroidVmShareApp",
     ":test_microdroid_vendor_image",
     ":test_microdroid_vendor_image_unsigned",
@@ -74,6 +76,29 @@
     defaults: ["MicrodroidTestAppsDefaults"],
     manifest: "AndroidManifestV5_relaxed_rollback_protection.xml",
     jni_libs: [
+        "MicrodroidTestNativeLib",
+        "MicrodroidTestNativeLibWithLibIcu",
+    ],
+    min_sdk_version: "33",
+}
+
+android_test_helper_app {
+    name: "MicrodroidTestHelperAppRelaxedRollbackProtection_no_rollback_index",
+    defaults: ["MicrodroidTestAppsDefaults"],
+    manifest: "AndroidManifestV5_relaxed_rollback_protection_no_rollback_index.xml",
+    jni_libs: [
+        "MicrodroidTestNativeLib",
+        "MicrodroidTestNativeLibWithLibIcu",
+    ],
+    min_sdk_version: "33",
+}
+
+android_test_helper_app {
+    name: "MicrodroidTestHelperAppRelaxedRollbackProtection_no_permission",
+    defaults: ["MicrodroidTestAppsDefaults"],
+    manifest: "AndroidManifestV5_relaxed_rollback_protection_no_permission.xml",
+    jni_libs: [
+        "MicrodroidTestNativeLib",
         "MicrodroidTestNativeLibWithLibIcu",
     ],
     min_sdk_version: "33",
diff --git a/tests/testapk/AndroidManifestV5.xml b/tests/testapk/AndroidManifestV5.xml
index 2ef1b6b..f80edac 100644
--- a/tests/testapk/AndroidManifestV5.xml
+++ b/tests/testapk/AndroidManifestV5.xml
@@ -18,7 +18,6 @@
       android:versionCode="5">
     <uses-permission android:name="android.permission.MANAGE_VIRTUAL_MACHINE" />
     <uses-permission android:name="android.permission.USE_CUSTOM_VIRTUAL_MACHINE" />
-    <uses-permission android:name="android.permission.USE_RELAXED_MICRODROID_ROLLBACK_PROTECTION" />
     <uses-sdk android:minSdkVersion="33" android:targetSdkVersion="33" />
     <uses-feature android:name="android.software.virtualization_framework" android:required="false" />
     <queries>
diff --git a/tests/testapk/AndroidManifestV5_relaxed_rollback_protection.xml b/tests/testapk/AndroidManifestV5_relaxed_rollback_protection.xml
index 619d158..16c585a 100644
--- a/tests/testapk/AndroidManifestV5_relaxed_rollback_protection.xml
+++ b/tests/testapk/AndroidManifestV5_relaxed_rollback_protection.xml
@@ -1,5 +1,5 @@
 <?xml version="1.0" encoding="utf-8"?>
-<!-- Copyright (C) 2021 The Android Open Source Project
+<!-- Copyright (C) 2025 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.
@@ -15,11 +15,13 @@
 -->
 <manifest xmlns:android="http://schemas.android.com/apk/res/android"
       package="com.android.microdroid.test_relaxed_rollback_protection_scheme"
-      android:versionCode="5">
+      android:versionCode="5" >
     <uses-permission android:name="android.permission.MANAGE_VIRTUAL_MACHINE" />
     <uses-permission android:name="android.permission.USE_CUSTOM_VIRTUAL_MACHINE" />
     <uses-permission android:name="android.permission.USE_RELAXED_MICRODROID_ROLLBACK_PROTECTION" />
     <uses-sdk android:minSdkVersion="33" android:targetSdkVersion="33" />
     <uses-feature android:name="android.software.virtualization_framework" android:required="false" />
-    <application />
+    <application>
+        <property android:name="android.system.virtualmachine.ROLLBACK_INDEX" android:value="1" />
+    </application>
 </manifest>
diff --git a/tests/testapk/AndroidManifestV5_relaxed_rollback_protection_no_permission.xml b/tests/testapk/AndroidManifestV5_relaxed_rollback_protection_no_permission.xml
new file mode 100644
index 0000000..91de2a0
--- /dev/null
+++ b/tests/testapk/AndroidManifestV5_relaxed_rollback_protection_no_permission.xml
@@ -0,0 +1,26 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!-- Copyright (C) 2021 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.
+-->
+<manifest xmlns:android="http://schemas.android.com/apk/res/android"
+      package="com.android.microdroid.test_relaxed_rollback_protection_scheme"
+      android:versionCode="5" >
+    <uses-permission android:name="android.permission.MANAGE_VIRTUAL_MACHINE" />
+    <uses-permission android:name="android.permission.USE_CUSTOM_VIRTUAL_MACHINE" />
+    <uses-sdk android:minSdkVersion="33" android:targetSdkVersion="33" />
+    <uses-feature android:name="android.software.virtualization_framework" android:required="false" />
+    <application>
+        <property android:name="android.system.virtualmachine.ROLLBACK_INDEX" android:value="1" />
+    </application>
+</manifest>
diff --git a/tests/testapk/AndroidManifestV5_relaxed_rollback_protection_no_rollback_index.xml b/tests/testapk/AndroidManifestV5_relaxed_rollback_protection_no_rollback_index.xml
new file mode 100644
index 0000000..3d6d734
--- /dev/null
+++ b/tests/testapk/AndroidManifestV5_relaxed_rollback_protection_no_rollback_index.xml
@@ -0,0 +1,25 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!-- Copyright (C) 2021 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.
+-->
+<manifest xmlns:android="http://schemas.android.com/apk/res/android"
+      package="com.android.microdroid.test_relaxed_rollback_protection_scheme"
+      android:versionCode="5" >
+    <uses-permission android:name="android.permission.MANAGE_VIRTUAL_MACHINE" />
+    <uses-permission android:name="android.permission.USE_CUSTOM_VIRTUAL_MACHINE" />
+    <uses-permission android:name="android.permission.USE_RELAXED_MICRODROID_ROLLBACK_PROTECTION" />
+    <uses-sdk android:minSdkVersion="33" android:targetSdkVersion="33" />
+    <uses-feature android:name="android.software.virtualization_framework" android:required="false" />
+    <application />
+</manifest>
diff --git a/tests/testapk/AndroidManifestV6.xml b/tests/testapk/AndroidManifestV6.xml
index 7dd0663..2115ef7 100644
--- a/tests/testapk/AndroidManifestV6.xml
+++ b/tests/testapk/AndroidManifestV6.xml
@@ -18,11 +18,11 @@
       android:versionCode="6">
     <uses-permission android:name="android.permission.MANAGE_VIRTUAL_MACHINE" />
     <uses-permission android:name="android.permission.USE_CUSTOM_VIRTUAL_MACHINE" />
-    <uses-permission android:name="android.permission.USE_RELAXED_MICRODROID_ROLLBACK_PROTECTION" />
     <uses-sdk android:minSdkVersion="33" android:targetSdkVersion="33" />
     <uses-feature android:name="android.software.virtualization_framework" android:required="false" />
     <queries>
         <package android:name="com.android.microdroid.vmshare_app" />
+        <package android:name="com.android.microdroid.test_relaxed_rollback_protection_scheme" />
     </queries>
     <application />
     <instrumentation android:name="androidx.test.runner.AndroidJUnitRunner"
diff --git a/tests/testapk/AndroidTestTemplate.xml b/tests/testapk/AndroidTestTemplate.xml
index 6cdf984..5ed7a07 100644
--- a/tests/testapk/AndroidTestTemplate.xml
+++ b/tests/testapk/AndroidTestTemplate.xml
@@ -21,7 +21,6 @@
     <target_preparer class="com.android.tradefed.targetprep.suite.SuiteApkInstaller">
         <option name="test-file-name" value="{MODULE}.apk" />
         <option name="test-file-name" value="MicrodroidVmShareApp.apk" />
-        <option name="test-file-name" value="MicrodroidTestHelperAppRelaxedRollbackProtection_correct_V5.apk" />
     </target_preparer>
     <target_preparer class="com.android.tradefed.targetprep.RunCommandTargetPreparer">
         <option name="run-command" value="mkdir -p /data/local/tmp/cts/microdroid" />
@@ -31,6 +30,9 @@
         <option name="cleanup" value="true" />
         <option name="push" value="test_microdroid_vendor_image.img->/data/local/tmp/cts/microdroid/test_microdroid_vendor_image.img" />
         <option name="push" value="test_microdroid_vendor_image_unsigned.img->/data/local/tmp/cts/microdroid/test_microdroid_vendor_image_unsigned.img" />
+        <option name="push" value="MicrodroidTestHelperAppRelaxedRollbackProtection_correct_V5.apk->/data/local/tmp/cts/microdroid/MicrodroidTestHelperAppRelaxedRollbackProtection_correct_V5.apk" />
+        <option name="push" value="MicrodroidTestHelperAppRelaxedRollbackProtection_no_permission.apk->/data/local/tmp/cts/microdroid/MicrodroidTestHelperAppRelaxedRollbackProtection_no_permission.apk" />
+        <option name="push" value="MicrodroidTestHelperAppRelaxedRollbackProtection_no_rollback_index.apk->/data/local/tmp/cts/microdroid/MicrodroidTestHelperAppRelaxedRollbackProtection_no_rollback_index.apk" />
     </target_preparer>
     <test class="com.android.tradefed.testtype.AndroidJUnitTest" >
         <option name="package" value="com.android.microdroid.test" />
diff --git a/tests/testapk/src/java/com/android/microdroid/test/MicrodroidTests.java b/tests/testapk/src/java/com/android/microdroid/test/MicrodroidTests.java
index b492684..521ee9a 100644
--- a/tests/testapk/src/java/com/android/microdroid/test/MicrodroidTests.java
+++ b/tests/testapk/src/java/com/android/microdroid/test/MicrodroidTests.java
@@ -59,6 +59,7 @@
 import android.system.virtualmachine.VirtualMachineDescriptor;
 import android.system.virtualmachine.VirtualMachineException;
 import android.system.virtualmachine.VirtualMachineManager;
+import android.util.Log;
 
 import androidx.test.platform.app.InstrumentationRegistry;
 
@@ -130,8 +131,8 @@
     private static final String VM_ATTESTATION_MESSAGE = "Hello RKP from AVF!";
     private static final int ENCRYPTED_STORAGE_BYTES = 4_000_000;
 
-    private static final String USE_RELAXED_MICRODROID_ROLLBACK_PROTECTION_PERMISSION =
-            "android.permission.USE_RELAXED_MICRODROID_ROLLBACK_PROTECTION";
+    private static final String RELAXED_ROLLBACK_PROTECTION_SCHEME_TEST_PACKAGE_NAME =
+            "com.android.microdroid.test_relaxed_rollback_protection_scheme";
 
     @Rule public Timeout globalTimeout = Timeout.seconds(300);
 
@@ -166,19 +167,18 @@
             // Tests that rely on the state of the permission should explicitly grant or revoke it.
             revokePermission(VirtualMachine.USE_CUSTOM_VIRTUAL_MACHINE_PERMISSION);
         }
-        revokePermission(USE_RELAXED_MICRODROID_ROLLBACK_PROTECTION_PERMISSION);
     }
 
     @After
     public void tearDown() {
         revokePermission(VirtualMachine.USE_CUSTOM_VIRTUAL_MACHINE_PERMISSION);
-        revokePermission(USE_RELAXED_MICRODROID_ROLLBACK_PROTECTION_PERMISSION);
+        // Some tests might install additional apks, so we need to clean them up here.
+        uninstallApp(RELAXED_ROLLBACK_PROTECTION_SCHEME_TEST_PACKAGE_NAME);
     }
+
     private static final String EXAMPLE_STRING = "Literally any string!! :)";
 
     private static final String VM_SHARE_APP_PACKAGE_NAME = "com.android.microdroid.vmshare_app";
-    private static final String RELAXED_ROLLBACK_PROTECTION_SCHEME_PACKAGE_NAME =
-            "com.android.microdroid.test_relaxed_rollback_protection_scheme";
 
     private void createAndConnectToVmHelper(int cpuTopology, boolean shouldUseHugepages)
             throws Exception {
@@ -2754,37 +2754,111 @@
         assertThat(testResults.mPageSize).isEqualTo(expectedPageSize);
     }
 
+    // This test requires MicrodroidTestApp to have USE_RELAXED_MICRODROID_ROLLBACK_PROTECTION
+    // permission. This means that the permission needs to be declared in the AndroidManifest.xml of
+    // the MicrodroidTestApp.apk. Which in turns leads microdroid_manager to enable the relaxed
+    // rollback protection scheme, which we don't want to be enabled for most of the tests here.
+    // For now comment out this test. It will be un-commented (and probably moved to a separate test
+    // apk) in a follow-up patch.
+    // TODO(ioffe): bring this test back!
+    /*
+        @Test
+        public void libIcuIsLoadable() throws Exception {
+            assumeSupportedDevice();
+            // This test relies on the test apk having USE_RELAXED_MICRODROID_ROLLBACK_PROTECTION
+            // permission.
+            grantPermission(USE_RELAXED_MICRODROID_ROLLBACK_PROTECTION_PERMISSION);
+
+            // This test requires additional test apk.
+            installApp("MicrodroidTestHelperAppRelaxedRollbackProtection_correct_V5.apk");
+
+            Context otherAppCtx =
+                    getContext()
+                            .createPackageContext(RELAXED_ROLLBACK_PROTECTION_SCHEME_TEST_PACKAGE_NAME, 0);
+
+            VirtualMachineConfig config =
+                    new VirtualMachineConfig.Builder(otherAppCtx)
+                            .setDebugLevel(DEBUG_LEVEL_FULL)
+                            .setPayloadBinaryName("MicrodroidTestNativeLibWithLibIcu.so")
+                            .setProtectedVm(isProtectedVm())
+                            .setOs(os())
+                            .build();
+
+            VirtualMachine vm = forceCreateNewVirtualMachine("test_libicu_is_loadable", config);
+
+            TestResults testResults =
+                    runVmTestService(
+                            TAG,
+                            vm,
+                            (ts, tr) -> {
+                                ts.checkLibIcuIsAccessible();
+                            });
+
+            // checkLibIcuIsAccessible will throw an exception if something goes wrong.
+            assertThat(testResults.mException).isNull();
+        }
+    */
+
     @Test
-    public void libIcuIsLoadable() throws Exception {
+    public void relaxedRollbackProtectionScheme_apkDoesNotHavePermission_bootFails()
+            throws Exception {
         assumeSupportedDevice();
 
-        // This test relies on the test apk having USE_RELAXED_MICRODROID_ROLLBACK_PROTECTION
-        // permission.
-        grantPermission(USE_RELAXED_MICRODROID_ROLLBACK_PROTECTION_PERMISSION);
+        // This test requires additional test apk.
+        installApp("MicrodroidTestHelperAppRelaxedRollbackProtection_no_permission.apk");
 
         Context otherAppCtx =
                 getContext()
-                        .createPackageContext(RELAXED_ROLLBACK_PROTECTION_SCHEME_PACKAGE_NAME, 0);
+                        .createPackageContext(
+                                RELAXED_ROLLBACK_PROTECTION_SCHEME_TEST_PACKAGE_NAME, 0);
+
         VirtualMachineConfig config =
                 new VirtualMachineConfig.Builder(otherAppCtx)
                         .setDebugLevel(DEBUG_LEVEL_FULL)
-                        .setPayloadBinaryName("MicrodroidTestNativeLibWithLibIcu.so")
+                        .setPayloadBinaryName("MicrodroidTestNativeLib.so")
                         .setProtectedVm(isProtectedVm())
                         .setOs(os())
                         .build();
 
-        VirtualMachine vm = forceCreateNewVirtualMachine("test_libicu_is_loadable", config);
+        VirtualMachine vm =
+                forceCreateNewVirtualMachine(
+                        "test_relaxed_rollback_protection_scheme_no_permission", config);
+        BootResult bootResult =
+                tryBootVm(TAG, "test_relaxed_rollback_protection_scheme_no_permission");
+        assertThat(bootResult.deathReason)
+                .isEqualTo(
+                        VirtualMachineCallback.STOP_REASON_MICRODROID_PAYLOAD_VERIFICATION_FAILED);
+    }
 
-        TestResults testResults =
-                runVmTestService(
-                        TAG,
-                        vm,
-                        (ts, tr) -> {
-                            ts.checkLibIcuIsAccessible();
-                        });
+    @Test
+    public void relaxedRollbackProtectionScheme_apkDoesNotHaveRollbackIndex_bootFails()
+            throws Exception {
+        assumeSupportedDevice();
 
-        // checkLibIcuIsAccessible will throw an exception if something goes wrong.
-        assertThat(testResults.mException).isNull();
+        // This test requires additional test apk.
+        installApp("MicrodroidTestHelperAppRelaxedRollbackProtection_no_rollback_index.apk");
+
+        Context otherAppCtx =
+                getContext()
+                        .createPackageContext(
+                                RELAXED_ROLLBACK_PROTECTION_SCHEME_TEST_PACKAGE_NAME, 0);
+
+        VirtualMachineConfig config =
+                new VirtualMachineConfig.Builder(otherAppCtx)
+                        .setDebugLevel(DEBUG_LEVEL_FULL)
+                        .setPayloadBinaryName("MicrodroidTestNativeLib.so")
+                        .setProtectedVm(isProtectedVm())
+                        .setOs(os())
+                        .build();
+
+        VirtualMachine vm =
+                forceCreateNewVirtualMachine(
+                        "test_relaxed_rollback_protection_scheme_no_rollback_index", config);
+        BootResult bootResult =
+                tryBootVm(TAG, "test_relaxed_rollback_protection_scheme_no_rollback_index");
+        assertThat(bootResult.deathReason)
+                .isEqualTo(
+                        VirtualMachineCallback.STOP_REASON_MICRODROID_PAYLOAD_VERIFICATION_FAILED);
     }
 
     private static class VmShareServiceConnection implements ServiceConnection {
@@ -2881,4 +2955,40 @@
         Exception e = assertThrows(VirtualMachineException.class, runnable);
         assertThat(e).hasMessageThat().contains(expectedContents);
     }
+
+    private void installApp(String apkName) throws Exception {
+        String apkFile = new File("/data/local/tmp/cts/microdroid/", apkName).getAbsolutePath();
+        UiAutomation uai = InstrumentationRegistry.getInstrumentation().getUiAutomation();
+        Log.i(TAG, "Installing apk " + apkFile);
+        // We read the output of the shell command not only to see if it succeeds, but also to make
+        // sure that the installation finishes. This avoids a race condition when test tries to
+        // create a context of the installed package before the installation finished.
+        try (ParcelFileDescriptor pfd = uai.executeShellCommand("pm install " + apkFile)) {
+            try (InputStream is = new FileInputStream(pfd.getFileDescriptor())) {
+                try (BufferedReader br = new BufferedReader(new InputStreamReader(is))) {
+                    String line;
+                    while ((line = br.readLine()) != null) {
+                        Log.i(TAG, line);
+                    }
+                }
+            }
+        }
+    }
+
+    private void uninstallApp(String packageName) {
+        Log.i(TAG, "Uninstalling package " + packageName);
+        UiAutomation uai = InstrumentationRegistry.getInstrumentation().getUiAutomation();
+        try (ParcelFileDescriptor pfd = uai.executeShellCommand("pm uninstall " + packageName)) {
+            try (InputStream is = new FileInputStream(pfd.getFileDescriptor())) {
+                try (BufferedReader br = new BufferedReader(new InputStreamReader(is))) {
+                    String line;
+                    while ((line = br.readLine()) != null) {
+                        Log.i(TAG, line);
+                    }
+                }
+            }
+        } catch (Exception e) {
+            Log.e(TAG, "Failed to uninstall " + packageName, e);
+        }
+    }
 }