diff --git a/tools/releasetools/apex_utils.py b/tools/releasetools/apex_utils.py
index 8dd7c31..194ff58 100644
--- a/tools/releasetools/apex_utils.py
+++ b/tools/releasetools/apex_utils.py
@@ -65,6 +65,8 @@
         OPTIONS.search_path, "bin", "debugfs_static")
     self.fsckerofs_path = os.path.join(
         OPTIONS.search_path, "bin", "fsck.erofs")
+    self.blkid_path = os.path.join(
+        OPTIONS.search_path, "bin", "blkid")
     self.avbtool = avbtool if avbtool else "avbtool"
     self.sign_tool = sign_tool
 
@@ -82,13 +84,8 @@
           "Couldn't find location of debugfs_static: " +
           "Path {} does not exist. ".format(self.debugfs_path) +
           "Make sure bin/debugfs_static can be found in -p <path>")
-    if not os.path.exists(self.fsckerofs_path):
-      raise ApexSigningError(
-          "Couldn't find location of fsck.erofs: " +
-          "Path {} does not exist. ".format(self.fsckerofs_path) +
-          "Make sure bin/fsck.erofs can be found in -p <path>")
     list_cmd = ['deapexer', '--debugfs_path', self.debugfs_path,
-                '--fsckerofs_path', self.fsckerofs_path, 'list', self.apex_path]
+                'list', self.apex_path]
     entries_names = common.RunAndCheckOutput(list_cmd).split()
     apk_entries = [name for name in entries_names if name.endswith('.apk')]
     sepolicy_entries = []
@@ -132,9 +129,15 @@
           "Couldn't find location of fsck.erofs: " +
           "Path {} does not exist. ".format(self.fsckerofs_path) +
           "Make sure bin/fsck.erofs can be found in -p <path>")
+    if not os.path.exists(self.blkid_path):
+      raise ApexSigningError(
+          "Couldn't find location of blkid: " +
+          "Path {} does not exist. ".format(self.blkid_path) +
+          "Make sure bin/blkid can be found in -p <path>")
     payload_dir = common.MakeTempDir()
     extract_cmd = ['deapexer', '--debugfs_path', self.debugfs_path,
-                   '--fsckerofs_path', self.fsckerofs_path, 'extract',
+                   '--fsckerofs_path', self.fsckerofs_path,
+                   '--blkid_path', self.blkid_path, 'extract',
                    self.apex_path, payload_dir]
     common.RunAndCheckOutput(extract_cmd)
     assert os.path.exists(self.apex_path)
@@ -470,7 +473,6 @@
     The path to the signed APEX file.
   """
   debugfs_path = os.path.join(OPTIONS.search_path, 'bin', 'debugfs_static')
-  fsckerofs_path = os.path.join(OPTIONS.search_path, 'bin', 'fsck.erofs')
 
   # 1. Decompress original_apex inside compressed apex.
   original_apex_file = common.MakeTempFile(prefix='original-apex-',
@@ -478,7 +480,6 @@
   # Decompression target path should not exist
   os.remove(original_apex_file)
   common.RunAndCheckOutput(['deapexer', '--debugfs_path', debugfs_path,
-                            '--fsckerofs_path', fsckerofs_path,
                             'decompress', '--input', apex_file,
                             '--output', original_apex_file])
 
@@ -544,9 +545,7 @@
     output_fp.write(apex_data)
 
   debugfs_path = os.path.join(OPTIONS.search_path, 'bin', 'debugfs_static')
-  fsckerofs_path = os.path.join(OPTIONS.search_path, 'bin', 'fsck.erofs')
   cmd = ['deapexer', '--debugfs_path', debugfs_path,
-         '--fsckerofs_path', fsckerofs_path,
          'info', '--print-type', apex_file]
 
   try:
@@ -621,10 +620,6 @@
   if OPTIONS.search_path:
     debugfs_path = os.path.join(OPTIONS.search_path, "bin", "debugfs_static")
 
-  fsckerofs_path = "fsck.erofs"
-  if OPTIONS.search_path:
-    fsckerofs_path = os.path.join(OPTIONS.search_path, "bin", "fsck.erofs")
-
   deapexer = 'deapexer'
   if OPTIONS.search_path:
     deapexer_path = os.path.join(OPTIONS.search_path, "bin", "deapexer")
@@ -645,7 +640,6 @@
     # Check if the file is compressed or not
     apex_type = RunAndCheckOutput([
         deapexer, "--debugfs_path", debugfs_path,
-        "--fsckerofs_path", fsckerofs_path,
         'info', '--print-type', apex_filepath]).rstrip()
     if apex_type == 'COMPRESSED':
       apex_info.is_compressed = True
diff --git a/tools/releasetools/merge/merge_dexopt.py b/tools/releasetools/merge/merge_dexopt.py
index 7bf9bd4..16182b5 100644
--- a/tools/releasetools/merge/merge_dexopt.py
+++ b/tools/releasetools/merge/merge_dexopt.py
@@ -164,6 +164,10 @@
           'deapexer',
           '--debugfs_path',
           'debugfs_static',
+          '--blkid_path',
+          'blkid',
+          '--fsckerofs_path',
+          'fsck.erofs',
           'extract',
           apex,
           apex_extract_dir,