On Thu, Sep 26, 2019 at 7:19 PM James Carter <jwcart2@xxxxxxxxxxxxx> wrote:
> This improves commit b8213acf (libsepol: add a function to optimize
> kernel policy) by Ondrej Mosnacek <omosnace@xxxxxxxxxx> by always
> removing redundant conditional rules which have an identical rule
> in the unconditional policy.
>
> Add a flag called not_cond to is_avrule_redundant(). When checking
> unconditional rules against the avtab (which stores the unconditional
> rules) we need to skip the actual rule that we are checking (otherwise
> a rule would be determined to be redundant with itself and bad things
> would happen), but when checking a conditional rule against the avtab
> we do not want to skip an identical rule (which is what currently
> happens), we want to remove the redundant permissions in the conditional
> rule.
>
> A couple of examples to illustrate when redundant condtional rules
> are not removed.
>
> Example 1
> allow t1 t2:class1 perm1;
> if (bool1) {
> allow t1 t2:class1 perm1;
> }
> The conditional rule is clearly redundant, but without this change it
> will not be removed, because of the check for an identical rule.
>
> Example 2
> typeattribute t1 a1;
> allow t1 t2:class1 perm1;
> allow a1 t2:class1 perm1;
> if (bool1) {
> allow t1 t2:class1 perm1;
> }
> The conditional rule is again clearly redundant, but now the order of
> processing during the optimization will determine whether or not the
> rule is removed. Because a1 contains only t1, a1 and t1 are considered
> to be supersets of each other. If the rule with the attribute is
> processed first, then it will be determined to be redundant and
> removed, so the conditional rule will not be removed. But if the rule
> with the type is processed first, then it will be removed and the
> conditional rule will be determined to be redundant with the rule with
> the attribute and removed as well.
>
> The change reduces the size of policy a bit more than the original
> optimization. Looking at the change in number of allow rules, there is
> about a 10% improvement over the old optimization.
> orig old new
> Refpolicy 113284 82467 78053
> Fedora 106410 64015 60008
>
> Signed-off-by: James Carter <jwcart2@xxxxxxxxxxxxx>
Nice improvement, thanks!
Reviewed-by: Ondrej Mosnacek <omosnace@xxxxxxxxxx>
> ---
> libsepol/src/optimize.c | 8 ++++----
> 1 file changed, 4 insertions(+), 4 deletions(-)
>
> diff --git a/libsepol/src/optimize.c b/libsepol/src/optimize.c
> index 10399a43..1e5e97e8 100644
> --- a/libsepol/src/optimize.c
> +++ b/libsepol/src/optimize.c
> @@ -123,7 +123,7 @@ static int process_avtab_datum(uint16_t specified,
>
> /* checks if avtab contains a rule that covers the given rule */
> static int is_avrule_redundant(avtab_ptr_t entry, avtab_t *tab,
> - const ebitmap_t *type_map)
> + const ebitmap_t *type_map, unsigned char not_cond)
> {
> unsigned int i, k, s_idx, t_idx;
> ebitmap_node_t *snode, *tnode;
> @@ -146,7 +146,7 @@ static int is_avrule_redundant(avtab_ptr_t entry, avtab_t *tab,
> key.source_type = i + 1;
>
> ebitmap_for_each_positive_bit(&type_map[t_idx], tnode, k) {
> - if (s_idx == i && t_idx == k)
> + if (not_cond && s_idx == i && t_idx == k)
> continue;
>
> key.target_type = k + 1;
> @@ -223,7 +223,7 @@ static void optimize_avtab(policydb_t *p, const ebitmap_t *type_map)
> for (i = 0; i < tab->nslot; i++) {
> cur = &tab->htable[i];
> while (*cur) {
> - if (is_avrule_redundant(*cur, tab, type_map)) {
> + if (is_avrule_redundant(*cur, tab, type_map, 1)) {
> /* redundant rule -> remove it */
> avtab_ptr_t tmp = *cur;
>
> @@ -279,7 +279,7 @@ static void optimize_cond_av_list(cond_av_list_t **cond, cond_av_list_t **del,
> * First check if covered by an unconditional rule, then also
> * check if covered by another rule in the same list.
> */
> - if (is_avrule_redundant((*cond)->node, &p->te_avtab, type_map) ||
> + if (is_avrule_redundant((*cond)->node, &p->te_avtab, type_map, 0) ||
> is_cond_rule_redundant((*cond)->node, *pcov_cur, type_map)) {
> cond_av_list_t *tmp = *cond;
>
> --
> 2.21.0
>
--
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.
