Attributes in new binary format

Attributes in new binary format

[Joshua Brindle]

In the new binary format the attribute values are preserved in the avtab 
but the attribute entries in the type symbol table are destroyed.

This makes analysis on the binary format difficult for a number of reasons.

Tools like apol will have to expand the type bitmaps and will lose 
attibutes on types. This is the same as analysing the current (v19) 
binary format but including attributes will be beneficial to analysis.

Further, the hierarchal constraint checking is currently broken with the 
new format. The reason is that we must be able to expand attributes at 
check time to ensure that types weren't given permissions via attributes 
that violate the constraints. This can be done with the new format but 
it's very time consuming.

I'd like to suggest that we preserve the attibute entries in the type 
table in the binary format and modify the kernel read function to not 
allocate space for them as it reads them in. This makes the binary 
format much more usable in terms of analysis at no cost to the kernel 
memory.

Let me know what you think.

Joshua

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: Attributes in new binary format

[Stephen Smalley]

On Mon, 2005-08-08 at 11:55 -0400, Joshua Brindle wrote:
> In the new binary format the attribute values are preserved in the avtab 
> but the attribute entries in the type symbol table are destroyed.
> 
> This makes analysis on the binary format difficult for a number of reasons.
> 
> Tools like apol will have to expand the type bitmaps and will lose 
> attibutes on types. This is the same as analysing the current (v19) 
> binary format but including attributes will be beneficial to analysis.
> 
> Further, the hierarchal constraint checking is currently broken with the 
> new format. The reason is that we must be able to expand attributes at 
> check time to ensure that types weren't given permissions via attributes 
> that violate the constraints. This can be done with the new format but 
> it's very time consuming.
> 
> I'd like to suggest that we preserve the attibute entries in the type 
> table in the binary format and modify the kernel read function to not 
> allocate space for them as it reads them in. This makes the binary 
> format much more usable in terms of analysis at no cost to the kernel 
> memory.
> 
> Let me know what you think.

I don't see why any of this would mean that we should put this
information into the kernel's binary format, particularly given that the
kernel is just going to discard it at read time (and it would need the
isattr flag to be written into the kernel binary format to know what to
discard at that point, I assume).  Including attributes in analysis can
be done by performing the analysis on policy source or the policy module
format.  As far as the hierarchical constraint checking code is
concerned, can't it just use expand_avtab like the assertion checking
code now does?  Running time on checkpolicy actually shows a nontrivial
speed up from the original upstream checkpolicy to the latest patched
one with the inline ebitmap operators.

-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

RE: Attributes in new binary format

[Frank Mayer]

 
> I don't see why any of this would mean that we should put this
> information into the kernel's binary format, particularly given that
> the kernel is just going to discard it at read time (and it would
> need the isattr flag to be written into the kernel binary format to
> know what to discard at that point, I assume).  Including attributes
> in analysis can be done by performing the analysis on policy source
> or the policy module format.  

It all comes down to trade-offs. In our experience there are times you need
to or are forced to use the binary format for analysis. We can with some
effort do the expansion in lipabol and put the binary format into the
current format without attributes. However, we always wished the binary
format had attributes. Now it does (almost). 

If it required extensive kernel resources to maintain the symbols in the
binary file format, we wouldn't suggest it. But it seems like the effort is
fairly small (skip over entries on read) and the gain, IMO, is great. Hence
the suggestion. Frank



--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: Attributes in new binary format

[Joshua Brindle]

Stephen Smalley wrote:

