path: root/libapol/src/infoflow-analysis.c

/**
 * @file
 * Implementation of the information flow analysis.
 *
 *  @author Jeremy A. Mowery jmowery@tresys.com
 *  @author Jason Tang jtang@tresys.com
 *
 *  Copyright (C) 2003-2007 Tresys Technology, LLC
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2.1 of the License, or (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */

#include "policy-query-internal.h"
#include "infoflow-analysis-internal.h"
#include "queue.h"
#include <apol/bst.h>
#include <apol/perm-map.h>

#include <assert.h>
#include <config.h>
#include <errno.h>
#include <limits.h>
#include <time.h>

/*
 * Nodes in the graph represent either a type used in the source
 * of an allow rule or the target: these defines are used to
 * represent which.
 */
#define APOL_INFOFLOW_NODE_SOURCE 0x1
#define APOL_INFOFLOW_NODE_TARGET 0x2

/*
 * These defines are used to color nodes in the graph algorithms.
 */
#define APOL_INFOFLOW_COLOR_WHITE 0
#define APOL_INFOFLOW_COLOR_GREY  1
#define APOL_INFOFLOW_COLOR_BLACK 2
#define APOL_INFOFLOW_COLOR_RED   3

typedef struct apol_infoflow_node apol_infoflow_node_t;
typedef struct apol_infoflow_edge apol_infoflow_edge_t;

struct apol_infoflow_graph
{
	/** vector of apol_infoflow_node_t */
	apol_vector_t *nodes;
	/** vector of apol_infoflow_edge_t */
	apol_vector_t *edges;
	/** temporary BST of apol_infoflow_node_t used while building
         *  the graph */
	apol_bst_t *nodes_bst;

	unsigned int mode, direction;
	regex_t *regex;

	/** vector of apol_infoflow_node_t, used for random restarts
	 * for further transitive analysis */
	apol_vector_t *further_start;
	/** vector of apol_infoflow_node_t of targets, used for
	 * further transitive analysis */
	apol_vector_t *further_end;
	size_t current_start;
#ifdef HAVE_RAND_R
	unsigned int seed;
#endif
};

struct apol_infoflow_node
{
	const qpol_type_t *type;
	/** one of APOL_INFOFLOW_NODE_SOURCE or APOL_INFOFLOW_NODE_TARGET */
	int node_type;
	/** vector of apol_infoflow_edge_t, pointing into the graph */
	apol_vector_t *in_edges;
	/** vector of apol_infoflow_edge_t, pointing into the graph */
	apol_vector_t *out_edges;
	unsigned char color;
	apol_infoflow_node_t *parent;
	int distance;
};

struct apol_infoflow_edge
{
	/** vector of qpol_avrule_t, pointing into the policy */
	apol_vector_t *rules;
	/** pointer into a node within the graph */
	apol_infoflow_node_t *start_node;
	/** pointer into a node within the graph */
	apol_infoflow_node_t *end_node;
	int length;
};

/**
 * apol_infoflow_analysis_h encapsulates all of the paramaters of a
 * query.  It should always be allocated with
 * apol_infoflow_analysis_create() and deallocated with
 * apol_infoflow_analysis_destroy().  Limiting by ending_types,
 * obj_classes, intermed types, obj_class permissions is optional - if
 * the vector is empty then no limiting is done.
 *
 * All of the vectors except end_types should contain the items that
 * you want to not appear in the results.  end_types lists the types
 * that you do want to appear.
 */
struct apol_infoflow_analysis
{
	unsigned int mode, direction;
	char *type, *result;
	apol_vector_t *intermed, *class_perms;
	int min_weight;
};

/**
 * The results of running an infoflow, either direct or transitive, is
 * a path from start_type to end_type.  The path consists of a vector
 * of intermediate steps.
 */
struct apol_infoflow_result
{
	const qpol_type_t *start_type, *end_type;
	/** vector of apol_infoflow_step_t */
	apol_vector_t *steps;
	unsigned int direction;
	unsigned int length;
};

/**
 * Each result consists of multiple steps, representing the steps
 * taken from the original start to end types.  Along each step there
 * is a vector of rules.  For a direct infoflow analysis there will be
 * exactly one step, and that flow's start type is the same as the
 * original result's start_type.  Likewise the end_types will be the
 * same.
 */
struct apol_infoflow_step
{
	const qpol_type_t *start_type, *end_type;
	/** vector of qpol_avrule_t */
	apol_vector_t *rules;
	int weight;
};

/**
 * Deallocate all space associated with an apol_infoflow_step_t,
 * including the pointer itself.  Does nothing if the pointer is
 * already NULL.
 *
 * @param step Infoflow step to free.
 */
static void apol_infoflow_step_free(void *step)
{
	if (step != NULL) {
		apol_infoflow_step_t *s = (apol_infoflow_step_t *) step;
		apol_vector_destroy(&s->rules);
		free(s);
	}
}

/******************** random number routines ********************/

/**
 * Initialize the pseudo-random number generator to be used during
 * further transitive analysis.
 *
 * @param g Transitive infoflow graph.
 */
static void apol_infoflow_srand(apol_infoflow_graph_t * g)
{
#ifdef HAVE_RAND_R
	g->seed = (int)time(NULL);
#else
	srand((int)time(NULL));
#endif
}

/**
 * Return a pseudo-random integer between 0 and RAND_MAX, for use
 * during further transitive analysis.  If the system supports it,
 * this function will use rand_r() so that this library remains
 * reentrant and thread-safe.
 *
 * @param g Transitive infoflow graph.
 *
 * @return Integer between 0 and RAND_MAX.
 */
static int apol_infoflow_rand(apol_infoflow_graph_t * g)
{
#ifdef HAVE_RAND_R
	return rand_r(&g->seed);
#else
	return rand();
#endif
}

/******************** infoflow graph node routines ********************/

/**
 * Given a pointer to an apol_infoflow_node_t, free its space
 * including the pointer itself.  Does nothing if the pointer is
 * already NULL.
 *
 * @param data Node to free.
 */
static void apol_infoflow_node_free(void *data)
{
	apol_infoflow_node_t *node = (apol_infoflow_node_t *) data;
	if (node != NULL) {
		/* the edges themselves are owned by the graph, not by
		 * the node */
		apol_vector_destroy(&node->in_edges);
		apol_vector_destroy(&node->out_edges);
		free(node);
	}
}

struct apol_infoflow_node_key
{
	const qpol_type_t *type;
	int node_type;
};

/**
 * Given an infoflow node and a key, returns 0 if they are the same,
 * non-zero if not.
 *
 * @param a Existing node within the infoflow graph.
 * @param b <i>Unused.</i>
 * @param data Pointer to a struct infoflow_node_key.
 *
 * @return 0 if the key matches a, non-zero if not.
 */
static int apol_infoflow_node_compare(const void *a, const void *b __attribute__ ((unused)), void *data)
{
	apol_infoflow_node_t *node = (apol_infoflow_node_t *) a;
	struct apol_infoflow_node_key *key = (struct apol_infoflow_node_key *)data;
	if (node->type != key->type) {
		return (int)((char *)node->type - (char *)key->type);
	}
	return node->node_type - key->node_type;
}

/**
 * Attempt to allocate a new node, add it to the infoflow graph, and
 * return a pointer to it.  If there already exists a node with the
 * same type then reuse that node.
 *
 * @param p Policy handler, for reporting error.
 * @param g Infoflow to which add the node.
 * @param type Type for the new node.
 * @param node_type Node type, one of APOL_INFOFLOW_NODE_SOURCE or
 * APOL_INFOFLOW_NODE_TARGET.
 *
 * @return Pointer an allocated node within the infoflow graph, or
 * NULL upon error.
 */
static apol_infoflow_node_t *apol_infoflow_graph_create_node(const apol_policy_t * p,
							     apol_infoflow_graph_t * g, const qpol_type_t * type, int node_type)
{
	struct apol_infoflow_node_key key = { type, node_type };
	apol_infoflow_node_t *node = NULL;
	if (apol_bst_get_element(g->nodes_bst, NULL, &key, (void **)&node) == 0) {
		return node;
	}
	if ((node = calloc(1, sizeof(*node))) == NULL ||
	    (node->in_edges = apol_vector_create(NULL)) == NULL || (node->out_edges = apol_vector_create(NULL)) == NULL) {
		ERR(p, "%s", strerror(errno));
		apol_infoflow_node_free(node);
		return NULL;
	}
	node->type = type;
	node->node_type = node_type;
	if (apol_bst_insert(g->nodes_bst, node, &key) != 0) {
		ERR(p, "%s", strerror(errno));
		apol_infoflow_node_free(node);
		return NULL;
	}
	return node;
}

/**
 * Attempt to allocate a new node, add it to the infoflow graph, and
 * return a pointer to it.  If there already exists a node with the
 * same type then reuse that node.
 *
 * @param p Policy handler, for reporting error.
 * @param g Infoflow to which add the node.
 * @param type Type for the new node.  If this is an attribute then it
 * will be expanded into its component types.
 * @param types If non-NULL, a BST of qpol_type_t pointers.  Only
 * create and return nodes which are members of this tree.
 * @param node_type Node type, one of APOL_INFOFLOW_NODE_SOURCE or
 * APOL_INFOFLOW_NODE_TARGET.
 *
 * @return Vector of nodes (type apol_infoflow_node_t *) within the
 * infoflow graph, or NULL upon error.  The caller is responsible for
 * calling apol_vector_destroy() upon the return value.
 */
