Announce: NetKeeper Firewall For Linux

Announce: NetKeeper Firewall For Linux

[Emmanuel Fleury]

Hi,

We'd like to announce the first alpha release of NetKeeper.
NetKeeper is a fast, decision diagram based firewall for Linux.

Current release includes (among other things) a stable kernel module
that allows a user filter packets based on header-field values, and
a performance evaluation demonstrating that there is a clear
performance advantages to use this approach.

For more details check out the netkeeper web-site:
    http://www.cs.auc.dk/~fleury/netkeeper/

Cheers,
    Mikkel & Emmanuel

Re: Announce: NetKeeper Firewall For Linux

[David S. Miller]

On Mon, 27 Oct 2003 21:13:32 +0100
Emmanuel Fleury <fleury@cs.auc.dk> wrote:

> For more details check out the netkeeper web-site:
>     http://www.cs.auc.dk/~fleury/netkeeper/

You may want to have a look at:

  http://www.cyberus.ca/~hadi/patches/action/README

which I believe is the way to implement these kinds
of things.

Re: Announce: NetKeeper Firewall For Linux

[Emmanuel Fleury]

Hi,

On Tue, 2003-10-28 at 10:42, David S. Miller wrote:
> On Mon, 27 Oct 2003 21:13:32 +0100
> Emmanuel Fleury <fleury@cs.auc.dk> wrote:
> 
> > For more details check out the netkeeper web-site:
> >     http://www.cs.auc.dk/~fleury/netkeeper/
> 
> You may want to have a look at:
> 
>   http://www.cyberus.ca/~hadi/patches/action/README
> 
> which I believe is the way to implement these kinds
> of things.

Actually, that is exactly the direction which we have been aiming at.

Thanks for this valuable input.

Regards
-- 
Mikkel & Emmanuel

Re: Announce: NetKeeper Firewall For Linux

[jamal]

Hi,

On Tue, 2003-10-28 at 05:07, Emmanuel Fleury wrote:
> Hi,
> 
> On Tue, 2003-10-28 at 10:42, David S. Miller wrote:
> > On Mon, 27 Oct 2003 21:13:32 +0100
> > Emmanuel Fleury <fleury@cs.auc.dk> wrote:
> > 
> > > For more details check out the netkeeper web-site:
> > >     http://www.cs.auc.dk/~fleury/netkeeper/
> > 
> > You may want to have a look at:
> > 
> >   http://www.cyberus.ca/~hadi/patches/action/README
> > 
> > which I believe is the way to implement these kinds
> > of things.
> 
> Actually, that is exactly the direction which we have been aiming at.


You seem to be attempting to replicate that functionalilty actually;->
(as opposed to using it). Therefore you are going to miss a lot of good
things. What was posted already is just the beggining.
If you want to incorporate i can send you the latest patches (posted
patches have intentional bugs to see who is actually testing). You seem
to be already hooking into netfilter btw so not sure how easy it would
be for you;
Why do you have a limit to 8 actions?

BTW, since you compile your filters, how fast are you at adding rules?
What about dynamic in kernel rules (such as those that may be created by
contracking) - do you have to cross to user space to compile them?
- Is there any reason you move the commit decision to the kernel?
Could this not have been done in user space?
I have doubts how fast you can install rules - which is a fundamental
measure of good filters.

cheers,
jamal

Re: Announce: NetKeeper Firewall For Linux

[Emmanuel Fleury]

Hi,

On Wed, 2003-11-05 at 04:00, jamal wrote:
> 
> You seem to be attempting to replicate that functionality actually;->
> (as opposed to using it). Therefore you are going to miss a lot of 
> good things. What was posted already is just the beggining.

I'm not sure it is the case (but I might have missed the point).

My first answer to David S. Miller was probably misleading. What we are
trying to do is to investigate an alternate algorithm to do packet
classification. Our overall goal is not to produce a shiny tool that
goes into Linux, but a new scheme which is more scalable than the one
that everybody is using right now (i.e. the "world famous"
classification based on rulesets).

If our scheme can be useful and is, at some point, included in one
existing tool, I would be the first one to take the netkeeper code and
put it to the trash (as it serve only to demonstrate and tune our
scheme).

So do not consider us as "yet another concurrent project to fight with",
because we are not really aiming at the same thing. :)

> If you want to incorporate i can send you the latest patches (posted
> patches have intentional bugs to see who is actually testing). You
> seem to be already hooking into netfilter btw so not sure how easy it
> would be for you;