>On Mon, 2005-08-08 at 11:55 -0400, Joshua Brindle wrote:
>  
>
>>In the new binary format the attribute values are preserved in the avtab 
>>but the attribute entries in the type symbol table are destroyed.
>>
>>This makes analysis on the binary format difficult for a number of reasons.
>>
>>Tools like apol will have to expand the type bitmaps and will lose 
>>attibutes on types. This is the same as analysing the current (v19) 
>>binary format but including attributes will be beneficial to analysis.
>>
>>Further, the hierarchal constraint checking is currently broken with the 
>>new format. The reason is that we must be able to expand attributes at 
>>check time to ensure that types weren't given permissions via attributes 
>>that violate the constraints. This can be done with the new format but 
>>it's very time consuming.
>>
>>I'd like to suggest that we preserve the attibute entries in the type 
>>table in the binary format and modify the kernel read function to not 
>>allocate space for them as it reads them in. This makes the binary 
>>format much more usable in terms of analysis at no cost to the kernel 
>>memory.
>>
>>Let me know what you think.
>>    
>>
>
>I don't see why any of this would mean that we should put this
>information into the kernel's binary format, particularly given that the
>kernel is just going to discard it at read time (and it would need the
>isattr flag to be written into the kernel binary format to know what to
>discard at that point, I assume).  Including attributes in analysis can
>be done by performing the analysis on policy source or the policy module
>format.  As far as the hierarchical constraint checking code is
>concerned, can't it just use expand_avtab like the assertion checking
>code now does? 
>
No, the hierarchal constraint checker is going to be a standalone 
verifier that runs during the module verification process.

> Running time on checkpolicy actually shows a nontrivial
>speed up from the original upstream checkpolicy to the latest patched
>one with the inline ebitmap operators.
>
>  
>
To do the hierarchal constraint check we walk the avtab, look up the 
types in the type symtab, find their parents and do avtab lookups to see 
if the permissions were granted to the parents. Now, after this patch, 
while walking the avtab, we run into avtab entries with type values not 
in the type symtab. At that point we'd have to go through every type and 
build up the same attr->type bitmaps that could just be stored in the 
binary format since it is already available.

Further, for semodule and policy server, we have some plans to be able 
to do information flow analysis on the resulting policy to make sure it 
matches the local security requirements. Having to rebuild attribute 
maps makes this much slower, and this is when the user is sitting 
wondering why inserting a 1 line module is taking so long.

I don't see a good reason not to include this info since it's so useful 
during the policy verification process.

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: Attributes in new binary format

[Stephen Smalley]

On Mon, 2005-08-08 at 13:19 -0400, Joshua Brindle wrote:
> No, the hierarchal constraint checker is going to be a standalone 
> verifier that runs during the module verification process.
<snip>
> To do the hierarchal constraint check we walk the avtab, look up the 
> types in the type symtab, find their parents and do avtab lookups to see 
> if the permissions were granted to the parents. Now, after this patch, 
> while walking the avtab, we run into avtab entries with type values not 
> in the type symtab. At that point we'd have to go through every type and 
> build up the same attr->type bitmaps that could just be stored in the 
> binary format since it is already available.

You need to pre-expand the avtab via expand_avtab, just like avtab_write
and check_assertions are doing.  Note that the attribute->type mapping
is built not only upon expansion, but also upon policydb_read (in
libsepol only, not in the kernel). The latter builds an in-memory
attribute->type mapping from the stored type->attribute reverse mapping
for later use by expand_avtab and expand_cond_av_list, because we need
that for performing a policydb_write for an older binary policy version.
I needed that to avoid breaking /sbin/init and load_policy of a
policy.19 file with the new libsepol (upon the genusers/genbools calls,
which pull in the file via policydb_read, mutate it, and then write it
to memory via policydb_write and load the result).  There is some up
front cost to building that mapping and using expand_avtab, but I don't
think it is prohibitive.

> Further, for semodule and policy server, we have some plans to be able 
> to do information flow analysis on the resulting policy to make sure it 
> matches the local security requirements. Having to rebuild attribute 
> maps makes this much slower, and this is when the user is sitting 
> wondering why inserting a 1 line module is taking so long.
> 
> I don't see a good reason not to include this info since it's so useful 
> during the policy verification process.

The information isn't used by the kernel, and I already provided code to
rebuild it upon libsepol's policydb_read, and I haven't seen evidence
that it is prohibitively costly.  Now, if you want to have checkpolicy
emit an additional file with auxiliary data that can be used by
userspace tools, similar to System.map, and have that file installed on
the end systems in a similar manner to System.map, then that may make
sense.

-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

RE: Attributes in new binary format

[Stephen Smalley]

