CS-636 Project 1

Network Analyzer

Introduction

A variety of tools exist that analyze packets on a network; they are invaluable when debugging network protocols. Although you will need an analyzer to help debug your class project, we do not supply you with one. Instead, your first assignment is to construct a network analyzer. You will modify the Xinu operating system to capture Ethernet packets, parse headers, accumulate statistics about the packet addresses and types, and search for specific packets. In addition to producing a useful debugging tool, this exercise will make you familiar with packet handling in Xinu, and expose you to basic of packet formats, both of which will be crucial when you build the semester project.

Description

This project has been divided in multiple parts that we recommend you to follow in sequence. Your grade in this project will be based in the number of features that work as well as their correctness.

Your network analyzer should run as a Xinu shell process. The syntax of the command is the following:

xnoop [options] [filter]
The options and the filter sections are optional and they will be explained next.

Table of Contents

Part 1. Basic Options
Part 2. Verbose mode
Part 3. Extended Verbose Mode
Part 4. Storing Packets for Further Analysis
Part 5. Filtering
Part 6. Adding New Functions
Part 7. Customizing Output
Technical Information
When to turn in

Part 1. Basic Options

If you run xnoop without any options or filter, it will capture maxcount  packets, where maxcount is 100 by default. It will also print a summary of the packets.
xinu> xnoop
ethernet frames:       100
ethernet broadcast:    5
ARP                    2
RARP                   1
IP                     80
BOOTP                  1
ICMP                   2
UDP                    20
TCP                    50
To this host:          3
-c <maxcount>
To change the number of captured packets maxcount, you will implement the option "-c". The following command captures 200 packets and displays the summary:
xinu> xnoop -c 200
-t <seconds>
This option allows you to capture packets for a specified amount of time or when the number of captured packets has reached maxcount, whatever happens first.

Implement ctrl-c to stop xnoop before it captures maxcount packets. After ctrl-c, the statistics should be printed with the packets received so far.

Part 2. Verbose mode

-v (lower case v)
This option will print one line for every packet captured. Here are some examples.

xinu> xnoop -c 4 -v
xinu1.cs.purdue.edu -> (broadcast)  ARP Who is 128.10.3.31
xinu1.cs.purdue.edu -> xinu7.cs.purdue.edu TCP TELNET sourceport= 23 destport=33060
lucan.cs.purdue.edu -> xinu1.cs.purdue.edu UDP NFS sourceport=2049 destport=121
lodegreaunce.cs.purdue.edu -> BROADCAST ICMP Destination unreachable (Bad port)

Note: In the previous output, host names are used instead of IP addresses or Ethernet addresses. The Xinu sources you are using do not have a DNS implementation to convert IP addresses to names. You may initially use IP addresses (or ethernet addresses) instead of host names, and then later in the project you can construct a static table of IP addresses to ethernet addresses to names in Xinu to perform this translation.

Note: The output examples in this handout do not cover all the possibilities you may encounter so you will have to design sometimes your own output. In these cases, be creative and think about functionality.

Part 3. Extended Verbose Mode

-V (capital V)
This option turns on an extended verbose mode. In the extended verbose mode you will print the packets more in detail. Here are some examples:
xinu> xnoop -c 4 -V
     ETHER:  ----- Ether Header -----
     ETHER:
     ETHER:  Packet 1
     ETHER:  Packet size = 210 bytes
     ETHER:  Destination = 8:0:20:1:3d:94,
     ETHER:  Source      = 8:0:69:1:5f:e,
     ETHER:  Ethertype = 0800 (IP)
     ETHER:
     IP:   ----- IP Header -----
     IP:
     IP:   Version = 4, header length = 20 bytes
     IP:   Type of service = 00
     IP:         ..0. .... = routine
     IP:         ...0 .... = normal delay
     IP:         .... 0... = normal throughput
     IP:         .... .0.. = normal reliability
     IP:   Total length = 196 bytes
     IP:   Identification 19846
     IP:   Flags = 0X
     IP:   .0.. .... = may fragment
     IP:   ..0. .... = more fragments
     IP:   Fragment offset = 0 bytes
     IP:   Time to live = 255 seconds/hops
     IP:   Protocol = 17 (UDP)
     IP:   Header checksum = 18DC
     IP:   Source address = 129.144.40.222,
     IP:   Destination address = 129.144.40.200,
     IP:
     UDP:  ----- UDP Header -----
     UDP:
     UDP:  Source port = 1023
     UDP:  Destination port = 2049
     UDP:  Length = 176
     UDP:  Checksum = 0
     UDP:
     UDP: Data: First 64 bytes
     UDP: 5408 0400 2100 0000 ffff ffff ffff c003 "T...!..........."
     UDP: 5408 0400 2100 0000 ffff ffff ffff c003 "T...!..........."
     UDP: 5408 0400 2100 0000 ffff ffff ffff c003 "T...!..........."
     UDP: 5408 0400 2100 0000 ffff ffff ffff c003 "T...!..........."
     UDP:
 
