diff --git a/android/android.system.virtualmachine.res/Android.bp b/android/android.system.virtualmachine.res/Android.bp
index 1c55f78..c5d2dbb 100644
--- a/android/android.system.virtualmachine.res/Android.bp
+++ b/android/android.system.virtualmachine.res/Android.bp
@@ -2,23 +2,11 @@
     default_applicable_licenses: ["Android-Apache-2.0"],
 }
 
-soong_config_module_type {
-    name: "avf_flag_aware_android_app",
-    module_type: "android_app",
-    config_namespace: "ANDROID",
-    bool_variables: ["release_avf_allow_preinstalled_apps"],
-    properties: ["manifest"],
-}
-
 // Defines our permissions
-avf_flag_aware_android_app {
+android_app {
     name: "android.system.virtualmachine.res",
     installable: true,
     apex_available: ["com.android.virt"],
     platform_apis: true,
-    soong_config_variables: {
-        release_avf_allow_preinstalled_apps: {
-            manifest: "AndroidManifestNext.xml",
-        },
-    },
+    manifest: "AndroidManifest.xml",
 }
diff --git a/android/android.system.virtualmachine.res/AndroidManifest.xml b/android/android.system.virtualmachine.res/AndroidManifest.xml
index 95b9cfa..c38d2b1 100644
--- a/android/android.system.virtualmachine.res/AndroidManifest.xml
+++ b/android/android.system.virtualmachine.res/AndroidManifest.xml
@@ -20,11 +20,11 @@
   <!-- @SystemApi Allows an application to create and run a Virtual Machine
        using the Virtualization Framework APIs
        (android.system.virtualmachine.*).
-       <p>Protection level: signature|privileged|development
+       <p>Protection level: signature|preinstalled|development
        @hide
   -->
   <permission android:name="android.permission.MANAGE_VIRTUAL_MACHINE"
-      android:protectionLevel="signature|privileged|development" />
+      android:protectionLevel="signature|preinstalled|development" />
 
   <!-- @hide Allows an application to run a Virtual Machine with a custom
        kernel or a Microdroid configuration file.
@@ -40,5 +40,14 @@
   <permission android:name="android.permission.DEBUG_VIRTUAL_MACHINE"
       android:protectionLevel="signature" />
 
+  <!-- @hide Makes Microdroid pVM use a more relaxed rollback protection scheme.
+    Should only be used by payloads delivered inside Mainline modules.
+    See packages/modules/Virtualization/docs/mainline_module_payload.md.
+    <p>Protection level: signature|development|privileged
+  -->
+  <permission android:name="android.permission.USE_RELAXED_MICRODROID_ROLLBACK_PROTECTION"
+      android:protectionLevel="signature|development|privileged" />
+
+
   <application android:hasCode="false" />
 </manifest>
diff --git a/android/android.system.virtualmachine.res/AndroidManifestNext.xml b/android/android.system.virtualmachine.res/AndroidManifestNext.xml
deleted file mode 100644
index ebcb8ba..0000000
--- a/android/android.system.virtualmachine.res/AndroidManifestNext.xml
+++ /dev/null
@@ -1,44 +0,0 @@
-<?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.virtualmachine.res">
-
-  <!-- @SystemApi Allows an application to create and run a Virtual Machine
-       using the Virtualization Framework APIs
-       (android.system.virtualmachine.*).
-       <p>Protection level: signature|preinstalled|development
-       @hide
-  -->
-  <permission android:name="android.permission.MANAGE_VIRTUAL_MACHINE"
-      android:protectionLevel="signature|preinstalled|development" />
-
-  <!-- @hide Allows an application to run a Virtual Machine with a custom
-       kernel or a Microdroid configuration file.
-       <p>Not for use by third-party applications.
-  -->
-  <permission android:name="android.permission.USE_CUSTOM_VIRTUAL_MACHINE"
-      android:protectionLevel="signature|development" />
-
-  <!-- @hide Allows an application to access various Virtual Machine debug
-       facilities, e.g. list all running VMs.
-       <p>Not for use by third-party applications.
-  -->
-  <permission android:name="android.permission.DEBUG_VIRTUAL_MACHINE"
-      android:protectionLevel="signature" />
-
-  <application android:hasCode="false" />
-</manifest>
diff --git a/android/virtmgr/src/aidl.rs b/android/virtmgr/src/aidl.rs
index 33f3be1..2d31b87 100644
--- a/android/virtmgr/src/aidl.rs
+++ b/android/virtmgr/src/aidl.rs
@@ -71,7 +71,7 @@
 use glob::glob;
 use libc::{AF_VSOCK, sa_family_t, sockaddr_vm};
 use log::{debug, error, info, warn};
-use microdroid_payload_config::{ApkConfig, Task, TaskType, VmPayloadConfig};
+use microdroid_payload_config::{ApexConfig, ApkConfig, Task, TaskType, VmPayloadConfig};
 use nix::unistd::pipe;
 use rpcbinder::RpcServer;
 use rustutils::system_properties;
@@ -1409,7 +1409,19 @@
     let extra_apks =
         (0..extra_apk_count).map(|i| ApkConfig { path: format!("extra-apk-{i}") }).collect();
 
-    Ok(VmPayloadConfig { task: Some(task), extra_apks, ..Default::default() })
+    if check_use_relaxed_microdroid_rollback_protection().is_ok() {
+        // The only payload delivered via Mainline module in this release requires
+        // com.android.i18n apex. However, we are past all the reasonable deadlines to add new
+        // APIs, so we use the fact that the payload is granted
+        // USE_RELAXED_MICRODROID_ROLLBACK_PROTECTION permission as a signal that we should include
+        // com.android.i18n APEX.
+        // TODO: remove this after we provide a stable @SystemApi to load additional APEXes to
+        // Microdroid pVMs.
+        let apexes = vec![ApexConfig { name: String::from("com.android.i18n") }];
+        Ok(VmPayloadConfig { task: Some(task), apexes, extra_apks, ..Default::default() })
+    } else {
+        Ok(VmPayloadConfig { task: Some(task), extra_apks, ..Default::default() })
+    }
 }
 
 /// Generates a unique filename to use for a composite disk image.
