A Framework for Understanding Vulnerabilities in Firewalls Using a Dataflow 	                  Model of Firewall Internals 1

                 Mike Frantzen                                     Florian Kerschbaum
        frantzen@cerias.purdue.edu                      kerschf@cs.purdue.edu
               Purdue University                     Center for Education and Research in
          West Lafayette, IN 47907            Information Assurance and Security           
                                                                                   (CERIAS)
                                                                              Purdue University
                                                                        West Lafayette, IN 47907

               E. Eugene Schultz                                     Sonia Fahmy
            ees@cerias.purdue.edu                        fahmy@cs.purdue.edu
     Center for Education and Research in    Department of Computer Science             
    Information Assurance and Security               Purdue University
                    (CERIAS)                                   West Lafayette, IN 47907
              Purdue University
         West Lafayette, IN 47907

Abstract

Vulnerabilities in vendor as well as freeware implementations of firewalls continue to emerge at a rapid pace. Each vulnerability superficially appears to be the result of something such as a coding flaw in one case, or a configuration weakness in another. Given the large number of firewall vulnerabilities that have surfaced in recent years, it is important to develop a comprehensive framework for understanding both what firewalls actually do when they receive incoming traffic and what can go wrong when they process this traffic. An intuitive starting point is to create a firewall dataflow model composed of discrete processing stages that reflect the processing characteristics of a given firewall. These stages do not necessarily all occur in all firewalls, nor do they always conform to the sequential order indicated in this paper. This paper also provides a more complete view of what happens inside a firewall, other than handling the filtering and possibly other rules that the administrator may have established. Complex interactions that influence the security that a firewall delivers frequently occur. Firewall administrators too often blindly believe that filtering rules solely decide the fate of any given packet. Distinguishing between the surface functionality (i.e., functionality related to packet filtering) and the deeper, dataflow-related functionality of firewalls provides a framework for understanding vulnerabilities that have surfaced in firewalls. 

Introduction

Postings of newsgroups such as bugtraq and Firewalls Digest frequently announce newly discovered vulnerabilities in firewall products (including firewall appliances) as well as public domain firewall implementations. With each description of each vulnerability generally comes a solution in the form of a patch that corrects one or more coding flaws or a recommended change in configuration. Those who read each latest posting justifiably turn their attention to issues such as whether or not to implement the solution(s) and, if so, how soon. An issue of concern is that few people pay attention to the types of vulnerabilities that emerge and the patterns of weaknesses that may be present within each implementation. These weaknesses may be more serious than individual bugs in underlying programs or faulty configuration---they may be indicative of underlying deficiencies in firewall design. 

Given the sheer number of vulnerabilities that have surfaced, it is important to develop a comprehensive framework for understanding at a deeper level what firewalls actually do when they receive incoming traffic and what can go wrong in terms of security-related weaknesses. An intuitive starting point is to create a firewall dataflow model composed of discrete components that can be reorganized into different orders or that can be removed individually in certain cases to more accurately reflect the processing characteristics of any specific firewall. From a functional perspective, what actually occurs inside a firewall other than filtering according to rules that the administrator has installed? 

Firewall administrators often naively believe that filtering rules exclusively determine the fate of a packet. For example, they may believe that an incoming packet bound for TCP port 80 of an internal host will or will not be passed through the firewall only if a firewall ruleset allows incoming traffic destined for this port, provided of course that the IP source address is an allowable address. In reality, much more influences not only what passes through a firewall, but also how it passes through. Complex interactions that influence the security of the system often occur. 

Figure 1 below shows the path a packet takes in an IP firewall between the receipt by the bastion and the release back out onto the network. (We assume that the reader at least has experience configuring a firewall and some minimal background in IP networking.) The following text describes each component in the dataflow model as the firewall sequentially processes each packet.

                                                      Packet Flow

 -------------------------------------           |
| Packet ingress                          |          |
 -------------------------------------           |
| Link Layer Filtering                |         \v/
 -------------------------------------
| NAT/PAT (Header Rewrite)   |
 -------------------------------------
