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

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.

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.)

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...)

described, S would be 144, and you would

are given, you don't -- you are