@@ -1469,6 +1481,12 @@
     check_permission("android.permission.USE_CUSTOM_VIRTUAL_MACHINE")
 }
 
+/// Check whether the caller of the current binder method is allowed to use relaxed microdroid
+/// rollback protection schema.
+fn check_use_relaxed_microdroid_rollback_protection() -> binder::Result<()> {
+    check_permission("android.permission.USE_RELAXED_MICRODROID_ROLLBACK_PROTECTION")
+}
+
 /// Return whether a partition is exempt from selinux label checks, because we know that it does
 /// not contain code and is likely to be generated in an app-writable directory.
 fn is_safe_app_partition(label: &str) -> bool {
diff --git a/build/microdroid/init.rc b/build/microdroid/init.rc
index 672f47d..ce26a35 100644
--- a/build/microdroid/init.rc
+++ b/build/microdroid/init.rc
@@ -35,6 +35,16 @@
     # (In Android this happens inside apexd-bootstrap.)
     wait_for_prop ro.cold_boot_done true
 
+    # We need to define ANDROID_TZDATA_ROOT otherwise libicu complains.
+    # For now set it to a non-existent value, because libicu APIs that don't depend on tzdata work
+    # correctly without it.
+    # Once loading tzdata APEX is supported, we can set this value to /apex/com.android.tzdata.
+    # This is no-op for most microdroid VMs, and is only used if com.android.i18n APEX was mounted.
+    export ANDROID_TZDATA_ROOT /does/not/exist
+    # Set ANDROID_I18N_ROOT otherwise libicu will complain.
+    # This is no-op for most microdroid VMs, and is only used if com.android.i18n APEX was mounted.
+    export ANDROID_I18N_ROOT /apex/com.android.i18n
+
 on init
     mkdir /mnt/apk 0755 root root
     mkdir /mnt/extra-apk 0755 root root
diff --git a/docs/mainline_module_payload.md b/docs/mainline_module_payload.md
new file mode 100644
index 0000000..84617f0
--- /dev/null
+++ b/docs/mainline_module_payload.md
@@ -0,0 +1,19 @@
+# Delivery Microdroid pVM payload via Mainline modules
+
+There are several additional challenges when a Microdroid pVM payload is
+delivered inside a Mainline module.
+
+## Mainline rollbacks
+
+Mainline modules are expected to be rolled back on a device in case a problem
+with a Mainline release has been detected. This doesn't work well with the
+rollback protection of Microdroid pVMs - if a payload is updated, then a
+previous version of the payload is not allowed to access it's secrets.
+
+To work around this challenge, payloads delivered via Mainline modules are
+expected to request
+`android.permission.USE_RELAXED_MICRODROID_ROLLBACK_PROTECTION` privileged
+permission.
+
+TODO(ioffe): add more context on how permission is used once the implementation
+is done.
diff --git a/tests/aidl/com/android/microdroid/testservice/ITestService.aidl b/tests/aidl/com/android/microdroid/testservice/ITestService.aidl
index 6a413d6..4c824f0 100644
--- a/tests/aidl/com/android/microdroid/testservice/ITestService.aidl
+++ b/tests/aidl/com/android/microdroid/testservice/ITestService.aidl
@@ -104,4 +104,9 @@
      * @return true on the first boot of the instance & false on subsequent boot.
      */
     boolean isNewInstance();
+
+    /**
+     * Checks that libicu is accessible to the payload that has com.android.i18n APEX mounted.
+     */
+    void checkLibIcuIsAccessible();
 }