Anyway, reading some new code can give us nice ideas. 
We would be pleased to see what you've already achieved.

> Why do you have a limit to 8 actions?

This limit is totally artificial.

Basically, the story is that we had a union in a struct and we filled up
the memory space with these actions so that no memory was left behind.

We decided (on arbitrary basis) that nobody would attach more than 8
different actions to a precise packet. We also though that having 256
different actions would be enough.

In fact, these two limits (8 and 256) are totally artificial and
have been introduced in our prototype just because it was "convenient".
We can extend the list of actions by using a chained list and code the
actions on a bigger variable than a byte.

> BTW, since you compile your filters, how fast are you at adding rules?

So, here, you are hitting the sensitive spot !

In fact, we are totally ignorant of what are the requirements on these
dynamic updates in networking. So any discussion about this is extremely
valuable for us.

For your question, the theory (and the practice) is telling us that the
time to add a new rule to an existing ruleset depend essentially of the
complexity of the already existing ruleset.

Don't miss my point, the number of rules which compose the ruleset is
not the only parameter. Because, as your are going through an
optimization a ruleset with a lot of trivial rules is simplified and
will be trivial at the end.

Therefore, it essentially depend on the ruleset to which you are adding
your new rule. 

But, we still have to work on this part. The way we have coded the
compiler is very simple and we have already some ideas on how to
optimize it.

Actually, a good thing for us would be to know what are your expectation
in matter of adding a new rule. What is "acceptable" and what is "not".

And, now, some tables with numbers:

+--------+---------+-------+-------+----------+
| #rules | time(s) | nodes | edges | size(KB) |
+--------+---------+-------+-------+----------+
|     10 |   0.01  |    28 |   102 |    1.584 |
|     25 |   0.03  |    77 |   279 |    4.296 |
|     50 |   0.11  |   128 |   481 |    7.332 |
|    100 |   0.44  |   232 |   891 |   13.500 |
|    250 |   3.44  |   542 |  2109 |   31.836 |
|    500 |  19.14  |   998 |  3952 |   59.424 |
|  1,000 |  37.72  |  1884 |  7544 |  113.160 |
|  2,500 |  102.1  |  4289 | 17493 |  261.408 |
|  5,000 |  237.0  |  7678 | 31880 |  474.720 |
| 10,000 |  571.4  | 13420 | 57417 |  850.068 |
| 25,000 | 1832.0  | 24657 |116673 | 1695.984 |
| 50,000 | 5221.0  | 37416 |198754 | 2834.064 |
+--------+---------+-------+-------+----------+

The rulesets considered here are totally artificially generated and are
matching our worst case in term of computing time.

Of course your question was about taking one of this big filters and
then add one tiny winny rule to it. So, I guess the time to do so would
be at most 1s (in the very worst case, I would say).

> What about dynamic in kernel rules (such as those that may be created
> by contracking) - do you have to cross to user space to compile them?

We have some ideas on how to handle it. But for now, the scheme is
totally static. I would say that we are keeping this area of research
(stateful inspection) for later. :)

> - Is there any reason you move the commit decision to the kernel?
> Could this not have been done in user space?

Yes, definitely.

When coding in the kernel, we are coding with the idea that: 
   « The kernel should defend itself against user-space. »

So, when the user say: "Commit". 

The kernel will first check the decision diagram for safety (no NULL
pointers, out of range variables, no loops, etc) and depending of the
tests, will take the decision to commit or not.