static apol_vector_t *apol_infoflow_graph_create_nodes(const apol_policy_t * p,
						       apol_infoflow_graph_t * g, const qpol_type_t * type, apol_bst_t * types,
						       int node_type)
{
	unsigned char isattr;
	apol_vector_t *v = NULL;
	apol_infoflow_node_t *node = NULL;
	if (qpol_type_get_isattr(p->p, type, &isattr) < 0) {
		return NULL;
	}
	if (isattr && g->mode != APOL_INFOFLOW_MODE_DIRECT) {
		qpol_iterator_t *iter = NULL;
		qpol_type_t *t;
		size_t len;
		if (qpol_type_get_type_iter(p->p, type, &iter) < 0 ||
		    qpol_iterator_get_size(iter, &len) < 0 || (v = apol_vector_create_with_capacity(len, NULL)) == NULL) {
			qpol_iterator_destroy(&iter);
			apol_vector_destroy(&v);
			return NULL;
		}
		for (; !qpol_iterator_end(iter); qpol_iterator_next(iter)) {
			qpol_iterator_get_item(iter, (void **)&t);
			void *result;
			if (types != NULL && apol_bst_get_element(types, t, NULL, &result) < 0) {
				continue;
			}
			if ((node = apol_infoflow_graph_create_node(p, g, t, node_type)) == NULL || apol_vector_append(v, node) < 0) {
				qpol_iterator_destroy(&iter);
				apol_vector_destroy(&v);
				return NULL;
			}
		}
		qpol_iterator_destroy(&iter);
	} else {
		/* for a direct search, do not expand types; the
		 * algorithm will do that with
		 * apol_infoflow_graph_get_nodes_for_type() and
		 * apol_infoflow_analysis_direct_expand().  for
		 * transitive searches the \a types BST was checked in
		 * apol_infoflow_graph_check_types() if \a type is
		 * just a type.
		 */
		if ((v = apol_vector_create_with_capacity(1, NULL)) == NULL) {
			return NULL;
		}
		if ((node = apol_infoflow_graph_create_node(p, g, type, node_type)) == NULL || apol_vector_append(v, node) < 0) {
			apol_vector_destroy(&v);
			return NULL;
		}
	}
	return v;
}

/******************** infoflow graph edge routines ********************/

/**
 * Given a pointer to an apol_infoflow_edge_t, free its space
 * including the pointer itself.  Does nothing if the pointer is
 * already NULL.
 *
 * @param data Edge to free.
 */
static void apol_infoflow_edge_free(void *data)
{
	apol_infoflow_edge_t *edge = (apol_infoflow_edge_t *) data;
	if (edge != NULL) {
		apol_vector_destroy(&edge->rules);
		free(edge);
	}
}

struct apol_infoflow_edge_key
{
	apol_infoflow_node_t *start_node, *end_node;
};

/**
 * Given an infoflow edge and a key, returns 0 if they are the same,
 * non-zero if not.
 *
 * @param a Existing edge within the infoflow graph.
 * @param b <i>Unused.</i>
 * @param data Pointer to a struct infoflow_edge_key.
 *
 * @return 0 if the key matches a, non-zero if not.
 */
static int apol_infoflow_edge_compare(const void *a, const void *b __attribute__ ((unused)), void *data)
{
	apol_infoflow_edge_t *edge = (apol_infoflow_edge_t *) a;
	struct apol_infoflow_edge_key *key = (struct apol_infoflow_edge_key *)data;
	if (key->start_node != NULL && edge->start_node != key->start_node) {
		return (int)((char *)edge->start_node - (char *)key->start_node);
	}
	if (key->end_node != NULL && edge->end_node != key->end_node) {
		return (int)((char *)edge->end_node - (char *)key->end_node);
	}
	return 0;
}

/**
 * Attempt to allocate a new edge, add it to the infoflow graph, and
 * return a pointer to it.  If there already exists a edge from the
 * start node to the end node then reuse that edge.
 *
 * @param p Policy handler, for reporting errors.
 * @param g Infoflow graph to which add the edge.
 * @param start_node Starting node for the edge.
 * @param end_node Ending node for the edge.
 * @param len Length of edge (proportionally inverse of permission weight)
 *
 * @return Pointer an allocated node within the infoflow graph, or
 * NULL upon error.
 */
static apol_infoflow_edge_t *apol_infoflow_graph_create_edge(const apol_policy_t * p,
							     apol_infoflow_graph_t * g __attribute__ ((unused)),
							     apol_infoflow_node_t * start_node,
							     apol_infoflow_node_t * end_node, int len)
{
	struct apol_infoflow_edge_key key = { NULL, end_node };
	size_t i;
	apol_infoflow_edge_t *edge = NULL;
	if (apol_vector_get_index(start_node->out_edges, NULL, apol_infoflow_edge_compare, &key, &i) == 0) {
		edge = (apol_infoflow_edge_t *) apol_vector_get_element(start_node->out_edges, i);
		if (edge->length < len) {
			edge->length = len;
		}
		return edge;
	}
	if ((edge = calloc(1, sizeof(*edge))) == NULL || (edge->rules = apol_vector_create(NULL)) == NULL ||
	    apol_vector_append(g->edges, edge) < 0) {
		ERR(p, "%s", strerror(errno));
		apol_infoflow_edge_free(edge);
		return NULL;
	}
	edge->start_node = start_node;
	edge->end_node = end_node;
	edge->length = len;
	if (apol_vector_append(start_node->out_edges, edge) < 0 || apol_vector_append(end_node->in_edges, edge) < 0) {
		/* don't free the edge -- it is owned by the graph */
		ERR(p, "%s", strerror(errno));
		return NULL;
	}
	return edge;
}

/******************** infoflow graph creation routines ********************/

/**
 * Take an avrule within a policy and possibly add it to the infoflow
 * graph.  The rule's source and target type sets are expanded.  If
 * the rule is to be added, then add its end nodes as necessary, and
 * an edge connecting those nodes as necessary, and then add the rule
 * to the edge.
 *
 * @param p Policy containing rules.
 * @param g Information flow graph being created.
 * @param rule AV rule to use.
 * @param types BST of qpol_type_t pointers; while adding avrules to
 * the graph, only add those whose source and/or target is a member of
 * \a types, if \a types is non-NULL.
 * @param found_read Non-zero to indicate that this rule performs a
 * read operation.
 * @param read_len Length of the edge to create (proportionally
 * inverse of permission weight).
 * @param found_write Non-zero to indicate that this rule performs a
 * write operation.
 * @param write_len Length of the edge to create (proportionally
 * inverse of permission weight).
 *
 * @return 0 on success, < 0 on error.
 */
static int apol_infoflow_graph_connect_nodes(const apol_policy_t * p,
					     apol_infoflow_graph_t * g,
					     const qpol_avrule_t * rule,
					     apol_bst_t * types, int found_read, int read_len, int found_write, int write_len)
{
	const qpol_type_t *src_type, *tgt_type;
	apol_vector_t *src_nodes = NULL, *tgt_nodes = NULL;
	size_t i, j;
	apol_infoflow_node_t *src_node, *tgt_node;
	apol_infoflow_edge_t *edge;
	int retval = -1;

	if (qpol_avrule_get_source_type(p->p, rule, &src_type) < 0 || qpol_avrule_get_target_type(p->p, rule, &tgt_type) < 0) {
		goto cleanup;
	}

	if ((src_nodes = apol_infoflow_graph_create_nodes(p, g, src_type, types, APOL_INFOFLOW_NODE_SOURCE)) == NULL) {
		goto cleanup;
	}
	if ((tgt_nodes = apol_infoflow_graph_create_nodes(p, g, tgt_type, types, APOL_INFOFLOW_NODE_TARGET)) == NULL) {
		goto cleanup;
	}
	for (i = 0; i < apol_vector_get_size(src_nodes); i++) {
		src_node = apol_vector_get_element(src_nodes, i);
		for (j = 0; j < apol_vector_get_size(tgt_nodes); j++) {
			tgt_node = apol_vector_get_element(tgt_nodes, j);
			if (found_read) {
				if ((edge = apol_infoflow_graph_create_edge(p, g, tgt_node, src_node, read_len)) == NULL) {
					goto cleanup;
				}
				if (apol_vector_append(edge->rules, (void *)rule) < 0) {
					ERR(p, "%s", strerror(ENOMEM));
					goto cleanup;
				}
			}
			if (found_write) {
				if ((edge = apol_infoflow_graph_create_edge(p, g, src_node, tgt_node, write_len)) == NULL) {
					goto cleanup;
				}
				if (apol_vector_append(edge->rules, (void *)rule) < 0) {
					ERR(p, "%s", strerror(ENOMEM));
					goto cleanup;
				}
			}
		}
	}
	retval = 0;
      cleanup:
	apol_vector_destroy(&src_nodes);
	apol_vector_destroy(&tgt_nodes);
	return retval;
}

/**
 * Given a policy and a partially completed infoflow graph, create the
 * nodes and edges associated with a particular rule.
 *
 * @param p Policy from which to create the infoflow graph.
 * @param g Infoflow graph being created.
 * @param rule AV rule to add.
 * @param types BST of qpol_type_t pointers; while adding avrules to
 * the graph, only add those whose source and/or target is a member of
 * \a types, if \a types is non-NULL.
 * @param max_len Maximum permission length (i.e., inverse of
 * permission weight) to consider when deciding to add this rule or
 * not.
 *
 * @return 0 on success, < 0 on error.
 */
