Changeset b67a7ac


Ignore:
Timestamp:
Mar 26, 2011 1:51:32 PM (8 years ago)
Author:
Ted Faber <faber@…>
Branches:
abac0-leak, abac0-mei, compt_changes, gec13, master, mei-id, mei-rt0-n, mei_rt0, mei_rt2, mei_rt2_fix_1, meiyap-rt1, meiyap1, rt2, tvf-new-xml
Children:
a5cfe93
Parents:
e36ea1d
Message:

Add docs

File:
1 edited

Legend:

Unmodified
Added
Removed
  • java/net/deterlab/abac/Query.java

    r0595372 rb67a7ac  
    1111 * A class for making queries against the graph. It supports direct queries as
    1212 * well as reachability in either direction. See the run method for details.
     13 * @author <a href="http://abac.deterlab.net">ISI ABAC team</a>
     14 * @version 1.3
    1315 */
    1416class Query {
     17    /** Internal graph representation */
    1518    private Graph<Role,Credential> g;
     19    /** Count of vertices in g */
    1620    private int vertex_count;
    1721
     22    /**
     23     * Create a query to be run against the credential graph.
     24     * @param g a Graph represneting the credentials and implicit connections.
     25     */
    1826    public Query(Graph<Role,Credential> g) {
    1927        this.g = g;
     
    2533     * derived edges are involved, the subgraphs that imply those edges are
    2634     * included.
     35     * @param attr a String containing the role to look for
     36     * @param prin a String containing the principal
     37     * @return a Graph with the proof or partial proof.
    2738     */
    2839    public Graph<Role,Credential> run(String attr, String prin) {
     
    6879     * Returns true after running a query that returns a non-empty set of
    6980     * vertices.
     81     * @return a boolean, true after running a query that returns a non-empty
     82     * set of vertices.
    7083     */
    7184    public boolean successful() {
     
    7689     * Returns a collection of principals reachable from a Role when
    7790     * traversing edges in the reverse direction.
     91     * @param n the Role to start from
     92     * @return a Set containinf the principals
    7893     */
    7994    public Set<Role> find_principals(Role n) {
     
    87102
    88103    /**
    89      * Interface to pass to the reverse_dfs class.  The node function gets
    90      * called for every node visited by the dfs.
     104     * Interface to pass to the reverse_dfs class that operates on nodes in the
     105     * graph as part of the depth first search (DFS).
    91106     */
    92107    interface DfsFcn {
     108        /**
     109         * Called when the node is first encountered on the DFS.
     110         * @param x the Role being visited
     111         */
    93112        public void node(Role x);
     113        /**
     114         * Called when all the node's children have been visited on the DFS.
     115         * @param x the Role being visited
     116         */
    94117        public void node_after(Role x);
    95118    }
     
    103126     */
    104127    private class GetPrincipals implements DfsFcn {
     128        /** The principals collected */
    105129        public Collection<Role> p;
    106130
     131        /**
     132         * Initialize the principals collection.
     133         * @param vc the initial collection.  May be null.
     134         */
    107135        public GetPrincipals(Collection<Role> vc) {
    108136            if ( vc != null) { p =vc;}
     
    110138        }
    111139
     140        /**
     141         * Adds principals to the collection, called by the DFS.
     142         * @param r the Role visited.
     143         */
    112144        public void node(Role r) {
    113145            if ( r.is_principal() ) p.add(r);
    114146        }
     147        /**
     148         * Does nothing.
     149         * @param r a Role, a dummy
     150         */
    115151        public void node_after(Role r) { }
    116152    }
     
    124160     */
    125161    private class CollectQueryGraph implements DfsFcn {
     162        /** The subgraph being collected */
    126163        public Graph<Role, Credential> ng;
     164        /** The linking roles already added to the sub-graph */
    127165        protected HashSet<Role> linking_roles_seen;
     166        /** The intersection roles already added to the sub-graph */
    128167        protected HashSet<Role> intersection_roles_seen;
    129168
     169        /**
     170         * Initialize the graph into which to gather nodes/edges.
     171         * @param g A graph to collect
     172         */
    130173        public CollectQueryGraph(Graph<Role,Credential> g) {
    131174            ng = g;
     
    134177        }
    135178
     179
     180        /**
     181         * Do the collection on each node we visit.
     182         * @param r a Role, the current node in the DFS.
     183         */
    136184        public void node(Role r) {
    137185            if (r.is_linking() && !linking_roles_seen.contains(r)) {
     
    154202            }
    155203        }
     204        /**
     205         * Does nothing.
     206         * @param r a Role, a dummy
     207         */
    156208        public void node_after(Role r) { }
    157209
     
    159211
    160212    /**
    161      * Collect the path from one node to another. It only includes vertices that
     213     * Collect the path from one node to another. It includes vertices that
    162214     * are traversed to reach the node. It also includes subgraphs that imply
    163215     * the linking/intersection edges traversed.
    164216     */
    165217    private class CollectQueryPath extends CollectQueryGraph {
    166         HashSet<Role> onPath;     // Vertices on the path to the principal
     218        /** Vertices on the path to the principal */
     219        HashSet<Role> onPath;
     220        /**
     221         * Establish the collection graph and the destination.
     222         * @param g the graph that collects the result
     223         * @param dest the Role to find
     224         */
    167225        public CollectQueryPath(Graph<Role,Credential> g, Role dest) {
    168226            super(g);
     
    171229        }
    172230
     231        /**
     232         * Does nothing.
     233         * @param r a Role, a dummy
     234         */
    173235        public void node(Role r) { }
    174236
     237        /**
     238         * Do the collection on each node we visit.
     239         * @param r a Role, the current node in the DFS.
     240         */
    175241        public void node_after(Role r) {
    176242            for (Credential c : g.getInEdges(r)) {
     
    180246                    Credential edge = g.findEdge(child, r);
    181247                    if (edge == null)
    182                         throw new RuntimeException("Credential missing from parent graph, state is messed up");
     248                        throw new RuntimeException("Credential missing from " +
     249                                "parent graph, state is messed up");
    183250
    184251                    ng.addEdge(edge, child, r);
     
    188255                    // authorizer
    189256                    if (r.is_linking()) {
    190                         CollectQueryPath link = new CollectQueryPath(ng, new Role(child.principal_part()));
     257                        CollectQueryPath link = new CollectQueryPath(ng,
     258                                new Role(child.principal_part()));
    191259                        reverse_dfs(new Role(r.principal_part()), link);
    192260                    }
     
    194262                    // intersection: collect the subgraph of each prereq
    195263                    else if (r.is_intersection()) {
    196                         CollectQueryPath prereq_finder = new CollectQueryPath(ng, child);
     264                        CollectQueryPath prereq_finder =
     265                            new CollectQueryPath(ng, child);
    197266                        for (Role prereq : r.prereqs())
    198267                            reverse_dfs(prereq, prereq_finder);
     
    208277     */
    209278    private class CollectReversePath extends CollectQueryGraph {
     279        /**
     280         * Initialize the collection graph.
     281         * @param g a Graph that collects the results.
     282         */
    210283        public CollectReversePath(Graph<Role,Credential> g) {
    211284            super(g);
    212285        }
    213286
    214         /* add all of the node's parents */
     287        /**
     288         * add all of the node's parents
     289         * @param r a Role, the current node being visited
     290         */
    215291        public void node(Role r) {
    216292            for (Credential c : g.getOutEdges(r)) {
     
    218294                Credential cred = g.findEdge(r, head);
    219295                if (cred == null)
    220                     throw new RuntimeException("Credential missing from parent graph, state is messed up");
     296                    throw new RuntimeException("Credential missing from " +
     297                            "parent graph, state is messed up");
    221298
    222299                ng.addEdge(cred, r, head);
     
    224301        }
    225302
     303        /**
     304         * Do the collection on each node we visit.
     305         * @param r a Role, the current node in the DFS.
     306         */
    226307        public void node_after(Role r) {
    227308            for (Credential c : g.getOutEdges(r)) {
     
    231312                // the subgraph that implies said link
    232313                if (parent.is_linking()) {
    233                     CollectQueryPath link = new CollectQueryPath(ng, new Role(r.principal_part()));
     314                    CollectQueryPath link = new CollectQueryPath(ng,
     315                            new Role(r.principal_part()));
    234316                    reverse_dfs(new Role(parent.principal_part()), link);
    235317                }
     
    245327     * Interface to the reverse_dfs member that does allocates the visited map
    246328     * so the user doesn't have to.
    247      * */
     329     * @param r a Role from which to start the search
     330     * @param f a DfsFcn that customizes the search operation
     331     */
    248332    private void reverse_dfs(Role r, DfsFcn f) {
    249333        reverse_dfs(r, new HashSet<Role>(), f);
     
    254338     * Role is visited once and has the node() function of the dfs_fcn called
    255339     * on it.  Order is not guaranteed.
     340     * @param r a Role from which to start the search
     341     * @param visited a HashSet of Roles that tells which nodes have been
     342     * visited.
     343     * @param f a DfsFcn that customizes the search operation
    256344     */
    257345    private void reverse_dfs(Role r, HashSet<Role> visited,
     
    270358     * Interface to the forward_dfs member that allocates the visited map so
    271359     * the user doesn't have to.
     360     * @param r a Role from which to start the search
     361     * @param f a DfsFcn that customizes the search operation
    272362     */
    273363    private void forward_dfs(Role r, DfsFcn f) {
     
    279369     * visited once and has the node() function of the dfs_fcn called on it.
    280370     * Order is not guaranteed
     371     * @param r a Role from which to start the search
     372     * @param visited a HashSet of Roles that tells which nodes have been
     373     * visited.
     374     * @param f a DfsFcn that customizes the search operation
    281375     */
    282376    private void forward_dfs(Role r, Set<Role> visited, DfsFcn f) {
Note: See TracChangeset for help on using the changeset viewer.