Loop Detection

Loop Detection

[Thomas Heinz]

Hi

Michael Bellion and I are busy implementing user-defined chains support
for nf-hipac. When it comes to user-defined chains one has to
consider a way of detecting loops. Now, there are at least two
definitions of what a loop actually is. The netfilter one (Def1) and
and a "tighter" one (Def2).

Def1: The chains and their rules having another chain as target can
       be considered to define a directed graph. In this graph the
       chains are the nodes and for each chain X we have an edge
       (X, Y) if X contains a rule whose target is Y.
       Now, a loop exists if and only if the graph contains a cycle.

Example: Assume we have 3 chains: A, B, C. We only consider those
          rules within the chains that have another chain as target:
          A: Rule 1 -j B    B: Rule 2 -j A    C: Rule 4 -j B
             Rule 4 -j C
             Rule 5 -j C
             Rule 7 -j B
          The resulting graph is:
                     C
                   /\  \
                   /   \/
                  A <-> B
          This graph contains a cycle and therefore a loop according to
          Def1. If Rule 2 of Chain B is removed there is no loop.


The other definition which is tighter is:

Def2: If a packet is matched it traverses certain chains until a
       terminal target is reached. Those chains form a path.
       A loop exists if and only if there exists a packet whose path
       through the chains contains some chain at least twice.

Example: Assume we have 3 chains: INPUT, A, B.
          INPUT: (1) -s 1.0.0.0/16 -j A
                 (2) -s 2.0.0.0/16 -j B
          A:     (1) -s 1.0.0.0/24 -j B      B: (1) -s 2.0.0.0/24 -j A
                                                (2) -s 1.0.0.5 -j A
          Consider a packet with source ip 1.0.0.5 destined for the
          host running the firewall. The path is:
          INPUT, A, B, A, B, A, ...
          Clearly, there is a loop according to Def2. If rule (2) is
          removed from B there is no loop according to Def2 but there is
          still a loop according to Def1.

I hope the differences between the two definitions are clear. Obviously,
a loop according to Def2 always leads to a invalid ruleset but this is
not necessarily true for Def1.

Now, I'm asking you what definition is more beneficial to the users.
The question goes to both users and developers.

Clearly, a loop detection based on Def1 disallows some rulesets that are
indeed valid. On the other hand the question is whether such rulesets
really make sense. It is possible that Def1 is in fact more beneficial
to users in order to help them to design sane rulesets.

What is your opinion?


Regards,

Thomas

Re: Loop Detection

[Thomas Heinz]

I wrote:
> The other definition which is tighter is:
> 
> Def2: If a packet is matched it traverses certain chains until a
>       terminal target is reached. Those chains form a path.
>       A loop exists if and only if there exists a packet whose path
>       through the chains contains some chain at least twice.

It must be stated that implementing a loop detection based on Def2
is not possible if general function based matches are used (like
netfilter does).

As we want nf-hipac to support function based matches we have in fact
no choice. Our loop detection will use Def1.

Re: Loop Detection

[Michael Richardson]

My opinion is that if if you can define an algorithm or heuristic that would
permit a sufficiently clueful user and/or program to transform a valid chain
that failes Def1 into one that passes it, then you should go ahead with
just doing Def1, and provide no override.

]       ON HUMILITY: to err is human. To moo, bovine.           |  firewalls  [
]   Michael Richardson, Sandelman Software Works, Ottawa, ON    |net architect[
] mcr@sandelman.ottawa.on.ca http://www.sandelman.ottawa.on.ca/ |device driver[
] panic("Just another Debian GNU/Linux using, kernel hacking, security guy"); [