static int apol_infoflow_graph_create_avrule(const apol_policy_t * p, apol_infoflow_graph_t * g, const qpol_avrule_t * rule,
					     apol_bst_t * types, int max_len)
{
	const qpol_class_t *obj_class;
	qpol_iterator_t *perm_iter = NULL;
	const char *obj_class_name;
	char *perm_name;
	int found_read = 0, found_write = 0, perm_error = 0;
	int read_len = INT_MAX, write_len = INT_MAX;
	int retval = -1;
	if (qpol_avrule_get_object_class(p->p, rule, &obj_class) < 0 ||
	    qpol_class_get_name(p->p, obj_class, &obj_class_name) < 0 || qpol_avrule_get_perm_iter(p->p, rule, &perm_iter) < 0) {
		goto cleanup;
	}

	/* find read or write flows for each object class/perm pair */
	for (; !qpol_iterator_end(perm_iter); qpol_iterator_next(perm_iter)) {
		int perm_map, perm_weight, len;

		if (qpol_iterator_get_item(perm_iter, (void **)&perm_name) < 0) {
			goto cleanup;
		}
		if (apol_policy_get_permmap(p, obj_class_name, perm_name, &perm_map, &perm_weight) < 0) {
			goto cleanup;
		}
		free(perm_name);
		if (perm_map == APOL_PERMMAP_UNMAPPED) {
			perm_error = 1;
			continue;
		}
		len = APOL_PERMMAP_MAX_WEIGHT - perm_weight + 1;
		if (len < APOL_PERMMAP_MIN_WEIGHT) {
			len = APOL_PERMMAP_MIN_WEIGHT;
		} else if (len > APOL_PERMMAP_MAX_WEIGHT) {
			len = APOL_PERMMAP_MAX_WEIGHT;
		}
		if (perm_map & APOL_PERMMAP_READ) {
			if (len < read_len && len <= max_len) {
				found_read = 1;
				read_len = len;
			}
		}
		if (perm_map & APOL_PERMMAP_WRITE) {
			if (len < write_len && len <= max_len) {
				found_write = 1;
				write_len = len;
			}
		}
	}

	/* if we have found any flows then connect them within the graph */
	if ((found_read || found_write) &&
	    apol_infoflow_graph_connect_nodes(p, g, rule, types, found_read, read_len, found_write, write_len) < 0) {
		goto cleanup;
	}
	if (perm_error) {
		WARN(p, "%s", "Not all of the permissions found had associated permission maps.");
	}

	retval = 0;
      cleanup:
	qpol_iterator_destroy(&perm_iter);
	return retval;
}

/**
 * Given a vector of strings representing types, return a BST of
 * qpol_type_t pointers consisting of those types, those types'
 * attributes, and those types' aliases.
 *
 * @param p Policy within which to look up types,
 * @param v Vector of type strings.
 *
 * @return BST of qpol_type_t pointers, or NULL on error.  The caller
 * is responsible for calling apol_bst_destroy() upon the returned
 * value.
 */
static apol_bst_t *apol_infoflow_graph_create_required_types(const apol_policy_t * p, const apol_vector_t * v)
{
	apol_bst_t *types = NULL;
	apol_vector_t *expanded_types = NULL;
	size_t i;
	char *s;
	int retval = -1;
	if ((types = apol_bst_create(NULL, NULL)) == NULL) {
		ERR(p, "%s", strerror(errno));
		goto cleanup;
	}
	for (i = 0; i < apol_vector_get_size(v); i++) {
		s = (char *)apol_vector_get_element(v, i);
		expanded_types = apol_query_create_candidate_type_list(p, s, 0, 1, APOL_QUERY_SYMBOL_IS_BOTH);
		if (expanded_types == NULL) {
			goto cleanup;
		}
		for (size_t j = 0; j < apol_vector_get_size(expanded_types); j++) {
			qpol_type_t *t = (qpol_type_t *) apol_vector_get_element(expanded_types, j);
			if (apol_bst_insert(types, t, NULL) < 0) {
				ERR(p, "%s", strerror(errno));
				goto cleanup;
			}
		}
		apol_vector_destroy(&expanded_types);
	}
	retval = 0;
      cleanup:
	apol_vector_destroy(&expanded_types);
	if (retval != 0) {
		apol_bst_destroy(&types);
	}
	return types;
}

/**
 * Determine if an av rule matches a list of qpol_type_t pointers.
 * Both the source and target of the rule must be in the list.
 *
 * @param p Policy to which look up classes and permissions.
 * @param rule AV rule to check.
 * @param types BST of qpol_type_t, of which both the source and
 * target types must be members.  If NULL allow all types.
 *
 * @return 1 if rule matches, 0 if not, < 0 on error.
 */
static int apol_infoflow_graph_check_types(const apol_policy_t * p, const qpol_avrule_t * rule, const apol_bst_t * types)
{
	const qpol_type_t *source, *target;
	void *result;
	int retval = -1;
	if (types == NULL) {
		retval = 1;
		goto cleanup;
	}
	if (qpol_avrule_get_source_type(p->p, rule, &source) < 0 || qpol_avrule_get_target_type(p->p, rule, &target) < 0) {
		goto cleanup;
	}
	if (apol_bst_get_element(types, source, NULL, &result) < 0 || apol_bst_get_element(types, target, NULL, &result) < 0) {
		retval = 0;
		goto cleanup;
	}
	retval = 1;
      cleanup:
	return retval;
}

/**
 * Determine if an av rule matches a list of apol_obj_perm_t.  The
 * rule's class must match at least one item in the list, and at least
 * one of the rule's permissions must be on the list.
 *
 * @param p Policy to which look up classes and permissions.
 * @param rule AV rule to check.
 * @param class_perms Vector of apol_obj_perm_t, of which rule's class
 * and permissions must be a member.  If NULL or empty then allow all
 * classes and permissions.
 *
 * @return 1 if rule matches, 0 if not, < 0 on error.
 */
static int apol_infoflow_graph_check_class_perms(const apol_policy_t * p, const qpol_avrule_t * rule,
						 const apol_vector_t * class_perms)
{
	const qpol_class_t *obj_class;
	const char *obj_name;
	char *perm;
	qpol_iterator_t *iter = NULL;
	apol_obj_perm_t *obj_perm = NULL;
	apol_vector_t *obj_perm_v = NULL;
	size_t i;
	int retval = -1;

	if (class_perms == NULL || apol_vector_get_size(class_perms) == 0) {
		retval = 1;
		goto cleanup;
	}
	if (qpol_avrule_get_object_class(p->p, rule, &obj_class) < 0 || qpol_class_get_name(p->p, obj_class, &obj_name) < 0) {
		goto cleanup;
	}
	for (i = 0; i < apol_vector_get_size(class_perms); i++) {
		obj_perm = (apol_obj_perm_t *) apol_vector_get_element(class_perms, i);
		if (strcmp(apol_obj_perm_get_obj_name(obj_perm), obj_name) == 0) {
			obj_perm_v = apol_obj_perm_get_perm_vector(obj_perm);
			break;
		}
	}
	if (i >= apol_vector_get_size(class_perms)) {
		retval = 0;	       /* no matching class */
		goto cleanup;
	}
	if (qpol_avrule_get_perm_iter(p->p, rule, &iter) < 0) {
		goto cleanup;
	}
	for (; !qpol_iterator_end(iter); qpol_iterator_next(iter)) {
		if (qpol_iterator_get_item(iter, (void **)&perm) < 0) {
			goto cleanup;
		}
		if (apol_vector_get_index(obj_perm_v, perm, apol_str_strcmp, NULL, &i) == 0) {
			free(perm);
			retval = 1;
			goto cleanup;
		}
		free(perm);
	}
	retval = 0;		       /* no matching perm */
      cleanup:
	qpol_iterator_destroy(&iter);
	return retval;
}

/**
 * Given a particular information flow analysis object, generate an
 * infoflow graph relative to a particular policy.  This graph is
 * customized for the particular analysis.
 *
 * @param p Policy from which to create the infoflow graph.
 * @param ia Parameters to tune the created graph.
 * @param g Reference to where to store the graph.  The caller is
 * responsible for calling apol_infoflow_graph_destroy() upon this.
 *
 * @return 0 if the graph was created, < 0 on error.  Upon error *g
 * will be set to NULL.
 */
static int apol_infoflow_graph_create(const apol_policy_t * p, const apol_infoflow_analysis_t * ia, apol_infoflow_graph_t ** g)
{
	apol_bst_t *types = NULL;
	qpol_iterator_t *iter = NULL;
	int max_len = APOL_PERMMAP_MAX_WEIGHT - ia->min_weight + 1;
	int compval, retval = -1;

	*g = NULL;
	if (p->pmap == NULL) {
		ERR(p, "%s", "A permission map must be loaded prior to building the infoflow graph.");
		goto cleanup;
	}

	INFO(p, "%s", "Generating information flow graph.");
	if (ia->mode == APOL_INFOFLOW_MODE_TRANS && ia->intermed != NULL &&
	    (types = apol_infoflow_graph_create_required_types(p, ia->intermed)) == NULL) {
		goto cleanup;
	}

	if ((*g = calloc(1, sizeof(**g))) == NULL ||
	    ((*g)->nodes_bst = apol_bst_create(apol_infoflow_node_compare, apol_infoflow_node_free)) == NULL) {
		ERR(p, "%s", strerror(errno));
		goto cleanup;
	}
	(*g)->mode = ia->mode;
	(*g)->direction = ia->direction;
	if (ia->result != NULL && ia->result[0] != '\0') {
		if (((*g)->regex = malloc(sizeof(regex_t))) == NULL || regcomp((*g)->regex, ia->result, REG_EXTENDED | REG_NOSUB)) {
			ERR(p, "%s", strerror(errno));
			goto cleanup;
		}
	}
	if (((*g)->edges = apol_vector_create(apol_infoflow_edge_free)) == NULL) {
		ERR(p, "%s", strerror(errno));
		goto cleanup;
	}

	if (qpol_policy_get_avrule_iter(p->p, QPOL_RULE_ALLOW, &iter) < 0) {
		goto cleanup;
	}

	for (; !qpol_iterator_end(iter); qpol_iterator_next(iter)) {
		qpol_avrule_t *rule;
		if (qpol_iterator_get_item(iter, (void **)&rule) < 0) {
			goto cleanup;
		}
		compval = apol_infoflow_graph_check_types(p, rule, types);
		if (compval < 0) {
			goto cleanup;
		} else if (compval == 0) {
			continue;
		}
		compval = apol_infoflow_graph_check_class_perms(p, rule, ia->class_perms);
		if (compval < 0) {
			goto cleanup;
		} else if (compval == 0) {
			continue;
		}
		if (apol_infoflow_graph_create_avrule(p, *g, rule, types, max_len) < 0) {
			goto cleanup;
		}
	}

	if (((*g)->nodes = apol_bst_get_vector((*g)->nodes_bst, 1)) == NULL) {
		ERR(p, "%s", strerror(errno));
		goto cleanup;
	}
	apol_bst_destroy(&(*g)->nodes_bst);
	retval = 0;
      cleanup:
	apol_bst_destroy(&types);
	qpol_iterator_destroy(&iter);
	if (retval < 0) {
		apol_infoflow_graph_destroy(g);
	}
	return retval;
}

