diff --git a/apex/Android.bp b/apex/Android.bp
index c875131..ccf34fd 100644
--- a/apex/Android.bp
+++ b/apex/Android.bp
@@ -52,6 +52,9 @@
     java_libs: [
         "android.system.virtualmachine",
     ],
+    apps: [
+        "android.system.virtualmachine.res",
+    ],
     prebuilts: [
         "com.android.virt.init.rc",
         "microdroid.json",
diff --git a/demo/AndroidManifest.xml b/demo/AndroidManifest.xml
index ae4f734..7e1a58d 100644
--- a/demo/AndroidManifest.xml
+++ b/demo/AndroidManifest.xml
@@ -2,6 +2,8 @@
 <manifest xmlns:android="http://schemas.android.com/apk/res/android"
     package="com.android.microdroid.demo">
 
+    <uses-permission android:name="android.permission.MANAGE_VIRTUAL_MACHINE" />
+
     <application
         android:label="MicrodroidDemo"
         android:theme="@style/Theme.MicrodroidDemo">
diff --git a/javalib/Android.bp b/javalib/Android.bp
index f920175..26ad848 100644
--- a/javalib/Android.bp
+++ b/javalib/Android.bp
@@ -20,3 +20,10 @@
     // TODO(jiyong): remove the below once this gets public
     unsafe_ignore_missing_latest_api: true,
 }
+
+android_app {
+    name: "android.system.virtualmachine.res",
+    installable: true,
+    apex_available: ["com.android.virt"],
+    sdk_version: "current",
+}
diff --git a/javalib/AndroidManifest.xml b/javalib/AndroidManifest.xml
new file mode 100644
index 0000000..21857f8
--- /dev/null
+++ b/javalib/AndroidManifest.xml
@@ -0,0 +1,27 @@
+<?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">
+
+  <permission android:name="android.permission.MANAGE_VIRTUAL_MACHINE"
+      android:protectionLevel="normal" />
+
+  <permission android:name="android.permission.DEBUG_VIRTUAL_MACHINE"
+      android:protectionLevel="signature" />
+
+  <application android:hasCode="false" />
+</manifest>
diff --git a/javalib/src/android/system/virtualmachine/VirtualMachine.java b/javalib/src/android/system/virtualmachine/VirtualMachine.java
index 7176486..3baec94 100644
--- a/javalib/src/android/system/virtualmachine/VirtualMachine.java
+++ b/javalib/src/android/system/virtualmachine/VirtualMachine.java
@@ -216,7 +216,8 @@
             throw new VirtualMachineException(this + " is not in stopped state");
         }
         IVirtualizationService service =
