Add sepolicy-analyze tool.

And also remove the unnecessary references to libselinux for
sepolicy-check, as it has no dependencies on libselinux.
Also enable -Wall -Werror on building all of these tools and
fix up all such errors.

Usage:
$ sepolicy-analyze -e -P out/target/product/<device>/root/sepolicy
or
$ sepolicy-analyze -d -P out/target/product/<device>/root/sepolicy

The first form will display all type pairs that are "equivalent", i.e.
they are identical with respect to allow rules, including indirect allow
rules via attributes and default-enabled conditional rules (i.e. default
boolean values yield a true conditional expression).

Equivalent types are candidates for being coalesced into a single type.
However, there may be legitimate reasons for them to remain separate,
for example:
- the types may differ in a respect not included in the current
analysis, such as default-disabled conditional rules, audit-related
rules (auditallow or dontaudit), default type transitions, or
constraints (e.g. mls), or
- the current policy may be overly permissive with respect to one or the
other of the types and thus the correct action may be to tighten access
to one or the other rather than coalescing them together, or
- the domains that would in fact have different accesses to the types
may not yet be defined or may be unconfined in the policy you are
analyzing (e.g. in AOSP policy).

The second form will display type pairs that differ and the first
difference found between the two types.  This output can be long.

We have plans to explore further enhancements to this tool, including
support for identifying isomorphic types.  That will be required to
identify similar domains since all domains differ in at least their
entrypoint type and in their tmpfs type and thus will never show up as
equivalent even if they are in all other respects identical to each other.

Change-Id: If0ee00188469d2a1e165fdd52f235c705d22cd4e
Signed-off-by: Stephen Smalley <sds@tycho.nsa.gov>

1 files changed, 379 insertions, 0 deletions

