Network Security Via Reverse Engineering of TCP Code:
`Vulnerability Analysis and Proposed Solutions
`
`Biswaroop Guha and Biswanath Mukherjee
`Department of Computer Science
`University of California
`Davis, CA  , U.S.A.
`
`fguha, mukherjeg@cs.ucdavis.edu
`Tel: + - -f- , -g
`Fax: + - --
`Corresponding Author: Biswanath Mukherjee
`
`November , 
`
`Abstract
`
`The Transmission Control ProtocolInternet Protocol TCPIP   suite is a very widely
`used technique that is employed to interconnect computing facilities in modern network envi-
`ronments. However, there exist several security vulnerabilities in the TCP specication and
`additional weaknesses in a number of widely-available implementations of TCP. These vulner-
`abilities may enable an intruder to attack" TCP-based systems, enabling himher to hijack"
`a TCP connection or cause denial of service to legitimate users. We analyze TCP code via a
`reverse engineering" technique called slicing" to identify several of these vulnerabilities, espe-
`cially those that are related to the TCP state-transition diagram. We discuss many of the aws
`present in the TCP implementation of many widely used operating systems, such as SUNOS
`. . , SVR, and ULTRIX . . We describe the corresponding TCP attack signatures" in-
`cluding the well-known  Christmas Day Mitnick Attack and provide recommendations to
`improve the security state of a TCP-based system, e.g., incorporation of a timer escape route"
`from every TCP state.
`
`Keywords and Phrases: Network Security, TCP, IP, Reverse Engineering, Slicing, Vulnerability
`
`Analysis, State Transitions, Timer Escape Route.
`
` This work has been supported by the Advanced Research Projects Agency ARPA under Contract No.
`DODDABT - -C-. A short, summarized version of this paper will appear in the Proceedings of the IEEE
`Infocom ’  Conference.
`
`
`
`CAVIUM-1071
`Cavium, Inc. v. Alacritech, Inc.
`Page 001
`
`

`

`
`
`Introduction
`
`Internetworking is an approach that allows dissimilar computers on dissimilar networks to com-
`
`municate with one another in a seamless fashion by hiding the details of the underlying network
`
`hardware. The most widely used form of internetworking is provided by the Transmission Control
`
`ProtocolInternet Protocol TCPIP suite.
`
`There are some inherent security problems in the TCPIP suite  which makes the situation
`
`conducive to intruders. TCP sequence number prediction, IP address spoong  , misuse of IP’s
`
`source routing principle, use of Internet Control Message Protocol ICMP messages for denial of
`
`service, etc. are some methods to exploit the network’s vulnerabilities. Considering the fact that most
`
`important application programs such as Simple Mail Transfer Protocol SMTP, telnet, r-commands
`
`rlogin, rsh, etc, File Transfer Protocol FTP, etc. have TCP as their transport layer, security aws
`
`in TCP can prove to be very hazardous for the network.
`
`The objectives of this paper are to identify and analyze the vulnerabilities of TCPIP and to
`
`develop security enhancements to overcome these aws. Our work is based on analyzing the state-
`
`transition diagram of TCP and determining the security relevance of some of the improperly-dened"
`
`transitions between dierent states in the state-transition diagram of many widely used TCP code im-
`
`plementations. Also, we determine the importance of timers in dierent states and security problems
`
`associated with them if a state does not have the necessary timer-backup or escape route.
`
`We analyze the TCP state-transition diagram using a reverse engineering" technique called slic-
`
`ing  . Program slicing is an abstraction mechanism in which code that might inuence the value
`
`of a given variable at a location is extracted from the full source code of the program. We employ
`
`slicing to lter out the relevant state-transition information from the TCP source code. In partic-
`
`ular, using the slicing techniques discussed later in the paper, a  line C le implementation of
`
`state-transitions in TCP along with all the header le denitions has been reduced to a very small
`
`and manageable size of approximately  lines of sliced code, which contains only the relevant
`
`state-transition information. This process aids in abandoning unnecessary information and simpli-
`
`fying the code. In this process, we have been able to locate extraneous state-transitions present in
`
`some implementations of TCP. In other words, using the method of slicing, we have determined the
`
`
`
`CAVIUM-1071
`Cavium, Inc. v. Alacritech, Inc.
`Page 002
`
`

`

