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