[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: fully transparent ftp-proxy?

On Thu, 31 Oct 2002 17:59:31 +0100, Daniel Hartmeier wrote:
> On Fri, Nov 01, 2002 at 02:14:58AM +1000, loki wrote:
> > having such a rule (or rules) has several other advantages, you could
> > create several trees, one for each proxy that requires it (include a
> > mechanism for the proxy to talk to its own tree). you could specify which
> > field of the state entry is variable (id still say that remote src port
> > would be th only one, but its nice to be flexible). you could specify tcp
> > flags and state modulation. whatever is needed for connections created by
> > the proxy.
> I can't think of a case where anything but the source port is missing,
> actually.
I just did, but in a way this is entirely unrelated to the proposed idea.
Filter rules are, in their own way, a lot like embryonic states.  They
contain some information that a state does, but not all.  Their other
significant difference is that matching a non-quick rule does not determine
whether the packet matches.
To me this suggests creating embryonic states corresponding to filter rules
and arranging them in trees; it feels like it would simplest to have the trees
rooted by interface, but that may not be true in practice.  At each node of
the tree would be an embryonic state.  For a packet to progress through the
tree, it must be compared to the embryonic states of the children of the
node it is currently in.  If it matches none of them, the block/pass rule of
its current node applies.  If it matches one of them, that node becomes the
packet's current node.  Processing ends when the packet reaches a terminal
node or no child of the current node matches the packet.  Quick rules would
always be terminal nodes.
The major difficulty, as far as I can tell, is in creating the tree.  No two
children of the same node could ever match the same packet or else the ruleset
becomes ambiguous.  Furthermore, the "most efficient" tree is probably
difficult to determine.  Even an inefficient tree would likely take a while to
create with a large ruleset, and I don't have any idea how one would insert or
delete rules into an existing tree.
The advantage, however, is that ruleset evaluation becomes very fast.  If the
tree is balanced, evaluation should be O(log n).  The worst case should be
a tree with a root and only terminal children, but that should still be O(n).
You lose skip steps with such a case, though, so performance would be worse
than it is now.  But it feels to me like it should be possible to avoid such a
pathological case with good tree construction.
Kyle R. Hofmann <[email protected]>