# Copyright 2026 SigmaSRC, Inc. All Rights Reserved.

"""Poliwall API for Fuel.

The policy firewall (poliwall for short) takes directives which
specify its actions (such as blocking or logging traffic based on IP
address, protocol or port number).  The directive format is
implemented by module sigma/poliwall/pwi.py, which contains some
samples and brief documentation; a longer example is
sigma/poliwall/pw_filters.txt, and a full description is in
Perforce as //People/Andrew.Davis/docs/PWInterfaces.doc .

Because the poliwall directives are rather low-level, and have
implicit priorities, Fuel offers a different interface.  Any Fuel
procedure wishing to control the poliwall should acquire a PoliWall
object by calling host.poliwall(), make some addcommand() method calls
on this object, and the call its save() method.

The addcommand() takes a numeric priority (lower numbers meaning
higher priority), a set of one or more actions (actions are
single-letter strings chosen from the set {A, D, B, I, R, C}, usually
referenced via symbolic constants like ALLOW), and a filter
specification (see below).  Any number of commands at the same
priority may exist, but it is not allowed to specifying conflicting
actions for filter specifications with a non-empty intersection.  The
only conflicting actions are A (allow) and D (deny); all other actions
may be combined with each other and with either of these.

Each policy rule also has a priority.  Originally, we would clip the
command priority with the rule priority (logging a message if this
happens); but since rule priorities won't be used in the May version,
we no longer do this.

Conflicts are currently reported by raising a ValueError exception.
Errors in the call order (calling addcommand() after save(), or
calling save() twice) are reported by raising a RuntimeError.
Exceptions cause an abrupt stop of the policy execution.  Call order
errors are easily avoided by proper Fuel coding; conflicts cannot
always be avoided and we should eventually decide on a way to handle
these.  Rules of different priorities cannot cause conflicts; the
highest priority rule wins.

Multiple policy rules may specify poliwall commands.  Each command is
associated with a specific policy rule id.  Whenever a PoliWall object
is acquired, all previous commands associated with the same policy
rule id are discarded, to be replaced by new commands added by
addcommand().  Upon save(), the commands from all policy rules are
combined and a set of poliwall directives is generated from these;
then the poliwall is informed of the updated directives file (this
final part isn't implemented yet).

There is currently no protection against parallel access to the
poliwall command database; the assumption is that policy rules are
executed serially.

Filter specifications: there is a Fuel API for creating filter
specifications based on sets of IP addresses (source and destination,
given in dotted-quad notation), sets of IP protocols (strings), and
sets of numeric IP port numbers.  For example, the Fuel expression

    new FilterSpec(ipsrc=host.ipaddrs('10.0.0.1', '10.0.0.255'),
                   ipproto={'tcp'},
                   ipport={25, 80})

specifies a filter that selects TCP/IP traffic whose source address in
in the range 10.0.0.1 through 10.0.0.255 (inclusive) and whose port is
either 25 or 80.  (There are some subtleties due to the statefulness
of the packet filter which I won't discuss here.)  The poliwall also
supports selection on MAC address and protocol and on packet contents;
this is not supported by the Fuel API yet.

For various reasons, these FilterSpec instances are translated into
InternalFilterSpec instances before we include them in the list of
commands (one reason is that FilterSpec instances created by Fuel code
are instaces of a class that is not easily accessible to Python code).

"""

import os
import re
import sys
import time
import socket
import struct
import logging
import pickle

if __name__ == "__main__":
    import sys
    sys.path.append(os.path.dirname(os.path.dirname(os.path.dirname(
        os.path.abspath(__file__)))))

from sigma.util import config, dance
from sigma.util.groupings import groupby, findruns
from sigma.util.pwutil import optset, optrange
from sigma.util.fuelset import FuelSet
from sigma.runtime.fuelobj import FuelObject

DEBUG = False            # Set to True for heavy invariant checking

# Allowable values for Host.pwall_mode (must be all lowercase)
GlobalAllow = "allow"
GlobalDeny = "deny"
AllowedPoliwallModes = (GlobalAllow, GlobalDeny)

logger = logging.getLogger("runtime.pwall")

def numeric2dotted(numeric):
    """Convert a numeric IP address to dotted-quad notation.

    The input must be a nonnegative integer (int or long) less than
    2**32.

    """
    assert 0 <= numeric <= 0xffffffff
    s = struct.pack(">L", numeric)
    return socket.inet_ntoa(s)

def dotted2numeric(dotted):
    if dotted == "255.255.255.255":
        # On Windows, inet_aton() barfs on this :-(
        return 0xffffffff
    s = socket.inet_aton(dotted)
    t = struct.unpack(">L", s)
    return t[0]

integers = (int,)

class IPAddr(int):
    """Object used to represent an IP address in Fuel.

    This has two attributes: dotted gives the dotted-quad
    representation and is what is actually stored, while numeric is a
    property that gives the value as an integer (the latter is useful
    for sorting and for manipulating ranges).

    """

    __slots__ = []

    def __new__(cls, arg):
        """Constructor.  The argument can be an int or dotted-quad notation."""
        if isinstance(arg, str):
            return int.__new__(cls, dotted2numeric(arg))
        else:
            return int.__new__(cls, arg)

    def __repr__(self):
        return "IPAddr(%r)" % self.dotted

    def __str__(self):
        return self.dotted

    def _get_dotted(self):
        """Property to return the dotted representation."""
        return numeric2dotted(self)
    dotted = property(_get_dotted)

    def _get_numeric(self):
        """Property to return the numeric representation."""
        return int(self)
    numeric = property(_get_numeric)

    def __add__(self, other):
        """Add an IPAddr and an int/long."""
        if not isinstance(other, integers):
            return NotImplemented
        return IPAddr(int(self) + other)

    __radd__ = __add__

    def __sub__(self, other):
        """Subtract an int/long from an IPAddr."""
        if not isinstance(other, integers):
            return NotImplemented
        return IPAddr(int(self) - other)