`presence of several spurious state-transitions in a number of TCP implementations such as SUNOS
`
`. . , SVR, and ULTRIX . ; these transitions are not dened in the TCP protocol specication.
`
`Using our approach, we can identify various sequences of packets in the network which can be po-
`
`tentially hazardous to the security state of the system. These attack signatures" represent TCP
`
`vulnerabilities, which can possibly be exploited by an intruder. Any network-snier" will be able to
`
`determine these signatures and inform the system’s security administrator of the intrusion. We also
`
`provide several recommendations to enhance the security state of a TCP-based system.
`
`The paper is organized as follows. Section  provides an overview of TCP with special emphasis
`
`on its state-transition diagram. Section discusses dierent scenarios having security relevance to
`
`the TCPIP suite. Section  discusses our slicing approach to identify extraneous state-transitions
`
`in TCP’s state-transition diagram. Section  provides information on our analytic approach, and
`
`the results we have obtained after employing slicing techniques on the TCP source code. Section 
`
`discusses the attack signatures", the test-bed which we have developed to test the vulnerabilities of
`
`TCP code in various implementations, and various recommendations to enhance the security state
`
`of a system. Section  concludes the paper including future research directions.
`
` Basics of TCPIP
`
`. Networking with TCPIP
`
`Network protocols employ a structured and layered approach, with each layer performing a separate
`
`function. This approach helps in developing individual layers without modifying other adjacent
`
`layers. Networking using the TCPIP suite can be viewed as a combination of four layers as shown
`
`in Fig. . Note the correspondence between these layers and those of the International Standard
`
`Organization ISO seven-layer model: Layers and  of the ISO model are combined into the lowest
`
`layer of the model in Fig. , while ISO Layers - are merged into the top-most layer in Fig. .
`
`The responsibilities of the dierent layers of the model in Fig. are well-dened.
`
` The lowest layer, the data-link layer,contains the network interface layer, connecting the
`
`system with the physical media. It includes device drivers in the operating system and network
`
`
`
`CAVIUM-1071
`Cavium, Inc. v. Alacritech, Inc.
`Page 003
`
`

`

`interface cards connected to the cable. Data-link layers of dierent systems exchange data
`
`packets.
`
` The next layer is the internet layer or the network layer. It assists with the movement rout-
`
`ing of packets in the network. Internet Protocol IP provides a best-eort, connectionless,
`
`and unreliable packet delivery service for the higher layer.
`
` User processes interact with the network layer through the transport layer. The Trans-
`
`mission Control Protocol TCP is the most common transport layer used in modern
`
`networking environments. TCP provides reliable data transfer between dierent application
`
`processes over the network. TCP provides ow control and congestion control as well.
`
` The Application layer handles the details of a particular application. This layer interacts
`
`with the user, gets data from the user, and sends the buered data to the transport layer. At
`
`the same time, this layer gets data from transport layer and conveys it to the corresponding
`
`application. The application layer shields the user from the details of the transport layer.
`
`When data is sent from the application layer down to the machine hardware, it moves through
`
`the dierent layers and each lower layer adds a header to the data it receives from the previous upper
`
`layer. This process of encapsulation enables a layer to easily interpret and parse the data that
`
`it receives from a lower layer and it has to pass on to the upper layer. Fig.    illustrates the
`
`encapsulation process that occurs in the TCPIP suite, assuming an Ethernet physical network.
`
`. Transport Layer
`
`Among all of the transport layers, TCP is the most popular. Below, we examine the details of the
`
`header format of TCP along with the TCP state-transition diagram and TCP timers.
`
`.. TCP Header
`
`The size of the TCP header is  bytes, without counting its options, as we observe in Fig.  .
`
`Each TCP segment contains the source and destination port number to identify the sending and
`
`receiving application programs, respectively. The sequence number is essential to maintain the bytes
`
`
`
`CAVIUM-1071
`Cavium, Inc. v. Alacritech, Inc.
`Page 004
`
`

`

