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/AndroidManifestV5.xml b/tests/testapk/AndroidManifestV5.xml
index 7d97680..296c929 100644
--- a/tests/testapk/AndroidManifestV5.xml
+++ b/tests/testapk/AndroidManifestV5.xml
@@ -18,6 +18,7 @@
       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/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/src/java/com/android/microdroid/test/MicrodroidTests.java b/tests/testapk/src/java/com/android/microdroid/test/MicrodroidTests.java
index 3ece140..e2379d7 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,11 +166,13 @@
             // 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!! :)";
 
@@ -2747,6 +2752,32 @@
         assertThat(testResults.mPageSize).isEqualTo(expectedPageSize);
     }
 
+    @Test
+    public void libIcuIsLoadable() throws Exception {
+        assumeSupportedDevice();
+        // This test relies on the test having USE_RELAXED_MICRODROID_ROLLBACK_PROTECTION
+        // permission.
+        grantPermission(USE_RELAXED_MICRODROID_ROLLBACK_PROTECTION_PERMISSION);
+
+        VirtualMachineConfig config =
+                newVmConfigBuilderWithPayloadBinary("MicrodroidTestNativeLib.so")
+                        .setDebugLevel(DEBUG_LEVEL_FULL)
+                        .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..c3904b7 100644
--- a/tests/testapk/src/native/testbinary.cpp
+++ b/tests/testapk/src/native/testbinary.cpp
@@ -384,6 +384,20 @@
             }
         }
 
+        ScopedAStatus checkLibIcuIsAccessible() override {
+            static constexpr const char* kLibIcuPath = "/apex/com.android.i18n/lib64/libicu.so";
+            if (access(kLibIcuPath, R_OK) == 0) {
+                // TODO(ioffe): call an API provided by libicu.so and check that it returns expected
+                // value.
+                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());
+            }
+        }
+
         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");
+        }
     }
 }