Actually, I think I read some stuff about it on the Netfilter-devel
mailing-list. As far as I remember, there was a similar problem in
netfilter as the safety of the whole thing is never really tested in
depth. Therefore you can end-up with some loops or inconsistancy 
(WARNING: I'm not sure about it!).

> I have doubts how fast you can install rules - which is a fundamental
> measure of good filters.

The fact is that theory is saying that optimizing is a complex problem
(but it still has a polynomial time complexity ). But, we can for sure
improve A LOT our current tools. The problem for us is that we do not
know against what we are fighting ! We really need some hints on how
fast should be this operation (just to see if it is possible or not in
our scheme).

PS: I would like also to say here that we got a really great feed back
from the nf-hipac team. So, thank a lot to Michael Bellion and Thomas
Heinz.

Regards
-- 
Emmanuel

Netkeeper (An IDD firewall) http://www.cs.auc.dk/~fleury/netkeeper/

Re: Announce: NetKeeper Firewall For Linux

[jamal]

Hi,

On Wed, 2003-11-05 at 10:28, Emmanuel Fleury wrote: 
> Hi,
> 
> On Wed, 2003-11-05 at 04:00, jamal wrote:
> > 
> > You seem to be attempting to replicate that functionality actually;->
> > (as opposed to using it). Therefore you are going to miss a lot of 
> > good things. What was posted already is just the beggining.
> 
> I'm not sure it is the case (but I might have missed the point).
> 

Yes, i think you missed my point ;-> 
You guys are doing a great job at coming up with some good packet
classification algorithm(s). I wanna encourage you to continue doing
that. 
OTOH, I have spent a lot of time thinking and coming up with a good
architecture for the action part (that follows classification). So it
will be a shame if you miss that because you happened to see one
good thing in the old code.
Putting the two together will result in some good things. You trying to
redo what i am doing will mean you are always a few steps behind[1]. Now
if you can do it better than what i have, then you can convert me 
too - thats the way opensource works. 

> Anyway, reading some new code can give us nice ideas. 
> We would be pleased to see what you've already achieved.
> 

Lets work together instead of you trying to get nice ideas from
my new code. This way you benefit from any evolution i have; and i have
lots coming down.
You must switch to making your code tc filter capable to do this.

> > Why do you have a limit to 8 actions?
> 
> This limit is totally artificial.
> 
> Basically, the story is that we had a union in a struct and we filled up
> the memory space with these actions so that no memory was left behind.

> We decided (on arbitrary basis) that nobody would attach more than 8
> different actions to a precise packet. We also though that having 256
> different actions would be enough.
> 

Probably true; but no point in making the limits when you dont have to.

> In fact, these two limits (8 and 256) are totally artificial and
> have been introduced in our prototype just because it was "convenient".
> We can extend the list of actions by using a chained list and code the
> actions on a bigger variable than a byte.
> 

I dont understand why you even have this byte to encode an action.
Look at my code.

> > BTW, since you compile your filters, how fast are you at adding rules?
> 
> So, here, you are hitting the sensitive spot !
> 
> In fact, we are totally ignorant of what are the requirements on these
> dynamic updates in networking. So any discussion about this is extremely
> valuable for us.
> 

Anything that requires "connection setup" to dynamically add rules is a
candidate. Think Voip SIP Proxy server for example which will insert
rules; think any authentication schemes that are needed before
installing rules, think tcp-splicing etc.

> For your question, the theory (and the practice) is telling us that the
> time to add a new rule to an existing ruleset depend essentially of the
> complexity of the already existing ruleset.
> 

I think thats a design issue. For example while u32 classifier may not
process as fast as you (lookups would take longer relatively ) - its
insertion time is independent of the complexity of the rules.
Lakshman (sp?) had a good paper on the tradeoffs between memory space
used, lookup times and insertion times (there was another variable) and
i think he may have proved you cant have all of them work well at the
same time.

> Don't miss my point, the number of rules which compose the ruleset is
> not the only parameter. Because, as your are going through an
> optimization a ruleset with a lot of trivial rules is simplified and
> will be trivial at the end.
> 
> Therefore, it essentially depend on the ruleset to which you are adding
> your new rule. 
> 
> But, we still have to work on this part. The way we have coded the
> compiler is very simple and we have already some ideas on how to
> optimize it.
> 
> Actually, a good thing for us would be to know what are your expectation
> in matter of adding a new rule. What is "acceptable" and what is "not".
> 
> And, now, some tables with numbers:
> 
> +--+--+--+--+--+
> | #rules | time(s) | nodes | edges | size(KB) |
> +--+--+--+--+--+
> |     10 |   0.01  |    28 |   102 |    1.584 |
> |     25 |   0.03  |    77 |   279 |    4.296 |
> |     50 |   0.11  |   128 |   481 |    7.332 |
> |    100 |   0.44  |   232 |   891 |   13.500 |
> |    250 |   3.44  |   542 |  2109 |   31.836 |
> |    500 |  19.14  |   998 |  3952 |   59.424 |
> |  1,000 |  37.72  |  1884 |  7544 |  113.160 |
> |  2,500 |  102.1  |  4289 | 17493 |  261.408 |
> |  5,000 |  237.0  |  7678 | 31880 |  474.720 |
> | 10,000 |  571.4  | 13420 | 57417 |  850.068 |
> | 25,000 | 1832.0  | 24657 |116673 | 1695.984 |
> | 50,000 | 5221.0  | 37416 |198754 | 2834.064 |
> +--+--+--+--+--+
> 

So if you add rule #50000 while there are already 49999 existing
it will take over an hour to install in the worst case, did i understand
this correctly?

> The rulesets considered here are totally artificially generated and are
> matching our worst case in term of computing time.
> 
> Of course your question was about taking one of this big filters and
> then add one tiny winny rule to it. So, I guess the time to do so would
> be at most 1s (in the very worst case, I would say).
> 

Ok, so i didnt understand your table above then. 1s is very bad;
actually i shouldnt say that since i dont have numbers infront of me of
what is considered good. I will look this up

> > What about dynamic in kernel rules (such as those that may be created
> > by contracking) - do you have to cross to user space to compile them?
> 
> We have some ideas on how to handle it. But for now, the scheme is
> totally static. I would say that we are keeping this area of research
> (stateful inspection) for later. :)
> 

