Statistical Analysis of Massive Data Streams: Proceedings of a Workshop (2004)

Below is the uncorrected machine-read text of this chapter, intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text of each book. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.

VISUALIZATION OF INTERNET PACKET HEADERS 264 TRANSCRIPT OF PRESENTATION MS. MARTINEZ: Our next speaker is Professor Ed Wegman from George Mason University, and he is going to continue to talk about Internet traffic and how can we analyze it. MR. WEGMAN: I must say, it is always a formidable challenge to come after Bill Cleveland, who was my colleague once upon a time in Chapel Hill, when we were both quite a lot younger. Bill was looking at Internet traffic from sort of the global perspective. What I would like to do is have a discussion of our sort of internal structure. We are particularly concerned with issues of intrusion into our systems. Don Faxon and I work at George Mason University. Jeff Solka and John Rigsby are colleagues of ours that work at the Naval Surface Warfare Center. One of the issues of interest is, how intrusions in a military setting are different from intrusions in an academic setting, and is there sort of a qualitative or quantitative characteristic difference between the Internet traffic in these two settings? So, we are working relatively closely with these guys. What I would like to do is give a little background on TCP/IP. I realize probably a lot of people in the audience already know a lot of this. This is, you know, partly, for me, but I hope that some people may not know as much about the nuts and bolts of it, which are relatively important in understanding how intrusions are done. I would like to talk a little bit about our project, do a little demo. Then, I would 

VISUALIZATION OF INTERNET PACKET HEADERS 265 like to talk about streaming algorithms and maybe some graphics proposals that we have. Now, Bill talked about IP addresses, but didn't go into any detail. Technically, these are called IP version 4 addresses. IPv addresses are 32-bit numbers, usually represented as four dotted fields. Field one, two, three or four, or sometimes called octet one, two, three and four. In general, these IP addresses uniquely identify a machine, although that is not entirely true, because IPs can be dynamically assigned. So, they may not uniquely identify a machine. There is also a number called a MAC number, which is a manufacturer's number, which does essentially uniquely identify the machine. So, in principle, it is better to find the MAC number than the IP address, if you are trying to identify and locate individual machines. Each of these fields is 256. It is an eight-bit field. So, if you multiply that you, you come out with approximately 4 billion addressable machines. There are a number of different types of networks—Class A, Class B, Class C. Most of us are probably associated with Class B networks, where the first two fields identify the network, and the second two fields identify specific hosts. Field three is often used as the identifier of the subnet. In a Class A network, field one is always smaller than 127, 127 is the loop-back number. So, there are relatively few, there can only be 126 or so Class A networks, and there are a few. I noticed in Bill's presentation—Bill Cleveland's presentation—none of the networks were identified as Class A networks. 

VISUALIZATION OF INTERNET PACKET HEADERS 266 You can also have Class C networks, in which field four identifies the host and the first three fields identify the particular network. So, Class C networks are relatively small networks, they only have 256 hosts in the network. Just a word on IP addressing. The TCP/IP addressing is normally regarded as a layered system. So, at the highest level, you have sort of the application layer, which is the data itself. Attached to that, application header. Attached to that is a protocol header. The protocol that we are typically familiar with is TCP/IP, although there are three or four other kinds of protocols that are relatively common. The discussion that Bill was talking about principally is the IP layer, which is the IP header, and then finally the hardware layer attached to this. So, in order to get the application data, you have all this other stuff, which is basically metadata about routing and so on, and what kind of stuff is in the IP address. So, here is the basic structure of the IP header. It is the version, IP version four is the common version. IP version six is in the wings. The length, the type of service, total length, some identification, flags, fragment offset, time to live. Each packet has a maximum possibility of 255 lifetimes, and each time it transits a router, the time to live gets decremented. So, if it goes through too many routers, it ceases to exist. There is information about the protocol and critical information of source IP and destination IP and other options. 

