diff --git a/virtualizationservice/Android.bp b/virtualizationservice/Android.bp
index a941742..c209f10 100644
--- a/virtualizationservice/Android.bp
+++ b/virtualizationservice/Android.bp
@@ -31,6 +31,7 @@
         "libmicrodroid_payload_config",
         "libprotobuf",
         "libprotos",
+        "libregex",
         "libserde_json",
         "libserde",
         "libshared_child",
diff --git a/virtualizationservice/src/aidl.rs b/virtualizationservice/src/aidl.rs
index b841ad0..5c0c3b8 100644
--- a/virtualizationservice/src/aidl.rs
+++ b/virtualizationservice/src/aidl.rs
@@ -16,7 +16,7 @@
 
 use crate::composite::make_composite_image;
 use crate::crosvm::{CrosvmConfig, DiskFile, VmInstance};
-use crate::payload;
+use crate::payload::{make_payload_disk, ApexInfoList};
 use crate::{Cid, FIRST_GUEST_CID};
 
 use android_system_virtualizationservice::aidl::android::system::virtualizationservice::IVirtualizationService::IVirtualizationService;
@@ -62,9 +62,19 @@
     ["com.android.adbd", "com.android.i18n", "com.android.os.statsd", "com.android.sdkext"];
 
 /// Implementation of `IVirtualizationService`, the entry point of the AIDL service.
-#[derive(Debug, Default)]
+#[derive(Debug)]
 pub struct VirtualizationService {
     state: Mutex<State>,
+    apex_info_list: ApexInfoList,
+}
+
+impl VirtualizationService {
+    pub fn new() -> Result<VirtualizationService> {
+        Ok(VirtualizationService {
+            state: Default::default(),
+            apex_info_list: ApexInfoList::load()?,
+        })
+    }
 }
 
 impl Interface for VirtualizationService {}
@@ -109,13 +119,15 @@
 
         let config = match config {
             VirtualMachineConfig::AppConfig(config) => BorrowedOrOwned::Owned(
-                load_app_config(config, &temporary_directory).map_err(|e| {
-                    error!("Failed to load app config from {}: {}", &config.configPath, e);
-                    new_binder_exception(
-                        ExceptionCode::SERVICE_SPECIFIC,
-                        format!("Failed to load app config from {}: {}", &config.configPath, e),
-                    )
-                })?,
+                load_app_config(&self.apex_info_list, config, &temporary_directory).map_err(
+                    |e| {
+                        error!("Failed to load app config from {}: {}", &config.configPath, e);
+                        new_binder_exception(
+                            ExceptionCode::SERVICE_SPECIFIC,
+                            format!("Failed to load app config from {}: {}", &config.configPath, e),
+                        )
+                    },
+                )?,
             ),
             VirtualMachineConfig::RawConfig(config) => BorrowedOrOwned::Borrowed(config),
         };
@@ -286,6 +298,7 @@
 }
 
 fn load_app_config(
+    apex_info_list: &ApexInfoList,
     config: &VirtualMachineAppConfig,
     temporary_directory: &Path,
 ) -> Result<VirtualMachineRawConfig> {
@@ -314,7 +327,8 @@
         );
         apexes.dedup_by(|a, b| a.name == b.name);
 
