Jeff Vander Stoep | 74e4f93 | 2016-02-08 15:27:10 -0800 | [diff] [blame] | 1 | # Authors: Karl MacMillan <kmacmillan@mentalrootkit.com> |
| 2 | # |
| 3 | # Copyright (C) 2006 Red Hat |
| 4 | # see file 'COPYING' for use and warranty information |
| 5 | # |
| 6 | # This program is free software; you can redistribute it and/or |
| 7 | # modify it under the terms of the GNU General Public License as |
| 8 | # published by the Free Software Foundation; version 2 only |
| 9 | # |
| 10 | # This program 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 General Public License for more details. |
| 14 | # |
| 15 | # You should have received a copy of the GNU General Public License |
| 16 | # along with this program; if not, write to the Free Software |
| 17 | # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
| 18 | # |
| 19 | |
| 20 | """ |
| 21 | Classes and algorithms for matching requested access to access vectors. |
| 22 | """ |
| 23 | |
| 24 | import itertools |
| 25 | |
| 26 | from . import access |
| 27 | from . import objectmodel |
| 28 | from . import util |
| 29 | |
| 30 | |
| 31 | class Match(util.Comparison): |
| 32 | def __init__(self, interface=None, dist=0): |
| 33 | self.interface = interface |
| 34 | self.dist = dist |
| 35 | self.info_dir_change = False |
| 36 | # when implementing __eq__ also __hash__ is needed on py2 |
| 37 | # if object is muttable __hash__ should be None |
| 38 | self.__hash__ = None |
| 39 | |
| 40 | def _compare(self, other, method): |
| 41 | try: |
| 42 | a = (self.dist, self.info_dir_change) |
| 43 | b = (other.dist, other.info_dir_change) |
| 44 | return method(a, b) |
| 45 | except (AttributeError, TypeError): |
| 46 | # trying to compare to foreign type |
| 47 | return NotImplemented |
| 48 | |
| 49 | class MatchList: |
| 50 | DEFAULT_THRESHOLD = 150 |
| 51 | def __init__(self): |
| 52 | # Match objects that pass the threshold |
| 53 | self.children = [] |
| 54 | # Match objects over the threshold |
| 55 | self.bastards = [] |
| 56 | self.threshold = self.DEFAULT_THRESHOLD |
| 57 | self.allow_info_dir_change = False |
| 58 | self.av = None |
| 59 | |
| 60 | def best(self): |
| 61 | if len(self.children): |
| 62 | return self.children[0] |
| 63 | if len(self.bastards): |
| 64 | return self.bastards[0] |
| 65 | return None |
| 66 | |
| 67 | def __len__(self): |
| 68 | # Only return the length of the matches so |
| 69 | # that this can be used to test if there is |
| 70 | # a match. |
| 71 | return len(self.children) + len(self.bastards) |
| 72 | |
| 73 | def __iter__(self): |
| 74 | return iter(self.children) |
| 75 | |
| 76 | def all(self): |
| 77 | return itertools.chain(self.children, self.bastards) |
| 78 | |
| 79 | def append(self, match): |
| 80 | if match.dist <= self.threshold: |
| 81 | if not match.info_dir_change or self.allow_info_dir_change: |
| 82 | self.children.append(match) |
| 83 | else: |
| 84 | self.bastards.append(match) |
| 85 | else: |
| 86 | self.bastards.append(match) |
| 87 | |
| 88 | def sort(self): |
| 89 | self.children.sort() |
| 90 | self.bastards.sort() |
| 91 | |
| 92 | |
| 93 | class AccessMatcher: |
| 94 | def __init__(self, perm_maps=None): |
| 95 | self.type_penalty = 10 |
| 96 | self.obj_penalty = 10 |
| 97 | if perm_maps: |
| 98 | self.perm_maps = perm_maps |
| 99 | else: |
| 100 | self.perm_maps = objectmodel.PermMappings() |
| 101 | # We want a change in the information flow direction |
| 102 | # to be a strong penalty - stronger than access to |
| 103 | # a few unrelated types. |
| 104 | self.info_dir_penalty = 100 |
| 105 | |
| 106 | def type_distance(self, a, b): |
| 107 | if a == b or access.is_idparam(b): |
| 108 | return 0 |
| 109 | else: |
| 110 | return -self.type_penalty |
| 111 | |
| 112 | |
| 113 | def perm_distance(self, av_req, av_prov): |
| 114 | # First check that we have enough perms |
| 115 | diff = av_req.perms.difference(av_prov.perms) |
| 116 | |
| 117 | if len(diff) != 0: |
| 118 | total = self.perm_maps.getdefault_distance(av_req.obj_class, diff) |
| 119 | return -total |
| 120 | else: |
| 121 | diff = av_prov.perms.difference(av_req.perms) |
| 122 | return self.perm_maps.getdefault_distance(av_req.obj_class, diff) |
| 123 | |
| 124 | def av_distance(self, req, prov): |
| 125 | """Determine the 'distance' between 2 access vectors. |
| 126 | |
| 127 | This function is used to find an access vector that matches |
| 128 | a 'required' access. To do this we comput a signed numeric |
| 129 | value that indicates how close the req access is to the |
| 130 | 'provided' access vector. The closer the value is to 0 |
| 131 | the closer the match, with 0 being an exact match. |
| 132 | |
| 133 | A value over 0 indicates that the prov access vector provides more |
| 134 | access than the req (in practice, this means that the source type, |
| 135 | target type, and object class is the same and the perms in prov is |
| 136 | a superset of those in req. |
| 137 | |
| 138 | A value under 0 indicates that the prov access less - or unrelated |
| 139 | - access to the req access. A different type or object class will |
| 140 | result in a very low value. |
| 141 | |
| 142 | The values other than 0 should only be interpreted relative to |
| 143 | one another - they have no exact meaning and are likely to |
| 144 | change. |
| 145 | |
| 146 | Params: |
| 147 | req - [AccessVector] The access that is required. This is the |
| 148 | access being matched. |
| 149 | prov - [AccessVector] The access provided. This is the potential |
| 150 | match that is being evaluated for req. |
| 151 | Returns: |
| 152 | 0 : Exact match between the acess vectors. |
| 153 | |
| 154 | < 0 : The prov av does not provide all of the access in req. |
| 155 | A smaller value indicates that the access is further. |
| 156 | |
| 157 | > 0 : The prov av provides more access than req. The larger |
| 158 | the value the more access over req. |
| 159 | """ |
| 160 | # FUTURE - this is _very_ expensive and probably needs some |
| 161 | # thorough performance work. This version is meant to give |
| 162 | # meaningful results relatively simply. |
| 163 | dist = 0 |
| 164 | |
| 165 | # Get the difference between the types. The addition is safe |
| 166 | # here because type_distance only returns 0 or negative. |
| 167 | dist += self.type_distance(req.src_type, prov.src_type) |
| 168 | dist += self.type_distance(req.tgt_type, prov.tgt_type) |
| 169 | |
| 170 | # Object class distance |
| 171 | if req.obj_class != prov.obj_class and not access.is_idparam(prov.obj_class): |
| 172 | dist -= self.obj_penalty |
| 173 | |
| 174 | # Permission distance |
| 175 | |
| 176 | # If this av doesn't have a matching source type, target type, and object class |
| 177 | # count all of the permissions against it. Otherwise determine the perm |
| 178 | # distance and dir. |
| 179 | if dist < 0: |
| 180 | pdist = self.perm_maps.getdefault_distance(prov.obj_class, prov.perms) |
| 181 | else: |
| 182 | pdist = self.perm_distance(req, prov) |
| 183 | |
| 184 | # Combine the perm and other distance |
| 185 | if dist < 0: |
| 186 | if pdist < 0: |
| 187 | return dist + pdist |
| 188 | else: |
| 189 | return dist - pdist |
| 190 | elif dist >= 0: |
| 191 | if pdist < 0: |
| 192 | return pdist - dist |
| 193 | else: |
| 194 | return dist + pdist |
| 195 | |
| 196 | def av_set_match(self, av_set, av): |
| 197 | """ |
| 198 | |
| 199 | """ |
| 200 | dist = None |
| 201 | |
| 202 | # Get the distance for each access vector |
| 203 | for x in av_set: |
| 204 | tmp = self.av_distance(av, x) |
| 205 | if dist is None: |
| 206 | dist = tmp |
| 207 | elif tmp >= 0: |
| 208 | if dist >= 0: |
| 209 | dist += tmp |
| 210 | else: |
| 211 | dist = tmp + -dist |
| 212 | else: |
| 213 | if dist < 0: |
| 214 | dist += tmp |
| 215 | else: |
| 216 | dist -= tmp |
| 217 | |
| 218 | # Penalize for information flow - we want to prevent the |
| 219 | # addition of a write if the requested is read none. We are |
| 220 | # much less concerned about the reverse. |
| 221 | av_dir = self.perm_maps.getdefault_direction(av.obj_class, av.perms) |
| 222 | |
| 223 | if av_set.info_dir is None: |
| 224 | av_set.info_dir = objectmodel.FLOW_NONE |
| 225 | for x in av_set: |
| 226 | av_set.info_dir = av_set.info_dir | \ |
| 227 | self.perm_maps.getdefault_direction(x.obj_class, x.perms) |
| 228 | if (av_dir & objectmodel.FLOW_WRITE == 0) and (av_set.info_dir & objectmodel.FLOW_WRITE): |
| 229 | if dist < 0: |
| 230 | dist -= self.info_dir_penalty |
| 231 | else: |
| 232 | dist += self.info_dir_penalty |
| 233 | |
| 234 | return dist |
| 235 | |
| 236 | def search_ifs(self, ifset, av, match_list): |
| 237 | match_list.av = av |
| 238 | for iv in itertools.chain(ifset.tgt_type_all, |
| 239 | ifset.tgt_type_map.get(av.tgt_type, [])): |
| 240 | if not iv.enabled: |
| 241 | #print "iv %s not enabled" % iv.name |
| 242 | continue |
| 243 | |
| 244 | dist = self.av_set_match(iv.access, av) |
| 245 | if dist >= 0: |
| 246 | m = Match(iv, dist) |
| 247 | match_list.append(m) |
| 248 | |
| 249 | |
| 250 | match_list.sort() |
| 251 | |
| 252 | |