VISUALIZATION OF INTERNET PACKET HEADERS 267 One of the things that is of significant importance is the flag. Of course, what really is important is the data, but that almost sort of gets lost in the, I guess, noise. Some flag types are acknowledgment flags ACKs, PSH flags that say the data should be pushed into the application as soon as possible, a reset, a SYN, or synchronization of a connection, and a FIN, which is the finish of the connection. So, a possible IP session might be that the Host 1, or the computer that is seeking data will send out a SYN packet. These are the 40-byte packets that Bill is talking about. Host two will send out a SYN/ACK, will acknowledge the fact that it has received this packet. So, one possibility for discovering intrusion is if you are receiving a lot of SYNs with no ACKs, no SYN/ACKs, then somebody is probing the system, and they are not probing the right ports, so they are not getting any acknowledgments. So, one of the ways of discovering that you are being probed and things maybe aren't quite what they should be is looking for the ratio of SYN that is in ACK packets. Once there is an acknowledgment, then the host one acknowledges the fact that it received the SYN/ACK packet, and then started sending out the data. So, essentially, those are the PSH things. When that stuff is received, the host two sends the acknowledgment. It pushes out some data. The host one will acknowledge it and say, I am done, and the host two can send out a FIN/ACK, which is the final acknowledgment. It is an acknowledgment of his FIN. Host 2 may not be done, so he may send out some more data. Finally, you get to an acknowledgment of that. Then finally, the sign off handshake is that Host 2 will say, I am done, send the FIN packet, and then the other host will send the FIN/ACK, and that 

VISUALIZATION OF INTERNET PACKET HEADERS 268 ends the session. Clearly, this is a very abbreviated kind of session. If you are getting Internet traffic from e-mail or, for example, from Web pages, there is maybe lots more of this going on, but this is sort of the typical prototype. Just to give you a scale of things, an IPv version 6 address is a 128-bit address, arranged as eight groups of 16-bit numbers, separated by colons. So, it is hexadecimal and so a typical IPv6 address may be configured something like that. In general, leaving zeros may be omitted. So, instead of writing all these zeros in, you can just put the final zero in, and so you can compress the address quite a lot by omitting leading zeros. If you have a sequence of zeros, then that can be replaced by a double colon. So, the address can be compressed even further. Now, it turns out the last two fields are sufficient to fit in current IPv4 addresses. So, for example, an address that is 1310345 can be compressed as this. The way that is, is that 130 in decimal is 82 in hex, so the 130 becomes 82, the 103 in decimal becomes 67 in hex. So, this part is the first two fields of an IPv4 address, and then the second part, 2805, corresponds to the party in five in the IPV 4 address. Since everything else would be leading zeroes, we can simply put the double colon in. So, this is the IPv6 version of the IPv4 address, and there are sort of hybrids allowed, so that you can put in the single point instead of a colon to get something. Now, a question is, how many hosts are possible? One reason I am sort of going through this is that, if you are interested in visualization, you are interested in how many 

VISUALIZATION OF INTERNET PACKET HEADERS 269 things you can see. If you sort of multiply all that junk out, you get 3.4 times 1038, which roughly means that every 30 atoms can be having its own IPv6 address. So, there are a lot of these addresses. AUDIENCE: It is still a factor of 30 short. MR. WEGMAN: I was thinking on the way in, because I have sort of stupid random thoughts while riding the subway, that one of the things that, you know, in Star Trek they have these transporters. They got it wrong in Star Trek because they always had these pattern buffers. See, this would be a sufficient amount to address every molecule in your body or, in fact, every atom in your body. So, if you had an IPv address for every molecule or atom in your body and you transmitted just the location and type of atom it was, you could clearly, as long as you had a streaming algorithm, you could clearly implement the transport. In fact, I was thinking even further that, if it lost a few packets, I wouldn't mind, you know? [Laughter.] So, in IPv4, there are basically 4 billion, and so, visualization of everything is hard to see, even with IPv4. Now, in addition to the issues of sort of looking at all possible Internet addresses, each machine has 216 or about 65,000 ports. So, looking at ports is an interesting thing. 65,000 is something that is visualizable. So, looking at ports is an interesting thing from the point of view that there are some standard ports, but attacks—intrusion attacks— often attempt to go after ports that are not properly closed off or not properly unused. So, one thing that can happen is that ports can get scanned to see if something is misallowed with those things. So, looking at attacks that scan ports and seeing if you can do that visually is interesting. I put some popular ports down. FTP is 21, simple-mail is 25, HTTP is typically 80, it is also 8080. Top three servers, or mail servers are 110. NFS is 2049. One of the things that I thought was interesting is that even Direct TV and AOL have standard ports that they use. 

