source: java/net/deterlab/abac/CredentialGraph.java @ 7ad0076

abac0-leakabac0-meicompt_changesgec13mei-idmei-rt0-nmei_rt0mei_rt2mei_rt2_fix_1meiyap-rt1meiyap1rt2tvf-new-xml
Last change on this file since 7ad0076 was a624bd1, checked in by Ted Faber <faber@…>, 14 years ago

Back to directed graphs. This may have fixed graph manipulation.

  • Property mode set to 100644
File size: 5.8 KB
Line 
1package net.deterlab.abac;
2
3import org.apache.commons.collections15.*;
4import org.apache.commons.collections15.functors.*;
5
6import edu.uci.ics.jung.graph.*;
7import edu.uci.ics.jung.graph.event.*;
8import edu.uci.ics.jung.graph.util.*;
9
10import java.awt.geom.Point2D;
11import java.io.*;
12import java.util.*;
13
14/**
15 * Represents a global graph of credentials in the form of principals and
16 * attributes.
17 */
18public class CredentialGraph {
19    protected Graph<Role,Credential> g = null;
20    protected java.util.Set<Credential> derived_edges = new HashSet<Credential>();
21    protected Query pq;
22    protected boolean m_dirty;
23
24    public CredentialGraph() {
25        /* create the graph */
26        g = Graphs.<Role,Credential>synchronizedDirectedGraph(
27                new DirectedSparseGraph<Role,Credential>());
28        pq = new Query(g);
29    }
30
31    /**
32     * Returns a Query object which can be used to query the graph. This object
33     * becomes invalid if the graph is modified.
34     */
35    public Query querier() {
36        derive_implied_edges();
37        return new Query(g);
38    }
39
40    /**
41     * Add a credential to the graph.
42     */
43    public void add_credential(Credential cred) {
44        Role tail = cred.tail();
45        Role head = cred.head();
46
47        /* explicitly add the vertices, otherwise get a null pointer exception */
48        g.addVertex(tail);
49        g.addVertex(head);
50
51        g.addEdge(cred, tail, head);
52
53        // add the prereqs of an intersection to the graph
54        if (tail.is_intersection())
55            for (Role prereq : tail.prereqs())
56                g.addVertex(prereq);
57
58        m_dirty = true;
59    }
60
61    /**
62     * Remove a credential from the graph.
63     */
64    public void remove_credential(Credential cred) {
65        if (g.containsEdge(cred))
66            g.removeEdge(cred);
67        m_dirty = true;
68    }
69
70    /**
71     * Returns a collection of the credentials in the graph.
72     */
73    public Collection<Credential> credentials() {
74        Collection<Credential> creds = new HashSet<Credential>();
75
76        // only return creds with a cert: all others are derived edges
77        for (Credential cred : g.getEdges())
78            if (cred.cert() != null)
79                creds.add(cred);
80
81        return creds;
82    }
83
84    /**
85     * Derive the implied edges in the graph, according to RT0 derivation rules.
86     * They are added to this graph. See "Distributed Credential Chain Discovery
87     * in Trust Management" by Ninghui Li et al. for details. Note that a
88     * derived linking edge can imply a new intersection edge and vice versa.
89     * Therefore we iteratively derive edges, giving up when an iteration
90     * produces 0 new edges.
91     */
92    protected synchronized void derive_implied_edges() {
93        // nothing to do on a clean graph
94        if (!m_dirty)
95            return;
96
97        clear_old_edges();
98
99        // iteratively derive links. continue as long as new links are added
100        while (derive_links_iter() > 0)
101            ;
102        m_dirty = false;
103    }
104
105    /**
106     * Single iteration of deriving implied edges. Returns the number of new
107     * links added.
108     */
109    protected int derive_links_iter() {
110        int count = 0;
111
112        /* for every node in the graph.. */
113        for (Role vertex : g.getVertices()) {
114            if (vertex.is_intersection()) {
115                // for each prereq edge:
116                //     find set of principals that have the prereq
117                // find the intersection of all sets (i.e., principals that satisfy all prereqs)
118                // for each principal in intersection:
119                //     add derived edge
120
121                Set<Role> principals = null;
122
123                for (Role prereq : vertex.prereqs()) {
124                    Set<Role> cur_principals = pq.find_principals(prereq);
125
126                    if (principals == null)
127                        principals = cur_principals;
128                    else
129                        // no, they couldn't just call it "intersection"
130                        principals.retainAll(cur_principals);
131
132                    if (principals.size() == 0)
133                        break;
134                }
135
136                // add em
137                for (Role principal : principals)
138                    if (add_derived_edge(vertex, principal))
139                        ++count;
140            }
141
142            else if (vertex.is_linking()) {
143                // make the rest of the code a bit clearer
144                Role A_r1_r2 = vertex;
145
146                Role A_r1 = new Role(A_r1_r2.A_r1());
147                String r2 = A_r1_r2.r2();
148
149                /* locate the node A.r1 */
150                if (!g.containsVertex(A_r1)) continue; /* boring: nothing of the form A.r1 */
151
152                /* for each B that satisfies A_r1 */
153                for (Role principal : pq.find_principals(A_r1)) {
154                    Role B_r2 = new Role(principal + "." + r2);
155                    if (!g.containsVertex(B_r2)) continue;
156
157                    if (add_derived_edge(A_r1_r2, B_r2))
158                        ++count;
159                }
160            }
161        }
162
163        return count;
164    }
165
166    /**
167     * Add a derived edge in the graph. Returns true only if the edge does not
168     * exist.
169     */
170    protected boolean add_derived_edge(Role head, Role tail) {
171        // edge exists: return false
172        if (g.findEdge(tail, head) != null)
173            return false;
174
175        // add the new edge
176        Credential derived_edge = new Credential(head, tail);
177        derived_edges.add(derived_edge);
178        g.addEdge(derived_edge, tail, head);
179
180        return true;
181    }
182
183    /**
184     * Clear the derived edges that currently exist in the graph. This is done
185     * before the edges are rederived. The derived edges in filtered graphs are
186     * also cleared.
187     */
188    protected void clear_old_edges() { 
189        for (Credential i: derived_edges) 
190            g.removeEdge(i);
191        derived_edges = new HashSet<Credential>();
192    }
193}
Note: See TracBrowser for help on using the repository browser.