class RangeSet(object):
    """Set of ints (or int-like things like IPAddrs) using ranges."""

    # Representation: a sorted list of non-overlapping non-adjacent
    # inclusive (lo, hi) pairs.  That is, lo <= hi, and for
    # consecutive pairs (a, b) and (c, d), b+1 < c.

    # XXX The code would probably be a tad faster or shorter if we
    # used more Pythonic open-ended [lo, hi+1) pairs.  Since the
    # code's already written and debugged this way, it hardly matters.

    def __init__(self, arg=None):
        "Constructor with optional iterable argument."
        self.pairs = []
        if arg is not None:
            if isinstance(arg, RangeSet):
                self.pairs = arg.pairs[:]
            else:
                for x in arg:
                    self.add(x)

    def __repr__(self):
        L = []
        for lo, hi in self.pairs:
            if lo == hi:
                L.append(repr(lo))
            else:
                L.append("%r-%r" % (lo, hi))
        return "RangeSet{%s}" % ", ".join(L)

    def __str__(self):
        L = []
        for lo, hi in self.pairs:
            if lo == hi:
                L.append(str(lo))
            else:
                L.append("%s-%s" % (lo, hi))
        return "{%s}" % ", ".join(L)

    def _check(self):
        "Check the invariant."
        pairs = self.pairs
        if pairs:
            it = iter(pairs)
            lo, hi = next(it)
            assert isinstance(lo, integers), pairs
            assert isinstance(hi, integers), pairs
            assert lo <= hi, pairs
            last = hi
            for lo, hi in it:
                assert isinstance(lo, integers), pairs
                assert isinstance(hi, integers), pairs
                assert lo <= hi, pairs
                assert last+1 < lo, pairs
                last = hi

    def __len__(self):
        """Calculate len(self).

        Note: it's possible that this overflows an int!  Then len(x)
        will raise OverflowError, but you can still use x.__len__().

        """
        n = 0
        for lo, hi in self.pairs:
            n += int(hi+1-lo)
        return n

    def __bool__(self):
        """Determine whether self is non-empty without integer overflow."""
        return bool(len(self.pairs))

    def __iter__(self):
        "Iterator.  Implemented as a generator."
        for lo, hi in self.pairs:
            # Can't use range(lo, hi+1) here -- must preserve IPAddr-ness
            while lo <= hi:
                yield lo
                lo += 1

    def __contains__(self, x):
        "Test whether x is an element of self."
        pairs = self.pairs
        left = 0
        right = len(pairs)
        while left < right:
            mid = (left+right) // 2
            lo, hi = pairs[mid]
            if hi < x:
                left = mid+1
            elif x < lo:
                right = mid
            else:
                return True
        return False

    def add(self, lo, hi=None):
        "Add [lo, hi] to self; hi defaults to lo."
        assert isinstance(lo, integers), repr(lo)
        if hi is None:
            hi = lo
        else:
            assert isinstance(hi, integers)
            if hi < lo:
                return
        assert lo <= hi
        pairs = self.pairs
        n = len(pairs)
        left = 0
        right = n
        lo1 = lo-1
        while left < right:
            mid = (left+right) // 2
            if pairs[mid][1] < lo1:
                left = mid+1
            else:
                right = mid
        i = left
        right = n
        hi1 = hi+1
        while left < right:
            mid = (left+right) // 2
            if hi1 < pairs[mid][0]:
                right = mid
            else:
                left = mid+1
        j = left
        #print pairs[:i], lo, pairs[i:j], hi, pairs[j:]
        if i < n:
            lo = min(lo, pairs[i][0])
        if 0 < j:
            hi = max(hi, pairs[j-1][1])
        pairs[i:j] = [(lo, hi)]
        if DEBUG:
            self._check()

    # XXX Do we need a remove() method?

    # Union, intersection, difference and symmetric difference

    def __or__(self, other):
        "Compute set union."
        if not isinstance(other, RangeSet):
            if other is None:
                return NotImplemented
            other = RangeSet(other)
        # Now self and other are both RangeSets
        mypairs = iter(self.pairs)
        opairs = iter(other.pairs)
        new = RangeSet()
        append = new.pairs.append
        x, y = 0, -1 # initial pair
        try:
            a, b = next(mypairs)
        except StopIteration:
            mypairs = None
        try:
            p, q = next(opairs)
        except StopIteration:
            opairs = None
        if mypairs is not None and opairs is not None:
            while True:
                if a < p:
                    if y+1 < a:
                        append((x, y))
                        x, y = a, b
                    elif b > y:
                        y = b
                    try:
                        a, b = next(mypairs)
                    except StopIteration:
                        mypairs = None
                        break
                else:
                    if y+1 < p:
                        append((x, y))
                        x, y = p, q
                    elif q > y:
                        y = q
                    try:
                        p, q = next(opairs)
                    except StopIteration:
                        opairs = None
                        break
        if mypairs is not None:
            if y+1 < a:
                append((x, y))
                x, y = a, b
            elif b > y:
                y = b
            for a, b in mypairs:
                if y+1 < a:
                    append((x, y))
                    x, y = a, b
                elif b > y:
                    y = b
        if opairs is not None:
            if y+1 < p:
                append((x, y))
                x, y = p, q
            elif q > y:
                y = q
            for p, q in opairs:
                if y+1 < p:
                    append((x, y))
                    x, y = p, q
                elif q > y:
                    y = q
        append((x, y))
        if new.pairs and new.pairs[0] == (0, -1):
            del new.pairs[0]
        return new

    __ror__ = __or__

    def __and__(self, other):
        "Compute set intersection."
        if not isinstance(other, RangeSet):
            if other is None:
                return NotImplemented
            other = RangeSet(other)
        new = RangeSet()
        newpairs = new.pairs
        mypairs = iter(self.pairs)
        otherpairs = iter(other.pairs)
        try:
            mylo, myhi = next(mypairs)
            otherlo, otherhi = next(otherpairs)
        except StopIteration:
            return new # If either is empty, so is the result
        while True:
            try:
                if myhi < otherlo:
                    mylo, myhi = next(mypairs)
                elif otherhi < mylo:
                    otherlo, otherhi = next(otherpairs)
                else:
                    lo = max(mylo, otherlo)
                    hi = min(myhi, otherhi)
                    assert lo <= hi, ((mylo, myhi), (otherlo, otherhi))
                    newpairs.append((lo, hi))
                    if myhi < otherhi:
                        mylo, myhi = next(mypairs)
                    else:
                        otherlo, otherhi = next(otherpairs)
            except StopIteration:
                break # If moving either iterator hits the end, we're done
        return new

    __rand__ = __and__

    def __sub__(self, other):
        "Compute asymmetric set difference: self & complement(other)."
        if not isinstance(other, RangeSet):
            if other is None:
                return NotImplemented
            other = RangeSet(other)
        if not self.pairs:
            return RangeSet()
        # Compute this as self & compl, where compl is other's
        # complement with respect to self
        first = self.pairs[0][0]
        last = self.pairs[-1][1]
        compl = RangeSet()
        for lo, hi in other.pairs:
            if first < lo:
                compl.add(first, lo-1)
            first = hi+1
            if first > last:
                break
        if first <= last:
            compl.add(first, last)
        return self & compl

    def __rsub__(self, other):
        "Compute reverse asymmetric set difference: other & complement(self)."
        if not isinstance(other, RangeSet):
            if other is None:
                return NotImplemented
            other = RangeSet(other)
        return other - self

    def __xor__(self, other):
        "Compute symmetric set difference."
        if not isinstance(other, RangeSet):
            if other is None:
                return NotImplemented
            other = RangeSet(other)
        return (self-other) | (other-self)
        # return (self|other) - (self&other)

    __rxor__ = __xor__

    # Equality testing

    def __eq__(self, other):
        "Test for equality."
        if not isinstance(other, RangeSet):
            if other is None:
                return False
            other = RangeSet(other)
        # Use the fact that pairs is normalized
        return self.pairs == other.pairs

    def __ne__(self, other):
        "Test for inequality."
        if not isinstance(other, RangeSet):
            if other is None:
                return True
            other = RangeSet(other)
        # Use the fact that pairs is normalized
        return self.pairs != other.pairs

    def __hash__(self):
        "Hash always raises TypeError since RangeSet is mutable."
        raise TypeError("RangeSet is not hashable")

    # Inequalities test for set inclusion etc.

    def __lt__(self, other):
        "Test whether self is strictly included in other."
        if not isinstance(other, RangeSet):
            if other is None:
                raise TypeError("can't compare set to None using inequality")
            other = RangeSet(other)
        return self.__len__() < other.__len__() and not (self-other)

    def __le__(self, other):
        "Test whether self is included in other."
        if not isinstance(other, RangeSet):
            if other is None:
                raise TypeError("can't compare set to None using inequality")
            other = RangeSet(other)
        return not (self-other)

    def __gt__(self, other):
        "Test whether other is strictly included in self."
        if not isinstance(other, RangeSet):
            if other is None:
                raise TypeError("can't compare set to None using inequality")
            other = RangeSet(other)
        return other.__len__() < self.__len__() and not (other-self)

    def __ge__(self, other):
        "Test whether other is included in self."
        if not isinstance(other, RangeSet):
            if other is None:
                raise TypeError("can't compare set to None using inequality")
            other = RangeSet(other)
        return not (other-self)

    def optset(self):
        "Generator yielding an optimal set of ranges per optrange()."
        # This is called indirectly by optset() in pwutil.py
        for lo, hi in self.pairs:
            for result in optrange(lo, hi):
                yield result

    def map(self, fn):
        new = RangeSet()
        for lo, hi in self.pairs:
            new.pairs.append((fn(lo), fn(hi)))
        return new