| Dynamic Ruleset (State)          | >------------>------------->--------
 -------------------------------------                                                     |
| Packet Sanity Checks               |  * Packet may be dropped         |  Bypass on
 -------------------------------------                                                     |   match
| IP & Port Filtering                   |  * Packet may be dropped          |
 -------------------------------------                                                     |
| Packet reassembly                    | <------------<-------------<--------
 -------------------------------------
| Application level                      |  * Stream may be dropped
 -------------------------------------
| Routing Decision                      |
 ----------------------------------------------
| NAT/PAT (header rewrite)     |           |
 -------------------------------------            |
| Dynamic Ruleset (State)          |           |
 -------------------------------------            |     Optional outbound filtering
| Packet Sanity Checks              |           |
 -------------------------------------            |
| IP & Port filtering                    |            |
 ----------------------------------------------
| Packet Egress                          |
 -------------------------------------

Figure 1: Packet Traversal through a Firewall.

Link Layer Filtering

Upon the firewall’s receipt of the packet, there may be a few levels of processing by the operating system, or, alternatively, the packet may be diverted directly to the firewall code. If programmed to do so, the firewall will next perform Link Layer Filtering (a rare commodity in modern firewalls). A firewall with such capabilities can lock a particular IP address to a specific hardware address, a potentially very advantageous feature given the constant threat of spoofed addresses. This kind of firewall could communicate with a DHCP server to assure that the hardware address corresponds to its given IP address, or could even enable the firewall to apply specific filters to individual VLANs.

Dynamic Ruleset

The next stage in handling incoming packets is applying the Dynamic Ruleset, the
core of stateful firewalls. The dynamic ruleset (aka: the state table) serves to associate each packet with its corresponding connection stream [1]. The state table is in many respects analogous to a cache. If a firewall passes a packet through, it generates an entry in the state table. When future packets in the stream arrive and are matched by the entry in the table, they can bypass all subsequent filtering rules. The entry also serves to allow any programmed responses (e.g., error notifications) to be sent back to the originating host through the firewall. To serve these two ends, the state table typically incorporates two assumptions about networking: 

•	If there is one packet, there will be more,

	and 

•	If there is one packet, responses will be sent back. 

A firewall generally implements the state table as a hash table. Hash tables are in many respects a “two-edged sword.” Practical considerations govern that they cannot realistically be dynamically grown, but, on the other hand, they are extremely fast. The fixed size table is thus a prime candidate for a resource starvation attack. 

Many of the caveats of hash tables can be delayed with the use of collision chains. Every entry in the hash table points to a linked list of table entries that all hash to that location. Unless all available memory is exhausted, the table cannot be physically filled by an attacker. Like straight hash tables, collision chains also have their perils. Imagine a few thousand connections all hashing into the same chain. Every new packet that is received that hashes to the same chain must be compared against the entire chain before the firewall knows the packet is not a member of any state table entry. This is actually a very costly operation, exacerbated by the significant quantity of page faults. (Further elaboration is far beyond the scope of this paper.) The authors have seen a total denial of service (DoS) attack against extremely high performance hardware. The list grew to 5,000 entries during an attack of 100 packets per second. The symptoms can be further delayed by the use of trees instead of linked lists, but the worst case scenario remain the same.

The firewall can take one of several actions when the table fills: 

•	The easiest action is to block the newest entries, resulting trivially in DoS. This is thus not a very acceptable solution.

•	The firewall can either delete the least recently used (LRU) entry in the hope that it is a dead connection or that it is no longer needed. Because an attacker’s packets will be the most recently used, this alternative is little better than the previous one.

•	The firewall can do a random early detection (RED) that randomly selects and drops packets when the table starts to get full. This, however, is more of a TCP congestion indication mechanism than anything else. More relevant to the subject of managing filled tables, therefore, is a discussion on SYN flooding with caveats about forced grooming of network tables which appears later in this paper. Reference [2] also contains a particularly enlightening paper on this and related subjects. 