`of data from the sender to the receiver in proper order. By communicating the sequence number
`
`and the corresponding acknowledgment number, the sender and the receiver can determine lost or
`
`retransmitted data in the connection. There are six ag bits in the TCP header, namely URG, ACK,
`
`PSH, RST, SYN and FIN. At any given time, one or more of these ag bits can be set.
`
`TCP provides ow control by advertising the window size. The checksum covers TCP header and
`
`TCP data and assists in determining any error in transmission of TCP header or data. TCP’s urgent
`
`mode is a method for the sender to transmit emergencyurgent data. The urgent pointer is valid
`
`only if the URG ag is set in the header. It helps to locate the sequence number of the last byte of
`
`urgent data. There is an optional options eld as well, taking care of vendor specic information.
`
`.. TCP State-Transition Diagram
`
`Initiation, establishment, and termination of a connection is governed by the TCP state-transition
`
`diagram, which consists of well-dened states and transition arcs between these states see Fig. 
`
`.
`
`.. TCP Timers
`
`The TCP state-transition diagram is very closely associated with timers. There are various timers
`
`associated with connection establishment or termination, ow control, and retransmission of data.
`
` A connection-establishment timer is set when the SYN packet is sent during the connection-
`
`establishment phase. If a response is not received within  seconds in most TCP implemen-
`
`tations, the connection establishment is aborted.
`
` A FIN WAIT  timer is set to minutes when a connection moves from the FIN WAIT
`
`state to the FIN WAIT  state . If the connection does not receive a TCP packet with the
`
`FIN bit set within the stipulated time, the timer expires and is set to  seconds. If no FIN
`
`packet arrives within this time, the connection is dropped.
`
` These are some of the states that TCP uses to successfully terminate a connection.
`
`
`
`CAVIUM-1071
`Cavium, Inc. v. Alacritech, Inc.
`Page 005
`
`

`

` There is a TIME WAIT timer, often called a  MSL Maximum Segment Lifetime timer. It
`
`is set when a connection enters the TIME WAIT state. When the timer expires, the kernel
`
`data-blocks related to that particular connection are deleted, and the connection is terminated.
`
` A keepalive timer can be set which periodically checks whether the other end of the connection
`
`is still active.
`
`If the SO KEEPALIVE socket option is set, and if the TCP state is either
`
`ESTABLISHED or CLOSE WAIT, and the connection is idle, then probes are sent to the
`
`other end of the connection once every two hours. If the other end does not respond to a xed
`
`number of these probes, the connection is terminated.
`
` Additional TCP timers such as persist timer, delayed ACK timer, and retransmission timer are
`
`not relevant for our purposes here and, hence, are not discussed. Interested readers may refer
`
`to    for more information on these timers.
`
` Example Attack Scenarios
`
` .
`
`IP Spoong
`
` . . Instances
`
`The concept of attacks on TCPIP such as TCP sequence-number guessing to do IP-spoong was
`
`rst brought to light by Morris  . The Computer Emergency Response Team CERT Coordination
`
`Center received reports of attacks in which intruders created packets with spoofed source IP addresses
`
` . These attacks exploit applications that use authentication based on IP addresses.
`
`Intruder
`
`activity in spoong IP addresses can lead to unauthorized remote root access to systems behind a
`
`ltering-router rewall  . We examine one such attack below.
`
`On Christmas Day, , Kevin Mitnick broke into the computer of Tsutomu Shimomura, a com-
`
`putational physicist at the San Diego Supercomputer Center. Prior to this attack, Mitnick had found
`
`his way into the Well, a small network used mainly by an eclectic group of about , computer
`
`users in the San Francisco Bay Area  . Mitnick had been reading electronic mail of the Well’s
`
`subscribers and using Well accounts for remote attacks on computers across the Internet. During the
`
`Common implementation values for MSL are minute or  minutes.
`
`
`
`CAVIUM-1071
`Cavium, Inc. v. Alacritech, Inc.
`Page 006
`
`

`