-        vm_config.disks.push(payload::make_disk_image(
+        vm_config.disks.push(make_payload_disk(
+            apex_info_list,
             format!("/proc/self/fd/{}", apk_file.as_raw_fd()).into(),
             format!("/proc/self/fd/{}", idsig_file.as_raw_fd()).into(),
             config_path,
diff --git a/virtualizationservice/src/main.rs b/virtualizationservice/src/main.rs
index 658203b..3f2e99c 100644
--- a/virtualizationservice/src/main.rs
+++ b/virtualizationservice/src/main.rs
@@ -39,7 +39,7 @@
         android_logger::Config::default().with_tag(LOG_TAG).with_min_level(Level::Trace),
     );
 
-    let service = VirtualizationService::default();
+    let service = VirtualizationService::new().unwrap();
     let service = BnVirtualizationService::new_binder(
         service,
         BinderFeatures { set_requesting_sid: true, ..BinderFeatures::default() },
diff --git a/virtualizationservice/src/payload.rs b/virtualizationservice/src/payload.rs
index b6e9c04..d3dc289 100644
--- a/virtualizationservice/src/payload.rs
+++ b/virtualizationservice/src/payload.rs
@@ -16,21 +16,66 @@
 
 use crate::composite::align_to_partition_size;
 
-use anyhow::Result;
+use anyhow::{anyhow, Result};
 use microdroid_metadata::{ApexPayload, ApkPayload, Metadata};
 use microdroid_payload_config::ApexConfig;
+use regex::Regex;
 use std::fs;
 use std::fs::OpenOptions;
-use std::io::{Seek, SeekFrom, Write};
+use std::io::{BufRead, BufReader, Seek, SeekFrom, Write};
 use std::path::{Path, PathBuf};
 use std::process::Command;
 use vmconfig::{DiskImage, Partition};
 
-// TODO(b/191601801): look up /apex/apex-info-list.xml
-fn get_path(package_name: &str) -> Result<PathBuf> {
-    let output = Command::new("pm").arg("path").arg(package_name).output()?;
-    let output = String::from_utf8(output.stdout)?;
-    Ok(PathBuf::from(output.strip_prefix("package:").unwrap().trim()))
+/// Represents the list of APEXes
+#[derive(Debug)]
+pub struct ApexInfoList {
+    list: Vec<ApexInfo>,
+}
+
+#[derive(Debug)]
+struct ApexInfo {
+    name: String,
+    path: PathBuf,
+}
+
+impl ApexInfoList {
+    /// Loads ApexInfoList
+    pub fn load() -> Result<ApexInfoList> {
+        // TODO(b/191601801): look up /apex/apex-info-list.xml instead of apexservice
+        // Each APEX prints the line:
+        //   Module: <...> Version: <...> VersionName: <...> Path: <...> IsActive: <...> IsFactory: <...>
+        // We only care about "Module:" and "Path:" tagged values for now.
+        let info_pattern = Regex::new(r"^Module: (?P<name>[^ ]*) .* Path: (?P<path>[^ ]*) .*$")?;
+        let output = Command::new("cmd")
+            .arg("-w")
+            .arg("apexservice")
+            .arg("getActivePackages")
+            .output()
+            .expect("failed to execute apexservice cmd");
+        let list = BufReader::new(output.stdout.as_slice())
+            .lines()
+            .map(|line| -> Result<ApexInfo> {
+                let line = line?;
+                let captures =
+                    info_pattern.captures(&line).ok_or_else(|| anyhow!("can't parse: {}", line))?;
+                let name = captures.name("name").unwrap();
+                let path = captures.name("path").unwrap();
+                Ok(ApexInfo { name: name.as_str().to_owned(), path: path.as_str().into() })
+            })
+            .collect::<Result<Vec<ApexInfo>>>()?;
+        Ok(ApexInfoList { list })
+    }
+
+    fn get_path_for(&self, apex_name: &str) -> Result<PathBuf> {
+        Ok(self
+            .list
+            .iter()
+            .find(|apex| apex.name == apex_name)
+            .ok_or_else(|| anyhow!("{} not found.", apex_name))?
+            .path
+            .clone())
+    }
 }
 
 /// When passing a host APEX file as a block device in a payload disk image,
@@ -74,7 +119,8 @@
 ///   ..
 ///   microdroid-apk: [apk, zero filler]
 ///   microdroid-apk-idsig: idsig
-pub fn make_disk_image(
+pub fn make_payload_disk(
+    apex_info_list: &ApexInfoList,
     apk_file: PathBuf,
     idsig_file: PathBuf,
     config_path: &str,
@@ -113,7 +159,7 @@
     for (i, apex) in apexes.iter().enumerate() {
         partitions.push(make_partition(
             format!("microdroid-apex-{}", i),
-            get_path(&apex.name)?,
+            apex_info_list.get_path_for(&apex.name)?,
             temporary_directory,
             &mut filler_count,
             &make_size_filler,