package net.deterlab.abac; import org.apache.commons.collections15.*; import org.apache.commons.collections15.functors.*; import edu.uci.ics.jung.graph.*; import edu.uci.ics.jung.graph.event.*; import edu.uci.ics.jung.graph.util.*; import java.awt.geom.Point2D; import java.io.*; import java.util.*; /** * Represents a global graph of credentials in the form of principals and * attributes. */ public class CredentialGraph { protected Graph g = null; protected java.util.Set derived_edges = new HashSet(); protected Query pq; protected boolean m_dirty; public CredentialGraph() { /* create the graph */ g = Graphs.synchronizedDirectedGraph( new DirectedSparseGraph()); pq = new Query(g); } /** * Returns a Query object which can be used to query the graph. This object * becomes invalid if the graph is modified. */ public Query querier() { derive_implied_edges(); return new Query(g); } /** * Add a credential to the graph. */ public void add_credential(Credential cred) { Role tail = cred.tail(); Role head = cred.head(); /* explicitly add the vertices, otherwise get a null pointer exception */ if ( !g.containsVertex(tail)) g.addVertex(tail); if ( !g.containsVertex(tail)) g.addVertex(head); if (!g.containsEdge(cred)) g.addEdge(cred, tail, head); // add the prereqs of an intersection to the graph if (tail.is_intersection()) for (Role prereq : tail.prereqs()) g.addVertex(prereq); m_dirty = true; } /** * Remove a credential from the graph. */ public void remove_credential(Credential cred) { if (g.containsEdge(cred)) g.removeEdge(cred); m_dirty = true; } /** * Add a role w/o an edge */ public void add_vertex(Role v) { if (!g.containsVertex(v)) { g.addVertex(v); m_dirty = true; } } public void remove_vertex(Role v) { if (g.containsVertex(v)) { g.removeVertex(v); m_dirty = true; } } /** * Returns a collection of the credentials in the graph. */ public Collection credentials() { Collection creds = new HashSet(); // only return creds with a cert: all others are derived edges for (Credential cred : g.getEdges()) if (cred.cert() != null) creds.add(cred); return creds; } public Collection roles() { return g.getVertices(); } /** * Derive the implied edges in the graph, according to RT0 derivation rules. * They are added to this graph. See "Distributed Credential Chain Discovery * in Trust Management" by Ninghui Li et al. for details. Note that a * derived linking edge can imply a new intersection edge and vice versa. * Therefore we iteratively derive edges, giving up when an iteration * produces 0 new edges. */ protected synchronized void derive_implied_edges() { // nothing to do on a clean graph if (!m_dirty) return; clear_old_edges(); // iteratively derive links. continue as long as new links are added while (derive_links_iter() > 0) ; m_dirty = false; } /** * Single iteration of deriving implied edges. Returns the number of new * links added. */ protected int derive_links_iter() { int count = 0; /* for every node in the graph.. */ for (Role vertex : g.getVertices()) { if (vertex.is_intersection()) { // for each prereq edge: // find set of principals that have the prereq // find the intersection of all sets (i.e., principals that satisfy all prereqs) // for each principal in intersection: // add derived edge Set principals = null; for (Role prereq : vertex.prereqs()) { Set cur_principals = pq.find_principals(prereq); if (principals == null) principals = cur_principals; else // no, they couldn't just call it "intersection" principals.retainAll(cur_principals); if (principals.size() == 0) break; } // add em for (Role principal : principals) if (add_derived_edge(vertex, principal)) ++count; } else if (vertex.is_linking()) { // make the rest of the code a bit clearer Role A_r1_r2 = vertex; Role A_r1 = new Role(A_r1_r2.A_r1()); String r2 = A_r1_r2.r2(); /* locate the node A.r1 */ if (!g.containsVertex(A_r1)) continue; /* boring: nothing of the form A.r1 */ /* for each B that satisfies A_r1 */ for (Role principal : pq.find_principals(A_r1)) { Role B_r2 = new Role(principal + "." + r2); if (!g.containsVertex(B_r2)) continue; if (add_derived_edge(A_r1_r2, B_r2)) ++count; } } } return count; } /** * Add a derived edge in the graph. Returns true only if the edge does not * exist. */ protected boolean add_derived_edge(Role head, Role tail) { // edge exists: return false if (g.findEdge(tail, head) != null) return false; // add the new edge Credential derived_edge = new Credential(head, tail); derived_edges.add(derived_edge); g.addEdge(derived_edge, tail, head); return true; } /** * Clear the derived edges that currently exist in the graph. This is done * before the edges are rederived. The derived edges in filtered graphs are * also cleared. */ protected void clear_old_edges() { for (Credential i: derived_edges) g.removeEdge(i); derived_edges = new HashSet(); } }