•	The firewall can time entries out (especially for UDP traffic, which is not connection oriented in the first place). Again, this alternative may be able to prevent a successful DoS attack. 

Finally, the firewall MUST remove entries upon receipt of a protocol shutdown (TCP RST, an ICMP packet). As previously stated, if a packet matches an entry in the state table, a firewall may skip further processing of the filtering rules. However, bypassing rules can result in extremely dire consequences, particularly if the firewall is configured to drop packets with IP options [3] or specific TCP options [4]. If the state table precedes these checks, however, a packet containing such options may be allowed, even though the firewall filtering rules have explicitly denied such traffic. The trend for today’s commercial firewalls is in fact to track minimal state, typically resulting in passing through more than the legitimate traffic defined by filtering rules.

The other prime use for the Dynamic Ruleset is to track auxiliary connections. Several protocols that open multiple connections have gained widespread acceptance. Protocols such as FTP and h.323 spawn multiple streams during their operation. The state table is a convenient location to track and associate the streams that belong together. 

Legality Checks

In still another stage of firewall dataflow packets undergo Legality Checks. This stage may actually occur before or after the previous stage, depending on the particular firewall in question. The purpose is to verify that the packet that has been received is not blatantly illegal, and will not subvert or fool the filtering stage that follows. A plethora of other checks can also be performed during this stage. Common checks here include anti-spoofing, reserved IP address checks, IP/TCP options checks, checks for short IP packets, checks for UDP packets in which UDP length does not correspond to the IP length, checks for obvious fragment attacks, and a determination whether a port scan accumulator is being used. In an ideal world, these checks would occur before the Dynamic Ruleset. But since this could substantially escalate the processing per packet, the trend in today’s firewalls is to perform only the bulk of the legality checks if the packet falls through the Dynamic Ruleset. Here we thus have another vulnerability in many firewalls; the firewall may not perform the entire range of legality checks, allowing unauthorized packets to pass through.

IP and Port Filtering

The fourth stage in packet dataflow is the IP and Port Filtering process, the stage with which firewall administrators are typically most familiar. This stage can be conceptualized in terms of the oddly shaped pegs that fit only in a certain hole. The peg (packet) goes down the procession of holes in the board. If it fits through the hole (matches a rule), then it is allowed through. If the peg (packet) does not fit in any of the holes, the peg (packet) is discarded. A stateful firewall will “remember” that the circular peg fits through the circular hole. Next time it “sees” a circular peg, it knows to bypass everything, shoving it through the right hole. Likewise, the firewall can add a Dynamic Rule to track the connection of the circular peg. But, if the packet does not match any of the rules or explicitly matches a rule to drop it, the firewall may take several actions:
The strictest course of action is to discard the packet [6]. But a “polite” firewall will tell the connecting host that the connection has been denied via a TCP RST packet, or an ICMP packet.

Note that authentication handling is often also initiated during the IP and Port Filtering stage, but this will be covered later in this paper. 

Header Rewrite

The next stage of packet traversal in a firewall is Header Rewrite. The purpose of this stage is directly related to network functionality. It includes features such as Network Address Translation (NAT) and Port Address Translation (PAT), which have been dubbed “IP Masquerading” by the Linux community. Address Translation is implemented in a table structure similar to the state tables mentioned above. The security concerns are thus identical to those previously discussed in this paper. 

Two other functions common to this component are TTL Preservation and TCP Sequence rewriting. During the life of a packet, every router it goes through decrements the TTL (time to live) of a packet. When the TTL reaches zero, the packet is assumed to be unroutable and will thus be destroyed. TTL Preservation makes the firewall appear invisible to conventional tracerouting and is thus actually a primitive but less than obvious form of firewalling. 

