Help with a tough question. RE: Firewall rule inspection overhead.

I have no idea how to approach this question. Can anybody help? I'm
lost. Thx!

A firewall has S accept rules and receives R (packet/sec) traffic rate.
What is the total matching overhead in seconds if the cost of
evaluating one rule is X seconds and 50% is accepted (uniformly
distributed over rules). (Hint: firewalls are filtering devices that
inspecting incoming packets against policy rules sequentially till one
rule is matched)

Re: Help with a tough question. RE: Firewall rule inspection overhead.

In article <1160879734.071268.254860@b28g2000cwb.googlegroups.com>,
abstractclass wrote:
>I have no idea how to approach this question. Can anybody help? I'm
>lost. Thx!

>A firewall has S accept rules and receives R (packet/sec) traffic rate.
>What is the total matching overhead in seconds if the cost of
>evaluating one rule is X seconds and 50% is accepted (uniformly
>distributed over rules). (Hint: firewalls are filtering devices that
>inspecting incoming packets against policy rules sequentially till one
>rule is matched)

To answer the question, we have to make an assumption about the way the
firewall works, based upon hints in the way the question is phrased.

A normal firewall would have a mix of "accept" and "reject" rules, and
it would have a policy as to whether "running off the end of the rules"
meant to accept or to reject. In the question, we are not told whether
the policies being matched against are only "accept" or only "reject"
or are a mix of both, and we aren't told about what to do at the end of
the rules.

It makes a difference because we must know, "In order to accept a
packet, does that mean that S 'reject' rules were scanned and none
found applicable and so the packet was accepted by default, after X*S
seconds of work?" versus "In order to accept a packet, does that mean
that from 1 to S 'accept' rules were searched and one was found
applicable and so the packet was accepted explicitly after R * X
seconds of work (R being the rule number of the accepting rule)?"

It turns out that in this question, if we suppose -either- of those
models, then the answer will be the same -- the same because we are
told that exactly 1/2 are accepted and 1/2 rejected; if we were given
-any- other ratio, we would have to know the innards. But if it were a
mixed model, we'd need to know that as it would affect the
mathematics.

The phrase about 50% accepted "uniformly distributed over the rules"
hints that the model we are to use is "acceptance rules only, reject if
not accepted"; a filtering model of that style is quite poor at
expressing some common configurations.


Anyhow, if we do decide that we don't have a mixed accept/deny model,
then what you need to do to arrive at the calculation is to ask
yourself, "What is the -average- number of rules that are examined to
permit (deny) a packet?". Once that number is known, multiply that
average by the cost of processing that number of rules. Then calculate
the cost of the opposite way -- e.g., if the previous calculation was
for acceptance, then that would mean rejecting always required that all
S rules be examined; if the previous calculation was for rejection,
that that would mean -accepting always required examining all S rules.
Multiply that S rules by the cost per second per rule. You now have an
average cost to do it one one, and an average (fixed) cost to do it the
other way; multiply each of those costs by the relative probabilities
that that was the outcome, and add those two weighted costs together to
find the total average weighted cost.

Re: Help with a tough question. RE: Firewall rule inspection overhead.

thanks for the thorough reply :). i'm still a bit lost though. i did
a bit of reading from the IEEE website that shows the average number of
rules in a firewall is 144 based on one research. so does that mean
that S = 72 (half of 144, since 50% is accepted)? How would I go about
determining the cost to evaluate one rule? I'm sorry, I'm very
confused...

On Oct 14, 11:43 pm, rober...@hushmail.com (Walter Roberson) wrote:
> In article <1160879734.071268.254...@b28g2000cwb.googlegroups.com>,
>
> abstractclass wrote:
> >I have no idea how to approach this question. Can anybody help? I'm
> >lost. Thx!
> >A firewall has S accept rules and receives R (packet/sec) traffic rate.
> >What is the total matching overhead in seconds if the cost of
> >evaluating one rule is X seconds and 50% is accepted (uniformly
> >distributed over rules). (Hint: firewalls are filtering devices that
> >inspecting incoming packets against policy rules sequentially till one
> >rule is matched)To answer the question, we have to make an assumption about the way the
> firewall works, based upon hints in the way the question is phrased.
>
> A normal firewall would have a mix of "accept" and "reject" rules, and
> it would have a policy as to whether "running off the end of the rules"
> meant to accept or to reject. In the question, we are not told whether
> the policies being matched against are only "accept" or only "reject"
> or are a mix of both, and we aren't told about what to do at the end of
> the rules.
>
> It makes a difference because we must know, "In order to accept a
> packet, does that mean that S 'reject' rules were scanned and none
> found applicable and so the packet was accepted by default, after X*S
> seconds of work?" versus "In order to accept a packet, does that mean
> that from 1 to S 'accept' rules were searched and one was found
> applicable and so the packet was accepted explicitly after R * X
> seconds of work (R being the rule number of the accepting rule)?"
>
> It turns out that in this question, if we suppose -either- of those
> models, then the answer will be the same -- the same because we are
> told that exactly 1/2 are accepted and 1/2 rejected; if we were given
> -any- other ratio, we would have to know the innards. But if it were a
> mixed model, we'd need to know that as it would affect the
> mathematics.
>
> The phrase about 50% accepted "uniformly distributed over the rules"
> hints that the model we are to use is "acceptance rules only, reject if
> not accepted"; a filtering model of that style is quite poor at
> expressing some common configurations.
>
> Anyhow, if we do decide that we don't have a mixed accept/deny model,
> then what you need to do to arrive at the calculation is to ask
> yourself, "What is the -average- number of rules that are examined to
> permit (deny) a packet?". Once that number is known, multiply that
> average by the cost of processing that number of rules. Then calculate
> the cost of the opposite way -- e.g., if the previous calculation was
> for acceptance, then that would mean rejecting always required that all
> S rules be examined; if the previous calculation was for rejection,
> that that would mean -accepting always required examining all S rules.
> Multiply that S rules by the cost per second per rule. You now have an
> average cost to do it one one, and an average (fixed) cost to do it the
> other way; multiply each of those costs by the relative probabilities
> that that was the outcome, and add those two weighted costs together to
> find the total average weighted cost.

