diff --git a/tests/testapk/Android.bp b/tests/testapk/Android.bp
index 284d706..806592d 100644
--- a/tests/testapk/Android.bp
+++ b/tests/testapk/Android.bp
@@ -47,7 +47,6 @@
     ],
     jni_libs: [
         "MicrodroidTestNativeLib",
-        "MicrodroidTestNativeLibWithLibIcu",
         "MicrodroidIdleNativeLib",
         "MicrodroidEmptyNativeLib",
         "MicrodroidExitNativeLib",
@@ -64,11 +63,22 @@
 
 DATA = [
     ":MicrodroidTestAppUpdated",
+    ":MicrodroidTestHelperAppRelaxedRollbackProtection_correct_V5",
     ":MicrodroidVmShareApp",
     ":test_microdroid_vendor_image",
     ":test_microdroid_vendor_image_unsigned",
 ]
 
+android_test_helper_app {
+    name: "MicrodroidTestHelperAppRelaxedRollbackProtection_correct_V5",
+    defaults: ["MicrodroidTestAppsDefaults"],
+    manifest: "AndroidManifestV5_relaxed_rollback_protection.xml",
+    jni_libs: [
+        "MicrodroidTestNativeLibWithLibIcu",
+    ],
+    min_sdk_version: "33",
+}
+
 android_test {
     name: "MicrodroidTestApp",
     defaults: ["MicrodroidVersionsTestAppDefaults"],
diff --git a/tests/testapk/AndroidManifestV5.xml b/tests/testapk/AndroidManifestV5.xml
index 296c929..2ef1b6b 100644
--- a/tests/testapk/AndroidManifestV5.xml
+++ b/tests/testapk/AndroidManifestV5.xml
@@ -23,6 +23,7 @@
     <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/AndroidManifestV5_relaxed_rollback_protection.xml b/tests/testapk/AndroidManifestV5_relaxed_rollback_protection.xml
new file mode 100644
index 0000000..619d158
--- /dev/null
+++ b/tests/testapk/AndroidManifestV5_relaxed_rollback_protection.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/AndroidTestTemplate.xml b/tests/testapk/AndroidTestTemplate.xml
index 613ce28..6cdf984 100644
--- a/tests/testapk/AndroidTestTemplate.xml
+++ b/tests/testapk/AndroidTestTemplate.xml
@@ -21,6 +21,7 @@
     <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" />
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 58fa262..b492684 100644
--- a/tests/testapk/src/java/com/android/microdroid/test/MicrodroidTests.java
+++ b/tests/testapk/src/java/com/android/microdroid/test/MicrodroidTests.java
@@ -177,6 +177,8 @@
     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 {
@@ -2755,13 +2757,20 @@
     @Test
     public void libIcuIsLoadable() throws Exception {
         assumeSupportedDevice();
-        // This test relies on the test having USE_RELAXED_MICRODROID_ROLLBACK_PROTECTION
+
+        // This test relies on the test apk having USE_RELAXED_MICRODROID_ROLLBACK_PROTECTION
         // permission.
         grantPermission(USE_RELAXED_MICRODROID_ROLLBACK_PROTECTION_PERMISSION);
 
+        Context otherAppCtx =
+                getContext()
+                        .createPackageContext(RELAXED_ROLLBACK_PROTECTION_SCHEME_PACKAGE_NAME, 0);
         VirtualMachineConfig config =
-                newVmConfigBuilderWithPayloadBinary("MicrodroidTestNativeLibWithLibIcu.so")
+                new VirtualMachineConfig.Builder(otherAppCtx)
                         .setDebugLevel(DEBUG_LEVEL_FULL)
+                        .setPayloadBinaryName("MicrodroidTestNativeLibWithLibIcu.so")
+                        .setProtectedVm(isProtectedVm())
+                        .setOs(os())
                         .build();
 
         VirtualMachine vm = forceCreateNewVirtualMachine("test_libicu_is_loadable", config);