Index: java/net/deterlab/abac/CredentialGraph.java
===================================================================
--- java/net/deterlab/abac/CredentialGraph.java	(revision 31b67d5cfd00ac323a7f60b4ba8c4e1567187bdb)
+++ java/net/deterlab/abac/CredentialGraph.java	(revision cac4c764ac3f95eb6e2bf8ebe2ad39c61bed910d)
@@ -31,5 +31,5 @@
      */
     public Query querier() {
-        derive_linked_edges();
+        derive_implied_edges();
         return new Query(g);
     }
@@ -47,4 +47,9 @@
 
         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);
     }
 
@@ -75,32 +80,94 @@
 
     /**
-     * Derive the linked edges in the graph, according to RT0 derivation rules.
-     * They are added to this graph and to any filtered graphs that match. See
-     * "Distributed Credential Chain Discovery in Trust Management" by Ninghui
-     * Li et al. for details.
+     * 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.
      */
-    private void derive_linked_edges() {
-        clear_old_edges();
+    private void derive_implied_edges() { clear_old_edges();
+
+        // iteratively derive links. continue as long as new links are added
+        while (derive_links_iter() > 0)
+            ;
+    }
+
+    /**
+     * Single iteration of deriving implied edges. Returns the number of new
+     * links added.
+     */
+    private int derive_links_iter() {
+        int count = 0;
 
         /* for every node in the graph.. */
-        for (Role A_r1_r2 : g.getVertices()) {
-            if (!A_r1_r2.is_linking()) continue;
+        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
 
-            Role A_r1 = new Role(A_r1_r2.A_r1());
-            String r2 = A_r1_r2.r2();
+                Set<Role> principals = null;
 
-            /* locate the node A.r1 */
-            if (!g.containsVertex(A_r1)) continue; /* boring: nothing of the form A.r1 */
+                for (Role prereq : vertex.prereqs()) {
+                    Set<Role> cur_principals = pq.find_principals(prereq);
 
-            /* 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 (principals == null)
+                        principals = cur_principals;
+                    else
+                        // no, they couldn't just call it "intersection"
+                        principals.retainAll(cur_principals);
 
-                Credential derived_edge = new Credential(A_r1_r2, B_r2);
-                derived_edges.add(derived_edge);
-                g.addEdge(derived_edge, B_r2, A_r1_r2);
+                    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.
+     */
+    private 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;
     }
 
Index: java/net/deterlab/abac/Query.java
===================================================================
--- java/net/deterlab/abac/Query.java	(revision 31b67d5cfd00ac323a7f60b4ba8c4e1567187bdb)
+++ java/net/deterlab/abac/Query.java	(revision cac4c764ac3f95eb6e2bf8ebe2ad39c61bed910d)
@@ -72,6 +72,6 @@
      * traversing edges in the reverse direction.
      */
-    public Collection<Role> find_principals(Role n) {
-        Collection<Role> principals = new ArrayList<Role>();
+    public Set<Role> find_principals(Role n) {
+        Set<Role> principals = new HashSet<Role>();
     
         GetPrincipals f = new GetPrincipals(principals);
Index: java/net/deterlab/abac/Role.java
===================================================================
--- java/net/deterlab/abac/Role.java	(revision 31b67d5cfd00ac323a7f60b4ba8c4e1567187bdb)
+++ java/net/deterlab/abac/Role.java	(revision cac4c764ac3f95eb6e2bf8ebe2ad39c61bed910d)
@@ -9,15 +9,42 @@
     private String m_A_r1, m_r2;
     private String m_prefix;
+    private Role[] m_prereqs;
 
     /**
-     * Create a role from a string. The string must be of the format "A",
+     * Create a role from a string. A single role must be of the format "A",
      * "A.r1", or "A.r1.r2", where A is a principal and r1 and r2 are role
-     * names. If the string does not have this format, the constructor throws
-     * a RuntimeException.
+     * names. This constructor also supports intersection roles: a sequence of
+     * two or more roles separated by " &amp; ".
+     *
+     * If the string does not have this format, the constructor throws a
+     * RuntimeException.
      */
     public Role(String s) throws RuntimeException {
         m_string = s;
 
-        m_parts = s.split("\\.");
+        // intersection roles have at least two roles separated by " & "
+        String[] isect_roles = s.split(" & ");
+
+        // ordinary role
+        if (isect_roles.length == 1)
+            single_role();
+
+        // intersection role: make a list of prereqs
+        else {
+            m_prereqs = new Role[isect_roles.length];
+            for (int i = 0; i < isect_roles.length; ++i)
+                m_prereqs[i] = new Role(isect_roles[i]);
+
+            // this make is_principal etc. work properly
+            m_parts = new String[0];
+        }
+    }
+
+    /**
+     * Initialize a single non-intersection role. See constructor for details of
+     * role format. Will throw RuntimeException if the role is invalid.
+     */
+    private void single_role() throws RuntimeException {
+        m_parts = m_string.split("\\.");
         if (m_parts.length > 3)
             throw new RuntimeException("Not a valid role: " + m_string);
@@ -53,4 +80,9 @@
      */
     public boolean is_linking() { return m_parts.length == 3; }
+
+    /**
+     * Returns true iff the role represents an intersection role.
+     */
+    public boolean is_intersection() { return m_prereqs != null; }
 
     /**
@@ -91,4 +123,15 @@
     }
 
+    /**
+     * Get the roles that form the prerequisites to this intersection. Throws
+     * a runtime exception if this is not an intersection role.
+     */
+    public Role[] prereqs() throws RuntimeException {
+        if (!is_intersection())
+            throw new RuntimeException("Not an intersection role.");
+
+        return m_prereqs;
+    }
+
     public String toString() {
         return m_string;