ETHER:  ----- Ether Header -----
ETHER:
ETHER:  Packet 2
ETHER:  Packet size = 60 bytes
ETHER:  Destination = 0:c0:4f:79:ed:a2,
ETHER:  Source      = 0:0:c:b:47:64,
ETHER:  Ethertype = 0800 (IP)
ETHER:
IP:   ----- IP Header -----
IP:
IP:   Version = 4
IP:   Header length = 20 bytes
IP:   Type of service = 0x00
IP:         xxx. .... = 0 (precedence)
IP:         ...0 .... = normal delay
IP:         .... 0... = normal throughput
IP:         .... .0.. = normal reliability
IP:   Total length = 40 bytes
IP:   Identification = 25372
IP:   Flags = 0x4
IP:         .1.. .... = do not fragment
IP:         ..0. .... = last fragment
IP:   Fragment offset = 0 bytes
IP:   Time to live = 254 seconds/hops
IP:   Protocol = 6 (TCP)
IP:   Header checksum = 4b14
IP:   Source address = 128.211.1.31, lorenzo.cs.purdue.edu
IP:   Destination address = 128.10.3.108, xinu8.cs.purdue.edu
IP:   No options
IP:
TCP:  ----- TCP Header -----
TCP:
TCP:  Source port = 41891
TCP:  Destination port = 23 (TELNET)
TCP:  Sequence number = 2009202523
TCP:  Acknowledgement number = 660063620
TCP:  Data offset = 20 bytes
TCP:  Flags = 0x10
TCP:        ..0. .... = No urgent pointer
TCP:        ...1 .... = Acknowledgement
TCP:        .... 0... = No push
TCP:        .... .0.. = No reset
TCP:        .... ..0. = No Syn
TCP:        .... ...0 = No Fin
TCP:  Window = 8760
TCP:  Checksum = 0x8080
TCP:  Urgent pointer = 0
TCP:  No options
TCP: Data: (first 64 bytes)
TCP: fffa 1800 5854 4552 4dff f0ff fa23 0069 "....XTERM....#.i"
TCP: 0d0a 0d0a 5375 6e4f 5320 352e 360d 0a0d "....SunOS 5.6..."
TCP: 0000 0000 0000 6e4f 5320 352e 360d 0a0d "......nOS 5.6..."
TCP: fffb 01ff fd01 6c6f 6769 6e3a 200d 0a0d "......login: ..."
TCP:

ETHER:  ----- Ether Header -----
ETHER:
ETHER:  Packet 3
ETHER:  Packet size = 60 bytes
ETHER:  Destination = ff:ff:ff:ff:ff:ff, (broadcast)
ETHER:  Source      = 0:aa:0:a2:ec:fa, Intel
ETHER:  Ethertype = 0806 (ARP)
ETHER:
ARP:  ----- ARP/RARP Frame -----
ARP:
ARP:  Hardware type = 1
ARP:  Protocol type = 0800 (IP)
ARP:  Length of hardware address = 6 bytes
ARP:  Length of protocol address = 4 bytes
ARP:  Opcode 1 (ARP Request)
ARP:  Sender's hardware address = 0:aa:0:a2:ec:fa
ARP:  Sender's protocol address = 128.10.3.201, xinu101.cs.purdue.edu
ARP:  Target hardware address = ?
ARP:  Target protocol address = 128.10.3.31, helga.cs.purdue.edu
ARP:

