diff --git a/adbd.te b/adbd.te
index a74d10b..cac2343 100644
--- a/adbd.te
+++ b/adbd.te
@@ -49,6 +49,10 @@
 # Run /system/bin/bu
 allow adbd system_file:file rx_file_perms;
 
+# XXX Run toolbox.  Might not be needed.
+allow adbd toolbox_exec:file rx_file_perms;
+auditallow adbd toolbox_exec:file rx_file_perms;
+
 # Perform binder IPC to surfaceflinger (screencap)
 # XXX Run screencap in a separate domain?
 binder_use(adbd)
diff --git a/app.te b/app.te
index a78fad1..583495e 100644
--- a/app.te
+++ b/app.te
@@ -74,6 +74,7 @@
 # Execute the shell or other system executables.
 allow appdomain shell_exec:file rx_file_perms;
 allow appdomain system_file:file rx_file_perms;
+allow appdomain toolbox_exec:file rx_file_perms;
 
 # Execute dex2oat when apps call dexclassloader
 allow appdomain dex2oat_exec:file rx_file_perms;
diff --git a/dhcp.te b/dhcp.te
index cbf105c..078e512 100644
--- a/dhcp.te
+++ b/dhcp.te
@@ -11,6 +11,9 @@
 allow dhcp self:netlink_route_socket nlmsg_write;
 allow dhcp shell_exec:file rx_file_perms;
 allow dhcp system_file:file rx_file_perms;
+# XXX Run toolbox.  Might not be needed.
+allow dhcp toolbox_exec:file rx_file_perms;
+auditallow dhcp toolbox_exec:file rx_file_perms;
 # For /proc/sys/net/ipv4/conf/*/promote_secondaries
 allow dhcp proc_net:file write;
 
diff --git a/domain.te b/domain.te
index e7e0d7d..bfbceab 100644
--- a/domain.te
+++ b/domain.te
@@ -109,10 +109,6 @@
 allow domain system_file:file execute;
 allow domain system_file:lnk_file r_file_perms;
 
-# Run toolbox.
-# Kernel, init, and mediaserver never run anything without changing domains.
-allow { domain -kernel -init -mediaserver } toolbox_exec:file rx_file_perms;
-
 # Read files already opened under /data.
 allow domain system_data_file:dir { search getattr };
 allow domain system_data_file:file { getattr read };
diff --git a/dumpstate.te b/dumpstate.te
index f2aab81..963f8cd 100644
--- a/dumpstate.te
+++ b/dumpstate.te
@@ -21,6 +21,7 @@
 #   /system/bin/logcat
 #   /system/bin/dumpsys
 allow dumpstate system_file:file execute_no_trans;
+allow dumpstate toolbox_exec:file rx_file_perms;
 
 # Create and write into /data/anr/
 allow dumpstate self:capability { dac_override chown fowner fsetid };
diff --git a/gpsd.te b/gpsd.te
index 2e05092..4b22223 100644
--- a/gpsd.te
+++ b/gpsd.te
@@ -18,6 +18,7 @@
 # Execute the shell or system commands.
 allow gpsd shell_exec:file rx_file_perms;
 allow gpsd system_file:file rx_file_perms;
+allow gpsd toolbox_exec:file rx_file_perms;
 
 ###
 ### neverallow
diff --git a/install_recovery.te b/install_recovery.te
index 1385220..cbc8634 100644
--- a/install_recovery.te
+++ b/install_recovery.te
@@ -13,6 +13,10 @@
 # Execute /system/bin/applypatch
 allow install_recovery system_file:file rx_file_perms;
 
+# XXX Execute toolbox.  Might not be needed.
+allow install_recovery toolbox_exec:file rx_file_perms;
+auditallow install_recovery toolbox_exec:file rx_file_perms;
+
 # Update the recovery block device based off a diff of the boot block device
 allow install_recovery block_device:dir search;
 allow install_recovery boot_block_device:blk_file r_file_perms;
diff --git a/netd.te b/netd.te
index d4c5153..81d76c3 100644
--- a/netd.te
+++ b/netd.te
@@ -20,6 +20,9 @@
 allow netd self:netlink_socket create_socket_perms;
 allow netd shell_exec:file rx_file_perms;
 allow netd system_file:file x_file_perms;
+# XXX Run toolbox.  Might not be needed.
+allow netd toolbox_exec:file rx_file_perms;
+auditallow netd toolbox_exec:file rx_file_perms;
 allow netd devpts:chr_file rw_file_perms;
 
 # For /proc/sys/net/ipv[46]/route/flush.