diff --git a/tests/testapk/Android.bp b/tests/testapk/Android.bp
index 99300e2..806592d 100644
--- a/tests/testapk/Android.bp
+++ b/tests/testapk/Android.bp
@@ -63,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"],
@@ -188,6 +199,17 @@
 }
 
 cc_library_shared {
+    name: "MicrodroidTestNativeLibWithLibIcu",
+    defaults: ["MicrodroidTestNativeLibDefaults"],
+    shared_libs: [
+        "libicu",
+    ],
+    cflags: [
+        "-D__MICRODROID_TEST_PAYLOAD_USES_LIBICU__",
+    ],
+}
+
+cc_library_shared {
     name: "MicrodroidTestNativeLibSub",
     defaults: ["avf_build_flags_cc"],
     srcs: ["src/native/testlib.cpp"],
diff --git a/tests/testapk/AndroidManifestV5.xml b/tests/testapk/AndroidManifestV5.xml
index 7d97680..2ef1b6b 100644
--- a/tests/testapk/AndroidManifestV5.xml
+++ b/tests/testapk/AndroidManifestV5.xml
@@ -18,10 +18,12 @@
       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>
         <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/AndroidManifestV6.xml b/tests/testapk/AndroidManifestV6.xml
index 19d5674..7dd0663 100644
--- a/tests/testapk/AndroidManifestV6.xml
+++ b/tests/testapk/AndroidManifestV6.xml
@@ -18,6 +18,7 @@
       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>
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 3ece140..b492684 100644
--- a/tests/testapk/src/java/com/android/microdroid/test/MicrodroidTests.java
+++ b/tests/testapk/src/java/com/android/microdroid/test/MicrodroidTests.java
@@ -130,6 +130,9 @@
     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";
+
     @Rule public Timeout globalTimeout = Timeout.seconds(300);
 
     @Parameterized.Parameters(name = "protectedVm={0},os={1}")
@@ -163,15 +166,19 @@
             // 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);
     }
     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 {
@@ -2747,6 +2754,39 @@
         assertThat(testResults.mPageSize).isEqualTo(expectedPageSize);
     }
 