void apol_infoflow_graph_destroy(apol_infoflow_graph_t ** g)
{
	if (g != NULL && *g != NULL) {
		apol_bst_destroy(&(*g)->nodes_bst);
		apol_vector_destroy(&(*g)->nodes);
		apol_vector_destroy(&(*g)->edges);
		apol_vector_destroy(&(*g)->further_start);
		apol_vector_destroy(&(*g)->further_end);
		apol_regex_destroy(&(*g)->regex);
		free(*g);
		*g = NULL;
	}
}

/*************** infoflow graph direct analysis routines ***************/

/**
 * Given a graph and a target type, append to vector v all nodes
 * (apol_infoflow_node_t) within the graph that use that type, one of
 * that type's aliases, or one of that type's attributes.  This will
 * also implicitly permutate across all of the type's object classes.
 *
 * @param p Error reporting handler.
 * @param g Information flow graph containing nodes.
 * @param type Target type name to find.
 * @param v Initialized vector to which append nodes.
 *
 * @return 0 on success, < 0 on error.
 */
static int apol_infoflow_graph_get_nodes_for_type(const apol_policy_t * p, const apol_infoflow_graph_t * g, const char *type,
						  apol_vector_t * v)
{
	size_t i, j;
	apol_vector_t *cand_list = NULL;
	int retval = -1;
	if ((cand_list = apol_query_create_candidate_type_list(p, type, 0, 1, APOL_QUERY_SYMBOL_IS_BOTH)) == NULL) {
		goto cleanup;
	}
	for (i = 0; i < apol_vector_get_size(g->nodes); i++) {
		apol_infoflow_node_t *node;
		node = (apol_infoflow_node_t *) apol_vector_get_element(g->nodes, i);
		if (apol_vector_get_index(cand_list, node->type, NULL, NULL, &j) == 0 && apol_vector_append(v, node) < 0) {
			goto cleanup;
		}
	}
	retval = 0;
      cleanup:
	apol_vector_destroy(&cand_list);
	return retval;
}

/**
 * Return a usable infoflow result object.  If there already exists a
 * result object within vector v with the same start and ending type
 * then reuse that object.  Otherwise allocate and return a new
 * infoflow result with its start and end type fields set.
 *
 * @param p Policy handler, for reporting errors.
 * @param v Non-null vector of infoflow results.
 * @param start_type Starting type for returned infoflow result object.
 * @param end_type Starting type for returned infoflow result object.
 *
 * @return A usable infoflow result object, or NULL upon error.
 */
static apol_infoflow_result_t *apol_infoflow_direct_get_result(const apol_policy_t * p,
							       apol_vector_t * v, const qpol_type_t * start_type,
							       const qpol_type_t * end_type)
{
	size_t i;
	apol_infoflow_result_t *r;
	for (i = 0; i < apol_vector_get_size(v); i++) {
		r = (apol_infoflow_result_t *) apol_vector_get_element(v, i);
		if (r->start_type == start_type && r->end_type == end_type) {
			return r;
		}
	}
	if ((r = calloc(1, sizeof(*r))) == NULL || (r->steps = apol_vector_create(apol_infoflow_step_free)) == NULL
	    || apol_vector_append(v, r) < 0) {
		ERR(p, "%s", strerror(ENOMEM));
		infoflow_result_free(r);
		return NULL;
	}
	r->start_type = start_type;
	r->end_type = end_type;
	r->length = INT_MAX;
	return r;
}

/**
 * Append the rules on an edge to a direct infoflow result.
 *
 * @param p Policy containing rules.
 * @param edge Infoflow edge containing rules.
 * @param direction Direction of flow, one of APOL_INFOFLOW_IN, etc.
 * @param result Infoflow result to modify.
 *
 * @return 0 on success, < 0 on error.
 */
static int apol_infoflow_direct_define(const apol_policy_t * p,
				       const apol_infoflow_edge_t * edge, unsigned int direction, apol_infoflow_result_t * result)
{
	apol_infoflow_step_t *step = NULL;
	if (apol_vector_get_size(result->steps) == 0) {
		if ((step = calloc(1, sizeof(*step))) == NULL ||
		    (step->rules = apol_vector_create(NULL)) == NULL || apol_vector_append(result->steps, step) < 0) {
			apol_infoflow_step_free(step);
			ERR(p, "%s", strerror(ENOMEM));
			return -1;
		}
		step->start_type = result->start_type;
		step->end_type = result->end_type;
		step->weight = 0;
	} else {
		step = (apol_infoflow_step_t *) apol_vector_get_element(result->steps, 0);
	}
	if (apol_vector_cat(step->rules, edge->rules) < 0) {
		ERR(p, "%s", strerror(ENOMEM));
		return -1;
	}
	result->direction |= direction;
	//TODO: check that edge->lenght can be safely unsigned
	if (edge->length < (int)result->length) {
		result->length = edge->length;
	}
	return 0;
}

/**
 * Given the regular expression compiled into the graph object and a
 * type, determine if that regex matches that type or any of the
 * type's aliases.
 *
 * @param p Policy containing type names.
 * @param g Graph object containing regex.
 * @param type Type to check against.
 *
 * @return 1 if comparison succeeds, 0 if not, < 0 on error.
 */
static int apol_infoflow_graph_compare(const apol_policy_t * p, apol_infoflow_graph_t * g, const qpol_type_t * type)
{
	const char *type_name;
	qpol_iterator_t *alias_iter = NULL;
	int compval = 0;
	if (g->regex == NULL) {
		return 1;
	}
	if (qpol_type_get_name(p->p, type, &type_name) < 0) {
		return -1;
	}
	if (regexec(g->regex, type_name, 0, NULL, 0) == 0) {
		return 1;
	}
	/* also check for matches against any of target's aliases */
	if (qpol_type_get_alias_iter(p->p, type, &alias_iter) < 0) {
		return -1;
	}
	for (; !qpol_iterator_end(alias_iter); qpol_iterator_next(alias_iter)) {
		char *iter_name;
		if (qpol_iterator_get_item(alias_iter, (void **)&iter_name) < 0) {
			compval = -1;
			break;
		}
		if (regexec(g->regex, iter_name, 0, NULL, 0) == 0) {
			compval = 1;
			break;
		}
	}
	qpol_iterator_destroy(&alias_iter);
	return compval;
}

/**
 * For each result object in vector working_results, append a
 * duplicate of it to vector results if (a) the infoflow analysis
 * object direction is not BOTH or (b) the result object's direction
 * is BOTH.  Regardless of success or error, it is safe to destroy
 * either vector without concern of double-free()ing things.
 *
 * @param p Policy handler, for reporting errors.
 * @param working_results Vector of infoflow results to check.
 * @param direction Direction of search.
 * @param results Vector to which append duplicated infoflow results.
 *
 * @return 0 on success, < 0 on error.
 */
static int apol_infoflow_results_check_both(const apol_policy_t * p,
					    const apol_vector_t * working_results, unsigned int direction, apol_vector_t * results)
{
	size_t i;
	apol_infoflow_result_t *r, *new_r;
	for (i = 0; i < apol_vector_get_size(working_results); i++) {
		r = (apol_infoflow_result_t *) apol_vector_get_element(working_results, i);
		if (direction != APOL_INFOFLOW_BOTH || r->direction == APOL_INFOFLOW_BOTH) {
			if ((new_r = calloc(1, sizeof(*new_r))) == NULL) {
				ERR(p, "%s", strerror(ENOMEM));
				return -1;
			}
			memcpy(new_r, r, sizeof(*new_r));
			r->steps = NULL;
			if (apol_vector_append(results, new_r) < 0) {
				infoflow_result_free(new_r);
				ERR(p, "%s", strerror(ENOMEM));
				return -1;
			}
		}
	}
	return 0;
}

/**
 * Given a start node, an edge, and flow direction, add an infoflow
 * results to a vector.  If the node on the other end of the edge is
 * an attribute, first expand the attribute to its component types.
 * If a regular expression is compiled into the infoflow graph, apply
 * that regex match against candidate end node types prior to creating
 * result nodes.
 *
 * @param p Policy to analyze.
 * @param g Information flow graph to analyze.
 * @param start_node Starting node.
 * @param edge An edge from start_node.
 * @param flow_dir Direction of search, either APOL_INFOFLOW_IN or
 * APOL_INFOFLOW_OUT.
 * @param results Non-NULL vector to which append infoflow results.
 * The caller is responsible for calling apol_infoflow_results_free()
 * upon each element afterwards.
 *
 * @return 0 on success, < 0 on error.
 */
