source: libabac/abac_graph.c @ 342e28f

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

load intersection attribute certificates, do not add them to the graph

  • Property mode set to 100644
File size: 11.5 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    UT_hash_handle hh;
19};
20
21// edge
22typedef struct _abac_edge_t {
23    abac_vertex_t *vertex;
24    abac_credential_t *credential;
25} abac_edge_t;
26
27// derived edge
28typedef struct _abac_derived_key_t {
29    abac_vertex_t *head;
30    abac_edge_t *tail;
31} abac_derived_key_t;
32
33typedef struct _abac_derived_t {
34    abac_derived_key_t key;
35    UT_hash_handle hh;
36} abac_derived_t;
37
38// graph
39struct _abac_graph_t {
40    abac_vertex_t *vertices;
41    abac_derived_t *derived;
42    int dirty;
43};
44
45/**
46 * Create a new graph.
47 */
48abac_graph_t *abac_graph_new(void) {
49    abac_graph_t *graph = abac_xmalloc(sizeof(abac_graph_t));
50
51    graph->vertices = NULL;
52    graph->derived = NULL;
53    graph->dirty = 0;
54
55    return graph;
56}
57
58/**
59 * Deep copy a graph.
60 */
61abac_graph_t *abac_graph_dup(abac_graph_t *graph) {
62    abac_vertex_t *vertex;
63    abac_edge_t *edge;
64
65    abac_graph_t *clone = abac_graph_new();
66
67    // copy the vertices edge by edge
68    for (vertex = graph->vertices; vertex != NULL; vertex = vertex->hh.next)
69        abac_list_foreach(vertex->edges, edge,
70            // only copy non-derived edges
71            if (edge->credential != NULL)
72                abac_graph_add_credential(clone, edge->credential);
73        );
74
75    return clone;
76}
77
78/**
79 * Add a vertex to the graph. Should only be called by abac_graph_add_credential.
80 */
81static abac_vertex_t *_get_vertex(abac_graph_t *graph, abac_role_t *role) {
82    abac_vertex_t *vertex;
83    char *string;
84   
85    string = abac_role_string(role);
86    HASH_FIND_STR(graph->vertices, string, vertex);
87
88    // add the vertex if it doesn't exist
89    if (vertex == NULL) {
90        vertex = abac_xmalloc(sizeof(abac_vertex_t));
91        vertex->role = abac_role_dup(role);
92        vertex->name = abac_role_string(vertex->role);
93
94        // create the list of edges
95        vertex->edges = abac_list_new();
96
97        // add it to the vertices
98        HASH_ADD_KEYPTR(hh, graph->vertices, vertex->name, strlen(vertex->name), vertex);
99    }
100
101    return vertex;
102}
103
104/**
105 * Add a credential to the credential graph.
106 */
107int abac_graph_add_credential(abac_graph_t *graph, abac_credential_t *cred) {
108    abac_vertex_t *head_vertex, *tail_vertex;
109    abac_edge_t *edge;
110
111    assert(cred != NULL);
112
113    abac_role_t *head = abac_credential_head(cred);
114    abac_role_t *tail = abac_credential_tail(cred);
115
116    // TODO: handle intersections properly
117    if (tail == NULL)
118        return 0;
119
120    // a valid credential must have a role for the head
121    if (!abac_role_is_role(head)) return 0;
122
123    head_vertex = _get_vertex(graph, head);
124    tail_vertex = _get_vertex(graph, tail);
125
126    // make sure we don't insert the same edge twice (ugh)
127    abac_list_foreach(head_vertex->edges, edge,
128        if (edge->vertex == tail_vertex)
129            return 0;
130    );
131
132    // create the edge and add it
133    edge = abac_xmalloc(sizeof(abac_edge_t));
134    edge->vertex = tail_vertex;
135    edge->credential = abac_credential_dup(cred);
136
137    abac_list_add(head_vertex->edges, edge);
138
139    // must re-derive edges
140    graph->dirty = 1;
141
142    return 1;
143}
144
145// find the principals that have a role
146static abac_set_t *_find_principals(abac_graph_t *graph, abac_vertex_t *start_vertex) {
147    abac_set_t *principals = abac_set_new();
148
149    abac_list_t *traversal = abac_graph_postorder(graph, start_vertex->role);
150    abac_vertex_t *vertex;
151
152    abac_list_foreach(traversal, vertex,
153        if (abac_role_is_principal(vertex->role))
154            abac_set_add(principals, abac_role_string(vertex->role));
155    );
156
157    abac_list_free(traversal);
158    return principals;
159}
160
161// remove any derived edges from the graph
162void _clear_derived(abac_graph_t *graph) {
163    abac_derived_t *current;
164
165    while (graph->derived) {
166        current = graph->derived;
167
168        HASH_DEL(graph->derived, current);
169
170        abac_vertex_t *head = current->key.head;
171        abac_edge_t *tail = current->key.tail;
172        assert(tail->credential == NULL);
173
174        // this can fail, but we assume the data structures are consistent
175        abac_list_remove(head->edges, tail);
176
177        free(current);
178        free(tail);
179    }
180}
181
182void abac_graph_derive_links(abac_graph_t *graph) {
183    abac_vertex_t *vertex;
184
185    if (!graph->dirty)
186        return;
187
188    for (vertex = graph->vertices; vertex != NULL; vertex = vertex->hh.next) {
189        // we only care about linking roles
190        if (!abac_role_is_linking(vertex->role))
191            continue;
192
193        // linking roles take the form A.r1.r2
194        char *A_r1 = abac_role_linked_role(vertex->role);
195        char *r2 = abac_role_role_name(vertex->role);
196
197        // find the linked role in the graph
198        abac_vertex_t *A_r1_vertex;
199        HASH_FIND_STR(graph->vertices, A_r1, A_r1_vertex);
200        if (A_r1_vertex == NULL)
201            continue;
202
203        // find the principals that have A.r1
204        abac_set_t *principals = _find_principals(graph, A_r1_vertex);
205        char *B;
206
207        abac_list_t *elts = abac_set_elements(principals);
208
209        // and add a link for each B.r2 to A.r1.r2
210        abac_list_foreach(elts, B,
211            int B_len = strlen(B);
212            int r2_len = strlen(r2);
213
214            // create the string B.r2, thx C
215            char *B_r2 = malloc(B_len + r2_len + 2);
216            memcpy(B_r2, B, B_len);
217            B_r2[B_len] = '.';
218            memcpy(B_r2 + B_len + 1, r2, r2_len);
219            B_r2[B_len + r2_len + 1] = 0;
220
221            abac_vertex_t *B_r2_vertex;
222            HASH_FIND_STR(graph->vertices, B_r2, B_r2_vertex);
223
224            // add an edge if the principal's granted it to someone
225            if (B_r2_vertex) {
226                debug_printf("adding edge from %s to %s\n", B_r2, abac_role_string(vertex->role));
227                abac_edge_t *edge = abac_xmalloc(sizeof(abac_edge_t));
228                edge->vertex = B_r2_vertex;
229                edge->credential = NULL;
230                abac_list_add(vertex->edges, edge);
231
232                // add to list of derived edges
233                abac_derived_t *derived = abac_xmalloc(sizeof(abac_derived_t));
234                derived->key.head = vertex;
235                derived->key.tail = edge;
236                HASH_ADD(hh, graph->derived, key, sizeof(abac_derived_key_t), derived);
237            }
238
239#ifdef DEBUG
240            debug_printf("    incoming edges for %s\n", abac_role_string(vertex->role));
241            abac_edge_t *cur;
242            abac_list_foreach(vertex->edges, cur,
243                debug_printf("        %s (%s)\n", abac_role_string(cur->vertex->role), cur->vertex->name);
244            );
245#endif
246
247            free(B_r2);
248        );
249
250        abac_list_free(elts);
251        abac_set_free(principals);
252    }
253
254    graph->dirty = 0;
255}
256
257static void _order_recurse(abac_vertex_t *vertex, abac_set_t *seen, int preorder, abac_list_t *stack) {
258    abac_edge_t *incoming;
259
260    // don't revisit nodes
261    if (!abac_set_add(seen, abac_role_string(vertex->role)))
262        return;
263
264    if (preorder)
265        abac_list_add(stack, vertex);
266
267    // recurse along the incoming vertices
268    abac_list_foreach(vertex->edges, incoming,
269        _order_recurse(incoming->vertex, seen, preorder, stack);
270    );
271
272    if (!preorder)
273        abac_list_add(stack, vertex);
274}
275
276static abac_list_t *_order(abac_graph_t *graph, abac_role_t *start, int preorder) {
277    debug_printf("%sorder at %s\n", preorder ? "pre" : "post", abac_role_string(start));
278
279    abac_vertex_t *start_vertex = _get_vertex(graph, start);
280    abac_set_t *seen = abac_set_new();
281
282    // create the return list
283    abac_list_t *stack = abac_list_new();
284
285    _order_recurse(start_vertex, seen, preorder, stack);
286
287    abac_set_free(seen);
288
289    return stack;
290}
291
292abac_list_t *abac_graph_postorder(abac_graph_t *graph, abac_role_t *start) {
293    return _order(graph, start, 0);
294}
295
296/**
297 * Postorder traverse the graph and return all the credentials within.
298 */
299abac_list_t *abac_graph_postorder_credentials(abac_graph_t *graph, char *start) {
300    abac_vertex_t *vertex;
301    abac_edge_t *incoming;
302
303    // get the postorder of vertices
304    abac_role_t *role = abac_role_from_string(start);
305    abac_list_t *order = abac_graph_postorder(graph, role);
306
307    // go through the list and dup all the credentials
308    abac_list_t *credentials = abac_list_new();
309    abac_list_foreach(order, vertex,
310        abac_list_foreach(vertex->edges, incoming,
311            if (incoming->credential != NULL)
312                abac_list_add(credentials, abac_credential_dup(incoming->credential));
313        );
314    );
315
316    abac_role_free(role);
317    abac_list_free(order);
318
319    return credentials;
320}
321
322static void _query(abac_graph_t *graph, char *role_name, char *principal, abac_graph_t *return_graph) {
323    abac_vertex_t *vertex;
324    abac_edge_t *incoming;
325
326    abac_role_t *role = abac_role_from_string(role_name);
327    abac_role_t *prin_role = abac_role_from_string(principal);
328
329    // give up on bogus roles
330    if (role == NULL || prin_role == NULL) {
331        free(role);
332        free(prin_role);
333        return;
334    }
335
336    abac_set_t *on_path = abac_set_new();
337    abac_set_add(on_path, abac_role_string(prin_role));
338
339    abac_list_t *traversal = abac_graph_postorder(graph, role);
340    abac_list_foreach(traversal, vertex,
341        abac_role_t *role = vertex->role;
342
343        abac_list_foreach(vertex->edges, incoming,
344            abac_role_t *incoming_role = incoming->vertex->role;
345
346            if (!abac_set_contains(on_path, abac_role_string(incoming_role)))
347                continue;
348
349            abac_set_add(on_path, abac_role_string(role));
350
351            // add non-derived edges to the proof graph
352            if (!abac_role_is_linking(role))
353                abac_graph_add_credential(return_graph, incoming->credential);
354
355            // recursively find linked roles
356            else {
357                char *linked_role = abac_role_linked_role(role);
358                char *principal = abac_role_principal(incoming_role);
359
360                _query(graph, linked_role, principal, return_graph);
361            }
362        );
363    );
364
365    abac_list_free(traversal);
366    abac_set_free(on_path);
367    abac_role_free(role);
368    abac_role_free(prin_role);
369}
370
371abac_graph_t *abac_graph_query(abac_graph_t *graph, char *role, char *principal) {
372    abac_graph_derive_links(graph);
373
374    abac_graph_t *return_graph = abac_graph_new();
375    _query(graph, role, principal, return_graph);
376    abac_graph_derive_links(return_graph);
377    return return_graph;
378}
379
380/**
381 * Get all the credentials (attribute/issuer cert pairs) from the graph.
382 */
383abac_list_t *abac_graph_credentials(abac_graph_t *graph) {
384    abac_list_t *credentials = abac_list_new();
385
386    abac_vertex_t *vertex;
387
388    for (vertex = graph->vertices; vertex != NULL; vertex = vertex->hh.next) {
389        abac_edge_t *edge;
390        abac_list_foreach(vertex->edges, edge,
391            if (edge->credential != NULL)
392                abac_list_add(credentials, abac_credential_dup(edge->credential));
393        );
394    }
395
396    return credentials;
397}
398
399void abac_graph_free(abac_graph_t *graph) {
400    abac_vertex_t *vertex;
401    abac_edge_t *edge;
402
403    // kill derived edges
404    _clear_derived(graph);
405
406    // delete vertices
407    while ((vertex = graph->vertices) != NULL) {
408        HASH_DEL(graph->vertices, vertex);
409
410        abac_role_free(vertex->role);
411
412        abac_list_foreach(vertex->edges, edge,
413            if (edge->credential != NULL)
414                abac_credential_free(edge->credential);
415            free(edge);
416        );
417        abac_list_free(vertex->edges);
418        free(vertex);
419    }
420
421    free(graph);
422}
423
424abac_role_t *abac_vertex_role(abac_vertex_t *vertex) {
425    return vertex->role;
426}
Note: See TracBrowser for help on using the repository browser.