On Mon, 2005-08-08 at 12:41 -0400, Frank Mayer wrote:
> It all comes down to trade-offs. In our experience there are times you need
> to or are forced to use the binary format for analysis. We can with some
> effort do the expansion in lipabol and put the binary format into the
> current format without attributes. However, we always wished the binary
> format had attributes. Now it does (almost). 
> 
> If it required extensive kernel resources to maintain the symbols in the
> binary file format, we wouldn't suggest it. But it seems like the effort is
> fairly small (skip over entries on read) and the gain, IMO, is great. Hence
> the suggestion. Frank

I'm not convinced there is a real gain (useful traceback from analysis
still requires higher level formats than the kernel format, even if we
include the attribute symbols in the kernel format), and in any event,
the kernel doesn't need the information.  The more natural step would be
to emit an auxiliary file with the additional information like the
kernel's System.map file and install that file for use by userspace
tools than to put it into the kernel's format.

-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: Attributes in new binary format

[Stephen Smalley]

On Mon, 2005-08-08 at 13:35 -0400, Stephen Smalley wrote:
> You need to pre-expand the avtab via expand_avtab, just like avtab_write
> and check_assertions are doing.  Note that the attribute->type mapping
> is built not only upon expansion, but also upon policydb_read (in
> libsepol only, not in the kernel). The latter builds an in-memory
> attribute->type mapping from the stored type->attribute reverse mapping
> for later use by expand_avtab and expand_cond_av_list, because we need
> that for performing a policydb_write for an older binary policy version.
> I needed that to avoid breaking /sbin/init and load_policy of a
> policy.19 file with the new libsepol (upon the genusers/genbools calls,
> which pull in the file via policydb_read, mutate it, and then write it
> to memory via policydb_write and load the result).  There is some up
> front cost to building that mapping and using expand_avtab, but I don't
> think it is prohibitive.

This patch changes the hierarchy checking code to use the expand_avtab
and expand_cond_av_list code that was added for the compatibility
support.  Along with an unrelated bug fix for the hierarchy checking
code sent separately, this seems to correctly catch a hierarchy
violation triggered by a rule that used an attribute.

diff -X /home/sds/dontdiff -rup libsepol.a/src/hierarchy.c libsepol/src/hierarchy.c
--- libsepol.a/src/hierarchy.c	2005-08-02 16:18:04.000000000 -0400
+++ libsepol/src/hierarchy.c	2005-08-08 16:52:10.000000000 -0400
@@ -27,9 +27,11 @@
 #include <sepol/policydb.h>
 #include <sepol/conditional.h>
 #include <sepol/hierarchy.h>