diff --git a/perfprofd.te b/perfprofd.te
index 58cb3e2..433b2b8 100644
--- a/perfprofd.te
+++ b/perfprofd.te
@@ -48,7 +48,7 @@
   allow perfprofd exec_type:file r_file_perms;
 
   # simpleperf is going to execute "sleep"
-  allow perfprofd toolbox_exec:file x_file_perms;
+  allow perfprofd toolbox_exec:file rx_file_perms;
 
   # needed for simpleperf on some kernels
   allow perfprofd self:capability ipc_lock;
diff --git a/ppp.te b/ppp.te
index af7062b..c9b27af 100644
--- a/ppp.te
+++ b/ppp.te
@@ -11,6 +11,9 @@
 allow ppp ppp_device:chr_file rw_file_perms;
 allow ppp self:capability net_admin;
 allow ppp system_file:file rx_file_perms;
+# XXX Run toolbox.  Might not be needed.
+allow ppp toolbox_exec:file rx_file_perms;
+auditallow ppp toolbox_exec:file rx_file_perms;
 allow ppp vpn_data_file:dir w_dir_perms;
 allow ppp vpn_data_file:file create_file_perms;
 allow ppp mtp:fd use;
diff --git a/racoon.te b/racoon.te
index 8b09cdf..6447a3d 100644
--- a/racoon.te
+++ b/racoon.te
@@ -19,6 +19,9 @@
 
 # XXX: should we give ip-up-vpn its own label (currently racoon domain)
 allow racoon system_file:file rx_file_perms;
+# XXX Run toolbox.  Might not be needed.
+allow racoon toolbox_exec:file rx_file_perms;
+auditallow racoon toolbox_exec:file rx_file_perms;
 allow racoon vpn_data_file:file create_file_perms;
 allow racoon vpn_data_file:dir w_dir_perms;
 
diff --git a/recovery.te b/recovery.te
index 1441db1..b11213f 100644
--- a/recovery.te
+++ b/recovery.te
@@ -15,6 +15,7 @@
   # Run helpers from / or /system without changing domain.
   allow recovery rootfs:file execute_no_trans;
   allow recovery system_file:file execute_no_trans;
+  allow recovery toolbox_exec:file rx_file_perms;
 
   # Mount filesystems.
   allow recovery rootfs:dir mounton;
diff --git a/rild.te b/rild.te
index 549a4aa..ea0e4ed 100644
--- a/rild.te
+++ b/rild.te
@@ -23,6 +23,9 @@
 allow rild system_data_file:dir r_dir_perms;
 allow rild system_data_file:file r_file_perms;
 allow rild system_file:file x_file_perms;
+# XXX Run toolbox.  Might not be needed.
+allow rild toolbox_exec:file rx_file_perms;
+auditallow rild toolbox_exec:file rx_file_perms;
 
 # property service
 set_prop(rild, radio_prop)
diff --git a/shell.te b/shell.te
index 28f79d6..84e1802 100644
--- a/shell.te
+++ b/shell.te
@@ -38,6 +38,7 @@
 allow shell input_device:dir r_dir_perms;
 allow shell input_device:chr_file rw_file_perms;
 allow shell system_file:file x_file_perms;
+allow shell toolbox_exec:file rx_file_perms;
 allow shell shell_exec:file rx_file_perms;
 allow shell zygote_exec:file rx_file_perms;
 
diff --git a/system_server.te b/system_server.te
index 5f07f65..6737783 100644
--- a/system_server.te
+++ b/system_server.te
@@ -311,6 +311,10 @@
 # Run system programs, e.g. dexopt.
 allow system_server system_file:file x_file_perms;
 
+# XXX Run toolbox.  Might not be needed.
+allow system_server toolbox_exec:file rx_file_perms;
+auditallow system_server toolbox_exec:file rx_file_perms;
+
 # LocationManager(e.g, GPS) needs to read and write
 # to uart driver and ctrl proc entry
 allow system_server gps_device:chr_file rw_file_perms;
diff --git a/vold.te b/vold.te
index a1aef72..b50e399 100644
--- a/vold.te
+++ b/vold.te
@@ -24,6 +24,9 @@
 typeattribute vold mlstrustedsubject;
 allow vold self:process setfscreate;
 allow vold system_file:file x_file_perms;
+# XXX Run toolbox.  Might not be needed.
+allow vold toolbox_exec:file rx_file_perms;
+auditallow vold toolbox_exec:file rx_file_perms;
 allow vold block_device:dir create_dir_perms;
 allow vold block_device:blk_file create_file_perms;
 auditallow vold block_device:blk_file create_file_perms;