Which is fine. I would say for something like firewalling you have a
desirable feature of very optimized lookups.

> > - Is there any reason you move the commit decision to the kernel?
> > Could this not have been done in user space?
> 
> Yes, definitely.
> 
> When coding in the kernel, we are coding with the idea that: 
>    « The kernel should defend itself against user-space. »
> 
> So, when the user say: "Commit". 
> 
> The kernel will first check the decision diagram for safety (no NULL
> pointers, out of range variables, no loops, etc) and depending of the
> tests, will take the decision to commit or not.
> 
> Actually, I think I read some stuff about it on the Netfilter-devel
> mailing-list. As far as I remember, there was a similar problem in
> netfilter as the safety of the whole thing is never really tested in
> depth. Therefore you can end-up with some loops or inconsistancy 
> (WARNING: I'm not sure about it!).
> 

That sounds more like still a user space problem ;->
I saw in your paper briefly that you have infact a checker for something
like this. That checker should run outside the kernel in my opinion.
The value in putting the commit in the kernel maybe for say making sure
you get the memory allocation you want etc before installing. But even
this is not a strong arguement. 

> > I have doubts how fast you can install rules - which is a fundamental
> > measure of good filters.
> 
> The fact is that theory is saying that optimizing is a complex problem
> (but it still has a polynomial time complexity ). But, we can for sure
> improve A LOT our current tools. The problem for us is that we do not
> know against what we are fighting ! We really need some hints on how
> fast should be this operation (just to see if it is possible or not in
> our scheme).
> 

So i would suggest that you look at the Lakshman paper for starters.
In my view the most important issues in priority order are:
lookup speed regardless of table size, insert/delete rate regardless of
table size, Capacity (should be able to go to the hundreds of thousands
of flows), memory use for storage purposes - although i dont really care
very much about these since memory is cheap these days.

> PS: I would like also to say here that we got a really great feed back
> from the nf-hipac team. So, thank a lot to Michael Bellion and Thomas
> Heinz.
> 

I am sorry i confused you with them;-> I suppose you are both from .dk.

cheers,
jamal

[1]I briefly looked at your paper and it seems the only action you had
initially was DENY or ACCEPT.
Looking at your code you now have an action dispatcher that seems
to be exactly like the old one i have (you havent implemented code
around it but you have the hooks in place). This is why i made the
comment. 

Re: Announce: NetKeeper Firewall For Linux

[Emmanuel Fleury]

Hi,

On Thu, 2003-11-06 at 04:29, jamal wrote:
> 
> Yes, i think you missed my point ;-> 

Oops ! :)

> You guys are doing a great job at coming up with some good packet
> classification algorithm(s). I wanna encourage you to continue doing
> that. 
> OTOH, I have spent a lot of time thinking and coming up with a good
> architecture for the action part (that follows classification). So it
> will be a shame if you miss that because you happened to see one
> good thing in the old code.
>
Putting the two together will result in some good things. You trying to
> redo what i am doing will mean you are always a few steps behind[1]. Now
> if you can do it better than what i have, then you can convert me 
> too - thats the way opensource works. 

Ok, actually we were so focused on the classification scheme that we
didn't really try to do something nice for the actions... In a matter of
facts, we have only one action (log) and it is not even implemented. 

So, we will definitely look at your code to avoid us to have to think
about this part (and avoid to have to recode the actions). 

> Anything that requires "connection setup" to dynamically add rules is a
> candidate. Think Voip SIP Proxy server for example which will insert
> rules; think any authentication schemes that are needed before
> installing rules, think tcp-splicing etc.

Ok, but you are speaking about non permanent rules (aka dynamic rules). 