+#include <sepol/expand.h>
 
 typedef struct hierarchy_args {
 	policydb_t *p;
+	avtab_t    *expa; /* expanded avtab */
 	/* This tells check_avtab_hierarchy to check this list in addition to the unconditional avtab */
 	cond_av_list_t *opt_cond_list; 
 	char errmsg[ERRMSG_LEN];
@@ -153,7 +155,7 @@ static int check_avtab_hierarchy_callbac
 		key.target_class = k->target_class;
 		key.specified = AVTAB_ALLOWED;
 	
-		avdatump = avtab_search(&a->p->te_avtab, &key);
+		avdatump = avtab_search(a->expa, &key);
 		if (avdatump) {
 			/* search for access allowed between type 1's parent and type 2 */
 			if ((avdatump->data & d->data) == d->data) {
@@ -192,7 +194,7 @@ static int check_avtab_hierarchy_callbac
 		key.target_class = k->target_class;
 		key.specified = AVTAB_ALLOWED;
 		
-		avdatump = avtab_search(&a->p->te_avtab, &key);
+		avdatump = avtab_search(a->expa, &key);
 		if (avdatump) {
 			if ((avdatump->data & d->data) == d->data) {
 				return 0;
@@ -217,7 +219,7 @@ static int check_avtab_hierarchy_callbac
 		key.target_class = k->target_class;
 		key.specified = AVTAB_ALLOWED;
 	
-		avdatump = avtab_search(&a->p->te_avtab, &key);
+		avdatump = avtab_search(a->expa, &key);
 		if (avdatump) {
 			if ((avdatump->data & d->data) == d->data) {
 				return 0;
@@ -255,28 +257,53 @@ static int check_cond_avtab_hierarchy(co
 {
 	int rc;
 	cond_list_t *cur_node;
-	cond_av_list_t *cur_av;
+	cond_av_list_t *cur_av, *expl = NULL;
+	avtab_t expa;
 
 	for (cur_node = cond_list; cur_node != NULL; cur_node = cur_node ->next) {
-		args->opt_cond_list = cur_node->true_list;
-		for (cur_av = cur_node->true_list; cur_av != NULL; cur_av = cur_av->next) {
+		if (avtab_init(&expa))
+			goto oom;
+		if (expand_cond_av_list(args->p, cur_node->true_list, &expl, &expa)) {
+			avtab_destroy(&expa);
+			goto oom;
+		}
+		args->opt_cond_list = expl;
+		for (cur_av = expl; cur_av != NULL; cur_av = cur_av->next) {
 			rc = check_avtab_hierarchy_callback(&cur_av->node->key, &cur_av->node->datum, args);
 			if (rc == 0)
 				continue;
 			/* error condition */
+			cond_av_list_destroy(expl);
+			avtab_destroy(&expa);
 			return rc;
 		}
-		args->opt_cond_list = cur_node->false_list;
-		for (cur_av = cur_node->false_list; cur_av != NULL; cur_av = cur_av->next) {
+		cond_av_list_destroy(expl);
+		avtab_destroy(&expa);
+		if (avtab_init(&expa))
+			goto oom;
+		if (expand_cond_av_list(args->p, cur_node->false_list, &expl, &expa)) {
+			avtab_destroy(&expa);
+			goto oom;
+		}
+		args->opt_cond_list = expl;
+		for (cur_av = expl; cur_av != NULL; cur_av = cur_av->next) {
 			rc = check_avtab_hierarchy_callback(&cur_av->node->key, &cur_av->node->datum, args);
 			if (rc == 0)
 				continue;
 			/* error condition */
+			cond_av_list_destroy(expl);
+			avtab_destroy(&expa);
 			return rc;
 		}
+		cond_av_list_destroy(expl);
+		avtab_destroy(&expa);
 	}
 
 	return 0;
+
+oom:
+	snprintf(args->errmsg, ERRMSG_LEN, "out of memory on conditional av list expansion");
+	return 1;
 }
 
 /* The role hierarchy is defined as: a child role cannot have more types than it's parent.
@@ -332,14 +359,23 @@ static int check_role_hierarchy_callback
 int hierarchy_check_constraints(policydb_t *p, char *error_msg, uint32_t error_len)
 {
 	hierarchy_args_t args;
+	avtab_t expa;
+
+	if (avtab_init(&expa))
+		goto oom;
+	if (expand_avtab(p, &p->te_avtab, &expa)) {
+		avtab_destroy(&expa);
+		goto oom;
+	}
 
 	args.p = p;
+	args.expa = &expa;
 	args.opt_cond_list = NULL;
 
 	if (hashtab_map(p->p_types.table, check_type_hierarchy_callback, &args)) 
 		goto bad;
 
-	if (avtab_map(&p->te_avtab, check_avtab_hierarchy_callback, &args))
+	if (avtab_map(&expa, check_avtab_hierarchy_callback, &args))
 		goto bad;
 
 	if (check_cond_avtab_hierarchy(p->cond_list, &args))
@@ -348,12 +384,18 @@ int hierarchy_check_constraints(policydb
 	if (hashtab_map(p->p_roles.table, check_role_hierarchy_callback, &args)) 
 		goto bad;
 
+	avtab_destroy(&expa);
 	return 0;
 
 bad:
 	if (args.errmsg)
 		error_msg = strncpy(error_msg, args.errmsg, error_len);
 
+	avtab_destroy(&expa);
+	return -1;
+
+oom:
+	strncpy(error_msg, "Out of memory", error_len);
 	return -1;
 }
 

-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.