ETHER:  ----- Ether Header -----
ETHER:
ETHER:  Packet 4
ETHER:  Packet size = 98 bytes
ETHER:  Destination = 0:c0:4f:79:ed:af,
ETHER:  Source      = 0:0:c:b:47:64, Cisco
ETHER:  Ethertype = 0800 (IP)
ETHER:
IP:   ----- IP Header -----
IP:
IP:   Version = 4
IP:   Header length = 20 bytes
IP:   Type of service = 0x00
IP:         xxx. .... = 0 (precedence)
IP:         ...0 .... = normal delay
IP:         .... 0... = normal throughput
IP:         .... .0.. = normal reliability
IP:   Total length = 84 bytes
IP:   Identification = 37847
IP:   Flags = 0x4
IP:         .1.. .... = do not fragment
IP:         ..0. .... = last fragment
IP:   Fragment offset = 0 bytes
IP:   Time to live = 254 seconds/hops
IP:   Protocol = 1 (ICMP)
IP:   Header checksum = 69e3
IP:   Source address = 128.211.1.31, lorenzo.cs.purdue.edu
IP:   Destination address = 128.10.3.107, xinu7.cs.purdue.edu
IP:   No options
IP:
ICMP:  ----- ICMP Header -----
ICMP:
ICMP:  Type = 8 (Echo request)
ICMP:  Code = 0
ICMP:  Checksum = 8dfd
ICMP:

By default print up to 80 bytes of each packet unless the length is explicitly specified by the -S option. You may use two columns: in the left column you will print the bytes in hexadecimal, and in the right column you will print the corresponding ASCII characters or "." if it is a non printable character (<ASCII 32). This is very useful feature when debugging programs that use TCP.

Part 4. Storing Packets for Further Analysis

Sometimes it is useful to analyze packets off-line, i.e., store them in memory and then analyze them at a later time. The following options provide this functionality.

-s idname
Store the captured packets in memory for further analysis under the name idname. There may be different sets of captured packets under different idname's. If the same idname is reused, the memory used by the previously captured packets under that idname will be released. If Xinu runs out of memory before all the packets are captured, xnoop will return with an error, and only the packets captured so far will be stored under idname.

-r idname
Releases the memory used by the previously captured packets under this idname.

-d idname
Displays packets previously captured and stored under this idname. Without this option, xnoop reads packets from the network interface.

-f first
Displays packets previously captured starting in packet first.

-l last
Displays packets previously captured ending in packet last.

-S snaplen
By default only a maximum of 80 bytes of every packet are stored. This option allows to store longer packets.

Examples:

Store five packets under the name mypackets:

xinu> xnoop -c 5 -s mypackets
5 packets captured and stored in "mypackets"
Display stored packets 3 and 4 in verbose mode:
xinu> xnoop -v -d mypackets -f 3 -l 4
lucan.cs.purdue.edu -> xinu1.cs.purdue.edu UDP NFS sourceport=23 destport=121
lodegreaunce.cs.purdue.edu -> BROADCAST ICMP Destination unreachable (Bad port)
Display packet 3 in extended verbose mode:
xinu> xnoop -V -d mypackets -f 3 -l 3
Release space used by packets stored under the idname "mypackets"

    xinu> xnoop -r mypackets

Part 5. Filtering

This feature allows to filter captured packets. A filter can be used in both the captured packets and the stored packets.

The filter part of the xnoop command uses Reverse Polish Notation (RPN) or postfix notation.  RPN is a stack based method of performing operations that is used in the HP scientific calculators, and in computer languages such as PostScript and FORTH.

For example, if you want to perform the operation 3*(4 + 5) in a calculator that uses RPN, you will type 3 4 5 + *.
 

3 Pushes 3 to the stack: Stack={3}
4 Pushes 4 to the stack: Stack ={3, 4}
5 Pushes 5 to the stack: Stack={3, 4, 5}
+ Pops the two topmost values in the stack, adds them, and pushes the result. Stack={3,9}
* Pops the two topmost values in the stack, multiplies them, and pushes the result. Stack=27.

RPN has the advantages that it is simple and easy to program. There are no problems with operator precedence, and therefore, there is no need for parenthesis.

The stack is defined as an array of 8 byte words, so each entry in the stack stores up to 8 bytes. Each stack entry may store a number, an IP address, or an Ethernet address. The unused bytes will be filled with 0s. The elements in the stack do not have types, and therefore it is not be possible to differentiate an IP address from an Ethernet address once they are pushed into the stack.

In order to capture or display a packet, the filter expression should evaluate to a number different than 0 on the top of the stack . An error during the evaluation of the filter will result in a 0 on the top of the stack.

Arithmetic operations will be done in 4 byte arithmetic. Comparisons will use 8 bytes.

The operators are the following.
 