The TCP sequence numbers are the key to TCP’s reliability. They allow the receiving host to acknowledge the exact octets it has received. If attackers can predict the initial sequence number (ISN), they can spoof an entire TCP session [5]. Many operating systems (including Windows NT, until Service Packs 3 and 6) used a predictable ISN. TCP Sequence rewriting generates a pseudo random ISN and adds it to the original sequence numbers of the TCP stream. In implementation, Header Rewrite is closely coupled to the Dynamic Ruleset. Most of the features of Header Rewrite require a table lookup of their own (ie, for NAT/PAT and to keep consistent sequence numbers). The table is indexed by the connection stream. The Dynamic Ruleset has already performed the table lookup for all but the initial packet. A bulk of the Header Rewrite can be logically extended to the packet processing done by the Dynamic Ruleset at the cost of multiple table entries.

Packet Reassembly

Historically, from a security perspective one of the most vulnerable components of firewalls has been the Packet Reassembly. Reassembly can be done before any of the previous filtering at the heightened risk of resource attacks. Alternatively, it can be performed after the bulk of the filtering, but at the cost of a more complex filter processing in connection with filtering fragmented packets. Two possible strategies for dealing with IP fragment reassembly are:

•	The first and easiest method is not to do it. A majority of the non-proxy capable firewalls filter the first fragment (which contains the entire TCP or UDP protocol header—short packets should have been previously dropped) [7] and allow all other fragments to pass. Since the first fragment can be blocked, the partial packets will be buffered at the endpoint and will eventually be expired [8]. Some firewalls require the first fragment before allowing any of the following fragments [9].

•	The second, better but more expensive method is to do total fragment reassembly. The firewall buffers all the fragments until the packet has been totally reassembled, only then will it pass the packet farther down the dataflow. If total reassembly is performed, the firewall will pay with speed and memory consumption. If reassembly is not done, internal (or external) hosts may be vulnerable to the all common fragmentation attacks. The fragments being reassembled are also referenced in a table structure similar to the primary state table. The security concerns of the table are identical to those discussed for the state table. We assume in this instance that a resource attack against the firewall is generally preferable to an attack against the hosts it protects. After all, the sole purpose of the firewall is to protect other hosts, not to “protect only if it is convenient.”

In a firewall that performs TCP application layer analysis, the firewall must perform TCP sequence reassembly. If a TCP packet is lost or delayed in route, the firewall must not process the following packets at the application layer until all the previous packets before have been received. This is a very tedious process; the firewall must track sequence numbers and windows. Because of this complexity, proxying firewalls often pass the packets through the operating system (OS) stack to handle IP fragment reassembly and TCP sequencing. There are severe downsides to passing the stream through the operating system (OS). If there are bugs in the OS stack, for example, there will be bugs in the firewall that are beyond the control of firewall developers. If the OS’s stack changes between patch levels, then a patch for the OS may cause the firewall to break.

Application Layer

After reassembly, packets are passed to the Application Layer filtering for analysis. The application level analysis must take place on whole data. For example, one of the fixes for the recent PASV2 exploit [10] was to drop packets from the client that resembled a reply that should come only from the server. The reasoning behind this fix was that the server will echo the reply back. So the firewall drops packets that match “227 (a,b,c,d,e,f)” from the client. But TCP is a strictly ordered protocol, not a temporally ordered protocol. Packets physically arriving in one order may be reordered by the TCP stack.

For the sake of brevity (at the loss of some degree of terminology precision) we refer to filtering at the application layer as “proxying.” Generally, proxies operate somewhere in a spectrum between two extremes: 

•	At one end is full protocol decomposition. The proxy interprets every packet and guesses at the intentions of the client or server. If the action is not legal according to the protocol or if the action is disallowed by the security policy, the packet can be dropped or the state table entry can be removed (effectively dropping the TCP stream). After approving the intentions of the packet, the proxy reconstructs a packet according to the interpreted intentions of the original. In theory, nothing will go through the proxy unchanged unless it is in exactly the format that the proxy would use to write it. In addition to sanitizing packets, the proxy also changes the current internal state of the stream, depending on the packet and the response back to it. The proxy’s operation is commonly depicted as speaking through two lawyers. If you need to converse with a business rival, you can speak to your lawyer. Your lawyer sanitizes and obfuscates what you say and tells it to your rival’s lawyer. Your rival’s lawyer attempts to guess at the original meaning and passes the message on to your rival. If the lawyers are doing their jobs correctly, no business secrets can leak across and you cannot insult your rival. Commercial firewalls near this end of the spectrum include Raptor, Gauntlet and the free Firewall Toolkit [11].