class ImmutableRangeSet(RangeSet):
    """Immutable version of RangeSet.

    This uses implementation inheritance from RangeSet, but the
    resulting type is not usable whenever a RangeSet is accepted
    (since it doesn't implement add()).

    """

    def __init__(self, arg=None):
        "Constructor.  Takes an optional sequence or set argument."
        if arg is None:
            self.pairs = []
        else:
            if not isinstance(arg, RangeSet):
                arg = RangeSet(arg)
            self.pairs = arg.pairs

    def __hash__(self):
        "Compute an appropriate hash function."
        if not self.pairs:
            return 0
        return hash((len(self.pairs), self.pairs[0], self.pairs[-1]))

    def add(self, lo, hi=None):
        "Override add() to always raise NotImplementedError."
        raise NotImplementedError("Can't add() to a %s instance" %
                                  self.__class__.__name__)

    def __or__(self, other):
        "Override __or__ to return an ImmutableRangeSet."
        res = RangeSet.__or__(self, other)
        if isinstance(res, RangeSet):
            res = self.__class__(res)
        return res

    __ror__ = __or__

    def __and__(self, other):
        "Override __and__ to return an ImmutableRangeSet."
        res = RangeSet.__and__(self, other)
        if isinstance(res, RangeSet):
            res = self.__class__(res)
        return res

    __rand__ = __and__

    def __sub__(self, other):
        "Override __sub__ to return an ImmutableRangeSet."
        res = RangeSet.__sub__(self, other)
        if isinstance(res, RangeSet):
            res = self.__class__(res)
        return res

    def __xor__(self, other):
        "Override __xor__ to return an ImmutableRangeSet."
        res = RangeSet.__xor__(self, other)
        if isinstance(res, RangeSet):
            res = self.__class__(res)
        return res

    __rxor__ = __xor__

def immutableset(a):
    """Factory function for immutable sets of various kinds.

    The argument must be a set.

    """
    if isinstance(a, frozenset) or isinstance(a, ImmutableRangeSet):
        return a
    if isinstance(a, FuelSet):
        return frozenset(a)
    if isinstance(a, RangeSet):
        return ImmutableRangeSet(a)
    raise TypeError("argument %s not a set" % repr(a))

class InternalFilterSpec(FuelObject):
    """Internal filter spec.

    This is an immutable object with the following attributes; the
    value None means 'all' or 'unrestricted':

    - macsrc  -- set of strings designating MAC addresses
    - macdst  -- set of strings designating MAC addresses
    - macproto -- set of strings designating MAC protocols
    - ipsrc   -- set of source address IPAddr objects, or None
    - ipdst   -- set of destination address IPAddr objects, or None
    - ipproto -- set of IP protocol strings, or Nnoe
    - ipport  -- set of numeric IP port numbers, or None

    There are also methods for equality testing, hashing, subset
    testing, and intersection.  See the module docstring for some
    background.

    """
    macsrc = macdst = macproto = None
    ipsrc = ipdst = ipproto = ipport = None
    attrnames = "macsrc macdst macproto ipsrc ipdst ipproto ipport".split()

    def __init__(self, **args):
        """Constructor.

        Keyword arguments corresponding to the instance variables
        provide initializers.

        """
        for key in args:
            if key not in self.attrnames:
                raise TypeError("bad keyword arg: %s=%r" % (key, args[key]))
        self.__dict__.update(args)

    def __eq__(self, other):
        """Equality test."""
        if not isinstance(other, InternalFilterSpec):
            return False
        for name in self.attrnames:
            if getattr(self, name, None) != getattr(other, name, None):
                return False
        return True

    def __ne__(self, other):
        """Inverse equality test."""
        return not self.__eq__(other)

    def __lt__(self, other):
        """Less-than comparison for sorting.

        Python 3 requires explicit ordering; compare attribute tuples
        using their repr so that None and heterogeneous set types can
        be ordered deterministically.
        """
        if not isinstance(other, InternalFilterSpec):
            return NotImplemented
        for name in self.attrnames:
            a = getattr(self, name, None)
            b = getattr(other, name, None)
            if a == b:
                continue
            return repr(a) < repr(b)
        return False  # equal

    def __hash__(self):
        """Hash computation.  This is an immutable object!"""
        h = 0
        for name in self.attrnames:
            x = getattr(self, name, None)
            h ^= hash(x)
        return h

    def includes(self, other):
        """Predicate to compute whether other is a subset of self."""
        for name in self.attrnames:
            a = getattr(self, name, None)
            if a is None:
                continue
            b = getattr(other, name, None)
            if b is None:
                return False
            if not issuperset(a, b):
                    return False
        return True

    def intersect(self, other):
        """Compute the intersection of self and other."""
        # XXX Could apply various optimizations for trivial results
        f = InternalFilterSpec()
        for name in self.attrnames:
            a = getattr(self, name, None)
            b = getattr(other, name, None)
            if a is None:
                x = b
            elif b is None:
                x = a
            else:
                x = intersection(a, b)
            setattr(f, name, x)
        return f

    def isempty(self):
        """We're empty if any attribute is not None and empty."""
        for name in self.attrnames:
            a = getattr(self, name, None)
            if a is not None:
                if not a:
                    return True
        return False

def issuperset(a, b):
    if type(a) != type(b):
        if isinstance(a, (RangeSet, ImmutableRangeSet)):
            b = ImmutableRangeSet(b)
        elif isinstance(b, (RangeSet, ImmutableRangeSet)):
            a = ImmutableRangeSet(a)
    return a >= b

