1#include <getopt.h>
2#include <sepol/policydb/expand.h>
3
4#include "typecmp.h"
5
6void typecmp_usage() {
7    fprintf(stderr, "\ttypecmp [-d|--diff] [-e|--equiv]\n");
8}
9
10static int insert_type_rule(avtab_key_t * k, avtab_datum_t * d,
11                            struct avtab_node *type_rules)
12{
13    struct avtab_node *p, *c, *n;
14
15    for (p = type_rules, c = type_rules->next; c; p = c, c = c->next) {
16        /*
17         * Find the insertion point, keeping the list
18         * ordered by source type, then target type, then
19         * target class.
20         */
21        if (k->source_type < c->key.source_type)
22            break;
23        if (k->source_type == c->key.source_type &&
24            k->target_type < c->key.target_type)
25            break;
26        if (k->source_type == c->key.source_type &&
27            k->target_type == c->key.target_type &&
28            k->target_class <= c->key.target_class)
29            break;
30    }
31
32    if (c &&
33        k->source_type == c->key.source_type &&
34        k->target_type == c->key.target_type &&
35        k->target_class == c->key.target_class) {
36        c->datum.data |= d->data;
37        return 0;
38    }
39
40    /* Insert the rule */
41    n = malloc(sizeof(struct avtab_node));
42    if (!n) {
43        fprintf(stderr, "out of memory\n");
44        exit(1);
45    }
46
47    n->key = *k;
48    n->datum = *d;
49    n->next = p->next;
50    p->next = n;
51    return 0;
52}
53
54static int create_type_rules_helper(avtab_key_t * k, avtab_datum_t * d,
55                                    void *args)
56{
57    struct avtab_node *type_rules = args;
58    avtab_key_t key;
59
60    /*
61     * Insert the rule into the list for
62     * the source type.  The source type value
63     * is cleared as we want to compare against other type
64     * rules with different source types.
65     */
66    key = *k;
67    key.source_type = 0;
68    if (k->source_type == k->target_type) {
69        /* Clear target type as well; this is a self rule. */
70        key.target_type = 0;
71    }
72    if (insert_type_rule(&key, d, &type_rules[k->source_type - 1]))
73        return -1;
74
75    if (k->source_type == k->target_type)
76        return 0;
77
78    /*
79     * If the target type differs, then we also
80     * insert the rule into the list for the target
81     * type.  We clear the target type value so that
82     * we can compare against other type rules with
83     * different target types.
84     */
85    key = *k;
86    key.target_type = 0;
87    if (insert_type_rule(&key, d, &type_rules[k->target_type - 1]))
88        return -1;
89
90    return 0;
91}
92
93static int create_type_rules(avtab_key_t * k, avtab_datum_t * d, void *args)
94{
95    if (k->specified & AVTAB_ALLOWED)
96        return create_type_rules_helper(k, d, args);
97    return 0;
98}
99
100static int create_type_rules_cond(avtab_key_t * k, avtab_datum_t * d,
101                                  void *args)
102{
103    if ((k->specified & (AVTAB_ALLOWED|AVTAB_ENABLED)) ==
104        (AVTAB_ALLOWED|AVTAB_ENABLED))
105        return create_type_rules_helper(k, d, args);
106    return 0;
107}
108
109static void free_type_rules(struct avtab_node *l)
110{
111    struct avtab_node *tmp;
112
113    while (l) {
114        tmp = l;
115        l = l->next;
116        free(tmp);
117    }
118}
119
120static int find_match(policydb_t *policydb, struct avtab_node *l1,
121                      int idx1, struct avtab_node *l2, int idx2)
122{
123    struct avtab_node *c;
124    uint32_t perms1, perms2;
125
126    for (c = l2; c; c = c->next) {
127        if (l1->key.source_type < c->key.source_type)
128            break;
129        if (l1->key.source_type == c->key.source_type &&
130            l1->key.target_type < c->key.target_type)
131            break;
132        if (l1->key.source_type == c->key.source_type &&
133            l1->key.target_type == c->key.target_type &&
134            l1->key.target_class <= c->key.target_class)
135            break;
136    }
137
138    if (c &&
139        l1->key.source_type == c->key.source_type &&
140        l1->key.target_type == c->key.target_type &&
141        l1->key.target_class == c->key.target_class) {
142        perms1 = l1->datum.data & ~c->datum.data;
143        perms2 = c->datum.data & ~l1->datum.data;
144        if (perms1 || perms2) {
145            if (perms1)
146                display_allow(policydb, &l1->key, idx1, perms1);
147            if (perms2)
148                display_allow(policydb, &c->key, idx2, perms2);
149            printf("\n");
150            return 1;
151        }
152    }
153
154    return 0;
155}
156
157static int analyze_types(policydb_t * policydb, char diff, char equiv)
158{
159    avtab_t exp_avtab, exp_cond_avtab;
160    struct avtab_node *type_rules, *l1, *l2;
161    struct type_datum *type;
162    size_t i, j;
163
164    /*
165     * Create a list of access vector rules for each type
166     * from the access vector table.
167     */
168    type_rules = malloc(sizeof(struct avtab_node) * policydb->p_types.nprim);
169    if (!type_rules) {
170        fprintf(stderr, "out of memory\n");
171        exit(1);
172    }
173    memset(type_rules, 0, sizeof(struct avtab_node) * policydb->p_types.nprim);
174
175    if (avtab_init(&exp_avtab) || avtab_init(&exp_cond_avtab)) {
176        fputs("out of memory\n", stderr);
177        return -1;
178    }
179
180    if (expand_avtab(policydb, &policydb->te_avtab, &exp_avtab)) {
181        fputs("out of memory\n", stderr);
182        avtab_destroy(&exp_avtab);
183        return -1;
184    }
185
186    if (expand_avtab(policydb, &policydb->te_cond_avtab, &exp_cond_avtab)) {
187        fputs("out of memory\n", stderr);
188        avtab_destroy(&exp_avtab); /*  */
189        return -1;
190    }
191
192    if (avtab_map(&exp_avtab, create_type_rules, type_rules))
193        exit(1);
194
195    if (avtab_map(&exp_cond_avtab, create_type_rules_cond, type_rules))
196        exit(1);
197
198    avtab_destroy(&exp_avtab);
199    avtab_destroy(&exp_cond_avtab);
200
201    /*
202     * Compare the type lists and identify similar types.
203     */
204    for (i = 0; i < policydb->p_types.nprim - 1; i++) {
205        if (!type_rules[i].next)
206            continue;
207        type = policydb->type_val_to_struct[i];
208        if (type->flavor) {
209            free_type_rules(type_rules[i].next);
210            type_rules[i].next = NULL;
211            continue;
212        }
213        for (j = i + 1; j < policydb->p_types.nprim; j++) {
214            type = policydb->type_val_to_struct[j];
215            if (type->flavor) {
216                free_type_rules(type_rules[j].next);
217                type_rules[j].next = NULL;
218                continue;
219            }
220            for (l1 = type_rules[i].next, l2 = type_rules[j].next;
221                 l1 && l2; l1 = l1->next, l2 = l2->next) {
222                if (l1->key.source_type != l2->key.source_type)
223                    break;
224                if (l1->key.target_type != l2->key.target_type)
225                    break;
226                if (l1->key.target_class != l2->key.target_class
227                    || l1->datum.data != l2->datum.data)
228                    break;
229            }
230            if (l1 || l2) {
231                if (diff) {
232                    printf
233                        ("Types %s and %s differ, starting with:\n",
234                         policydb->p_type_val_to_name[i],
235                         policydb->p_type_val_to_name[j]);
236
237                    if (l1 && l2) {
238                        if (find_match(policydb, l1, i, l2, j))
239                            continue;
240                        if (find_match(policydb, l2, j, l1, i))
241                            continue;
242                    }
243                    if (l1)
244                        display_allow(policydb, &l1->key, i, l1->datum.data);
245                    if (l2)
246                        display_allow(policydb, &l2->key, j, l2->datum.data);
247                    printf("\n");
248                }
249                continue;
250            }
251            free_type_rules(type_rules[j].next);
252            type_rules[j].next = NULL;
253            if (equiv) {
254                printf("Types %s and %s are equivalent.\n",
255                       policydb->p_type_val_to_name[i],
256                       policydb->p_type_val_to_name[j]);
257            }
258        }
259        free_type_rules(type_rules[i].next);
260        type_rules[i].next = NULL;
261    }
262
263    free(type_rules);
264    return 0;
265}
266
267int typecmp_func (int argc, char **argv, policydb_t *policydb) {
268    char ch, diff = 0, equiv = 0;
269
270    struct option typecmp_options[] = {
271        {"diff", no_argument, NULL, 'd'},
272        {"equiv", no_argument, NULL, 'e'},
273        {NULL, 0, NULL, 0}
274    };
275
276    while ((ch = getopt_long(argc, argv, "de", typecmp_options, NULL)) != -1) {
277        switch (ch) {
278        case 'd':
279            diff = 1;
280            break;
281        case 'e':
282            equiv = 1;
283            break;
284        default:
285            USAGE_ERROR = true;
286            return -1;
287        }
288    }
289
290    if (!(diff || equiv)) {
291        USAGE_ERROR = true;
292        return -1;
293    }
294    return analyze_types(policydb, diff, equiv);
295}
296