From mboxrd@z Thu Jan 1 00:00:00 1970 Message-ID: <557AD936.7060005@tycho.nsa.gov> Date: Fri, 12 Jun 2015 09:05:58 -0400 From: James Carter MIME-Version: 1.0 To: Stephen Smalley , selinux@tycho.nsa.gov Subject: Re: [PATCH 03/10] libsepol: Refactored neverallow checking. References: <1434047207-25503-1-git-send-email-jwcart2@tycho.nsa.gov> <1434047207-25503-4-git-send-email-jwcart2@tycho.nsa.gov> <5579EA96.5020108@tycho.nsa.gov> <557AD7AB.1080408@tycho.nsa.gov> In-Reply-To: <557AD7AB.1080408@tycho.nsa.gov> Content-Type: text/plain; charset=windows-1252; format=flowed List-Id: "Security-Enhanced Linux \(SELinux\) mailing list" List-Post: List-Help: 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 >>> --- >>> 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 National Security Agency