RPKI Engine 1.0
|
00001 """ 00002 Classes dealing with sets of resources. 00003 00004 The basic mechanics of a resource set are the same for any of the 00005 resources we handle (ASNs, IPv4 addresses, or IPv6 addresses), so we 00006 can provide the same operations on any of them, even though the 00007 underlying details vary. 00008 00009 We also provide some basic set operations (union, intersection, etc). 00010 00011 $Id: resource_set.py 3688 2011-02-24 00:00:05Z melkins $ 00012 00013 Copyright (C) 2009--2010 Internet Systems Consortium ("ISC") 00014 00015 Permission to use, copy, modify, and distribute this software for any 00016 purpose with or without fee is hereby granted, provided that the above 00017 copyright notice and this permission notice appear in all copies. 00018 00019 THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 00020 REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 00021 AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 00022 INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 00023 LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 00024 OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 00025 PERFORMANCE OF THIS SOFTWARE. 00026 00027 Portions copyright (C) 2007--2008 American Registry for Internet Numbers ("ARIN") 00028 00029 Permission to use, copy, modify, and distribute this software for any 00030 purpose with or without fee is hereby granted, provided that the above 00031 copyright notice and this permission notice appear in all copies. 00032 00033 THE SOFTWARE IS PROVIDED "AS IS" AND ARIN DISCLAIMS ALL WARRANTIES WITH 00034 REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 00035 AND FITNESS. IN NO EVENT SHALL ARIN BE LIABLE FOR ANY SPECIAL, DIRECT, 00036 INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 00037 LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 00038 OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 00039 PERFORMANCE OF THIS SOFTWARE. 00040 """ 00041 00042 import re, math 00043 import rpki.ipaddrs, rpki.oids, rpki.exceptions 00044 00045 ## @var inherit_token 00046 # Token used to indicate inheritance in read and print syntax. 00047 00048 inherit_token = "<inherit>" 00049 00050 re_asn_range = re.compile("^([0-9]+)-([0-9]+)$") 00051 re_address_range = re.compile("^([0-9:.a-fA-F]+)-([0-9:.a-fA-F]+)$") 00052 re_prefix_with_maxlen = re.compile("^([0-9:.a-fA-F]+)/([0-9]+)-([0-9]+)$") 00053 re_prefix = re.compile("^([0-9:.a-fA-F]+)/([0-9]+)$") 00054 00055 class resource_range(object): 00056 """ 00057 Generic resource range type. Assumes underlying type is some kind 00058 of integer. 00059 00060 This is a virtual class. You probably don't want to use this type 00061 directly. 00062 """ 00063 00064 def __init__(self, min, max): 00065 """ 00066 Initialize and sanity check a resource_range. 00067 """ 00068 assert min.__class__ is max.__class__, "Type mismatch, %r doesn't match %r" % (min.__class__, max.__class__) 00069 assert min <= max, "Mis-ordered range: %s before %s" % (min, max) 00070 self.min = min 00071 self.max = max 00072 00073 def __cmp__(self, other): 00074 """ 00075 Compare two resource_range objects. 00076 """ 00077 assert self.__class__ is other.__class__, "Type mismatch, comparing %r with %r" % (self.__class__, other.__class__) 00078 return cmp(self.min, other.min) or cmp(self.max, other.max) 00079 00080 class resource_range_as(resource_range): 00081 """ 00082 Range of Autonomous System Numbers. 00083 00084 Denotes a single ASN by a range whose min and max values are 00085 identical. 00086 """ 00087 00088 ## @var datum_type 00089 # Type of underlying data (min and max). 00090 00091 datum_type = long 00092 00093 def __str__(self): 00094 """ 00095 Convert a resource_range_as to string format. 00096 """ 00097 if self.min == self.max: 00098 return str(self.min) 00099 else: 00100 return str(self.min) + "-" + str(self.max) 00101 00102 def to_rfc3779_tuple(self): 00103 """ 00104 Convert a resource_range_as to tuple format for RFC 3779 ASN.1 encoding. 00105 """ 00106 if self.min == self.max: 00107 return ("id", self.min) 00108 else: 00109 return ("range", (self.min, self.max)) 00110 00111 @classmethod 00112 def parse_str(cls, x): 00113 """ 00114 Parse ASN resource range from text (eg, XML attributes). 00115 """ 00116 r = re_asn_range.match(x) 00117 if r: 00118 return cls(long(r.group(1)), long(r.group(2))) 00119 else: 00120 return cls(long(x), long(x)) 00121 00122 @classmethod 00123 def from_strings(cls, a, b = None): 00124 """ 00125 Construct ASN range from strings. 00126 """ 00127 if b is None: 00128 b = a 00129 return cls(long(a), long(b)) 00130 00131 class resource_range_ip(resource_range): 00132 """ 00133 Range of (generic) IP addresses. 00134 00135 Prefixes are converted to ranges on input, and ranges that can be 00136 represented as prefixes are written as prefixes on output. 00137 00138 This is a virtual class. You probably don't want to use it 00139 directly. 00140 """ 00141 00142 def prefixlen(self): 00143 """ 00144 Determine whether a resource_range_ip can be expressed as a 00145 prefix. Returns prefix length if it can, otherwise raises 00146 MustBePrefix exception. 00147 """ 00148 mask = self.min ^ self.max 00149 if self.min & mask != 0: 00150 raise rpki.exceptions.MustBePrefix 00151 prefixlen = self.datum_type.bits 00152 while mask & 1: 00153 prefixlen -= 1 00154 mask >>= 1 00155 if mask: 00156 raise rpki.exceptions.MustBePrefix 00157 return prefixlen 00158 00159 # Backwards compatability, will go away at some point 00160 _prefixlen = prefixlen 00161 00162 def __str__(self): 00163 """ 00164 Convert a resource_range_ip to string format. 00165 """ 00166 try: 00167 return str(self.min) + "/" + str(self.prefixlen()) 00168 except rpki.exceptions.MustBePrefix: 00169 return str(self.min) + "-" + str(self.max) 00170 00171 def to_rfc3779_tuple(self): 00172 """ 00173 Convert a resource_range_ip to tuple format for RFC 3779 ASN.1 00174 encoding. 00175 """ 00176 try: 00177 return ("addressPrefix", _long2bs(self.min, self.datum_type.bits, 00178 prefixlen = self.prefixlen())) 00179 except rpki.exceptions.MustBePrefix: 00180 return ("addressRange", (_long2bs(self.min, self.datum_type.bits, strip = 0), 00181 _long2bs(self.max, self.datum_type.bits, strip = 1))) 00182 00183 @classmethod 00184 def parse_str(cls, x): 00185 """ 00186 Parse IP address range or prefix from text (eg, XML attributes). 00187 """ 00188 r = re_address_range.match(x) 00189 if r: 00190 return cls(cls.datum_type(r.group(1)), cls.datum_type(r.group(2))) 00191 r = re_prefix.match(x) 00192 if r: 00193 return cls.make_prefix(cls.datum_type(r.group(1)), int(r.group(2))) 00194 raise rpki.exceptions.BadIPResource, 'Bad IP resource "%s"' % (x) 00195 00196 @classmethod 00197 def make_prefix(cls, prefix, prefixlen): 00198 """ 00199 Construct a resource range corresponding to a prefix. 00200 """ 00201 assert isinstance(prefix, cls.datum_type) and isinstance(prefixlen, (int, long)) 00202 assert prefixlen >= 0 and prefixlen <= cls.datum_type.bits, "Nonsensical prefix length: %s" % prefixlen 00203 mask = (1 << (cls.datum_type.bits - prefixlen)) - 1 00204 assert (prefix & mask) == 0, "Resource not in canonical form: %s/%s" % (prefix, prefixlen) 00205 return cls(cls.datum_type(prefix), cls.datum_type(prefix | mask)) 00206 00207 def chop_into_prefixes(self, result): 00208 """ 00209 Chop up a resource_range_ip into ranges that can be represented as 00210 prefixes. 00211 """ 00212 try: 00213 self.prefixlen() 00214 result.append(self) 00215 except rpki.exceptions.MustBePrefix: 00216 min = self.min 00217 max = self.max 00218 while max >= min: 00219 bits = int(math.log(max - min + 1, 2)) 00220 while True: 00221 mask = ~(~0 << bits) 00222 assert min + mask <= max 00223 if min & mask == 0: 00224 break 00225 assert bits > 0 00226 bits -= 1 00227 result.append(self.make_prefix(min, self.datum_type.bits - bits)) 00228 min = self.datum_type(min + mask + 1) 00229 00230 @classmethod 00231 def from_strings(cls, a, b = None): 00232 """ 00233 Construct IP address range from strings. 00234 """ 00235 if b is None: 00236 b = a 00237 a = rpki.ipaddrs.parse(a) 00238 b = rpki.ipaddrs.parse(b) 00239 if a.__class__ is not b.__class__: 00240 raise TypeError 00241 if cls is resource_range_ip: 00242 if isinstance(a, rpki.ipaddrs.v4addr): 00243 return resource_range_ipv4(a, b) 00244 if isinstance(a, rpki.ipaddrs.v6addr): 00245 return resource_range_ipv6(a, b) 00246 elif isinstance(a, cls.datum_type): 00247 return cls(a, b) 00248 raise TypeError 00249 00250 class resource_range_ipv4(resource_range_ip): 00251 """ 00252 Range of IPv4 addresses. 00253 """ 00254 00255 ## @var datum_type 00256 # Type of underlying data (min and max). 00257 00258 datum_type = rpki.ipaddrs.v4addr 00259 00260 class resource_range_ipv6(resource_range_ip): 00261 """ 00262 Range of IPv6 addresses. 00263 """ 00264 00265 ## @var datum_type 00266 # Type of underlying data (min and max). 00267 00268 datum_type = rpki.ipaddrs.v6addr 00269 00270 def _rsplit(rset, that): 00271 """ 00272 Utility function to split a resource range into two resource ranges. 00273 """ 00274 this = rset.pop(0) 00275 cell_type = type(this.min) 00276 assert type(this) is type(that) and type(this.max) is cell_type and \ 00277 type(that.min) is cell_type and type(that.max) is cell_type 00278 if this.min < that.min: 00279 rset.insert(0, type(this)(this.min, cell_type(that.min - 1))) 00280 rset.insert(1, type(this)(that.min, this.max)) 00281 else: 00282 assert this.max > that.max 00283 rset.insert(0, type(this)(this.min, that.max)) 00284 rset.insert(1, type(this)(cell_type(that.max + 1), this.max)) 00285 00286 class resource_set(list): 00287 """ 00288 Generic resource set, a list subclass containing resource ranges. 00289 00290 This is a virtual class. You probably don't want to use it 00291 directly. 00292 """ 00293 00294 ## @var inherit 00295 # Boolean indicating whether this resource_set uses RFC 3779 inheritance. 00296 00297 inherit = False 00298 00299 ## @var canonical 00300 # Whether this resource_set is currently in canonical form. 00301 00302 canonical = False 00303 00304 def __init__(self, ini = None): 00305 """ 00306 Initialize a resource_set. 00307 """ 00308 list.__init__(self) 00309 if isinstance(ini, (int, long)): 00310 ini = str(ini) 00311 if ini is inherit_token: 00312 self.inherit = True 00313 elif isinstance(ini, str) and len(ini): 00314 self.extend(self.parse_str(s) for s in ini.split(",")) 00315 elif isinstance(ini, tuple): 00316 self.parse_rfc3779_tuple(ini) 00317 elif isinstance(ini, list): 00318 self.extend(ini) 00319 else: 00320 assert ini is None or (isinstance(ini, str) and ini == ""), "Unexpected initializer: %s" % str(ini) 00321 self.canonize() 00322 00323 def canonize(self): 00324 """ 00325 Whack this resource_set into canonical form. 00326 """ 00327 assert not self.inherit or not self 00328 if not self.canonical: 00329 self.sort() 00330 for i in xrange(len(self) - 2, -1, -1): 00331 if self[i].max + 1 == self[i+1].min: 00332 self[i] = type(self[i])(self[i].min, self[i+1].max) 00333 self.pop(i + 1) 00334 if __debug__: 00335 for i in xrange(0, len(self) - 1): 00336 assert self[i].max < self[i+1].min, "Resource overlap: %s %s" % (self[i], self[i+1]) 00337 self.canonical = True 00338 00339 def append(self, item): 00340 """ 00341 Wrapper around list.append() (q.v.) to reset canonical flag. 00342 """ 00343 list.append(self, item) 00344 self.canonical = False 00345 00346 def extend(self, item): 00347 """ 00348 Wrapper around list.extend() (q.v.) to reset canonical flag. 00349 """ 00350 list.extend(self, item) 00351 self.canonical = False 00352 00353 def __str__(self): 00354 """ 00355 Convert a resource_set to string format. 00356 """ 00357 if self.inherit: 00358 return inherit_token 00359 else: 00360 return ",".join(str(x) for x in self) 00361 00362 def _comm(self, other): 00363 """ 00364 Like comm(1), sort of. 00365 00366 Returns a tuple of three resource sets: resources only in self, 00367 resources only in other, and resources in both. Used (not very 00368 efficiently) as the basis for most set operations on resource 00369 sets. 00370 """ 00371 00372 assert not self.inherit 00373 assert type(self) is type(other), "Type mismatch %r %r" % (type(self), type(other)) 00374 set1 = type(self)(self) # clone and whack into canonical form 00375 set2 = type(other)(other) # ditto 00376 only1, only2, both = [], [], [] 00377 while set1 or set2: 00378 if set1 and (not set2 or set1[0].max < set2[0].min): 00379 only1.append(set1.pop(0)) 00380 elif set2 and (not set1 or set2[0].max < set1[0].min): 00381 only2.append(set2.pop(0)) 00382 elif set1[0].min < set2[0].min: 00383 _rsplit(set1, set2[0]) 00384 elif set2[0].min < set1[0].min: 00385 _rsplit(set2, set1[0]) 00386 elif set1[0].max < set2[0].max: 00387 _rsplit(set2, set1[0]) 00388 elif set2[0].max < set1[0].max: 00389 _rsplit(set1, set2[0]) 00390 else: 00391 assert set1[0].min == set2[0].min and set1[0].max == set2[0].max 00392 both.append(set1.pop(0)) 00393 set2.pop(0) 00394 return type(self)(only1), type(self)(only2), type(self)(both) 00395 00396 def union(self, other): 00397 """ 00398 Set union for resource sets. 00399 """ 00400 00401 assert not self.inherit 00402 assert type(self) is type(other), "Type mismatch: %r %r" % (type(self), type(other)) 00403 set1 = type(self)(self) # clone and whack into canonical form 00404 set2 = type(other)(other) # ditto 00405 result = [] 00406 while set1 or set2: 00407 if set1 and (not set2 or set1[0].max < set2[0].min): 00408 result.append(set1.pop(0)) 00409 elif set2 and (not set1 or set2[0].max < set1[0].min): 00410 result.append(set2.pop(0)) 00411 else: 00412 this = set1.pop(0) 00413 that = set2.pop(0) 00414 assert type(this) is type(that) 00415 if this.min < that.min: min = this.min 00416 else: min = that.min 00417 if this.max > that.max: max = this.max 00418 else: max = that.max 00419 result.append(type(this)(min, max)) 00420 while set1 and set1[0].max <= max: 00421 assert set1[0].min >= min 00422 del set1[0] 00423 while set2 and set2[0].max <= max: 00424 assert set2[0].min >= min 00425 del set2[0] 00426 return type(self)(result) 00427 00428 def intersection(self, other): 00429 """ 00430 Set intersection for resource sets. 00431 """ 00432 return self._comm(other)[2] 00433 00434 def difference(self, other): 00435 """ 00436 Set difference for resource sets. 00437 """ 00438 return self._comm(other)[0] 00439 00440 def symmetric_difference(self, other): 00441 """ 00442 Set symmetric difference (XOR) for resource sets. 00443 """ 00444 com = self._comm(other) 00445 return com[0].union(com[1]) 00446 00447 def contains(self, item): 00448 """ 00449 Set membership test for resource sets. 00450 """ 00451 assert not self.inherit 00452 self.canonize() 00453 if not self: 00454 return False 00455 if type(item) is type(self[0]): 00456 min = item.min 00457 max = item.max 00458 else: 00459 min = item 00460 max = item 00461 lo = 0 00462 hi = len(self) 00463 while lo < hi: 00464 mid = (lo + hi) / 2 00465 if self[mid].max < max: 00466 lo = mid + 1 00467 else: 00468 hi = mid 00469 return lo < len(self) and self[lo].min <= min and self[lo].max >= max 00470 00471 def issubset(self, other): 00472 """ 00473 Test whether self is a subset (possibly improper) of other. 00474 """ 00475 for i in self: 00476 if not other.contains(i): 00477 return False 00478 return True 00479 00480 def issuperset(self, other): 00481 """ 00482 Test whether self is a superset (possibly improper) of other. 00483 """ 00484 return other.issubset(self) 00485 00486 @classmethod 00487 def from_sql(cls, sql, query, args = None): 00488 """ 00489 Create resource set from an SQL query. 00490 00491 sql is an object that supports execute() and fetchall() methods 00492 like a DB API 2.0 cursor object. 00493 00494 query is an SQL query that returns a sequence of (min, max) pairs. 00495 """ 00496 00497 sql.execute(query, args) 00498 return cls(ini = [cls.range_type(cls.range_type.datum_type(b), 00499 cls.range_type.datum_type(e)) 00500 for (b, e) in sql.fetchall()]) 00501 00502 @classmethod 00503 def parse_str(cls, s): 00504 """ 00505 Parse resource set from text string (eg, XML attributes). This is 00506 a backwards compatability wrapper, real functionality is now part 00507 of the range classes. 00508 """ 00509 return cls.range_type.parse_str(s) 00510 00511 class resource_set_as(resource_set): 00512 """ 00513 Autonomous System Number resource set. 00514 """ 00515 00516 ## @var range_type 00517 # Type of range underlying this type of resource_set. 00518 00519 range_type = resource_range_as 00520 00521 def parse_rfc3779_tuple(self, x): 00522 """ 00523 Parse ASN resource from tuple format generated by RFC 3779 ASN.1 00524 decoder. 00525 """ 00526 if x[0] == "asIdsOrRanges": 00527 for aor in x[1]: 00528 if aor[0] == "range": 00529 min = aor[1][0] 00530 max = aor[1][1] 00531 else: 00532 min = aor[1] 00533 max = min 00534 self.append(resource_range_as(min, max)) 00535 else: 00536 assert x[0] == "inherit" 00537 self.inherit = True 00538 00539 def to_rfc3779_tuple(self): 00540 """ 00541 Convert ASN resource set into tuple format used for RFC 3779 ASN.1 00542 encoding. 00543 """ 00544 self.canonize() 00545 if self: 00546 return ("asIdsOrRanges", tuple(a.to_rfc3779_tuple() for a in self)) 00547 elif self.inherit: 00548 return ("inherit", "") 00549 else: 00550 return None 00551 00552 class resource_set_ip(resource_set): 00553 """ 00554 (Generic) IP address resource set. 00555 00556 This is a virtual class. You probably don't want to use it 00557 directly. 00558 """ 00559 00560 def parse_rfc3779_tuple(self, x): 00561 """ 00562 Parse IP address resource sets from tuple format generated by RFC 00563 3779 ASN.1 decoder. 00564 """ 00565 if x[0] == "addressesOrRanges": 00566 for aor in x[1]: 00567 if aor[0] == "addressRange": 00568 min = _bs2long(aor[1][0], self.range_type.datum_type.bits, 0) 00569 max = _bs2long(aor[1][1], self.range_type.datum_type.bits, 1) 00570 else: 00571 min = _bs2long(aor[1], self.range_type.datum_type.bits, 0) 00572 max = _bs2long(aor[1], self.range_type.datum_type.bits, 1) 00573 self.append(self.range_type(self.range_type.datum_type(min), self.range_type.datum_type(max))) 00574 else: 00575 assert x[0] == "inherit" 00576 self.inherit = True 00577 00578 def to_roa_prefix_set(self): 00579 """ 00580 Convert from a resource set to a ROA prefix set. 00581 """ 00582 prefix_ranges = [] 00583 for r in self: 00584 r.chop_into_prefixes(prefix_ranges) 00585 return self.roa_prefix_set_type([ 00586 self.roa_prefix_set_type.prefix_type(r.min, r.prefixlen()) 00587 for r in prefix_ranges]) 00588 00589 def to_rfc3779_tuple(self): 00590 """ 00591 Convert IP resource set into tuple format used by RFC 3779 ASN.1 00592 encoder. 00593 """ 00594 self.canonize() 00595 if self: 00596 return (self.afi, ("addressesOrRanges", tuple(a.to_rfc3779_tuple() for a in self))) 00597 elif self.inherit: 00598 return (self.afi, ("inherit", "")) 00599 else: 00600 return None 00601 00602 class resource_set_ipv4(resource_set_ip): 00603 """ 00604 IPv4 address resource set. 00605 """ 00606 00607 ## @var range_type 00608 # Type of range underlying this type of resource_set. 00609 00610 range_type = resource_range_ipv4 00611 00612 ## @var afi 00613 # Address Family Identifier value for IPv4. 00614 00615 afi = "\x00\x01" 00616 00617 class resource_set_ipv6(resource_set_ip): 00618 """ 00619 IPv6 address resource set. 00620 """ 00621 00622 ## @var range_type 00623 # Type of range underlying this type of resource_set. 00624 00625 range_type = resource_range_ipv6 00626 00627 ## @var afi 00628 # Address Family Identifier value for IPv6. 00629 00630 afi = "\x00\x02" 00631 00632 def _bs2long(bs, addrlen, fill): 00633 """ 00634 Utility function to convert a bitstring (rpki.POW.pkix tuple 00635 representation) into a Python long. 00636 """ 00637 x = 0L 00638 for y in bs: 00639 x = (x << 1) | y 00640 for y in xrange(addrlen - len(bs)): 00641 x = (x << 1) | fill 00642 return x 00643 00644 def _long2bs(number, addrlen, prefixlen = None, strip = None): 00645 """ 00646 Utility function to convert a Python long into a rpki.POW.pkix tuple 00647 bitstring. This is a bit complicated because it supports the 00648 fiendishly compact encoding used in RFC 3779. 00649 """ 00650 assert prefixlen is None or strip is None 00651 bs = [] 00652 while number: 00653 bs.append(int(number & 1)) 00654 number >>= 1 00655 if addrlen > len(bs): 00656 bs.extend((0 for i in xrange(addrlen - len(bs)))) 00657 bs.reverse() 00658 if prefixlen is not None: 00659 return tuple(bs[0:prefixlen]) 00660 if strip is not None: 00661 while bs and bs[-1] == strip: 00662 bs.pop() 00663 return tuple(bs) 00664 00665 class resource_bag(object): 00666 """ 00667 Container to simplify passing around the usual triple of ASN, IPv4, 00668 and IPv6 resource sets. 00669 """ 00670 00671 ## @var asn 00672 # Set of Autonomous System Number resources. 00673 00674 ## @var v4 00675 # Set of IPv4 resources. 00676 00677 ## @var v6 00678 # Set of IPv6 resources. 00679 00680 ## @var valid_until 00681 # Expiration date of resources, for setting certificate notAfter field. 00682 00683 def __init__(self, asn = None, v4 = None, v6 = None, valid_until = None): 00684 self.asn = asn or resource_set_as() 00685 self.v4 = v4 or resource_set_ipv4() 00686 self.v6 = v6 or resource_set_ipv6() 00687 self.valid_until = valid_until 00688 00689 def oversized(self, other): 00690 """ 00691 True iff self is oversized with respect to other. 00692 """ 00693 return not self.asn.issubset(other.asn) or \ 00694 not self.v4.issubset(other.v4) or \ 00695 not self.v6.issubset(other.v6) 00696 00697 def undersized(self, other): 00698 """ 00699 True iff self is undersized with respect to other. 00700 """ 00701 return not other.asn.issubset(self.asn) or \ 00702 not other.v4.issubset(self.v4) or \ 00703 not other.v6.issubset(self.v6) 00704 00705 @classmethod 00706 def from_inheritance(cls): 00707 """ 00708 Build a resource bag that just inherits everything from its 00709 parent. 00710 """ 00711 self = cls() 00712 self.asn = resource_set_as() 00713 self.v4 = resource_set_ipv4() 00714 self.v6 = resource_set_ipv6() 00715 self.asn.inherit = True 00716 self.v4.inherit = True 00717 self.v6.inherit = True 00718 return self 00719 00720 @classmethod 00721 def from_rfc3779_tuples(cls, exts): 00722 """ 00723 Build a resource_bag from intermediate form generated by RFC 3779 00724 ASN.1 decoder. 00725 """ 00726 asn = None 00727 v4 = None 00728 v6 = None 00729 for x in exts: 00730 if x[0] == rpki.oids.name2oid["sbgp-autonomousSysNum"]: 00731 assert len(x[2]) == 1 or x[2][1] is None, "RDI not implemented: %s" % (str(x)) 00732 assert asn is None 00733 asn = resource_set_as(x[2][0]) 00734 if x[0] == rpki.oids.name2oid["sbgp-ipAddrBlock"]: 00735 for fam in x[2]: 00736 if fam[0] == resource_set_ipv4.afi: 00737 assert v4 is None 00738 v4 = resource_set_ipv4(fam[1]) 00739 if fam[0] == resource_set_ipv6.afi: 00740 assert v6 is None 00741 v6 = resource_set_ipv6(fam[1]) 00742 return cls(asn, v4, v6) 00743 00744 def empty(self): 00745 """ 00746 True iff all resource sets in this bag are empty. 00747 """ 00748 return not self.asn and not self.v4 and not self.v6 00749 00750 def __eq__(self, other): 00751 return self.asn == other.asn and \ 00752 self.v4 == other.v4 and \ 00753 self.v6 == other.v6 and \ 00754 self.valid_until == other.valid_until 00755 00756 def __ne__(self, other): 00757 return not (self == other) 00758 00759 def intersection(self, other): 00760 """ 00761 Compute intersection with another resource_bag. valid_until 00762 attribute (if any) inherits from self. 00763 """ 00764 return self.__class__(self.asn.intersection(other.asn), 00765 self.v4.intersection(other.v4), 00766 self.v6.intersection(other.v6), 00767 self.valid_until) 00768 00769 def union(self, other): 00770 """ 00771 Compute union with another resource_bag. valid_until attribute 00772 (if any) inherits from self. 00773 """ 00774 return self.__class__(self.asn.union(other.asn), 00775 self.v4.union(other.v4), 00776 self.v6.union(other.v6), 00777 self.valid_until) 00778 00779 def __str__(self): 00780 s = "" 00781 if self.asn: 00782 s += "ASN: %s" % self.asn 00783 if self.v4: 00784 if s: 00785 s += ", " 00786 s += "V4: %s" % self.v4 00787 if self.v6: 00788 if s: 00789 s += ", " 00790 s += "V6: %s" % self.v6 00791 return s 00792 00793 # Sadly, there are enough differences between RFC 3779 and the data 00794 # structures in the latest proposed ROA format that we can't just use 00795 # the RFC 3779 code for ROAs. So we need a separate set of classes 00796 # that are similar in concept but different in detail, with conversion 00797 # functions. Such is life. I suppose it might be possible to do this 00798 # with multiple inheritance, but that's probably more bother than it's 00799 # worth. 00800 00801 class roa_prefix(object): 00802 """ 00803 ROA prefix. This is similar to the resource_range_ip class, but 00804 differs in that it only represents prefixes, never ranges, and 00805 includes the maximum prefix length as an additional value. 00806 00807 This is a virtual class, you probably don't want to use it directly. 00808 """ 00809 00810 ## @var prefix 00811 # The prefix itself, an IP address with bits beyond the prefix 00812 # length zeroed. 00813 00814 ## @var prefixlen 00815 # (Minimum) prefix length. 00816 00817 ## @var max_prefixlen 00818 # Maxmimum prefix length. 00819 00820 def __init__(self, prefix, prefixlen, max_prefixlen = None): 00821 """ 00822 Initialize a ROA prefix. max_prefixlen is optional and defaults 00823 to prefixlen. max_prefixlen must not be smaller than prefixlen. 00824 """ 00825 if max_prefixlen is None: 00826 max_prefixlen = prefixlen 00827 assert max_prefixlen >= prefixlen, "Bad max_prefixlen: %d must not be shorter than %d" % (max_prefixlen, prefixlen) 00828 self.prefix = prefix 00829 self.prefixlen = prefixlen 00830 self.max_prefixlen = max_prefixlen 00831 00832 def __cmp__(self, other): 00833 """ 00834 Compare two ROA prefix objects. Comparision is based on prefix, 00835 prefixlen, and max_prefixlen, in that order. 00836 """ 00837 assert self.__class__ is other.__class__ 00838 return (cmp(self.prefix, other.prefix) or 00839 cmp(self.prefixlen, other.prefixlen) or 00840 cmp(self.max_prefixlen, other.max_prefixlen)) 00841 00842 def __str__(self): 00843 """ 00844 Convert a ROA prefix to string format. 00845 """ 00846 if self.prefixlen == self.max_prefixlen: 00847 return str(self.prefix) + "/" + str(self.prefixlen) 00848 else: 00849 return str(self.prefix) + "/" + str(self.prefixlen) + "-" + str(self.max_prefixlen) 00850 00851 def to_resource_range(self): 00852 """ 00853 Convert this ROA prefix to the equivilent resource_range_ip 00854 object. This is an irreversable transformation because it loses 00855 the max_prefixlen attribute, nothing we can do about that. 00856 """ 00857 return self.range_type.make_prefix(self.prefix, self.prefixlen) 00858 00859 def min(self): 00860 """ 00861 Return lowest address covered by prefix. 00862 """ 00863 return self.prefix 00864 00865 def max(self): 00866 """ 00867 Return highest address covered by prefix. 00868 """ 00869 t = self.range_type.datum_type 00870 return t(self.prefix | ((1 << (t.bits - self.prefixlen)) - 1)) 00871 00872 def to_roa_tuple(self): 00873 """ 00874 Convert a resource_range_ip to tuple format for ROA ASN.1 00875 encoding. 00876 """ 00877 return (_long2bs(self.prefix, self.range_type.datum_type.bits, prefixlen = self.prefixlen), 00878 None if self.prefixlen == self.max_prefixlen else self.max_prefixlen) 00879 00880 @classmethod 00881 def parse_str(cls, x): 00882 """ 00883 Parse ROA prefix from text (eg, an XML attribute). 00884 """ 00885 r = re_prefix_with_maxlen.match(x) 00886 if r: 00887 return cls(cls.range_type.datum_type(r.group(1)), int(r.group(2)), int(r.group(3))) 00888 r = re_prefix.match(x) 00889 if r: 00890 return cls(cls.range_type.datum_type(r.group(1)), int(r.group(2))) 00891 raise rpki.exceptions.BadROAPrefix, 'Bad ROA prefix "%s"' % (x) 00892 00893 @classmethod 00894 def from_roa_tuple(cls, o): 00895 """ 00896 Convert from ROA ASN.1 tuple format. 00897 """ 00898 assert isinstance(o, (list, tuple)), 'argument must be either list or tuple' 00899 return cls(cls.range_type.datum_type(_bs2long(o[0], cls.range_type.datum_type.bits, 0)), len(o[0]), o[1]) 00900 00901 class roa_prefix_ipv4(roa_prefix): 00902 """ 00903 IPv4 ROA prefix. 00904 """ 00905 00906 ## @var range_type 00907 # Type of corresponding resource_range_ip. 00908 00909 range_type = resource_range_ipv4 00910 00911 class roa_prefix_ipv6(roa_prefix): 00912 """ 00913 IPv6 ROA prefix. 00914 """ 00915 00916 ## @var range_type 00917 # Type of corresponding resource_range_ip. 00918 00919 range_type = resource_range_ipv6 00920 00921 class roa_prefix_set(list): 00922 """ 00923 Set of ROA prefixes, analogous to the resource_set_ip class. 00924 """ 00925 00926 def __init__(self, ini = None): 00927 """ 00928 Initialize a ROA prefix set. 00929 """ 00930 list.__init__(self) 00931 if isinstance(ini, str) and len(ini): 00932 self.extend(self.parse_str(s) for s in ini.split(",")) 00933 elif isinstance(ini, (list, tuple)): 00934 self.extend(ini) 00935 else: 00936 assert ini is None or ini == "", "Unexpected initializer: %s" % str(ini) 00937 self.sort() 00938 00939 def __str__(self): 00940 """ 00941 Convert a ROA prefix set to string format. 00942 """ 00943 return ",".join(str(x) for x in self) 00944 00945 @classmethod 00946 def parse_str(cls, s): 00947 """ 00948 Parse ROA prefix from text (eg, an XML attribute). 00949 This method is a backwards compatability shim. 00950 """ 00951 return cls.prefix_type.parse_str(s) 00952 00953 def to_resource_set(self): 00954 """ 00955 Convert a ROA prefix set to a resource set. This is an 00956 irreversable transformation. We have to compute a union here 00957 because ROA prefix sets can include overlaps, while RFC 3779 00958 resource sets cannot. This is ugly, and there is almost certainly 00959 a more efficient way to do this, but start by getting the output 00960 right before worrying about making it fast or pretty. 00961 """ 00962 r = self.resource_set_type() 00963 s = self.resource_set_type() 00964 s.append(None) 00965 for p in self: 00966 s[0] = p.to_resource_range() 00967 r = r.union(s) 00968 return r 00969 00970 @classmethod 00971 def from_sql(cls, sql, query, args = None): 00972 """ 00973 Create ROA prefix set from an SQL query. 00974 00975 sql is an object that supports execute() and fetchall() methods 00976 like a DB API 2.0 cursor object. 00977 00978 query is an SQL query that returns a sequence of (prefix, 00979 prefixlen, max_prefixlen) triples. 00980 """ 00981 00982 sql.execute(query, args) 00983 return cls([cls.prefix_type(cls.prefix_type.range_type.datum_type(x), int(y), int(z)) 00984 for (x, y, z) in sql.fetchall()]) 00985 00986 def to_roa_tuple(self): 00987 """ 00988 Convert ROA prefix set into tuple format used by ROA ASN.1 00989 encoder. This is a variation on the format used in RFC 3779. 00990 """ 00991 if self: 00992 return (self.resource_set_type.afi, tuple(a.to_roa_tuple() for a in self)) 00993 else: 00994 return None 00995 00996 class roa_prefix_set_ipv4(roa_prefix_set): 00997 """ 00998 Set of IPv4 ROA prefixes. 00999 """ 01000 01001 ## @var prefix_type 01002 # Type of underlying roa_prefix. 01003 01004 prefix_type = roa_prefix_ipv4 01005 01006 ## @var resource_set_type 01007 # Type of corresponding resource_set_ip class. 01008 01009 resource_set_type = resource_set_ipv4 01010 01011 # Fix back link from resource_set to roa_prefix 01012 resource_set_ipv4.roa_prefix_set_type = roa_prefix_set_ipv4 01013 01014 class roa_prefix_set_ipv6(roa_prefix_set): 01015 """ 01016 Set of IPv6 ROA prefixes. 01017 """ 01018 01019 ## @var prefix_type 01020 # Type of underlying roa_prefix. 01021 01022 prefix_type = roa_prefix_ipv6 01023 01024 ## @var resource_set_type 01025 # Type of corresponding resource_set_ip class. 01026 01027 resource_set_type = resource_set_ipv6 01028 01029 # Fix back link from resource_set to roa_prefix 01030 resource_set_ipv6.roa_prefix_set_type = roa_prefix_set_ipv6 01031 01032 # Test suite for set operations. 01033 01034 if __name__ == "__main__": 01035 01036 def testprefix(v): 01037 return " (%s)" % v.to_roa_prefix_set() if isinstance(v, resource_set_ip) else "" 01038 01039 def test1(t, s1, s2): 01040 if isinstance(s1, str) and isinstance(s2, str): 01041 print "x: ", s1 01042 print "y: ", s2 01043 r1 = t(s1) 01044 r2 = t(s2) 01045 print "x: ", r1, testprefix(r1) 01046 print "y: ", r2, testprefix(r2) 01047 v1 = r1._comm(r2) 01048 v2 = r2._comm(r1) 01049 assert v1[0] == v2[1] and v1[1] == v2[0] and v1[2] == v2[2] 01050 for i in r1: assert r1.contains(i) and r1.contains(i.min) and r1.contains(i.max) 01051 for i in r2: assert r2.contains(i) and r2.contains(i.min) and r2.contains(i.max) 01052 for i in v1[0]: assert r1.contains(i) and not r2.contains(i) 01053 for i in v1[1]: assert not r1.contains(i) and r2.contains(i) 01054 for i in v1[2]: assert r1.contains(i) and r2.contains(i) 01055 v1 = r1.union(r2) 01056 v2 = r2.union(r1) 01057 assert v1 == v2 01058 print "x|y:", v1, testprefix(v1) 01059 v1 = r1.difference(r2) 01060 v2 = r2.difference(r1) 01061 print "x-y:", v1, testprefix(v1) 01062 print "y-x:", v2, testprefix(v2) 01063 v1 = r1.symmetric_difference(r2) 01064 v2 = r2.symmetric_difference(r1) 01065 assert v1 == v2 01066 print "x^y:", v1, testprefix(v1) 01067 v1 = r1.intersection(r2) 01068 v2 = r2.intersection(r1) 01069 assert v1 == v2 01070 print "x&y:", v1, testprefix(v1) 01071 01072 def test2(t, s1, s2): 01073 print "x: ", s1 01074 print "y: ", s2 01075 r1 = t(s1) 01076 r2 = t(s2) 01077 print "x: ", r1 01078 print "y: ", r2 01079 print "x>y:", (r1 > r2) 01080 print "x<y:", (r1 < r2) 01081 test1(t.resource_set_type, 01082 r1.to_resource_set(), 01083 r2.to_resource_set()) 01084 01085 def test3(t, s1, s2): 01086 test1(t, s1, s2) 01087 r1 = t(s1).to_roa_prefix_set() 01088 r2 = t(s2).to_roa_prefix_set() 01089 print "x: ", r1 01090 print "y: ", r2 01091 print "x>y:", (r1 > r2) 01092 print "x<y:", (r1 < r2) 01093 test1(t.roa_prefix_set_type.resource_set_type, 01094 r1.to_resource_set(), 01095 r2.to_resource_set()) 01096 01097 print 01098 print "Testing set operations on resource sets" 01099 print 01100 test1(resource_set_as, "1,2,3,4,5,6,11,12,13,14,15", "1,2,3,4,5,6,111,121,131,141,151") 01101 print 01102 test1(resource_set_ipv4, "10.0.0.44/32,10.6.0.2/32", "10.3.0.0/24,10.0.0.77/32") 01103 print 01104 test1(resource_set_ipv4, "10.0.0.44/32,10.6.0.2/32", "10.0.0.0/24") 01105 print 01106 test1(resource_set_ipv4, "10.0.0.0/24", "10.3.0.0/24,10.0.0.77/32") 01107 print 01108 test1(resource_set_ipv4, "10.0.0.0/24", "10.0.0.0/32,10.0.0.2/32,10.0.0.4/32") 01109 print 01110 print "Testing set operations on ROA prefixes" 01111 print 01112 test2(roa_prefix_set_ipv4, "10.0.0.44/32,10.6.0.2/32", "10.3.0.0/24,10.0.0.77/32") 01113 print 01114 test2(roa_prefix_set_ipv4, "10.0.0.0/24-32,10.6.0.0/24-32", "10.3.0.0/24,10.0.0.0/16-32") 01115 print 01116 test2(roa_prefix_set_ipv4, "10.3.0.0/24-24,10.0.0.0/16-32", "10.3.0.0/24,10.0.0.0/16-32") 01117 print 01118 test2(roa_prefix_set_ipv6, "2002:0a00:002c::1/128", "2002:0a00:002c::2/128") 01119 print 01120 test2(roa_prefix_set_ipv6, "2002:0a00:002c::1/128", "2002:0a00:002c::7/128") 01121 print 01122 test2(roa_prefix_set_ipv6, "2002:0a00:002c::1/128", "2002:0a00:002c::/120") 01123 print 01124 test2(roa_prefix_set_ipv6, "2002:0a00:002c::1/128", "2002:0a00:002c::/120-128") 01125 print 01126 test3(resource_set_ipv4, "10.0.0.44/32,10.6.0.2/32", "10.3.0.0/24,10.0.0.77/32") 01127 print 01128 test3(resource_set_ipv6, "2002:0a00:002c::1/128", "2002:0a00:002c::2/128") 01129 print 01130 test3(resource_set_ipv6, "2002:0a00:002c::1/128", "2002:0a00:002c::/120")