VISUALIZATION OF INTERNET PACKET HEADERS 270 So, in order to analyze the traffic data, you have to basically capture the traffic data. This is done—at least in our case—with something called sniffers. I think Bill had a less provocative name for such things. Anyway, these things sit outside the firewall in our case. We have implemented a couple of these things and I will show you a little bit about this. The idea is that the program will capture something like TCP Delta's program that captures the header information of all data flowing through a given point. Ours is implemented in such a way that all traffic in and out of George Mason University is routed through—not routed through, but also sent to this machine. The sniffer is actually a covert machine. It is not visible on anybody's system. You can't tell that it is there, basically. So, our network at George Mason University is a Class B network, and just to give you some calibration, the data in and out, the traffic in and out of the Class B network, which is a sort of medium-sized network, is in the multi- terabyte range daily. We can collect, when we do, on the order of 35 to 45 megabits of header information per minute, something like 50 to 60 gigabytes of header information per day. Even within our relatively small statistics subnet we have eight faculty members that sit on statistics subnet, plus a secretary or two. Last week, just in getting ready for this, we were collecting a little data just to see what kind of things were going on. Last week was final exam week, so we didn't have as much activity as we usually do. Usually only the faculty that are giving final exams are around. Even in this relatively small subnet, we were getting 65,000 to 155,000 packets per hour. 

VISUALIZATION OF INTERNET PACKET HEADERS 271 So, some observations. With the scale of traffic, even though things are usually thought of, in computer terms, as being discrete, for many purposes, they are essentially continuous. If I tried to look at all IP addresses, somehow I couldn't do that in any reasonable discrete form. If I tried to do graph theory associated with that, it would be tough. Clearly, the storage of all header data is not possible. We have a terabyte storage capability and that would run out in not too long a time. So, streaming algorithms and methods are essentially, and essentially, recursive algorithms are of great interest. I think, in general, for streaming data, that is something we would like to make a comment on. The good news is that not every computer system talks to every other computer system. So, the networks are relatively sparse. Even so, the visualization methods typically are stretched to the limit. Of course, the nature of traffic changes during the day. Within George Mason University, we have very little traffic between about 3:00 and 5:00 in the morning, comparatively little, very heavy traffic up to about 10:00 o'clock when people are sorting out, I guess, their e-mail. Traffic tapers off a little bit. George Mason has a lot of evening students, so traffic builds up again relatively heavily in the evening. As students go to their dorms and surface naughty Web sites, we get a lot of traffic after 10:00 o'clock. By the way, I worked for a while at the Bureau of Labor Statistics. The Bureau of Labor Statistics has a filter that cuts off any IP that seems to have nasty stuff on it. One of the discussions, when I was working at BLS, was that the Washington Post Web site was cut off because it apparently had offensive material in it. My friend, Don Faxon, who is working with me on this project, went to the Isle of Crete during the summer. My wife was in the hospital and I couldn't go to give a talk, so I sent him to give a talk. He started calling this project Knossos. I don't know why, because that is a city in the Isle of Crete. I was not fond of this name. 

