RPKI Engine 1.0

resource_set.py (3688)

Go to the documentation of this file.
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")
 All Classes Namespaces Files Functions Variables