source: libabac/abac_graph.c @ cb135e1

abac0-leak
Last change on this file since cb135e1 was cb135e1, checked in by Mei <mei@…>, 7 years ago

1) mark off couple of debug statements

  • Property mode set to 100644
File size: 19.8 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
11int debug=0;
12
13// vertex
14struct _abac_vertex_t {
15    abac_role_t *role;
16    char *name;
17    int refcount;
18
19    abac_list_t *edges;
20    abac_list_t *reverse_edges;
21
22    // only relevant to intersection edges
23    abac_list_t *prereqs;
24
25    UT_hash_handle hh;
26};
27
28// edge
29typedef struct _abac_edge_t {
30    int refcount;
31    abac_vertex_t *vertex;
32    abac_vertex_t *reverse_vertex;
33    abac_credential_t *credential;
34} abac_edge_t;
35
36// derived edge
37typedef struct _abac_derived_key_t {
38    abac_vertex_t *head;
39    abac_edge_t *tail;
40} abac_derived_key_t;
41
42typedef struct _abac_derived_t {
43    abac_derived_key_t key;
44    UT_hash_handle hh;
45} abac_derived_t;
46
47// graph
48struct _abac_graph_t {
49    abac_vertex_t *vertices;
50    abac_derived_t *derived;
51    int dirty;
52};
53
54// ugghhhghhhghh need this for intersections
55abac_list_t *abac_role_prereqs(abac_role_t *);
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 = 0;
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                if(debug) printf("XXX add a prereq to vertex\n");
123            );
124        }
125
126        // normal edges have no prereqs
127        else
128            vertex->prereqs = NULL;
129
130        // add it to the vertices
131        HASH_ADD_KEYPTR(hh, graph->vertices, vertex->name, strlen(vertex->name), vertex);
132    }
133    vertex->refcount++;
134
135    return vertex;
136}
137
138/* forward decl */
139static void _free_edge(abac_edge_t *edge);
140/*
141 * Reduce the vertex reference count and free it if this is the last reference
142 */
143static void _free_vertex(abac_vertex_t *vertex) {
144    abac_edge_t *edge=NULL;
145    abac_vertex_t *pre=NULL;
146
147    --vertex->refcount;
148
149    if ( vertex->refcount > 0) return;
150
151    abac_role_free(vertex->role);
152
153    abac_list_foreach(vertex->edges, edge,
154        _free_edge(edge);
155    );
156    abac_list_free(vertex->edges);
157
158    abac_list_foreach(vertex->reverse_edges, edge,
159        _free_edge(edge);
160    );
161    abac_list_free(vertex->reverse_edges);
162
163    // Free the prereqs
164    if (vertex->prereqs != NULL) {
165        abac_list_foreach(vertex->prereqs, pre,
166            if (pre != NULL) {
167                _free_vertex(pre);
168                if(debug) printf("YYY free a prereq to vertex\n");
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    );
275
276    abac_list_free(traversal);
277    return principals;
278}
279
280// remove any derived edges from the graph
281void _clear_derived(abac_graph_t *graph) {
282    abac_derived_t *current;
283
284    while (graph->derived) {
285        current = graph->derived;
286
287        HASH_DEL(graph->derived, current);
288
289        abac_vertex_t *head = current->key.head;
290        abac_edge_t *tail = current->key.tail;
291        assert(tail->credential == NULL);
292
293        // this can fail, but we assume the data structures are consistent
294        abac_list_remove(head->edges, tail);
295        abac_list_remove(tail->reverse_vertex->edges, tail);
296
297        free(current);
298        _free_edge(tail);
299    }
300}
301
302// add a derived edge, returns 1 if added 0 if dup
303static int _derived_edge(abac_graph_t *graph, abac_vertex_t *head, abac_vertex_t *tail) {
304    abac_edge_t *edge;
305
306    // don't add duplicate edges
307    abac_list_foreach(head->edges, edge,
308        if (edge->vertex == tail)
309            return 0;
310    );
311
312    debug_printf("derived edge %s <- %s\n", head->name, tail->name);
313
314    edge = _get_edge(head, tail, NULL);
315    abac_list_add(head->edges, edge);
316    abac_list_add(tail->reverse_edges, _dup_edge(edge));
317
318    // add to list of derived edges
319    abac_derived_t *derived = abac_xmalloc(sizeof(abac_derived_t));
320    derived->key.head = head;
321    derived->key.tail = edge;
322    HASH_ADD(hh, graph->derived, key, sizeof(abac_derived_key_t), derived);
323
324    return 1;
325}
326
327// find a vertex by name
328abac_vertex_t *_find_vertex(abac_graph_t *graph, char *name) {
329    abac_vertex_t *ret = NULL;
330    HASH_FIND_STR(graph->vertices, name, ret);
331    return ret;
332}
333
334/**
335 * Single iteration of deriving new edges. Returns the number of new edges
336 * added.
337 */
338static int _derive_links_iter(abac_graph_t *graph) {
339    int count = 0;
340    abac_vertex_t *vertex;
341
342    for (vertex = graph->vertices; vertex != NULL; vertex = vertex->hh.next) {
343        // intersection
344        if (abac_role_is_intersection(vertex->role)) {
345            // for each prereq edge:
346            //     find principals that have the edge
347            // find intersection of all sets
348            // for each principal B in intersection:
349            //     add link
350
351            char *name;
352            abac_vertex_t *prereq;
353            abac_set_t *principals = NULL;
354
355            abac_list_foreach(vertex->prereqs, prereq,
356                abac_set_t *cur = _find_principals(graph, prereq);
357
358                if (principals == NULL)
359                    principals = cur;
360                else {
361                    abac_set_intersect(principals, cur);
362                    abac_set_free(cur);
363                }
364
365                if (abac_set_size(principals) == 0)
366                    goto isect_done;
367            );
368
369            abac_list_t *prin_names = abac_set_elements(principals);
370            abac_list_foreach(prin_names, name,
371                abac_vertex_t *principal = _find_vertex(graph, name);
372                count += _derived_edge(graph, vertex, principal);
373            );
374
375            abac_list_free(prin_names);
376isect_done:
377            abac_set_free(principals);
378        }
379
380        // linking role
381        else if (abac_role_is_linking(vertex->role)) {
382            // linking roles take the form A.r1.r2
383            char *A_r1 = abac_role_linked_role(vertex->role);
384            char *r2 = abac_role_role_name(vertex->role);
385
386            // find the linked role in the graph
387            abac_vertex_t *A_r1_vertex;
388            HASH_FIND_STR(graph->vertices, A_r1, A_r1_vertex);
389            if (A_r1_vertex == NULL)
390                continue;
391
392            // find the principals that have A.r1
393            abac_set_t *principals = _find_principals(graph, A_r1_vertex);
394            char *B;
395
396            abac_list_t *elts = abac_set_elements(principals);
397
398            // and add a link for each B.r2 to A.r1.r2
399            abac_list_foreach(elts, B,
400                int B_len = strlen(B);
401                int r2_len = strlen(r2);
402
403                // create the string B.r2, thx C
404                char *B_r2 = malloc(B_len + r2_len + 2);
405                memcpy(B_r2, B, B_len);
406                B_r2[B_len] = '.';
407                memcpy(B_r2 + B_len + 1, r2, r2_len);
408                B_r2[B_len + r2_len + 1] = 0;
409
410                // add an edge if the principal's granted it to someone
411                abac_vertex_t *B_r2_vertex = _find_vertex(graph, B_r2);
412                if (B_r2_vertex) {
413                    debug_printf("adding edge from %s to %s\n", B_r2, abac_role_string(vertex->role));
414                    count += _derived_edge(graph, vertex, B_r2_vertex);
415                }
416
417#ifdef DEBUG
418                debug_printf("    incoming edges for %s\n", abac_role_string(vertex->role));
419                abac_edge_t *cur;
420                abac_list_foreach(vertex->edges, cur,
421                    debug_printf("        %s (%s)\n", abac_role_string(cur->vertex->role), cur->vertex->name);
422                );
423#endif
424
425                free(B_r2);
426            );
427
428            abac_list_free(elts);
429            abac_set_free(principals);
430        }
431    }
432
433    return count;
434}
435
436/**
437 * Derive all implied edges in the graph. These can come from linking roles
438 * and intersections.
439 *
440 * We have to do it iteratively because derived edges can imply new edges.
441 */
442void abac_graph_derive_links(abac_graph_t *graph) {
443    if (!graph->dirty)
444        return;
445
446    // iterate as long as new links are derived
447    while (_derive_links_iter(graph) > 0)
448        ;
449
450    graph->dirty = 0;
451}
452
453static void _reverse_order_recurse(abac_vertex_t *vertex, abac_set_t *seen, int preorder, abac_list_t *stack) {
454    abac_edge_t *outgoing;
455
456    // don't revisit nodes
457    if (!abac_set_add(seen, abac_role_string(vertex->role)))
458        return;
459
460    if (preorder)
461        abac_list_add(stack, vertex);
462
463    // recurse along the incoming vertices
464    abac_list_foreach(vertex->reverse_edges, outgoing,
465        _reverse_order_recurse(outgoing->reverse_vertex, seen, preorder, stack);
466    );
467
468    if (!preorder)
469        abac_list_add(stack, vertex);
470}
471
472static abac_list_t *_reverse_order(abac_graph_t *graph, abac_role_t *start, int preorder) {
473    debug_printf("%sorder at %s\n", preorder ? "pre" : "post", abac_role_string(start));
474
475    abac_vertex_t *start_vertex = _get_vertex(graph, start);
476    abac_set_t *seen = abac_set_new();
477
478    // create the return list
479    abac_list_t *stack = abac_list_new();
480
481    _reverse_order_recurse(start_vertex, seen, preorder, stack);
482
483    abac_set_free(seen);
484
485    return stack;
486}
487
488static void _order_recurse(abac_vertex_t *vertex, abac_set_t *seen, int preorder, abac_list_t *stack) {
489    abac_edge_t *incoming;
490
491    // don't revisit nodes
492    if (!abac_set_add(seen, abac_role_string(vertex->role)))
493        return;
494
495    if (preorder)
496        abac_list_add(stack, vertex);
497
498    // recurse along the incoming vertices
499    abac_list_foreach(vertex->edges, incoming,
500        _order_recurse(incoming->vertex, seen, preorder, stack);
501    );
502
503    if (!preorder)
504        abac_list_add(stack, vertex);
505}
506
507static abac_list_t *_order(abac_graph_t *graph, abac_role_t *start, int preorder) {
508    debug_printf("%sorder at %s\n", preorder ? "pre" : "post", abac_role_string(start));
509
510    abac_vertex_t *start_vertex = _get_vertex(graph, start);
511    abac_set_t *seen = abac_set_new();
512
513    // create the return list
514    abac_list_t *stack = abac_list_new();
515
516    _order_recurse(start_vertex, seen, preorder, stack);
517
518    abac_set_free(seen);
519
520    return stack;
521}
522
523abac_list_t *abac_graph_postorder(abac_graph_t *graph, abac_role_t *start) {
524    return _order(graph, start, 0);
525}
526
527/**
528 * Postorder traverse the graph and return all the credentials within.
529 */
530abac_list_t *abac_graph_postorder_credentials(abac_graph_t *graph, char *start) {
531    abac_vertex_t *vertex;
532    abac_edge_t *incoming;
533
534    // get the postorder of vertices
535    abac_role_t *role = abac_role_from_string(start);
536    abac_list_t *order = abac_graph_postorder(graph, role);
537
538    // go through the list and dup all the credentials
539    abac_list_t *credentials = abac_list_new();
540    abac_list_foreach(order, vertex,
541        abac_list_foreach(vertex->edges, incoming,
542            if (incoming->credential != NULL)
543                abac_list_add(credentials, abac_credential_dup(incoming->credential));
544        );
545    );
546
547    abac_role_free(role);
548    abac_list_free(order);
549
550    return credentials;
551}
552
553
554abac_list_t *abac_graph_postorder_reverse(abac_graph_t *graph, abac_role_t *start) {
555    return _reverse_order(graph, start, 0);
556}
557
558/**
559 * Postorder traverse the graph and return all the credentials within.
560 */
561abac_list_t *abac_graph_postorder_reverse_credentials(abac_graph_t *graph, char *start) {
562    abac_vertex_t *vertex;
563    abac_edge_t *outgoing;
564
565    // get the postorder of vertices
566    abac_role_t *role = abac_role_from_string(start);
567    abac_list_t *order = abac_graph_postorder_reverse(graph, role);
568
569    // go through the list and dup all the credentials
570    abac_list_t *credentials = abac_list_new();
571    abac_list_foreach(order, vertex,
572        abac_list_foreach(vertex->reverse_edges, outgoing,
573            if (outgoing->credential != NULL)
574                abac_list_add(credentials, abac_credential_dup(outgoing->credential));
575        );
576    );
577
578    abac_role_free(role);
579    abac_list_free(order);
580
581    return credentials;
582}
583
584static void _query(abac_graph_t *graph, char *role_name, char *principal, abac_graph_t *return_graph) {
585    abac_vertex_t *vertex;
586    abac_edge_t *incoming;
587
588    abac_role_t *role = abac_role_from_string(role_name);
589    abac_role_t *prin_role = abac_role_from_string(principal);
590
591    // give up on bogus roles
592    if (role == NULL || prin_role == NULL) {
593        free(role);
594        free(prin_role);
595        return;
596    }
597
598    abac_set_t *on_path = abac_set_new();
599    abac_set_add(on_path, abac_role_string(prin_role));
600
601    abac_list_t *traversal = abac_graph_postorder(graph, role);
602    abac_list_foreach(traversal, vertex,
603        abac_role_t *role = vertex->role;
604
605        abac_list_foreach(vertex->edges, incoming,
606            abac_role_t *incoming_role = incoming->vertex->role;
607
608            if (!abac_set_contains(on_path, abac_role_string(incoming_role)))
609                continue;
610
611            abac_set_add(on_path, abac_role_string(role));
612
613            // get implying edges for intersection vertices
614            if (abac_role_is_intersection(role)) {
615                abac_vertex_t *prereq;
616                abac_list_foreach(vertex->prereqs, prereq,
617                    _query(graph, prereq->name, principal, return_graph);
618                );
619            }
620
621            // recursively find linked roles
622            else if (abac_role_is_linking(role)) {
623                char *linked_role = abac_role_linked_role(role);
624                char *principal = abac_role_principal(incoming_role);
625
626                _query(graph, linked_role, principal, return_graph);
627            }
628
629            // add non-derived edges to the proof graph
630            else
631                abac_graph_add_credential(return_graph, incoming->credential);
632        );
633    );
634
635    abac_list_free(traversal);
636    abac_set_free(on_path);
637    abac_role_free(role);
638    abac_role_free(prin_role);
639}
640
641abac_graph_t *abac_graph_query(abac_graph_t *graph, char *role, char *principal) {
642    abac_graph_derive_links(graph);
643
644    abac_graph_t *return_graph = abac_graph_new();
645    _query(graph, role, principal, return_graph);
646    abac_graph_derive_links(return_graph);
647    return return_graph;
648}
649
650abac_graph_t *abac_graph_principal_creds(abac_graph_t *graph, char *principal) {
651    abac_graph_derive_links(graph);
652    abac_graph_t *result_graph = abac_graph_new();
653    abac_list_t *result = abac_graph_postorder_reverse_credentials(graph, 
654            principal);
655    abac_credential_t *cur = NULL;
656    abac_list_foreach(result, cur,
657        abac_graph_add_credential(result_graph, cur);
658    );
659    abac_list_free(result);
660    /* For each terminal role that the principal can reach, roll a proof into
661       the result_graph. */
662    abac_vertex_t *vertex = NULL;
663    for (vertex = result_graph->vertices; vertex != NULL; 
664            vertex = vertex->hh.next) {
665        if ( abac_list_size(vertex->reverse_edges) == 0) 
666            _query(graph, vertex->name, principal, result_graph);
667    }
668    abac_graph_derive_links(result_graph);
669    return result_graph;
670}
671
672
673/**
674 * Get all the credentials (attribute/issuer cert pairs) from the graph.
675 */
676abac_list_t *abac_graph_credentials(abac_graph_t *graph) {
677    abac_list_t *credentials = abac_list_new();
678
679    abac_vertex_t *vertex;
680
681    for (vertex = graph->vertices; vertex != NULL; vertex = vertex->hh.next) {
682        abac_edge_t *edge;
683        abac_list_foreach(vertex->edges, edge,
684            if (edge->credential != NULL)
685                abac_list_add(credentials, abac_credential_dup(edge->credential));
686        );
687    }
688
689    return credentials;
690}
691
692void abac_graph_free(abac_graph_t *graph) {
693    abac_vertex_t *vertex;
694    abac_edge_t *edge;
695
696    // kill derived edges
697    _clear_derived(graph);
698
699    // delete vertices
700    while ((vertex = graph->vertices) != NULL) {
701        HASH_DEL(graph->vertices, vertex);
702        _free_vertex(vertex);
703    }
704
705    free(graph);
706}
707
708abac_role_t *abac_vertex_role(abac_vertex_t *vertex) {
709    return vertex->role;
710}
Note: See TracBrowser for help on using the repository browser.