static int apol_infoflow_analysis_direct_expand(const apol_policy_t * p,
						apol_infoflow_graph_t * g,
						apol_infoflow_node_t * start_node,
						apol_infoflow_edge_t * edge, unsigned int flow_dir, apol_vector_t * results)
{
	apol_infoflow_node_t *end_node;
	unsigned char isattr;
	qpol_iterator_t *iter = NULL;
	const qpol_type_t *type;
	apol_infoflow_result_t *r;
	int retval = -1, compval;

	if (edge->start_node == start_node) {
		end_node = edge->end_node;
	} else {
		end_node = edge->start_node;
	}
	if (qpol_type_get_isattr(p->p, end_node->type, &isattr) < 0) {
		goto cleanup;
	}
	if (isattr) {
		if (qpol_type_get_type_iter(p->p, end_node->type, &iter) < 0) {
			goto cleanup;
		}
		if (qpol_iterator_end(iter)) {
			retval = 0;
			goto cleanup;
		}
	}
	/* always do this loop once, either if end_node is an attribute or not */
	do {
		if (isattr) {
			if (qpol_iterator_get_item(iter, (void **)&type) < 0) {
				goto cleanup;
			}
			qpol_iterator_next(iter);
		} else {
			type = end_node->type;
		}
		compval = apol_infoflow_graph_compare(p, g, type);
		if (compval < 0) {
			goto cleanup;
		} else if (compval == 0) {
			continue;
		}
		if ((r = apol_infoflow_direct_get_result(p, results, start_node->type, type)) == NULL ||
		    apol_infoflow_direct_define(p, edge, flow_dir, r) < 0) {
			goto cleanup;
		}
	} while (isattr && !qpol_iterator_end(iter));

	retval = 0;
      cleanup:
	qpol_iterator_destroy(&iter);
	return retval;
}

/**
 * Perform a direct information flow analysis upon the given infoflow
 * graph.
 *
 * @param p Policy to analyze.
 * @param g Information flow graph to analyze.
 * @param start_type Type from which to begin search.
 * @param results Non-NULL vector to which append infoflow results.
 * The caller is responsible for calling apol_infoflow_results_free()
 * upon each element afterwards.
 *
 * @return 0 on success, < 0 on error.
 */
static int apol_infoflow_analysis_direct(const apol_policy_t * p,
					 apol_infoflow_graph_t * g, const char *start_type, apol_vector_t * results)
{
	apol_vector_t *nodes = NULL;
	size_t i, j;
	apol_infoflow_node_t *node;
	apol_infoflow_edge_t *edge;
	apol_vector_t *working_results = NULL;
	int retval = -1;

	if ((nodes = apol_vector_create(NULL)) == NULL || (working_results = apol_vector_create(infoflow_result_free)) == NULL) {
		ERR(p, "%s", strerror(ENOMEM));
		goto cleanup;
	}
	if (apol_infoflow_graph_get_nodes_for_type(p, g, start_type, nodes) < 0) {
		goto cleanup;
	}

	if (g->direction == APOL_INFOFLOW_IN || g->direction == APOL_INFOFLOW_EITHER || g->direction == APOL_INFOFLOW_BOTH) {
		for (i = 0; i < apol_vector_get_size(nodes); i++) {
			node = (apol_infoflow_node_t *) apol_vector_get_element(nodes, i);
			for (j = 0; j < apol_vector_get_size(node->in_edges); j++) {
				edge = (apol_infoflow_edge_t *) apol_vector_get_element(node->in_edges, j);
				if (apol_infoflow_analysis_direct_expand(p, g, node, edge, APOL_INFOFLOW_IN, working_results) < 0) {
					goto cleanup;
				}
			}
		}
	}
	if (g->direction == APOL_INFOFLOW_OUT || g->direction == APOL_INFOFLOW_EITHER || g->direction == APOL_INFOFLOW_BOTH) {
		for (i = 0; i < apol_vector_get_size(nodes); i++) {
			node = (apol_infoflow_node_t *) apol_vector_get_element(nodes, i);
			for (j = 0; j < apol_vector_get_size(node->out_edges); j++) {
				edge = (apol_infoflow_edge_t *) apol_vector_get_element(node->out_edges, j);
				if (apol_infoflow_analysis_direct_expand(p, g, node, edge, APOL_INFOFLOW_OUT, working_results) < 0) {
					goto cleanup;
				}
			}
		}
	}

	if (apol_infoflow_results_check_both(p, working_results, g->direction, results) < 0) {
		goto cleanup;
	}

	retval = 0;
      cleanup:
	apol_vector_destroy(&nodes);
	apol_vector_destroy(&working_results);
	return retval;
}

/*************** infoflow graph transitive analysis routines ***************/

/**
 * Prepare an infoflow graph for a transitive analysis by coloring its
 * nodes and setting its parent and distance.  For the start node
 * color it red; for all others color them white.
 *
 * @param p Policy handler, for reporting errors.
 * @param g Infoflow graph to initialize.
 * @param start Node from which to begin analysis.
 * @param q Queue of apol_infoflow_node_t pointers to which search.
 *
 * @return 0 on success, < 0 on error.
 */
static int apol_infoflow_graph_trans_init(const apol_policy_t * p,
					  apol_infoflow_graph_t * g, apol_infoflow_node_t * start, apol_queue_t * q)
{
	size_t i;
	apol_infoflow_node_t *node;
	for (i = 0; i < apol_vector_get_size(g->nodes); i++) {
		node = (apol_infoflow_node_t *) apol_vector_get_element(g->nodes, i);
		node->parent = NULL;
		if (node == start) {
			node->color = APOL_INFOFLOW_COLOR_RED;
			node->distance = 0;
			if (apol_queue_insert(q, node) < 0) {
				ERR(p, "%s", strerror(ENOMEM));
				return -1;
			}
		} else {
			node->color = APOL_INFOFLOW_COLOR_WHITE;
			node->distance = INT_MAX;
		}
	}
	return 0;
}

/**
 * Prepare an infoflow graph for furher transitive analysis by
 * coloring its nodes and setting its parent and distance.  For the
 * start node color it grey; for all others color them white.
 *
 * @param p Policy handler, for reporting errors.
 * @param g Infoflow graph to initialize.
 * @param start Node from which to begin analysis.
 * @param q Queue of apol_infoflow_node_t pointers to which search.
 *
 * @return 0 on success, < 0 on error.
 */
static int apol_infoflow_graph_trans_further_init(const apol_policy_t * p,
						  apol_infoflow_graph_t * g, apol_infoflow_node_t * start, apol_queue_t * q)
{
	size_t i;
	apol_infoflow_node_t *node;
	for (i = 0; i < apol_vector_get_size(g->nodes); i++) {
		node = (apol_infoflow_node_t *) apol_vector_get_element(g->nodes, i);
		node->parent = NULL;
		if (node == start) {
			node->color = APOL_INFOFLOW_COLOR_GREY;
			node->distance = 0;
			if (apol_queue_insert(q, node) < 0) {
				ERR(p, "%s", strerror(ENOMEM));
				return -1;
			}
		} else {
			node->color = APOL_INFOFLOW_COLOR_WHITE;
			node->distance = -1;
		}
	}
	return 0;
}

/**
 * Given a colored infoflow graph from apol_infoflow_analysis_trans(),
 * find the shortest path from the end node to the start node.
 * Allocate and return a vector of apol_infoflow_node_t that lists the
 * nodes from the end to start.
 *
 * @param p Policy from which infoflow graph was generated.
 * @param g Infoflow graph that has been colored.
 * @param start_node Starting node for the path
 * @param end_node Ending node to which to find a path.
 * @param path Reference to a vector that will be allocated and filled
 * with apol_infoflow_node_t pointers from the graph.  The path will
 * be in reverse order (i.e., from end node to a start node).  Upon
 * error this will be set to NULL.
 *
 * @return 0 on success, < 0 on error.
 */
static int apol_infoflow_trans_path(const apol_policy_t * p,
				    apol_infoflow_graph_t * g,
				    apol_infoflow_node_t * start_node, apol_infoflow_node_t * end_node, apol_vector_t ** path)
{
	int retval = -1;
	apol_infoflow_node_t *next_node = end_node;
	if ((*path = apol_vector_create(NULL)) == NULL) {
		ERR(p, "%s", strerror(errno));
		goto cleanup;
	}
	while (1) {
		if (apol_vector_append(*path, next_node) < 0) {
			ERR(p, "%s", strerror(errno));
			goto cleanup;
		}
		if (next_node == start_node) {
			break;
		}
		if (next_node == NULL || apol_vector_get_size(*path) >= apol_vector_get_size(g->nodes)) {
			ERR(p, "%s", "Infinite loop in trans_path.");
			errno = EPERM;
			goto cleanup;
		}
		next_node = next_node->parent;
	}
	retval = 0;
      cleanup:
	if (retval != 0) {
		apol_vector_destroy(path);
	}
	return retval;
}

/**
 * Given a node within an infoflow graph, return the edge that
 * connects it to next_node.
 *
 * @param p Policy handler, for reporting errors.
 * @param g Infoflow graph from which to find edge.
 * @param node Starting node.
 * @param next_node Ending node.
 *
 * @return Edge connecting node to next_node, or NULL on error.
 */
static apol_infoflow_edge_t *apol_infoflow_trans_find_edge(const apol_policy_t * p,
							   apol_infoflow_graph_t * g,
							   apol_infoflow_node_t * node, apol_infoflow_node_t * next_node)
{
	apol_vector_t *v;
	apol_infoflow_edge_t *edge;
	size_t i;

	if (g->direction == APOL_INFOFLOW_OUT) {
		v = node->out_edges;
	} else {
		v = node->in_edges;
	}
	for (i = 0; i < apol_vector_get_size(v); i++) {
		edge = (apol_infoflow_edge_t *) apol_vector_get_element(v, i);
		if (g->direction == APOL_INFOFLOW_OUT) {
			if (edge->start_node == node && edge->end_node == next_node) {
				return edge;
			}
		} else {
			if (edge->end_node == node && edge->start_node == next_node) {
				return edge;
			}

		}
	}
	ERR(p, "%s", "Did not find an edge.");
	return NULL;
}

/**
 * Given a path of nodes, define a new infoflow result that represents
 * that path.  The given path is a list of nodes that must be in
 * reverse order (i.e., from end node to start node) and must have at
 * least 2 elements within.
 *
 * @param p Policy handler, for reporting errors.
 * @param g Graph from which the node path originated.
 * @param path Vector of apol_infoflow_node_t representing an infoflow
 * path.
 * @param end_type Ending type for the path.
 * @param result Reference pointer to where to store result.  The
 * caller is responsible for calling apol_infoflow_result_free() upon
 * the returned value.  Upon error this will be set to NULL.
 *
 * @return 0 on success, < 0 on error.
 */