Re: Help with a tough question. RE: Firewall rule inspection overhead.

In article <1161021540.726548.74470@i42g2000cwa.googlegroups.com>,
abstractclass wrote:
>thanks for the thorough reply :). i'm still a bit lost though. i did
>a bit of reading from the IEEE website that shows the average number of
>rules in a firewall is 144 based on one research. so does that mean
>that S = 72 (half of 144, since 50% is accepted)?

No, in the mathematics I described, S would be 144, and you would
need to figure out what the average number is of those S rules that
need to be examined in order to make a decision. You will need some
very basic probability theory to calculate that, given the assumption
of uniform random distribution of acceptance.

You also have a problem that the IEEE study is almost certainly
examining firewalls in which each rule might be a permit or a deny,
rather than a model in which all the rules are permit rules or all
the rules are deny rules.

Firewalls that have a mix of permit and deny rules cannot fit into your
original question: your original question was phrased as indicating
that 50% of the packets were accepted "uniformly randomly distributed
over the S rules". If we do a uniform random distribution over S rules
each of which might be a permit or a deny, then if there is even one
deny rule in the mix, then because of the uniform random distribution
of acceptance requirement, and by the pigeon-hole principle, the
outcome would have to be that a deny rule would have to result in a
packet acceptance, which is a contradiction.

To phrase this a slightly different way: if you have S rules in
the firewall, and P of them are permit rules, and D of them are deny
rules, then any uniform random distribution of acceptance would
have to be uniformly randomly selecting from the P rules that -can-
accept, it not being possible to accept a packet based upon one of the
D deny rules. P/S can accept, D/S can only deny, but the question
requires that the probability of acceptance is equal over all S rules,
which can only hold true of D is 0.

So... the question cannot be applicable to real firewalls that
has a mix of accept and deny rules. The 144 number is not a number
you can use for this purpose.

A firewall that only has permit rules (as is implied by the question),
will on average have many more than 144 rules: if you do not have
deny rules available, then to permit traffic to everything -except-
something, you have to configure to permit the traffic to all the
other possibilities, leaving out the one you do not want to permit.
For example, to block ICMP Redirect while permitting all other ICMP,
you would have to specifically say that you wanted to accept
each of the other 255 possible ICMP "major numbers", probably requiring
255 rules to do so (but possibly requiring 65280 rules, if you
must specify the ICMP "minor number" in each rule.)


>How would I go about
>determining the cost to evaluate one rule?

In the context of the question you are given, you don't -- you are
being asked for a symbolic formula under the assumption that the cost
to evaluate one rule is X seconds. And this applies to trying to find
the value of S as well: don't go looking on IEEE and so on, because
the question is asking for a -formula-, not for a specific number based
upon studies.

The question you are given imposes the assumption that it takes the same
time to evaluate each rule, and the assumption that rules must be
evaluated from the beginning sequentially until one is matched. Neither
assumption holds up in real firewalls.

Cisco's IOS routers, for example, do not fetch some parts of the packet
until, when they are examining the rules for that packet, -first-
encounter a rule that requires looking at the information (such as the
TCP port number). Once that information has been fetch for a given
packet, then it is already present and that extra cost does not have to
be paid again for another check of that kind of information...

"compare, compare, compare, Woah! Stop and get the TCP port! Fetched it?
Okay, compare, compare, compare.. ah, we already know the port number,
no need to fetch it again, so don't wait, keep going... compare,
compare..."

There are also techniques that "compile" access-control lists in various
ways, using more space but reducing the average number of comparisons
that need to be made. For example, if the rules list a bunch of
addresses that are permitted access, then you can pre-scan the rules
and find the largest and smallest address that are permitted, and then
you can start the whole series of checks by seeing if the input is
smaller than the smallest or bigger than the largest, and if so reject
it immediately -- that's one to four comparisons done that saves examining
all S rules for packets that cannot possibly be accepted.


