GATE IT 2007 | Question: 18

Question

A firewall is to be configured to allow hosts in a private network to freely open TCP connections and send packets on open connections. However, it will only allow external hosts to send packets on existing open TCP connections or connections that are being opened (by internal hosts) but not allow them to open TCP connections to hosts in the private network. To achieve this the minimum capability of the firewall should be that of

• A. A combinational circuit
• B. A finite automaton
• C. A pushdown automaton with one stack
• D. A pushdown automaton with two stacks

Comments

It is not PDA+1 but PDA with one/two stacks.

 

makes sense?

Answer 1

• A. A combinational circuit$\Rightarrow$ Not possible, because we need memory in Firewall, Combinational ckt has none.
   
• B. A finite automaton$\Rightarrow$ We need infinite memory, there is no upper limit on Number of TCP ckt so Not this.
   
• C. A pushdown automaton with one stack$\Rightarrow$ Stack is infinite. Suppose we have $2$ connections, we have pushed details of those on stack we can not access the details of connection which was pushed first, without popping it off. So, Big NO.
   
• D. A pushdown automaton with two stacks$\Rightarrow$ This is TM. It can do everything our normal computer can do so Yes. A firewall can be created out of TM.

Correct Answer: $D$

Comments

I think all the explanations are correct except the Finite Automation one.

First of all, we don't need infinite memory here, because there could be only finite no. of TCP connections opened by a finite no. of internal hosts at a time.

A FA also does not have any memory, but it can automate a pattern, but there is no pattern to the no. of TCP connections and the internal hosts which will open them. So a FA cannot work here.

---

can't we just block syn packets from outside no need for memory?

---

Finite automata have finite amount of memory encoded in its states.

---

If somebody is thinking, why is @ravi_ssj4 ji  saying --> number of TCP connection will be finite then answer is 

https://stackoverflow.com/questions/2332741/what-is-the-theoretical-maximum-number-of-open-tcp-connections-that-a-modern-lin

OR 

in simple terms our main memory is finite. 

---

why option C is not correct...we need to track of only the connection which is created by the private network.raise me if I'm wrong.

---

Someone please answer this:

can't we just block syn packets from outside no need for memory?

---

What if external host tries to send packets on not opened TCP connections, We need to block those packets as well.

---

For all outgoing packets, if the ACK bit of TCP segment is set to 0(which represents the first SYN) segment, these types of packets must be allowed to leave the network. For all packets coming from outside the network into the private network, all packets which have ACK bit set to 0 must be blocked(means ALL SYN packets from outside are blocked) but if ACK bit is set to 1, this means we are allowing our internal hosts to make TCP connections to the outside world and this is allowed.

---

An attacker could send messages on a TCP connection that has not been established, but has the SYN bit set to 0. The question says that the firewall

"will only allow external hosts to send packets on existing open TCP connections.... but not allow them to open TCP connections to hosts in the private network".

Rejecting incoming packets with the SYN bit set will not help us achieve "will only allow external hosts to send packets on existing open TCP connections", but will allow us to achieve the second part of the question.

---

isnt TM= FA + 2 Stacks = PDA + 1 stack?

and TM and all other TM with 1 or more stacks are equally powerful, so isnt option C and D same?

---

@ Rishabh Gupta 2

If we block syn packet from outside wouldn't it also block SYN + ACK packet required during 3 way handshake in connection establishment phase ?

---

@Akash Kanase You arguments make sense, but since the question mentions the word minimum, I think option $(C)$ could be correct as well if we assume that the TCP connections are accessed in the opposite order in which they are opened.

Comments?

---

Markzuck

 by “pda with one stack” we dont mean “pda with one additional stack” we mean “pda consisting of one stack”

Answer 2

It should be D as it is equal to turing machine and since we need to keep track of all the open connections as they should only be connected with outside world(one to one matching) a PDA won't suffice..

Comments

Answer should be (D)

It can be done by finite state machine only if it is allowed only one host to open connection at a time, becuase when the replying packet will come back, then NAT (network address translator) very much knowing who has asked for the packet.. but since more than one host can open connection simultaneously, so memory requirement may not be finite because we don't know how many host in the private network has asked for the network.. So it does require some memory capability.. And as per the options we have to use stack as the memory.. We will be requring two stack, because when a external packets coems as a reply then firewall pop each of the requiesting packet to see, who has ordred the packet and keep on pushing on the another stack, and once it is found, he forwards it to the requesting host.. else if not found the packet is discarded..

Answer 3

pushdown automata with two stacks which is the Turing machine.
Turing machine can do everything as the normal computer can do, so firewall can be created by the TM.

Answer 4

COMMENT BELOW IF YOU HAVE ANY DOUBT