source: libabac/abac_graph.c @ 3f21704

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

1) cleanup alittle X

  • Property mode set to 100644
File size: 19.9 KB
Line 
1
2/* abac_graph.c */
3
4#include <assert.h>
5#include <stdlib.h>
6
7#include "abac_graph.h"
8
9#include "abac_set.h"
10#include "abac_util.h"
11
12#include "uthash.h"
13
14// vertex
15struct _abac_vertex_t {
16    abac_role_t *role;
17    char *name;
18    int refcount;
19
20    abac_list_t *edges;
21    abac_list_t *reverse_edges;
22
23    // only relevant to intersection edges
24    abac_list_t *prereqs;
25
26    UT_hash_handle hh;
27};
28
29// edge
30typedef struct _abac_edge_t {
31    int refcount;
32    abac_vertex_t *vertex;
33    abac_vertex_t *reverse_vertex;
34    abac_credential_t *credential;
35} abac_edge_t;
36
37// derived edge
38typedef struct _abac_derived_key_t {
39    abac_vertex_t *head;
40    abac_edge_t *tail;
41} abac_derived_key_t;
42
43typedef struct _abac_derived_t {
44    abac_derived_key_t key;
45    UT_hash_handle hh;
46} abac_derived_t;
47
48// graph
49struct _abac_graph_t {
50    abac_vertex_t *vertices;
51    abac_derived_t *derived;
52    int dirty;
53};
54
55// ugghhhghhhghh need this for intersections
56abac_list_t *abac_role_prereqs(abac_role_t *);
57
58static abac_vertex_t *_dup_vertex(abac_vertex_t *v);
59int abac_graph_add_credential(abac_graph_t *graph, abac_credential_t *cred);
60
61/**
62 * Create a new graph.
63 */
64abac_graph_t *abac_graph_new(void) {
65    abac_graph_t *graph = abac_xmalloc(sizeof(abac_graph_t));
66
67    graph->vertices = NULL;
68    graph->derived = NULL;
69    graph->dirty = 0;
70
71    return graph;
72}
73
74/**
75 * Deep copy a graph.
76 */
77abac_graph_t *abac_graph_dup(abac_graph_t *graph) {
78    abac_vertex_t *vertex;
79    abac_edge_t *edge;
80
81    abac_graph_t *clone = abac_graph_new();
82
83    // copy the vertices edge by edge
84    for (vertex = graph->vertices; vertex != NULL; vertex = vertex->hh.next)
85        abac_list_foreach(vertex->edges, edge,
86            // only copy non-derived edges
87            if (edge->credential != NULL)
88                abac_graph_add_credential(clone, edge->credential);
89        );
90
91    return clone;
92}
93/**
94 * Add a vertex to the graph. Should only be called by
95 * abac_graph_add_credential. This returns an existing vertex
96 * or a new vertex with a refcount of 1.  Either way it gets and
97 * references the vertex.
98 */
99static abac_vertex_t *_get_vertex(abac_graph_t *graph, abac_role_t *role) {
100    abac_vertex_t *vertex;
101    char *string;
102   
103    string =abac_role_string(role);
104    HASH_FIND_STR(graph->vertices, string, vertex);
105
106    // add the vertex if it doesn't exist
107    if (vertex == NULL) {
108        vertex = abac_xmalloc(sizeof(abac_vertex_t));
109        vertex->refcount = 1;
110        vertex->role = abac_role_dup(role);
111        vertex->name = abac_role_string(vertex->role);
112
113        // create the list of edges
114        vertex->edges = abac_list_new();
115        vertex->reverse_edges = abac_list_new();
116
117        // for intersections, always NULL on normal vertices
118        if (abac_role_is_intersection(role)) {
119            abac_role_t *prereq;
120            vertex->prereqs = abac_list_new();
121
122            // add each prereq to the vertex (dup'ed)
123            abac_list_foreach(abac_role_prereqs(role), prereq,
124                abac_vertex_t *tail_vertex = _get_vertex(graph, prereq);
125                abac_list_add(vertex->prereqs, _dup_vertex(tail_vertex));
126            );
127        }
128
129        // normal edges have no prereqs
130        else
131            vertex->prereqs = NULL;
132
133        // add it to the vertices
134        HASH_ADD_KEYPTR(hh, graph->vertices, vertex->name, strlen(vertex->name), vertex);
135
136    } 
137
138    return vertex;
139}
140
141/* forward decl */
142static void _free_edge(abac_edge_t *edge);
143
144/*
145 * Reduce the vertex reference count and free it if this is the last reference
146 */
147static void _free_vertex(abac_vertex_t *vertex) {
148    abac_edge_t *edge=NULL;
149    abac_vertex_t *pre=NULL;
150
151    --vertex->refcount;
152
153    if ( vertex->refcount > 0) return;
154
155    abac_role_free(vertex->role);
156
157    abac_list_foreach(vertex->edges, edge,
158        _free_edge(edge);
159    );
160    abac_list_free(vertex->edges);
161
162    abac_list_foreach(vertex->reverse_edges, edge,
163        _free_edge(edge);
164    );
165    abac_list_free(vertex->reverse_edges);
166
167    // Free the prereqs
168    if (vertex->prereqs != NULL) {
169        abac_list_foreach(vertex->prereqs, pre,
170            if (pre != NULL) {
171                _free_vertex(pre);
172            }
173        );
174        abac_list_free(vertex->prereqs);
175    }
176
177    free(vertex);
178}
179
180/*
181 * Increment vertex reference count
182 */
183static abac_vertex_t *_dup_vertex(abac_vertex_t *v) {
184    v->refcount++;
185    return v;
186}
187
188
189/*
190 * create a new edge from the given head, tail and credential
191 */
192
193static abac_edge_t *_get_edge(abac_vertex_t *h, abac_vertex_t *t,
194        abac_credential_t *c) {
195
196    /* An edge does not own it's vertices.  Do not delete them from an edge
197     * reference. */
198    abac_edge_t *edge = abac_xmalloc(sizeof(abac_edge_t));
199    edge->refcount = 1;
200    edge->vertex = t;
201    edge->reverse_vertex = h;
202    /* Don't dup a null credential */
203    edge->credential = (c) ? abac_credential_dup(c): NULL;
204
205    return edge;
206}
207
208
209/**
210 * Increment the reference count
211 */
212static abac_edge_t *_dup_edge(abac_edge_t *e) {
213    e->refcount++;
214    return e;
215}
216
217/**
218 * Decerement the refcount and free it if this was the last reference.  NB
219 * edges do not own teh vertices, so they must be deleted elsewhere.
220 */
221static void _free_edge(abac_edge_t *edge) {
222    assert(edge && edge->refcount > 0);
223    if ( --edge->refcount > 0) return;
224    if (edge->credential) abac_credential_free(edge->credential);
225    free(edge);
226}
227
228/**
229 * Add a credential to the credential graph.
230 */
231int abac_graph_add_credential(abac_graph_t *graph, abac_credential_t *cred) {
232    abac_vertex_t *head_vertex, *tail_vertex;
233    abac_edge_t *edge;
234
235    assert(cred != NULL);
236
237    abac_role_t *head = abac_credential_head(cred);
238    abac_role_t *tail = abac_credential_tail(cred);
239
240    // a valid credential must have a role for the head
241    if (!abac_role_is_role(head)) return 0;
242
243    head_vertex = _get_vertex(graph, head);
244    tail_vertex = _get_vertex(graph, tail);
245
246    // make sure we don't insert the same edge twice (ugh)
247    abac_list_foreach(head_vertex->edges, edge,
248        if (edge->vertex == tail_vertex) {
249            return 0;
250        }
251    );
252
253    // create the edge and add it
254    edge = _get_edge(head_vertex, tail_vertex, cred);
255
256    abac_list_add(head_vertex->edges, edge);
257    abac_list_add(tail_vertex->reverse_edges, _dup_edge(edge));
258
259    // must re-derive edges
260    graph->dirty = 1;
261
262    return 1;
263}
264
265// find the principals that have a role
266static abac_set_t *_find_principals(abac_graph_t *graph, abac_vertex_t *start_vertex) {
267    abac_set_t *principals = abac_set_new();
268
269    abac_list_t *traversal = abac_graph_postorder(graph, start_vertex->role);
270    abac_vertex_t *vertex;
271
272    abac_list_foreach(traversal, vertex,
273        if (abac_role_is_principal(vertex->role))
274            abac_set_add(principals, abac_role_string(vertex->role));
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_edge(tail);
299        free(current);
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
465    // recurse along the incoming vertices
466    abac_list_foreach(vertex->reverse_edges, outgoing,
467        _reverse_order_recurse(outgoing->reverse_vertex, seen, preorder, stack);
468    );
469
470    if (!preorder) {
471        abac_list_add(stack, vertex);
472    }
473}
474
475static abac_list_t *_reverse_order(abac_graph_t *graph, abac_role_t *start, int preorder) {
476    debug_printf("%sorder at %s\n", preorder ? "pre" : "post", abac_role_string(start));
477
478
479    abac_vertex_t *start_vertex = _get_vertex(graph, start);
480
481    abac_set_t *seen = abac_set_new();
482
483    // create the return list
484    abac_list_t *stack = abac_list_new();
485
486    _reverse_order_recurse(start_vertex, seen, preorder, stack);
487
488    abac_set_free(seen);
489
490
491    return stack;
492}
493
494static void _order_recurse(abac_vertex_t *vertex, abac_set_t *seen, int preorder, abac_list_t *stack) {
495    abac_edge_t *incoming;
496
497    // don't revisit nodes
498    if (!abac_set_add(seen, abac_role_string(vertex->role)))
499        return;
500
501    if (preorder) {
502        abac_list_add(stack, vertex);
503    }
504
505    // recurse along the incoming vertices
506    abac_list_foreach(vertex->edges, incoming,
507        _order_recurse(incoming->vertex, seen, preorder, stack);
508    );
509
510    if (!preorder) {
511        abac_list_add(stack, vertex);
512    }
513}
514
515static abac_list_t *_order(abac_graph_t *graph, abac_role_t *start, int preorder) {
516    debug_printf("%sorder at %s\n", preorder ? "pre" : "post", abac_role_string(start));
517
518    abac_vertex_t *start_vertex = _get_vertex(graph, start);
519
520    abac_set_t *seen = abac_set_new();
521
522    // create the return list
523    abac_list_t *stack = abac_list_new();
524
525    _order_recurse(start_vertex, seen, preorder, stack);
526
527    abac_set_free(seen);
528
529    return stack;
530}
531
532abac_list_t *abac_graph_postorder(abac_graph_t *graph, abac_role_t *start) {
533    return _order(graph, start, 0);
534}
535
536/**
537 * Postorder traverse the graph and return all the credentials within.
538 */
539abac_list_t *abac_graph_postorder_credentials(abac_graph_t *graph, char *start) {
540    abac_vertex_t *vertex;
541    abac_edge_t *incoming;
542
543    // get the postorder of vertices
544    abac_role_t *role = abac_role_from_string(start);
545    abac_list_t *order = abac_graph_postorder(graph, role);
546
547    // go through the list and dup all the credentials
548    abac_list_t *credentials = abac_list_new();
549    abac_list_foreach(order, vertex,
550        abac_list_foreach(vertex->edges, incoming,
551            if (incoming->credential != NULL) {
552                abac_list_add(credentials, abac_credential_dup(incoming->credential));
553            }
554        );
555    );
556
557    abac_role_free(role);
558    abac_list_free(order);
559
560    return credentials;
561}
562
563
564abac_list_t *abac_graph_postorder_reverse(abac_graph_t *graph, abac_role_t *start) {
565    return _reverse_order(graph, start, 0);
566}
567
568/**
569 * Postorder traverse the graph and return all the credentials within.
570 */
571abac_list_t *abac_graph_postorder_reverse_credentials(abac_graph_t *graph, char *start) {
572    abac_vertex_t *vertex;
573    abac_edge_t *outgoing;
574
575    // get the postorder of vertices
576    abac_role_t *role = abac_role_from_string(start);
577    abac_list_t *order = abac_graph_postorder_reverse(graph, role);
578
579    // go through the list and dup all the credentials
580    abac_list_t *credentials = abac_list_new();
581
582    abac_list_foreach(order, vertex,
583        abac_list_foreach(vertex->reverse_edges, outgoing,
584            if (outgoing->credential != NULL) {
585                abac_list_add(credentials, abac_credential_dup(outgoing->credential));
586            }
587        );
588    );
589
590    abac_role_free(role);
591    abac_list_free(order);
592
593    return credentials;
594}
595
596static void _query(abac_graph_t *graph, char *role_name, char *principal, abac_graph_t *return_graph) {
597    abac_vertex_t *vertex;
598    abac_edge_t *incoming;
599    abac_role_t *role = abac_role_from_string(role_name);
600    abac_role_t *prin_role = abac_role_from_string(principal);
601
602    // give up on bogus roles
603    if (role == NULL || prin_role == NULL) {
604        abac_role_free(role);
605        abac_role_free(prin_role);
606        return;
607    }
608
609    abac_set_t *on_path = abac_set_new();
610    abac_set_add(on_path, abac_role_string(prin_role));
611
612    abac_list_t *traversal = abac_graph_postorder(graph, role);
613    abac_list_foreach(traversal, vertex,
614        abac_role_t *role = vertex->role;
615
616        abac_list_foreach(vertex->edges, incoming,
617            abac_role_t *incoming_role = incoming->vertex->role;
618
619            if (!abac_set_contains(on_path, abac_role_string(incoming_role)))
620                continue;
621
622            abac_set_add(on_path, abac_role_string(role));
623
624            // get implying edges for intersection vertices
625            if (abac_role_is_intersection(role)) {
626                abac_vertex_t *prereq;
627                abac_list_foreach(vertex->prereqs, prereq,
628                    _query(graph, prereq->name, principal, return_graph);
629                );
630            }
631
632            // recursively find linked roles
633            else if (abac_role_is_linking(role)) {
634                char *linked_role = abac_role_linked_role(role);
635                char *principal = abac_role_principal(incoming_role);
636
637                _query(graph, linked_role, principal, return_graph);
638            }
639
640            // add non-derived edges to the proof graph
641            else
642                abac_graph_add_credential(return_graph, incoming->credential);
643        );
644    );
645
646    abac_list_free(traversal);
647    abac_set_free(on_path);
648    abac_role_free(role);
649    abac_role_free(prin_role);
650}
651
652abac_graph_t *abac_graph_query(abac_graph_t *graph, char *role, char *principal) {
653    abac_graph_derive_links(graph);
654
655    abac_graph_t *return_graph = abac_graph_new();
656    _query(graph, role, principal, return_graph);
657    abac_graph_derive_links(return_graph);
658    return return_graph;
659}
660
661abac_graph_t *abac_graph_principal_creds(abac_graph_t *graph, char *principal) {
662    abac_graph_derive_links(graph);
663    abac_graph_t *result_graph = abac_graph_new();
664
665    abac_list_t *result = abac_graph_postorder_reverse_credentials(graph, 
666            principal);
667
668    abac_credential_t *cur = NULL;
669    int add_ret;
670    abac_list_foreach(result, cur,
671        add_ret=abac_graph_add_credential(result_graph, cur);
672        assert(add_ret != ABAC_GRAPH_CRED_INVALID);
673        abac_credential_free(cur);
674    );
675    abac_list_free(result);
676    /* For each terminal role that the principal can reach, roll a proof into
677       the result_graph. */
678
679    abac_vertex_t *vertex = NULL;
680    for (vertex = result_graph->vertices; vertex != NULL; 
681            vertex = vertex->hh.next) {
682        if ( abac_list_size(vertex->reverse_edges) == 0) 
683            _query(graph, vertex->name, principal, result_graph);
684    }
685    abac_graph_derive_links(result_graph);
686
687    return result_graph;
688}
689
690
691/**
692 * Get all the credentials (attribute/issuer cert pairs) from the graph.
693 */
694abac_list_t *abac_graph_credentials(abac_graph_t *graph) {
695    abac_list_t *credentials = abac_list_new();
696
697    abac_vertex_t *vertex;
698
699    for (vertex = graph->vertices; vertex != NULL; vertex = vertex->hh.next) {
700        abac_edge_t *edge;
701        abac_list_foreach(vertex->edges, edge,
702            if (edge->credential != NULL)
703                abac_list_add(credentials, abac_credential_dup(edge->credential));
704        );
705    }
706
707    return credentials;
708}
709
710void abac_graph_free(abac_graph_t *graph) {
711    abac_vertex_t *vertex;
712    abac_edge_t *edge;
713
714    // kill derived edges
715    _clear_derived(graph);
716
717    // delete vertices
718    while ((vertex = graph->vertices) != NULL) {
719        HASH_DEL(graph->vertices, vertex);
720        _free_vertex(vertex);
721    }
722
723    free(graph);
724}
725
726abac_role_t *abac_vertex_role(abac_vertex_t *vertex) {
727    return vertex->role;
728}
Note: See TracBrowser for help on using the repository browser.