Index: java/.classpath
===================================================================
--- java/.classpath	(revision 31b67d5cfd00ac323a7f60b4ba8c4e1567187bdb)
+++ java/.classpath	(revision 31b67d5cfd00ac323a7f60b4ba8c4e1567187bdb)
@@ -0,0 +1,1 @@
+.:jar/jung-algorithms-2.0.jar:jar/jung-api-2.0.jar:jar/jung-graph-impl-2.0.jar:jar/jung-visualization-2.0.jar:jar/collections-generic-4.01.jar
Index: java/GraphTest.java
===================================================================
--- java/GraphTest.java	(revision 31b67d5cfd00ac323a7f60b4ba8c4e1567187bdb)
+++ java/GraphTest.java	(revision 31b67d5cfd00ac323a7f60b4ba8c4e1567187bdb)
@@ -0,0 +1,62 @@
+import java.io.*;
+
+import edu.uci.ics.jung.graph.*;
+
+import net.deterlab.abac.Credential;
+import net.deterlab.abac.CredentialGraph;
+import net.deterlab.abac.Query;
+import net.deterlab.abac.Role;
+
+/**
+ * Simple test of the native Java implementation of ABAC. Loads credentials
+ * from an rt0 file and runs a query against them.
+ */
+public class GraphTest {
+    public static void main(String[] args) throws IOException {
+        if (args.length < 3) {
+            System.out.println("Usage: GraphTest <rt0 file> <role> <principal>");
+            System.out.println("    runs the query role <-?- principal and prints the result");
+            System.exit(1);
+        }
+
+        String role = args[1];
+        String prin = args[2];
+
+        CredentialGraph graph = new CredentialGraph();
+
+        BufferedReader reader = new BufferedReader(new FileReader(args[0]));
+        String line;
+        while ((line = reader.readLine()) != null) {
+            // skip comments
+            if (line.startsWith("#"))
+                continue;
+
+            String[] parts = line.split("\\s*<--?\\s*");
+
+            if (parts.length != 2) {
+                System.out.println("Warning: funky line: " + line);
+                continue;
+            }
+
+            Role head = new Role(parts[0]);
+            Role tail = new Role(parts[1]);
+
+            if (!head.is_role()) {
+                System.out.println("Warning: invalid role in head position: " + line);
+                continue;
+            }
+
+            Credential cred = new Credential(head, tail);
+            graph.add_credential(cred);
+        }
+
+        //
+        // run the query
+        //
+
+        Query q = graph.querier();
+        Graph<Role, Credential> ret = q.run(role, prin);
+        for (Credential c : ret.getEdges())
+            System.out.println(c.toString());
+    }
+}
Index: java/net/deterlab/abac/Credential.java
===================================================================
--- java/net/deterlab/abac/Credential.java	(revision 31b67d5cfd00ac323a7f60b4ba8c4e1567187bdb)
+++ java/net/deterlab/abac/Credential.java	(revision 31b67d5cfd00ac323a7f60b4ba8c4e1567187bdb)
@@ -0,0 +1,37 @@
+package net.deterlab.abac;
+
+public class Credential {
+    /**
+     * Create a credential from a head and tail role. This is only for testing.
+     * In a real implementation the Credential must be loaded from an X.509
+     * attribute cert.
+     */
+    public Credential(Role head, Role tail) {
+        m_head = head;
+        m_tail = tail;
+    }
+
+    /**
+     * Get the head role from the credential.
+     */
+    public Role head() {
+        return m_head;
+    }
+
+    /**
+     * Get the tail role from the credential
+     */
+    public Role tail() {
+        return m_tail;
+    }
+
+    /**
+     * Turn the credential into string form. The format is head &lt;- tail. For
+     * example: A.r1 &lt;- B.r2.r3.
+     */
+    public String toString() {
+        return m_head + " <- " + m_tail;
+    }
+
+    private Role m_head, m_tail;
+}
Index: java/net/deterlab/abac/CredentialGraph.java
===================================================================
--- java/net/deterlab/abac/CredentialGraph.java	(revision 31b67d5cfd00ac323a7f60b4ba8c4e1567187bdb)
+++ java/net/deterlab/abac/CredentialGraph.java	(revision 31b67d5cfd00ac323a7f60b4ba8c4e1567187bdb)
@@ -0,0 +1,117 @@
+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 {
+    private Graph<Role,Credential> g = null;
+    private java.util.Set<Credential> derived_edges = new HashSet<Credential>();
+    private Query pq;
+
+    public CredentialGraph() {
+        /* create the graph */
+        g = Graphs.<Role,Credential>synchronizedDirectedGraph(new DirectedSparseGraph<Role,Credential>());
+        pq = new Query(g);
+    }
+
+    /**
+     * Returns a Query object which can be used to query the graph.
+     */
+    public Query querier() {
+        derive_linked_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 */
+        g.addVertex(tail);
+        g.addVertex(head);
+
+        g.addEdge(cred, tail, head);
+    }
+
+    /**
+     * Remove a credential from the graph.
+     */
+    public void remove_credential(Credential cred) {
+        g.removeEdge(cred);
+    }
+
+    /**
+     * Returns a collection of the credentials in the graph.
+     */
+    public Collection<Credential> credentials() {
+        Collection<Credential> creds = new HashSet<Credential>();
+        for (Credential cred : g.getEdges()) {
+            // FIXME: this should check if there's a cert on the cred
+            // this supports all types of derived edges, including intersection
+
+            Role head = g.getDest(cred);
+
+            /* any edge to a linking node is derived, so skip it */
+            if (!head.is_linking())
+                creds.add(cred);
+        }
+        return creds;
+    }
+
+    /**
+     * 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.
+     */
+    private void derive_linked_edges() {
+        clear_old_edges();
+
+        /* for every node in the graph.. */
+        for (Role A_r1_r2 : g.getVertices()) {
+            if (!A_r1_r2.is_linking()) continue;
+
+            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;
+
+                Credential derived_edge = new Credential(A_r1_r2, B_r2);
+                derived_edges.add(derived_edge);
+                g.addEdge(derived_edge, B_r2, A_r1_r2);
+            }
+        }
+    }
+
+    /**
+     * 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.
+     */
+    private void clear_old_edges() {
+        for (Credential i: derived_edges)
+            g.removeEdge(i);
+        derived_edges = new HashSet<Credential>();
+    }
+}
Index: java/net/deterlab/abac/Query.java
===================================================================
--- java/net/deterlab/abac/Query.java	(revision 31b67d5cfd00ac323a7f60b4ba8c4e1567187bdb)
+++ java/net/deterlab/abac/Query.java	(revision 31b67d5cfd00ac323a7f60b4ba8c4e1567187bdb)
@@ -0,0 +1,266 @@
+package net.deterlab.abac;
+
+import org.apache.commons.collections15.*;
+
+import edu.uci.ics.jung.graph.*;
+import edu.uci.ics.jung.graph.util.*;
+
+import java.util.*;
+
+/**
+ * A class for making queries against the graph. It supports direct queries as
+ * well as reachability in either direction. See the run method for details.
+ */
+public class Query {
+    private Graph<Role,Credential> g;
+    private int vertex_count;
+
+    public Query(Graph<Role,Credential> g) {
+        this.g = g;
+    }
+
+    /**
+     * Run a query against the graph, returning a graph of the results. If the
+     * results are empty or the query fails, an empty graph is returned. When
+     * derived edges are involved, the subgraphs that imply those edges are
+     * included.
+     */
+    public Graph<Role,Credential> run(String attr, String prin) {
+        Role attribute = new Role(attr);
+        Role principal = new Role(prin);
+        Graph<Role,Credential> ret =
+            Graphs.<Role,Credential>synchronizedDirectedGraph(
+                    new DirectedSparseGraph<Role,Credential>());
+
+        /* empty attribute, non-empty principal: find everywhere the principal can go */
+        if (attr.isEmpty() && !prin.isEmpty()) {
+            if (g.containsVertex(principal)) {
+                CollectReversePath collect = new CollectReversePath(ret);
+                forward_dfs(principal, collect);
+            }
+        }
+
+        /* otherwise we're going to do some kind of a reverse dfs */
+        else if (g.containsVertex(attribute)) { 
+            if ( prin == null || prin.isEmpty()) {
+                CollectQueryGraph  collect = new CollectQueryGraph(ret);
+                reverse_dfs(new Role(attr), collect);
+            }
+            else {
+                if ( g.containsVertex(principal)) {
+                    CollectQueryPath  collect = new CollectQueryPath(ret, principal);
+                    reverse_dfs(new Role(attr), collect);
+                }
+            }
+        }
+
+        vertex_count = ret.getVertexCount();
+
+        return ret;
+    }
+
+    /**
+     * Returns true after running a query that returns a non-empty set of
+     * vertices.
+     */
+    public boolean successful() {
+        return vertex_count > 0;
+    }
+
+    /**
+     * Returns a collection of principals reachable from a Role when
+     * traversing edges in the reverse direction.
+     */
+    public Collection<Role> find_principals(Role n) {
+        Collection<Role> principals = new ArrayList<Role>();
+    
+        GetPrincipals f = new GetPrincipals(principals);
+        reverse_dfs(n, f);
+        return principals;
+    }
+
+
+    /**
+     * Interface to pass to the reverse_dfs class.  The node function gets
+     * called for every node visited by the dfs.
+     */
+    interface DfsFcn {
+        public void node(Role x);
+        public void node_after(Role x);
+    }
+
+    /**
+     * Class used to pull all the principals out of a reverse_dfs searched
+     * graph.  It takes a collection to the constructor and adds all principals
+     * it sees to that collection.  In no collection is passed in, it creates a
+     * local HashSet of vertices.  The collection is accessible via the p
+     * (i.e., principals) member.
+     */
+    private class GetPrincipals implements DfsFcn {
+        public Collection<Role> p;
+
+        public GetPrincipals(Collection<Role> vc) {
+            if ( vc != null) { p =vc;}
+            else { p = new HashSet<Role>(); }
+        }
+
+        public void node(Role r) {
+            if ( r.is_principal() ) p.add(r);
+        }
+        public void node_after(Role r) { }
+    }
+
+    /**
+     * Collect a subgraph.  Add every node and outgoing arc we encounter, and
+     * pull in the linking node subtrees as well.  Because it's possible that
+     * linking node subtrees have been encountered more than once, we're
+     * careful not to pull them in twice.  The created graph is found in the
+     * public ng member.
+     */
+    private class CollectQueryGraph implements DfsFcn {
+        public Graph<Role, Credential> ng;
+        protected HashSet<Role> linking_roles_seen;
+
+        public CollectQueryGraph(Graph<Role,Credential> g) {
+            ng = g;
+            linking_roles_seen = new HashSet<Role>();
+        }
+
+        public void node(Role r) {
+            if (r.is_linking() && !linking_roles_seen.contains(r)) {
+                // Collect this linking role subgraph
+                reverse_dfs(new Role(r.principal_part()), this);
+                linking_roles_seen.add(r);
+            }
+            // Add this node's children
+            for (Credential c : g.getInEdges(r) ) {
+                Role tail = g.getSource(c);
+                ng.addEdge(c, tail, r); // FIXME tail and r can come from c [?]
+            }
+        }
+        public void node_after(Role r) { }
+
+    }
+
+    /**
+     * Collect the path from one node to another. It only includes vertices that
+     * are traversed to reach the node. It also includes subgraphs that imply
+     * the linking edges traversed.
+     */
+    private class CollectQueryPath extends CollectQueryGraph {
+        HashSet<Role> onPath;     // Vertices on the path to the principal
+        public CollectQueryPath(Graph<Role,Credential> g, Role dest) {
+            super(g);
+            onPath = new HashSet<Role>();
+            onPath.add(dest);
+        }
+
+        public void node(Role r) { }
+
+        public void node_after(Role r) {
+            for (Credential c : g.getInEdges(r)) {
+                Role child = c.tail();
+
+                if (onPath.contains(child)) {
+                    Credential edge = g.findEdge(child, r);
+                    if (edge == null)
+                        throw new RuntimeException("Credential missing from parent graph, state is messed up");
+
+                    ng.addEdge(edge, child, r);
+                    onPath.add(r);
+
+                    // For linking roles, collect the whole subgraph of the
+                    // authorizer
+                    if (r.is_linking()) {
+                        CollectQueryPath link = new CollectQueryPath(ng, new Role(child.principal_part()));
+                        reverse_dfs(new Role(r.principal_part()), link);
+                    }
+                }
+            }
+        }
+    }
+
+    /**
+     * Collect the path that a node can reach. It includes subgraphs that imply
+     * the linked edges traversed.
+     */
+    private class CollectReversePath extends CollectQueryGraph {
+        public CollectReversePath(Graph<Role,Credential> g) {
+            super(g);
+        }
+
+        /* add all of the node's parents */
+        public void node(Role r) {
+            for (Credential c : g.getOutEdges(r)) {
+                Role head = g.getDest(c);
+                Credential cred = g.findEdge(r, head);
+                if (cred == null)
+                    throw new RuntimeException("Credential missing from parent graph, state is messed up");
+
+                ng.addEdge(cred, r, head);
+            }
+        }
+
+        public void node_after(Role r) {
+            for (Credential c : g.getOutEdges(r)) {
+                Role parent = g.getDest(c);
+
+                // if any of the links we follow is derived, copy the subgraph
+                // that implies said link
+                if (parent.is_linking()) {
+                    CollectQueryPath link = new CollectQueryPath(ng, new Role(r.principal_part()));
+                    reverse_dfs(new Role(parent.principal_part()), link);
+                }
+            }
+        }
+    }
+
+    /**
+     * Interface to the reverse_dfs member that does allocates the visited map
+     * so the user doesn't have to.
+     * */
+    private void reverse_dfs(Role r, DfsFcn f) {
+        reverse_dfs(r, new HashSet<Role>(), f);
+    }
+
+    /**
+     * Member function to walk the edges in reverse from a given Role.  Each
+     * Role is visited once and has the node() function of the dfs_fcn called
+     * on it.  Order is not guaranteed.
+     */
+    private void reverse_dfs(Role r, HashSet<Role> visited,
+            DfsFcn f) {
+        if (visited.contains(r)) return;
+
+        f.node(r);
+        visited.add(r);
+
+        for (Credential c : g.getInEdges(r)) 
+            reverse_dfs(g.getSource(c), visited, f);
+        f.node_after(r);
+    }
+
+    /**
+     * Interface to the forward_dfs member that allocates the visited map so
+     * the user doesn't have to.
+     */
+    private void forward_dfs(Role r, DfsFcn f) {
+        forward_dfs(r, new HashSet<Role>(), f);
+    }
+
+    /**
+     * Member function to walk the edges from a given Role. Each Role is
+     * visited once and has the node() function of the dfs_fcn called on it.
+     * Order is not guaranteed
+     */
+    private void forward_dfs(Role r, Set<Role> visited, DfsFcn f) {
+        if (visited.contains(r)) return;
+
+        f.node(r);
+        visited.add(r);
+
+        for (Credential c : g.getOutEdges(r))
+            forward_dfs(g.getDest(c), visited, f);
+        f.node_after(r);
+    }
+}
Index: java/net/deterlab/abac/Role.java
===================================================================
--- java/net/deterlab/abac/Role.java	(revision 31b67d5cfd00ac323a7f60b4ba8c4e1567187bdb)
+++ java/net/deterlab/abac/Role.java	(revision 31b67d5cfd00ac323a7f60b4ba8c4e1567187bdb)
@@ -0,0 +1,106 @@
+package net.deterlab.abac;
+
+/**
+ * Represents a role, which is a vertex in a Credential graph.
+ */
+public class Role {
+    private String m_string;
+    private String[] m_parts;
+    private String m_A_r1, m_r2;
+    private String m_prefix;
+
+    /**
+     * Create a role from a string. The string 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.
+     */
+    public Role(String s) throws RuntimeException {
+        m_string = s;
+
+        m_parts = s.split("\\.");
+        if (m_parts.length > 3)
+            throw new RuntimeException("Not a valid role: " + m_string);
+
+        // linking role: prefix is A.r1 from A.r1.r2
+        if (is_linking()) {
+            m_A_r1 = m_parts[0] + "." + m_parts[1];
+            m_r2 = m_parts[2];
+            m_prefix = m_A_r1;
+        }
+
+        // role: prefix is A from A.r1
+        else if (is_role())
+            m_prefix = m_parts[0];
+
+        // principal: prefix is the whole thing
+        else
+            m_prefix = m_string;
+    }
+
+    /**
+     * Returns true iff the role is a principal.
+     */
+    public boolean is_principal() { return m_parts.length == 1; }
+
+    /**
+     * Returns true iff the role is a role (i.e., A.r1).
+     */
+    public boolean is_role() { return m_parts.length == 2; }
+
+    /**
+     * Returns true iff the role is a linking role (i.e., A.r1.r2).
+     */
+    public boolean is_linking() { return m_parts.length == 3; }
+
+    /**
+     * Returns the first two elements of a linking role's name. This typically
+     * refers to another role in the graph. This will throw a runtime
+     * exception if the node is not a linking role.
+     */
+    public String A_r1() throws RuntimeException {
+        if (!is_linking())
+            throw new RuntimeException("Not a linking role");
+        return m_A_r1;
+    }
+
+    /**
+     * Return the last element of a linking role's name. This will throw a
+     * runtime exception if the node is not a linking role.
+     */
+    public String r2() throws RuntimeException {
+        if (!is_linking())
+            throw new RuntimeException("Not a linking role");
+        return m_r2;
+    }
+
+    /**
+     * Returns the principal part of a role or principal. This is everything
+     * except the last element of the name.
+     */
+    public String principal_part() {
+        return m_prefix;
+    }
+
+    /**
+     * Returns true if the principal part of the name matches a prefix. This
+     * is used when filtering graphs.
+     */
+    public boolean matches(String prefix) {
+        return prefix.length() == 0 || m_prefix.equals(prefix);
+    }
+
+    public String toString() {
+        return m_string;
+    }
+
+    public boolean equals(Object v2) {
+        if (v2 instanceof Role)
+            return m_string.equals(((Role)v2).m_string);
+        return false;
+    }
+
+    public int hashCode() {
+        return m_string.hashCode();
+    }
+}
Index: java/simple.rt0
===================================================================
--- java/simple.rt0	(revision 31b67d5cfd00ac323a7f60b4ba8c4e1567187bdb)
+++ java/simple.rt0	(revision 31b67d5cfd00ac323a7f60b4ba8c4e1567187bdb)
@@ -0,0 +1,14 @@
+# bob 302.0 519.0
+# Emulab.friend 353.0 151.0
+# faber.is_cool 89.0 522.0
+# Emulab.friend.is_cool 100.0 406.0
+# Emulab.create 160.0 244.0
+# Mike 154.0 593.0
+# faber 406.0 226.0
+# Emulab.federant 253.0 351.0
+Emulab.create <- Emulab.friend.is_cool
+faber.is_cool <- Mike
+Emulab.create <- Emulab.federant
+Emulab.friend <- faber
+Emulab.federant <- bob
+Emulab.federant <- Mike
