source: libabac/abac_graph.c @ ebe824c

abac0-leakabac0-meicompt_changesgec13mei-idmei-rt0-nmei_rt0mei_rt2mei_rt2_fix_1meiyap-rt1meiyap1rt2tvf-new-xml
Last change on this file since ebe824c was ebe824c, checked in by Mike Ryan <mikeryan@…>, 14 years ago

get implying edges for an intersection

  • Property mode set to 100644
File size: 15.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
11// vertex
12struct _abac_vertex_t {
13    abac_role_t *role;
14    char *name;
15
16    abac_list_t *edges;
17
18    // only relevant to intersection edges
19    abac_list_t *prereqs;
20
21    UT_hash_handle hh;
22};
23
24// edge
25typedef struct _abac_edge_t {
26    abac_vertex_t *vertex;
27    abac_credential_t *credential;
28} abac_edge_t;
29
30// derived edge
31typedef struct _abac_derived_key_t {
32    abac_vertex_t *head;
33    abac_edge_t *tail;
34} abac_derived_key_t;
35
36typedef struct _abac_derived_t {
37    abac_derived_key_t key;
38    UT_hash_handle hh;
39} abac_derived_t;
40
41// graph
42struct _abac_graph_t {
43    abac_vertex_t *vertices;
44    abac_derived_t *derived;
45    int dirty;
46};
47
48// ugghhhghhhghh need this for intersections
49abac_list_t *abac_credential_prereqs(abac_credential_t *);
50
51/**
52 * True iff a vertex is linking.
53 */
54static inline int _vertex_is_intersection(abac_vertex_t *vertex) {
55    return vertex->role == NULL;
56}
57
58/**
59 * Create a new graph.
60 */
61abac_graph_t *abac_graph_new(void) {
62    abac_graph_t *graph = abac_xmalloc(sizeof(abac_graph_t));
63
64    graph->vertices = NULL;
65    graph->derived = NULL;
66    graph->dirty = 0;
67
68    return graph;
69}
70
71/**
72 * Deep copy a graph.
73 */
74abac_graph_t *abac_graph_dup(abac_graph_t *graph) {
75    abac_vertex_t *vertex;
76    abac_edge_t *edge;
77
78    abac_graph_t *clone = abac_graph_new();
79
80    // copy the vertices edge by edge
81    for (vertex = graph->vertices; vertex != NULL; vertex = vertex->hh.next)
82        abac_list_foreach(vertex->edges, edge,
83            // only copy non-derived edges
84            if (edge->credential != NULL)
85                abac_graph_add_credential(clone, edge->credential);
86        );
87
88    return clone;
89}
90
91/**
92 * Add a vertex to the graph. Should only be called by abac_graph_add_credential.
93 */
94static abac_vertex_t *_get_vertex(abac_graph_t *graph, abac_role_t *role) {
95    abac_vertex_t *vertex;
96    char *string;
97   
98    string = abac_role_string(role);
99    HASH_FIND_STR(graph->vertices, string, vertex);
100
101    // add the vertex if it doesn't exist
102    if (vertex == NULL) {
103        vertex = abac_xmalloc(sizeof(abac_vertex_t));
104        vertex->role = abac_role_dup(role);
105        vertex->name = abac_role_string(vertex->role);
106
107        // create the list of edges
108        vertex->edges = abac_list_new();
109
110        // for intersections, always NULL on normal vertices
111        vertex->prereqs = NULL;
112
113        // add it to the vertices
114        HASH_ADD_KEYPTR(hh, graph->vertices, vertex->name, strlen(vertex->name), vertex);
115    }
116
117    return vertex;
118}
119
120/**
121 * convert a list of prereqs to a string suitable for use as a hash key
122 * format: role & role & ... & role
123 */
124static char *_prereq_key(abac_list_t *prereqs) {
125    abac_role_t *role;
126    char *string;
127    int i = 0, size;
128    size_t len = 0;
129
130    // find the required size
131    abac_list_foreach(prereqs, role,
132        len += strlen(abac_role_string(role)) + 3;
133    );
134
135    string = abac_xmalloc(len);
136    string[0] = '\0';
137
138    size = abac_list_size(prereqs);
139
140    // concat the names
141    abac_list_foreach(prereqs, role,
142        strcat(string, abac_role_string(role));
143        if (i++ < size - 1)
144            strcat(string, " & ");
145    );
146
147    return string;
148}
149
150/**
151 * Find/create intersection vertex. Only called by abac_graph_add_credential.
152 */
153static abac_vertex_t *_get_intersection_vertex(abac_graph_t *graph, abac_credential_t *cred) {
154    abac_role_t *role, *tail_role;
155    abac_vertex_t *vertex;
156
157    abac_list_t *prereqs = abac_credential_prereqs(cred);
158    char *string = _prereq_key(prereqs);
159    HASH_FIND_STR(graph->vertices, string, vertex);
160
161    // add the vertex if it doesn't exist
162    if (vertex == NULL) {
163        vertex = abac_xmalloc(sizeof(abac_vertex_t));
164        vertex->role = NULL;
165        vertex->name = string;
166
167        // create the list of edges
168        vertex->edges = abac_list_new();
169
170        // for intersections, will be populated first time it's created
171        vertex->prereqs = abac_list_new();
172
173        // add each prereq to the vertex
174        abac_list_foreach(prereqs, tail_role,
175            abac_vertex_t *tail_vertex = _get_vertex(graph, tail_role);
176            abac_list_add(vertex->prereqs, tail_vertex);
177        );
178
179        // add it to the vertices
180        HASH_ADD_KEYPTR(hh, graph->vertices, vertex->name, strlen(vertex->name), vertex);
181    }
182    else
183        free(string); // already exists, get rid of useless memory
184
185    return vertex;
186
187}
188
189/**
190 * Add a credential to the credential graph.
191 */
192int abac_graph_add_credential(abac_graph_t *graph, abac_credential_t *cred) {
193    abac_vertex_t *head_vertex, *tail_vertex;
194    abac_edge_t *edge;
195
196    assert(cred != NULL);
197
198    abac_role_t *head = abac_credential_head(cred);
199    abac_role_t *tail = abac_credential_tail(cred);
200
201    // a valid credential must have a role for the head
202    if (!abac_role_is_role(head)) return 0;
203
204    head_vertex = _get_vertex(graph, head);
205
206    // tail is a normal role
207    if (tail != NULL)
208        tail_vertex = _get_vertex(graph, tail);
209
210    // intersection
211    else
212        tail_vertex = _get_intersection_vertex(graph, cred);
213
214    // make sure we don't insert the same edge twice (ugh)
215    abac_list_foreach(head_vertex->edges, edge,
216        if (edge->vertex == tail_vertex)
217            return 0;
218    );
219
220    // create the edge and add it
221    edge = abac_xmalloc(sizeof(abac_edge_t));
222    edge->vertex = tail_vertex;
223    edge->credential = abac_credential_dup(cred);
224
225    abac_list_add(head_vertex->edges, edge);
226
227    // must re-derive edges
228    graph->dirty = 1;
229
230    return 1;
231}
232
233// find the principals that have a role
234static abac_set_t *_find_principals(abac_graph_t *graph, abac_vertex_t *start_vertex) {
235    abac_set_t *principals = abac_set_new();
236
237    abac_list_t *traversal = abac_graph_postorder(graph, start_vertex->role);
238    abac_vertex_t *vertex;
239
240    abac_list_foreach(traversal, vertex,
241        if (vertex->role != NULL && abac_role_is_principal(vertex->role))
242            abac_set_add(principals, vertex->name);
243    );
244
245    abac_list_free(traversal);
246    return principals;
247}
248
249// remove any derived edges from the graph
250void _clear_derived(abac_graph_t *graph) {
251    abac_derived_t *current;
252
253    while (graph->derived) {
254        current = graph->derived;
255
256        HASH_DEL(graph->derived, current);
257
258        abac_vertex_t *head = current->key.head;
259        abac_edge_t *tail = current->key.tail;
260        assert(tail->credential == NULL);
261
262        // this can fail, but we assume the data structures are consistent
263        abac_list_remove(head->edges, tail);
264
265        free(current);
266        free(tail);
267    }
268}
269
270// add a derived edge
271static void _derived_edge(abac_graph_t *graph, abac_vertex_t *head, abac_vertex_t *tail) {
272    abac_edge_t *edge = abac_xmalloc(sizeof(abac_edge_t));
273    edge->vertex = tail;
274    edge->credential = NULL;
275    abac_list_add(head->edges, edge);
276
277    // add to list of derived edges
278    abac_derived_t *derived = abac_xmalloc(sizeof(abac_derived_t));
279    derived->key.head = head;
280    derived->key.tail = edge;
281    HASH_ADD(hh, graph->derived, key, sizeof(abac_derived_key_t), derived);
282}
283
284// find a vertex by name
285abac_vertex_t *_find_vertex(abac_graph_t *graph, char *name) {
286    abac_vertex_t *ret = NULL;
287    HASH_FIND_STR(graph->vertices, name, ret);
288    return ret;
289}
290
291void abac_graph_derive_links(abac_graph_t *graph) {
292    abac_vertex_t *vertex;
293
294    if (!graph->dirty)
295        return;
296
297    for (vertex = graph->vertices; vertex != NULL; vertex = vertex->hh.next) {
298        // intersection
299        if (_vertex_is_intersection(vertex)) {
300            // for each prereq edge:
301            //     find principals that have the edge
302            // find intersection of all sets
303            // for each principal B in intersection:
304            //     add link
305
306            char *name;
307            abac_vertex_t *prereq;
308            abac_set_t *principals = NULL;
309
310            abac_list_foreach(vertex->prereqs, prereq,
311                abac_set_t *cur = _find_principals(graph, prereq);
312
313                if (principals == NULL)
314                    principals = cur;
315                else {
316                    abac_set_intersect(principals, cur);
317                    abac_set_free(cur);
318                }
319
320                if (abac_set_size(principals) == 0)
321                    goto isect_done;
322            );
323
324            abac_list_t *prin_names = abac_set_elements(principals);
325            abac_list_foreach(prin_names, name,
326                abac_vertex_t *principal = _find_vertex(graph, name);
327                _derived_edge(graph, vertex, principal);
328
329                printf("adding edge from %s to %s\n", principal->name, vertex->name);
330            );
331
332            abac_list_free(prin_names);
333isect_done:
334            abac_set_free(principals);
335        }
336
337        // linking role
338        else if (abac_role_is_linking(vertex->role)) {
339            // linking roles take the form A.r1.r2
340            char *A_r1 = abac_role_linked_role(vertex->role);
341            char *r2 = abac_role_role_name(vertex->role);
342
343            // find the linked role in the graph
344            abac_vertex_t *A_r1_vertex;
345            HASH_FIND_STR(graph->vertices, A_r1, A_r1_vertex);
346            if (A_r1_vertex == NULL)
347                continue;
348
349            // find the principals that have A.r1
350            abac_set_t *principals = _find_principals(graph, A_r1_vertex);
351            char *B;
352
353            abac_list_t *elts = abac_set_elements(principals);
354
355            // and add a link for each B.r2 to A.r1.r2
356            abac_list_foreach(elts, B,
357                int B_len = strlen(B);
358                int r2_len = strlen(r2);
359
360                // create the string B.r2, thx C
361                char *B_r2 = malloc(B_len + r2_len + 2);
362                memcpy(B_r2, B, B_len);
363                B_r2[B_len] = '.';
364                memcpy(B_r2 + B_len + 1, r2, r2_len);
365                B_r2[B_len + r2_len + 1] = 0;
366
367                // add an edge if the principal's granted it to someone
368                abac_vertex_t *B_r2_vertex = _find_vertex(graph, B_r2);
369                if (B_r2_vertex) {
370                    debug_printf("adding edge from %s to %s\n", B_r2, abac_role_string(vertex->role));
371                    _derived_edge(graph, vertex, B_r2_vertex);
372                }
373
374#ifdef DEBUG
375                debug_printf("    incoming edges for %s\n", abac_role_string(vertex->role));
376                abac_edge_t *cur;
377                abac_list_foreach(vertex->edges, cur,
378                    debug_printf("        %s (%s)\n", abac_role_string(cur->vertex->role), cur->vertex->name);
379                );
380#endif
381
382                free(B_r2);
383            );
384
385            abac_list_free(elts);
386            abac_set_free(principals);
387        }
388    }
389
390    graph->dirty = 0;
391}
392
393static void _order_recurse(abac_vertex_t *vertex, abac_set_t *seen, int preorder, abac_list_t *stack) {
394    abac_edge_t *incoming;
395
396    // don't revisit nodes
397    if (!abac_set_add(seen, vertex->name))
398        return;
399
400    if (preorder)
401        abac_list_add(stack, vertex);
402
403    // recurse along the incoming vertices
404    abac_list_foreach(vertex->edges, incoming,
405        _order_recurse(incoming->vertex, seen, preorder, stack);
406    );
407
408    if (!preorder)
409        abac_list_add(stack, vertex);
410}
411
412static abac_list_t *_order(abac_graph_t *graph, abac_role_t *start, int preorder) {
413    debug_printf("%sorder at %s\n", preorder ? "pre" : "post", abac_role_string(start));
414
415    abac_vertex_t *start_vertex = _get_vertex(graph, start);
416    abac_set_t *seen = abac_set_new();
417
418    // create the return list
419    abac_list_t *stack = abac_list_new();
420
421    _order_recurse(start_vertex, seen, preorder, stack);
422
423    abac_set_free(seen);
424
425    return stack;
426}
427
428abac_list_t *abac_graph_postorder(abac_graph_t *graph, abac_role_t *start) {
429    return _order(graph, start, 0);
430}
431
432/**
433 * Postorder traverse the graph and return all the credentials within.
434 */
435abac_list_t *abac_graph_postorder_credentials(abac_graph_t *graph, char *start) {
436    abac_vertex_t *vertex;
437    abac_edge_t *incoming;
438
439    // get the postorder of vertices
440    abac_role_t *role = abac_role_from_string(start);
441    abac_list_t *order = abac_graph_postorder(graph, role);
442
443    // go through the list and dup all the credentials
444    abac_list_t *credentials = abac_list_new();
445    abac_list_foreach(order, vertex,
446        abac_list_foreach(vertex->edges, incoming,
447            if (incoming->credential != NULL)
448                abac_list_add(credentials, abac_credential_dup(incoming->credential));
449        );
450    );
451
452    abac_role_free(role);
453    abac_list_free(order);
454
455    return credentials;
456}
457
458static void _query(abac_graph_t *graph, char *role_name, char *principal, abac_graph_t *return_graph) {
459    abac_vertex_t *vertex;
460    abac_edge_t *incoming;
461
462    abac_role_t *role = abac_role_from_string(role_name);
463    abac_role_t *prin_role = abac_role_from_string(principal);
464
465    // give up on bogus roles
466    if (role == NULL || prin_role == NULL) {
467        free(role);
468        free(prin_role);
469        return;
470    }
471
472    abac_set_t *on_path = abac_set_new();
473    abac_set_add(on_path, abac_role_string(prin_role));
474
475    abac_list_t *traversal = abac_graph_postorder(graph, role);
476    abac_list_foreach(traversal, vertex,
477        abac_role_t *role = vertex->role;
478        char *vertex_name = vertex->name;
479
480        abac_list_foreach(vertex->edges, incoming,
481            abac_role_t *incoming_role = incoming->vertex->role;
482            char *incoming_name = incoming->vertex->name;
483
484            if (!abac_set_contains(on_path, incoming_name))
485                continue;
486
487            abac_set_add(on_path, vertex_name);
488
489            // get implying edges for intersection vertices
490            if (_vertex_is_intersection(vertex)) {
491                abac_vertex_t *prereq;
492                abac_list_foreach(vertex->prereqs, prereq,
493                    _query(graph, prereq->name, principal, return_graph);
494                );
495            }
496
497            // recursively find linked roles
498            else if (abac_role_is_linking(role)) {
499                char *linked_role = abac_role_linked_role(role);
500                char *principal = abac_role_principal(incoming_role);
501
502                _query(graph, linked_role, principal, return_graph);
503            }
504
505            // add non-derived edges to the proof graph
506            else
507                abac_graph_add_credential(return_graph, incoming->credential);
508        );
509    );
510
511    abac_list_free(traversal);
512    abac_set_free(on_path);
513    abac_role_free(role);
514    abac_role_free(prin_role);
515}
516
517abac_graph_t *abac_graph_query(abac_graph_t *graph, char *role, char *principal) {
518    abac_graph_derive_links(graph);
519
520    abac_graph_t *return_graph = abac_graph_new();
521    _query(graph, role, principal, return_graph);
522    abac_graph_derive_links(return_graph);
523    return return_graph;
524}
525
526/**
527 * Get all the credentials (attribute/issuer cert pairs) from the graph.
528 */
529abac_list_t *abac_graph_credentials(abac_graph_t *graph) {
530    abac_list_t *credentials = abac_list_new();
531
532    abac_vertex_t *vertex;
533
534    for (vertex = graph->vertices; vertex != NULL; vertex = vertex->hh.next) {
535        abac_edge_t *edge;
536        abac_list_foreach(vertex->edges, edge,
537            if (edge->credential != NULL)
538                abac_list_add(credentials, abac_credential_dup(edge->credential));
539        );
540    }
541
542    return credentials;
543}
544
545void abac_graph_free(abac_graph_t *graph) {
546    abac_vertex_t *vertex;
547    abac_edge_t *edge;
548
549    // kill derived edges
550    _clear_derived(graph);
551
552    // delete vertices
553    while ((vertex = graph->vertices) != NULL) {
554        HASH_DEL(graph->vertices, vertex);
555
556        abac_role_free(vertex->role);
557
558        abac_list_foreach(vertex->edges, edge,
559            if (edge->credential != NULL)
560                abac_credential_free(edge->credential);
561            free(edge);
562        );
563        abac_list_free(vertex->edges);
564        free(vertex);
565    }
566
567    free(graph);
568}
569
570abac_role_t *abac_vertex_role(abac_vertex_t *vertex) {
571    return vertex->role;
572}
Note: See TracBrowser for help on using the repository browser.