•	At the other end of the spectrum, the proxy may operate in “plug mode.” A plug mode proxy essentially forwards a packet from the incoming queue to the outgoing queue. If anything, it operates a minimal state machine. Proxies near this end of the spectrum perform duties such as pattern matching or primitive content filtering. Commercial firewalls with filtering near this end of the spectrum comprise the bulk of the product offerings and include Firewall-1 and PIX.

Deriving a generic model of Application Layer filtering is futile. Reasons include the many disparities between various protocol implementations and the complex variety of firewalls on the market. We will thus instead present a case study of a generic FTP proxy. We will first assume that the TCP stream is being reassembled before being passed to the proxy and that the proxy is buffering full lines before passing it to the analysis logic. We have chosen FTP because it is a conventional command and response protocol and also because it has the unusual property of using auxiliary connections [12].

A proxy towards the stricter end of the spectrum will drop all input from the client until the server has sent an initial banner. After the server’s banner, the proxy will not accept anything until the client sends the username. After receiving the username, the proxy blocks everything until the server returns the response for an accepted username. Likewise, the proxy blocks input until the client send the password and the server replies that the authentication was successful. After authentication, the proxy allows the bulk of the FTP commands specified in the RFCs. The proxy sanitizes all commands and responses sent according to the protocol specification. Such sanitation should prevent successful exploits against the server or client.

In contrast, a proxy towards the more primitive end of the spectrum will not do any of the above. It will watch and rewrite one or perhaps two FTP commands. To transfer files, FTP sends a command via the control stream to set up another TCP connection called the “data connection.” If a FTP client wishes to transfer a file, it either notifies the server to connect to a port on the client or asks the server to allocate a port to which the client can connect. If the server is to connect to the client for the auxiliary connection, the client sends the PORT command. If the client is to connect to the server, it sends the PASV (passive) command. Since NAT/PAT is likely to occur at the firewall, the proxy must rewrite the IP address and ports to avoid leakage of the internal network topography and for the data connection to go to the correct host [13]. The proxy must also allocate an entry in the Dynamic Ruleset to allow the connection to pass through. It adds a NAT/PAT entry to make the auxiliary connection go to and from the proper IPs. A high-performance firewall translates and passes the data connection directly through, rather than redirecting the data back down to the proxy level.

Upon receipt of the PORT or PASV commands, a proxy at the stricter end of the spectrum also takes similar action. It also adds an entry to the Dynamic Ruleset to pass the data connection through the firewall. But unlike the lax implementation, it redirects the data connection back into the proxy code before forwarding. The proxy can then restrict the data to a uni-directional stream if the Dynamic Ruleset supports only bi-directional streams. It can restrict non-binary transfers to 7-bit ASCII; it can also buffer or redirect the transfer to scan it for viruses, worms, and other types of malicious code.

Routing Decision

By now, the packet is almost out of the system and can be handed back to the OS for a Routing Decision. This is a simple decision concerning which interface will be used to shunt the packet out. Conventionally the basis has been the destination IP address. Modern firewalls provide the choice of routing a packet by the destination port and the ability to redirect packets to adjacent caching servers. An often-overlooked feature is the ability to make a copy of a packet, then send the copy out to an isolated network for intrusion detection and split logging.

Outbound Filtering

The choice whether or not to now perform outbound filtering presents a dilemma. At this stage of dataflow through a firewall a given packet can either now leave the system for the network or can go through another set of filters. The packet could, after all, have been changed by NAT or other components. Alternatively, the packet may have been generated by the firewall host. It is thus prudent from a security viewpoint to run the packet through the filter rules again to assure that the firewall has not generated an illegal packet. Once again, however, many of today’s firewalls are not programmed to perform this additional check. 

Packet Release

