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