source: libabac/abac_graph.c @ 7764378

abac0-leak
Last change on this file since 7764378 was f2622ee, checked in by Mei-Hui Su <mei@…>, 6 years ago

1) ran with valgrind and did some leak patching

  • Property mode set to 100644
File size: 20.0 KB
Line 
1#include <assert.h>
2#include <stdlib.h>
3
4#include "abac_graph.h"
5
6#include "abac_set.h"
7#include "abac_util.h"
8
9#include "uthash.h"
10
11// vertex
12struct _abac_vertex_t {
13    abac_role_t *role;
14    char *name;
15    int refcount;
16
17    abac_list_t *edges;
18    abac_list_t *reverse_edges;
19
20    // only relevant to intersection edges
21    abac_list_t *prereqs;
22
23    UT_hash_handle hh;
24};
25
26// edge
27typedef struct _abac_edge_t {
28    int refcount;
29    abac_vertex_t *vertex;
30    abac_vertex_t *reverse_vertex;
31    abac_credential_t *credential;
32} abac_edge_t;
33
34// derived edge
35typedef struct _abac_derived_key_t {
36    abac_vertex_t *head;
37    abac_edge_t *tail;
38} abac_derived_key_t;
39
40typedef struct _abac_derived_t {
41    abac_derived_key_t key;
42    UT_hash_handle hh;
43} abac_derived_t;
44
45// graph
46struct _abac_graph_t {
47    abac_vertex_t *vertices;
48    abac_derived_t *derived;
49    int dirty;
50};
51
52// ugghhhghhhghh need this for intersections
53abac_list_t *abac_role_prereqs(abac_role_t *);
54
55static abac_vertex_t *_dup_vertex(abac_vertex_t *v);
56
57/**
58 * Create a new graph.
59 */
60abac_graph_t *abac_graph_new(void) {
61    abac_graph_t *graph = abac_xmalloc(sizeof(abac_graph_t));
62
63    graph->vertices = NULL;
64    graph->derived = NULL;
65    graph->dirty = 0;
66
67    return graph;
68}
69
70/**
71 * Deep copy a graph.
72 */
73abac_graph_t *abac_graph_dup(abac_graph_t *graph) {
74    abac_vertex_t *vertex;
75    abac_edge_t *edge;
76
77    abac_graph_t *clone = abac_graph_new();
78
79    // copy the vertices edge by edge
80    for (vertex = graph->vertices; vertex != NULL; vertex = vertex->hh.next)
81        abac_list_foreach(vertex->edges, edge,
82            // only copy non-derived edges
83            if (edge->credential != NULL)
84                abac_graph_add_credential(clone, edge->credential);
85        );
86
87    return clone;
88}
89/**
90 * Add a vertex to the graph. Should only be called by
91 * abac_graph_add_credential. This returns an existing vertex with the refcount
92 * bumped, or a new vertex with a refcount of 1.  Either way it gets and
93 * references the vertex.
94 */
95static abac_vertex_t *_get_vertex(abac_graph_t *graph, abac_role_t *role) {
96    abac_vertex_t *vertex;
97    char *string;
98   
99    string =abac_role_string(role);
100    HASH_FIND_STR(graph->vertices, string, vertex);
101
102    // add the vertex if it doesn't exist
103    if (vertex == NULL) {
104        vertex = abac_xmalloc(sizeof(abac_vertex_t));
105        vertex->refcount = 1;
106        vertex->role = abac_role_dup(role);
107        vertex->name = abac_role_string(vertex->role);
108
109        // create the list of edges
110        vertex->edges = abac_list_new();
111        vertex->reverse_edges = abac_list_new();
112
113        // for intersections, always NULL on normal vertices
114        if (abac_role_is_intersection(role)) {
115            abac_role_t *prereq;
116            vertex->prereqs = abac_list_new();
117
118            // add each prereq to the vertex
119            abac_list_foreach(abac_role_prereqs(role), prereq,
120                abac_vertex_t *tail_vertex = _get_vertex(graph, prereq);
121                abac_list_add(vertex->prereqs, tail_vertex);
122            );
123        }
124
125        // normal edges have no prereqs
126        else
127            vertex->prereqs = NULL;
128
129        // add it to the vertices
130        HASH_ADD_KEYPTR(hh, graph->vertices, vertex->name, strlen(vertex->name), vertex);
131
132        } else {
133            _dup_vertex(vertex);
134
135    }
136
137    return vertex;
138}
139
140/* forward decl */
141static void _free_edge(abac_edge_t *edge);
142/*
143 * Reduce the vertex reference count and free it if this is the last reference
144 */
145static void _free_vertex(abac_vertex_t *vertex) {
146    abac_edge_t *edge=NULL;
147    abac_vertex_t *pre=NULL;
148
149    --vertex->refcount;
150    if ( vertex->refcount > 0) return;
151
152    abac_role_free(vertex->role);
153
154    abac_list_foreach(vertex->edges, edge,
155        _free_edge(edge);
156    );
157    abac_list_free(vertex->edges);
158
159    abac_list_foreach(vertex->reverse_edges, edge,
160        _free_edge(edge);
161    );
162    abac_list_free(vertex->reverse_edges);
163
164    // Free the prereqs
165    if (vertex->prereqs != NULL) {
166        abac_list_foreach(vertex->prereqs, pre,
167            if (pre != NULL) {
168                _free_vertex(pre);
169            }
170        );
171        abac_list_free(vertex->prereqs);
172    }
173
174    free(vertex);
175}
176
177/*
178 * Increment vertex reference count
179 */
180static abac_vertex_t *_dup_vertex(abac_vertex_t *v) {
181    v->refcount++;
182    return v;
183}
184
185
186/*
187 * create a new edge from the given head, tail and credential
188 */
189
190static abac_edge_t *_get_edge(abac_vertex_t *h, abac_vertex_t *t,
191        abac_credential_t *c) {
192
193    /* An edge does not own it's vertices.  Do not delete them from an edge
194     * reference. */
195    abac_edge_t *edge = abac_xmalloc(sizeof(abac_edge_t));
196    edge->refcount = 1;
197    edge->vertex = t;
198    edge->reverse_vertex = h;
199    /* Don't dup a null credential */
200    edge->credential = (c) ? abac_credential_dup(c): NULL;
201
202    return edge;
203}
204
205
206/**
207 * Increment the reference count
208 */
209static abac_edge_t *_dup_edge(abac_edge_t *e) {
210    e->refcount++;
211    return e;
212}
213
214/**
215 * Decerement the refcount and free it if this was the last reference.  NB
216 * edges do not own teh vertices, so they must be deleted elsewhere.
217 */
218static void _free_edge(abac_edge_t *edge) {
219    assert(edge && edge->refcount > 0);
220    if ( --edge->refcount > 0) return;
221    if (edge->credential) abac_credential_free(edge->credential);
222    free(edge);
223}
224
225/**
226 * Add a credential to the credential graph.
227 */
228int abac_graph_add_credential(abac_graph_t *graph, abac_credential_t *cred) {
229    abac_vertex_t *head_vertex, *tail_vertex;
230    abac_edge_t *edge;
231
232    assert(cred != NULL);
233
234    abac_role_t *head = abac_credential_head(cred);
235    abac_role_t *tail = abac_credential_tail(cred);
236
237    // a valid credential must have a role for the head
238    if (!abac_role_is_role(head)) return 0;
239
240    head_vertex = _get_vertex(graph, head);
241    tail_vertex = _get_vertex(graph, tail);
242
243    // make sure we don't insert the same edge twice (ugh)
244    abac_list_foreach(head_vertex->edges, edge,
245        if (edge->vertex == tail_vertex) {
246            _free_vertex(head_vertex);
247            _free_vertex(tail_vertex);
248            return 0;
249        }
250    );
251
252    // create the edge and add it
253    edge = _get_edge(head_vertex, tail_vertex, cred);
254
255    abac_list_add(head_vertex->edges, edge);
256    abac_list_add(tail_vertex->reverse_edges, _dup_edge(edge));
257
258    // must re-derive edges
259    graph->dirty = 1;
260
261    return 1;
262}
263
264// find the principals that have a role
265static abac_set_t *_find_principals(abac_graph_t *graph, abac_vertex_t *start_vertex) {
266    abac_set_t *principals = abac_set_new();
267
268    abac_list_t *traversal = abac_graph_postorder(graph, start_vertex->role);
269    abac_vertex_t *vertex;
270
271    abac_list_foreach(traversal, vertex,
272        if (abac_role_is_principal(vertex->role))
273            abac_set_add(principals, abac_role_string(vertex->role));
274        /* ???  _free_vertex(vertex); */
275    );
276
277    abac_list_free(traversal);
278    return principals;
279}
280
281// remove any derived edges from the graph
282void _clear_derived(abac_graph_t *graph) {
283    abac_derived_t *current;
284
285    while (graph->derived) {
286        current = graph->derived;
287
288        HASH_DEL(graph->derived, current);
289
290        abac_vertex_t *head = current->key.head;
291        abac_edge_t *tail = current->key.tail;
292        assert(tail->credential == NULL);
293
294        // this can fail, but we assume the data structures are consistent
295        abac_list_remove(head->edges, tail);
296        abac_list_remove(tail->reverse_vertex->edges, tail);
297
298        free(current);
299        _free_edge(tail);
300    }
301}
302
303// add a derived edge, returns 1 if added 0 if dup
304static int _derived_edge(abac_graph_t *graph, abac_vertex_t *head, abac_vertex_t *tail) {
305    abac_edge_t *edge;
306
307    // don't add duplicate edges
308    abac_list_foreach(head->edges, edge,
309        if (edge->vertex == tail)
310            return 0;
311    );
312
313    debug_printf("derived edge %s <- %s\n", head->name, tail->name);
314
315    edge = _get_edge(head, tail, NULL);
316    abac_list_add(head->edges, edge);
317    abac_list_add(tail->reverse_edges, _dup_edge(edge));
318
319    // add to list of derived edges
320    abac_derived_t *derived = abac_xmalloc(sizeof(abac_derived_t));
321    derived->key.head = head;
322    derived->key.tail = edge;
323    HASH_ADD(hh, graph->derived, key, sizeof(abac_derived_key_t), derived);
324
325    return 1;
326}
327
328// find a vertex by name
329abac_vertex_t *_find_vertex(abac_graph_t *graph, char *name) {
330    abac_vertex_t *ret = NULL;
331    HASH_FIND_STR(graph->vertices, name, ret);
332    return ret;
333}
334
335/**
336 * Single iteration of deriving new edges. Returns the number of new edges
337 * added.
338 */
339static int _derive_links_iter(abac_graph_t *graph) {
340    int count = 0;
341    abac_vertex_t *vertex;
342
343    for (vertex = graph->vertices; vertex != NULL; vertex = vertex->hh.next) {
344        // intersection
345        if (abac_role_is_intersection(vertex->role)) {
346            // for each prereq edge:
347            //     find principals that have the edge
348            // find intersection of all sets
349            // for each principal B in intersection:
350            //     add link
351
352            char *name;
353            abac_vertex_t *prereq;
354            abac_set_t *principals = NULL;
355
356            abac_list_foreach(vertex->prereqs, prereq,
357                abac_set_t *cur = _find_principals(graph, prereq);
358
359                if (principals == NULL)
360                    principals = cur;
361                else {
362                    abac_set_intersect(principals, cur);
363                    abac_set_free(cur);
364                }
365
366                if (abac_set_size(principals) == 0)
367                    goto isect_done;
368            );
369
370            abac_list_t *prin_names = abac_set_elements(principals);
371            abac_list_foreach(prin_names, name,
372                abac_vertex_t *principal = _find_vertex(graph, name);
373                count += _derived_edge(graph, vertex, principal);
374            );
375
376            abac_list_free(prin_names);
377isect_done:
378            abac_set_free(principals);
379        }
380
381        // linking role
382        else if (abac_role_is_linking(vertex->role)) {
383            // linking roles take the form A.r1.r2
384            char *A_r1 = abac_role_linked_role(vertex->role);
385            char *r2 = abac_role_role_name(vertex->role);
386
387            // find the linked role in the graph
388            abac_vertex_t *A_r1_vertex;
389            HASH_FIND_STR(graph->vertices, A_r1, A_r1_vertex);
390            if (A_r1_vertex == NULL)
391                continue;
392
393            // find the principals that have A.r1
394            abac_set_t *principals = _find_principals(graph, A_r1_vertex);
395            char *B;
396
397            abac_list_t *elts = abac_set_elements(principals);
398
399            // and add a link for each B.r2 to A.r1.r2
400            abac_list_foreach(elts, B,
401                int B_len = strlen(B);
402                int r2_len = strlen(r2);
403
404                // create the string B.r2, thx C
405                char *B_r2 = malloc(B_len + r2_len + 2);
406                memcpy(B_r2, B, B_len);
407                B_r2[B_len] = '.';
408                memcpy(B_r2 + B_len + 1, r2, r2_len);
409                B_r2[B_len + r2_len + 1] = 0;
410
411                // add an edge if the principal's granted it to someone
412                abac_vertex_t *B_r2_vertex = _find_vertex(graph, B_r2);
413                if (B_r2_vertex) {
414                    debug_printf("adding edge from %s to %s\n", B_r2, abac_role_string(vertex->role));
415                    count += _derived_edge(graph, vertex, B_r2_vertex);
416                }
417
418#ifdef DEBUG
419                debug_printf("    incoming edges for %s\n", abac_role_string(vertex->role));
420                abac_edge_t *cur;
421                abac_list_foreach(vertex->edges, cur,
422                    debug_printf("        %s (%s)\n", abac_role_string(cur->vertex->role), cur->vertex->name);
423                );
424#endif
425
426                free(B_r2);
427            );
428
429            abac_list_free(elts);
430            abac_set_free(principals);
431        }
432    }
433
434    return count;
435}
436
437/**
438 * Derive all implied edges in the graph. These can come from linking roles
439 * and intersections.
440 *
441 * We have to do it iteratively because derived edges can imply new edges.
442 */
443void abac_graph_derive_links(abac_graph_t *graph) {
444    if (!graph->dirty)
445        return;
446
447    // iterate as long as new links are derived
448    while (_derive_links_iter(graph) > 0)
449        ;
450
451    graph->dirty = 0;
452}
453
454static void _reverse_order_recurse(abac_vertex_t *vertex, abac_set_t *seen, int preorder, abac_list_t *stack) {
455    abac_edge_t *outgoing;
456
457    // don't revisit nodes
458    if (!abac_set_add(seen, abac_role_string(vertex->role)))
459        return;
460
461    if (preorder)
462        abac_list_add(stack, vertex);
463
464    // recurse along the incoming vertices
465    abac_list_foreach(vertex->reverse_edges, outgoing,
466        _reverse_order_recurse(outgoing->reverse_vertex, seen, preorder, stack);
467    );
468
469    if (!preorder)
470        abac_list_add(stack, vertex);
471}
472
473static abac_list_t *_reverse_order(abac_graph_t *graph, abac_role_t *start, int preorder) {
474    debug_printf("%sorder at %s\n", preorder ? "pre" : "post", abac_role_string(start));
475
476    abac_vertex_t *start_vertex = _get_vertex(graph, start);
477    abac_set_t *seen = abac_set_new();
478
479    // create the return list
480    abac_list_t *stack = abac_list_new();
481
482    _reverse_order_recurse(start_vertex, seen, preorder, stack);
483
484    abac_set_free(seen);
485
486/*??? _free_vertex(start_vertex); */
487
488    return stack;
489}
490
491static void _order_recurse(abac_vertex_t *vertex, abac_set_t *seen, int preorder, abac_list_t *stack) {
492    abac_edge_t *incoming;
493
494    // don't revisit nodes
495    if (!abac_set_add(seen, abac_role_string(vertex->role)))
496        return;
497
498    if (preorder)
499        abac_list_add(stack, vertex);
500
501    // recurse along the incoming vertices
502    abac_list_foreach(vertex->edges, incoming,
503        _order_recurse(incoming->vertex, seen, preorder, stack);
504    );
505
506    if (!preorder)
507        abac_list_add(stack, vertex);
508}
509
510static abac_list_t *_order(abac_graph_t *graph, abac_role_t *start, int preorder) {
511    debug_printf("%sorder at %s\n", preorder ? "pre" : "post", abac_role_string(start));
512
513    abac_vertex_t *start_vertex = _get_vertex(graph, start);
514    abac_set_t *seen = abac_set_new();
515
516    // create the return list
517    abac_list_t *stack = abac_list_new();
518
519    _order_recurse(start_vertex, seen, preorder, stack);
520
521    abac_set_free(seen);
522
523/* ???  _free_vertex(start_vertex); */
524
525    return stack;
526}
527
528abac_list_t *abac_graph_postorder(abac_graph_t *graph, abac_role_t *start) {
529    return _order(graph, start, 0);
530}
531
532/**
533 * Postorder traverse the graph and return all the credentials within.
534 */
535abac_list_t *abac_graph_postorder_credentials(abac_graph_t *graph, char *start) {
536    abac_vertex_t *vertex;
537    abac_edge_t *incoming;
538
539    // get the postorder of vertices
540    abac_role_t *role = abac_role_from_string(start);
541    abac_list_t *order = abac_graph_postorder(graph, role);
542
543    // go through the list and dup all the credentials
544    abac_list_t *credentials = abac_list_new();
545    abac_list_foreach(order, vertex,
546        abac_list_foreach(vertex->edges, incoming,
547            if (incoming->credential != NULL)
548                abac_list_add(credentials, abac_credential_dup(incoming->credential));
549        );
550        /* ???  _free_vertex(vertex); */ 
551    );
552
553    abac_role_free(role);
554    abac_list_free(order);
555
556    return credentials;
557}
558
559
560abac_list_t *abac_graph_postorder_reverse(abac_graph_t *graph, abac_role_t *start) {
561    return _reverse_order(graph, start, 0);
562}
563
564/**
565 * Postorder traverse the graph and return all the credentials within.
566 */
567abac_list_t *abac_graph_postorder_reverse_credentials(abac_graph_t *graph, char *start) {
568    abac_vertex_t *vertex;
569    abac_edge_t *outgoing;
570
571    // get the postorder of vertices
572    abac_role_t *role = abac_role_from_string(start);
573    abac_list_t *order = abac_graph_postorder_reverse(graph, role);
574
575    // go through the list and dup all the credentials
576    abac_list_t *credentials = abac_list_new();
577    abac_list_foreach(order, vertex,
578        abac_list_foreach(vertex->reverse_edges, outgoing,
579            if (outgoing->credential != NULL)
580                abac_list_add(credentials, abac_credential_dup(outgoing->credential));
581        );
582        /* ???  _free_vertex(vertex); */
583    );
584
585    abac_role_free(role);
586    abac_list_free(order);
587
588    return credentials;
589}
590
591static void _query(abac_graph_t *graph, char *role_name, char *principal, abac_graph_t *return_graph) {
592    abac_vertex_t *vertex;
593    abac_edge_t *incoming;
594
595    abac_role_t *role = abac_role_from_string(role_name);
596    abac_role_t *prin_role = abac_role_from_string(principal);
597
598    // give up on bogus roles
599    if (role == NULL || prin_role == NULL) {
600        abac_role_free(role);
601        abac_role_free(prin_role);
602        return;
603    }
604
605    abac_set_t *on_path = abac_set_new();
606    abac_set_add(on_path, abac_role_string(prin_role));
607
608    abac_list_t *traversal = abac_graph_postorder(graph, role);
609    abac_list_foreach(traversal, vertex,
610        abac_role_t *role = vertex->role;
611
612        abac_list_foreach(vertex->edges, incoming,
613            abac_role_t *incoming_role = incoming->vertex->role;
614
615            if (!abac_set_contains(on_path, abac_role_string(incoming_role)))
616                continue;
617
618            abac_set_add(on_path, abac_role_string(role));
619
620            // get implying edges for intersection vertices
621            if (abac_role_is_intersection(role)) {
622                abac_vertex_t *prereq;
623                abac_list_foreach(vertex->prereqs, prereq,
624                    _query(graph, prereq->name, principal, return_graph);
625                );
626            }
627
628            // recursively find linked roles
629            else if (abac_role_is_linking(role)) {
630                char *linked_role = abac_role_linked_role(role);
631                char *principal = abac_role_principal(incoming_role);
632
633                _query(graph, linked_role, principal, return_graph);
634            }
635
636            // add non-derived edges to the proof graph
637            else
638                abac_graph_add_credential(return_graph, incoming->credential);
639        );
640        /* ???  _free_vertex(vertex); */ 
641    );
642
643    abac_list_free(traversal);
644    abac_set_free(on_path);
645    abac_role_free(role);
646    abac_role_free(prin_role);
647}
648
649abac_graph_t *abac_graph_query(abac_graph_t *graph, char *role, char *principal) {
650    abac_graph_derive_links(graph);
651
652    abac_graph_t *return_graph = abac_graph_new();
653    _query(graph, role, principal, return_graph);
654    abac_graph_derive_links(return_graph);
655    return return_graph;
656}
657
658abac_graph_t *abac_graph_principal_creds(abac_graph_t *graph, char *principal) {
659    abac_graph_derive_links(graph);
660    abac_graph_t *result_graph = abac_graph_new();
661    abac_list_t *result = abac_graph_postorder_reverse_credentials(graph, 
662            principal);
663    abac_credential_t *cur = NULL;
664    abac_list_foreach(result, cur,
665        abac_graph_add_credential(result_graph, cur);
666    );
667    abac_list_free(result);
668    /* For each terminal role that the principal can reach, roll a proof into
669       the result_graph. */
670    abac_vertex_t *vertex = NULL;
671    for (vertex = result_graph->vertices; vertex != NULL; 
672            vertex = vertex->hh.next) {
673        if ( abac_list_size(vertex->reverse_edges) == 0) 
674            _query(graph, vertex->name, principal, result_graph);
675    }
676    abac_graph_derive_links(result_graph);
677    return result_graph;
678}
679
680
681/**
682 * Get all the credentials (attribute/issuer cert pairs) from the graph.
683 */
684abac_list_t *abac_graph_credentials(abac_graph_t *graph) {
685    abac_list_t *credentials = abac_list_new();
686
687    abac_vertex_t *vertex;
688
689    for (vertex = graph->vertices; vertex != NULL; vertex = vertex->hh.next) {
690        abac_edge_t *edge;
691        abac_list_foreach(vertex->edges, edge,
692            if (edge->credential != NULL)
693                abac_list_add(credentials, abac_credential_dup(edge->credential));
694        );
695    }
696
697    return credentials;
698}
699
700void abac_graph_free(abac_graph_t *graph) {
701    abac_vertex_t *vertex;
702    abac_edge_t *edge;
703
704    // kill derived edges
705    _clear_derived(graph);
706
707    // delete vertices
708    while ((vertex = graph->vertices) != NULL) {
709        HASH_DEL(graph->vertices, vertex);
710        _free_vertex(vertex);
711    }
712
713    free(graph);
714}
715
716abac_role_t *abac_vertex_role(abac_vertex_t *vertex) {
717    return vertex->role;
718}
Note: See TracBrowser for help on using the repository browser.