1edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep# Copyright 2014-2015, Tresys Technology, LLC 2edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep# 3edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep# This file is part of SETools. 4edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep# 5edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep# SETools is free software: you can redistribute it and/or modify 6edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep# it under the terms of the GNU Lesser General Public License as 7edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep# published by the Free Software Foundation, either version 2.1 of 8edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep# the License, or (at your option) any later version. 9edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep# 10edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep# SETools is distributed in the hope that it will be useful, 11edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep# but WITHOUT ANY WARRANTY; without even the implied warranty of 12edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep# GNU Lesser General Public License for more details. 14edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep# 15edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep# You should have received a copy of the GNU Lesser General Public 16edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep# License along with SETools. If not, see 17edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep# <http://www.gnu.org/licenses/>. 18edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep# 19edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep# pylint: disable=unsubscriptable-object 20edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 21edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoepimport itertools 22edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoepimport logging 23edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoepfrom collections import defaultdict, namedtuple 24edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 25edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoepimport networkx as nx 26edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoepfrom networkx.exception import NetworkXError, NetworkXNoPath 27edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 28edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoepfrom .descriptors import EdgeAttrDict, EdgeAttrList 29edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 30edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep__all__ = ['DomainTransitionAnalysis'] 31edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 32edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep# Return values for the analysis 33edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep# are in the following tuple formats: 34edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoepstep_output = namedtuple("step", ["source", 35edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep "target", 36edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep "transition", 37edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep "entrypoints", 38edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep "setexec", 39edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep "dyntransition", 40edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep "setcurrent"]) 41edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 42edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoepentrypoint_output = namedtuple("entrypoints", ["name", 43edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep "entrypoint", 44edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep "execute", 45edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep "type_transition"]) 46edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 47edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 48edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoepclass DomainTransitionAnalysis(object): 49edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 50edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """Domain transition analysis.""" 51edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 52edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __init__(self, policy, reverse=False, exclude=None): 53edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 54edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Parameter: 55edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep policy The policy to analyze. 56edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 57edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.log = logging.getLogger(__name__) 58edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 59edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.policy = policy 60edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.exclude = exclude 61edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.reverse = reverse 62edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.rebuildgraph = True 63edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.rebuildsubgraph = True 64edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.G = nx.DiGraph() 65edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.subG = None 66edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 67edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep @property 68edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def reverse(self): 69edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return self._reverse 70edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 71edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep @reverse.setter 72edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def reverse(self, direction): 73edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self._reverse = bool(direction) 74edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.rebuildsubgraph = True 75edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 76edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep @property 77edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def exclude(self): 78edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return self._exclude 79edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 80edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep @exclude.setter 81edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def exclude(self, types): 82edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if types: 83edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self._exclude = [self.policy.lookup_type(t) for t in types] 84edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 85edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self._exclude = [] 86edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 87edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.rebuildsubgraph = True 88edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 89edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def shortest_path(self, source, target): 90edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 91edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Generator which yields one shortest domain transition path 92edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep between the source and target types (there may be more). 93edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 94edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Parameters: 95edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep source The source type. 96edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep target The target type. 97edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 98edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Yield: generator(steps) 99edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 100edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep steps A generator that returns the tuple of 101edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep source, target, and rules for each 102edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep domain transition. 103edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 104edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep s = self.policy.lookup_type(source) 105edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep t = self.policy.lookup_type(target) 106edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 107edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if self.rebuildsubgraph: 108edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self._build_subgraph() 109edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 110edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.log.info("Generating one domain transition path from {0} to {1}...".format(s, t)) 111edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 112edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep try: 113edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep yield self.__generate_steps(nx.shortest_path(self.subG, s, t)) 114edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep except (NetworkXNoPath, NetworkXError): 115edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # NetworkXError: the type is valid but not in graph, e.g. excluded 116edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # NetworkXNoPath: no paths or the target type is 117edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # not in the graph 118edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep pass 119edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 120edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def all_paths(self, source, target, maxlen=2): 121edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 122edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Generator which yields all domain transition paths between 123edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep the source and target up to the specified maximum path 124edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep length. 125edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 126edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Parameters: 127edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep source The source type. 128edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep target The target type. 129edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep maxlen Maximum length of paths. 130edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 131edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Yield: generator(steps) 132edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 133edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep steps A generator that returns the tuple of 134edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep source, target, and rules for each 135edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep domain transition. 136edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 137edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if maxlen < 1: 138edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep raise ValueError("Maximum path length must be positive.") 139edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 140edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep s = self.policy.lookup_type(source) 141edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep t = self.policy.lookup_type(target) 142edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 143edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if self.rebuildsubgraph: 144edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self._build_subgraph() 145edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 146edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.log.info("Generating all domain transition paths from {0} to {1}, max length {2}...". 147edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep format(s, t, maxlen)) 148edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 149edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep try: 150edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep for path in nx.all_simple_paths(self.subG, s, t, maxlen): 151edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep yield self.__generate_steps(path) 152edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep except (NetworkXNoPath, NetworkXError): 153edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # NetworkXError: the type is valid but not in graph, e.g. excluded 154edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # NetworkXNoPath: no paths or the target type is 155edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # not in the graph 156edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep pass 157edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 158edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def all_shortest_paths(self, source, target): 159edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 160edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Generator which yields all shortest domain transition paths 161edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep between the source and target types. 162edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 163edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Parameters: 164edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep source The source type. 165edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep target The target type. 166edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 167edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Yield: generator(steps) 168edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 169edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep steps A generator that returns the tuple of 170edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep source, target, and rules for each 171edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep domain transition. 172edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 173edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep s = self.policy.lookup_type(source) 174edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep t = self.policy.lookup_type(target) 175edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 176edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if self.rebuildsubgraph: 177edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self._build_subgraph() 178edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 179edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.log.info("Generating all shortest domain transition paths from {0} to {1}...". 180edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep format(s, t)) 181edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 182edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep try: 183edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep for path in nx.all_shortest_paths(self.subG, s, t): 184edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep yield self.__generate_steps(path) 185edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep except (NetworkXNoPath, NetworkXError, KeyError): 186edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # NetworkXError: the type is valid but not in graph, e.g. excluded 187edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # NetworkXNoPath: no paths or the target type is 188edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # not in the graph 189edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # KeyError: work around NetworkX bug 190edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # when the source node is not in the graph 191edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep pass 192edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 193edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def transitions(self, type_): 194edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 195edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Generator which yields all domain transitions out of a 196edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep specified source type. 197edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 198edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Parameters: 199edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep type_ The starting type. 200edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 201edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Yield: generator(steps) 202edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 203edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep steps A generator that returns the tuple of 204edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep source, target, and rules for each 205edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep domain transition. 206edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 207edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep s = self.policy.lookup_type(type_) 208edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 209edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if self.rebuildsubgraph: 210edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self._build_subgraph() 211edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 212edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.log.info("Generating all domain transitions {1} {0}". 213edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep format(s, "in to" if self.reverse else "out from")) 214edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 215edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep try: 216edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep for source, target in self.subG.out_edges_iter(s): 217edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep edge = Edge(self.subG, source, target) 218edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 219edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if self.reverse: 220edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep real_source, real_target = target, source 221edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 222edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep real_source, real_target = source, target 223edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 224edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep yield step_output(real_source, real_target, 225edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep edge.transition, 226edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.__generate_entrypoints(edge), 227edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep edge.setexec, 228edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep edge.dyntransition, 229edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep edge.setcurrent) 230edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 231edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep except NetworkXError: 232edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # NetworkXError: the type is valid but not in graph, e.g. excluded 233edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep pass 234edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 235edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def get_stats(self): # pragma: no cover 236edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 237edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Get the domain transition graph statistics. 238edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 239edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Return: str 240edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 241edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if self.rebuildgraph: 242edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self._build_graph() 243edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 244edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return nx.info(self.G) 245edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 246edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 247edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # Internal functions follow 248edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 249edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep @staticmethod 250edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __generate_entrypoints(edge): 251edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 252edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Creates a list of entrypoint, execute, and 253edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep type_transition rules for each entrypoint. 254edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 255edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Parameter: 256edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep data The dictionary of entrypoints. 257edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 258edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Return: list of tuple(type, entry, exec, trans) 259edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 260edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep type The entrypoint type. 261edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep entry The list of entrypoint rules. 262edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep exec The list of execute rules. 263edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep trans The list of type_transition rules. 264edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 265edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return [entrypoint_output(e, edge.entrypoint[e], edge.execute[e], edge.type_transition[e]) 266edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep for e in edge.entrypoint] 267edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 268edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __generate_steps(self, path): 269edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 270edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Generator which yields the source, target, and associated rules 271edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep for each domain transition. 272edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 273edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Parameter: 274edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep path A list of graph node names representing an information flow path. 275edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 276edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Yield: tuple(source, target, transition, entrypoints, 277edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep setexec, dyntransition, setcurrent) 278edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 279edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep source The source type for this step of the domain transition. 280edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep target The target type for this step of the domain transition. 281edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep transition The list of transition rules. 282edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep entrypoints Generator which yields entrypoint-related rules. 283edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep setexec The list of setexec rules. 284edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep dyntranstion The list of dynamic transition rules. 285edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep setcurrent The list of setcurrent rules. 286edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 287edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 288edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep for s in range(1, len(path)): 289edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep source = path[s - 1] 290edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep target = path[s] 291edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep edge = Edge(self.subG, source, target) 292edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 293edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # Yield the actual source and target. 294edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # The above perspective is reversed 295edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # if the graph has been reversed. 296edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if self.reverse: 297edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep real_source, real_target = target, source 298edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 299edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep real_source, real_target = source, target 300edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 301edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep yield step_output(real_source, real_target, 302edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep edge.transition, 303edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.__generate_entrypoints(edge), 304edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep edge.setexec, 305edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep edge.dyntransition, 306edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep edge.setcurrent) 307edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 308edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 309edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # Graph building functions 310edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 311edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 312edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # Domain transition requirements: 313edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 314edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # Standard transitions a->b: 315edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # allow a b:process transition; 316edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # allow a b_exec:file execute; 317edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # allow b b_exec:file entrypoint; 318edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 319edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # and at least one of: 320edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # allow a self:process setexec; 321edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # type_transition a b_exec:process b; 322edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 323edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # Dynamic transition x->y: 324edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # allow x y:process dyntransition; 325edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # allow x self:process setcurrent; 326edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 327edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # Algorithm summary: 328edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 1. iterate over all rules 329edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 1. skip non allow/type_transition rules 330edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 2. if process transition or dyntransition, create edge, 331edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # initialize rule lists, add the (dyn)transition rule 332edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 3. if process setexec or setcurrent, add to appropriate dict 333edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # keyed on the subject 334edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 4. if file exec, entrypoint, or type_transition:process, 335edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # add to appropriate dict keyed on subject,object. 336edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 2. Iterate over all graph edges: 337edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 1. if there is a transition rule (else add to invalid 338edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # transition list): 339edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 1. use set intersection to find matching exec 340edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # and entrypoint rules. If none, add to invalid 341edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # transition list. 342edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 2. for each valid entrypoint, add rules to the 343edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # edge's lists if there is either a 344edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # type_transition for it or the source process 345edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # has setexec permissions. 346edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 3. If there are neither type_transitions nor 347edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # setexec permissions, add to the invalid 348edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # transition list 349edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 2. if there is a dyntransition rule (else add to invalid 350edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # dyntrans list): 351edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 1. If the source has a setcurrent rule, add it 352edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # to the edge's list, else add to invalid 353edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # dyntransition list. 354edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 3. Iterate over all graph edges: 355edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 1. if the edge has an invalid trans and dyntrans, delete 356edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # the edge. 357edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 2. if the edge has an invalid trans, clear the related 358edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # lists on the edge. 359edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 3. if the edge has an invalid dyntrans, clear the related 360edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # lists on the edge. 361edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # 362edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def _build_graph(self): 363edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.G.clear() 364edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.G.name = "Domain transition graph for {0}.".format(self.policy) 365edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 366edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.log.info("Building domain transition graph from {0}...".format(self.policy)) 367edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 368edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # hash tables keyed on domain type 369edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep setexec = defaultdict(list) 370edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep setcurrent = defaultdict(list) 371edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 372edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # hash tables keyed on (domain, entrypoint file type) 373edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # the parameter for defaultdict has to be callable 374edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # hence the lambda for the nested defaultdict 375edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep execute = defaultdict(lambda: defaultdict(list)) 376edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep entrypoint = defaultdict(lambda: defaultdict(list)) 377edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 378edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # hash table keyed on (domain, entrypoint, target domain) 379edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep type_trans = defaultdict(lambda: defaultdict(lambda: defaultdict(list))) 380edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 381edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep for rule in self.policy.terules(): 382edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if rule.ruletype == "allow": 383edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if rule.tclass not in ["process", "file"]: 384edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep continue 385edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 386edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep perms = rule.perms 387edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 388edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if rule.tclass == "process": 389edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if "transition" in perms: 390edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep for s, t in itertools.product(rule.source.expand(), rule.target.expand()): 391edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # only add edges if they actually 392edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # transition to a new type 393edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if s != t: 394edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep edge = Edge(self.G, s, t, create=True) 395edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep edge.transition.append(rule) 396edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 397edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if "dyntransition" in perms: 398edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep for s, t in itertools.product(rule.source.expand(), rule.target.expand()): 399edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # only add edges if they actually 400edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # transition to a new type 401edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if s != t: 402edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep e = Edge(self.G, s, t, create=True) 403edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep e.dyntransition.append(rule) 404edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 405edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if "setexec" in perms: 406edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep for s in rule.source.expand(): 407edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep setexec[s].append(rule) 408edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 409edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if "setcurrent" in perms: 410edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep for s in rule.source.expand(): 411edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep setcurrent[s].append(rule) 412edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 413edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 414edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if "execute" in perms: 415edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep for s, t in itertools.product( 416edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep rule.source.expand(), 417edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep rule.target.expand()): 418edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep execute[s][t].append(rule) 419edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 420edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if "entrypoint" in perms: 421edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep for s, t in itertools.product(rule.source.expand(), rule.target.expand()): 422edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep entrypoint[s][t].append(rule) 423edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 424edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep elif rule.ruletype == "type_transition": 425edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if rule.tclass != "process": 426edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep continue 427edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 428edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep d = rule.default 429edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep for s, t in itertools.product(rule.source.expand(), rule.target.expand()): 430edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep type_trans[s][t][d].append(rule) 431edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 432edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep invalid_edge = [] 433edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep clear_transition = [] 434edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep clear_dyntransition = [] 435edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 436edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep for s, t in self.G.edges_iter(): 437edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep edge = Edge(self.G, s, t) 438edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep invalid_trans = False 439edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep invalid_dyntrans = False 440edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 441edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if edge.transition: 442edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # get matching domain exec w/entrypoint type 443edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep entry = set(entrypoint[t].keys()) 444edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep exe = set(execute[s].keys()) 445edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep match = entry.intersection(exe) 446edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 447edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if not match: 448edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # there are no valid entrypoints 449edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep invalid_trans = True 450edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 451edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # TODO try to improve the 452edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # efficiency in this loop 453edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep for m in match: 454edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if s in setexec or type_trans[s][m]: 455edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # add key for each entrypoint 456edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep edge.entrypoint[m] += entrypoint[t][m] 457edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep edge.execute[m] += execute[s][m] 458edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 459edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if type_trans[s][m][t]: 460edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep edge.type_transition[m] += type_trans[s][m][t] 461edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 462edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if s in setexec: 463edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep edge.setexec.extend(setexec[s]) 464edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 465edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if not edge.setexec and not edge.type_transition: 466edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep invalid_trans = True 467edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 468edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep invalid_trans = True 469edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 470edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if edge.dyntransition: 471edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if s in setcurrent: 472edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep edge.setcurrent.extend(setcurrent[s]) 473edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 474edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep invalid_dyntrans = True 475edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 476edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep invalid_dyntrans = True 477edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 478edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # cannot change the edges while iterating over them, 479edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # so keep appropriate lists 480edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if invalid_trans and invalid_dyntrans: 481edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep invalid_edge.append(edge) 482edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep elif invalid_trans: 483edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep clear_transition.append(edge) 484edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep elif invalid_dyntrans: 485edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep clear_dyntransition.append(edge) 486edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 487edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # Remove invalid transitions 488edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.G.remove_edges_from(invalid_edge) 489edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep for edge in clear_transition: 490edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # if only the regular transition is invalid, 491edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # clear the relevant lists 492edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep del edge.transition 493edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep del edge.execute 494edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep del edge.entrypoint 495edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep del edge.type_transition 496edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep del edge.setexec 497edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep for edge in clear_dyntransition: 498edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # if only the dynamic transition is invalid, 499edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # clear the relevant lists 500edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep del edge.dyntransition 501edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep del edge.setcurrent 502edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 503edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.rebuildgraph = False 504edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.rebuildsubgraph = True 505edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.log.info("Completed building domain transition graph.") 506edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.log.debug("Graph stats: nodes: {0}, edges: {1}.".format( 507edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep nx.number_of_nodes(self.G), 508edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep nx.number_of_edges(self.G))) 509edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 510edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __remove_excluded_entrypoints(self): 511edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep invalid_edges = [] 512edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep for source, target in self.subG.edges_iter(): 513edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep edge = Edge(self.subG, source, target) 514edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep entrypoints = set(edge.entrypoint) 515edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep entrypoints.intersection_update(self.exclude) 516edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 517edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if not entrypoints: 518edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # short circuit if there are no 519edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # excluded entrypoint types on 520edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # this edge. 521edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep continue 522edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 523edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep for e in entrypoints: 524edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # clear the entrypoint data 525edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep del edge.entrypoint[e] 526edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep del edge.execute[e] 527edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 528edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep try: 529edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep del edge.type_transition[e] 530edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep except KeyError: # setexec 531edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep pass 532edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 533edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # cannot delete the edges while iterating over them 534edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if not edge.entrypoint and not edge.dyntransition: 535edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep invalid_edges.append(edge) 536edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 537edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.subG.remove_edges_from(invalid_edges) 538edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 539edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def _build_subgraph(self): 540edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if self.rebuildgraph: 541edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self._build_graph() 542edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 543edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.log.info("Building domain transition subgraph.") 544edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.log.debug("Excluding {0}".format(self.exclude)) 545edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.log.debug("Reverse {0}".format(self.reverse)) 546edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 547edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # reverse graph for reverse DTA 548edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if self.reverse: 549edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.subG = self.G.reverse(copy=True) 550edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 551edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.subG = self.G.copy() 552edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 553edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if self.exclude: 554edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # delete excluded domains from subgraph 555edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.subG.remove_nodes_from(self.exclude) 556edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 557edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # delete excluded entrypoints from subgraph 558edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.__remove_excluded_entrypoints() 559edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 560edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.rebuildsubgraph = False 561edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.log.info("Completed building domain transition subgraph.") 562edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.log.debug("Subgraph stats: nodes: {0}, edges: {1}.".format( 563edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep nx.number_of_nodes(self.subG), 564edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep nx.number_of_edges(self.subG))) 565edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 566edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 567edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoepclass Edge(object): 568edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 569edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 570edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep A graph edge. Also used for returning domain transition steps. 571edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 572edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Parameters: 573edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep graph The NetworkX graph. 574edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep source The source type of the edge. 575edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep target The target tyep of the edge. 576edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 577edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep Keyword Parameters: 578edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep create (T/F) create the edge if it does not exist. 579edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep The default is False. 580edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """ 581edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 582edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep transition = EdgeAttrList('transition') 583edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep setexec = EdgeAttrList('setexec') 584edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep dyntransition = EdgeAttrList('dyntransition') 585edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep setcurrent = EdgeAttrList('setcurrent') 586edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep entrypoint = EdgeAttrDict('entrypoint') 587edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep execute = EdgeAttrDict('execute') 588edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep type_transition = EdgeAttrDict('type_transition') 589edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 590edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __init__(self, graph, source, target, create=False): 591edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.G = graph 592edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.source = source 593edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.target = target 594edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 595edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if not self.G.has_edge(source, target): 596edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if not create: 597edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep raise ValueError("Edge does not exist in graph") 598edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 599edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.G.add_edge(source, target) 600edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.transition = None 601edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.entrypoint = None 602edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.execute = None 603edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.type_transition = None 604edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.setexec = None 605edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.dyntransition = None 606edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep self.setcurrent = None 607edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 608edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def __getitem__(self, key): 609edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # This is implemented so this object can be used in NetworkX 610edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep # functions that operate on (source, target) tuples 611edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if isinstance(key, slice): 612edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return [self._index_to_item(i) for i in range(* key.indices(2))] 613edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 614edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return self._index_to_item(key) 615edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep 616edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep def _index_to_item(self, index): 617edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep """Return source or target based on index.""" 618edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep if index == 0: 619edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return self.source 620edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep elif index == 1: 621edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep return self.target 622edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep else: 623edbb763a2b63074cd468a5d33a17908b2cc0654Jeff Vander Stoep raise IndexError("Invalid index (edges only have 2 items): {0}".format(index)) 624