Loop Detection
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
Quoted 6 lines · 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.
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[ ] [email protected] http://www.sandelman.ottawa.on.ca/ |device driver[
] panic("Just another Debian GNU/Linux using, kernel hacking, security guy"); [