-                IVirtualizationService.Stub.asInterface(ServiceManager.getService(SERVICE_NAME));
+                IVirtualizationService.Stub.asInterface(
+                        ServiceManager.waitForService(SERVICE_NAME));
 
         try {
             if (mConsoleReader == null && mConsoleWriter == null) {
diff --git a/virtualizationservice/Android.bp b/virtualizationservice/Android.bp
index 40aa139..a1dba43 100644
--- a/virtualizationservice/Android.bp
+++ b/virtualizationservice/Android.bp
@@ -21,6 +21,7 @@
     prefer_rlib: true,
     rustlibs: [
         "android.system.virtualizationservice-rust",
+        "android.os.permissions_aidl-rust",
         "libandroid_logger",
         "libanyhow",
         "libcommand_fds",
diff --git a/virtualizationservice/src/aidl.rs b/virtualizationservice/src/aidl.rs
index d99d63a..3ebde6f 100644
--- a/virtualizationservice/src/aidl.rs
+++ b/virtualizationservice/src/aidl.rs
@@ -19,6 +19,7 @@
 use crate::payload::make_payload_disk;
 use crate::{Cid, FIRST_GUEST_CID};
 
+use android_os_permissions_aidl::aidl::android::os::IPermissionController;
 use android_system_virtualizationservice::aidl::android::system::virtualizationservice::IVirtualizationService::IVirtualizationService;
 use android_system_virtualizationservice::aidl::android::system::virtualizationservice::DiskImage::DiskImage;
 use android_system_virtualizationservice::aidl::android::system::virtualizationservice::IVirtualMachine::{
@@ -54,10 +55,6 @@
 /// Directory in which to write disk image files used while running VMs.
 pub const TEMPORARY_DIRECTORY: &str = "/data/misc/virtualizationservice";
 
-// TODO(qwandor): Use PermissionController once it is available to Rust.
-/// Only processes running with one of these UIDs are allowed to call debug methods.
-const DEBUG_ALLOWED_UIDS: [u32; 2] = [0, 2000];
-
 /// The list of APEXes which microdroid requires.
 /// TODO(b/192200378) move this to microdroid.json?
 const MICRODROID_REQUIRED_APEXES: [&str; 3] =
@@ -87,6 +84,7 @@
         config: &VirtualMachineConfig,
         log_fd: Option<&ParcelFileDescriptor>,
     ) -> binder::Result<Strong<dyn IVirtualMachine>> {
+        check_manage_access()?;
         let state = &mut *self.state.lock().unwrap();
         let log_fd = log_fd.map(clone_file).transpose()?;
         let requester_uid = ThreadState::get_calling_uid();
@@ -183,6 +181,7 @@
         image_fd: &ParcelFileDescriptor,
         size: i64,
     ) -> binder::Result<()> {
+        check_manage_access()?;
         let size = size.try_into().map_err(|e| {
             new_binder_exception(
                 ExceptionCode::ILLEGAL_ARGUMENT,
@@ -431,17 +430,36 @@
     })
 }
 
-/// Check whether the caller of the current Binder method is allowed to call debug methods.
-fn check_debug_access() -> binder::Result<()> {
-    let uid = ThreadState::get_calling_uid();
-    log::trace!("Debug method call from UID {}.", uid);
-    if DEBUG_ALLOWED_UIDS.contains(&uid) {
+/// Checks whether the caller has a specific permission
+fn check_permission(perm: &str) -> binder::Result<()> {
+    let calling_pid = ThreadState::get_calling_pid();
+    let calling_uid = ThreadState::get_calling_uid();
+    // Root can do anything
+    if calling_uid == 0 {
+        return Ok(());
+    }
+    let perm_svc: Strong<dyn IPermissionController::IPermissionController> =
+        binder::get_interface("permission")?;
+    if perm_svc.checkPermission(perm, calling_pid, calling_uid as i32)? {
         Ok(())
     } else {
-        Err(new_binder_exception(ExceptionCode::SECURITY, "Debug access denied"))
+        Err(new_binder_exception(
+            ExceptionCode::SECURITY,
+            format!("does not have the {} permission", perm),
+        ))
     }
 }
 
+/// Check whether the caller of the current Binder method is allowed to call debug methods.
+fn check_debug_access() -> binder::Result<()> {
+    check_permission("android.permission.DEBUG_VIRTUAL_MACHINE")
+}
+
+/// Check whether the caller of the current Binder method is allowed to manage VMs
+fn check_manage_access() -> binder::Result<()> {
+    check_permission("android.permission.MANAGE_VIRTUAL_MACHINE")
+}
+
 /// Implementation of the AIDL `IVirtualMachine` interface. Used as a handle to a VM.
 #[derive(Debug)]
 struct VirtualMachine {
@@ -459,10 +477,14 @@
 
 impl IVirtualMachine for VirtualMachine {
     fn getCid(&self) -> binder::Result<i32> {
+        // Don't check permission. The owner of the VM might have passed this binder object to
+        // others.
         Ok(self.instance.cid as i32)
     }
 
     fn isRunning(&self) -> binder::Result<bool> {
+        // Don't check permission. The owner of the VM might have passed this binder object to
+        // others.
         Ok(self.instance.running())
     }
 
@@ -470,6 +492,9 @@
         &self,
         callback: &Strong<dyn IVirtualMachineCallback>,
     ) -> binder::Result<()> {
+        // Don't check permission. The owner of the VM might have passed this binder object to
+        // others.
+        //
         // TODO: Should this give an error if the VM is already dead?
         self.instance.callbacks.add(callback.clone());
         Ok(())