On 06/12/2015 08:59 AM, James Carter wrote:
On 06/11/2015 04:07 PM, Stephen Smalley wrote:On 06/11/2015 02:26 PM, James Carter wrote:Instead of creating an expanded avtab, generating all of the avtab keys corresponding to a neverallow rule and searching for a match, walk the nodes in the avtab and use the attr_type_map and ebitmap functions to find matching rules. Memory usage is reduced from 370M to 125M and time is reduced from 14 sec to 2 sec. (Bounds checking commented out in both cases.) Signed-off-by: James Carter <jwcart2@xxxxxxxxxxxxx> --- libsepol/include/sepol/policydb/policydb.h | 2 +- libsepol/src/assertion.c | 225 ++++++++++++++++++----------- 2 files changed, 145 insertions(+), 82 deletions(-) diff --git a/libsepol/include/sepol/policydb/policydb.h b/libsepol/include/sepol/policydb/policydb.h index 1d8310c..b3cf9db 100644 --- a/libsepol/include/sepol/policydb/policydb.h +++ b/libsepol/include/sepol/policydb/policydb.h @@ -652,7 +652,7 @@ extern void level_datum_init(level_datum_t * x); extern void level_datum_destroy(level_datum_t * x); extern void cat_datum_init(cat_datum_t * x); extern void cat_datum_destroy(cat_datum_t * x); - +extern int check_assertion(policydb_t *p, avrule_t *avrule); extern int check_assertions(sepol_handle_t * handle, policydb_t * p, avrule_t * avrules); diff --git a/libsepol/src/assertion.c b/libsepol/src/assertion.c index c335968..35698df 100644 --- a/libsepol/src/assertion.c +++ b/libsepol/src/assertion.c @@ -27,11 +27,16 @@ #include "debug.h" -static void report_failure(sepol_handle_t *handle, policydb_t *p, - const avrule_t * avrule, +struct avtab_match_args { + sepol_handle_t *handle; + policydb_t *p; + avrule_t *avrule; + unsigned long errors; +}; + +static void report_failure(sepol_handle_t *handle, policydb_t *p, const avrule_t *avrule, unsigned int stype, unsigned int ttype, - const class_perm_node_t *curperm, - const avtab_ptr_t node) + const class_perm_node_t *curperm, uint32_t perms) { if (avrule->source_filename) { ERR(handle, "neverallow on line %lu of %s (or line %lu of policy.conf) violated by allow %s %s:%s {%s };", @@ -39,69 +44,164 @@ static void report_failure(sepol_handle_t *handle, policydb_t *p, p->p_type_val_to_name[stype], p->p_type_val_to_name[ttype], p->p_class_val_to_name[curperm->tclass - 1], - sepol_av_to_string(p, curperm->tclass, - node->datum.data & curperm->data)); + sepol_av_to_string(p, curperm->tclass, perms));So you're reporting the entire list of permissions from the allow rule, not just the offending ones? I guess I could go either way; the old approach was more indicative of what the problem was, while the new is closer to what they might find in source (albeit after macro expansion).It is just the offending ones (node->datum.data & curperm->data).
Oops. Sorry, I switched to master when I was responding to your previous email.We report just the offending ones for the bounds checking and it would be better to do the same here as well.
} else if (avrule->line) { ERR(handle, "neverallow on line %lu violated by allow %s %s:%s {%s };", avrule->line, p->p_type_val_to_name[stype], p->p_type_val_to_name[ttype], p->p_class_val_to_name[curperm->tclass - 1], - sepol_av_to_string(p, curperm->tclass, - node->datum.data & curperm->data)); + sepol_av_to_string(p, curperm->tclass, perms)); } else { ERR(handle, "neverallow violated by allow %s %s:%s {%s };", p->p_type_val_to_name[stype], p->p_type_val_to_name[ttype], p->p_class_val_to_name[curperm->tclass - 1], - sepol_av_to_string(p, curperm->tclass, - node->datum.data & curperm->data)); + sepol_av_to_string(p, curperm->tclass, perms)); } } -static unsigned long check_assertion_helper(sepol_handle_t * handle, - policydb_t * p, - avtab_t * te_avtab, avtab_t * te_cond_avtab, - unsigned int stype, unsigned int ttype, - const avrule_t * avrule) +static int report_assertion_avtab_matches(avtab_key_t *k, avtab_datum_t *d, void *args) { - avtab_key_t avkey; - avtab_ptr_t node; - class_perm_node_t *curperm; - unsigned long errors = 0; + struct avtab_match_args *a = (struct avtab_match_args *)args; + sepol_handle_t *handle = a->handle; + policydb_t *p = a->p; + avrule_t *avrule = a->avrule; + class_perm_node_t *cp; + uint32_t perms; + ebitmap_t src_matches, tgt_matches; + ebitmap_node_t *snode, *tnode; + unsigned int i, j; - for (curperm = avrule->perms; curperm != NULL; curperm = curperm->next) { - avkey.source_type = stype + 1; - avkey.target_type = ttype + 1; - avkey.target_class = curperm->tclass; - avkey.specified = AVTAB_ALLOWED; - for (node = avtab_search_node(te_avtab, &avkey); - node != NULL; - node = avtab_search_node_next(node, avkey.specified)) { - if (node->datum.data & curperm->data) { - report_failure(handle, p, avrule, stype, ttype, curperm, node); - errors++; - } + if (k->specified != AVTAB_ALLOWED) + goto exit; + + for (cp = avrule->perms; cp; cp = cp->next) { + perms = cp->data & d->data; + if ((cp->tclass != k->target_class) || !perms) { + continue; + } + + ebitmap_and(&src_matches, &avrule->stypes.types, + &p->attr_type_map[k->source_type - 1]); + if (ebitmap_length(&src_matches) == 0) + continue; + + if (avrule->flags == RULE_SELF) { + ebitmap_t matches; + ebitmap_init(&matches); + ebitmap_and(&matches, &p->attr_type_map[k->source_type - 1], &p->attr_type_map[k->target_type - 1]); + ebitmap_and(&tgt_matches, &avrule->stypes.types, &matches); + ebitmap_destroy(&matches);ebitmap_and() can fail on memory allocation failure so we need to check and handle.Don't know how I missed that.+ } else { + ebitmap_and(&tgt_matches, &avrule->ttypes.types, &p->attr_type_map[k->target_type -1]); + } + + if (ebitmap_length(&tgt_matches) == 0) { + ebitmap_destroy(&src_matches); + continue; } - for (node = avtab_search_node(te_cond_avtab, &avkey); - node != NULL; - node = avtab_search_node_next(node, avkey.specified)) { - if (node->datum.data & curperm->data) { - report_failure(handle, p, avrule, stype, ttype, curperm, node); - errors++; + + ebitmap_for_each_bit(&src_matches, snode, i) { + if (!ebitmap_node_get_bit(snode, i)) + continue; + ebitmap_for_each_bit(&tgt_matches, tnode, j) { + if (!ebitmap_node_get_bit(tnode, j)) + continue; + a->errors++; + report_failure(handle, p, avrule, i, j, cp, perms); } } } - return errors; +exit: + return 0; +} + +int report_assertion_failures(sepol_handle_t *handle, policydb_t *p, avrule_t *avrule) +{ + struct avtab_match_args args; + + args.handle = handle; + args.p = p; + args.avrule = avrule; + args.errors = 0; + + avtab_map(&p->te_avtab, report_assertion_avtab_matches, &args); + avtab_map(&p->te_cond_avtab, report_assertion_avtab_matches, &args); + + return args.errors; +} + +static int check_assertion_avtab_match(avtab_key_t *k, avtab_datum_t *d, void *args) +{ + int rc; + struct avtab_match_args *a = (struct avtab_match_args *)args; + policydb_t *p = a->p; + avrule_t *avrule = a->avrule; + class_perm_node_t *cp; + + if (k->specified != AVTAB_ALLOWED) + goto exit; + + for (cp = avrule->perms; cp; cp = cp->next) { + if ((cp->tclass == k->target_class) && (cp->data & d->data)) { + break; + } + } + if (!cp) + goto exit; + + rc = ebitmap_match_any(&avrule->stypes.types, &p->attr_type_map[k->source_type - 1]); + if (rc == 0) + goto exit; + + if (avrule->flags == RULE_SELF) { + /* If the neverallow uses SELF, then it is not enough that the + * neverallow's source matches the src and tgt of the rule being checked. + * It must match the same thing in the src and tgt, so AND the source + * and target together and check for a match on the result. + */ + ebitmap_t match; + ebitmap_init(&match); + ebitmap_and(&match, &p->attr_type_map[k->source_type - 1], &p->attr_type_map[k->target_type - 1] ); + rc = ebitmap_match_any(&avrule->stypes.types, &match); + ebitmap_destroy(&match); + } else { + rc = ebitmap_match_any(&avrule->ttypes.types, &p->attr_type_map[k->target_type -1]); + } + if (rc == 0) + goto exit; + + return 1; + +exit: + return 0; +}Seems like we are duplicating a lot of logic between the check and report functions. I assume you split them so that the check function could be reused for CIL. Can we perhaps take the common code though to a shared helper or macro?It is split so it can be reused for CIL. I'll see if I can factor out some of the common code.+ +int check_assertion(policydb_t *p, avrule_t *avrule) +{ + int rc; + struct avtab_match_args args; + + args.handle = NULL; + args.p = p; + args.avrule = avrule; + args.errors = 0; + + rc = avtab_map(&p->te_avtab, check_assertion_avtab_match, &args); + + if (rc == 0) { + rc = avtab_map(&p->te_cond_avtab, check_assertion_avtab_match, &args); + } + + return rc; } int check_assertions(sepol_handle_t * handle, policydb_t * p, avrule_t * avrules) { + int rc; avrule_t *a; - avtab_t te_avtab, te_cond_avtab; - ebitmap_node_t *snode, *tnode; - unsigned int i, j; unsigned long errors = 0; if (!avrules) { @@ -111,54 +211,17 @@ int check_assertions(sepol_handle_t * handle, policydb_t * p, return 0; } - if (avrules) { - if (avtab_init(&te_avtab)) - goto oom; - if (avtab_init(&te_cond_avtab)) { - avtab_destroy(&te_avtab); - goto oom; - } - if (expand_avtab(p, &p->te_avtab, &te_avtab) || - expand_avtab(p, &p->te_cond_avtab, &te_cond_avtab)) { - avtab_destroy(&te_avtab); - avtab_destroy(&te_cond_avtab); - goto oom; - } - } - for (a = avrules; a != NULL; a = a->next) { - ebitmap_t *stypes = &a->stypes.types; - ebitmap_t *ttypes = &a->ttypes.types; - if (!(a->specified & AVRULE_NEVERALLOW)) continue; - - ebitmap_for_each_bit(stypes, snode, i) { - if (!ebitmap_node_get_bit(snode, i)) - continue; - if (a->flags & RULE_SELF) { - errors += check_assertion_helper - (handle, p, &te_avtab, &te_cond_avtab, i, i, - a); - } - ebitmap_for_each_bit(ttypes, tnode, j) { - if (!ebitmap_node_get_bit(tnode, j)) - continue; - errors += check_assertion_helper - (handle, p, &te_avtab, &te_cond_avtab, i, j, - a); - } + rc = check_assertion(p, a); + if (rc) { + errors += report_assertion_failures(handle, p, a); } } if (errors) ERR(handle, "%lu neverallow failures occurred", errors); - avtab_destroy(&te_avtab); - avtab_destroy(&te_cond_avtab); return errors ? -1 : 0; - - oom: - ERR(handle, "Out of memory - unable to check neverallows"); - return -1; }
-- James Carter <jwcart2@xxxxxxxxxxxxx> National Security Agency _______________________________________________ Selinux mailing list Selinux@xxxxxxxxxxxxx To unsubscribe, send email to Selinux-leave@xxxxxxxxxxxxx. To get help, send an email containing "help" to Selinux-request@xxxxxxxxxxxxx.