Filter Operators
Primitives
Decimal Numbers: [0-9][0-9]* Push this number to stack. The number is 4 bytes long. 
Hexadecimal Number 0x[0-9,A-F,a-f][0-9,A-F,a-f]* Push this hexadecimal number to stack The number is 4 bytes long. 
IP Address: d.d.d.d Push IP Address to stack The IP address uses the 4 lower bytes and the 4 top bytes are filled with 0s.
Ethernet address xx:xx:xx:xx:xx:xx Push Ethernet address to stack. The Ethernet address uses the 6 lower bytes and the 2 top bytes are filled with 0s.
Operators
a b =  or a b eq Pops a and b from the stack. If both a and b are identical, it pushes 1 to the stack. Otherwise, it pushes 0. 
a b and Pops a and b from the stack. If a!=0 and b!=0, then it pushes 1 to the stack. Otherwise, it pushes 0.
a b or Pops a and b from the stack. If a!=0 or b!=0, then it pushes 1 to the stack. Otherwise, it pushes 0.
a not Negates the top of the stack. If a!=0, then it pushes 0, otherwise it pushes 1.
a b <operator> Pops a and b from the stack. Performs the operation indicated by <operator> and pushes the result back to the stack. The operations can be +, -, *, /, and %. Any error will result in 0 being pushed to the stack.
Bit operators
a b sl Pops a and b from the stack. It shifts a  a number of b places to the left and pushes the results to the stack.
a b sr Pops a and b from the stack. It shifts a  a number of b places to the right and pushes the results to the stack.
a b band Pops a and b from the stack. It performs a bit-and operation between a and b and pushes the result to the stack.
a b bor Pops a and b from the stack. It performs a bit-or operation between a and b and pushes the result to the stack.
a bnot Pops a. It performs a bit-not operation and pushes the result to the stack. 
Protocols
ip Pushes 1 to the stack if the packet is an IP packet. Otherwise, it pushes 0.
udp Pushes 1 to the stack if packet is an UDP packet. Otherwise, it pushes 0.
tcp Pushes 1 to the stack if packet is a TCP packet. Otherwise, it pushes 0.
icmp Pushes 1 to the stack if packet is an ICMP packet. Otherwise, it pushes 0.
arp Pushes 1 to the stack if packet is an ARP packet. Otherwise, it pushes 0.
rarp Pushes 1 to the stack if packet is an RARP packet. Otherwise, it pushes 0.
bootp Pushes 1 to the stack if packet is an BOOTP packet. Otherwise, it pushes 0.
Ethernet
etherto Pushes to the stack the destination ethernet address.
etherfrom Pushes to the stack the source ethernet address.
ethertype Pushes to the stack the ethernet type.
IP
ipto Pushes to the stack the IP destination address. If the packet is not an IP packet, it pushes 0.
ipfrom Pushes to the stack the IP source address. If the packet is not an IP packet, it pushes 0.
ipproto Pushes to the stack the IP protocol. If the packet is not an IP packet, it pushes 0.
UDP
udptoport Pushes to the stack the destination port. If the packet is not an UDP packet, it pushes 0.
udpfromport Pushes to the stack the source port. If the packet is not an UDP packet, it pushes 0.
TCP
tcptoport Pushes to the stack the destination port. If the packet is not a TCP packet, it pushes 0.
tcpfromport Pushes to the stack the source port. If the packet is not an TCP packet, it pushes 0.
ICMP
icmptype Pushes to the stack the icmptype. If the packet is not an ICMP packet, it pushes 0.
Packet Arrays
a b ethera Pushes to the stack b bytes from the Ethernet packet starting at position a bytes from the beginning of the Ethernet packet. It pushes 0 if this is not an Ethernet packet. If the end of the packet is reached, 0's are copied. Bytes are copied in host byte order.
a b ipa Pushes to the stack b bytes from the IP packet starting at position a bytes from the beginning of the IP packet. It pushes 0 if this is not an IP packet. If the end of the packet is reached, 0's are copied. Bytes are copied in host byte order.
a b udpa Pushes to the stack b bytes from the UDP packet starting at position a bytes from the beginning of the UDP packet. It pushes 0 if this is not an UDP packet. If the end of the packet is reached, 0's are copied. Bytes are copied in host byte order.
a b tcpa Pushes to the stack b bytes from the TCP packet starting at position a bytes from the beginning of the TCP packet. It pushes 0 if this is not an TCP packet. If the end of the packet is reached, 0's are copied. Bytes are copied in host byte order.
a b icmpa Pushes to the stack b bytes from the ICMP packet starting at position a bytes from the beginning of the ICMP packet. It pushes 0 if this is not an ICMP packet. If the end of the packet is reached, 0's are copied. Bytes are copied in host byte order.
Stack Manipulation  
a b swap Swaps a and b.
a dup Duplicates the value of a in the stack.
a disc Pops a from the stack and discards it.
n get Pops n and pushes the nth entry below the top of the stack. 0 get is equivalent to dup.
n del Pops n and deletes the nth entry below the top of the stack. 0 del is equivalent to disc.
phi Pushes the hight of the stack to the top.