static int apol_infoflow_trans_define(const apol_policy_t * p,
				      apol_infoflow_graph_t * g,
				      apol_vector_t * path, const qpol_type_t * end_type, apol_infoflow_result_t ** result)
{
	apol_infoflow_step_t *step = NULL;
	size_t path_len = apol_vector_get_size(path), i;
	apol_infoflow_node_t *node, *next_node;
	apol_infoflow_edge_t *edge;
	int retval = -1, length = 0;
	*result = NULL;

	if (((*result) = calloc(1, sizeof(**result))) == NULL ||
	    ((*result)->steps = apol_vector_create_with_capacity(path_len, apol_infoflow_step_free)) == NULL) {
		ERR(p, "%s", strerror(ENOMEM));
		goto cleanup;
	}
	(*result)->end_type = end_type;
	/* build in reverse order because path is from end node to
	 * start node */
	node = (apol_infoflow_node_t *) apol_vector_get_element(path, path_len - 1);
	(*result)->start_type = node->type;
	(*result)->direction = g->direction;
	for (i = path_len - 1; i > 0; i--, node = next_node) {
		next_node = (apol_infoflow_node_t *) apol_vector_get_element(path, i - 1);
		edge = apol_infoflow_trans_find_edge(p, g, node, next_node);
		if (edge == NULL) {
			goto cleanup;
		}
		length += edge->length;
		if ((step = calloc(1, sizeof(*step))) == NULL ||
		    (step->rules = apol_vector_create_from_vector(edge->rules, NULL, NULL, NULL)) == NULL ||
		    apol_vector_append((*result)->steps, step) < 0) {
			apol_infoflow_step_free(step);
			ERR(p, "%s", strerror(ENOMEM));
			return -1;
		}
		step->start_type = edge->start_node->type;
		step->end_type = edge->end_node->type;
		step->weight = APOL_PERMMAP_MAX_WEIGHT - edge->length + 1;
	}
	(*result)->length = length;
	retval = 0;
      cleanup:
	if (retval != 0) {
		infoflow_result_free(*result);
		*result = NULL;
	}
	return retval;
}

/**
 * Compares two apol_infoflow_step_t objects, returning 0 if they have
 * the same contents, non-zero or not.  This is a callback function to
 * apol_vector_compare().
 *
 * @param a First apol_infoflow_step_t to compare.
 * @param b Other apol_infoflow_step_t to compare.
 * @param data Unused.
 *
 * @return 0 if the steps are the same, non-zero if different.
 */
static int apol_infoflow_trans_step_comp(const void *a, const void *b, void *data __attribute__ ((unused)))
{
	const apol_infoflow_step_t *step_a = (const apol_infoflow_step_t *)a;
	const apol_infoflow_step_t *step_b = (const apol_infoflow_step_t *)b;
	size_t i;
	if (step_a->start_type != step_b->start_type) {
		return (int)((char *)step_a->start_type - (char *)step_b->start_type);
	}
	if (step_a->end_type != step_b->end_type) {
		return (int)((char *)step_a->end_type - (char *)step_b->end_type);
	}
	return apol_vector_compare(step_a->rules, step_b->rules, NULL, NULL, &i);
}

/**
 * Given a path, append to the results vector a new
 * apol_infoflow_result object - but only if there is not already a
 * result describing the same path.
 *
 * @param p Policy handler, for reporting errors.
 * @param g Infoflow graph to which create results.
 * @param path Vector of apol_infoflow_node_t describing a path from
 * an end node to a starting node.
 * @param end_type Ending type for the path.
 * @param results Vector of apol_infoflow_result_t to possibly append
 * a new result.
 *
 * @return 0 on success, < 0 on error.
 */
static int apol_infoflow_trans_append(const apol_policy_t * p,
				      apol_infoflow_graph_t * g,
				      apol_vector_t * path, const qpol_type_t * end_type, apol_vector_t * results)
{
	apol_infoflow_result_t *new_r = NULL, *r;
	size_t i, j;
	int compval, retval = -1;

	if (apol_infoflow_trans_define(p, g, path, end_type, &new_r) < 0) {
		goto cleanup;
	}

	/* First we look for duplicate paths */
	for (i = 0; i < apol_vector_get_size(results); i++) {
		r = (apol_infoflow_result_t *) apol_vector_get_element(results, i);
		if (r->end_type != end_type ||
		    r->direction != new_r->direction || apol_vector_get_size(r->steps) != apol_vector_get_size(new_r->steps)) {
			break;
		}
		compval = apol_vector_compare(r->steps, new_r->steps, apol_infoflow_trans_step_comp, NULL, &j);
		/* found a dup TODO - make certain all of the object
		 * class / rules are kept */
		if (compval == 0) {
			infoflow_result_free(new_r);
			new_r = NULL;
			retval = 0;
			goto cleanup;
		}
	}

	/* If we are here the newly built path is unique. */
	if (apol_vector_append(results, new_r) < 0) {
		goto cleanup;
	}
	retval = 0;
      cleanup:
	if (retval != 0) {
		infoflow_result_free(new_r);
	}
	return retval;
}

/**
 * Given a start and end node, add a trans infoflow results to a
 * vector.  If a regular expression is compiled into the infoflow
 * graph, apply that regex match against candidate end node types
 * prior to creating result nodes.
 *
 * @param p Policy to analyze.
 * @param g Information flow graph to analyze.
 * @param start_node Starting node.
 * @param end_node Ending node.
 * @param results Non-NULL vector to which append infoflow result.
 * The caller is responsible for calling apol_infoflow_results_free()
 * upon each element afterwards.
 *
 * @return 0 on success (including no result actually added), or < 0
 * on error.
 */
static int apol_infoflow_analysis_trans_expand(const apol_policy_t * p,
					       apol_infoflow_graph_t * g,
					       apol_infoflow_node_t * start_node,
					       apol_infoflow_node_t * end_node, apol_vector_t * results)
{
	unsigned char isattr;
	apol_vector_t *path = NULL;
	int retval = -1, compval;

	if (qpol_type_get_isattr(p->p, end_node->type, &isattr) < 0) {
		goto cleanup;
	}
	assert(isattr == 0);
	if (start_node->type == end_node->type) {
		return 0;
	}
	compval = apol_infoflow_graph_compare(p, g, end_node->type);
	if (compval < 0) {
		goto cleanup;
	} else if (compval == 0) {
		return 0;
	}
	if (apol_infoflow_trans_path(p, g, start_node, end_node, &path) < 0 ||
	    apol_infoflow_trans_append(p, g, path, end_node->type, results) < 0) {
		goto cleanup;
	}
	retval = 0;
      cleanup:
	apol_vector_destroy(&path);
	return retval;
}

/**
 * Perform a transitive information flow analysis upon the given
 * infoflow graph starting from some particular node within the graph.
 *
 * This is a label correcting shortest path algorithm; see Bertsekas,
 * D. P., "A Simple and Fast Label Correcting Algorithm for Shortest
 * Paths," Networks, Vol. 23, pp. 703-709, 1993. for more information.
 * A label correcting algorithm is needed instead of the more common
 * Dijkstra label setting algorithm to correctly handle the the cycles
 * that are possible in these graphs.
 *
 * This algorithm finds the shortest path between a given start node
 * and all other nodes in the graph.  Any paths that it finds it
 * appends to the iflow_transitive_t structure. This is a basic label
 * correcting algorithm with 1 optimization.  It uses the D'Esopo-Pape
 * method for node selection in the node queue.  Why is this faster?
 * The paper referenced above says "No definitive explanation has been
 * given."  They have fancy graphs to show that it is faster though
 * and the important part is that the worst case isn't much worse that
 * N^2 - much better than an n^3 transitive closure.  Additionally,
 * most normal sparse graphs are significantly better than the worst
 * case.
 *
 * @param p Policy to analyze.
 * @param g Information flow graph to analyze.
 * @param start Node from which to begin search.
 * @param results Non-NULL vector to which append infoflow results.
 * The caller is responsible for calling apol_infoflow_results_free()
 * upon each element afterwards.
 *
 * @return 0 on success, < 0 on error.
 */
static int apol_infoflow_analysis_trans_shortest_path(const apol_policy_t * p,
						      apol_infoflow_graph_t * g,
						      apol_infoflow_node_t * start, apol_vector_t * results)
{
	apol_vector_t *edge_list;
	apol_queue_t *queue = NULL;
	apol_infoflow_node_t *node, *cur_node;
	apol_infoflow_edge_t *edge;
	size_t i;
	int retval = -1;

	if ((queue = apol_queue_create()) == NULL) {
		ERR(p, "%s", strerror(ENOMEM));
		goto cleanup;
	}
	if (apol_infoflow_graph_trans_init(p, g, start, queue) < 0) {
		goto cleanup;
	}

	while ((cur_node = apol_queue_remove(queue)) != NULL) {
		cur_node->color = APOL_INFOFLOW_COLOR_GREY;
		if (g->direction == APOL_INFOFLOW_OUT) {
			edge_list = cur_node->out_edges;
		} else {
			edge_list = cur_node->in_edges;
		}
		for (i = 0; i < apol_vector_get_size(edge_list); i++) {
			edge = (apol_infoflow_edge_t *) apol_vector_get_element(edge_list, i);
			if (g->direction == APOL_INFOFLOW_OUT) {
				node = edge->end_node;
			} else {
				node = edge->start_node;
			}
			if (node == start) {
				continue;
			}

			if (node->distance > cur_node->distance + edge->length) {
				node->distance = cur_node->distance + edge->length;
				node->parent = cur_node;
				/* If this node has been inserted into
				 * the queue before insert it at the
				 * beginning, otherwise it goes to the
				 * end.  See the comment at the
				 * beginning of the function for
				 * why. */
				if (node->color != APOL_INFOFLOW_COLOR_RED) {
					if (node->color == APOL_INFOFLOW_COLOR_GREY) {
						if (apol_queue_push(queue, node) < 0) {
							ERR(p, "%s", strerror(ENOMEM));
							goto cleanup;
						}
					} else {
						if (apol_queue_insert(queue, node) < 0) {
							ERR(p, "%s", strerror(ENOMEM));
							goto cleanup;
						}
					}
					node->color = APOL_INFOFLOW_COLOR_RED;
				}
			}
		}
	}

	/* Find all of the paths and add them to the results vector */
	for (i = 0; i < apol_vector_get_size(g->nodes); i++) {
		cur_node = (apol_infoflow_node_t *) apol_vector_get_element(g->nodes, i);
		if (cur_node->parent == NULL || cur_node == start) {
			continue;
		}
		if (apol_infoflow_analysis_trans_expand(p, g, start, cur_node, results) < 0) {
			goto cleanup;
		}
	}

	retval = 0;
      cleanup:
	apol_queue_destroy(&queue);
	return retval;
}