Finally, the packet will leave the firewall. It is now well on its way to meeting the needs of a user or application as its time to live rapidly approaches zero.

Conclusion

Firewalls, like any other host, are in the most fundamental sense, machines that process data.  The model presented in this paper depicts dataflow in terms of a sequence of stages that start with a receipt of a packet. Link Layer Filtering, Use of a Dynamic Ruleset, Packet Legality Checking, IP and Port Filtering, NAT/PAT, Packet Reassembly, Application Level Analysis, a Routing Decision, Use of a Dynamic Ruleset (once again), Packet Sanity Checks, IP and Port Filtering, and then the release of the packet comprise the complete set of stages.  At any given stage a firewall may or may not handle a packet satisfactorily from a security perspective.  Possible weaknesses include anything from failure to perform a particular stage of processing altogether to performing it incompletely to performing it inappropriately (or, more often, inappropriately under certain conditions, such as during traffic overload conditions).  Understanding the underlying dataflow stages provides a conceptual framework for identifying and categorizing vulnerabilities commonly found in firewalls, something that will facilitate making strategic improvements in firewall design and implementaiton.  

The framework presented in this is by no means intended to be completely comprehensive, however.  The most notable limitation is that it depicts only what happens to packets on the basis of stages of input processing.  It does not consider specific security needs and characteristics of applications residing with networks protected by firewalls.  This dataflow framework also does not consider virtual private network encapsulation or decapsulation.  Our understanding is that there is not a common placement for such functions. The authors must also caution the reader that the constructs presented in this paper apply generically to firewalls. Some constructs do not apply to specific firewall implementations. That is the penalty we have paid for trying to describe radically different implementations such as Firewall-1, Gauntlet, PIX and IP Filter. 

References

[1] Newman, D. “Benchmarking Terminology for Firewall Performance.”  RFC 2647, August 1999.  

[2] Sally, F. and  Jacobson V. “Random Early Detection Gateways for Congestion Avoidance.” IEEE/ACM Transactions on Networking, Vol. 1(4). pp. 397-413. August 1993.

[3] Postel, J. “Internet Protocol.”  RFC 791, September 1981.

[4] Postel, J. “Transmission Control Protocol.”  RFC 793. September 1981.

[5] Bellovin, S. M. “Security Problems in the TCP/IP Protocol Suite.”  Computer Communication Review, Vol. 19 No. 2. pp. 32-48. April 1989. 

[6] Chapman, B. D. “Network (In)Security Through IP Packet Filtering.” Proceedings of the Third UNIX Security Symposium. September 1992 

[7] Ziemba, G., Reed D. and Traina P. “Security Considerations for IP Fragment Filtering.” RFC 1858, October 1995.

[8] Corbridge, B., Henig, R. and Slater, C. “Packet Filtering in an IP Router.”  http://www.raptor.com/lib/./cslater.ps.

[9] Mogul, J. C. “Simple and Flexible Datagram Access Controls for UNIX-based Gateways.” Proceedings of the USENIX Summer 1989 Conference,  pp. 203-221. 1989

[10] Postel, J., Reynolds, J. “File Transfer Protocol”. RFC 959. October 1985. [11] Ranum, M. J. and Avolio, F. M. “A Toolkit and Methods for Internet Firewalls.”  Proceedings of the USENIX Summer 1994 Conference,  pp.37-44. 1994.

[12] ] Postel, J., Reynolds, J. “File Transfer Protocol.”  RFC 959. October 1985.  [13] Treese, Winfield G. and Alec Wolman. “X Through the Firewall, and Other Application Relays.”  Proceedings of the USENIX Summer 1993 Conference, pp. 87-99. 1993

Footnotes

1 This work was supported by sponsors of the Center for Education and Research in Information Assurance and Security (CERIAS) at Purdue University.

2 In this PASV exploit some firewalls will open up any TCP port to FTP servers behind those firewalls. The FTP server can be tricked into echoing “227 PASV” commands outwards through the firewall.  Interestingly, running the PASV exploit through Dug Song’s fragrouter will still affect many ‘fixed’ firewalls