source: java/net/deterlab/abac/CredentialGraph.java @ cb6b61d

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<Role,Credential> g = null;
    protected java.util.Set<Credential> derived_edges = new HashSet<Credential>();
    protected Query pq;
    protected boolean m_dirty;

    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. 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<Credential> credentials() {
        Collection<Credential> creds = new HashSet<Credential>();

        // 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<Role> 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<Role> principals = null;

                for (Role prereq : vertex.prereqs()) {
                    Set<Role> 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<Credential>();
    }
}