Examples:

Capture two UDP packets and display them in verbose mode
xinu> xnoop -c 2 -V udp
Capture ten UDP or TCP packets that come from 128.10.3.108.
xinu> xnoop -c 10 -V udp tcp or 128.10.3.108 ipfrom eq and
Capture ten packets that  go to 0:c0:4f:79:ed:a2 and store them.
xinu> xnoop -c 10 -s mypackets etherto 0:c0:4f:79:ed:a2 eq
From the stored packets display only the TCP packets.
xinu> xnoop -d mypackets tcp
The following two commands are equivalent, both of them get one ARP packet.
xinu> xnoop -c 1 ethertype 0x806 eq
xinu> xnoop -c 1 12 2 ethera  0x806 eq
IMPORTANT: You will also implement  a Xinu command called calc: 
xinu> calc <filter>
This command will evaluate the filter passed. This function will be used for testing your filter evaluator. The packet operators such as ip etc will return 0 when used inside the calc operator.

Part 6. Adding New Functions

-u function-name <filter>
Defines a new filter and stores it under the name function-name. To use a defined function inside a filter use function-name anywhere in a filter and it will be expanded to the corresponding function.

-U
Lists all the defined functions.

Examples:

Define a filter for TELNET packets
xinu> xnoop -u telnet tcptoport 23 eq tcpfromport 23 eq or
Use the telnet filter: capture one telnet packet and display it.
xinu> xnoop -c 1 telnet

Part 7. Customizing Output

The following operators are used to customize the output.
 
Customizing Output
a b prdec If a is 1 it prints b as decimal. a is left on the stack.
a b prhex If a is 1 it prints b as hexadecimal. a is left on the stack.
a b prip If a is 1 it prints b as an IP address. a is left on the stack.
a b prhost If a is 1 it prints b as a host name. a is left on the stack.

Example:

Capture 10 tcp packets and print the from and to IP address:

xnoop -c 10 tcp tcpfrom prip tcpto prip

Technical Information

Which Sources to Use

The Xinu sources that you will use are in  /u/u3/636/otx636.tgz You can untar them by typing from your home directory:
tar -xzf /u/u3/636/otx636.tgz

Promiscuous Mode

For this project you will need to be able to put the Ethernet device into promiscuous mode. Normally the Ethernet device will accept only frames with a destination address which is the same as its own, with a broadcast destination address, or with a multicast destination address for which the device is  listening. In promiscuous mode the device will accept all frames, regardless of destination address.

Before sniffing you will want promiscuous mode to be turned on, and after sniffing turned off. To accomplish this will will need to control() the Ethernet device. For details see 636/eth/eep_cntl.c.

Getting the Data

You may want to follow the code beginning at eep_intr() to see the path that an incoming frame takes. In one of the functions you will find a hook which passes incoming frames to a user specified function. The function is specified by the (pseudo) field ed_xpafunc in the ethdev structure. The decision as to whether or not to pass the packet to that function is based on the boolean field, ed_xpa, of the same structure.

Machine's Own Addresses

The handout asks you to count the number of packets destined for the machine on which it is running. You can find the interfaces' IP and hardware addresses in the structure which describes the interfaces.
 

When to turn in

CS636 students should turn in their projects by  11:59pm, Saturday Feburary 7, 2004.

Follow these instructions to turnin project 1.

Assuming that your project's top directory is otx636/

1. Write a otx636/README file including  the following:

  a) Enumerate the features (or parts) in the handout that work in
   your project

  b) Enumerate the Features (parts) in the handout that do not work in
   your project.

2. cd to otx636/compile/ and type "make clean".

3. cd to otx636/.. (above otx636/) and type:

        turnin -c cs636 -p proj1 otx636

4. To make sure that you have submitted the right files type:

        turnin -c cs636 -p proj1 -v