diff --git a/app.te b/app.te
index 7d4acfb..00af7e7 100644
--- a/app.te
+++ b/app.te
@@ -158,6 +158,10 @@
 # For art.
 allow appdomain dalvikcache_data_file:file execute;
 
+# For legacy unlabeled userdata on existing devices.
+# See discussion of Unlabeled files in domain.te for more information.
+allow appdomain unlabeled:file x_file_perms;
+
 ###
 ### CTS-specific rules
 ###
diff --git a/domain.te b/domain.te
index 653a507..103d690 100644
--- a/domain.te
+++ b/domain.te
@@ -129,9 +129,8 @@
 # capability, it's essentially useless. This is needed to allow an app with
 # relabelto to relabel unlabeled files.
 #
-allow domain unlabeled:file { create_file_perms rwx_file_perms relabelfrom };
+allow domain unlabeled:notdevfile_class_set { create_file_perms relabelfrom };
 allow domain unlabeled:dir { create_dir_perms relabelfrom };
-allow domain unlabeled:lnk_file { create_file_perms };
 neverallow { domain -relabeltodomain } *:dir_file_class_set relabelto;
 
 ###
diff --git a/system_server.te b/system_server.te
index 37d4cc6..22d739b 100644
--- a/system_server.te
+++ b/system_server.te
@@ -239,3 +239,8 @@
 
 # For SELinuxPolicyInstallReceiver
 selinux_manage_policy(system_server)
+
+# For legacy unlabeled userdata on existing devices.
+# See discussion of Unlabeled files in domain.te for more information.
+# This rule is for dalvikcache mmap/mprotect PROT_EXEC.
+allow system_server unlabeled:file execute;
diff --git a/zygote.te b/zygote.te
index 9092457..daa9782 100644
--- a/zygote.te
+++ b/zygote.te
@@ -50,3 +50,8 @@
 allow zygote shell_data_file:file { write getattr };
 allow zygote system_server:binder { transfer call };
 allow zygote servicemanager:binder { call };
+
+# For legacy unlabeled userdata on existing devices.
+# See discussion of Unlabeled files in domain.te for more information.
+# This rule is for dalvikcache mmap/mprotect PROT_EXEC.
+allow zygote unlabeled:file execute;