diff --git a/security/selinux/include/security.h b/security/selinux/include/security.h
index 111121281c47..aa6b5a689cb7 100644
--- a/security/selinux/include/security.h
+++ b/security/selinux/include/security.h
@@ -22,28 +22,29 @@
 #define SECCLASS_NULL			0x0000 /* no class */
 
 /* Identify specific policy version changes */
-#define POLICYDB_VERSION_BASE		15
-#define POLICYDB_VERSION_BOOL		16
-#define POLICYDB_VERSION_IPV6		17
-#define POLICYDB_VERSION_NLCLASS	18
-#define POLICYDB_VERSION_VALIDATETRANS	19
-#define POLICYDB_VERSION_MLS		19
-#define POLICYDB_VERSION_AVTAB		20
-#define POLICYDB_VERSION_RANGETRANS	21
-#define POLICYDB_VERSION_POLCAP		22
-#define POLICYDB_VERSION_PERMISSIVE	23
-#define POLICYDB_VERSION_BOUNDARY	24
-#define POLICYDB_VERSION_FILENAME_TRANS	25
-#define POLICYDB_VERSION_ROLETRANS	26
+#define POLICYDB_VERSION_BASE			15
+#define POLICYDB_VERSION_BOOL			16
+#define POLICYDB_VERSION_IPV6			17
+#define POLICYDB_VERSION_NLCLASS		18
+#define POLICYDB_VERSION_VALIDATETRANS		19
+#define POLICYDB_VERSION_MLS			19
+#define POLICYDB_VERSION_AVTAB			20
+#define POLICYDB_VERSION_RANGETRANS		21
+#define POLICYDB_VERSION_POLCAP			22
+#define POLICYDB_VERSION_PERMISSIVE		23
+#define POLICYDB_VERSION_BOUNDARY		24
+#define POLICYDB_VERSION_FILENAME_TRANS		25
+#define POLICYDB_VERSION_ROLETRANS		26
 #define POLICYDB_VERSION_NEW_OBJECT_DEFAULTS	27
-#define POLICYDB_VERSION_DEFAULT_TYPE	28
+#define POLICYDB_VERSION_DEFAULT_TYPE		28
 #define POLICYDB_VERSION_CONSTRAINT_NAMES	29
-#define POLICYDB_VERSION_XPERMS_IOCTL	30
+#define POLICYDB_VERSION_XPERMS_IOCTL		30
 #define POLICYDB_VERSION_INFINIBAND		31
+#define POLICYDB_VERSION_TYPE_TRANS_ATTR	32
 
 /* Range of policy versions we understand*/
 #define POLICYDB_VERSION_MIN   POLICYDB_VERSION_BASE
-#define POLICYDB_VERSION_MAX   POLICYDB_VERSION_INFINIBAND
+#define POLICYDB_VERSION_MAX   POLICYDB_VERSION_TYPE_TRANS_ATTR
 
 /* Mask for just the mount related flags */
 #define SE_MNTMASK	0x0f
diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
index cc043bc8fd4c..1e8293201184 100644
--- a/security/selinux/ss/services.c
+++ b/security/selinux/ss/services.c
@@ -1610,30 +1610,137 @@ out:
 	return -EACCES;
 }
 
-static void filename_compute_type(struct policydb *policydb,
-				  struct context *newcontext,
-				  u32 stype, u32 ttype, u16 tclass,
-				  const char *objname)
+static void compute_type_noattr(struct policydb *policydb,
+				struct context *newcontext,
+				u32 stype, u32 ttype,
+				u16 tclass, u32 specified,
+				const char *objname)
 {
-	struct filename_trans ft;
-	struct filename_trans_datum *otype;
+	struct avtab_key avkey;
+	struct avtab_datum *avdatum = NULL;
+	struct avtab_node *node;
 
 	/*
-	 * Most filename trans rules are going to live in specific directories
-	 * like /dev or /var/run.  This bitmap will quickly skip rule searches
-	 * if the ttype does not contain any rules.
+	 * if we have a objname this is a file trans check so check those
+	 * rules
 	 */
-	if (!ebitmap_get_bit(&policydb->filename_trans_ttypes, ttype))
+	if (objname) {
+		struct filename_trans ft;
+		struct filename_trans_datum *otype;
+
+		/*
+		 * Most filename trans rules are going to live in specific
+		 * directories like /dev or /var/run.  This bitmap will quickly
+		 * skip rule searches if the ttype does not contain any rules.
+		 */
+		if (ebitmap_get_bit(&policydb->filename_trans_ttypes, ttype)) {
+			ft.stype = stype;
+			ft.ttype = ttype;
+			ft.tclass = tclass;
+			ft.name = objname;
+
+			otype = hashtab_search(policydb->filename_trans, &ft);
+			if (otype) {
+				newcontext->type = otype->otype;
+				return;
+			}
+		}
+	}
+
+	/* Look for a type transition/member/change rule. */
+	avkey.source_type = stype;
+	avkey.target_type = ttype;
+	avkey.target_class = tclass;
+	avkey.specified = specified;
+	avdatum = avtab_search(&policydb->te_avtab, &avkey);
+	if (avdatum) {
+		newcontext->type = avdatum->u.data;
 		return;
+	}
+
+	/* If no permanent rule, also check for enabled conditional rules */
+	node = avtab_search_node(&policydb->te_cond_avtab, &avkey);
+	for (; node; node = avtab_search_node_next(node, specified)) {
+		if (node->key.specified & AVTAB_ENABLED) {
+			newcontext->type = node->datum.u.data;
+			return;
+		}
+	}
+}
 