The idea we have to handle stateful inspection is to have the core
filter (totally static) plus some "state" nodes placed inside the IDD
which are calling a function to evaluate the "state" of the packet
(based on some informations given by the packet header and a database of
the open connections). When reaching the terminals, one of the action
can be to change the state of the connection.

I guess that what you describe can be handled by such mechanism 
(better than changing the ruleset each time). As it is handled outside
of the IDD, this take only the time of the look-up in the database and
the time to modify the database (when necessary).

But, I over simplified things here, this scheme is far from being ready
at this point. We should investigate it more in depth (we need more
time!!!). 

> I think thats a design issue. For example while u32 classifier may not
> process as fast as you (lookups would take longer relatively ) - its
> insertion time is independent of the complexity of the rules.
> Lakshman (sp?) had a good paper on the tradeoffs between memory space
> used, lookup times and insertion times (there was another variable) and
> i think he may have proved you cant have all of them work well at the
> same time.

Ok. Could you give more details about the references of this paper from
Lakshman ?

> So if you add rule #50000 while there are already 49999 existing
> it will take over an hour to install in the worst case, did i understand
> this correctly?

Yes (I messed up things in the following paragraph), you are totally
right here. I totally forgot that you have to deal with rule-overlapping
which is actually making things incredibly sequential).

> > Of course your question was about taking one of this big filters and
> > then add one tiny winy rule to it. So, I guess the time to do so would
> > be at most 1s (in the very worst case, I would say).

I am wrong here, terribly wrong. The thing is that is you add a rule at
the end of your filter, you will not have to rebuild it, but inserting a
rule randomly in the list is... bad. For now, we don't have any good
algorithm to insert a rule, so we just rebuild the whole thing.

> > When coding in the kernel, we are coding with the idea that: 
> >    « The kernel should defend itself against user-space. »
> > 
> > So, when the user say: "Commit". 
> > 
> > The kernel will first check the decision diagram for safety (no NULL
> > pointers, out of range variables, no loops, etc) and depending of the
> > tests, will take the decision to commit or not.
> 
> That sounds more like still a user space problem ;->

No.

Users shouldn't be able to break the kernel just by misconfiguring it.

> I saw in your paper briefly that you have infact a checker for something
> like this. 

If you are speaking about the "network access verifier", it is something
totally different. But, I might have misunderstood you.

> In my view the most important issues in priority order are:
> lookup speed regardless of table size, insert/delete rate regardless of
> table size, Capacity (should be able to go to the hundreds of thousands
> of flows), memory use for storage purposes - although i dont really care
> very much about these since memory is cheap these days.

Ok, I think we have to work on the insert/delete part. I know for a fact
that insert/delete inside the IDD is not an option (as the complexity of
this operation is too high), so we will look at some other way to handle
it.

> > PS: I would like also to say here that we got a really great feed back
> > from the nf-hipac team. So, thank a lot to Michael Bellion and Thomas
> > Heinz.
> > 
> 
> I am sorry i confused you with them;-> I suppose you are both from .dk.

No, Michael and Thomas are from Germany. Mikkel Christiansen is from
Denmark and I'm from France (working in Denmark currently).

> [1]I briefly looked at your paper and it seems the only action you had
> initially was DENY or ACCEPT.

We can extend this without any problem.

> Looking at your code you now have an action dispatcher that seems
> to be exactly like the old one i have (you havent implemented code
> around it but you have the hooks in place). This is why i made the
> comment. 

Actually, as I said, we were just no so concerned about the handling of
the actions, so we just did it in the most natural way (for us). It is a
good sign that we are meeting your very first implementation. 

Regards
-- 
Emmanuel Fleury

Computer Science Department, |  Office: B1-201
Aalborg University,          |  Phone:  +45 96 35 72 23
Fredriks Bajersvej 7E,       |  Fax:    +45 98 15 98 89
9220 Aalborg East, Denmark   |  Email:  fleury@cs.auc.dk

Re: Announce: NetKeeper Firewall For Linux

[jamal]

On Thu, 2003-11-06 at 05:26, Emmanuel Fleury wrote:

> Ok, actually we were so focused on the classification scheme that we
> didn't really try to do something nice for the actions... In a matter of
> facts, we have only one action (log) and it is not even implemented. 
> 
> So, we will definitely look at your code to avoid us to have to think
> about this part (and avoid to have to recode the actions). 
> 

I am asking you to switch to the TC code. I dont think i am making my
point across ;->[1]. Integrate your classifer like any other tc
classifier and then you dont have to look at my code unless you really
want to.