So... the question isn't realistic, firewalls don't really work that
way, but don't worry about it, because all you need to do is give them
a simple formula that fits with their assumptions. (The answer
is really simple, by the way...)

Re: Help with a tough question. RE: Firewall rule inspection overhead.

Thanks, I really appreciate your in-depth explanation, however this is
way over my head so I have no idea what the answer could be. The part
where it is asking for a figure in "seconds" led me to believe that I
was to offer a number as an answer. I give up here, but I do
appreciate all of your help. :)

On Oct 16, 2:38 pm, rober...@hushmail.com (Walter Roberson) wrote:
> In article <1161021540.726548.74...@i42g2000cwa.googlegroups.com>,
>
> abstractclass wrote:
> >thanks for the thorough reply :). i'm still a bit lost though. i did
> >a bit of reading from the IEEE website that shows the average number of
> >rules in a firewall is 144 based on one research. so does that mean
> >that S = 72 (half of 144, since 50% is accepted)?No, in the mathematics I described, S would be 144, and you would
> need to figure out what the average number is of those S rules that
> need to be examined in order to make a decision. You will need some
> very basic probability theory to calculate that, given the assumption
> of uniform random distribution of acceptance.
>
> You also have a problem that the IEEE study is almost certainly
> examining firewalls in which each rule might be a permit or a deny,
> rather than a model in which all the rules are permit rules or all
> the rules are deny rules.
>
> Firewalls that have a mix of permit and deny rules cannot fit into your
> original question: your original question was phrased as indicating
> that 50% of the packets were accepted "uniformly randomly distributed
> over the S rules". If we do a uniform random distribution over S rules
> each of which might be a permit or a deny, then if there is even one
> deny rule in the mix, then because of the uniform random distribution
> of acceptance requirement, and by the pigeon-hole principle, the
> outcome would have to be that a deny rule would have to result in a
> packet acceptance, which is a contradiction.
>
> To phrase this a slightly different way: if you have S rules in
> the firewall, and P of them are permit rules, and D of them are deny
> rules, then any uniform random distribution of acceptance would
> have to be uniformly randomly selecting from the P rules that -can-
> accept, it not being possible to accept a packet based upon one of the
> D deny rules. P/S can accept, D/S can only deny, but the question
> requires that the probability of acceptance is equal over all S rules,
> which can only hold true of D is 0.
>
> So... the question cannot be applicable to real firewalls that
> has a mix of accept and deny rules. The 144 number is not a number
> you can use for this purpose.
>
> A firewall that only has permit rules (as is implied by the question),
> will on average have many more than 144 rules: if you do not have
> deny rules available, then to permit traffic to everything -except-
> something, you have to configure to permit the traffic to all the
> other possibilities, leaving out the one you do not want to permit.
> For example, to block ICMP Redirect while permitting all other ICMP,
> you would have to specifically say that you wanted to accept
> each of the other 255 possible ICMP "major numbers", probably requiring
> 255 rules to do so (but possibly requiring 65280 rules, if you
> must specify the ICMP "minor number" in each rule.)
>
> >How would I go about
> >determining the cost to evaluate one rule?In the context of the question you are given, you don't -- you are
> being asked for a symbolic formula under the assumption that the cost
> to evaluate one rule is X seconds. And this applies to trying to find
> the value of S as well: don't go looking on IEEE and so on, because
> the question is asking for a -formula-, not for a specific number based
> upon studies.
>
> The question you are given imposes the assumption that it takes the same
> time to evaluate each rule, and the assumption that rules must be
> evaluated from the beginning sequentially until one is matched. Neither
> assumption holds up in real firewalls.
>
> Cisco's IOS routers, for example, do not fetch some parts of the packet
> until, when they are examining the rules for that packet, -first-
> encounter a rule that requires looking at the information (such as the
> TCP port number). Once that information has been fetch for a given
> packet, then it is already present and that extra cost does not have to
> be paid again for another check of that kind of information...
>
> "compare, compare, compare, Woah! Stop and get the TCP port! Fetched it?
> Okay, compare, compare, compare.. ah, we already know the port number,
> no need to fetch it again, so don't wait, keep going... compare,
> compare..."
>
> There are also techniques that "compile" access-control lists in various
> ways, using more space but reducing the average number of comparisons
> that need to be made. For example, if the rules list a bunch of
> addresses that are permitted access, then you can pre-scan the rules
> and find the largest and smallest address that are permitted, and then
> you can start the whole series of checks by seeing if the input is
> smaller than the smallest or bigger than the largest, and if so reject
> it immediately -- that's one to four comparisons done that saves examining
> all S rules for packets that cannot possibly be accepted.
>
> So... the question isn't realistic, firewalls don't really work that
> way, but don't worry about it, because all you need to do is give them
> a simple formula that fits with their assumptions. (The answer
> is really simple, by the way...)