diff --git a/private/adbd.te b/private/adbd.te
index bde6864..58038c7 100644
--- a/private/adbd.te
+++ b/private/adbd.te
@@ -12,6 +12,14 @@
   allow adbd su:process dyntransition;
 ')
 
+# When 'adb shell' is executed in recovery mode, adbd explicitly
+# switches into shell domain using setcon() because the shell executable
+# is not labeled as shell but as rootfs.
+recovery_only(`
+  domain_trans(adbd, rootfs, shell)
+  allow adbd shell:process dyntransition;
+')
+
 # Do not sanitize the environment or open fds of the shell. Allow signaling
 # created processes.
 allow adbd shell:process { noatsecure signal };
@@ -148,4 +156,4 @@
 # transitions to the shell domain (except when it crashes). In particular, we
 # never want to see a transition from adbd to su (aka "adb root")
 neverallow adbd { domain -crash_dump -shell }:process transition;
-neverallow adbd { domain userdebug_or_eng(`-su') }:process dyntransition;
+neverallow adbd { domain userdebug_or_eng(`-su') recovery_only(`-shell') }:process dyntransition;
diff --git a/public/kernel.te b/public/kernel.te
index b7a351c..cf913ba 100644
--- a/public/kernel.te
+++ b/public/kernel.te
@@ -103,3 +103,18 @@
 # Instead of adding dac_{read_search,override}, fix the unix permissions
 # on files being accessed.
 neverallow kernel self:global_capability_class_set { dac_override dac_read_search };
+
+# Allow the first-stage init (which is running in the kernel domain) to execute the
+# dynamic linker when it re-executes /init to switch into the second stage.
+# Until Linux 4.8, the program interpreter (dynamic linker in this case) is executed
+# before the domain is switched to the target domain. So, we need to allow the kernel
+# domain (the source domain) to execute the dynamic linker (system_file type).
+# TODO(b/110147943) remove these allow rules when we no longer need to support Linux
+# kernel older than 4.8.
+allow kernel system_file:file execute;
+# The label for the dynamic linker is rootfs in the recovery partition. This is because
+# the recovery partition which is rootfs does not support xattr and thus labeling can't be
+# done at build-time. All files are by default labeled as rootfs upon booting.
+recovery_only(`
+  allow kernel rootfs:file execute;
+')
diff --git a/public/recovery.te b/public/recovery.te
index 57ad202..48fffe6 100644
--- a/public/recovery.te
+++ b/public/recovery.te
@@ -30,6 +30,7 @@
 
   # Mount filesystems.
   allow recovery rootfs:dir mounton;
+  allow recovery tmpfs:dir mounton;
   allow recovery fs_type:filesystem ~relabelto;
   allow recovery unlabeled:filesystem ~relabelto;
   allow recovery contextmount_type:filesystem relabelto;
diff --git a/public/shell.te b/public/shell.te
index 4293f52..8e6ae4c 100644
--- a/public/shell.te
+++ b/public/shell.te
@@ -199,6 +199,12 @@
 # Allow shell to start up vendor shell
 allow shell vendor_shell_exec:file rx_file_perms;
 
+# Everything is labeled as rootfs in recovery mode. Allow shell to
+# execute them.
+recovery_only(`
+  allow shell rootfs:file rx_file_perms;
+')
+
 ###
 ### Neverallow rules
 ###
diff --git a/public/ueventd.te b/public/ueventd.te
index 9b9eacb..0cac32d 100644
--- a/public/ueventd.te
+++ b/public/ueventd.te
@@ -39,6 +39,12 @@
 # Allow ueventd to read androidboot.android_dt_dir from kernel cmdline.
 allow ueventd proc_cmdline:file r_file_perms;
 
+# Everything is labeled as rootfs in recovery mode. ueventd has to execute
+# the dynamic linker and shared libraries.
+recovery_only(`
+  allow ueventd rootfs:file { r_file_perms execute };
+')
+
 #####
 ##### neverallow rules
 #####
diff --git a/public/vendor_init.te b/public/vendor_init.te
index ad69437..6307f2c 100644
--- a/public/vendor_init.te
+++ b/public/vendor_init.te
@@ -155,6 +155,12 @@
 # Raw writes to misc block device
 allow vendor_init misc_block_device:blk_file w_file_perms;
 
+# Everything is labeled as rootfs in recovery mode. Vendor init has to execute
+# the dynamic linker and shared libraries.
+recovery_only(`
+  allow vendor_init rootfs:file { r_file_perms execute };
+')
+
 not_compatible_property(`
     set_prop(vendor_init, {
       property_type