source: java/net/deterlab/abac/Query.java @ 1a7e6d3

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 = null, principal = null;;

        if (!attr.isEmpty()) attribute = new Role(attr);
        if (!prin.isEmpty()) 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(attribute, collect);
            }
            else {
                if ( g.containsVertex(principal)) {
                    CollectQueryPath  collect = new CollectQueryPath(ret, principal);
                    reverse_dfs(attribute, 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 Set<Role> find_principals(Role n) {
        Set<Role> principals = new HashSet<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 and intersection subtrees as well. Because it's
     * possible that these 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;
        protected HashSet<Role> intersection_roles_seen;

        public CollectQueryGraph(Graph<Role,Credential> g) {
            ng = g;
            linking_roles_seen = new HashSet<Role>();
            intersection_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);
            }

            // collect subgraph for each intersection prereq
            if (r.is_intersection() && !intersection_roles_seen.contains(r)) {
                for (Role prereq : r.prereqs())
                    reverse_dfs(prereq, this);
                intersection_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/intersection 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);
                    }

                    // intersection: collect the subgraph of each prereq
                    else if (r.is_intersection()) {
                        CollectQueryPath prereq_finder = new CollectQueryPath(ng, child);
                        for (Role prereq : r.prereqs())
                            reverse_dfs(prereq, prereq_finder);
                    }
                }
            }
        }
    }

    /**
     * Collect the path that a node can reach. It includes subgraphs that imply
     * the linked/intersection 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 from a linking node, 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);
                }

                // intersection roles do not need to be treated specially
                // because the forward path from the principal will traverse all
                // edges that imply the edge to the intersection node
            }
        }
    }

    /**
     * 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);
    }
}