diff --git a/tools/sepolicy-analyze.c b/tools/sepolicy-analyze.c
new file mode 100644
index 0000000..9b3d444
--- /dev/null
+++ b/tools/sepolicy-analyze.c
@@ -0,0 +1,379 @@
+#include <getopt.h>
+#include <unistd.h>
+#include <stddef.h>
+#include <stdlib.h>
+#include <sys/mman.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <stdio.h>
+#include <sepol/policydb/policydb.h>
+#include <sepol/policydb/services.h>
+#include <sepol/policydb/expand.h>
+#include <sepol/policydb/util.h>
+
+void usage(char *arg0)
+{
+    fprintf(stderr, "%s [-e|--equiv] [-d|--diff] -P <policy file>\n", arg0);
+    exit(1);
+}
+
+int load_policy(char *filename, policydb_t * policydb, struct policy_file *pf)
+{
+    int fd;
+    struct stat sb;
+    void *map;
+    int ret;
+
+    fd = open(filename, O_RDONLY);
+    if (fd < 0) {
+        fprintf(stderr, "Can't open '%s':  %s\n", filename, strerror(errno));
+        return 1;
+    }
+    if (fstat(fd, &sb) < 0) {
+        fprintf(stderr, "Can't stat '%s':  %s\n", filename, strerror(errno));
+        close(fd);
+        return 1;
+    }
+    map = mmap(NULL, sb.st_size, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);
+    if (map == MAP_FAILED) {
+        fprintf(stderr, "Can't mmap '%s':  %s\n", filename, strerror(errno));
+        close(fd);
+        return 1;
+    }
+
+    policy_file_init(pf);
+    pf->type = PF_USE_MEMORY;
+    pf->data = map;
+    pf->len = sb.st_size;
+    if (policydb_init(policydb)) {
+        fprintf(stderr, "Could not initialize policydb!\n");
+        close(fd);
+        munmap(map, sb.st_size);
+        return 1;
+    }
+    ret = policydb_read(policydb, pf, 0);
+    if (ret) {
+        fprintf(stderr, "error(s) encountered while parsing configuration\n");
+        close(fd);
+        munmap(map, sb.st_size);
+        return 1;
+    }
+
+    return 0;
+}
+
+static int insert_type_rule(avtab_key_t * k, avtab_datum_t * d,
+                            struct avtab_node *type_rules)
+{
+    struct avtab_node *p, *c, *n;
+
+    for (p = type_rules, c = type_rules->next; c; p = c, c = c->next) {
+        /*
+         * Find the insertion point, keeping the list
+         * ordered by source type, then target type, then
+         * target class.
+         */
+        if (k->source_type < c->key.source_type)
+            break;
+        if (k->source_type == c->key.source_type &&
+            k->target_type < c->key.target_type)
+            break;
+        if (k->source_type == c->key.source_type &&
+            k->target_type == c->key.target_type &&
+            k->target_class <= c->key.target_class)
+            break;
+    }
+
+    if (c &&
+        k->source_type == c->key.source_type &&
+        k->target_type == c->key.target_type &&
+        k->target_class == c->key.target_class) {
+        c->datum.data |= d->data;
+        return 0;
+    }
+
+    /* Insert the rule */
+    n = malloc(sizeof(struct avtab_node));
+    if (!n) {
+        fprintf(stderr, "out of memory\n");
+        exit(1);
+    }
+
+    n->key = *k;
+    n->datum = *d;
+    n->next = p->next;
+    p->next = n;
+    return 0;
+}
+
+static int create_type_rules_helper(avtab_key_t * k, avtab_datum_t * d,
+                                    void *args)
+{
+    struct avtab_node *type_rules = args;
+    avtab_key_t key;
+
+    /*
+     * Insert the rule into the list for
+     * the source type.  The source type value
+     * is cleared as we want to compare against other type
+     * rules with different source types.
+     */
+    key = *k;
+    key.source_type = 0;
+    if (k->source_type == k->target_type) {
+        /* Clear target type as well; this is a self rule. */
+        key.target_type = 0;
+    }
+    if (insert_type_rule(&key, d, &type_rules[k->source_type - 1]))
+        return -1;
+
+    if (k->source_type == k->target_type)
+        return 0;
+
+    /*
+     * If the target type differs, then we also
+     * insert the rule into the list for the target
+     * type.  We clear the target type value so that
+     * we can compare against other type rules with
+     * different target types.
+     */
+    key = *k;
+    key.target_type = 0;
+    if (insert_type_rule(&key, d, &type_rules[k->target_type - 1]))
+        return -1;
+
+    return 0;
+}
+
+static int create_type_rules(avtab_key_t * k, avtab_datum_t * d, void *args)
+{
+    if (k->specified & AVTAB_ALLOWED)
+        return create_type_rules_helper(k, d, args);
+    return 0;
+}
+
+static int create_type_rules_cond(avtab_key_t * k, avtab_datum_t * d,
+                                  void *args)
+{
+    if ((k->specified & (AVTAB_ALLOWED|AVTAB_ENABLED)) ==
+        (AVTAB_ALLOWED|AVTAB_ENABLED))
+        return create_type_rules_helper(k, d, args);
+    return 0;
+}
+
+static void free_type_rules(struct avtab_node *l)
+{
+    struct avtab_node *tmp;
+
+    while (l) {
+        tmp = l;
+        l = l->next;
+        free(tmp);
+    }
+}
+
+static void display_allow(policydb_t *policydb, struct avtab_node *n, int idx,
+                         uint32_t perms)
+{
+    printf("    allow %s %s:%s { %s };\n",
+           policydb->p_type_val_to_name[n->key.source_type
+                                        ? n->key.source_type - 1 : idx],
+           n->key.target_type == n->key.source_type ? "self" :
+           policydb->p_type_val_to_name[n->key.target_type
+                                        ? n->key.target_type - 1 : idx],
+           policydb->p_class_val_to_name[n->key.target_class - 1],
+           sepol_av_to_string
+           (policydb, n->key.target_class, perms));
+}
+
+static int find_match(policydb_t *policydb, struct avtab_node *l1,
+                      int idx1, struct avtab_node *l2, int idx2)
+{
+    struct avtab_node *c;
+    uint32_t perms1, perms2;
+
+    for (c = l2; c; c = c->next) {
+        if (l1->key.source_type < c->key.source_type)
+            break;
+        if (l1->key.source_type == c->key.source_type &&
+            l1->key.target_type < c->key.target_type)
+            break;
+        if (l1->key.source_type == c->key.source_type &&
+            l1->key.target_type == c->key.target_type &&
+            l1->key.target_class <= c->key.target_class)
+            break;
+    }
+
+    if (c &&
+        l1->key.source_type == c->key.source_type &&
+        l1->key.target_type == c->key.target_type &&
+        l1->key.target_class == c->key.target_class) {
+        perms1 = l1->datum.data & ~c->datum.data;
+        perms2 = c->datum.data & ~l1->datum.data;
+        if (perms1 || perms2) {
+            if (perms1)
+                display_allow(policydb, l1, idx1, perms1);
+            if (perms2)
+                display_allow(policydb, c, idx2, perms2);
+            printf("\n");
+            return 1;
+        }
+    }
+
+    return 0;
+}
+
+static int analyze_types(policydb_t * policydb, char equiv, char diff)
+{
+    avtab_t exp_avtab, exp_cond_avtab;
+    struct avtab_node *type_rules, *l1, *l2;
+    struct type_datum *type;
+    size_t i, j;
+
+    /*
+     * Create a list of access vector rules for each type
+     * from the access vector table.
+     */
+    type_rules = malloc(sizeof(struct avtab_node) * policydb->p_types.nprim);
+    if (!type_rules) {
+        fprintf(stderr, "out of memory\n");
+        exit(1);
+    }
+    memset(type_rules, 0, sizeof(struct avtab_node) * policydb->p_types.nprim);
+
+    if (avtab_init(&exp_avtab) || avtab_init(&exp_cond_avtab)) {
+        fputs("out of memory\n", stderr);
+        return -1;
+    }
+
+    if (expand_avtab(policydb, &policydb->te_avtab, &exp_avtab)) {
+        fputs("out of memory\n", stderr);
+        avtab_destroy(&exp_avtab);
+        return -1;
+    }
+
+    if (expand_avtab(policydb, &policydb->te_cond_avtab, &exp_cond_avtab)) {
+        fputs("out of memory\n", stderr);
+        avtab_destroy(&exp_avtab);
+        return -1;
+    }
+
+    if (avtab_map(&exp_avtab, create_type_rules, type_rules))
+        exit(1);
+
+    if (avtab_map(&exp_cond_avtab, create_type_rules_cond, type_rules))
+        exit(1);
+
+    avtab_destroy(&exp_avtab);
+    avtab_destroy(&exp_cond_avtab);
+
+    /*
+     * Compare the type lists and identify similar types.
+     */
+    for (i = 0; i < policydb->p_types.nprim - 1; i++) {
+        if (!type_rules[i].next)
+            continue;
+        type = policydb->type_val_to_struct[i];
+        if (type->flavor) {
+            free_type_rules(type_rules[i].next);
+            type_rules[i].next = NULL;
+            continue;
+        }
+        for (j = i + 1; j < policydb->p_types.nprim; j++) {
+            type = policydb->type_val_to_struct[j];
+            if (type->flavor) {
+                free_type_rules(type_rules[j].next);
+                type_rules[j].next = NULL;
+                continue;
+            }
+            for (l1 = type_rules[i].next, l2 = type_rules[j].next;
+                 l1 && l2; l1 = l1->next, l2 = l2->next) {
+                if (l1->key.source_type != l2->key.source_type)
+                    break;
+                if (l1->key.target_type != l2->key.target_type)
+                    break;
+                if (l1->key.target_class != l2->key.target_class
+                    || l1->datum.data != l2->datum.data)
+                    break;
+            }
+            if (l1 || l2) {
+                if (diff) {
+                    printf
+                        ("Types %s and %s differ, starting with:\n",
+                         policydb->p_type_val_to_name[i],
+                         policydb->p_type_val_to_name[j]);
+
+                    if (l1 && l2) {
+                        if (find_match(policydb, l1, i, l2, j))
+                            continue;
+                        if (find_match(policydb, l2, j, l1, i))
+                            continue;
+                    }
+                    if (l1)
+                        display_allow(policydb, l1, i, l1->datum.data);
+                    if (l2)
+                        display_allow(policydb, l2, j, l2->datum.data);
+                    printf("\n");
+                }
+                continue;
+            }
+            free_type_rules(type_rules[j].next);
+            type_rules[j].next = NULL;
+            if (equiv) {
+                printf("Types %s and %s are equivalent.\n",
+                       policydb->p_type_val_to_name[i],
+                       policydb->p_type_val_to_name[j]);
+            }
+        }
+        free_type_rules(type_rules[i].next);
+        type_rules[i].next = NULL;
+    }
+
+    free(type_rules);
+    return 0;
+}
+
+int main(int argc, char **argv)
+{
+    char *policy = NULL;
+    struct policy_file pf;
+    policydb_t policydb;
+    char ch;
+    char equiv = 0, diff = 0;
+
+    struct option long_options[] = {
+        {"equiv", no_argument, NULL, 'e'},
+        {"diff", no_argument, NULL, 'd'},
+        {"policy", required_argument, NULL, 'P'},
+        {NULL, 0, NULL, 0}
+    };
+
+    while ((ch = getopt_long(argc, argv, "edP:", long_options, NULL)) != -1) {
+        switch (ch) {
+        case 'e':
+            equiv = 1;
+            break;
+        case 'd':
+            diff = 1;
+            break;
+        case 'P':
+            policy = optarg;
+            break;
+        default:
+            usage(argv[0]);
+        }
+    }
+
+    if (!policy || (!equiv && !diff))
+        usage(argv[0]);
+
+    if (load_policy(policy, &policydb, &pf))
+        exit(1);
+
+    analyze_types(&policydb, equiv, diff);
+
+    policydb_destroy(&policydb);
+
+    return 0;
+}