source: libabac/abac_graph.c @ 704fde7

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

iteratively derive edges

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