> > Anything that requires "connection setup" to dynamically add rules is a
> > candidate. Think Voip SIP Proxy server for example which will insert
> > rules; think any authentication schemes that are needed before
> > installing rules, think tcp-splicing etc.
> 
> Ok, but you are speaking about non permanent rules (aka dynamic rules). 
> 

These types are most dominant these days in my opinion unless you are a
single user behind a DSL line.

> The idea we have to handle stateful inspection is to have the core
> filter (totally static) plus some "state" nodes placed inside the IDD
> which are calling a function to evaluate the "state" of the packet
> (based on some informations given by the packet header and a database of
> the open connections). 

Isnt the state database another classifier and therefore you will be
faced with the same challenges for it? 
I dont think you wuill get a free ride putting the state lookups
somewhere else.

> When reaching the terminals, one of the action
> can be to change the state of the connection.

tc allows you to have multiple cascaded classifiers; so 
you could "reclassify" and jump to a state classifier.
I think the other guys from .dk also had their own scheme of achieving
the same goal. Being able to do this in my opinion is architecturally
cleaner.

> I guess that what you describe can be handled by such mechanism 
> (better than changing the ruleset each time). As it is handled outside
> of the IDD, this take only the time of the look-up in the database and
> the time to modify the database (when necessary).
> 

This is true if you consider the state database to be a different
problem other than a classification one. 

> But, I over simplified things here, this scheme is far from being ready
> at this point. We should investigate it more in depth (we need more
> time!!!). 
> 

no problem.

> > I think thats a design issue. For example while u32 classifier may not
> > process as fast as you (lookups would take longer relatively ) - its
> > insertion time is independent of the complexity of the rules.
> > Lakshman (sp?) had a good paper on the tradeoffs between memory space
> > used, lookup times and insertion times (there was another variable) and
> > i think he may have proved you cant have all of them work well at the
> > same time.
> 
> Ok. Could you give more details about the references of this paper from
> Lakshman ?
> 

You are in academia, you better make sure you are aware of these 
things ;-> 

The Lakshman paper describes an algorithm but i remember it was the
first to introduce classification constraints:

T.V.Lakshman and D.Stiliadis. High Speed Policy-based Packet Forwarding
Using Efficient Multi-dimensional Range Matching. Proceedings of ACM
Sigcomm98

Another good paper to look at is:

A.Feldmann and S.Muthukrishnan. Tradeoffs for packet classification.
Proceedings of IEEE Infocom2000

> I am wrong here, terribly wrong. The thing is that is you add a rule at
> the end of your filter, you will not have to rebuild it, but inserting a
> rule randomly in the list is... bad. For now, we don't have any good
> algorithm to insert a rule, so we just rebuild the whole thing.
> 

Then you have some work to do

> > > When coding in the kernel, we are coding with the idea that: 
> > >    « The kernel should defend itself against user-space. »
> > > 
> > > So, when the user say: "Commit". 
> > > 
> > > The kernel will first check the decision diagram for safety (no NULL
> > > pointers, out of range variables, no loops, etc) and depending of the
> > > tests, will take the decision to commit or not.
> > 
> > That sounds more like still a user space problem ;->
> 
> No.
> 
> Users shouldn't be able to break the kernel just by misconfiguring it.
> 

Couldnt you, knowing the rules already existing check for breakage in
user space?

> > I saw in your paper briefly that you have infact a checker for something
> > like this. 
> 
> If you are speaking about the "network access verifier", it is something
> totally different. But, I might have misunderstood you.
> 

I meant that network access verifier. I believe you should be able to
verify things not only just in user space bu even in a remote location
(example a network management station). Now this stuff is interesting.

> > In my view the most important issues in priority order are:
> > lookup speed regardless of table size, insert/delete rate regardless of
> > table size, Capacity (should be able to go to the hundreds of thousands
> > of flows), memory use for storage purposes - although i dont really care
> > very much about these since memory is cheap these days.
> 
> Ok, I think we have to work on the insert/delete part. I know for a fact
> that insert/delete inside the IDD is not an option (as the complexity of
> this operation is too high), so we will look at some other way to handle
> it.
> 

cool. Looking forward to see some of your thoughts on this when you have
experienced it.

cheers,
jamal

[1] Look at your action code dispatch name and my old one and note the
name being _exactly_ the same. I dont think it is a big coincidence and
i dont think you had any bad intent. I am just saying you can continue
doing that or you can integrate. Why dont we drop this part of the
discussion if you dont wanna move forward to the tc code? I thought you
agreed with Dave to integrate ;->