def intersection(a, b):
    if type(a) != type(b):
        if isinstance(a, (RangeSet, ImmutableRangeSet)):
            b = ImmutableRangeSet(b)
        elif isinstance(b, (RangeSet, ImmutableRangeSet)):
            a = ImmutableRangeSet(a)
    return a & b

def filterspec(filter):
    """Convert from a Fuel FilterSpec to an InternalFilterSpec."""
    if isinstance(filter, InternalFilterSpec):
        return filter
    # Range check on port sets
    a = getattr(filter, "ipport", None)
    if a is not None:
        portsrangecheck(a)
    f = InternalFilterSpec()
    for name in f.attrnames:
        a = getattr(filter, name, None)
        if a is not None:
            if name in ("macsrc", "macdst"):
                a = validatemacset(a)
            if name in ("macproto", "ipproto"):
                a = fixprotosetcase(a)
            if name == "ipport" and isallports(a):
                continue
            setattr(f, name, immutableset(a))
    return f

def portsrangecheck(a):
    """Helper to do efficient range checks on a set of ports."""
    if isinstance(a, (RangeSet, ImmutableRangeSet)):
        for lo, hi in a.pairs:
            if lo < 0 or hi > 65535:
                raise ValueError("IP port out of range [0-65535]")
    else:
        for x in a:
            if x < 0 or x > 65535:
                raise ValueError("IP port out of range [0-65535]")

ALLPORTS = RangeSet()
ALLPORTS.add(1, 65535)

def isallports(portset):
    """Returns whether the portset represents 'all ports'.

    Three possibilities:

    - nil
    - contains 0
    - includes all ports from 1 through 65535 inclusive

    """
    if portset is None or 0 in portset:
        return True
    lo = min(portset)
    if lo > 1:
        return False
    hi = max(portset)
    if hi < 65535:
        return False
    return not (ALLPORTS - portset)

def fixprotosetcase(ss):
    """Helper to make the case of a set of protocol names all lower case."""
    result = FuelSet()
    for s in ss:
        result.add(s.lower())
    return result

def validatemacset(ss):
    """Helper to validate a set of MAC addresses.

    Each element should be a string consisting of either exactly 12
    hex digits, or up to 12 hex digits followed by a slash and a
    decimal number in the range 0-48.

    We return the input set, but normalized: converted to lowercase
    and '/48' added to single addresses.
    """
    result = FuelSet()
    for s in ss:
        if "/" not in s:
            m = re.match(r"\A[0-9A-Fa-f]{12}\Z", s)
            if m is None:
                raise ValueError("invalid MAC address %s" % repr(s))
            result.add(s.lower() + "/48")
        else:
            m = re.match(r"\A([0-9A-Fa-f]{1,12})/(\d{1,2})\Z", s)
            if m is None:
                raise ValueError("invalid MAC address %s" % repr(s))
            n = int(m.group(2))
            if n < 0 or n > 48:
                raise ValueError("invalid bit count '/%d' in mac address %s",
                                 n, repr(s))
            result.add("%s/%d" % (m.group(1).lower(), int(m.group(2))))
    return result

def ipaddr(dotted, numeric=False):
    """Fuel API: create an IPAddr instance from a dotted IP address.

    This is a factory for IPAddr that does better argument checking.

    The argument can also be a hostname; it is interpreted by
    gethostbyname() unless it is all-numeric or the optional second
    argument is true.

    The argument can also be a long or int or an IPAddr instance.

    All syntax errors raise ValueError.

    A None argument (e.g. an unresolved/unconfigured server name) returns
    None rather than raising, honoring the documented "returns None on
    lookup failure" contract that callers already test for.

    """
    if dotted is None:
        return None
    try:
        if isinstance(dotted, int): # IPAddr is a subclass of int
            if dotted < 0 or dotted > 0xFFFFFFFF:
                raise ValueError("integral argument %s out of range" % dotted)
            return IPAddr(dotted)
        if re.match(r"\A\d+\.\d+\.\d+\.\d+\Z", dotted):
            return IPAddr(dotted)
        if re.match(r"\A[\d\s./*-]*\Z", dotted):
            raise ValueError("invalid numeric IP addess %r" % dotted)
        if not numeric:
            try:
                dotted = socket.gethostbyname(dotted)
            except socket.error:
                return None
        return IPAddr(dotted)
    except socket.error as err:
        raise ValueError(str(err))

def ipaddrs(lo, hi=None):
    """Fuel API: create a set of IPAddr instances from an inclusive range.

    The first argument is the lower dotted IP address; the second
    is the opper dotted IP address, defaulting to the first
    argument.

    Alternatively, the first argument can be an IP address pattern
    using trailing * wildcards, or a subnet specification using a
    /; then no second argument should be passed.

    Unlike ipaddr(), the arguments can not be hostnames.

    The return type is a RangeSet.

    All syntax errors raise ValueError.

    """
    if hi is None:
        lo, hi = parse_range(lo)
    lo = ipaddr(lo, True)
    hi = ipaddr(hi, True)
    r = RangeSet()
    r.add(lo, hi)
    return r

def parse_range(s):
    """Helper to parse addresses using * (wildcard) and / (subnet).

    The * form can replace one or more quads from the end with *;
    *.* may then be shortened to *.  For example, 1.2.3.* is the
    same as the range 1.2.3.0 through 1.2.3.255; 1.2.* is the same
    as 1.2.0.0 through 1.2.255.255; * means all IP addresses.

    The / form takes a full address, a /, and a decimal number
    giving the number of relevant bits from the left.  For
    example, 1.2.3.0/24 is the same as 1.2.3.*, and 1.2.3.4/30 is
    the same as the range 1.2.3.4 through 1.2.3.7.  Trailing parts of
    the address may be left out if they are irrelevant, e.g. 10/8 is
    the same as 10.0.0.0/8.

    The two forms cannot be combined.  All syntax errors raise
    ValueError.

    The return value is two integers representing the inclusive
    low and high end of the range.

    """
    slash = s.find("/")
    if slash >= 0:
        ip, bits = s[:slash], s[slash+1:]
        nbits = int(bits)
        if nbits < 0 or nbits > 32:
            raise ValueError("invalid mask size %r" % bits)
        mask = 2**(32-nbits) - 1
        n = ip.count(".")
        if n < 3:
            ip += ".0" * (3-n)
    else:
        ip = s
        n = 0
        while ip.endswith(".*"):
            ip = ip[:-2]
            n += 1
        if ip == "*" and n <= 3:
            return (0, 0xffffffff)
        if not n:
            if ip.count(".") != 3:
                raise ValueError("invalid all-numeric IP address %r" % ip)
        ip += n*".0"
        if n:
            while ip.count(".") < 3:
                ip += ".0"
                n += 1
        if n > 3:
            raise ValueError("too many stars %r" % s)
        mask = 2**(8*n) - 1
    try:
        lo = dotted2numeric(ip)
    except socket.error:
        raise ValueError("invalid IP address %r" % ip)
    return (lo&~mask, lo|mask)

