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