1 # Copyright 2014-2015, Tresys Technology, LLC 2 # 3 # This file is part of SETools. 4 # 5 # SETools is free software: you can redistribute it and/or modify 6 # it under the terms of the GNU Lesser General Public License as 7 # published by the Free Software Foundation, either version 2.1 of 8 # the License, or (at your option) any later version. 9 # 10 # SETools is distributed in the hope that it will be useful, 11 # but WITHOUT ANY WARRANTY; without even the implied warranty of 12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 # GNU Lesser General Public License for more details. 14 # 15 # You should have received a copy of the GNU Lesser General Public 16 # License along with SETools. If not, see 17 # <http://www.gnu.org/licenses/>. 18 # 19 import itertools 20 import logging 21 from collections import namedtuple 22 23 import networkx as nx 24 from networkx.exception import NetworkXError, NetworkXNoPath 25 26 from .descriptors import EdgeAttrIntMax, EdgeAttrList 27 28 __all__ = ['InfoFlowAnalysis'] 29 30 # Return values for the analysis 31 # are in the following tuple format: 32 step_output = namedtuple("step", ["source", 33 "target", 34 "rules"]) 35 36 37 class InfoFlowAnalysis(object): 38 39 """Information flow analysis.""" 40 41 def __init__(self, policy, perm_map, min_weight=1, exclude=None): 42 """ 43 Parameters: 44 policy The policy to analyze. 45 perm_map The permission map or path to the permission map file. 46 minweight The minimum permission weight to include in the analysis. 47 (default is 1) 48 exclude The types excluded from the information flow analysis. 49 (default is none) 50 """ 51 self.log = logging.getLogger(self.__class__.__name__) 52 53 self.policy = policy 54 55 self.min_weight = min_weight 56 self.perm_map = perm_map 57 self.exclude = exclude 58 self.rebuildgraph = True 59 self.rebuildsubgraph = True 60 61 self.G = nx.DiGraph() 62 self.subG = None 63 64 @property 65 def min_weight(self): 66 return self._min_weight 67 68 @min_weight.setter 69 def min_weight(self, weight): 70 if not 1 <= weight <= 10: 71 raise ValueError( 72 "Min information flow weight must be an integer 1-10.") 73 74 self._min_weight = weight 75 self.rebuildsubgraph = True 76 77 @property 78 def perm_map(self): 79 return self._perm_map 80 81 @perm_map.setter 82 def perm_map(self, perm_map): 83 self._perm_map = perm_map 84 self.rebuildgraph = True 85 self.rebuildsubgraph = True 86 87 @property 88 def exclude(self): 89 return self._exclude 90 91 @exclude.setter 92 def exclude(self, types): 93 if types: 94 self._exclude = [self.policy.lookup_type(t) for t in types] 95 else: 96 self._exclude = [] 97 98 self.rebuildsubgraph = True 99 100 def shortest_path(self, source, target): 101 """ 102 Generator which yields one shortest path between the source 103 and target types (there may be more). 104 105 Parameters: 106 source The source type. 107 target The target type. 108 109 Yield: generator(steps) 110 111 steps Yield: tuple(source, target, rules) 112 113 source The source type for this step of the information flow. 114 target The target type for this step of the information flow. 115 rules The list of rules creating this information flow step. 116 """ 117 s = self.policy.lookup_type(source) 118 t = self.policy.lookup_type(target) 119 120 if self.rebuildsubgraph: 121 self._build_subgraph() 122 123 self.log.info("Generating one shortest path from {0} to {1}...".format(s, t)) 124 125 try: 126 yield self.__generate_steps(nx.shortest_path(self.subG, s, t)) 127 except (NetworkXNoPath, NetworkXError): 128 # NetworkXError: the type is valid but not in graph, e.g. 129 # excluded or disconnected due to min weight 130 # NetworkXNoPath: no paths or the target type is 131 # not in the graph 132 pass 133 134 def all_paths(self, source, target, maxlen=2): 135 """ 136 Generator which yields all paths between the source and target 137 up to the specified maximum path length. This algorithm 138 tends to get very expensive above 3-5 steps, depending 139 on the policy complexity. 140 141 Parameters: 142 source The source type. 143 target The target type. 144 maxlen Maximum length of paths. 145 146 Yield: generator(steps) 147 148 steps Yield: tuple(source, target, rules) 149 150 source The source type for this step of the information flow. 151 target The target type for this step of the information flow. 152 rules The list of rules creating this information flow step. 153 """ 154 if maxlen < 1: 155 raise ValueError("Maximum path length must be positive.") 156 157 s = self.policy.lookup_type(source) 158 t = self.policy.lookup_type(target) 159 160 if self.rebuildsubgraph: 161 self._build_subgraph() 162 163 self.log.info("Generating all paths from {0} to {1}, max len {2}...".format(s, t, maxlen)) 164 165 try: 166 for path in nx.all_simple_paths(self.subG, s, t, maxlen): 167 yield self.__generate_steps(path) 168 except (NetworkXNoPath, NetworkXError): 169 # NetworkXError: the type is valid but not in graph, e.g. 170 # excluded or disconnected due to min weight 171 # NetworkXNoPath: no paths or the target type is 172 # not in the graph 173 pass 174 175 def all_shortest_paths(self, source, target): 176 """ 177 Generator which yields all shortest paths between the source 178 and target types. 179 180 Parameters: 181 source The source type. 182 target The target type. 183 184 Yield: generator(steps) 185 186 steps Yield: tuple(source, target, rules) 187 188 source The source type for this step of the information flow. 189 target The target type for this step of the information flow. 190 rules The list of rules creating this information flow step. 191 """ 192 s = self.policy.lookup_type(source) 193 t = self.policy.lookup_type(target) 194 195 if self.rebuildsubgraph: 196 self._build_subgraph() 197 198 self.log.info("Generating all shortest paths from {0} to {1}...".format(s, t)) 199 200 try: 201 for path in nx.all_shortest_paths(self.subG, s, t): 202 yield self.__generate_steps(path) 203 except (NetworkXNoPath, NetworkXError, KeyError): 204 # NetworkXError: the type is valid but not in graph, e.g. 205 # excluded or disconnected due to min weight 206 # NetworkXNoPath: no paths or the target type is 207 # not in the graph 208 # KeyError: work around NetworkX bug 209 # when the source node is not in the graph 210 pass 211 212 def infoflows(self, type_, out=True): 213 """ 214 Generator which yields all information flows in/out of a 215 specified source type. 216 217 Parameters: 218 source The starting type. 219 220 Keyword Parameters: 221 out If true, information flows out of the type will 222 be returned. If false, information flows in to the 223 type will be returned. Default is true. 224 225 Yield: generator(steps) 226 227 steps A generator that returns the tuple of 228 source, target, and rules for each 229 information flow. 230 """ 231 s = self.policy.lookup_type(type_) 232 233 if self.rebuildsubgraph: 234 self._build_subgraph() 235 236 self.log.info("Generating all infoflows out of {0}...".format(s)) 237 238 if out: 239 flows = self.subG.out_edges_iter(s) 240 else: 241 flows = self.subG.in_edges_iter(s) 242 243 try: 244 for source, target in flows: 245 edge = Edge(self.subG, source, target) 246 yield step_output(source, target, edge.rules) 247 except NetworkXError: 248 # NetworkXError: the type is valid but not in graph, e.g. 249 # excluded or disconnected due to min weight 250 pass 251 252 def get_stats(self): # pragma: no cover 253 """ 254 Get the information flow graph statistics. 255 256 Return: tuple(nodes, edges) 257 258 nodes The number of nodes (types) in the graph. 259 edges The number of edges (information flows between types) 260 in the graph. 261 """ 262 return (self.G.number_of_nodes(), self.G.number_of_edges()) 263 264 # 265 # Internal functions follow 266 # 267 268 def __generate_steps(self, path): 269 """ 270 Generator which returns the source, target, and associated rules 271 for each information flow step. 272 273 Parameter: 274 path A list of graph node names representing an information flow path. 275 276 Yield: tuple(source, target, rules) 277 278 source The source type for this step of the information flow. 279 target The target type for this step of the information flow. 280 rules The list of rules creating this information flow step. 281 """ 282 for s in range(1, len(path)): 283 edge = Edge(self.subG, path[s - 1], path[s]) 284 yield step_output(edge.source, edge.target, edge.rules) 285 286 # 287 # 288 # Graph building functions 289 # 290 # 291 # 1. _build_graph determines the flow in each direction for each TE 292 # rule and then expands the rule. All information flows are 293 # included in this main graph: memory is traded off for efficiency 294 # as the main graph should only need to be rebuilt if permission 295 # weights change. 296 # 2. _build_subgraph derives a subgraph which removes all excluded 297 # types (nodes) and edges (information flows) which are below the 298 # minimum weight. This subgraph is rebuilt only if the main graph 299 # is rebuilt or the minimum weight or excluded types change. 300 301 def _build_graph(self): 302 self.G.clear() 303 304 self.perm_map.map_policy(self.policy) 305 306 self.log.info("Building graph from {0}...".format(self.policy)) 307 308 for rule in self.policy.terules(): 309 if rule.ruletype != "allow": 310 continue 311 312 (rweight, wweight) = self.perm_map.rule_weight(rule) 313 314 for s, t in itertools.product(rule.source.expand(), rule.target.expand()): 315 # only add flows if they actually flow 316 # in or out of the source type type 317 if s != t: 318 if wweight: 319 edge = Edge(self.G, s, t, create=True) 320 edge.rules.append(rule) 321 edge.weight = wweight 322 323 if rweight: 324 edge = Edge(self.G, t, s, create=True) 325 edge.rules.append(rule) 326 edge.weight = rweight 327 328 self.rebuildgraph = False 329 self.rebuildsubgraph = True 330 self.log.info("Completed building graph.") 331 332 def _build_subgraph(self): 333 if self.rebuildgraph: 334 self._build_graph() 335 336 self.log.info("Building subgraph...") 337 self.log.debug("Excluding {0!r}".format(self.exclude)) 338 self.log.debug("Min weight {0}".format(self.min_weight)) 339 340 # delete excluded types from subgraph 341 nodes = [n for n in self.G.nodes() if n not in self.exclude] 342 self.subG = self.G.subgraph(nodes) 343 344 # delete edges below minimum weight. 345 # no need if weight is 1, since that 346 # does not exclude any edges. 347 if self.min_weight > 1: 348 delete_list = [] 349 for s, t in self.subG.edges_iter(): 350 edge = Edge(self.subG, s, t) 351 if edge.weight < self.min_weight: 352 delete_list.append(edge) 353 354 self.subG.remove_edges_from(delete_list) 355 356 self.rebuildsubgraph = False 357 self.log.info("Completed building subgraph.") 358 359 360 class Edge(object): 361 362 """ 363 A graph edge. Also used for returning information flow steps. 364 365 Parameters: 366 source The source type of the edge. 367 target The target type of the edge. 368 369 Keyword Parameters: 370 create (T/F) create the edge if it does not exist. 371 The default is False. 372 """ 373 374 rules = EdgeAttrList('rules') 375 376 # use capacity to store the info flow weight so 377 # we can use network flow algorithms naturally. 378 # The weight for each edge is 1 since each info 379 # flow step is no more costly than another 380 # (see below add_edge() call) 381 weight = EdgeAttrIntMax('capacity') 382 383 def __init__(self, graph, source, target, create=False): 384 self.G = graph 385 self.source = source 386 self.target = target 387 388 # a bit of a hack to make edges work 389 # in NetworkX functions that work on 390 # 2-tuples of (source, target) 391 # (see __getitem__ below) 392 self.st_tuple = (source, target) 393 394 if not self.G.has_edge(source, target): 395 if create: 396 self.G.add_edge(source, target, weight=1) 397 self.rules = None 398 self.weight = None 399 else: 400 raise ValueError("Edge does not exist in graph") 401 402 def __getitem__(self, key): 403 return self.st_tuple[key] 404