def ports(lo, hi=None):
    """Fuel API: create a set of ports from an inclusive range."""
    if not isinstance(lo, int):
        raise TypeError("ports() lower bound must be int")
    if not 0 < lo <= 65535:
        raise ValueError("ports() lower bound must be in [1, 65535]")
    if hi is None:
        return FuelSet([lo])
    if not isinstance(hi, int):
        raise TypeError("ports() upper bound must be int")
    if not 0 <= hi <= 65535:
        raise ValueError("ports() upper bound must be in [0, 65535]")
    if hi < lo:
        return FuelSet()
    if hi == lo:
        return FuelSet([lo])
    r = RangeSet()
    r.add(lo, hi)
    return r

class PoliWall(FuelObject):
    """Policy wall interface.

    This provides some Fuel APIs and some internal methods.

    Fuel APIs include:
    - the ALLOW, DENY etc. constants
    - methods ipaddr() and ipaddrs()
    - methods addcommand(), skipinterface(), and save()

    """

    # Constants exported to Fuel naming actions
    ALLOW = FuelSet("A")
    DENY = FuelSet("D")
    LOG = FuelSet("B") # batch log
##    NOTIFY = FuelSet("I") # immediate log
##    RECORD = FuelSet("R")
##    COUNT = FuelSet("C")
    NOINFO = FuelSet("N") # no information gathering

    # Exported constants naming magic IP addresses and ranges ("macros")
    MY_IP = IPAddr("127.69.83.65")          # 'E', 'S', 'A'
    MY_IP_LINE = IPAddr("127.69.83.76")     # 'E', 'S', 'L'
    MY_IP_WIRELESS = IPAddr("127.69.83.87") # 'E', 'S', 'W'
    MY_LAN = FuelSet([IPAddr("127.69.83.255")]) # 'E', 'S', 0xff

    # Another exported constant
    MAX_DIRECTIVES = 4096    # Should match PW_MAX_RULES in pw_config.h

    # Re-purpose some module-global functions as static methods
    ipaddr = staticmethod(ipaddr)
    ipaddrs = staticmethod(ipaddrs)
    ports = staticmethod(ports)

    def __init__(self, host, ruleid, priority=0,
                 picklefile=None, conffile=None):
        """Constructor, called by the Host's poliwall() method.

        Arguments:
        - host     -- the Host instance (for its enforce flag)
        - ruleid   -- string giving the policy rule id
        - priority -- integer giving the rule priority, defaulting to zero
        - picklefile -- string giving the file where to read/write the
                      commands 'database' (a Python pickle)
        - conffile -- string giving the file where to write the
                      poliwall directives

        XXX Note: The rule priority is ignored in Sigma 1.0.

        """
        self.options = config.Options()
        if picklefile is None:
            picklefile = self.options.datapath("pwconf.pickle")
        if conffile is None:
            conffile = self.options.datapath("pwconf.txt")
        self.host = host         # host object
        self.ruleid = ruleid     # policy rule id
        self.priority = priority # policy rule priority
        self.picklefile = picklefile # pickled commands (in/out, binary)
        self.conffile = conffile # poliwall directives (output, text)
        self.commands = []       # list of (pri, ruleid, action, filter) tuples
        self.oldcommands = []    # comands for this rule id from database
        self.newcommands = []    # new commands for this rule id
        self.ifnameskips = []    # list of ifskips
        self.oldifnameskips = [] # ifskips for this rule id from database
        self.newifnameskips = [] # new ifskips for this rule id
        self.saved = False
        self.skipped = 0 # number of commands skipped due to global allow/deny
        self.load()

    def clear(self):
        """Delete all commands.  Not accessible from Fuel."""
        self.commands = []
        self.oldcommands = []
        self.newcommands = []
        self.ifnameskips = []
        self.oldifnameskips = []
        self.newifnameskips = []

    def load(self):
        """Internal helper to load the database, minus our rule id."""
        if self.host.pw_commands is not None:
            # Get it from the cache
            newcommands = self.host.pw_commands
            newifnameskips = self.host.pw_ifnameskips
        else:
            # Get it from disk
            newcommands = self.host.pw_commands = []
            newifnameskips = self.host.pw_ifnameskips = []
            if not os.path.exists(self.picklefile):
                return
            try:
                f = open(self.picklefile, "rb")
            except IOError as msg:
                logger.error("Can't read poliwall pickle: %s", msg)
                return
            try:
                try:
                    newcommands = self.host.pw_commands = pickle.load(f)
                    newifnameskips = self.host.pw_ifnameskips = pickle.load(f)
                except EOFError:
                    logger.info("Can't read one or more parts of a poliwall"
                                " pickle. Upgrade in progress.")
            finally:
                f.close()
        for t in newcommands:
            if t[1] == self.ruleid:
                self.oldcommands.append(t)
            else:
                self.commands.append(t)
        for t in newifnameskips:
            if t[0] == self.ruleid:
                self.oldifnameskips.append(t)
            else:
                self.ifnameskips.append(t)

    # gethostgroup(), gethostgroupnames(), getmatrixid() are here for
    # backward compatibility with old Fuel only

    def gethostgroup(self, name):
        """Fuel API: get a host group by name from the Matrix."""
        return self.host.gethostgroup(name)

    def gethostgroupnames(self):
        """Fuel API: get the names of all host groups in the Matrix."""
        return self.host.gethostgroupnames()

    def getmatrixid(self):
        """Fuel API: get the Matrix id."""
        return self.host.getmatrixid()

    def addcommand(self, pri, actions, filter=None):
        """Fuel API: add a poliwall command.

        The priority argument should be 0, 500 or 1000.

        The actions argument should be one of the following sets:

            {A}
            {D}
            {D, B}
            {N}

        The filter should be either None or a FilterSpec.

        """
        if self.saved:
            raise RuntimeError("you can't add poliwall commands after saving")

        assert isinstance(pri, int), repr(pri)
        if pri not in (0, 500, 1000):
            raise ValueError("Priority (%s) should be 0, 500 or 1000", pri)

        assert isinstance(actions, FuelSet), repr(actions)
        if "".join(sorted(actions)) not in ("A", "D", "BD", "N", "R"):
            raise ValueError("Action (%s) should be"
                             " ALLOW, DENY, DENY|LOG, NOTIFY or RECORD", actions)

        actions = self.mapactions(actions)

        # If global allow or deny mode is on, priorities are
        # used as follows:
        #
        # 0: the command that always allows access to the central server
        # 500: ordinary rules
        # 1000: the baseline allow or deny command
        #
        # In global allow mode, the baseline must be "allow all" and
        # the ordinary rules must all be deny rules; other rules are
        # *skipped*.  In global deny mode, it's the opposite (but the
        # central server rule is always on, and always specifies
        # "allow").
        if self.host.pwall_mode is None:
            logger.warn("Poliwall mode not set")
        else:
            if pri == 0:
                if "A" not in actions:
                    raise ValueError("priority 0 rule must be ALLOW")
            elif pri == 500:
                if self.host.pwall_mode == GlobalAllow:
                    if "A" in actions:
                        self.skipped += 1
                        logger.info(
                            "Skipping regular ALLOW rule in global allow mode")
                        return
                elif self.host.pwall_mode == GlobalDeny:
                    if "D" in actions or "B" in actions:
                        self.skipped += 1
                        logger.info(
                            "Skipping regular DENY rule in global deny mode")
                        return
            elif pri == 1000:
                if self.host.pwall_mode == GlobalAllow:
                    if "D" in actions or "B" in actions:
                        self.skipped += 1
                        logger.info(
                            "Skipping base DENY rule in global allow mode")
                        return
                elif self.host.pwall_mode == GlobalDeny:
                    if "A" in actions:
                        self.skipped += 1
                        logger.info(
                            "Skipping base ALLOW rule in global deny mode")
                        return

        # There may be a conflict with other actions at the same
        # priority, but we won't know until save(True) is called.
        # It's too expensive to check for this each time.
        t = (pri, self.ruleid, actions, filterspec(filter))

        self.newcommands.append(t)

    def skipinterface(self, ifname):
        """Fuel API: add a poliwall interface name filter.

        """
        if self.saved:
            raise RuntimeError("you can't add poliwall filters after saving")

        assert isinstance(ifname, str), repr(ifname)
        t = (self.ruleid, ifname)
        self.newifnameskips.append(t)

    def count_directives(self):
        """Fuel API: return the number of Poliwall directives.

        This is provided so that we can write a Fuel rule that fails
        compliance when there are too many directives.

        This operation is expensive -- it calls makedirectives(),
        which does a fair amount of work!

        """
        self.makedirectives()
        # Pattern to look for port ranges (port is the 9th field)
        regex = r"\s*" + 8*r"\S+\s+" + r"(\d+)-(\d+)\s+"
        prog = re.compile(regex)
        n = 0
        for d in self.directives:
            if d[0] not in "*#SI":
                match = prog.match(d)
                if match:
                    lo, hi = map(int, match.groups())
                    k = len(list(optrange(lo, hi)))
                else:
                    k = 1
                n += k
        logger.info("adjusted directive count = %d", n)
        return n

    def add_central_server_allow(self):
        """Unconditionally allow the management channel to the central server.

        This mirrors the pw_always_talk_to_central_server Fuel rule, but is
        invoked directly by engine.py so the allow is present even when the
        deployed poliwall policy omits that rule.  Priority-0 ALLOW commands
        are never dropped by the global allow/deny skip logic (see
        addcommand()), so a global-deny policy can no longer black-hole the
        agent's own uplink.  That black-hole is unrecoverable from the server:
        the directive that turns enforcement back off travels over this very
        channel, so once it is blocked the host can only be freed by hand.

        Opens, for the configured central server: ARP; and TCP to the server
        on {port, port+2, 8080} (mTLS 17747, non-SSL 17749, UI 8080).  These
        are exactly the outbound flows the agent needs to keep reaching the
        server so a remote "disable enforcement" directive can always land.
        """
        # Always allow ARP so the host can resolve its gateway/peers.
        self.addcommand(0, FuelSet(['A']),
                        InternalFilterSpec(
                            macproto=immutableset(FuelSet(['arp']))))

        conf = self.options.central_server or "dogfood:17747"
        servername, sep, portstr = conf.partition(":")
        servername = servername.strip()
        if sep:
            try:
                port = int(portstr)
            except ValueError:
                port = 17747
        else:
            port = 17747

        server = self.ipaddr(servername)
        if server is None:
            # Treat as a transient lookup failure (e.g. DNS down): keep the ARP
            # allow rather than aborting, so we never emit an emptier-than-Fuel
            # ruleset.  The next regen retries the lookup.
            logger.error("central-server allow: name lookup failed for %r; "
                         "management-channel allow limited to ARP", servername)
        else:
            servers = immutableset(FuelSet([server]))
            protos = immutableset(FuelSet(['tcp']))
            # port+2 is the non-SSL port; 8080 is the UI.
            ports = immutableset(FuelSet([port, port + 2, 8080]))
            self.addcommand(0, FuelSet(['A']),
                            InternalFilterSpec(ipdst=servers, ipport=ports,
                                               ipproto=protos))
        self.save()

    def save(self):
        """Fuel API: Save results.

        When invoked by 'engine.py -p', this updates host.pw_commands;
        otherwise, this just setts self.saved and calls host.leave()
        when no new commands were issued.

        """
        # Check for out-of-order call
        if self.saved:
            raise RuntimeError("you can't save twice")

        # Update complete list of commands
        self.commands += self.newcommands
        self.ifnameskips += self.newifnameskips

        # Update the cache (host.pw_commands) if requested
        if self.host.pw_update_commands:
            self.host.pw_commands = self.commands
            self.host.pw_ifnameskips = self.ifnameskips

        # Set saved state to trap out-of-order calls
        self.saved = True

        # Exit with "walk" if only skipped rules in global allow/deny mode
        if self.skipped and not self.newcommands:
            self.host.leave(
                0,
                "%d inapplicable command(s) skipped in global %s mode",
                self.skipped,
                self.host.pwall_mode)

    def save_directives(self):
        """Helper for engine.py to actually write pwconf.{txt,pickle}."""

        # Write pickle file
        new = self.picklefile + ".new"
        try:
            f = open(new, "wb")
        except IOError as msg:
            logger.error("Can't write %s: %s", new, msg)
        else:
            try:
                pickle.dump(self.commands, f, 2)
                pickle.dump(self.ifnameskips, f, 2)
            finally:
                f.close()
            if dance.rename(new, self.picklefile, logger) is None:
                logger.info("Wrote pickled commands to %s",
                            self.picklefile)

        # Turn the amorphous list of commands into a series of
        # poliwall directives, ordered from highest priority to
        # lowest
        logger.info("Creating directives ...")
        self.makedirectives()

        # Write directives file
        new = self.conffile + ".new"
        try:
            f = open(new, "w")
        except IOError as msg:
            logger.error("Can't write %s: %s", new, msg)
        else:
            try:
                f.writelines(self.directives)
            finally:
                f.close()
            if dance.rename(new, self.conffile, logger) is None:
                logger.info("Wrote poliwall configuration to %s",
                            self.conffile)

        # Count number of directives, and cry foul if too many
        n = 0
        for d in self.directives:
            if d[0] not in "*#SI":
                n += 1
        if n > self.MAX_DIRECTIVES:
            logger.error("Too many poliwall directives: "
                         "%d generated, %d allowed",
                         n, self.MAX_DIRECTIVES)

    # The rest are internal helper for writing poliwall directives

    def makedirectives(self):
        """Internal: produce the list of directives.

        Commands are grouped by priority, highest priority (lowerst
        number) first.  Within each priority, a separate directive are
        generated for each non-empty intersection of a subset of
        commands.

        """
        t0 = time.time()
        sep = "#"*20 + "\n"
        noinfo, realcommands = self.separate_noinfo_commands()
        realcommands.sort(key=lambda t: t[0])
        self.directives = [] # writedirectives() puts output here
        self.ipsets = {} # maps ImmutableSet values to ipset names
        self.directives.append(sep)
        self.directives.append("# Each filter line consists of the fields:\n")
        self.directives.append("# filterID action macDA/Len macSA/Len macProto ipDA/len ipSA/len ipProto wPort string\n")
        self.directives.append(sep)
        self.directives.append("# Interface name Filters:\n")
        for r, ifname in self.ifnameskips:
            self.directives.append("I %s\n" % (ifname))
        self.directives.append(sep)

        for pri, commands in groupby(realcommands, lambda t: t[0]):
            map = {}
            allows = FuelSet()
            denies = FuelSet()
            for p, r, a, f in commands: # priority, ruleid, action, filterspec
                if f.isempty():
                    continue
                for action in a:
                    key = (action, r)
                    target = map.get(key)
                    if target is None:
                        map[key] = target = FuelSet()
                    unify(target, f)
                if "A" in a:
                    unify(allows, f)
                if "D" in a:
                    unify(denies, f)
            if intersect(allows, denies):
                raise ValueError("conflict between allows (%r) "
                                 "and denies (%r) at priority %s" %
                                 (allows, denies, pri))
            self.directives.append(sep)
            self.directives.append("# PRIORITY %s\n" % pri)
            self.directives.append(sep)
            # Due to the way the poliwall works, there's no need to
            # ever output a filter that is fully covered by what we've
            # seen before.  Weeding out these redundancies in
            # allsubsets() is harder than it seems, so we do it here
            # using brute force.  Yes, this is quadratic.
            seen = FuelSet()
            for subkeys, target in allsubsets(sorted(map.keys()), map):
                if not sloppy_issubset(target, seen):
                    for f in target:
                        unify(seen, f)
                    self.writedirectives(pri, subkeys, target, noinfo)
        t1 = time.time()
        logger.info("makedirectives() took %.3f seconds", t1-t0)

    def separate_noinfo_commands(self):
        """Internal: separate self.commands into noinfo and real commands."""
        noinfo = FuelSet()
        realcommands = []
        for command in self.commands:
            p, r, a, f = command # priority, ruleid, action, filterspec
            if "N" in a:
                assert len(a) == 1 # only "N" should be there
                unify(noinfo, f)
            else:
                realcommands.append(command)
        return noinfo, realcommands

    def mapactions(self, actions):
        """Internal: map a Fuel action set to Poliwall action letters.

        (Sigh.  This must be one of the most changing bits of code.)

        The poliwall has two logging options: B and I (Batch log and
        Immediate log, for historical reasons).  The output is
        identical but they are written to different files and can be
        controlled separately by specifying the B and/or I flags.

        We have three different cases for denied traffic: two for when
        enforcement is on, and one for when enforcement is off.

        When enforcement is on:

        (a) Deny the traffic, notify the local console user via the
            systray icon (which links to the Agent UI), and generate
            an <enforced> record for the affected rule in the server.
            This is suitable for forbidden outgoing connections, which
            may be initiated by the local console user, who deserves
            to get a hint as to why his attempts are being blocked.

        (b) Deny the traffic *without* telling the local console user,
            still generating an <enforced> record.  This is suitable
            for forbidding incoming connections (which are likely
            attacks and which the local console user needn't be told
            about since they ar successfully thwarted -- or at least
            that's the theory).

        When enforcement is off:

        (c) Let the traffic pass, don't tell the local console user,
            but generate a <violation> record for the server.  (Since
            we're not affecting the traffic, there's no point in
            alerting the local user -- says the theory.)

        The Fuel code doesn't know (and needn't know) whether
        enforcement is on or off.  For historical reasons (the code
        was written this way and I don't want to change it), it
        indicates the difference between cases (a) and (b) by using
        DENY|LOG for (a) and just DENY for (b).  Both of these must be
        collapsed to (c) when enforcement is off.

        Summarizing:

        +----------------+---------------------+----------------------+
        | When you write | With enforcement on | With enforcement off |
        | in Fuel source | it becomes          | it becomes           |
        +----------------+---------------------+----------------------+
        | DENY     (D)   | DB                  | B                    |
        | DENY|LOG (DB)  | DBI                 | B                    |
        +----------------+---------------------+----------------------+

        """

        result = FuelSet()

        if self.host.pwall_enforce:
            for action in actions:
                if action == "D":
                    result.add("D")
                    result.add("B")
                elif action == "B":
                    result.add("I")
                else:
                    result.add(action)
        else:
            for action in actions:
                if action == "D":
                    action = "B"
                result.add(action)

        return result

    # Counter for generating unique directive ids.
    # Each PoliWall instance has its own sequence starting at 1.
    nextdirectiveid = 1

    def writedirectives(self, pri, subkeys, target, noinfo):
        strongrules = FuelSet() # Enforcing rules (have 'D')
        weakrules = FuelSet() # Non-enforcing rules (have 'B' but not 'D')
        allrules = FuelSet() # All rules (including 'A')
        actions = FuelSet() # Action letters ('A', 'B', 'D', 'I')
        # Action 'R' is special, it ends up as action 'A' in pwconf.txt
        # but we have it as a separate action in fuel because we don't want it
        # to be overwritten by NOINFO rules and 'A' rules from fuel do get
        # overwritten by NOINFO rules. 
        record = False
        for action, ruleid in subkeys:
            if "R" in action:
                actions.add("A")
                record = True
            else:
                actions.add(action)
            allrules.add(ruleid)
            if "D" in action:
                strongrules.add(ruleid)
            if "B" in action:
                weakrules.add(ruleid)
        if strongrules:
            # Weak rules are those with 'B' but not 'W'
            weakrules -= strongrules
        else:
            # If there are no strong rules, we don't want to exclude
            # the weak rules
            weakrules = FuelSet()
        for ruleid in sorted(allrules):
            code = (ruleid in weakrules) and "#" or "*"
            mapping = "%s %s %s\n" % (code, ruleid, self.nextdirectiveid)
            self.directives.append(mapping)
        actionstr = "".join(sorted(actions))
        # noninfo rules are to be added only if it's a non-record rule.
        if noinfo and not record:
            noinfotarget = intersect(noinfo, target)
            for filter in noinfotarget:
                self.writefilter("N" + actionstr, filter)
            if noinfotarget == target:
                target = FuelSet() # Disable the next loop
        for filter in target:
            self.writefilter(actionstr, filter)
        self.nextdirectiveid += 1

    def makesets(self, ipset):
        """Generator producing IP ranges or named IP sets from an IP set.

        This either produces one or more strings of the form x/y where
        x is an IP address (or 0) and y is a number of significant
        bits on the left; or one IP set name of the form X<digits>.

        As a side effect, it may also append the 'S' commands that
        define the set to self.directives().  This always happens
        before the first yield, if it happens at all.

        """
        if ipset is None:
            yield "0/0"
        else:
            # We have to decide whether to define a named set or a
            # series of ranges.  It's better to use a named set than
            # many ranges; but it's better to use a few ranges than a
            # large named set.  Where the cut-off point is we don't
            # know yet.  For now, we use ranges if the number of
            # ranges is at most the square root of the total number of
            # elements.  Let's tweak this later.  Some examples:
            #
            # SETSIZE  USE RANGES IF NRANGES IS AT MOST
            #       0         0 (always; cannot happen)
            #       1         1 (always)
            #       2         1
            #       3         1
            #       4         2
            #      10         3
            #     100        10
            #   1,000        31
            #  10,000       100
            # 100,000       316
            #
            # In practice most large sets will probably fall at some
            # extreme: either they are almost completely contiguous,
            # or they are extremely scattered.  The algorithm makes
            # the right choice in those cases.
            #
            # (XXX An important additional factor that should figure
            # in the decision is how often a set will be reused.
            # Unfortunately we don't have that information; it would
            # take an extra pass over the data.  Later.)
            ranges = list(optset(ipset))
            nranges = len(ranges)
            setsize = ipset.__len__() # Can't use len() for extreme range sets
            if nranges**2 <= setsize:
                for v, m in ranges:
                    yield "%s/%d" % (numeric2dotted(v), 32-m)
            else:
                ipset = immutableset(ipset) # Make it usable as a key
                setname = self.ipsets.get(ipset)
                if not setname:
                    setname = "X%d" % len(self.ipsets)
                    self.ipsets[ipset] = setname
                    for x in ipset:
                        self.directives.append("S %s %s\n" % (setname, x))
                yield setname

    def writefilter(self, actionstr, filter):
        for set in self.makesets(filter.ipsrc):
            self.writeipdst(actionstr, set, filter)

    def writeipdst(self, actionstr, ipsrc, filter):
        for set in self.makesets(filter.ipdst):
            self.writeipproto(actionstr, ipsrc, set, filter)

    def writeipproto(self, actionstr, ipsrc, ipdst, filter):
        ipproto = filter.ipproto
        if ipproto is None:
            self.writeipport(actionstr, ipsrc, ipdst, "Any", filter)
        else:
            for x in sorted(ipproto):
                self.writeipport(actionstr, ipsrc, ipdst, str(x), filter)

    def writeipport(self, actionstr, ipsrc, ipdst, ipproto, filter):
        ipport = filter.ipport
        if ipport is None:
            self.writemacproto(actionstr, ipsrc, ipdst, ipproto, "0", filter)
        else:
            for first, last, group in findruns(sorted(ipport)):
                if first == last:
                    s = str(first)
                else:
                    s = "%s-%s" % (first, last)
                self.writemacproto(actionstr, ipsrc, ipdst, ipproto, s, filter)

    def writemacproto(self, actionstr, ipsrc, ipdst, ipproto, ipport, filter):
        macproto = filter.macproto
        if macproto is None:
            self.writemacsrc(actionstr, ipsrc, ipdst, ipproto, ipport,
                             "Any", filter)
        else:
            for x in macproto:
                self.writemacsrc(actionstr, ipsrc, ipdst, ipproto, ipport,
                                 x, filter)

    def writemacsrc(self, actionstr, ipsrc, ipdst, ipproto, ipport,
                    macproto, filter):
        macsrc = filter.macsrc
        if macsrc is None:
            self.writemacdst(actionstr, ipsrc, ipdst, ipproto, ipport,
                             macproto, "0/0", filter)
        else:
            for x in macsrc:
                self.writemacdst(actionstr, ipsrc, ipdst, ipproto, ipport,
                                 macproto, x, filter)

    def writemacdst(self, actionstr, ipsrc, ipdst, ipproto, ipport,
                    macproto, macsrc, filter):
        macdst = filter.macdst
        if macdst is None:
            self.writedirective(actionstr, ipsrc, ipdst, ipproto, ipport,
                                macproto, macsrc, "0/0")
        else:
            for x in macdst:
                self.writedirective(actionstr, ipsrc, ipdst, ipproto, ipport,
                                    macproto, macsrc, x)

    def writedirective(self, actionstr, ipsrc, ipdst, ipproto, ipport,
                       macproto, macsrc, macdst):
        s = "%s %s %s %s %s %s %s %s %s ''\n" % (
            self.nextdirectiveid, actionstr,
            macdst, macsrc, macproto,
            ipdst, ipsrc, ipproto, ipport)
        self.directives.append(s)