-	ft.stype = stype;
-	ft.ttype = ttype;
-	ft.tclass = tclass;
-	ft.name = objname;
+static void compute_type(struct policydb *policydb, struct context *newcontext,
+			 u32 stype, u32 ttype, u16 tclass, u32 specified,
+			 const char *objname)
+{
+	struct avtab_key avkey;
+	struct avtab_datum *avdatum = NULL;
+	struct avtab_node *node;
+	struct ebitmap *sattr, *tattr;
+	struct ebitmap_node *snode, *tnode;
+	unsigned int i, j;
+
+	sattr = &policydb->type_attr_map_array[stype - 1];
+	tattr = &policydb->type_attr_map_array[ttype - 1];
+
+	if (objname) {
+		struct filename_trans ft;
+		struct filename_trans_datum *otype;
+
+		ebitmap_for_each_positive_bit(tattr, tnode, j) {
+			/*
+			 * Most filename trans rules are going to live in
+			 * specific directories like /dev or /var/run.  This
+			 * bitmap will quickly skip rule searches if the ttype
+			 * does not contain any rules.
+			 */
+			if (!ebitmap_get_bit(&policydb->filename_trans_ttypes,
+					     j + 1))
+				continue;
 
-	otype = hashtab_search(policydb->filename_trans, &ft);
-	if (otype)
-		newcontext->type = otype->otype;
+			ebitmap_for_each_positive_bit(sattr, snode, i) {
+				ft.stype = i + 1;
+				ft.ttype = j + 1;
+				ft.tclass = tclass;
+				ft.name = objname;
+
+				otype = hashtab_search(policydb->filename_trans,
+						       &ft);
+				if (otype) {
+					newcontext->type = otype->otype;
+					return;
+				}
+			}
+		}
+	}
+
+	/* Look for a type transition/member/change rule. */
+	avkey.target_class = tclass;
+	avkey.specified = specified;
+	ebitmap_for_each_positive_bit(sattr, snode, i) {
+		ebitmap_for_each_positive_bit(tattr, tnode, j) {
+			avkey.source_type = i + 1;
+			avkey.target_type = j + 1;
+			avdatum = avtab_search(&policydb->te_avtab, &avkey);
+			if (avdatum) {
+				newcontext->type = avdatum->u.data;
+				return;
+			}
+
+			/*
+			 * If no permanent rule, also check for enabled
+			 * conditional rules
+			 */
+			node = avtab_search_node(&policydb->te_cond_avtab,
+						 &avkey);
+			for (; node;
+			     node = avtab_search_node_next(node, specified)) {
+				if (node->key.specified & AVTAB_ENABLED) {
+					newcontext->type = node->datum.u.data;
+					return;
+				}
+			}
+		}
+	}
 }
 
 static int security_compute_sid(struct selinux_state *state,
@@ -1650,9 +1757,6 @@ static int security_compute_sid(struct selinux_state *state,
 	struct class_datum *cladatum = NULL;
 	struct context *scontext = NULL, *tcontext = NULL, newcontext;
 	struct role_trans *roletr = NULL;
-	struct avtab_key avkey;
-	struct avtab_datum *avdatum;
-	struct avtab_node *node;
 	u16 tclass;
 	int rc = 0;
 	bool sock;
@@ -1748,33 +1852,12 @@ static int security_compute_sid(struct selinux_state *state,
 		}
 	}
 
-	/* Look for a type transition/member/change rule. */
-	avkey.source_type = scontext->type;
-	avkey.target_type = tcontext->type;
-	avkey.target_class = tclass;
-	avkey.specified = specified;
-	avdatum = avtab_search(&policydb->te_avtab, &avkey);
-
-	/* If no permanent rule, also check for enabled conditional rules */
-	if (!avdatum) {
-		node = avtab_search_node(&policydb->te_cond_avtab, &avkey);
-		for (; node; node = avtab_search_node_next(node, specified)) {
-			if (node->key.specified & AVTAB_ENABLED) {
-				avdatum = &node->datum;
-				break;
-			}
-		}
-	}
-
-	if (avdatum) {
-		/* Use the type from the type transition/member/change rule. */
-		newcontext.type = avdatum->u.data;
-	}
-
-	/* if we have a objname this is a file trans check so check those rules */
-	if (objname)
-		filename_compute_type(policydb, &newcontext, scontext->type,
-				      tcontext->type, tclass, objname);
+	if (policydb->policyvers < POLICYDB_VERSION_TYPE_TRANS_ATTR)
+		compute_type_noattr(policydb, &newcontext, scontext->type,
+				    tcontext->type, tclass, specified, objname);
+	else
+		compute_type(policydb, &newcontext, scontext->type,
+			     tcontext->type, tclass, specified, objname);
 
 	/* Check for class-specific changes. */
 	if (specified & AVTAB_TRANSITION) {