`attack on Shimomura’s machine, two dierent intrusion mechanisms were employed  . IP source
`
`address spoong and TCP sequence-number prediction were used to gain initial access to a diskless
`
`workstation, being used mostly as an X terminal. After obtaining root access, Mitnick hijacked" an
`
`existing connection to another system by means of a loadable kernel STREAMS module  .
`
` . . Methodology
`
`Let us assume that there are three hosts, host A, host B, and the intruder-controlled host X. Let
`
`us assume that B grants A some special privileges, and thus A can get some actions performed by
`
`B. The goal of X is to get the same action done by B for itself. In order to achieve this goal, X has
`
`to perform two operations: rst, establish a forged connection with B, and second, prevent A from
`
`informing B of any malfunction of the network authentication system. Host X has to spoof the IP
`
`address of A in order to make B believe that the packets from X are actually being sent by A.
`
`Let us also assume that the hosts A and B communicate with one another by following the
`
`three-way handshake mechanism of TCPIP. The handshake method is depicted below.
`
`A -- B : SYN Seq. no. = M
`
`B -- A : SYN Seq. no. = N, ACK Ack. no. = M+ 
`
`A -- B : ACK Ack. no. = N+ 
`
`Host X does the following to perform IP spoong. First, it sends a SYN packet to host B with
`
`some random sequence number, posing as host A. Host B responds to it by sending a SYN+ACK
`
`packet back to host A with an acknowledgment number which is equal to one added to the original
`
`sequence number. At the same time, host B generates its own sequence number and sends it along
`
`with the acknowledgment number. In order to complete the three-way handshake, host X should
`
`send an ACK packet back to host B with an acknowledgment number which is equal to one added
`
`to the sequence number sent by host B to host A. If we assume that the host X is not present in the
`
`same subnet as A or B so that it cannot sni" B’s packets, host X has to gure out B’s sequence
`
`number in order to create the TCP connection. These steps are described below .
`
` A kernel module named tap-. " was compiled and installed on the system. This is a kernel STREAMS module
`which can be pushed onto an existing STREAMS stack and used to take control of a tty device  .
`
`
`
`CAVIUM-1071
`Cavium, Inc. v. Alacritech, Inc.
`Page 007
`
`

`

`X -- B : SYN Seq. no. = M, SRC = A
`
`B -- A : SYN Seq. no. = N, ACK Ack. no. = M+ 
`
`X -- B : ACK Ack. no. = N+ , SRC = A
`
`At the same time, host X should take away host A’s ability to respond to the packets of host B.
`
`To achieve this, X may either wait for host A to go down for some reason, or block the protocol
`
`part of the operating system so that it does not respond back to host B, for example, by ooding B
`
`with incomplete connections. We shall discuss this in more details in next subsection.
`
` . . The Attack
`
`During the Christmas Day, , attack, Shimomura observed a sequence of packets that were gener-
`
`ated to perform IP spoong  . Let us continue with the previous example with X as the intruder-
`
`controlled system and observe the actions performed by the intruder.
`
` . X sends a number of probe packets to B and A, trying to determine whether there exists any
`
`kind of trust relationship among hosts A and B. Commands such as showmount, rpcinfo, and
`
`nger   were utilized for this purpose.
`
`. X sends a number of TCP SYN packets, i.e., packets containing the SYN ag set with some
`
`arbitrary initial sequence numbers to host A. However, the source IP address of these packets
`
`have been forged, so that they appear to be coming from some host which does not exist in the
`
`network. Host A responds to these packets by sending corresponding SYN-ACK packets to the
`
`non-existent host. As there are no corresponding ACK packets to the packets sent by A, the
`
`three-way handshake is never complete. The connection queue for port  the login port of
`
`A are lled up with connection-setup requests; thus, the port will not be able to generate RST
`
`packets in response to unexpected SYN-ACK packets.
`
` . X sends a number of connection-request packets SYN packets to host B. When host B responds
`
`to them by sending corresponding SYN-ACK packets to X, X sends RST packets to B. Thus,
`
`the three-way handshake is not completed and TCP connections are never established between
`
`B and X. The purpose of this step is to determine the behavior of B’s TCP sequence-number
`
`
`
`CAVIUM-1071
`Cavium, Inc. v. Alacritech, Inc.
`Page 008
`
`