Re: Announce: NetKeeper Firewall For Linux

[Mikkel Christiansen]

jamal wrote:

>On Thu, 2003-11-06 at 05:26, Emmanuel Fleury wrote:
>
>  
>
>>Ok, actually we were so focused on the classification scheme that we
>>didn't really try to do something nice for the actions... In a matter of
>>facts, we have only one action (log) and it is not even implemented. 
>>
>>So, we will definitely look at your code to avoid us to have to think
>>about this part (and avoid to have to recode the actions). 
>>
>>    
>>
>
>I am asking you to switch to the TC code. I dont think i am making my
>point across ;->[1]. Integrate your classifer like any other tc
>classifier and then you dont have to look at my code unless you really
>want to.
>
>  
>

If we integrate it would mean a new/alternative interface
to tc where you compile the filter/configuratoin before
uploading. We believe this is a good thing since it allows
admins to (syntax) check the filter before inserting it.
I believe the guys from shorewall sees this as a missing
feature of iptables.

Would you consider such an interface for tc good are bad?

>>>Anything that requires "connection setup" to dynamically add rules is a
>>>candidate. Think Voip SIP Proxy server for example which will insert
>>>rules; think any authentication schemes that are needed before
>>>installing rules, think tcp-splicing etc.
>>>      
>>>
>>Ok, but you are speaking about non permanent rules (aka dynamic rules). 
>>
>>    
>>
>
>These types are most dominant these days in my opinion unless you are a
>single user behind a DSL line.
>
>  
>
>>The idea we have to handle stateful inspection is to have the core
>>filter (totally static) plus some "state" nodes placed inside the IDD
>>which are calling a function to evaluate the "state" of the packet
>>(based on some informations given by the packet header and a database of
>>the open connections). 
>>    
>>
>
>Isnt the state database another classifier and therefore you will be
>faced with the same challenges for it? 
>I dont think you wuill get a free ride putting the state lookups
>somewhere else.
>
>  
>
current scheme cant handle dynamic rules - and it will
be a while (if ever) before it can.

>>When reaching the terminals, one of the action
>>can be to change the state of the connection.
>>    
>>
>
>tc allows you to have multiple cascaded classifiers; so 
>you could "reclassify" and jump to a state classifier.
>I think the other guys from .dk also had their own scheme of achieving
>the same goal. Being able to do this in my opinion is architecturally
>cleaner.
>
>  
>
>>I guess that what you describe can be handled by such mechanism 
>>(better than changing the ruleset each time). As it is handled outside
>>of the IDD, this take only the time of the look-up in the database and
>>the time to modify the database (when necessary).
>>
>>    
>>
>
>This is true if you consider the state database to be a different
>problem other than a classification one. 
>
>  
>
>>But, I over simplified things here, this scheme is far from being ready
>>at this point. We should investigate it more in depth (we need more
>>time!!!). 
>>
>>    
>>
>
>no problem.
>
>  
>
>>>I think thats a design issue. For example while u32 classifier may not
>>>process as fast as you (lookups would take longer relatively ) - its
>>>insertion time is independent of the complexity of the rules.
>>>Lakshman (sp?) had a good paper on the tradeoffs between memory space
>>>used, lookup times and insertion times (there was another variable) and
>>>i think he may have proved you cant have all of them work well at the
>>>same time.
>>>      
>>>
>>Ok. Could you give more details about the references of this paper from
>>Lakshman ?
>>
>>    
>>
>
>You are in academia, you better make sure you are aware of these 
>things ;-> 
>
>  
>
>The Lakshman paper describes an algorithm but i remember it was the
>first to introduce classification constraints:
>
>T.V.Lakshman and D.Stiliadis. High Speed Policy-based Packet Forwarding
>Using Efficient Multi-dimensional Range Matching. Proceedings of ACM
>Sigcomm98
>
>Another good paper to look at is:
>
>A.Feldmann and S.Muthukrishnan. Tradeoffs for packet classification.
>Proceedings of IEEE Infocom2000
>
>  
>
>>I am wrong here, terribly wrong. The thing is that is you add a rule at
>>the end of your filter, you will not have to rebuild it, but inserting a
>>rule randomly in the list is... bad. For now, we don't have any good
>>algorithm to insert a rule, so we just rebuild the whole thing.
>>
>>    
>>
>
>Then you have some work to do
>
>  
>
>>>>When coding in the kernel, we are coding with the idea that: 
>>>>   « The kernel should defend itself against user-space. »
>>>>
>>>>So, when the user say: "Commit". 
>>>>
>>>>The kernel will first check the decision diagram for safety (no NULL
>>>>pointers, out of range variables, no loops, etc) and depending of the
>>>>tests, will take the decision to commit or not.
>>>>        
>>>>
>>>That sounds more like still a user space problem ;->
>>>      
>>>
>>No.
>>
>>Users shouldn't be able to break the kernel just by misconfiguring it.
>>
>>    
>>
>
>Couldnt you, knowing the rules already existing check for breakage in
>user space?
>
>  
>
no - if someone decided to write their own "client/compiler" in
userspace they could potentially produce a broken IDD - that
could crash the kernel!