def allsubsets(keys, map):
    """Generator to compute all non-empty intersections of keyed sets.

    I'm not going to explain this fully.  The algorithm is similar as
    that to compute the powerset, but modified to compute what we're
    actually interested in: the non-empty intersections of all
    possible combinations of the keys to the map.

    The order in which the results are generated is important; each
    set must precede all its subsets.

    Implementation notes:

    1) In practice, we have a large number of keys whose corresponding
       sets have an empty intersection; in this case we can do it in
       O(n**2) time rather than O(2**n).

    2) The real savings, in practice, appears to come from collapsing
       duplicates ahead of time, since these are the most frequent
       cause for non-empty intersections.

    """
    xmap = []
    for key in keys:
        set = map[key]
        for xkey, xset in xmap:
            if sloppy_equals(set, xset):
                xkey.append(key)
                break
        else:
            xmap.append(([key], set))
    n = len(xmap)
    for i in range(n):
        ki, si = xmap[i]
        for j in range(i+1, n):
            kj, sj = xmap[j]
            sij = intersect(si, sj)
            if sij:
                kij = ki + kj
                for result in recurse_subsets(kij, sij, xmap, j+1, n):
                    yield result
                yield kij, sij
        yield ki, si

def recurse_subsets(key, set, xmap, i1, n):
    """Helper to do the recursive heavy lifting."""
    for i in range(i1, n):
        ki, si = xmap[i]
        sx = intersect(set, si)
        if sx:
            kx = key + ki
            for result in recurse_subsets(kx, sx, xmap, i+1, n):
                yield result
            yield kx, sx

def intersect(a, b):
    """Intersection between two sets of filter specs."""
    target = FuelSet()
    for x in a:
        for y in b:
            z = x.intersect(y)
            unify(target, z)
    return target

def unify(target, filter):
    """Filter union computation.

    The target is a mutable set of filters.  Update the target to
    include the filter argument.

    (Conceptually, this does target |= {filter}.)

    """
    if filter.isempty():
        return
    for f in target:
        if f.includes(filter):
            return
    for f in [f for f in target if filter.includes(f)]:
       target.remove(f)
    target.add(filter)

def sloppy_issubset(a, b):
    """Sloppy issubset() test for sets of filters.

    This may lie when it returns False, but not when it returns True.

    """
    for x in a:
        for y in b:
            if y.includes(x):
                break
        else:
            return False
    return True

def sloppy_equals(a, b):
    """Sloppy equivalence test for sets of filters.

    When this returns True, it's really true; when it returns False it
    may be a lie.

    """
    return sloppy_issubset(a, b) and sloppy_issubset(b, a)