VISUALIZATION OF INTERNET PACKET HEADERS 272 I thought, as long as you are going with Greek mythology, certainly Cerberus would probably be a good name for this. Cerberus is the three-headed dog that guards the gates of hell. The comment is, after all, they do call it a firewall, and the question is, which side of hell is on our gateway—is it on our side or is it on the outside? I thought maybe a better name is to call it St. Peter because he guards the gates of heaven. But for a streaming data set, this is no good, because in theory, St. Peter keeps the records forever. So, you are potentially in trouble. He stores too much data. So, I decided it would be Project Santa Claus, keeping with the season. He wants to find out who is naughty or nice, but he discards the data after a year, so he is clearly a streaming data analyst. 

VISUALIZATION OF INTERNET PACKET HEADERS 273 So, let me toggle over to show you a little bit about this. This is just a little bit of stuff that we have put together. It has some interesting things in it. You can go to a glossary and you can look up any of these acronyms that you can imagine what they might actually mean. You can do things like look up port numbers. So, if you are interested in finding out which port is which, you can do such things. You can look up route zones. So, if you want to know what a suffix is and where that place is, you can do that. One that has been advertised a lot lately is “tv.” So, if you want to know where “tv” actually is, it is in Tuvalu, wherever that is. So, you can do some things like that. We have two stations, Ariadne, which is the sniffer, which sits outside the firewall, has roughly a terabyte of storage capability, and it runs the TCP dump and other kinds of stuff. You can find out some stuff about that, if you are interested. Theseus is the analysis station which sits in side of our lab. By the way, as Bill pointed out, these are sort of sensitive issues. The content of what is being looked at is an interesting privacy issue. There is an assumption of privacy in general on the Internet, although it is not so clear that that is maintained. We could, in principle, track the actual stuff that people are downloading and certainly the IP addresses that they are downloading. One of the interesting things in the state of Virginia is that faculty are not allowed to look at X-rated Web sites, but students are, and so are secretaries. It is against the law for me to look at anything bad, unless I have a project like this. Steve Marin was asking me why I do this instead of using somebody else's database. Let me show you a little bit of sort of what data looks like. So, here is some data that comes out of—this is what Amy would call sort of Level 2 data, I guess. This is sort of semi-raw data that comes out of—that is slightly processed coming out of something like TCP dump. We can look at substructure data. One variable of interest is the source manufacturer, and source serial number. So, we can track things to specific machines. This is the time stamp that is put on by our machine, when the packet comes through it. So, we do have a time stamp associated with it. As somebody pointed out the other day, no talk of Ed Wegman's would be complete without some kind of graphic parallel coordinate display. So, here is a scatterplot matrix of things that we might be interested in. We could increase the size of the pixels. One of the interesting things is to go to the parallel coordinate display. Source manufacturer is an interesting thing. If we don't know the MAC number of the machine, it continues to record the IP address. So, these things over here on the right-hand side are things where we couldn't identify the MAC number of the machine, but those are things that have an IP address. Just for purposes of discussion, we can get rid of those things, and we see a couple of things that are of interest. AUDIENCE: Ed, could you just be clear about that? Do you mean you don't have a MAC number? MR. WEGMAN: We don't have the MAC number for it. We have the IP but we don't have the MAC. So, here are a couple of things that are of interest. So, the thing I just colored in green, let me do one other quick little thing here. We can drag this down. So, the thing I just colored in green, you will notice, is one machine source manufacturer and one source serial number. We only have one machine and one serial number. That, in fact, is our router. What we have here is, this is delta 

VISUALIZATION OF INTERNET PACKET HEADERS 274 time, this is time. The frame is essentially, in an IP there is a sequence number. So, what is happening is there is a lot of data coming in. There is a batch of data coming in here, and it is coming in through this time frame. So, these are the sequence numbers that are associated with the data that is coming in. Here is another probably Web page that is coming in, and here are the frame numbers associated with that. Here is a third item, and the frame numbers that are associated with that. So, those are big files. The red thing also has only one IP, one source manufacturer number, and one source serial number. So, that turns out to be our Web server. So, sad to say, we get less traffic. People aren't interested in us as much as they could be, I guess, but occasionally we get some hits. Just to give some other interesting things, we have a lot of Dell machines and we have a number of Gateway machines. So, we can identify those. This is all stuff that is internal to our subnet. So, that is a quick tour of something that you could do. I am going to exit Santa and go back to the PowerPoint. So, I wanted to say a word on recursive algorithms, because recursive algorithms are the algorithms that you basically need to deal with streaming data. Clearly, things like means and moments can be formulated recursively. The idea with recursive algorithms is that you don't want to store data any longer than you have to. So, you want to keep whatever quantity you have and do an update. So, things like counts, means, variances, covariances, other moments, are easily computed recursively. Probably less well known is that there are recursive forms of kernel density 