>>>I saw in your paper briefly that you have infact a checker for something
>>>like this. 
>>>      
>>>
>>If you are speaking about the "network access verifier", it is something
>>totally different. But, I might have misunderstood you.
>>
>>    
>>
>
>I meant that network access verifier. I believe you should be able to
>verify things not only just in user space bu even in a remote location
>(example a network management station). Now this stuff is interesting.
>
>  
>
>>>In my view the most important issues in priority order are:
>>>lookup speed regardless of table size, insert/delete rate regardless of
>>>table size, Capacity (should be able to go to the hundreds of thousands
>>>of flows), memory use for storage purposes - although i dont really care
>>>very much about these since memory is cheap these days.
>>>      
>>>
>>Ok, I think we have to work on the insert/delete part. I know for a fact
>>that insert/delete inside the IDD is not an option (as the complexity of
>>this operation is too high), so we will look at some other way to handle
>>it.
>>
>>    
>>
>
>cool. Looking forward to see some of your thoughts on this when you have
>experienced it.
>
>cheers,
>jamal
>
>[1] Look at your action code dispatch name and my old one and note the
>name being _exactly_ the same. I dont think it is a big coincidence and
>i dont think you had any bad intent. I am just saying you can continue
>doing that or you can integrate. Why dont we drop this part of the
>discussion if you dont wanna move forward to the tc code? I thought you
>agreed with Dave to integrate ;->
>
>  
>
Well, then you need to think again - it is in fact a coincidence!

Cheers
    Mikkel

Re: Announce: NetKeeper Firewall For Linux

[Henrik Nordstrom]

On Sun, 9 Nov 2003, Mikkel Christiansen wrote:

> uploading. We believe this is a good thing since it allows
> admins to (syntax) check the filter before inserting it.
> I believe the guys from shorewall sees this as a missing
> feature of iptables.

See iptables-restore. It is exacly this (compile whole ruleset before
insert) for iptables. The only thing missing is that it only compiles one
table at a time.

Regards
Henrik

Re: Announce: NetKeeper Firewall For Linux

[jamal]

Hi,

On Sun, 2003-11-09 at 14:55, Mikkel Christiansen wrote:

> >
> Integrate your classifer like any other tc
> >classifier and then you dont have to look at my code unless you really
> >want to.  
> >
> 
> If we integrate it would mean a new/alternative interface
> to tc where you compile the filter/configuratoin before
> uploading.

Why cant you use the same interface that exists today - the one that is
used to load new filter rules?

>  We believe this is a good thing since it allows
> admins to (syntax) check the filter before inserting it.

Sure. It will be nice to have something like that in user space.

> I believe the guys from shorewall sees this as a missing
> feature of iptables.
> 
> Would you consider such an interface for tc good are bad?
> 

Refer to my comment above: I dont think you need anything new. Look at a
simple classifier like fwmark and comment if you need something new.

> >Isnt the state database another classifier and therefore you will be
> >faced with the same challenges for it? 
> >I dont think you wuill get a free ride putting the state lookups
> >somewhere else.
> >
> current scheme cant handle dynamic rules - and it will
> be a while (if ever) before it can.
> 

Please think about that problem - otherwise you get an C in your course
work from me ;-> (F would be too harsh ;->)

> >
> >Couldnt you, knowing the rules already existing check for breakage in
> >user space?
> >
> no - if someone decided to write their own "client/compiler" in
> userspace they could potentially produce a broken IDD - that
> could crash the kernel!
> 

I think it is nice to have a feature that does the verification in
user space before downloading.  
I didnt understand what you mean that someone else writes their own
"client/compiler". Arent you the one in charge of this compiler?
Why would you allow other people to write this compiler?

cheers,
jamal