/**
 * Perform a transitive information flow analysis upon the given
 * infoflow graph.
 *
 * @param p Policy to analyze.
 * @param g Information flow graph to analyze.
 * @param start_type Type from which to begin search.
 * @param results Non-NULL vector to which append infoflow results.
 * The caller is responsible for calling apol_infoflow_results_free()
 * upon each element afterwards.
 *
 * @return 0 on success, < 0 on error.
 */
static int apol_infoflow_analysis_trans(const apol_policy_t * p,
					apol_infoflow_graph_t * g, const char *start_type, apol_vector_t * results)
{
	apol_vector_t *start_nodes = NULL;
	apol_infoflow_node_t *start_node;
	size_t i;
	int retval = -1;

	if (g->direction != APOL_INFOFLOW_IN && g->direction != APOL_INFOFLOW_OUT) {
		ERR(p, "%s", strerror(EINVAL));
		goto cleanup;
	}
	if ((start_nodes = apol_vector_create(NULL)) == NULL) {
		ERR(p, "%s", strerror(errno));
		goto cleanup;
	}
	if (apol_infoflow_graph_get_nodes_for_type(p, g, start_type, start_nodes) < 0) {
		goto cleanup;
	}
	for (i = 0; i < apol_vector_get_size(start_nodes); i++) {
		start_node = (apol_infoflow_node_t *) apol_vector_get_element(start_nodes, i);
		if (apol_infoflow_analysis_trans_shortest_path(p, g, start_node, results) < 0) {
			goto cleanup;
		}
	}
	retval = 0;
      cleanup:
	apol_vector_destroy(&start_nodes);
	return retval;
}

/**
 * Given a vector, allocate and return a new vector with the elements
 * shuffled about.  This will make a shallow copy of the original
 * vector's elements.
 *
 * @param p Policy handler, for error reporting.
 * @param g Transitive infoflow graph containing PRNG object.
 * @param v Vector to shuffle.
 *
 * @return A newly allocated vector with shuffled elements, or NULL
 * upon error.  The caller must call apol_vector_destroy() upon the
 * returned value.
 */
static apol_vector_t *apol_infoflow_trans_further_shuffle(const apol_policy_t * p, apol_infoflow_graph_t * g, apol_vector_t * v)
{
	size_t i, j, size;
	void **deck = NULL, *tmp;
	apol_vector_t *new_v = NULL;
	int retval = -1;
	size = apol_vector_get_size(v);
	if ((new_v = apol_vector_create_with_capacity(size, NULL)) == NULL) {
		ERR(p, "%s", strerror(errno));
		goto cleanup;
	}
	if (size == 0) {
		retval = 0;
		goto cleanup;
	}
	if ((deck = malloc(size * sizeof(*deck))) == NULL) {
		ERR(p, "%s", strerror(errno));
		goto cleanup;
	}
	for (i = 0; i < size; i++) {
		deck[i] = apol_vector_get_element(v, i);
	}
	for (i = size - 1; i > 0; i--) {
		j = (size_t) ((apol_infoflow_rand(g) / (RAND_MAX + 1.0)) * i);
		tmp = deck[i];
		deck[i] = deck[j];
		deck[j] = tmp;
	}
	for (i = 0; i < size; i++) {
		if (apol_vector_append(new_v, deck[i]) < 0) {
			ERR(p, "%s", strerror(ENOMEM));
			goto cleanup;
		}
	}
	retval = 0;
      cleanup:
	free(deck);
	if (retval != 0) {
		apol_vector_destroy(&new_v);
	}
	return new_v;
}

static int apol_infoflow_analysis_trans_further(const apol_policy_t * p,
						apol_infoflow_graph_t * g, apol_infoflow_node_t * start, apol_vector_t * results)
{
	apol_vector_t *edge_list = NULL;
	apol_queue_t *queue = NULL;
	apol_infoflow_node_t *node, *cur_node;
	apol_infoflow_edge_t *edge;
	size_t i;
	int retval = -1;

	if ((queue = apol_queue_create()) == NULL) {
		ERR(p, "%s", strerror(ENOMEM));
		goto cleanup;
	}
	if (apol_infoflow_graph_trans_further_init(p, g, start, queue) < 0) {
		goto cleanup;
	}

	while ((cur_node = apol_queue_remove(queue)) != NULL) {
		if (cur_node != start &&
		    apol_vector_get_index(g->further_end, cur_node, NULL, NULL, &i) == 0 &&
		    apol_infoflow_analysis_trans_expand(p, g, start, cur_node, results) < 0) {
			goto cleanup;
		}
		cur_node->color = APOL_INFOFLOW_COLOR_BLACK;
		if (g->direction == APOL_INFOFLOW_OUT) {
			edge_list = cur_node->out_edges;
		} else {
			edge_list = cur_node->in_edges;
		}
		edge_list = apol_infoflow_trans_further_shuffle(p, g, edge_list);
		if (edge_list == NULL) {
			goto cleanup;
		}
		for (i = 0; i < apol_vector_get_size(edge_list); i++) {
			edge = (apol_infoflow_edge_t *) apol_vector_get_element(edge_list, i);
			if (g->direction == APOL_INFOFLOW_OUT) {
				node = edge->end_node;
			} else {
				node = edge->start_node;
			}
			if (node->color == APOL_INFOFLOW_COLOR_WHITE) {
				node->color = APOL_INFOFLOW_COLOR_GREY;
				node->distance = cur_node->distance + 1;
				node->parent = cur_node;
				if (apol_queue_push(queue, node) < 0) {
					ERR(p, "%s", strerror(ENOMEM));
					goto cleanup;
				}
			}
		}
		apol_vector_destroy(&edge_list);
	}
	retval = 0;
      cleanup:
	apol_vector_destroy(&edge_list);
	apol_queue_destroy(&queue);
	return retval;
}

/******************** infoflow analysis object routines ********************/

int apol_infoflow_analysis_do(const apol_policy_t * p, const apol_infoflow_analysis_t * ia, apol_vector_t ** v,
			      apol_infoflow_graph_t ** g)
{
	int retval = -1;
	if (v != NULL) {
		*v = NULL;
	}
	if (g != NULL) {
		*g = NULL;
	}
	if (p == NULL || ia == NULL || v == NULL || g == NULL || ia->mode == 0 || ia->direction == 0) {
		ERR(p, "%s", strerror(EINVAL));
		goto cleanup;
	}
	if (apol_infoflow_graph_create(p, ia, g) < 0) {
		goto cleanup;
	}
	INFO(p, "%s", "Searching information flow graph.");
	retval = apol_infoflow_analysis_do_more(p, *g, ia->type, v);
      cleanup:
	if (retval != 0) {
		apol_infoflow_graph_destroy(g);
	}
	return retval;
}

int apol_infoflow_analysis_do_more(const apol_policy_t * p, apol_infoflow_graph_t * g, const char *type, apol_vector_t ** v)
{
	const qpol_type_t *start_type;
	int retval = -1;
	if (v != NULL) {
		*v = NULL;
	}
	if (p == NULL || g == NULL || type == NULL || v == NULL) {
		ERR(p, "%s", strerror(EINVAL));
		goto cleanup;
	}

	if (apol_query_get_type(p, type, &start_type) < 0) {
		goto cleanup;
	}

	if ((*v = apol_vector_create(infoflow_result_free)) == NULL) {
		ERR(p, "%s", strerror(ENOMEM));
		goto cleanup;
	}

	if ((g->mode == APOL_INFOFLOW_MODE_DIRECT &&
	     apol_infoflow_analysis_direct(p, g, type, *v) < 0) ||
	    (g->mode == APOL_INFOFLOW_MODE_TRANS && apol_infoflow_analysis_trans(p, g, type, *v) < 0)) {
		goto cleanup;
	}

	retval = 0;
      cleanup:
	if (retval != 0) {
		apol_vector_destroy(v);
	}
	return retval;
}

int apol_infoflow_analysis_trans_further_prepare(const apol_policy_t * p,
						 apol_infoflow_graph_t * g, const char *start_type, const char *end_type)
{
	const qpol_type_t *stype, *etype;
	int retval = -1;

	apol_infoflow_srand(g);
	if (apol_query_get_type(p, start_type, &stype) < 0 || apol_query_get_type(p, end_type, &etype) < 0) {
		goto cleanup;
	}
	if (g->mode != APOL_INFOFLOW_MODE_TRANS) {
		ERR(p, "%s", "May only perform further infoflow analysis when the graph is transitive.");
		goto cleanup;
	}
	apol_vector_destroy(&g->further_start);
	apol_vector_destroy(&g->further_end);
	if ((g->further_start = apol_vector_create(NULL)) == NULL || (g->further_end = apol_vector_create(NULL)) == NULL) {
		ERR(p, "%s", strerror(errno));
		goto cleanup;
	}
	if (apol_infoflow_graph_get_nodes_for_type(p, g, start_type, g->further_start) < 0 ||
	    apol_infoflow_graph_get_nodes_for_type(p, g, end_type, g->further_end) < 0) {
		goto cleanup;
	}
	g->current_start = 0;
	retval = 0;
      cleanup:
	return retval;
}