`

`generator. The sequence numbers obtained from B for each new connection are analyzed by X.
`
`The periodicity of these numbers is determined, and this data will be used by X in the next
`
`step to generate and send a forged packet to B with a forged sequence number.
`
`. X creates a forged SYN packet with the source IP address same as that of host A. X sends this
`
`packet to B. B sends a corresponding SYN-ACK packet to A. However, A is ignoring all of the
`
`new packets coming to its login port; it will not send any RST packet to B in response to the
`
`unexpected SYN-ACK packets from B.
`
`. X does not receive the SYN-ACK packet sent by B to A assuming X is present in a dierent
`
`subnet. However, X is in a position to predict the sequence number present in B’s SYN-ACK
`
`packet. X generates and sends a forged ACK packet to B with the source host address same
`
`as that of A and an acknowledgment number corresponding to the sequence number in B’s
`
`SYN-ACK packet. B assumes that the three-way handshake is successfully performed. Hence,
`
`there is a one-way TCP connection established from X to B.
`
`Host X is now in a position to send commands to B. B will perform these commands, assuming
`
`that they are being sent by the trusted host A.
`
` . Problems with TCP State Transitions
`
`Let us take a closer look at Step  of Section . . . The intruder-controlled host X is able to stall the
`
`login-port of host A by sending a series of SYN packets but not sending ACK packets corresponding
`
`to the SYN-ACK packets from A to X. As we have observed before, TCP maintains a connection-
`
`establishment timer. If a connection does not get established within a stipulated time typically
`
` seconds, TCP resets the connection. Thus, in our previous example, the server port will not be
`
`able to respond for a duration of  seconds.
`
` .. Extraneous State Transitions
`
`Consider a sequence of packets between hosts X and A. X sends a packet to A, with both SYN and
`
`FIN ags set. A responds by sending an ACK packet back to X, as illustrated below.
`
`
`
`CAVIUM-1071
`Cavium, Inc. v. Alacritech, Inc.
`Page 009
`
`

`

`X -- A : SYN FIN Seq. no. = M
`
`A -- X : ACK Ack. no. = M+ 
`
`Examining the state-transition diagram in Fig. , we observe that A is initially in state LISTEN.
`
`When it receives the packet from X, it starts processing the packet. It processes the SYN ag rst,
`
`then transitions to the SYN RCVD state. Then it processes the FIN ag and performs a transi-
`
`tion to the state CLOSE WAIT. Had the previous state been ESTABLISHED, this transition to the
`
`CLOSE WAIT state would have been a normal" transition. However, a transition from SYN RCVD
`
`state to the CLOSE WAIT state is not dened in the TCP specication. This phenomenon occurs in
`
`several TCP implementations, such as those in the operating systems SUNOS . . , SVR, and UL-
`
`TRIX . . Thus, contrary to specications, there exists in several TCP implementations a transition
`
`arc from the state SYN RCVD to the state CLOSE WAIT, as shown in Fig. !
`
` .. Security Relevance
`
`In our example attack scenario, the TCP connection is not yet fully established since the three-way
`
`handshake is not completed; thus, the corresponding network application never got the connection
`
`from the kernel. However, host A’s TCP machine" is in CLOSE WAIT state and is expecting
`
`the application to send a close signal so that it can send a FIN packet to X and terminate the
`
`connection. This half-open connection remains in the socket-listen queue and the application does
`
`not send any message to help TCP perform any state-transition. Thus, A’s TCP machine" gets
`
`stuck in the CLOSE WAIT state. If the keep-alive timer feature is enabled, TCP will be able to reset
`
`the connection and perform a transition to the CLOSED state after a period of usually two hours.
`
`Intruder-controlled host X needs to perform the following steps to wedge A’s operating steps so
`
`that it cannot respond to unexpected SYN-ACKs from other hosts for as long as two hours.
`
` . X sends a packet to host A with SYN and FIN ags set. A responds with an ACK packet. A
`
`changes its state from CLOSEDLISTEN to SYN RCVD, and then to CLOSE WAIT.
`
`. X does not send any more packet to A, thus preventing any TCP state-transitions in A.
`
`
`
`CAVIUM-1071
`Cavium, Inc. v. Alacritech, Inc.
`Page 010
`
`