+    @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);
+
+        Context otherAppCtx =
+                getContext()
+                        .createPackageContext(RELAXED_ROLLBACK_PROTECTION_SCHEME_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();
+    }
+
     private static class VmShareServiceConnection implements ServiceConnection {
 
         private final CountDownLatch mLatch = new CountDownLatch(1);
diff --git a/tests/testapk/src/native/testbinary.cpp b/tests/testapk/src/native/testbinary.cpp
index 2ab73a4..355cfb1 100644
--- a/tests/testapk/src/native/testbinary.cpp
+++ b/tests/testapk/src/native/testbinary.cpp
@@ -30,6 +30,9 @@
 #include <stdio.h>
 #include <sys/capability.h>
 #include <sys/system_properties.h>
+#ifdef __MICRODROID_TEST_PAYLOAD_USES_LIBICU__
+#include <unicode/uchar.h>
+#endif
 #include <unistd.h>
 #include <vm_main.h>
 #include <vm_payload_restricted.h>
@@ -384,6 +387,29 @@
             }
         }
 
+        ScopedAStatus checkLibIcuIsAccessible() override {
+#ifdef __MICRODROID_TEST_PAYLOAD_USES_LIBICU__
+            static constexpr const char* kLibIcuPath = "/apex/com.android.i18n/lib64/libicu.so";
+            if (access(kLibIcuPath, R_OK) == 0) {
+                if (!u_hasBinaryProperty(U'❤' /* Emoji heart U+2764 */, UCHAR_EMOJI)) {
+                    return ScopedAStatus::fromExceptionCodeWithMessage(EX_SERVICE_SPECIFIC,
+                                                                       "libicu broken!");
+                }
+                return ScopedAStatus::ok();
+            } else {
+                std::string msg = "failed to access " + std::string(kLibIcuPath) + "(" +
+                        std::to_string(errno) + ")";
+                return ScopedAStatus::fromExceptionCodeWithMessage(EX_SERVICE_SPECIFIC,
+                                                                   msg.c_str());
+            }
+#else
+            return ScopedAStatus::
+                    fromExceptionCodeWithMessage(EX_SERVICE_SPECIFIC,
+                                                 "should be only used together with "
+                                                 "MicrodroidTestNativeLibWithLibIcu.so payload");
+#endif
+        }
+
         ScopedAStatus quit() override { exit(0); }
     };
     auto testService = ndk::SharedRefBase::make<TestService>();
diff --git a/tests/testapk/src/native/testbinary.rs b/tests/testapk/src/native/testbinary.rs
index c9d46b8..3900cad 100644
--- a/tests/testapk/src/native/testbinary.rs
+++ b/tests/testapk/src/native/testbinary.rs
@@ -135,6 +135,9 @@
     fn isNewInstance(&self) -> BinderResult<bool> {
         unimplemented()
     }
+    fn checkLibIcuIsAccessible(&self) -> BinderResult<()> {
+        unimplemented()
+    }
 }
 
 fn unimplemented<T>() -> BinderResult<T> {
diff --git a/tests/vmshareapp/src/java/com/android/microdroid/test/sharevm/VmShareServiceImpl.java b/tests/vmshareapp/src/java/com/android/microdroid/test/sharevm/VmShareServiceImpl.java
index 1f71888..7f44fa5 100644
--- a/tests/vmshareapp/src/java/com/android/microdroid/test/sharevm/VmShareServiceImpl.java
+++ b/tests/vmshareapp/src/java/com/android/microdroid/test/sharevm/VmShareServiceImpl.java
@@ -291,5 +291,10 @@
         public boolean isNewInstance() {
             throw new UnsupportedOperationException("Not supported");
         }
+
+        @Override
+        public void checkLibIcuIsAccessible() {
+            throw new UnsupportedOperationException("Not supported");
+        }
     }
 }