int apol_infoflow_analysis_trans_further_next(const apol_policy_t * p, apol_infoflow_graph_t * g, apol_vector_t ** v)
{
	apol_infoflow_node_t *start_node;
	int retval = -1;
	if (p == NULL || g == NULL || v == NULL) {
		ERR(p, "%s", strerror(EINVAL));
		errno = EINVAL;
		return -1;
	}
	if (*v == NULL) {
		*v = apol_vector_create(infoflow_result_free);
	}
	if (g->further_start == NULL) {
		ERR(p, "%s", "Infoflow graph was not prepared yet.");
		goto cleanup;
	}
	start_node = apol_vector_get_element(g->further_start, g->current_start);
	if (apol_infoflow_analysis_trans_further(p, g, start_node, *v) < 0) {
		goto cleanup;
	}
	g->current_start++;
	if (g->current_start >= apol_vector_get_size(g->further_start)) {
		g->current_start = 0;
	}
	retval = 0;
      cleanup:
	return retval;
}

apol_infoflow_analysis_t *apol_infoflow_analysis_create(void)
{
	return calloc(1, sizeof(apol_infoflow_analysis_t));
}

void apol_infoflow_analysis_destroy(apol_infoflow_analysis_t ** ia)
{
	if (*ia != NULL) {
		free((*ia)->type);
		free((*ia)->result);
		apol_vector_destroy(&(*ia)->intermed);
		apol_vector_destroy(&(*ia)->class_perms);
		free(*ia);
		*ia = NULL;
	}
}

int apol_infoflow_analysis_set_mode(const apol_policy_t * p, apol_infoflow_analysis_t * ia, unsigned int mode)
{
	switch (mode) {
	case APOL_INFOFLOW_MODE_DIRECT:
	case APOL_INFOFLOW_MODE_TRANS:
	{
		ia->mode = mode;
		break;
	}
	default:
	{
		ERR(p, "%s", strerror(EINVAL));
		return -1;
	}
	}
	return 0;
}

int apol_infoflow_analysis_set_dir(const apol_policy_t * p, apol_infoflow_analysis_t * ia, unsigned int dir)
{
	switch (dir) {
	case APOL_INFOFLOW_IN:
	case APOL_INFOFLOW_OUT:
	case APOL_INFOFLOW_BOTH:
	case APOL_INFOFLOW_EITHER:
	{
		ia->direction = dir;
		break;
	}
	default:
	{
		ERR(p, "%s", strerror(EINVAL));
		return -1;
	}
	}
	return 0;
}

int apol_infoflow_analysis_set_type(const apol_policy_t * p, apol_infoflow_analysis_t * ia, const char *name)
{
	if (name == NULL) {
		ERR(p, "%s", strerror(EINVAL));
		return -1;
	}
	return apol_query_set(p, &ia->type, NULL, name);
}

static int compare_class_perm_by_class_name(const void *in_op, const void *class_name, void *unused __attribute__ ((unused)))
{
	const apol_obj_perm_t *op = (const apol_obj_perm_t *)in_op;
	const char *name = (const char *)class_name;

	return strcmp(apol_obj_perm_get_obj_name(op), name);
}

int apol_infoflow_analysis_append_intermediate(const apol_policy_t * policy, apol_infoflow_analysis_t * ia, const char *type)
{
	char *tmp = NULL;
	if (type == NULL) {
		apol_vector_destroy(&ia->intermed);
		return 0;
	}
	if (ia->intermed == NULL && (ia->intermed = apol_vector_create(free)) == NULL) {
		ERR(policy, "Error appending type to analysis: %s", strerror(ENOMEM));
		return -1;
	}
	if ((tmp = strdup(type)) == NULL || apol_vector_append(ia->intermed, tmp) < 0) {
		free(tmp);
		ERR(policy, "Error appending type to analysis: %s", strerror(ENOMEM));
		return -1;
	}
	return 0;
}

int apol_infoflow_analysis_append_class_perm(const apol_policy_t * p,
					     apol_infoflow_analysis_t * ia, const char *class_name, const char *perm_name)
{
	apol_obj_perm_t *op = NULL;
	size_t i;

	if (p == NULL || ia == NULL) {
		ERR(p, "%s", strerror(EINVAL));
		errno = EINVAL;
		return -1;
	}
	if (class_name == NULL) {
		apol_vector_destroy(&ia->class_perms);
		return 0;
	}
	if (perm_name == NULL) {
		ERR(p, "%s", strerror(EINVAL));
		errno = EINVAL;
		return -1;
	}
	if (ia->class_perms == NULL && (ia->class_perms = apol_vector_create(apol_obj_perm_free)) == NULL) {
		ERR(p, "%s", strerror(errno));
		return -1;
	}

	if (apol_vector_get_index(ia->class_perms, (void *)class_name, compare_class_perm_by_class_name, NULL, &i) < 0) {
		if (perm_name) {
			if ((op = apol_obj_perm_create()) == NULL) {
				ERR(p, "%s", strerror(errno));
				return -1;
			}
			if (apol_obj_perm_set_obj_name(op, class_name) ||
			    apol_obj_perm_append_perm(op, perm_name) || apol_vector_append(ia->class_perms, op)) {
				ERR(p, "%s", strerror(errno));
				apol_obj_perm_free(op);
				return -1;
			}
		} else {
			return 0;      /* nothing to clear; done */
		}
	} else {
		op = apol_vector_get_element(ia->class_perms, i);
		if (apol_obj_perm_append_perm(op, perm_name)) {
			ERR(p, "%s", strerror(errno));
			return -1;
		}
	}
	return 0;
}

int apol_infoflow_analysis_set_min_weight(const apol_policy_t * p
					  __attribute__ ((unused)), apol_infoflow_analysis_t * ia, int min_weight)
{
	if (min_weight <= 0) {
		ia->min_weight = 0;
	} else if (min_weight >= APOL_PERMMAP_MAX_WEIGHT) {
		ia->min_weight = APOL_PERMMAP_MAX_WEIGHT;
	} else {
		ia->min_weight = min_weight;
	}
	return 0;
}

int apol_infoflow_analysis_set_result_regex(const apol_policy_t * p, apol_infoflow_analysis_t * ia, const char *result)
{
	return apol_query_set(p, &ia->result, NULL, result);
}

/*************** functions to access infoflow results ***************/

unsigned int apol_infoflow_result_get_dir(const apol_infoflow_result_t * result)
{
	if (!result) {
		errno = EINVAL;
		return 0;
	}
	return result->direction;
}

const qpol_type_t *apol_infoflow_result_get_start_type(const apol_infoflow_result_t * result)
{
	if (!result) {
		errno = EINVAL;
		return NULL;
	}
	return result->start_type;
}

const qpol_type_t *apol_infoflow_result_get_end_type(const apol_infoflow_result_t * result)
{
	if (!result) {
		errno = EINVAL;
		return NULL;
	}
	return result->end_type;
}

unsigned int apol_infoflow_result_get_length(const apol_infoflow_result_t * result)
{
	if (!result) {
		errno = EINVAL;
		return 0;
	}
	assert(result->length != 0);
	return result->length;
}

const apol_vector_t *apol_infoflow_result_get_steps(const apol_infoflow_result_t * result)
{
	if (!result) {
		errno = EINVAL;
		return NULL;
	}
	return result->steps;
}

const qpol_type_t *apol_infoflow_step_get_start_type(const apol_infoflow_step_t * step)
{
	if (!step) {
		errno = EINVAL;
		return NULL;
	}
	return step->start_type;
}

const qpol_type_t *apol_infoflow_step_get_end_type(const apol_infoflow_step_t * step)
{
	if (!step) {
		errno = EINVAL;
		return NULL;
	}
	return step->end_type;
}

int apol_infoflow_step_get_weight(const apol_infoflow_step_t * step)
{
	if (!step) {
		errno = EINVAL;
		return -1;
	}
	return step->weight;
}

const apol_vector_t *apol_infoflow_step_get_rules(const apol_infoflow_step_t * step)
{
	if (!step) {
		errno = EINVAL;
		return NULL;
	}
	return step->rules;
}

/******************** protected functions ********************/

apol_infoflow_result_t *infoflow_result_create_from_infoflow_result(const apol_infoflow_result_t * result)
{
	apol_infoflow_result_t *new_r = NULL;
	apol_infoflow_step_t *step, *new_step;
	size_t i;
	int retval = -1;

	if ((new_r = calloc(1, sizeof(*new_r))) == NULL ||
	    (new_r->steps = apol_vector_create_with_capacity(apol_vector_get_size(result->steps), apol_infoflow_step_free)) == NULL)
	{
		goto cleanup;
	}
	new_r->start_type = result->start_type;
	new_r->end_type = result->end_type;
	new_r->direction = result->direction;
	new_r->length = result->length;
	for (i = 0; i < apol_vector_get_size(result->steps); i++) {
		step = (apol_infoflow_step_t *) apol_vector_get_element(result->steps, i);
		if ((new_step = calloc(1, sizeof(*new_step))) == NULL ||
		    (new_step->rules = apol_vector_create_from_vector(step->rules, NULL, NULL, NULL)) == NULL ||
		    apol_vector_append(new_r->steps, new_step) < 0) {
			apol_infoflow_step_free(new_step);
			goto cleanup;
		}
		new_step->start_type = step->start_type;
		new_step->end_type = step->end_type;
		new_step->weight = step->weight;
	}
	retval = 0;
      cleanup:
	if (retval != 0) {
		infoflow_result_free(new_r);
		return NULL;
	}
	return new_r;
}

void infoflow_result_free(void *result)
{
	if (result != NULL) {
		apol_infoflow_result_t *r = (apol_infoflow_result_t *) result;
		apol_vector_destroy(&r->steps);
		free(r);
	}
}