`

`Thus, we observe that extraneous state-transitions exist in several implementations of TCP and
`
`these may lead to severe security violations of the system.
`
` . Problem with Timers
`
`As we have discussed before, whenever the process of connection setup is in progress, a connection-
`
`establishment timer is turned on. If the connection does not get established within a stipulated time,
`
`TCP reverts back to the CLOSED state.
`
` . . Simultaneous Open
`
`During establishment of a simultaneous open connection between two hosts, we have found that
`
`the connection-establishment timer behaves in a dierent way. Let us consider our example of hosts
`
`A and X. Host A sends a SYN packet to X, expecting a SYN-ACK packet back in response. Let us
`
`assume that, almost at the same time, host X wants to start a connection with A and sends a SYN
`
`packet to A. Both A and X send a SYN-ACK packet to each other when they receive the SYN packet
`
`from the other party. When each receives the SYN-ACK packet from the other party, it assumes
`
`that the connection is established. In this scenario, the connection-establishment timer is switched
`
`o when the host receives the SYN packet from the other host , as shown below.
`
`X -- A : SYN Seq. no. = M
`
`A -- X : SYN Seq. no. = N
`
`X -- A : SYN Seq. no. = M, ACK Ack. no. = N+ 
`
`A -- X : SYN Seq. no. = N, ACK Ack. no. = M+ ,
`
` . . Security Relevance
`
`Let us consider the sequence of steps followed by an intruder-controlled host X and host A.
`
`The connection-establishment timer is turned o when the TCP connection is fully established, i.e., the TCP
`machine" does a state-transition to the ESTABLISHED state and both the hosts have the ACK packets from the
`peer hosts.
`
`
`
`CAVIUM-1071
`Cavium, Inc. v. Alacritech, Inc.
`Page 011
`
`

`

` . Host X sends a FTP request to host A. A TCP connection is established between X and A to
`
`transfer control signals. Host A sends a SYN packet to X in order to start a TCP connection
`
`for data-transfer and performs a state-transition to the state SYN SENT.
`
`. When X receives the SYN packet from A, it sends a SYN packet back in response.
`
` . When host A receives this packet, it assumes that a simultaneous open connection is in progress;
`
`it sends out a SYN-ACK packet to X and at the same time switches o the connection-
`
`establishment timer and makes a state-transition to state SYN RCVD.
`
`. Host X receives the SYN-ACK packet from A but does not send back any packet.
`
`. Host A is expecting a SYN-ACK from the host X. Since X does not send back any packet, A
`
`gets stalled in the state SYN RCVD.
`
`Thus, X is successfully able to stall a port of host A. This is clearly a denial-of-service attack.
`
`In the following section, we shall discuss our approach to single out extraneous state-transitions
`
`in the TCP state-transition diagram using the slicing method.
`
` Slicing
`
`Program slicing   produces a bona-de program|a subset of the original program|that behaves
`
`exactly the same with respect to the computation of a designated property  . In the following
`
`subsections, we shall examine the basic idea behind program slicing, the meaning of slicing criteria,
`
`and some example slicing applications.
`
`. Overview
`
`Program slicing is an abstraction mechanism in which code that might inuence the value of a given
`
`variable or a set of variables at a location is extracted from the full source code of the program  .
`
`Weiser   originally implemented slicing for FORTRAN programs. Automatic slicing requires that
`
`the behavior of interest be expressed in a certain way. If this behavior can be communicated as
`
` 
`
`CAVIUM-1071
`Cavium, Inc. v. Alacritech, Inc.
`Page 012
`
`

`

`values of some set of variables at some set of statements, then the specication is said to be slicing
`
`criterion  .
`
`The concept of breaking down a large program into smaller and simpler modules for analysis is
`
`observed in  . Zislis denes busy variables" as variables that will be used later in the program.
`
`He employed these variables as the criteria to group related program statements and form a program
`
`slice. Weiser   used data-dependence to group statements together. There are several other ways
`
`to slice a program, namely backward data-ow slicing, forward data-ow slicing, control-ow slicing,
`
`etc. There are two essential properties of a program slice  , as follows.
`
` . The program slice must be executable.
`
`. For the same input values, the variables must have identical values at the corresponding lo-
`
`cations both in the slice and the original program. This assists in maintaining the semantic
`
`meaning of the program.
`
`Finding the exact and smallest program slice from a given program is an undecidable problem.
`
`However, data-ow analysis can determine an approximate program slice by nding all of the program
`
`code that might have inuenced the specied behavior. A simple approach would have been to delete
`
`source statements; but this will lead to ungrammatical program slices. For example, removing
`
`the THEN clause from an IF-THEN-ELSE statement leaves an ungrammatical program fragment,
`
`assuming that a null" statement is not allowed between THEN and ELSE. A more ecient but
`
`elaborate method will be to translate the input program into an intermediate form, apply program
`
`slicing to it, and then reconstruct the slice into a complete program.
`
`Slicing is a valuable tool in debugging, testing, and maintenance of software when only a portion
`
`of a program’s behavior is to be examined. It identies the portion of the program that aects the
`
`specied behavior and produces slices that are signicantly simpler, and smaller, than the original
`
`program.
`
`. Slicing Criteria
`
`As we mentioned before, slicing is carried out with respect to a slicing criterion. In the simplest form,
`
`a criterion is a variable, andor a location in the program. More complex criteria involve multiple
`
`
`
`CAVIUM-1071
`Cavium, Inc. v. Alacritech, Inc.
`Page 013
`
`