VISUALIZATION OF INTERNET PACKET HEADERS 275 estimators. So, for the people at Rice University who think that probability density estimation was invented, there are some recursive forms of kernel estimators. This is one and this is another one. These have essentially the same properties as ordinary kernel density estimators, the same kinds of convergence rates. They can be extended to multivariate settings as well. So, if you are interested in streaming data and collecting density information, you can do that this way. I thought Daryl Pregibon brought up an interesting idea yesterday, which is the idea of exponentially weighted averages. If you have something that is sort of an exponentially weighted average, that takes some data and creates an object, then you can do this recursively, and you can do this with almost any old object. So, if you have a starting object and you have some data that updates it in the proper way, you can do streaming data with this as well. 

VISUALIZATION OF INTERNET PACKET HEADERS 276 I just wanted to give you a couple of references. This paper, I told someone the other day of the rusty staple principle which is, if the staples on your reprint are rusty, it is time to cycle the research, because clearly everybody has forgotten about it. I did some work with Ian Davies in the late 1970s that did this stuff on recursive density estimation, and gave exact rates of almost—Carey Priebe, who is in the audience here, did the stuff on adaptive mixtures, and adaptive mixtures has a formulation that is a recursive formulation as well. I had a student a few years ago, Mark Sullivan, who did stuff on correlation and spectral estimators in a recursive fashion, so, computationally efficient stuff. Some of the things we are planning to do is some waterfall graphics, where we scan ports and IP addresses. One of the things we are planning to do is transient geographic mapping. 

VISUALIZATION OF INTERNET PACKET HEADERS 277 We are interested in both high-intensity traffic being persistent and low-intensity traffic being persistent. The idea is that people who are trying to intrude often do it very, very quickly. So, what we would be interested in doing is looking at a geographic map that had the locations of IPs that are very short-lived. We, for example, at George Mason have had a lot of trouble with people in mainland China probing our systems. There are just a couple of graphics that I will hurry through. Again, as someone pointed out, one has to have a parallel coordinate plot. 

VISUALIZATION OF INTERNET PACKET HEADERS 278 So, some additional references—and a lot is due to Dave Marchette, who is also in the audience, who wrote this wonderful book on computer intrusion detection and network monitoring—Stevens and this Leiden-Wilensky book, are both useful in terms of understanding TCP/IP addressing and so on. Some of the pictures that I just hurried through were from Solka, Marchette, Brad Wallett, all three of whom were my students. Just for acknowledgment, our work here and the work on surveillance is supported by a critical infrastructure grant from the Air Force. I also work on the DARPA ISP program with Carey Priebe as the principal investigator and, as I said, Dave Marchette plays a key role. So, that is it. MS. MARTINEZ: While we are switching, we have time for one question. 

VISUALIZATION OF INTERNET PACKET HEADERS 279 AUDIENCE: Ed, it doesn't strike me—looking at these packets, it doesn't strike me as a visualization problem. So, I am sort of curious why you framed it that way. MR. WEGMAN: I am not sure why you don't think it is that. So, I guess I am curious the other way. I guess I see a lot of things as visualization problems. One of the issues that we are particularly interested in is having a monitoring system that can detect, very, very quickly that we are getting intrusions into the system. We want to be able to cut off things quite rapidly, I guess. I am not sure that is an adequate address any more than my answer to Steve Marin. I guess I am one of those guys who likes to do it myself.