`

`variables, multiple locations, and more complex program analysis.
`
`A program slice is represented by a set of nodes. Anything that can be described in terms of
`
`nodes in a dataow graph can serve as a slicing criterion  . At the same time, it is possible to
`
`combine the eects of dierent slicing methods using dierent criteria by simply manipulating the
`
`sets of nodes. Features such as set-union, set-dierences, etc. can be accomplished on these set of
`
`nodes. This approach facilitates better analysis of a given program using multiple slicing criteria.
`
`There exist a number of dierent techniques to slice a given program, the most common being
`
`the backward slice approach. A basic backward slice of a program is produced by rst generating
`
`a combined control and data ow graph of the program, based upon the parse tree of the program.
`
`Nodes that correspond to the slicing criteria form the basis of the slice. A node is added to the slice
`
`if it is a denition of the value of a node in the slice, if it is used in a computation of a node in the
`
`slice, or if it is a part of a control point which dominates a node in the slice  . The nal slice is
`
`the subset of the nodes of the ow graph which have been identied by the above procedure.
`
`The forward slice technique works forward through the parse tree. It traces the fan-out eect
`
`of a ow node. Combination of backward and forward slicing techniques can produce slices which
`
`characterize the behavior of a program in a more lucid way.
`
`. Example
`
`Let us examine the program in Fig. . It computes the mean and the maximum value of all the data
`
`elements in the array data. We want to retain the part of the program that computes the mean
`
`of all the data elements. Hence, we slice this program with respect to the variable mean". The
`
`program slicer computes the control and data dependence and creates the slice. In order to compute
`
`the value of mean in line , the slicer needs the values of the variables sum and n. Data-ow analysis
`
`tells the slicer to use the values of the variable sum dened in lines , , and . Similarly, the
`
`program slicer will examine the lines , , and for the variable n. Continuing in this fashion,
`
`the nal program slice looks as shown in Fig. .
`
`Thus, from the original program, we obtain a subprogram which is functionally complete, and
`
`which focuses on the variable mean and the way it is referred to and computed in the program.
`
` 
`
`CAVIUM-1071
`Cavium, Inc. v. Alacritech, Inc.
`Page 014
`
`

`

`. TCP State-Transition Diagram
`
`The TCPIP protocol stack is implemented in the kernel space for most commercial implementation
`
`of UNIX systems. The TCP part of the code usually consists of six C les and seven header les. Out
`
`of these les, the le tcp input.c" contains the implementation of the TCP state-transition diagram.
`
`This le handles most of the state transitions dened in the protocol implementation. However, it
`
`incorporates other features of TCP such as retransmission of data packets, timer controls, ow control,
`
`etc. Since we are most interested in analyzing the state-transition diagram, we slice this program
`
`with respect to the TCP state variable" called t state" and obtain a simplied program slice. The
`
`result and its security relevance will be discussed in the following sections.
`
` Analysis
`
`. The Slicer
`
`In order to analyze the TCP source code for spurious state-transitions, we have employed the slicer
`
`Tester’s Assistant TA, version .  . TA has been developed in part by the Software Testing
`
`Research Laboratory at University of California, Davis.
`
`In order to slice a C le using TA, we
`
`rst pass the program through a C preprocessor and feed it to the slicer. After computing some
`
`initial node-analysis, TA responds with a prompt and accepts commands such as back" subsequent
`
`slices will be backward slices, forward" subsequent slices will be forward slices, prog" print
`
`out original code, summary" print out a description of previous slice commands, var var" slice
`
`program with respect to the variable var, func func" slice program with respect to the function
`
`func", union num num" perform the union of two previous slices num and num, etc. One
`
`limitation of the slicer is that it does not handle pointer aliasing properly yet. However, for our
`
`current TCP code analysis, this limitation does not create any problem.
`
`. Slicing Criteria
`
`As we