Network security tools

The Art of Port Scanning

2008-09-01T03:11:00.000-07:00

This paper details many of the techniques used to determine what ports (or similar protocol abstraction) of a host are listening for connections. These ports represent potential communication channels. Mapping their existence facilitates the exchange of information with the host, and thus it is quite useful for anyone wishing to explore their networked environment, including hackers. Despite what you have heard from the media, the Internet is NOT all about TCP port 80. Anyone who relies exclusively on the WWW for information gathering is likely to gain the same level of proficiency as your average AOLer, who does the same. This paper is also meant to serve as an introduction to and ancillary documentation for a coding project I have been working on. It is a full featured, robust port scanner which (I hope) solves some of the problems I have encountered when dealing with other scanners and when working to scan massive networks. The tool, nmap, supports the following:

The freely distributable source code is available at http://nmap.org/

Introduction

Scanning, as a method for discovering exploitable communication channels, has been around for ages. The idea is to probe as many listeners as possible, and keep track of the ones that are receptive or useful to your particular need. Much of the field of advertising is based on this paradigm, and the "to current resident" brute force style of bulk mail is an almost perfect parallel to what we will discuss. Just stick a message in every mailbox and wait for the responses to trickle back.

Scanning entered the h/p world along with the phone systems. Here we have this tremendous global telecommunications network, all reachable through codes on our telephone. Millions of numbers are reachable locally, yet we may only be interested in 0.5% of these numbers, perhaps those that answer with a carrier.

The logical solution to finding those numbers that interest us is to try them all. Thus the field of "wardialing" arose. Excellent programs like Toneloc were developed to facilitate the probing of entire exchanges and more. The basic idea is simple. If you dial a number and your modem gives you a CONNECT, you record it. Otherwise the computer hangs up and tirelessly dials the next one.

While wardialing is still useful, we are now finding that many of the computers we wish to communicate with are connected through networks such as the Internet rather than analog phone dialups. Scanning these machines involves the same brute force technique. We send a blizzard of packets for various protocols, and we deduce which services are listening from the responses we receive (or don't receive).

Techniques

Over time, a number of techniques have been developed for surveying the protocols and ports on which a target machine is listening. They all offer different benefits and problems. Here is a line up of the most common:

TCP connect() scanning : This is the most basic form of TCP scanning. The connect() system call provided by your operating system is used to open a connection to every interesting port on the machine. If the port is listening, connect() will succeed, otherwise the port isn't reachable. One strong advantage to this technique is that you don't need any special privileges. Any user on most UNIX boxes is free to use this call. Another advantage is speed. While making a separate connect() call for every targeted port in a linear fashion would take ages over a slow connection, you can hasten the scan by using many sockets in parallel. Using non-blocking I/O allows you to set a low time-out period and watch all the sockets at once. This is the fastest scanning method supported by nmap, and is available with the -t (TCP) option. The big downside is that this sort of scan is easily detectable and filterable. The target hosts logs will show a bunch of connection and error messages for the services which take the connection and then have it immediately shutdown.
TCP SYN scanning : This technique is often referred to as "half-open" scanning, because you don't open a full TCP connection. You send a SYN packet, as if you are going to open a real connection and wait for a response. A SYN|ACK indicates the port is listening. A RST is indicative of a non- listener. If a SYN|ACK is received, you immediately send a RST to tear down the connection (actually the kernel does this for us). The primary advantage to this scanning technique is that fewer sites will log it. Unfortunately you need root privileges to build these custom SYN packets. SYN scanning is the -s option of nmap.
TCP FIN scanning : There are times when even SYN scanning isn't clandestine enough. Some firewalls and packet filters watch for SYNs to restricted ports, and programs like synlogger and Courtney are available to detect these scans. FIN packets, on the other hand, may be able to pass through unmolested. This scanning technique was featured in detail by Uriel Maimon in Phrack 49, article 15. The idea is that closed ports tend to reply to your FIN packet with the proper RST. Open ports, on the other hand, tend to ignore the packet in question. As Alan Cox has pointed out, this is required TCP behavior. However, some systems (notably Micro$oft boxes), are broken in this regard. They send RST's regardless of the port state, and thus they aren't vulnerable to this type of scan. It works well on most other systems I've tried. Actually, it is often useful to discriminate between a *NIX and NT box, and this can be used to do that. FIN scanning is the -U (Uriel) option of nmap.
Fragmentation scanning : This is not a new scanning method in and of itself, but a modification of other techniques. Instead of just sending the probe packet, you break it into a couple of small IP fragments. You are splitting up the TCP header over several packets to make it harder for packet filters and so forth to detect what you are doing. Be careful with this! Some programs have trouble handling these tiny packets. My favorite sniffer segmentation faulted immediately upon receiving the first 36-byte fragment. After that comes a 24 byte one! While this method won't get by packet filters and firewalls that queue all IP fragments (like the CONFIG_IP_ALWAYS_DEFRAG option in Linux), a lot of networks can't afford the performance hit this causes. This feature is rather unique to scanners (at least I haven't seen any others that do this). Thanks to daemon9 for suggesting it. The -f instructs the specified SYN or FIN scan to use tiny fragmented packets.
TCP reverse ident scanning : As noted by Dave Goldsmith in a 1996 Bugtraq post, the ident protocol (rfc1413) allows for the disclosure of the username of the owner of any process connected via TCP, even if that process didn't initiate the connection. So you can, for example, connect to the http port and then use identd to find out whether the server is running as root. This can only be done with a full TCP connection to the target port (i.e. the -t option). nmap's -i option queries identd for the owner of all listen()ing ports.
FTP bounce attack : An interesting "feature" of the ftp protocol (RFC 959) is support for "proxy" ftp connections. In other words, I should be able to connect from evil.com to the FTP server-PI (protocol interpreter) of target.com to establish the control communication connection. Then I should be able to request that the server-PI initiate an active server-DTP (data transfer process) to send a file ANYWHERE on the internet! Presumably to a User-DTP, although the RFC specifically states that asking one server to send a file to another is OK. Now this may have worked well in 1985 when the RFC was just written. But nowadays, we can't have people hijacking ftp servers and requesting that data be spit out to arbitrary points on the internet. As *Hobbit* wrote back in 1995, this protocol flaw "can be used to post virtually untraceable mail and news, hammer on servers at various sites, fill up disks, try to hop firewalls, and generally be annoying and hard to track down at the same time." What we will exploit this for is to (surprise, surprise) scan TCP ports from a "proxy" ftp server. Thus you could connect to an ftp server behind a firewall, and then scan ports that are more likely to be blocked (139 is a good one). If the ftp server allows reading from and writing to a directory (such as /incoming), you can send arbitrary data to ports that you do find open.
For port scanning, our technique is to use the PORT command to declare that our passive "User-DTP" is listening on the target box at a certain port number. Then we try to LIST the current directory, and the result is sent over the Server-DTP channel. If our target host is listening on the specified port, the transfer will be successful (generating a 150 and a 226 response). Otherwise we will get "425 Can't build data connection: Connection refused." Then we issue another PORT command to try the next port on the target host. The advantages to this approach are obvious (harder to trace, potential to bypass firewalls). The main disadvantages are that it is slow, and that some FTP servers have finally got a clue and disabled the proxy "feature". For what it is worth, here is a list of banners from sites where it does/doesn't work:
*Bounce attacks worked:*
```
220 xxxxxxx.com FTP server (Version wu-2.4(3) Wed Dec 14 ...) ready.
220 xxx.xxx.xxx.edu FTP server ready.
220 xx.Telcom.xxxx.EDU FTP server (Version wu-2.4(3) Tue Jun 11 ...) ready.
220 lem FTP server (SunOS 4.1) ready.
220 xxx.xxx.es FTP server (Version wu-2.4(11) Sat Apr 27 ...) ready.
220 elios FTP server (SunOS 4.1) ready
```
*Bounce attack failed:*
```
220 wcarchive.cdrom.com FTP server (Version DG-2.0.39 Sun May 4 ...) ready.
220 xxx.xx.xxxxx.EDU Version wu-2.4.2-academ[BETA-12](1) Fri Feb 7
220 ftp Microsoft FTP Service (Version 3.0).
220 xxx FTP server (Version wu-2.4.2-academ[BETA-11](1) Tue Sep 3 ...) ready.
220 xxx.unc.edu FTP server (Version wu-2.4.2-academ[BETA-13](6) ...) ready.
```
The 'x's are partly there to protect those guilty of running a flawed server, but mostly just to make the lines fit in 80 columns. Same thing with the ellipse points. The bounce attack is available with the -b option of nmap. proxy_server can be specified in standard URL format, username:password@server:port , with everything but server being optional.
UDP ICMP port unreachable scanning : This scanning method varies from the above in that we are using the UDP protocol instead of TCP. While this protocol is simpler, scanning it is actually significantly more difficult. This is because open ports don't have to send an acknowledgement in response to our probe, and closed ports aren't even required to send an error packet. Fortunately, most hosts do send an ICMP_PORT_UNREACH error when you send a packet to a closed UDP port. Thus you can find out if a port is NOT open, and by exclusion determine which ports which are. Neither UDP packets, nor the ICMP errors are guaranteed to arrive, so UDP scanners of this sort must also implement retransmission of packets that appear to be lost (or you will get a bunch of false positives). Also, this scanning technique is slow because of compensation for machines that took RFC 1812 section 4.3.2.8 to heart and limit ICMP error message rate. For example, the Linux kernel (in net/ipv4/icmp.h) limits destination unreachable message generation to 80 per 4 seconds, with a 1/4 second penalty if that is exceeded. At some point I will add a better algorithm to nmap for detecting this. Also, you will need to be root for access to the raw ICMP socket necessary for reading the port unreachable. The -u (UDP) option of nmap implements this scanning method for root users.
Some people think UDP scanning is lame and pointless. I usually remind them of the recent Solaris rcpbind hole. Rpcbind can be found hiding on an undocumented UDP port somewhere above 32770. So it doesn't matter that 111 is blocked by the firewall. But can you find which of the more than 30,000 high ports it is listening on? With a UDP scanner you can!
UDP recvfrom() and write() scanning : While non-root users can't read port unreachable errors directly, Linux is cool enough to inform the user indirectly when they have been received. For example a second write() call to a closed port will usually fail. A lot of scanners such as netcat and Pluvius' pscan.c does this. I have also noticed that recvfrom() on non-blocking UDP sockets usually return EAGAIN ("Try Again", errno 13) if the ICMP error hasn't been received, and ECONNREFUSED ("Connection refused", errno 111) if it has. This is the technique used for determining open ports when non-root users use -u (UDP). Root users can also use the -l (lamer UDP scan) options to force this, but it is a really dumb idea.
ICMP echo scanning : This isn't really port scanning, since ICMP doesn't have a port abstraction. But it is sometimes useful to determine what hosts in a network are up by pinging them all. the -P option does this. ICMP scanning is now in parallel, so it can be quite fast. To speed things up even more, you can increase the number of pings in parallel with the '-L ' option. It can also be helpful to tweek the ping timeout value with '-T '. nmap supports a host/bitmask notation to make this sort of thing easier. For example 'nmap -P cert.org/24 152.148.0.0/16' would scan CERT's class C network and whatever class B entity 152.148.* represents. Host/26 is useful for 6-bit subnets within an organization. Nmap now also offers a more powerful form. You can now do things like '150.12,17,71-79.7.*' and it will do what you expect. For each of the four values, you can either put a single number, a range (with '-'), a comma-separated list of numbers and ranges, or a '*' which is just a short cut for 0-255. By default, likely network/broadcast addresses like .0 and .255 are not scanned, but the '-A' option allows you to do this if you wish.

Features

Prior to writing nmap, I spent a lot of time with other scanners exploring the Internet and various private networks (note the avoidance of the "intranet" buzzword). I have used many of the top scanners available today, including strobe by Julian Assange, netcat by *Hobbit*, stcp by Uriel Maimon, pscan by Pluvius, ident-scan by Dave Goldsmith, and the SATAN tcp/udp scanners by Wietse Venema. These are all excellent scanners! In fact, I ended up hacking most of them to support the best features of the others. Finally I decided to write a whole new scanner, rather than rely on hacked versions of a dozen different scanners in my /usr/local/sbin. While I wrote all the code, nmap uses a lot of good ideas from its predecessors. I also incorporated some new stuff like fragmentation scanning and options that were on my "wish list" for other scanners. Here are some of the (IMHO) useful features of nmap:

dynamic delay time calculations: Some scanners require that you supply a delay time between sending packets. Well how should I know what to use? Sure, I can ping them, but that is a pain, and plus the response time of many hosts changes dramatically when they are being flooded with requests. nmap tries to determine the best delay time for you. It also tries to keep track of packet retransmissions, etc. so that it can modify this delay time during the course of the scan. For root users, the primary technique for finding an initial delay is to time the internal "ping" function. For non-root users, it times an attempted connect() to a closed port on the target. It can also pick a reasonable default value. Again, people who want to specify a delay themselves can do so with -w (wait), but you shouldn't have to.
retransmission: Some scanners just send out all the query packets, and collect the responses. But this can lead to false positives or negatives in the case where packets are dropped. This is especially important for "negative" style scans like UDP and FIN, where what you are looking for is a port that does NOT respond. In most cases, nmap implements a configurable number of retransmissions for ports that don't respond.
parallel port scanning: Some scanners simply scan ports linearly, one at a time, until they do all 65535. This actually works for TCP on a very fast local network, but the speed of this is not at all acceptable on a wide area network like the Internet. nmap uses non-blocking i/o and parallel scanning in all TCP and UDP modes. The number of scans in parallel is configurable with the -M (Max sockets) option. On a very fast network you will actually decrease performance if you do more than 18 or so. On slow networks, high values increase performance dramatically.
Flexible port specification: I don't always want to just scan all 65535 ports. Also, the scanners which only allow you to scan ports 1 - N sometimes fall short of my need. The -p option allows you to specify an arbitrary number of ports and ranges for scanning. For example, '-p 21-25,80,113, 60000-' does what you would expect (a trailing hyphen means up to 65536, a leading hyphen means 1 through). You can also use the -F (fast) option, which scans all the ports registered in your /etc/services (a la strobe).
Flexible target specification: I often want to scan more then one host, and I certainly don't want to list every single host on a large network to scan. Everything that isn't an option (or option argument) in nmap is treated as a target host. As mentioned before, you can optionally append /mask to a hostname or IP address in order to scan all hosts with the same initial bits of the 32 bit IP address. You can use the same powerful syntax as the port specifications to specify targets like '150.12.17.71-79.7.*'. '*' is just a shortcut for 0-255, remember to escape it from your shell if used.
detection of down hosts: Some scanners allow you to scan large networks, but they waste a huge amount of time scanning 65535 ports of a dead host! By default, nmap pings each host to make sure it is up before wasting time on it. It also does thin in parallel, to speed things up. You can change the parrallel ping lookahead with '-L' and the ping timeout with '-T'. You can turn pinging off completely with the '-D' command line option. This is useful for scanning networks like microsoft.com where ICMP echo requests can't get through. Nmap is also capable of bailing on hosts that seem down based on strange port scanning errors. It is also meant to be tolerant of people who accidentally scan network addresses, broadcast addresses, etc.
detection of your IP address: For some reason, a lot of scanners ask you to type in your IP address as one of the parameters. Jeez, I don't want to have to 'ifconfig' and figure out my current address every time I scan. Of course, this is better then the scanners I've seen which require recompilation every time you change your address! nmap first tries to detect your address during the ping stage. It uses the address that the echo response is received on, as that is the interface it should almost always be routed through. If it can't do this (like if you don't have host pinging enabled), nmap tries to detect your primary interface and uses that address. You can also use -S to specify it directly, but you shouldn't have to (unless you want to make it look like someone ELSE is SYN or FIN scanning a host.

Some other, more minor options:

 -v (verbose): This is highly recommended for interactive use.  Among other
useful messages, you will see ports come up as they are found, rather than
having to wait for the sorted summary list.

-r (randomize): This will randomize the order in which the target host's
ports are scanned.

-q (quash argv): This changes argv[0] to FAKE_ARGV ("pine" by default).
It also eliminates all other arguments, so you won't look too suspicious in
'w' or 'ps' listings.

-h for an options summary.

-R show and resolve all hosts, even down ones.

Also look for http://nmap.org/, which is the web site I plan to put future versions and more information on. In fact, you would be well advised to check there right now. (If that isn't where you are reading this).

Example Usage

To launch a stealth scan of the entire class 'B' networks 166.66.0.0 and 166.67.0.0 for the popularly exploitable imapd daemon:

# nmap -Up 143 166.66.0.0/16 166.67.0.0/16

To do a standard tcp scan on the reserved ports of host :

> nmap target

To check the class 'C' network on which warez.com sits for popular services (via fragmented SIN scan):

# nmap -fsp 21,22,23,25,80,110 warez.com/24

To scan the same network for all the services in your /etc/services via (very fast) tcp scan:

> nmap -F warez.com/24

To scan secret.pathetic.net using the ftp bounce attack off of ftp.pathetic.net:

> nmap -Db ftp.pathetic.net secret.pathetic.net

To find hosts that are up in the the adjacent class C's 193.14.12, .13, .14, .15, ... , .30:

> nmap -P '193.14.[12-30].*'

If you don't want to have to quote it to avoid shell interpretation, this does the same thing:

> nmap -P 193.14.12-30.0-255

Compendium of Best Papers

2008-08-28T02:47:00.000-07:00

Compendium of Best Papers

Over the past decade, the Program Committees from many of the USENIX conferences and workshops have given out Best Paper, Best Student Paper, and Best Presentation awards. For a paper to qualify for the Best Student Paper award, a student must be the lead author. Following is a list of these awards, with links to the papers. Note: You do not need to be a USENIX member to access the papers in this compendium.

2008 | 2007 | 2006 | 2005 | 2004 | 2003 | 2002 | 2001 | 2000 | 1999 | 1998 | 1997 | 1996 | 1995 | 1994 | 1993 | 1992 | 1991 | 1990

2008

USENIX Security '08
Best Paper:
Highly Predictive Blacklisting
Jian Zhang and Phillip Porras, SRI International; Johannes Ullrich, SANS Institute

Best Student Paper:
Lest We Remember: Cold Boot Attacks on Encryption Keys
J. Alex Halderman, Princeton University; Seth D. Schoen, Electronic Frontier Foundation; Nadia Heninger and William Clarkson, Princeton University; William Paul, Wind River Systems; Joseph A. Calandrino and Ariel J. Feldman, Princeton University; Jacob Appelbaum; Edward W. Felten, Princeton University

USENIX '08
Best Paper:
Decoupling Dynamic Program Analysis from Execution in Virtual Environments
Jim Chow, Tal Garfinkel, and Peter M. Chen, VMware

Best Student Paper:
Vx32: Lightweight User-level Sandboxing on the x86
Bryan Ford and Russ Cox, Massachusetts Institute of Technology

NSDI '08
Best Paper:
Remus: High Availability via Asynchronous Virtual Machine Replication
Brendan Cully, Geoffrey Lefebvre, Dutch Meyer, Mike Feeley, and Norm Hutchinson, University of British Columbia; Andrew Warfield, University of British Columbia and Citrix Systems, Inc.

Best Paper:
Consensus Routing: The Internet as a Distributed System
John P. John, Ethan Katz-Bassett, Arvind Krishnamurthy, and Thomas Anderson, University of Washington; Arun Venkataramani, University of Massachusetts Amherst

LEET '08
Best Paper:
Designing and Implementing Malicious Hardware (PDF) or read in HTML
Samuel T. King, Joseph Tucek, Anthony Cozzie, Chris Grier, Weihang Jiang, and Yuanyuan Zhou, University of Illinois at Urbana-Champaign

FAST '08
Best Paper:
Portably Solving File TOCTTOU Races with Hardness Amplification
Dan Tsafrir, IBM T.J. Watson Research Center; Tomer Hertz, Microsoft Research; David Wagner, University of California, Berkeley; Dilma Da Silva, IBM T.J. Watson Research Center

Best Student Paper:
An Analysis of Data Corruption in the Storage Stack
Lakshmi N. Bairavasundaram, University of Wisconsin, Madison; Garth Goodson, Network Appliance Inc.; Bianca Schroeder, University of Toronto; Andrea C. Arpaci-Dusseau and Remzi H. Arpaci-Dusseau, University of Wisconsin, Madison

2007

LISA '07
Best Paper:
Application Buffer-Cache Management for Performance: Running the World's Largest MRTG
David Plonka, Archit Gupta, and Dale Carder, University of Wisconsin Madison

Best Paper:
PoDIM: A Language for High-Level Configuration Management
Thomas Delaet and Wouter Joosen, Katholieke Universiteit Leuven, Belgium

16th USENIX Security Symposium
Best Paper:
Towards Automatic Discovery of Deviations in Binary Implementations with Applications to Error Detection and Fingerprint Generation
David Brumley, Juan Caballero, Zhenkai Liang, James Newsome, and Dawn Song, Carnegie Mellon University

Best Student Paper:
Keep Your Enemies Close: Distance Bounding Against Smartcard Relay Attacks
Saar Drimer and Steven J. Murdoch, Computer Laboratory, University of Cambridge

USENIX '07
Best Paper:
Hyperion: High Volume Stream Archival for Retrospective Querying
Peter Desnoyers and Prashant Shenoy, University of Massachusetts Amherst

Best Paper:
SafeStore: A Durable and Practical Storage System
Ramakrishna Kotla, Lorenzo Alvisi, and Mike Dahlin, The University of Texas at Austin

NSDI '07
Best Paper:
Life, Death, and the Critical Transition: Finding Liveness Bugs in Systems Code
Charles Killian, James W. Anderson, Ranjit Jhala, and Amin Vahdat, University of California, San Diego

Best Student Paper:
Do Incentives Build Robustness in BitTorrent?
Michael Piatek, Tomas Isdal, Thomas Anderson, and Arvind Krishnamurthy, University of Washington; Arun Venkataramani, University of Massachusetts Amherst

FAST '07
Best Paper:
Disk Failures in the Real World: What Does an MTTF of 1,000,000 Hours Mean to You?
Bianca Schroeder and Garth A. Gibson, Carnegie Mellon University

Best Paper:
TFS: A Transparent File System for Contributory Storage
James Cipar, Mark D. Corner, and Emery D. Berger, University of Massachusetts Amherst

2006

LISA '06
Best Paper:
A Platform for RFID Security and Privacy Administration
Melanie R. Rieback, Vrije Universiteit Amsterdam; Georgi N. Gaydadjiev, Delft University of Technology; Bruno Crispo, Rutger F.H. Hofman, and Andrew S. Tanenbaum, Vrije Universiteit Amsterdam

Honorable Mention:
A Forensic Analysis of a Distributed Two-Stage Web-Based Spam Attack
Daniel V. Klein, LoneWolf Systems

OSDI '06
Best Paper:
Rethink the Sync
Edmund B. Nightingale, Kaushik Veeraraghavan, Peter M. Chen, and Jason Flinn, University of Michigan

Best Paper:
Bigtable: A Distributed Storage System for Structured Data
Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber, Google, Inc.

15th USENIX Security Symposium
Best Paper:
Evaluating SFI for a CISC Architecture
Stephen McCamant, Massachusetts Institute of Technology; Greg Morrisett, Harvard University

Best Student Paper:
Keyboards and Covert Channels
Gaurav Shah, Andres Molina, and Matt Blaze, University of Pennsylvania

2006 USENIX Annual Technical Conference
Best Paper:
Optimizing Network Virtualization in Xen
Aravind Menon, EPFL; Alan L. Cox, Rice University; Willy Zwaenepoel, EPFL

Best Paper:
Replay Debugging for Distributed Applications
Dennis Geels, Gautam Altekar, Scott Shenker, and Ion Stoica, University of California, Berkeley

NSDI '06
Best Paper:
Experience with an Object Reputation System for Peer-to-Peer Filesharing
Kevin Walsh and Emin Gün Sirer, Cornell University

Best Paper:
Availability of Multi-Object Operations
Haifeng Yu, Intel Research Pittsburgh and Carnegie Mellon University; Phillip B. Gibbons, Intel Research Pittsburgh; Suman Nath, Microsoft Research

2005

FAST '05
Best Paper:
Ursa Minor: Versatile Cluster-based Storage
Michael Abd-El-Malek, William V. Courtright II, Chuck Cranor, Gregory R. Ganger, James Hendricks, Andrew J. Klosterman, Michael Mesnier, Manish Prasad, Brandon Salmon, Raja R. Sambasivan, Shafeeq Sinnamohideen, John D. Strunk, Eno Thereska, Matthew Wachs, and Jay J. Wylie, Carnegie Mellon University

Best Paper:
On Multidimensional Data and Modern Disks
Steven W. Schlosser, Intel Research Pittsburgh; Jiri Schindler, EMC Corporation; Stratos Papadomanolakis, Minglong Shao, Anastassia Ailamaki, Christos Faloutsos, and Gregory R. Ganger, Carnegie Mellon University

LISA '05
Best Paper:
Toward a Cost Model for System Administration
Alva L. Couch, Ning Wu, and Hengky Susanto, Tufts University

Best Student Paper:
Toward an Automated Vulnerability Comparison of Open Source IMAP Servers
Chaos Golubitsky, Carnegie Mellon University

Best Student Paper:
Reducing Downtime Due to System Maintenance and Upgrades
Shaya Potter and Jason Nieh, Columbia University

IMC 2005
Best Student Paper:
Measurement-based Characterization of a Collection of On-line Games
Chris Chambers and Wu-chang Feng, Portland State University; Sambit Sahu and Debanjan Saha, IBM Research

Security '05
Best Paper:
Mapping Internet Sensors with Probe Response Attacks
John Bethencourt, Jason Franklin, and Mary Vernon University of Wisconsin, Madison

Best Student Paper:
Security Analysis of a Cryptographically-Enabled RFID Device
Steve Bono, Matthew Green, and Adam Stubblefield, Johns Hopkins University; Ari Juels, RSA Laboratories; Avi Rubin, Johns Hopkins University; Michael Szydlo, RSA Laboratories

MobiSys '05
Best Paper:
Reincarnating PCs with Portable SoulPads
Ramón Cáceres, Casey Carter, Chandra Narayanaswami, and Mandayam Raghunath, IBM T.J. Watson Research Center

NSDI '05
Best Paper:
Detecting BGP Configuration Faults with Static Analysis
Nick Feamster and Hari Balakrishnan, MIT Computer Science and Artificial Intelligence Laboratory

Best Student Paper:
Botz-4-Sale: Surviving Organized DDoS Attacks That Mimic Flash Crowds
Srikanth Kandula and Dina Katabi, Massachusetts Institute of Technology; Matthias Jacob, Princeton University; Arthur Berger, Massachusetts Institute of Technology/Akamai

2005 USENIX Annual Technical Conference
General Track
Best Paper:
Debugging Operating Systems with Time-Traveling Virtual Machines
Samuel T. King, George W. Dunlap, and Peter M. Chen, University of Michigan

Best Student Paper:
Itanium—A System Implementor's Tale
Charles Gray, University of New South Wales; Matthew Chapman and Peter Chubb, University of New South Wales and National ICT Australia; David Mosberger-Tang, Hewlett-Packard Labs; Gernot Heiser, University of New South Wales and National ICT Australia

FREENIX Track
Best Paper:
USB/IP—A Peripheral Bus Extension for Device Sharing over IP Network
Takahiro Hirofuchi, Eiji Kawai, Kazutoshi Fujikawa, and Hideki Sunahara, Nara Institute of Science and Technology

2004

OSDI '04
Best Paper:
Recovering Device Drivers

Michael M. Swift, Muthukaruppan Annamalai, Brian N. Bershad, and Henry M. Levy, University of Washington

Best Paper:
Using Model Checking to Find Serious File System Errors

Junfeng Yang, Paul Twohey, and Dawson Engler, Stanford University; Madanlal Musuvathi, Microsoft Research

LISA '04
Best Paper:
Scalable Centralized Bayesian Spam Mitigation with Bogofilter

Jeremy Blosser and David Josephsen, VHA, Inc.

Security '04
Best Paper:
Understanding Data Lifetime via Whole System Simulation

Jim Chow, Ben Pfaff, Tal Garfinkel, Kevin Christopher, and Mendel Rosenblum, Stanford University

Best Student Paper:
Fairplay—A Secure Two-Party Computation System

Dahlia Malkhi and Noam Nisan, Hebrew University; Benny Pinkas, HP Labs; Yaron Sella, Hebrew University

2004 USENIX Annual Technical Conference

General Track Best Paper:
Handling Churn in a DHT

Sean Rhea and Dennis Geels, University of California, Berkeley; Timothy Roscoe, Intel Research, Berkeley; John Kubiatowicz, University of California, Berkeley

Best Paper:
Energy Efficient Prefetching and Caching

Athanasios E. Papathanasiou and Michael L. Scott, University of Rochester

FREENIX TrackBest Paper:
Wayback: A User-level Versioning File System for Linux

Brian Cornell, Peter A. Dinda, and Fabián E. Bustamante, Northwestern University

Best Student Paper:
Design and Implementation of Netdude, a Framework for Packet Trace Manipulation

Christian Kreibich, University of Cambridge, UK

VM '04
Best Paper:
Semantic Remote Attestation—A Virtual Machine Directed Approach to Trusted Computing

Vivek Haldar, Deepak Chandra, and Michael Franz, University of California, Irvine

FAST '04
Best Paper:
Row-Diagonal Parity for Double Disk Failure Correction

Peter Corbett, Bob English, Atul Goel, Tomislav Grcanac, Steven Kleiman, James Leong, and Sunitha Sankar, Network Appliance, Inc.

Best Student Paper:
Improving Storage System Availability with D-GRAID

Muthian Sivathanu, Vijayan Prabhakaran, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau, University of Wisconsin, Madison

Best Student Paper:
A Framework for Building Unobtrusive Disk Maintenance Applications

Eno Thereska, Jiri Schindler, John Bucy, Brandon Salmon, Christopher R. Lumb, and Gregory R. Ganger, Carnegie Mellon University NSDI '04
Best Paper:
Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks

Philip Levis, University of California, Berkeley, and Intel Research Berkeley; Neil Patel, University of California, Berkeley; David Culler, University of California, Berkeley, and Intel Research Berkeley; Scott Shenker, University of California, Berkeley, and ICSI

Best Student Paper:
Listen and Whisper: Security Mechanisms for BGP

Lakshminarayanan Subramanian, University of California, Berkeley; Volker Roth, Fraunhofer Institute, Germany; Ion Stoica, University of California, Berkeley; Scott Shenker, University of California, Berkeley, and ICSI; Randy H. Katz, University of California, Berkeley

2003 [back to top]

LISA '03
Award Paper:

STRIDER: A Black-box, State-based Approach to Change and Configuration Management and Support

Yi-Min Wang, Chad Verbowski, John Dunagan, Yu Chen, Helen J. Wang, Chun Yuan, and Zheng Zhang, Microsoft Research

Award Paper:

Distributed Tarpitting: Impeding Spam Across Multiple Servers

Tim Hunter, Paul Terry, and Alan Judge, eircom.net BSDCon '03
Best Paper:
Cryptographic Device Support for FreeBSD

Samuel J. Leffler, Errno Consulting

Best Student Paper:
Running BSD Kernels as User Processes by Partial Emulation and Rewriting of Machine Instructions

Hideki Eiraku and Yasushi Shinjo, University of Tsukuba 12th USENIX Security Symposium
Best Paper:
Remote Timing Attacks Are Practical

David Brumley and Dan Boneh, Stanford University

Best Student Paper:
Establishing the Genuinity of Remote Computer Systems

Rick Kennell and Leah H. Jamieson, Purdue University 2003 USENIX Annual Technical Conference

General Track

Award Paper:

Undo for Operators: Building an Undoable E-mail Store

Aaron B. Brown and David A. Patterson, University of California, Berkeley

Award Paper:

Operating System I/O Speculation: How Two Invocations Are Faster Than One

Keir Fraser, University of Cambridge Computer Laboratory; Fay Chang, Google Inc.

FREENIX TrackBest Paper:
StarFish: Highly Available Block Storage

Eran Gabber, Jeff Fellin, Michael Flaster, Fengrui Gu, Bruce Hillyer, Wee Teck Ng, Banu Özden, and Elizabeth Shriver, Lucent Technologies, Bell Labs

Best Student Paper:
Flexibility in ROM: A Stackable Open Source BIOS

Adam Agnew and Adam Sulmicki, University of Maryland at College Park; Ronald Minnich, Los Alamos National Labs; William Arbaugh, University of Maryland at College Park First International Conference on Mobile Systems, Applications, and Services
Best Paper:
Energy Aware Lossless Data Compression

Kenneth Barr and Krste Asanovic, Massachusetts Institute of Technology 2nd USENIX Conference on File and Storage Technologies
Best Paper:
Using MEMS-Based Storage in Disk Arrays

Mustafa Uysal and Arif Merchant, Hewlett-Packard Labs; Guillermo A. Alvarez, IBM Almaden Research Center

Best Student Paper:
Pond: The OceanStore Prototype

Sean Rhea, Patrick Eaton, Dennis Geels, Hakim Weatherspoon, Ben Zhao, and John Kubiatowicz, University of California, Berkeley 4th USENIX Symposium on Internet Technologies and Systems
Best Paper:
SkipNet: A Scalable Overlay Network with Practical Locality Properties

Nicholas J. A. Harvey, Microsoft Research and University of Washington; Michael B. Jones, Microsoft Research; Stefan Saroiu, University of Washington; Marvin Theimer and Alec Wolman, Microsoft Research

Best Student Paper:
Scriptroute: A Public Internet Measurement Facility

Neil Spring, David Wetherall, and Tom Anderson, University of Washington

2002 [back to top]

5th Symposium on Operating Systems Design and Implementation
Best Paper:
Memory Resource Management in VMware ESX Server

Carl A. Waldspurger, VMware, Inc.

Best Student Paper:
An Analysis of Internet Content Delivery Systems

Stefan Saroiu, Krishna P. Gummadi, Richard J. Dunn, Steven D. Gribble, and Henry M. Levy, University of Washington LISA '02: 16th Systems Administration Conference
Best Paper:
RTG: A Scalable SNMP Statistics Architecture for Service Providers

Robert Beverly, MIT Laboratory for Computer Science

Best Paper:
Work-Augmented Laziness with the Los Task Request System

Thomas Stepleton, Swarthmore College Computer Society 11th USENIX Security Symposium
Best Paper:
Security in Plan 9

Russ Cox, MIT LCS; Eric Grosse and Rob Pike, Bell Labs; Dave Presotto, Avaya Labs and Bell Labs; Sean Quinlan, Bell Labs

Best Student Paper:
Infranet: Circumventing Web Censorship and Surveillance

Nick Feamster, Magdalena Balazinska, Greg Harfst, Hari Balakrishnan, and David Karger, MIT 2nd Java Virtual Machine Research and Technology Symposium
Best Paper:
An Empirical Study of Method In-lining for a Java Just-in-Time Compiler

Toshio Suganuma, Toshiaki Yasue, and Toshio Nakatani, IBM Tokyo Research Laboratory

Best Student Paper:
Supporting Binary Compatibility with Static Compilation

Dachuan Yu, Zhong Shao, and Valery Trifonov, Yale University 2002 USENIX Annual Technical Conference

General Track Best Paper:
Structure and Performance of the Direct Access File System

Kostas Magoutis, Salimah Addetia, Alexandra Fedorova, and Margo I. Seltzer, Harvard University; Jeffrey S. Chase, Andrew J. Gallatin, Richard Kisley, and Rajiv G. Wickremesinghe, Duke University; and Eran Gabber, Lucent Technologies

Best Student Paper:
EtE: Passive End-to-End Internet Service Performance Monitoring

Yun Fu and Amin Vahdat, Duke University; Ludmila Cherkasova and Wenting Tang, Hewlett-Packard Laboratories

FREENIX Track

Best FREENIX Paper:

CPCMS: A Configuration Management System Based on Cryptographic Names

Jonathan S. Shapiro and John Vanderburgh, Johns Hopkins University

Best FREENIX Student Paper:

SWILL: A Simple Embedded Web Server Library

Sotiria Lampoudi and David M. Beazley, University of Chicago BSDCon '02
Best Paper:
Running "fsck" in the Background Marshall Kirk McKusick, Author and Consultant

Best Paper:
Design And Implementation of a Direct Access File System (DAFS) Kernel Server for FreeBSD

Kostas Magoutis, Division of Engineering and Applied Sciences, Harvard University Conference on File and Storage Technologies
Best Paper:
VENTI - A New Approach to Archival Data Storage Sean Quinlan and Sean Dorward, Bell Labs, Lucent Technologies

Best Student Paper:
Track-aligned Extents: Matching Access Patterns to Disk Drive Characteristics

Jiri Schindler, John Linwood Griffin, Christopher R. Lumb, Gregory R. Ganger, Carnegie Mellon University

2001 [back to top]

LISA 2001: 15th Systems Administration Conference
Best Theory Paper:

A Probabilistic Approach to Estimating Computer System Reliability

Robert Apthorpe, Excite@Home, Inc.

Best Applied Paper:

Lexis EXam Invigilation System

Mike Wyer and Susan Eisenbach, Imperial College 5th Annual Linux Showcase & Conference
Best Paper:
Design and implementation of a Linux SCSI target for storage area networks

Ashish Palekar, Trebia Networks Inc. and Narendran Ganapathy, Anshul Chadda, Robert D. Russell, InterOperability Laboratory 10th USENIX Security Symposium
Best Paper:
Inferring Internet Denial-of-Service Activity

David Moore, CAIDA; Geoffrey M. Voelker and Stefan Savage, University of California, San Diego

Best Student Paper:
The Dos and Don'ts of Client Authentication on the Web

Kevin Fu, Emil Sit, Kendra Smith, and Nick Feamster, MIT 2001 USENIX Annual Technical Conference
General Track

Best Paper (1):

Virtualizing I/O Devices on VMware Workstation's Hosted Virtual Machine Monitor

Jeremy Sugerman, Ganesh Venkitachalam, and Beng-Hong Lim, VMware Inc.

Best Paper (2):

A Toolkit for User-Level File Systems

David Mazières, NYU

FREENIX Track

Best FREENIX Paper:

Nickle: Language Principles and Pragmatics

Bart Massey, Portland State University, and Keith Packard, SuSE Inc.

Best FREENIX Student Paper:

MEF, Malicious Email Filter–A UNIX Mail Filter That Detects Malicious Windows Executables

Matthew G. Schultz and Eleazar Eskin, Columbia University; Erez Zadok, SUNY Stony Brook;

Manasi Bhattacharyya and Salvatore J. Stolfo, Columbia University Java Virtual Machine Research and Technology Symposium
Best Student Paper:
SableVM: A Research Framework for the Efficient Execution of Java Bytecode

Etienne M. Gagnon and Laurie J. Hendren, McGill University 3rd USENIX Symposium on Internet Technologies and Systems (USITS)
Best Paper:
Measurement and Analysis of a Streaming Media Workload

Maureen Chesire, Alec Wolman, Geoffrey M. Voelker, and Henry M. Levy 6th USENIX Conference on Object-Oriented Technologies and Systems
Best Student Paper: (1)

Content-Based Publish/Subscribe with Structural Reflection

Patrick Thomas Eugster and Rachid Guerraoui

Best Student Paper: (2)

Multi-Dispatch in the Java Virtual Machine: Design and Implementation

Christopher Dutchyn, Paul Lu, Duane Szafron, Steve Bromling, and Wade Holst

2000 [back to top]

7th USENIX Tcl/Tk Conference
Best Paper:
Rapid CORBA Server Development in Tcl: A Case Study

Jason Brazile, Andrej Vckovski

Best Student Paper:
Supporting Information Awareness Using Animated Widgets

Scott McCrickard, Q. Alex Zhao 2000 USENIX Annual Technical Conference
General Track Best Paper:
Scalable Content-aware Request Distribution in Cluster-based Network Servers

Mohit Aron, Darren Sanders, Peter Druschel, Willy Zwaenepoel

Best Student Paper (1):

Integrating a Command Shell Into a Web Browser

Robert Miller, Brad Myers

Best Student Paper (2):

Virtual Services: A New Abstraction for Server Consolidation

John Reumann, Ashish Mehra, Kang G. Shin, Dilip Kandlur

FREENIX Track

Best Freenix Paper:

An Operating System in Java for the Lego Mindstorms RCX Microcontroller

Pekka Nikander

Best Freenix Student Paper:

Protocol Independence Using the Sockets API

Craig Metz 3rd Large Installation System Administration of Windows NT Conference
Best Paper:
Kerberos Interoperability Issues

Paul B. Hill

Best Student Paper:
On Designing a Database for Integrated User Management: Pitfalls and Possibilities

Amy LaMeyer, Shankaranarayanan Ganesan, Jesper M. Johansson 4th USENIX Windows Systems Symposium
Best Student Paper:
Archipelago: An Island-Based File System for Highly Available and Scalable Internet Services

Minwen Ji, Edward Felten, Randolph Wang, Jaswinder Pal Singh 9th USENIX Security Symposium
Best Paper:
Publius: A Robust, Tamper-Evident, Censorship-Resistant, and Source Anonymous

Web Publishing System

Marc Waldman, Aviel D. Rubin, Lorrie Faith Cranor

Best Student Paper:
Detecting Backdoors

Yin Zhang, Vern Paxson 4th Symposium on Operating Systems Design and Implementation
Best Paper:

Checking System Rules Using System-Specific, Programmer-Written

Compiler Extensions

Dawson Engler, Benjamin Chelf, Andy Chou, and Seth Hallem

Best Student Paper:
Proactive Recovery in a Byzantine-Fault-Tolerant System

Miguel Castro and Barbara Liskov 4th Annual Linux Showcase & Conference
Best Paper:
PVFS: A Parallel File System for Linux Clusters

Philip H. Carns, Walter B. Ligon, Robert B. Ross, Rajeef Thakur LISA 2000: 14th Systems Administration Conference
Best Paper: (1)

Deployme: Tellme's Software and Content Manager

Kyle Oppenheim and Patrick McCormick

Best Paper: (2)

Tracing Anonymous Packets to Their Approximate Source

Hal Burch, Bill Cheswick

Best Student Paper:
Peep (The Network Auralizer): Monitoring Your Network with Sound

Michael Gilfix and Alva Couch

1999 [back to top]

3rd Symposium on Operating Systems Design and Implementation
Best Paper:
IO-Lite: A Unified I/O Buffering and Caching System

Vivek S. Pai, Peter Druschel, Willy Zwaenepoel

Best Student Paper (1):

Automatic I/O Hint Generation through Speculative Execution

Fay Chang, Garth A. Gibson

Best Student Paper (2):

Resource Containers: A New Facility for Resource Management in Server Systems

Gaurav Banga (student), Peter Druschel, Jeffrey Mogul 1st Workshop on Intrusion Detection and Network Monitoring
Best Student Paper:
Intrusion Detection Through Dynamic Software Measurement

Sebastian Elbaum (student), John C. Munson

Best Paper:
Experience with EMERALD to Date

Peter G. Neumann and Phillip A. Porras 5th USENIX Conference on Object-Oriented Technologies and Systems
Best Student Paper:
Filters as a Language Support for Design Patterns in Object-Oriented Scripting Languages

Gusaf Neumann, Uwe Zdun (student) USENIX Workshop on Smartcard Technology
Best Paper:
Breaking Up Is Hard To Do: Modeling Security Threats for Smart Cards

Bruce Schneier, Adam Shostack

Best Student Paper:
Design Strategies for Tamper-Resistant Card Processors

Oliver Kommerling, Markus G. Kuhn (student) 1999 USENIX Annual Technical Conference
Outstanding paper award for a promising new tool:

Lightweight Structured Text Processing

Robert C. Miller and Brad A. Myers

Outstanding paper award for a promising new algorithm:

The Case for Compressed Caching in Virtual Memory Systems

Paul R. Wilson, Scott F. Kaplan, and Yannis Smaragdakis

Outstanding paper award for research excellence:

A scalable and explicit event delivery mechanism for UNIX

Gaurav Banga, Jeffrey C. Mogul, Peter Druschel 2nd Large Installation System Administration of Windows NT Conference
Best Paper:
NT Security in an Open Academic Environment

Gregg Daly, Gary Buhrnmaster, Matthew Campbell, Andrea Chan, Robert Cowles, Ernest Danys, Patrick Hancox, Bill Johnson, David Leung, Jeff Lwin 3rd USENIX Windows NT Symposium
Best Student Paper:
Evaluating Windows NT Terminal Server Performance

Alexander Ya-li Wong (student) & Margo I. Seltzer 8th USENIX Security Symposium
Best Paper and Best Student Paper:

The Design and Analysis of Graphical Passwords

Ian Jermyn (student), Alain Mayer, Fabian Monrose, Michael K. Reiter, Aviel D. Rubin 2nd USENIX Symposium on Intenet Technologies & Systems (USITS)
Best Paper:
Prefetching Hyperlinks

Dan Duchamp

Best Student Paper:
Sting: A TCP-based Network Measurment Tool

Stefan Savage LISA '99: 13th Systems Administration Conference
Best Paper:
Dealing with Public Ethernet Jacks - Switches, Gateways, and Authentication

Robert Beck

Best Student Paper:
A Retrospective on Twelve Years of LISA Proceedings

Eric Anderson, Dave Patterson

1998 [back to top]

7th USENIX Security Symposium
Best Paper:
Bro: A System for Detecting Network Intruders in Real-Time

Vern Paxson

Best Student Paper:
Certificate Revocation and Certificate Update

Kobbi Nissim (student), Moni Naor 4th USENIX Conference on Object-Oriented Technologies and Systems
Best Student Paper:
The Design and Performance of MedJava

Prashnat Jain (student), Seth Widoff, Douglas Schmidt 1998 USENIX Annual Technical Conference
Best Paper and Best Student Paper:

Scalable Kernel Performance for Internet Servers Under Realistic Loads

Gaurav Banga (student) and Jeffrey C. Mogul Large Installation System Administration of Windows NT Symposium
Best Paper:
Patch32: A System for Automated Client OS Updates

Gerald Carter 2nd USENIX Windows NT Symposium
Best Student Paper (1):

A Performance Study of Sequential I/O on Windows NT 4

Erik Riedel

Best Student Paper (2):

Vassal: Loadable Scheduler Support for Multi-Policy Scheduling

George M. Candea (student) and Michael B. Jones 3rd USENIX Workshop on Electronic Commerce
Best Paper:
Detecting Hit Shaving in Click-Through Payment Schemes

Michael Reiter, Vinod Anupam, Alain Mayer

Best Student Paper:
Electronic Auctions with Private Bids

Michael Harkavy, Douglas Tygar, Hiroaki Kikuchi USENIX 6th Annual Tcl/Tk Conference
Best Paper:
NBC's GEnesis Broadcase Automation System: From Prototype to Product

Stephen J. Angelovich, Kevin B. Kenny, Brion D. Sarachan

Best Student Paper:
WebWiseTclTk: A Safe-Tcl/Tk-based Toolkit Enhanced for the World Wide Web

Hemang Lavana (student), Franc Brglez (professor) LISA '98: 12th Systems Administration Conference
Best Paper:
Computer Immunology

Mark Burgess

Best Student Paper:
Design and Implementation of an Administration System for Distributed Web Server

C.S. Yang and M.Y. Luo (Student)

1997 [back to top]

USENIX 1997 Annual Technical Conference
Best Paper:
Embedded Inodes and Explicit Grouping: Exploiting Disk Bandwidth for Small Files

Gregory R. Ganger & M. Frans Kaashoek

Best Student Paper:
Protected Shared Libraries - A New Approach to Modularity and Sharing

Arindam Banerji, John Mochael Tracey, David L. Cohn 3rd USENIX Conference on Object-Oriented Technologies and Systems
Best Student Paper:
Using the Strategy Design Pattern to Compose Reliable Distributed Protocols

Benoit Garbinato and Rachid Guerraoui 5th Tcl/Tk Workshop
Best Paper:
Writing a Tcl Extension in only 7 years

Don Libes

Best Student Paper:

Jacl: A Tcl Implementation in Java

Ioi Lam and Brian C. Smith LISA '97: 11th USENIX Systems Administration Conference
Best Paper:
Implementing a Generalized Tool for Network Monitoring

Marcus J. Ranum, Kent Landfield, Mike Stolarchuk, Mark Sienkiewicz, Andrew Lambeth, Eric Wall USENIX Symposium on Internet Technologies & Systems (USITS)
Best Paper:
Measuring the Capacity of a Web Server

Gaurav Banga, and Peter Druschel

1996 [back to top]

USENIX 1996 Annual Technical Conference
Best Paper:
Imbench: Portable Tools for Performance Analysis

Larry McVoy and Carl Staelin

Best Student Paper (1):

AFRAID - A Frequently Redundant Array of Independent Disks

Stefan Savage and John Wilkes

Best Student Paper (2):

A Comparison of FFS Disk Allocation Policies

Keith A. Smith and Margo Seltzer 4th Annual USENIX Tcl/Tk Workshop
Best Paper:
Lessons from the Neighborhood Viewer: Building Innovative Collaborative Applications in Tcl and Tk

Alex Safonov, Douglas Perrin, Joseph A. Konstan, John Carlis, and Robert Elde USENIX 2nd Symposium on OS Design and Implementation
Best Paper:
Automatic Compiler-Inserted I/O Prefetching for Out-Of-Core Applications

Todd C. Mowry, Angela K. Demke, Orran Krieger

Best Student Paper:
Safe Kernel Extensions Without Run-Time Checking

George C. Necula and Peter Lee 6th USENIX Security Symposium
Best Paper:
A Secure Environment for Untrusted Helper Applications - Confining the Wiley Hacker

Ian Goldberg, David Wagner, Randi Thomas and Eric A. Brewer

Best Student Paper:
Building Systems That Flexibly Control Download Executable Content

Trent Jaeger, Aviel D. Rubin, and Atul Prakash Second USENIX Workshop on Electronic Commerce
Best Paper:
Tamper Resistance--A Cautionary Note

Ross Anderson and Markus Kuhn

Best Student Paper:
Analysis of the SSL 3.0 Protocol

David Wagner and Bruce Schneier LISA '96: 10th System Administration Conference
Best Paper:
SLINK: Simple, Effective Filesystem Maintenance Abstractions for Community-Based Administration

Alva L. Couch

Best Student Paper:
Automatic and Reliable Elimination of E-mail Loops Based on Statistical Analysis

Eduardo Solana, V. Baggiolini, M. Ramluckun, J. Harms

1995 [back to top]

USENIX 1995 Annual Technical Conference, New Orleans, Louisiana
Best Paper:
Performance Implecations of Multiple Pointer Sizes

Jefffrey C. Mogul, Joel F. Bartlett, Robert N. Mayo and Amitabh Srivastava

Best Student Paper:
File System Logging versus Clustering: A Performance Comparison

Margot Seltzer, Keith A. Smith, Hari Balakrishnan, Jacqueline Chang, Sara McMains and Venkata Padmanabhan LISA '95: 9th System Administration Conference
Best Paper:
OpenDist—Incremental Software Distribution

Peter W. Osel and Wilfried Gansheimer

Best Student Paper:
Multi-platform Interrogation and Reporting with Rscan

Nathaniel Sammons USENIX 3rd Annual Tcl/Tk Workshop
Best Paper:
Two years with the TkMan: Lessons and Innovations

Thomas A. Phelps

Best Presentation:

Advances in the Pad++ Zoomable Graphics Widget

Benjamin B. Bederson and James D. Hollan

1994 [back to top]

USENIX Summer 1994 Technical Conference
Best Paper:
A Better Update Policy

Jeff Mogul

Best Student Paper:
Secure Short-Cut routine for Mobile IP

Trevor Blackwell, Kee Chan, Koling Chang, Thomas Charuhas, James Gwertzman, Brad Karp, H. T. Kung, David Li, Dong Lin, Robert Morris, Rob Polansky, Diane Tang, Cliff Young, John Zao USENIX Winter 1994 Technical Conference
Best Paper:
GLIMPSE: A Tool to Search Through Entire File Systems

Udi Manber and Sun Wu

Best Student Paper:
Memory Behavior for an X11 Window System

J.Bradley Chen

Best Presentation:

Acme: A User Interface for Programmers

Rob Pike LISA '94: 8th USENIX System Administration Conference
Best Paper:
The Group Administration Shell and the GASH Network Computing Environment

Jonathan Abbey

Best Student Paper:
Soft: A Software Environment Abstraction Mechanism

Robert Leslie First Symposium on Operating Systems Design and Implementation
Best Paper:
Lottery Scheduling: Flexible Propotional-Share Resource Management

Carl A. Waldspurger

1993 [back to top]

USENIX Summer 1993 Technical Conference
Best Paper:
Call Path Profiling of Monotonic Program Resources in UNIX

Robert J. Hall and Aaron J. Goldberg

Best Student Paper:
Anonymous RPC: Low-latency Protection in a 64-Bit Address Space

Curtis Yarvin, Richard Bukowski, and Thomas Anderson

Best Presentation:

AudioFile: A Network-transparent System for Distributed Audio Applications

James Gettys, Thomas Levergood, Andrew C. Payne, Lawrence C. Stewart, and G. Winfield Treese USENIX Winter 1993 Conference
Best Paper:
The Nachos Instructional Operating System

Wayne Christopher, Steven J. Procter and Thomas E. Anderson

Best Student Paper:
The BSD Packet Filter: A New Architecture for User-level Packet Capture

Steve McCanne

Best Presentation (1):

An Implementation of a Log-Structured File System

Margo Seltzer, Keith Bostick and M. Kirk McKusick

Best Presentation (2):

Phonestation, Moving the Telephone Onto the Virtual Desktop

Stephen A. Uhler

1992 [back to top]

USENIX Summer 1992 Conference
Best Paper:
A Discipline of Error Handling (PDF format)

Doug Moen

Best Student Paper:
The Recover Box (PDF format)

Mary Baker and Mark Sullivan USENIX Winter 1992 Conference
Best Student Paper (1):

Trace-Driven Analysis of Name and Attribute Caching in a Distributed System (PDF format)

Ken Shirriff and John Ousterhout

Best Student Paper (2):

agrep - A Fast Approximate Pattern Matching Tool (PDF format)

Sun Wu and Udi Manber

1991 [back to top]

USENIX Summer 1991 Conference
Best Student Paper:
Long-term Caching Strategies for Very Large Distributed File Systems (PDF format)

Matt Blaze and Rafael Alonso USENIX Winter 1991 Conference
Best Student Paper:
A New Hash Package for UNIX (PDF format)

Margo Seltzer and Ozan Yigit

1990 [back to top]

USENIX Summer 1990 Conference
Best Student Paper:
Montage: Breaking Windows into Small Pieces (PDF format)

Paul Haahr USENIX Winter 1990 Conference
Best Student Paper:
Disk Scheduling Revisited (PDF format)

Margo Seltzer, Peter Chen, John Ousterhout

Highly Predictive Blacklisting

2008-08-28T02:42:00.000-07:00

Highly Predictive Blacklisting

Jian Zhang

SRI International Menlo Park, CA 94025

Phillip Porras

SRI International Menlo Park, CA 94025

Johannes Ullrich

SANS Institute Bethesda, MD 20814

Abstract:

The notion of blacklisting communication sources has been a well-established defensive measure since the origins of the Internet community. In particular, the practice of compiling and sharing lists of the worst offenders of unwanted traffic is a blacklisting strategy that has remained virtually unquestioned over many years. But do the individuals who incorporate such blacklists into their perimeter defenses benefit from the blacklisting contents as much as they could from other list-generation strategies? In this paper, we will argue that there exist better alternative blacklist generation strategies that can produce higher-quality results for an individual network. In particular, we introduce a blacklisting system based on a relevance ranking scheme borrowed from the link-analysis community. The system produces customized blacklists for individuals who choose to contribute data to a centralized log-sharing infrastructure. The ranking scheme measures how closely related an attack source is to a contributor, using that attacker's history and the contributor's recent log production patterns. The blacklisting system also integrates substantive log prefiltering and a severity metric that captures the degree to which an attacker's alert patterns match those of common malware-propagation behavior. Our intent is to yield individualized blacklists that not only produce significantly higher hit rates, but that also incorporate source addresses that pose the greatest potential threat. We tested our scheme on a corpus of over 700 million log entries produced from the DShield data center and the result shows that our blacklists not only enhance hit counts but also can proactively incorporate attacker addresses in a timely fashion. An early form of our system have been fielded to DShield contributors over the last year.

1 Introduction

A network address blacklist represents a collection of source IP addresses that have been deemed undesirable, where typically these addresses have been involved in some previous illicit activities. For example, DShield (a large-scale security-log sharing system) regularly compiles and posts a firewall-parsable blacklist of the most prolific attack sources seen by its contributors [17]. With more than 1700 contributing sources providing a daily stream of 30 million security log entries, such daily blacklists provide an informative view of those class C subnets that are among the bane of the Internet with respect to unwanted traffic. We refer to the blacklists that are formulated by a large-scale alert repository and consist of the most prolific sources in the repository's collection of data as the global worst offender list (GWOL). Another strategy for formulating network address blacklists is for an individual network to create a local blacklist based entirely on its own history of incoming communications. Such lists are often culled from a network's private firewall log or local IDS alert store, and incorporate the most repetitive addresses that appear within the logs. We call this blacklist scheme the local worst offender list (LWOL) method.

The GWOL and LWOL strategies have both strengths and inherent weaknesses. For example, while GWOLs provide networks with important information about highly prolific attack sources, they also have the potential to exhaust the subscribers' firewall filter sets with addresses that will simply never be encountered. Among the sources that do target the subscriber, GWOLs may miss a significant number of attacks, in particular when the attack sources prefer to choose their targets more strategically, focusing on a few known vulnerable networks [4]. Such attackers are not necessarily very prolific and are hence elusive to GWOLs. The sources on an LWOL have repetitively sent unwanted communications to the local network and are likely to continue doing so. However, LWOLs are limited by being entirely reactive - they only capture attackers that have been pounding the local network and hence cannot provide a potential for the blacklist consumer to learn of attack sources before these sources reach their networks.

Furthermore, both types of lists suffer from the fact that an attack source does not achieve candidacy until it has produced a sufficient mass of communications. That is, although it is desirable for firewall filters to include an attacker's address before it has saturated the network, neither GWOL nor LWOL offer a solution that can provide such timely filters. This is a problem particularly with GWOL. Even after an attacker has produced significant illicit traffic, it may not show up as a prolific source within the security log repository, because the data contributors of the repository are a very small set of networks on the Internet. Even repositories such as DShield that receive nearly 1 billion log entries per month represent only a small sampling of Internet activity. Significant attacker sources may elude incorporation into a blacklist until they have achieved extensive saturation across the Internet.

In summary, a high-quality blacklist that fortifies network firewalls should achieve high hit rate, should incorporate addresses in a timely fashion, and should proactively include addresses even when they have not been encountered previously by the blacklist consumer's network. Toward this goal, we present a new blacklist generation system which we refer to as the highly predictive blacklisting (HPB) system. The system incorporates 1) an automated log prefiltering phase to remove unreliable alert contents, 2) a novel relevance-based attack source ranking phase in which attack sources are prioritized on a per-contributor basis, and 3) a severity analysis phase in which attacker priorities are adjusted to favor attackers whose alerts mirror known malware propagation patterns. The system constructs final individualized blacklists for each DShield contributor by a weighted fusion of the relevance and severity scores.

HPB's underlying relevance-based ranking scheme represents a significant departure from the long-standing LWOL and GWOL strategies. Specifically, the HPB scheme examines not just how many targets a source address has attacked, but also which targets it has attacked. In the relevance-based ranking phase, each source address is ranked according to how closely related the source is to the target blacklist subscriber. This relevance measure is based on the attack source similarity patterns that are computed across all members of the DShield contributor pool (i.e., the amount of attacker overlap observed between the contributors). Using a data correlation strategy similar to hyper-text link analysis, such as Google's PageRank [2], the relationships among all the contributors are iteratively explored to compute an individual relevance value from each attacker to each contributor.

We evaluated our HPB system using more than 720 million log entries produced by DShield contributors from October to November 2007. We contrast the performance of the system with that of the corresponding GWOLs and LWOLs, using identical time windows, input data, and blacklist lengths. Our results show that for most contributors (more than 80%), our blacklist entries exhibit significantly higher hit counts over a multiday testing window than both GWOL and LWOL. Further experiments show that our scheme can proactively incorporate attacker addresses into the blacklist before these addresses reach the blacklist consumer network, and it can do so in a timely fashion. Finally, our experiments demonstrate that the hit count increase is consistent over time, and the advantages of our blacklist remain stable across various list lengths and testing windows.

The contribution of this paper is the introduction of the highly predictive blacklisting system, which includes our methodology for prefiltering, relevance-based ranking, attacker severity ranking, and final blacklist construction. Ours is the first exploration of a link-analysis-based scheme in the context of security filter production and to quantify the predictive quality of the resulting data. The HPB system is also one of the only new approaches we are aware of for large-scale blacklist publication that has been proposed in many years. However, our HPB system is applicable only to those users who participate as active contributors to collaborative security log data centers. Rather than a detriment, we hope that this fact provides some operators a tangible incentive to participate in security log contributor pools. Finally, the system discussed in this paper, while still a research prototype, has been fully implemented and deployed for nearly a year as a free service on the Internet at DShield.org. Our experience to date leads us to believe that this approach is both scalable and feasible for daily use.

The rest of the paper is organized as follows. Section 2 provides a background on previous work in blacklist generation and related topics. In Section 3 we provide a detailed description of the Highly Predictive Blacklist system. In Section 4 we present a performance evaluation of HPBs, GWOLs, and LWOLS, including assessments of the extent to which the above three desired blacklist properties (hit rate, proactive appearance, and timely inclusion) are realized by these three blacklists. In Section 5 we present a prototype implementation of the HPB system that is freely available to DShield.org log contributors, and we summarize our key findings in Section 6.

2 Related Work

Network address and email blacklists have been around since the early development of the Internet [6]. Today, sites such as DShield regularly compile and publish firewall-parsable filters of the most prolific attack sources reported to its website [17]. DShield represents a centralized approach to blacklist formulation, providing a daily perspective of the malicious background radiation that plagues the Internet[20,15]. Other recent examples of computer and network blacklists include IP and DNS blacklists to help networks detect and block unwanted web content, SPAM producers, and phishing sites, to name a few [7,17,8,18]. The HPB system presented here complements, but does not displace these resources or their blacklisting strategies. In addition, HPBs are only applicable to active log contributors (we hope as an incentive), not as generically publishable one-size-fits-all resources.

More agile forms of network blacklisting have also been explored, with the intention of rapidly publishing perimeter filters to control actively spreading malware epidemics [12,1,3,14]. For example, in [14] a peer-to-peer blacklisting scheme is proposed, where each network incorporates an address into its local blacklist when a threshold number of peers have reported attacks from this address. We separate our HPB system from these malware defense schemes. While the HPB system does incorporate a malware-oriented attacker severity metric into its final blacklist selection, we have not contemplated nor propose HPBs for use in the context of dynamic quarantine defenses for malware epidemics.

One key insight that inspired the HPB relevance-based ranking scheme was raised by Katti et al. [10], who identified the existence of stable correlations among the attackers reported by security log contributors. Here we introduce a relevance-based recommendation scheme that selects candidate attack sources based on the attacker overlaps found among peer contributors. This relevance-based ranking scheme can be viewed as a random walk on the correlation graph, going from one node to another following the edges in the graph with the probability proportional to the weight of the graph. This form of random walk has been applied in link-analysis systems such as Google's PageRank [2], where it is used to estimate the probability that a webpage may be visited. Similar link analysis has been used to rank movies [13] and reading lists [19].

The problem of predicting attackers has also been recently considered in [24] using a Guassian process model. However, [24] purely focused on developing statistical learning techniques for attacker prediction based on collaborative filtering. In this paper, we present a comprehensive blacklisting generation system that considers many other characteristics of attackers. The prediction part is only one component in our system. Furthermore, the prediction model presented here is completely different from the one in [24] (Gaussian process model in [24] and link analysis model here). By taking some penalty in predictive power, the prediction model presented here is much more scalable, which is of necessity for implementing a deployable service (Section 5).

Finally, [23] provides a six-page summary of the earliest release of our DShield HPB service, including a high-level description of an early ranking scheme. In this paper we have substantially expanded this algorithm and present its full description for the first time. This present paper also introduces the integration of metrics to capture attack source maliciousness in its final rank selection, and presents the full blacklist construction system. We also present our quantitative evaluation of multiple system properties, and address several open questions that have been raised over the past year since our initial prototype.

3 Blacklisting System

**Figure 1:** Blacklisting system architecture

We illustrate our blacklisting system in Figure 1. The system constructs blacklists in three stages. First, the security alerts supplied by sensors across the Internet are preprocessed. This removes known noises in the alert collection. We call this the prefiltering stage. The preprocessed data are then fed into two parallel engines. One ranks, for each contributors, the attack sources according to their relevance to that contributor. The other scores the sources using a severity assessment that measures their maliciousness. The relevance ranking and the severity score are combined at the last stage to generate a final blacklist for each contributor.

We descibe the prefiltering process in Section 3.1, relevance ranking in Section 3.2, severity score in Section 3.3 and the final production of the blacklists in Section 3.4.

3.1 Prefiltering Logs for Noise Reduction

One challenge to producing high-quality threat intelligence for use in perimeter filtering is that of reducing the amount of noise and erroneous data that may exist in the input data that drives our blacklist construction algorithm. That is, in addition to the unwanted port scans, sweeps, and intrusion attempts reported daily within the DShield log data, there are also commonly produced log entries that arise from nonhostile activity, or activity from which useful filters cannot be reliably derived. While it is not possible to separate attack from nonattack data, the HPB system prefilters from consideration logs that match criteria that we have been able to empirically identify as commonly occurring nonuseful input for blacklist construction purposes.

As a preliminary step prior to blacklist construction, we apply three filtering techniques to the DShield alert logs. First, the HPB system removes from consideration DShield logs produced from attack sources from invalid or unassigned IP address space. Here we employ the bogon list created by the Cymru team that captures addresses that are reserved, not yet allocated, or delegated by the Internet Assigned Number Authority [16]. Typically, such addresses should not be routed, but otherwise do appear anyway in the DShield data. In addition, reserved addresses such as the 10.x.x.x or 192.168.x.x may also appear in misconfigured contributor logs that are not useful for translating into blacklists.

Second, the system prefilters from consideration network addresses from Internet measurement services, web crawlers, or common software update sources. From experience, we have developed a whitelist of highly common sources that, while innocuous from an intrusion perspective, often generate alarms in DShield contributor logs.

Finally, the HPB system applies heuristics to avoid common false positives that arise from commonly timed-out network services. Specifically, we exclude logs produced from source ports TCP 53 (DNS), 25 (SMTP), 80 (HTTP), and 443 (often used for secure web, IMAP, and VPN), and from destination ports TCP 53 (DNS) and 25 (SMTP). Firewalls will commonly time out sessions from these services when the server or client becomes unresponsive or is slow. In practice, the combination of these prefiltering steps provides approximately a 10% reduction in the DShield input stream prior delivery to the blacklist generation system.

3.2 Relevance Ranking

Our notion of attacker relevance is a measure that indicates how close the attacker is related to a particular blacklist consumer. It also reflects the likelihood to which the attacker may come to the blacklist consumer in the near future. Note that this relevance is orthogonal to metrics that measure the severity (or benignness) of the source, which we will discuss in the next section.

In our context, the blacklist consumers are the contributors that supply security logs to a log-sharing repository such as DShield. Recent research has observed the existence of attacker overlap correlations between DShield contributors [10], i.e., there are pairs of contributors that share quite a few common attackers, where the common attacker is defined as a source address that both contributors have logged and reported to the repository. This research also found that this attacker overlap phenomenon is not due to attacks that select targets randomly (as in a random scan case). The correlations are long lived and some of them are independent of address proximity. We exploit these overlap relationships to measure attacker relevance.

We first illustrate a simple concept of attacker relevance. Consider a collection of security logs displayed in a tabular form as shown in Table 1. We use the rows of the table to represent attack sources and the columns to represent contributors. We refer to the unique source addresses that are reported within the log repository as attackers, and use the terms ``attacker'' and ``source'' interchangeably. Since the contributors are also the targets of the logged attacks, we refer to them as victims. We will use the terms ``contributor'' and ``victim'' interchangeably. An asterisk ``*'' in the table cell indicates that the corresponding source has reportedly attacked the corresponding contributor.

Table 1: Sample Attack Table


*	*
*	*
*		*
	*	*
	*
			*	*
		*
		*	*

Let us assume that Table 1 represents a series of logs contributed in the recent past by our five victims, through . Now suppose we would like to calculate the relevance of the sources for contributor based on these attack patterns. From the attack table we observe that contributors and share multiple common attackers. also shares one common attack source () with , but does not share attacker overlap with the other contributors. Given this observation, between sources and , we would say that has more relevance to than because has reportedly attacked , which has recently experienced multiple attack source overlaps with . But the victims of 's attacks share no overlap with . Note that this relevance measure is quite different from the measures based on how prolific the attack source has been. The latter would favor over , as has attacked more victims than . In this sense, which contributors a source has attacked is of greater significance to our scheme than how many victims it has attacked. Similarly, between and , is more relevant, because the victim of () shares more common attacks with than the victim of (). Finally, because has attacked both and , we would like to say that it is the most relevant among , and .

To formalize the above intuition, we model the attack correlation relationship between contributors using a correlation graph, which is a weighted undirected graph . The nodes in the graph consist of the contributors . There is an edge between node and if is correlated with . The weight on the edge is determined by the strength of the correlation (i.e., occurrences of attacker overlap) between the two corresponding contributors. We now introduce some notation for the relevance model.

Let be the number of nodes (number of contributors) in the correlation graph. We use to denote the adjacency matrix of the correlation graph, where the entry in this matrix is the weight of the edge between node and . For a source , we denote by the set of contributors that have reported an attack from . can be written in a vector form such that if and otherwise. We also associate with each source a relevance vector such that is the relevance value of attacker with respect to contributor . We use lowercase boldface to indicate vectors and uppercase boldface to indicate matrices. Table 2 summarizes our notation.

Table 2: Summary of Relevance Model Notations

	# of contributors
	-th contributor
	Adjacency matrix of the correlation graph
	Set of contributors that have reported attack(s) from source
	Attack vector for source . if and 0 otherwise
	Relevance vector for source . is the relevance value of attacker with respect to contributor

We now describe how to derive the matrix from the attack reports. Consider the following two cases. In Case 1, contributor sees attacks from 500 sources and sees 10 sources. Five of these sources attack both and . In Case 2, there are also five common sources. However, sees only 50 sources and sees 10. Although the number of overlapping sources is the same (i.e., 5 common sources), the strength of connection between and is different in the two cases. If a contributor observes a lot of attacks, it is expected that there should be more overlap between this contributor and the others. Let be the number of sources seen by , the number seen by , and the number of common attack sources. The ratio shows how important is for while shows how important is for . Since we want to reflect the strength of the connection between and , we set . One may view this new as a standardized correlation matrix. Figure 2 shows the matrix for Table 1 constructed using this method.

**Figure 2:** Standardized Correlation Matrix for Attack Table 1

Given this correlation matrix, we follow the aforementioned intuition and calculate the relevance as . This is to say that if the repository reports that source has attacked contributor , this fact contributes a value of to the source's relevance with respect to the victim . Written in vector form, it gives us

(1)

The above simple relevance calculation lacks certain desired properties. For example, the simple relevance value is calculated solely from the observed activities from the source by the repository contributors. In some cases, this observation does not represent the complete view of the source's activity. One reason is that the contributors consist of only a very small set of networks in the Internet. Before an attacker saturates the Internet with malicious activity, it is often the case that only a few contributors have observed the attacker. The attacker may be at its early stage or it has attacked many places, most of which do not participate in the security log sharing system. Therefore, one may want a relevance measure that has a ``look-ahead'' capability. That is, the relevance calculation should take into consideration possible future observations of the source and include these anticipated observations from the contributors into the relevance values.

**Figure 3:** Relevance Evaluation Considers Possible Future Attacks

Figure 3 gives an example where one may apply this ``look-ahead'' feature. (Examples here are independent of the one shown in Table 1.) The correlation graph of Figure 3 consists of four contributors numbered 1, 2, 3, and 4. Contributor 2 reported an attack from source (represented by the star). Our goal is to evaluate how relevant this attacker is to contributor 1 (double-circled node). Using Equation 1, the relevance would be zero. However, we observe that has relevance 0.5 with respect to contributor 3 and relevance 0.3 with respect to contributor 4. Although at this time, contributors 3 and 4 have not observed yet, there may be possible future attacks from . In anticipation of this, when evaluating 's relevance with respect to contributor 1, contributors 3 and 4 pass to contributor 1 their relevance values after multiplying them with the weights on their edges, respectively. The attacker's relevance value for contributor 1 then is 0.5*0.2+0.3*0.2 = 0.16. Note that, had actually attacked contributors 3 and 4, the contributors would have passed the relevance value 1 (again after multiplying them with the weights on the edges) to contributor 1.

This can be viewed as a relevance propagation process. If a contributor observed an attacker, we say that the attacker has an initial relevance value 1 for that contributor. Following the edges that go out of the contributor, a fraction of this relevance can be distributed to the neighbors of the contributor in the graph. Each of 's neighbors receives a share of relevance that is proportional to the weight on the edge that connects the neighbor to . Suppose is one of the neighbors. A fraction of the relevance received by is then further distributed, in similar fashion, to its neighbors. The propagation of relevance continues until the relevance values for each contributor reach a stable state.

**Figure 4:** Attacks on Members in a Correlated Group Contribute More Relevance

This relevance propagation process has another benefit besides the ``look-ahead'' feature. Consider the correlation graph given in Figure 4 (a). The subgraph formed by nodes 1, 2, 3, and 4 is very different from that formed by nodes 1, 5, 6, and 7. The subgraph from nodes 1, 2, 3, and 4 is well connected (in fact it forms a clique). The contributors in the subgraph are thus more tied together. We call them a correlated group. (We use a dotted circle to indicate the correlated group in Figure 4.) There may be certain intrinsic similarities between the members in the correlated group (e.g., IP address proximity, similar vulnerability). Therefore, it is natural to assign more relevance to source addresses that have attacked other contributors in the same correlated group. For example, consider the sources and in Figure 4. They both attacked three contributors. All the edges in the correlation graph have the same weights. (Hence, we omitted the weights in the figure.) We would like to say that is more relevant than for contributor 1. If we calculate the relevance value by Equation 1, the values would be the same for the two attackers. Relevance propagation helps to give more value to the attacker because members of the correlated group are well connected. There are more paths in the subgraph that lead from the contributors where the attack happened to the contributor for which we are evaluating the attacker relevance. For example, the relevance from contributor 2 can propagate to contributor 3 and then to contributor 1. It can also go to contributor 4 and then to contributor 1. This is effectively the same as having an edge with larger weight between the contributors 2 and 1. Therefore, relevance propagation can effectively discover and adapt to the structures in the correlation graph. The relevance values assigned then reflect certain intrinsic relationships among contributors.

We extend Equation 1 to employ relevance propagation. If we propagate the relevance values to the immediate neighbors in the correlation graph, we obtain a relevance vector that represents the propagated values. Now we propagate the relevance values one more hop. This gives us . The relevance vector that reflects the total relevance value each contributor receives is then . If we let the propagation process iterate indefinitely, the relevance vector would become . There is a technical detail in this process we need to resolve. Naturally, we would like the relevance value to decay along the path of propagation. The further it goes on the graph, the smaller its contribution becomes. To achieve this, we scale the matrix by a constant such that the 2-norm of the new matrix becomes smaller than one. With this modification, an attacker will have only a negligible relevance value to contributors that are far away in the correlation graph. Putting the above together, we compute the relevance vector by the following equation:

(2)

We observe that is the solution for in the following system of linear equations:

(3)

The linear system described by Equation 3 is exactly the system used by Google's PageRank [2]. PageRank analyzes the link structures of webpages to determine the relevance of each webpage with respect to a keyword query. In PageRank, is set to be an all-one vector and is determined by letting be 1/(# of outgoing links on page ) if one of these outgoing links points to webpage , and otherwise. Therefore, PageRank propagates relevance where every node provides an initial relevance value of one. In our relevance calculation, only nodes whose corresponding contributors have reported the attacker are assigned one unit of initial relevance. Similar to the PageRank values that reflect the link structures of the webpages, our relevance values reflect the structure of the correlation graph that captures intrinsic relationships among the contributors.

Equation 3 can be solved to give , where is the identity matrix. Also, since , . This gives the relevance vector for each attack source. The sources are then ranked, for each contributor, according to the relevance values. As each attack source has a potentially different relevance value for each contributor, the rank of a source with respect to different contributors is different. Note that our concept of relevance measure and relevance propagation does not depend on a particular choice of the matrix. As long as reflects the connection weight between the contributors, our relevance measure applies.

3.3 Analyzing Attack Pattern Severity

**Figure 5:** Malware Associated Ports

We now consider the problem of measuring the degree to which each attack source exhibits known patterns of malicious behavior. In the next section, we will disuss how this measure can be fused into our final blacklist construction decisions. In this section we will describe our model of malicious behavior and the attributes we extract to map each attacker's log production patterns to this model.

Our model of malicious behavior, in this instance, focuses on identifying typical scan-and-infect malicious software (or malware). We define our malware behavior pattern as that of an attacker who conducts an IP sweep to small sets of ports that are known to be associated with malware propagation or backdoor access. This behavior pattern matches the malware behavior pattern documented by Yegeneswaren et.al. in [20], as well as our own most recent experiences (within the last twelve months) of more than 20K live malware infections observed within our honeynet [21]. Other potential malware behavior patterns may be applied, for example, such as the scan-oriented malicious address detection schemes outlined in the context of dynamic signature generation [11] and malicious port scan analysis [9]. Regardless of the malware behavior model used, the design and integration of other severity metrics into the final blacklist generation process can be carried out in a similar fashion.

For the set of log entries over the relevance-calculation time window, we calculate several attributes for each attacker's /24 network address. (Our blacklists are specified on a per /24 basis, meaning that a single malicious address has the potential to induce a LAN-wide filter. This is standard practice for DShield and other blacklists.) For each attacker, we assign a score to target ports associated with the attacker, assigning a different weight depending on whether or not the port is associated with known malware communications.

Let be the set of malware-associated ports, where we currently uses the definition in Figure 5. This is derived from various AV lists and our honeynet experiences. We do not argue that this list is complete and can be expanded across the life of our HPB service. However, our experiences in live malware analysis indicate that the entries in are both highly common and highly indicative of malware propagation.

Let the number of target ports that attacker connects to be , and the total number of unique ports connected to be defined as . We associate a weighting (or importance) factor for all ports in , and a weighting factor for all nonmalware ports. We then compute a malware port score () metric for each attacker as follows:

(4)

Here, we intend to be of greater weight than , and choose an initial default of . has the property that even if a large is found, if is also large (as in a horizontal portscan), then will remain small. Again, our intention is to promote a malware behavior pattern in which malware propagation will tend to target fewer specific ports, and is not associated with attackers that engage in horizontal port sweeps.

Next, we compute the set of unique target IP addresses connected to by attacker . We refer to this count as . A large represents confirmed IP sweep behavior, which we strongly associate with our malware behavior model. is the exclusive prioritization metric used by GWOL, whereas here we consider a secondary factor to in computing a final malware behavior score. We could also include metrics regarding the number of DShield sensors (i.e., unique contributor IDs) that have reported the attacker, which arguably represents the degree of consensus in the contributor pool that the attack source is active across the Internet. However, the IP sweep pattern is of high interest, even when the IP sweep experiences may have been reported only by a smaller set of sensors.

Third, we compute an optional tertiary behavior metric that captures the ratio of national to international addresses that are targeted by attacker . Within the DShield repository we find many cases of sources (such as from China, Russian, the Czech Republic) that exclusively target international victims. However, this may also illustrate a weakness in the DShield contributor pool, as there may be very few contributors that operate sensors within these countries. We incorporate a dampening factor ( ) that allows the consumer to express the degree to which the factor should be nullified in computing the final severity score for each attacker.

Finally, we compute a malware severity score for each candidate attacker that may appear in the set of final blacklist entries:

(5)

The three factors are computed in order of significance in mapping to our malware behavior model. Logarithm is used because in our model, the secondary metric () and the tertiary metric () are less important than the malware port score and we only care about their order of magnitude.

3.4 Blacklist Production

For each attacker, we now have both its relevance ranking and its severity score. We can combine them to generate a final blacklist for each contributor.

For the final blacklist, we would like to include the attackers that have strong relevance and discard the nonrelevant attackers. To generate a final list of length , we use the attacker's relevance ranking to compile a candidate list of size . (We often set .) Then, we use severity scores of the attackers on the candidate list to adjust its ranking and pick the highest-ranked attackers to form the final list. Intuitively, the adjustment should promote the rank of an attacker if the severity assessment indicates that it is very malicious. Toward this goal, we define a final score that combines the attacker's relevance rank in the candidate list and its severity assessment. In particular, let be the relevance rank of the attacker (i.e., is the k-th entry in the candidate list). Recall from last section is the severity score of . The final score is defined to be

(6)

where

where is the ``S'' shaped Gaussian error function. We plot in Figure 6 with and different .

**Figure 6:** Phi with different d value

promotes the rank of an attacker according to its maliciousness. The larger the value of is, the more the attacker is moved above comparing to its original rank. A of value 1 would then move the attacker above for one half of the size of the final list comparing to its original rank. The ``S'' shaped transforms the severity assessment into a value between 0 and 1. The less-malicious attackers often give an assessment score below 3. After transformation, they will receive only small promotions. On the other hand, malicious attackers that give an assessment score above 7 will be highly promoted.

To generate the final list, we sort the values of the attackers in the candidate list and then pick of them that have the smallest .

4 Experiment Results

We created an experimental HPB blacklist formulation system. To evaluate the HPBs, we performed a battery of experiments using the DShield.org security firewall and IDS log repository. We examined a collection of more than 720 million log entries produced by DShield contributors from October to November 2007. Since our relevance measure is based on correlations between contributors, HPB production is not applicable to contributors that have submitted very few reports (DShield has contributors that hand-select or sporadically contribute logs, providing very few alerts). We therefore exclude those contributors that we find effectively have no correlation with the wider contributor pool or simply have too few alerts to produce meaningful results. For this analysis, we found that we could compute correlation relationships for about 700 contributors, or 41% of the DShield contributor pool.

To assess the performance of the HPB system, we compare its performance relative to the standard DShield-produced GWOL [17]. In addition, we compare our HPB performance to that of LWOLs, which we compute individually for all contributors in our comparison set. For the purpose of our comparative assessment, we fixed the length of all three competing blacklists to exactly 1000 entries. However, after we present our comparative performance results, we will then continue our investigation by analyzing how the blacklist length affects the performance of the HPBs.

In the experiments, we generate GWOL, LWOL, and HPBs using data for a certain time period and then test the blacklists on data from the time window following this period. We call the period used for producing blacklists the training window and the period for testing the prediction window. In practice, the training period represents a snapshot of the most recent history of the repository, used to formulate each blacklist for a contributor that is then expected to use the blacklist for the length of the prediction window. The sizes of these two windows are not necessarily equal. We will first describe experiments that use 5-day lengths for both the training window and the prediction window. We then present experiments that investigate the effects of the two windows' lengths on HPB quality.

Table 3: Hit Number Comparison between HPB, LWOL and GWOL

Window	GWOL total hit	LWOL total hit	HPB total hit	HPB/GWOL	HPB/LWOL
1	81937	85141	112009	1.36701	1.31557
2	83899	74206	115296	1.37422	1.55373
3	87098	96411	122256	1.40366	1.26807
4	80849	75127	115715	1.43125	1.54026
5	87271	88661	118078	1.353	1.33179
6	93488	73879	122041	1.30542	1.6519
7	100209	105374	133421	1.33143	1.26617
8	96541	91289	126436	1.30966	1.38501
9	94441	107717	128297	1.35849	1.19106
10	96702	94813	128753	1.33144	1.35797
11	97229	108137	131777	1.35533	1.21861
Average	90879 6851	90978 13002	123098 7193	1.36 0.04	1.37 0.15

Table 4: Hit Count Performance, HPB vs. (GWOL and LWOL), Length 1000 Entries

	Contributor	Average	Median	StdDev	Increase
	Percentage	Increase	Increase		Range
Improved vs. GWOL	90%	51	22	89	1 to 732
Poor vs. GWOL	7%	-27	-7	47	-1 to -206
Improved vs. LWOL	95%	75	36	90	1 to 491
Poor vs. LWOL	4%	-19	-9	28	-1 to -104

4.1 Hit Count Improvement

DShield logs submitted during the prediction window are used to determine how many sources included within a contributor's HPB are indeed encountered during that prediction window. We call this value the blacklist hit count. We view each blacklist address filter not encountered by the blacklist consumer as an opportunity cost to have prevented the deployment of other filters that could have otherwise blocked unwanted traffic. In this sense, we view our hit count metric as an important measure of the effectiveness of a blacklist formulation algorithm. Note that our HPBs are formulated with severity analysis while the other lists are not. As the severity analysis prefers malicious activities, we expect that the hits on the HPBs are more malicious.

To compare the three types of lists, we take 60 days of data, divided into twelve 5-day windows. We repeat the experiment 11 times using the -th window as the training window and the -th window as the testing window. In the training window, we construct HPB, LWOL, and GWOL. Then the three types of lists are tested on the data in the testing window.

Table 3 shows the total number of hits summed over the contributors for HPB, GWOL, and LWOL, respectively. It also shows the ratio of HPB hits over that of GWOL and LWOL. We see that in every window, HPB has more hits than GWOL and LWOL. Overall, HPBs predict 20-30% more hits than LWOL and GWOL. Note that there are quite large variances among the number of hits between time windows. Most of the variances, however, are not from our blacklist construction, rather they are from the variance among the number of attackers the networks experience in different testing windows.

Table 5: Top 200 Contributors' Hit Count Increases (Blacklist Length 1000)

	Increase	Increase	Increase	Increase
	Average	Median	StdDev	Range
vs. GWOL	129	78	124	40 to 732
vs. LWOL	183	188	93	59 to 491

The results in Table 3 show HPB's hit improvement over time windows. We now investigate the distribution of the HPB's hit improvement across contributors in one time window. We use two quantities for comparison. The first is the hit count improvement, which is simply the HPB hit count minus the hit count of the other list. The second comparative measure we used is the relative hit count improvement (RI), which is the ratio in percentage of the HPB hit count increase over the other blacklist hit count. If the other list hit count is zero we define RI to be 100x the HPB hit count, and if both hit counts are zero we set RI to 100.

Table 5 provides a summary of hit-count improvement for the 200 contributors where HPBs perform the best. The hit-count results for all the contributors are summarized in Table 4.

**Figure 7:** Hit Count Comparison of HPB and GWOL: Length 1000 Entries

**Figure 8:** Hit Count Comparison of HPB and LWOL: Length 1000 Entries

Figure 7 compares HPB to GWOL. The left panel of the figure plots the histogram showing the distribution of the hit improvement across the contributors. The x-axis indicates improvements, and the hight of the bars represents the number of contributors whose improvement fall in the corresponding bin. Bars left to represent contributors for whom the HPB has worse performance and bars on the right represent contributors for whom HPBs performed better. For most contributors, the improvment is positive. The largest improvement reaches 732. For only a few contributors, HPB performs worse in this time window.

The panel on the right of Figure 7 plots the RI (ratio % of HPB's hit count increase over GWOL's hit count) distribution. We sort the RI values and plot them against the contributors. We label the x-axis by cummulative percentage, i.e., a tick on x-axis represents the percentage of contributors that lie to the left of the tick. For example, the tick 20 means 20 percent of the contributors lie left to this tick. There are contributors for which the RI value can be more than 3900. Instead of showing such large RI values, we cut off the plot at RI value 300. From the plot, we see that there are about 20% of contributors for which the HPBs achieve an RI more than 100, i.e., the HPB at least doubled the GWOL hit count. For about half of the contributors, the HPBs have about 25% more hits (an RI of 25). The HPBs have more hits than GWOL for almost 90% of the contributors. Only for a few contributors (about 7%), HPBs perform worse. (We discuss the reasons why HPB may perform worse in Section 4.4.)

Figure 8 compares HPB hit counts to those of LWOL. The data are plotted in the same way as in Figure 7. Overall, HPBs demonstrate a performance advantage over LWOL. The IV and RI values also exhibit similar distributions. However, comparing Figures 8 and 7, we see that HPB has more hit improvement comparing to LWOL than to GWOL in this time window.

4.2 Prediction of New Attacks

One clear motivating assumption in secure collaborative defense strategies is that participants have the potential to prepare themselves from attacks that they have not yet encountered. We will say that a new attack occurs when a contributor produces a DShield log entry from a source that this contributor has never before reported. In this experiment, we show that HPB analysis provides contributors a potential to predict more new attacks than GWOL. (LWOL is not considered, since by definition it includes only attackers that are actively hitting the LWOL owner.) For each contributor, we construct two new HPB and GWOL lists with equal length of 1000 entries, such that no entries have been reported by the contributor during our training window. We call these lists HPB-local (HPB minus local) and GWOL-local (GWOL minus local), respectively. Figure 9 compares HPB-local and GWOL-local on their ability to predict on new attack sources for the local contributor. These hit number plots demonstrate that HPB-local provides substantial improvement over the predictive value of GWOL.

**Figure 9:** HPB-local Predicts More New Attacks Than GWOL-local

4.3 Timely Inclusion of Sources

By timely inclusion, we refer to the ability of a blacklist to incorporate addresses relevant to the blacklist owner before those addresses have saturated the Internet. To investigate the timeliness of the GWOL, LWOL, and the HPB we examine how many contributors need to report a particular attacker before it can be included into the respective blacklists. We focus our attention on the set of attackers within these blacklists that did carry out attacks during the prediction window. And we use the number of distinct victims (contributors) that a source attacked in the training window to measure the extent to which the source has saturated the Internet. Figure 10 plots the distribution of the number of distinct victims across different attackers on the three blacklists. As expected, the attackers that get selected on the GWOL were the most prolific in the training period. In particular, all the sources on the GWOL have attacked more than 20 contributors and almost 1/3 of them attacked more than 200 contributors. To some extent, these attackers have saturated the Internet with their activities. (DShield sensors are a very small sample of the Internet. A random attacker has to target many places to be picked up by the sensors.) The LWOLs select attacker addresses that focused on the local networks. Most of these addresses had attacked far fewer contributors. HPBs's distribution is close to that of the LWOL, hence allowing the incorporation of attackers that have not saturated the Internet.

**Figure 10:** Cumulative Distribution of Distinct Victim Numbers

4.4 Performance Consistency

The results in the above experiments show that the HPB provides an increase in hit count performance across the majority of all contributors. We now ask the following question: is the HPB's performance consistent for a given contributor over time? In this experiment, we investigate this consistency question.

We use a 60-day DShield dataset. We divide it into 12 time windows, . We generate blacklists from data in time window and test the lists on data in . For each contributor , we compare HPB with GWOL and obtain eleven improvement values for window to . We denote them
. We then define a consistency index (CI) for each contributor. If , we say that the HPB performs well for in window . Otherwise, we say that the HPB performs worse. CI is the difference between the number of windows in which HPB performs well and the ones in which HPB performs poorly, i.e., for each individual day in the prediction window. All lists are generated using data from a 5-day window prior to the prediction window. For all blacklists, the number of hits decreases along time. The HPB maintains an advantage over the entire duration of the prediction window. From this plot, we also see that the blacklists need to be refreshed frequently. In particular, there may be an almost 30% hit drop when the HPB is more than a week old.

The right panel of Figure 13 plots hit-number medians for four HPBs. These HPBs are generated in a slightly different way from the HPBs we used so far. In previous experiments, to generate an HPB, we produce the correlation matrix from a set of attack reports. Then the sources in the same set of reports are selected into HPBs based on their relevance. In this experiment, we construct the correlation matrix using reports from training windows of size 2, 5, 7, and 10 days. Then the sources that are in the reports within the 5-day window right before the prediction (test) window are picked based on their relevance. In this formulation, we exclude sources that appear only in reports from distant history; we view their extended silence to represent a significant loss in relevance. The remainder of the test is performed in the same way as the previous experiments, i.e., the hit counts are obtained in the following 5-day prediction window. The experiment result shows that there is a slight increase in the hit counts going from a 2-day training window to a 5-day training window. The hit counts then remain roughly the same for the other training-window size. This indicates that for most of the contributors, the correlation matrix can be quite stable over time.

5 An Example Blacklisting Service

In mid 2007, we deployed an initial prototype implementation of the HPB system, providing a subset of the features described in this paper. This initial deployment was packaged as a free Internet blacklisting service for DShield log contributors [22,23]. HPB blacklists are constructed for all contributors daily, and each contributor can download her individual HPB through her DShield website account. To date, we have had a relative small pool of HPB downloaders (roughly 70 users over the most 3 months). We now describe several aspects of fielding a practical and scalable implementation of an HPB system based on our initial deployment experiences. We present an assessment of the algorithm complexity, the DShield service implementation, and discuss some open questions raised from the open release of our service.

5.1 Algorithm Complexity

Because HPBs are constructed from a relatively high-volume corpus of security logs, our system must be prepared to process well over 100M log entries per day to process entries over the current 5-day training window. The bottleneck of the system is the relevance ranking. Therefore, our complexity discussion focuses on the ranking algorithm. There is always an amount of complexity that is linear to the size of the alert data. That is, let be the number of alerts in the data collection; we have a minimum complexity of . Our discussion will focus on other complexities incurred by the algorithm besides this linear-time requirement.

We denote by and the number of sources in the data collection and the number of contributors to the repository respectively. In practice, one can expect to be in the order of thousands while is much larger, typically in the tens of millions. We obtain and by going through the repository and doing simple accounting. The adjacency matrix requires the most work to construct. To obtain this matrix, we record every overlapped attack while going through the alert data and then perform standardization. The latter steps require us to go through the whole matrix, which results in complexity.

Besides going through the data, the most time-consuming step in the relevance estimate process is the computation that solves the linear equations in Equation 3. At first glance, because for each source , we have a linear system determined by Equation 3, it seems that we need to solve linear systems. This can be expensive as is very large. Further investigation shows that while is different per source , the part of the solution to Equation 3 is the same for all . Therefore, we need to compute it only once, which requires time by brute force or using more sophisticated methods [5]. Because is sparse, once we have , the total time to obtain the ranking scores for all the sources and all the contributors is . Assuming is much smaller than , the total complexity to make relevance ranking is . For a data set that contains a billion records contributed by a thousand sensors, generating a thousand rankings requires only several trillion operations (additions and multiplications). This can be easily handled by modern computers. In fact, in our experiments, with in the high tens of millions and on the order of one thousand, it takes less than 30 minutes to generate all contributor blacklists on an Intel Xeon 3.6 GHz machine.

5.2 The DShield Implementation

The pragmatics of deploying an HPB service through the DShield website are straightforward. DShield log contributors are already provided private web accounts in order to review their reports. However, to ease the automatic retrieval of HPBs, users are not required to log in via DShield's standard web account procedure. Instead, contributors wishing to access their individual HPBs can create account-specific hexadecimal tokens, and can then append this token to the HPB URL. This token has a number of advantages, particularly for developing and maintaining automated HPB retrieval scripts. That is, a user account password may be changed regularly, but the retrieval token (and script) will remain unaffected.

**Figure 14:** A Sample Blocklist from DShield Implementation

To provide further protection of the integrity and confidentiality of an HPB the user may also pull the HPB via https. A detached PGP signature can be retrieved in case https is not available or not considered a sufficient proof of authenticity.

HPBs are distributed using a simple tab-delimited format. The first column identifies the network address. The second column provides the netmask. Additional columns are used to provide more information about the respective offender, such as the name of the network and country of origin (or type of attacks seen). These additional columns are intended for human review of the HPB. Comments may be added to the blocklist. All comments start with a # mark. A sample blocklist is shown in Figure 14.

5.3 Gaming the System

As we have made efforts to implement, test, and advertise early versions of the HPB system, several open questions have been raised regarding the ability of adversaries to game the HPB system. That is, can an attacker contribute data to DShield with the intention of manipulating HPB production in ways that negatively harm HPB quality? Let us consider several questions that arise from the fact that HPBs are derived from volunteer sources, which may include dishonest contributors that are actively trying to harm or negatively manipulate HPB results.

Can an attacker cause a consumer to incorporate an unsuspecting victim address into a third party's HPB? Let us assume that attacker participates as one or more DShield contributors ( might register multiple IDs) and knows that consumer is also a DShield contributor and an active HPB user. Furthermore, would like to cause address to be inserted into consumer 's HPB. There are two potential strategies can pursue to achieve this goal. First, can spoof attacks as address , directing these attacks to other contributors that are highly correlated with . However, 's correlated contributor set is neither readily available to (unless is a DShield insider) or necessarily stable over time. More plausibly, could artificially cause his own contributor IDs to report the same attacks as . He can do this by attacking with a set of spoofed addresses, and then reporting similarly spoofed logs from his contributor IDs. Once a sufficient set of attack logs with identical spoofed attackers is reported by and , could then positively influence the likelihood that address will be inserted into 's HPB. While this is a possible threat, we also observe that similar attacks can be launched against GWOL and more trivially against LWOL. Furthermore, in the case of GWOL, will be inserted in all consumers' GWOLs, whereas A must launch this attack individually against each HPB consumer.

Can an attacker cause his own address to be excluded from a specific third-party HPB? Let us assume that would like to guarantee that address will not appear in 's HPB. This is very difficult for to guarantee. While may cause artificial alignment between his and 's logs using the alert spoofing method discussed above, cannot control what other addresses may also align with . If attacks other contributors that are aligned with , has the potential to enter 's HPB.

Can an attacker fully prevent or poison all HPB production? In short, yes. Data poisoning is a fundamental threat that arises in all volunteer contributor-based data centers, and is an inherently difficult threat to overcome. However, DShield does occasionally experience, and incorporate countermeasures for issues such as accidental flooding and sensor misconfiguration. DDoS threats also arise and are dealt with by DShield case by case.

HPB generation could also be specifically targeted by a malicious contributor that attempts to artificially inflate the number of attacker or victim addresses, which will increase the values of or , as described in our complexity analysis, Section 5.1. However, to sufficiently prohibit HPB production, the contributor would necessarily produce highly anomalous volumes of attackers (or sources) that would likely allow us to identify and (temporarily) filter this contributor.

6 Conclusion

In this paper, we introduced a new system to generate blacklists for contributors to a large-scale security-log sharing infrastructure. The system employs a link analysis method similar to Google's PageRank for blacklist formulation. It also integrates substantive log prefiltering and a severity metric that captures the degree to which an attacker's alert patterns match those of common malware-propagation behavior. Experimenting on a large corpus of real DShield data, we demonstrate that our blacklists have higher attacker hit rates, better new attacker prediction quality, and long-term performance stability.

In April of 2007, we released a highly predictive blacklist service at DShield.org. We view this service as a first experimental step toward a new direction of high-quality blacklist generation. We also believe that this service offers a new argument to help motivate the field of secure collaborative data sharing. In particular, it demonstrates that people who collaborate in blacklist formulation can share a greater understanding of attack source histories, and thereby derive more informed filtering policies. As future work, we will continue to evolve the HPB blacklisting system as our experience grows through managing the blacklist service.

7 Acknowledgments

This material is based upon work supported through the U.S. Army Research Office under the Cyber-TA Research Grant No. W911NF-06-1-0316.

Bibliography

1: ANAGNOSTAKIS, K. G., GREENWALD, M. B., IOANNIDIS, S., KEROMYTIS, A. D., AND LI, D.
A cooperative immunization system for an untrusting Internet.
In Proceedings of the 11th IEEE International Conference on Networks (ICON'03) (October 2003).
2: BRIN, S., AND PAGE, L.
The anatomy of a large-scale hypertextual Web search engine.
Computer Networks and ISDN Systems 30, 1-7 (1998), 107-117.
3: CAI, M., HWANG, K., KWOK, Y., SONG, S., AND CHEN, Y.
Collaborative Internet worm containment.
IEEE Security and Privacy Magazine 3, 3 (May/June 2005), 25-33.
4: CHEN, Z., AND JI, C.
Optimal worm-scanning method using vulnerable-host distributions.
International Journal of Security and Networks (IJSN) Special Issue on Computer & Network Security 2, 1 (2007).
5: COPPERSMITH, D., AND WINOGRAD, S.
Matrix multiplication via arithmetic progressions.
Journal of Symbolic Computation 9 (1990), 251-280.
6: HUMPHRYS, M.
The Internet in the 1980s.
http://www.computing.dcu.ie/~humphrys/net.80s.html, 2007.
7: INCORPORATED, G.
List of blacklists.
http://directory.google.com/Top/Computers/Internet/Abuse/Spam/Blacklists/, 2007.
8: INCORPORATED, G.
Live-feed anti-phishing blacklist.
http://sb.google.com/safebrowsing/update?version=goog-black-url:1:1, 2007.
9: JUNG, J., PAXSON, V., BERGER, A. W., AND BALAKRISHNAN, H.
Fast portscan detection using sequential hypothesis testing.
In IEEE Symposium on Security and Privacy 2004 (Oakland, CA, May 2004).
10: KATTI, S., KRISHNAMURTHY, B., AND KATABI, D.
Collaborating against common enemies.
In Proceedings of the ACM SIGCOMM/USENIX Internet Measurement Conference (October 2005).
11: KIM, H.-A., AND KARP, B.
Autograph: Toward automated, distributed worm signature detection.
In USENIX Security Symposium (2004), pp. 271-286.
12: LOCASTO, M., PAREKH, J., KEROMYTIS, A., AND STOLFO, S.
Towards collaborative security and P2P intrusion detection.
In Proceedings of the 2005 IEEE Workshop on Information Assurance and Security (June 2005).
13: M.GORI, AND PUCCI, A.
Itemrank: A random-walk based scoring algorithm for recommender engines.
In Proceedings of the International Joint Conference on Artificial Intelligence (January 2007).
14: PORRAS, P., BRIESEMEISTER, L., SKINNER, K., LEVITT, K., ROWE, J., AND TING, Y.
A hybrid quarantine defense.
In Proceedings of the 2004 ACM Workshop on Rapid Malcode (WORM) (October 2004).
15: RUOMING, P., YEGNESWARAN, V., BARFORD, P., PAXSON, V., AND PETERSON, L.
Characteristics of internet background radiation.
In Proceedings of ACM SIGCOMM/USENIX Internet Measurement Conference (October 2004).
16: THOMAS, R.
Bogon dotted decimal list v3.9.
http://www.cymru.com/Documents/bogon-dd.hml, October 2007.
17: ULLRICH, J.
DShield global worst offender list.
https://feeds.dshield.org/block.txt.
18: VIXIE, P., AND RAND, D.
Mail abuse prevention system (MAPS).
http://www.mail-abuse.com, 1997.
19: WISSNER-GROSS, A. D.
Preparation of topical readings lists from the link structure of Wikipedia.
In Proceedings of the IEEE International Conference on Advanced Learning Technology (July 2006).
20: YEGNESWARAN, V., BARFORD, P., AND ULLRICH, J.
Internet intrusions: global characteristics and prevalence.
In Proceedings of ACM SIGMETRICS (June 2003).
21: YEGNESWARAN, V., PORRAS, P., SAIDI, H., SHARIF, M., AND NARAYANAN, A.
The Cyber-TA compendium honeynet page.
http://www.cyber-ta.org/Honeynet.
22: ZHANG, J., PORRAS, P., AND ULLRICH, J.
The DSHIELD highly predictive blacklisting service.
http://www.dshield.org/hpbinfo.html.
23: ZHANG, J., PORRAS, P., AND ULLRICH, J.
A new service for increasing the effectiveness of network address blacklists.
In Proceedings of the 3rd Workshop of Steps to Reduce Unwanted Traffic on the Internet (June 2007).
24: ZHANG, J., PORRAS, P., AND ULLRICH, J.
Gaussian process learning for cyber-attack early warning.
to appear in Proceedings of SIAM Conference on data mining (2008).

Proceedings of the annual conference on USENIX Annual Technical Conference

2008-08-28T02:25:00.000-07:00

Mapping and visualizing the internet
Bill Cheswick, Hal Burch, Steve Branigan
Pages: 1 - 1

Additional Information:

full citation, abstract, references, cited by, index terms

Measuring and characterizing system behavior using kernel-level event logging
Karim Yaghmour, Michel R. Dagenais
Pages: 2 - 2

Additional Information:

full citation, abstract, references, cited by, index terms

Pandora: a flexible network monitoring platform
Simon Patarin, Mesaac Makpangou
Pages: 3 - 3

Additional Information:

full citation, abstract, references, index terms

A comparison of file system workloads
Drew Roselli, Jacob R. Lorch, Thomas E. Anderson
Pages: 4 - 4

Additional Information:

full citation, abstract, references, cited by, index terms

FiST: a language for stackable file systems
Erez Zadok, Jason Nieh
Pages: 5 - 5

Additional Information:

full citation, abstract, references, cited by, index terms

Journaling versus soft updates: asynchronous meta-data protection in file systems
Margo I. Seltzer, Gregory R. Ganger, M. Kirk McKusick, Keith A. Smith, Craig A. N. Soules, Christopher A. Stein
Pages: 6 - 6

Additional Information:

full citation, abstract, references, cited by, index terms

Lexical file names in plan 9 or getting dot-dot right
Rob Pike
Pages: 7 - 7

Additional Information:

full citation, abstract, references, index terms

Gecko: tracking a very large billing system
Andrew Hume, Scott Daniels, Angus MacLellan
Pages: 8 - 8

Additional Information:

full citation, abstract, references, index terms

Extended data formatting using Sfio
Glenn S. Fowler, David G. Korn, Kiem-Phong Vo
Pages: 9 - 9

Additional Information:

full citation, abstract, references, index terms

Virtual services: a new abstraction for server consolidation
John Reumann, Ashish Mehra, Kang G. Shin, Dilip Kandlur
Pages: 10 - 10

Additional Information:

full citation, abstract, references, index terms

Location-aware scheduling with minimal infrastructure
John Heidemann, Dhaval Shah
Pages: 11 - 11

Additional Information:

full citation, abstract, references, index terms

Distributed computing: moving from CGI to CORBA
James FitzGibbon, Tim Strike
Pages: 12 - 12

Additional Information:

full citation, abstract, references, index terms

Outwit: Unix tool-based programming meets the windows world
Diomidis D. Spinellis
Pages: 13 - 13

Additional Information:

full citation, abstract, references, index terms

Plumbing and other utilities
Rob Pike
Pages: 14 - 14

Additional Information:

full citation, abstract, references, index terms

Integrating a command shell into a web browser
Robert C. Miller, Brad A. Myers
Pages: 15 - 15

Additional Information:

full citation, abstract, references, cited by, index terms

Operating system support for multi-user, remote, graphical interaction
Alexander Ya-Li Wong, Margo Seltzer
Pages: 16 - 16

Additional Information:

full citation, abstract, references, index terms

Techniques for the design of java operating systems
Godmar Back, Patrick Tullmann, Leigh Stoller, Wilson C. Hsieh, Jay Lepreau
Pages: 17 - 17

Additional Information:

full citation, abstract, references, index terms

Signaled receiver processing
José Brustoloni, Eran Gabber, Abraham Silberschatz, Amit Singh
Pages: 18 - 18

Additional Information:

full citation, abstract, references, index terms

DITools: application-level support for dynamic extension and flexible composition
Albert Serra, Nacho Navarro, Toni Cortes
Pages: 19 - 19

Additional Information:

full citation, abstract, references, index terms

Portable multithreading: the signal stack trick for user-space thread creation
Ralf S. Engelschall
Pages: 20 - 20

Additional Information:

full citation, abstract, references, cited by, index terms

Transparent run-time defense against stack smashing attacks
Arash Baratloo, Navjot Singh, Timothy Tsai
Pages: 21 - 21

Additional Information:

full citation, abstract, references, cited by, index terms

Towards availability benchmarks: a case study of software raid systems
Aaron Brown, David A. Patterson
Pages: 22 - 22

Additional Information:

full citation, abstract, references, cited by, index terms

Performing replacement in modem pools
Yannis Smaragdakis, Paul Wilson
Pages: 23 - 23

Additional Information:

full citation, abstract, references, index terms

Auto-diagnosis of field problems in an appliance operating system
Gaurav Banga
Pages: 24 - 24

Additional Information:

full citation, abstract, references, cited by, index terms

Dynamic function placement for data-intensive cluster computing
Khalil Amiri, David Petrou, Gregory R. Ganger, Garth A. Gibson
Pages: 25 - 25

Additional Information:

full citation, abstract, references, cited by, index terms

Scalable content-aware request distribution in cluster-based networks servers
Mohit Aron, Darren Sanders, Peter Druschel, Willy Zwaenepoel
Pages: 26 - 26

Additional Information:

full citation, abstract, references, cited by, index terms

Isolation with flexibility: a resource management framework for central servers
David G. Sullivan, Margo I. Seltzer
Pages: 27 - 27

Additional Information:

full citation, abstract, references, cited by, index terms

Swarm: a log-structured storage system for Linux
Ian Murdock, John H. Hartman
Pages: 28 - 28

Additional Information:

full citation, abstract, references, index terms

DMFS: a data migration file system for NetBSD
William Studenmund
Pages: 29 - 29

Additional Information:

full citation, abstract, references, index terms

A 3-tier RAID storage system with RAID1, RAID5 and compressed RAID5 for Linux
K. Gopinath, Nitin Muppalaneni, N. Suresh Kumar, Pankaj Risbood
Pages: 30 - 30

Additional Information:

full citation, abstract, references, index terms

Extending internet services Via LDAP
James E. Dutton
Pages: 31 - 31

Additional Information:

full citation, abstract, references, index terms

MOSIX: how Linux clusters solve real world problems
Steve McClure, Richard Wheeler
Pages: 32 - 32

Additional Information:

full citation, abstract, references, index terms

Webmin a web-based system administration tool for unix
Jamie Cameron
Pages: 33 - 33

Additional Information:

full citation, abstract, index terms

Porting the SGI XFS file system to Linux
Jim Mostek, Bill Earl, Steven Levine, Steve Lord, Russell Cattelan, Ken McDonell, Ted Kline, Brian Gaffey, Rajagopal Ananthanarayanan
Pages: 34 - 34

Additional Information:

full citation, abstract, references, index terms

LinLogFS: a log-structured filesystem for Linux
Christian Czezatke, M. Anton Ertl
Pages: 35 - 35

Additional Information:

full citation, abstract, references, index terms

Unix file system extensions in the GNOME environment
Ettore Perazzoli
Pages: 36 - 36

Additional Information:

full citation, references, index terms

Protocol independence using the sockets API
Craig Metz
Pages: 37 - 37

Additional Information:

full citation, abstract, references, index terms

Scalable network I/O in Linux
Niels Provos, Chuck Lever
Pages: 38 - 38

Additional Information:

full citation, abstract, references, index terms

Accept() scalability on Linux
Stephen P. Molloy, Chuck Lever
Pages: 39 - 39

Additional Information:

full citation, abstract, references, index terms

Permanent web publishing
David S. H. Rosenthal, Vicky Reich
Pages: 40 - 40

Additional Information:

full citation, abstract, references, index terms

The globe distribution network
A. Bakker, E. Amade, G. Ballintijn, I. Kuz, P. Verkaik, I. van der Wijk, M. van Steen, A. S. Tanenbaum
Pages: 41 - 41

Additional Information:

full citation, abstract, references, cited by, index terms

Open information pools
Johan Pouwelse
Pages: 42 - 42

Additional Information:

full citation, abstract, references, index terms

The GNOME canvas: a generic engine for structured graphics
Federico Mena-Quintero, Raph Levien
Pages: 43 - 43

Additional Information:

full citation, abstract, references, index terms

Efficiently scheduling X clients
Keith Packard
Pages: 44 - 44

Additional Information:

full citation, abstract, references, index terms

The AT&T AST OpenSource software collection
Glenn S. Fowler, David G. Korn, Stephen S. North, Kiem-Phong Vo
Pages: 45 - 45

Additional Information:

full citation, abstract, references, index terms

Implementing internet key exchange (IKE)
Niklas Hallqvist, Angelos D. Keromytis
Pages: 46 - 46

Additional Information:

full citation, abstract, references, index terms

Transparent network security policy enforcement
Angelos D. Keromytis, Jason L. Wright
Pages: 47 - 47

Additional Information:

full citation, abstract, references, index terms

Safety checking of kernel extensions
Craig Metz
Pages: 48 - 48

Additional Information:

full citation, abstract, references, index terms

An operating system in java for the Lego Mindstorms RCX microcontroller
Pekka Nikander
Pages: 49 - 49

Additional Information:

full citation, abstract, references, index terms

LAP: a little language for OS emulation
Donn M. Seeley
Pages: 50 - 50

Additional Information:

full citation, abstract, references, index terms

Traffic data repository at the WIDE project
Kenjiro Cho, Koushirou Mitsuya, Akira Kato
Pages: 51 - 51

Additional Information:

full citation, abstract, references, cited by, index terms

JEmacs: the Java/scheme-based Emacs
Per Bothner
Pages: 52 - 52

Additional Information:

full citation, abstract, references, index terms

A new rendering model for X
Keith Packard
Pages: 53 - 53

Additional Information:

full citation, abstract, references, index terms

UBC: an efficient unified I/O and memory caching subsystem for NetBSD
Chuck Silvers
Pages: 54 - 54

Additional Information:

full citation, abstract, references, index terms

Mbuf issues in 4.4BSD IPv6/IPsec support-experiences from KAME IPv6/IPsec implementation
Jun-ichiro Itojun Hagino
Pages: 55 - 55

Additional Information:

full citation, abstract, references, index terms

malloc() performance in a multithreaded Linux environment
Chuck Lever, David Boreham
Pages: 56 - 56

Additional Information:

full citation, abstract, references, index terms

Network stack

2008-08-26T04:55:00.000-07:00

There are basically three different attacks that can be performed against TCP by means of ICMP: blind connection-reset attacks, blind throughput-reduction attacks, and blind-performance degrading attacks. There are general counter-measures that you can implement for ICMP-based attacks, and attack-specific ones. In OpenBSD, we implement both.

The general counter-measures are based on performing checks on the received ICMP messages. Basically, we check that the TCP sequence number contained in the ICMP payload corresponds to data already sent but not yet acknowledged. The rationale is obvious: if the TCP sequence number contained in the ICMP payload corresponds to data already sent but already acknowledged, then the error message must have been forged, caused by an old TCP segment, or corrupted, and thus should not be honored. If the TCP sequence number contained in the ICMP payload corresponds to data not yet sent, then the error message must have been forged, or corrupted, and thus should not be honored, either.

This is a general validation check for ICMP messages. However, it doesn't eliminate the vulnerabilities: it just requires more work (or luck) on the side of the attacker. Therefore, in OpenBSD we implement, in addition to this general validation check, attack-specific counter-measures that completely eliminate the vulnerabilities.

The blind throughput-reduction attack is performed by means of ICMP Source Quench messages. These messages were originally introduced for flow control and congestion control in IP networks. An attacker can use ICMP Source Quench messages to fool the attacked host into thinking the network is congested, and as a result, the attacked system will reduce the rate at which it is sending information. However, if you look at it carefully, TCP implements its own flow-control mechanism, and thus does not rely on ICMP Source Quench messages for performing flow-control. Also, ICMP Source Quench messages have been considered for a long time to be ineffective and unfair for controlling congestion. Thus, the counter-measure for the blind throughput-reduction attack is very simple: ignore ICMP Source Quench messages meant for TCP connections.

The blind performance-degrading attack is an attack against the Path-MTU Discovery mechanism implemented by TCP. Basically, an attacker will send a "fragmentation needed and DF bit set" ICMP error message that advertises a small Next-Hop MTU to the victim host, to fool it into thinking it is sending packets that are too large to be forwarded without fragmentation. As a result, the attacked system will reduce the size of the packets it sends, accordingly.

The counter-measure we implement for this attack works as follows. First, we keep track of the largest packet size that has so far been sent for this connection. If the Next-Hop MTU claimed by the ICMP error message is larger than that size, then we simply ignore the error message. Second, we keep track of the largest packet size that has so far been acknowledged for this connection (say, "maxsizeacked"). This allows us to divide Path-MTU Discovery into two phases: Initial Path-MTU Discovery, and Path-MTU Update. This two-phase separation allows us to quickly discover the Path-MTU for a fresh connection (and thus not affect interactive applications), while still being resistant to the discussed attack.

Whenever we receive an ICMP "fragmentation needed and DF bit set" (and provided it has passed all the general validation checks), we compare the advertised Next-Hop MTU with "maxsizeacked". If it's larger than "maxsizeacked", then it means we are in the Initial Path-MTU phase (that is, we are trying to find out the Path-MTU of this connection for the first time), and thus honor the ICMP message immediately. If the advertised Next-Hop MTU is smaller than "maxsizeacked", then it means we are in the Path-MTU Update phase, trying to change the assumed Path-MTU for this connection. In this phase, we should be much more cautious when processing ICMP messages. The error messages could be legitimate (and sent because the packets that correspond to the connection are now being forwarded through a different Internet path), or they could be part of an attack. If the error messages were legitimate, then the corresponding data (those claimed by the TCP sequence number contained in the ICMP payload) should have been dropped by the Internet router that sent the ICMP error message. Therefore, we wait for an RTO (TCP's retransmission timeout), and see if the corresponding data gets acknowledged. If the corresponding data times out, then it means the error message must be legitimate, and thus we honor it, updating the Path-MTU for the connection accordingly. If while we are waiting for a RTO those data get acknowledged, then it means our data are still getting to the remote system, and thus the ICMP error message must have been forged. Therefore, we simply drop the ICMP error message we had received.

The implication of this counter-measure is that in order to perform the blind performance-degrading attack, the attacker should be a "man in the middle," and should be not only lucky enough to hit the TCP window, but should also be able to selectively drop the packets that correspond to the attacked connection. This is so that either the data segments don't get to the remote endpoint, or the TCP acknowledgements sent by the remote end-point don't get [to] the attacked system. If an attacker were able to do this, he would have already DoS'ed the connection, and thus wouldn't have the need to perform the attack.

As for the blind connection-reset attack, BSD-derived implementations are not vulnerable to it. BSD-derived systems never abort established connections in response to ICMP messages. This has been the traditional BSD behavior for quite a long time.

Is there already any other OS that includes them?

Fernando Gont: OpenBSD has been the first operating system to implement a complete set of counter-measures for ICMP-based attacks. Following OpenBSD, NetBSD fortunately ported OpenBSD's counter-measures to their system.

Other systems have followed us, implementing only some of the OpenBSD counter-measures. Unfortunately, it seems they have failed to understand the importance of the counter-measure for the blind performance-degrading (PMTUD) attack. Some vendors/projects simply seem to think that the TCP sequence number check is enough to protect a system from this attack. Others simply wanted to see a working (and tested) implementation, and were not willing to take the lead. At the c2k5 Hackathon we implemented the counter-measure for the PMTUD attack, and tested it extensively. So there I think are no more excuses to vendors: they can follow us, or continue ignoring the problem.

What about Linux?

Fernando Gont: In the same way as BSD-derived systems, they were already treating the so-called ICMP "hard errors" as "soft errors," so they were not vulnerable to the ICMP-based blind connection-reset attack.

Linux had also been implementing the basic TCP sequence number check for several years.

When I published my IETF internet-draft "ICMP attacks against TCP," they removed support for ICMP Source Quench messages, as recommended in my draft. They were very responsive on this particular fix.

However, they have not yet implemented the full counter-measure for the PMTUD attack. They basically said they first wanted the counter-measure to be tested. So maybe that now that OpenBSD ships with this counter-measure, and that NetBSD has followed us, they will finally implement it.

The counter-measure for the PMTUD attack is particularly important. First, because those ICMP messages used for PMTUD are probably the only ones you cannot filter. Second, because even if you protect your TCP connections by means of the TCP MD5 option, or by means of IPSec, you still need the Path-MTU Discovery mechanism. And, at that point, PMTUD becomes "the weakest link in the chain".

There are scenarios in which IPSec-secured connections could get frozen by means of the PMTUD attack. If you count the number of bytes required for headers (IP+IPSec+TCP), along with the number of bytes required for IP and TCP options, and realize that the minimum IPv4 MTU is 68 (i.e., a "fragmentation needed and DF bit set" ICMP message can report a Next-Hop MTU as small as 68 bytes), you come to the conclusion that the attacked connection could become frozen, or the TCP/IP stack may end up behaving in some unexpected manner.

I must acknowledge that Alan Cox and David S. Miller read the draft, and took the time to provide feedback and contribute to make my internet-draft a better one. This is something I appreciate. Most other vendors/projects didn't care to provide feedback, or anything.

Vulnerability Scanners

2008-07-31T04:26:00.001-07:00

Each tool is described by one ore more attributes:

	Did not appear on the 2003 list
	Generally costs money. A free limited/demo/trial version may be available.
	Works natively on Linux
	Works natively on OpenBSD, FreeBSD, Solaris, and/or other UNIX variants
	Works natively on Apple Mac OS X
	Works natively on Microsoft Windows
	Features a command-line interface
	Offers a GUI (point and click) interface
	Source code available for inspection.

Please send updates and suggestions (or better tool logos) to Fyodor. If your tool is featured or you think your site visitors might enjoy this list, you are welcome to use our link banners. Here is the list, starting with the most popular:

Nessus : Premier UNIX vulnerability assessment tool
Nessus was a popular free and open source vulnerability scanner until they closed the source code in 2005 and removed the free version ("registered feed") in 2008. While the cost has gone from free to $1200/year, it is still the best UNIX vulnerability scanner available and among the best to run on Windows. Nessus is constantly updated, with more than 20,000 plugins. Key features include remote and local (authenticated) security checks, a client/server architecture with a GTK graphical interface, and an embedded scripting language for writing your own plugins or understanding the existing ones.

GFI LANguard : A commercial network security scanner for Windows
GFI LANguard scans IP networks to detect what machines are running. Then it tries to discern the host OS and what applications are running. I also tries to collect Windows machine's service pack level, missing security patches, wireless access points, USB devices, open shares, open ports, services/applications active on the computer, key registry entries, weak passwords, users and groups, and more. Scan results are saved to an HTML report, which can be customized/queried. It also includes a patch manager which detects and installs missing patches. A free trial version is available, though it only works for up to 30 days.

#3	Retina : Commercial vulnerability assessment scanner by eEye Like Nessus, Retina's function is to scan all the hosts on a network and report on any vulnerabilities found. It was written by eEye, who are well known for their security research.

Core Impact : An automated, comprehensive penetration testing product
Core Impact isn't cheap (be prepared to spend tens of thousands of dollars), but it is widely considered to be the most powerful exploitation tool available. It sports a large, regularly updated database of professional exploits, and can do neat tricks like exploiting one machine and then establishing an encrypted tunnel through that machine to reach and exploit other boxes. If you can't afford Impact, take a look at the cheaper Canvas or the excellent and free Metasploit Framework. Your best bet is to use all three.

Also categorized as: vulnerability exploitation tools

#5	ISS Internet Scanner : Application-level vulnerability assessment Internet Scanner started off in '92 as a tiny open source scanner by Christopher Klaus. Now he has grown ISS into a billion-dollar company with a myriad of security products.

X-scan : A general scanner for scanning network vulnerabilities
A multi-threaded, plug-in-supported vulnerability scanner. X-Scan includes many features, including full NASL support, detecting service types, remote OS type/version detection, weak user/password pairs, and more. You may be able to find newer versions available here if you can deal with most of the page being written in Chinese.

#7	Sara : Security Auditor's Research Assistant SARA is a vulnerability assessment tool that was derived from the infamous SATAN scanner. They try to release updates twice a month and try to leverage other software created by the open source community (such as Nmap and Samba).

QualysGuard : A web-based vulnerability scanner
Delivered as a service over the Web, QualysGuard eliminates the burden of deploying, maintaining, and updating vulnerability management software or implementing ad-hoc security applications. Clients securely access QualysGuard through an easy-to-use Web interface. QualysGuard features 5,000+ unique vulnerability checks, an Inference-based scanning engine, and automated daily updates to the QualysGuard vulnerability KnowledgeBase.

#9	SAINT : Security Administrator's Integrated Network Tool SAINT is another commercial vulnerability assessment tool (like Nessus, ISS Internet Scanner, or Retina). It runs on UNIX and used to be free and open source, but is now a commercial product.

#10

MBSA : Microsoft Baseline Security Analyzer
Microsoft Baseline Security Analyzer (MBSA) is an easy-to-use tool designed for the IT professional that helps small and medium-sized businesses determine their security state in accordance with Microsoft security recommendations and offers specific remediation guidance. Built on the Windows Update Agent and Microsoft Update infrastructure, MBSA ensures consistency with other Microsoft management products including Microsoft Update (MU), Windows Server Update Services (WSUS), Systems Management Server (SMS) and Microsoft Operations Manager (MOM). Apparently MBSA on average scans over 3 million computers each week.

Password Crackers

2008-07-31T04:26:00.000-07:00

Each tool is described by one ore more attributes:

	Did not appear on the 2003 list
	Generally costs money. A free limited/demo/trial version may be available.
	Works natively on Linux
	Works natively on OpenBSD, FreeBSD, Solaris, and/or other UNIX variants
	Works natively on Apple Mac OS X
	Works natively on Microsoft Windows
	Features a command-line interface
	Offers a GUI (point and click) interface
	Source code available for inspection.

Cain and Abel : The top password recovery tool for Windows
UNIX users often smugly assert that the best free security tools support their platform first, and Windows ports are often an afterthought. They are usually right, but Cain & Abel is a glaring exception. This Windows-only password recovery tool handles an enormous variety of tasks. It can recover passwords by sniffing the network, cracking encrypted passwords using Dictionary, Brute-Force and Cryptanalysis attacks, recording VoIP conversations, decoding scrambled passwords, revealing password boxes, uncovering cached passwords and analyzing routing protocols. It is also well documented.

Also categorized as: packet sniffers

John the Ripper : A powerful, flexible, and fast multi-platform password hash cracker
John the Ripper is a fast password cracker, currently available for many flavors of Unix (11 are officially supported, not counting different architectures), DOS, Win32, BeOS, and OpenVMS. Its primary purpose is to detect weak Unix passwords. It supports several crypt(3) password hash types which are most commonly found on various Unix flavors, as well as Kerberos AFS and Windows NT/2000/XP LM hashes. Several other hash types are added with contributed patches. You will want to start with some wordlists, which you can find here, here, or here.

THC Hydra : A Fast network authentication cracker which support many different services
When you need to brute force crack a remote authentication service, Hydra is often the tool of choice. It can perform rapid dictionary attacks against more then 30 protocols, including telnet, ftp, http, https, smb, several databases, and much more. Like THC Amap this release is from the fine folks at THC.

Aircrack : The fastest available WEP/WPA cracking tool
Aircrack is a suite of tools for 802.11a/b/g WEP and WPA cracking. It can recover a 40 through 512-bit WEP key once enough encrypted packets have been gathered. It can also attack WPA 1 or 2 networks using advanced cryptographic methods or by brute force. The suite includes airodump (an 802.11 packet capture program), aireplay (an 802.11 packet injection program), aircrack (static WEP and WPA-PSK cracking), and airdecap (decrypts WEP/WPA capture files).

Also categorized as: wireless tools

L0phtcrack : Windows password auditing and recovery application
L0phtCrack, also known as LC5, attempts to crack Windows passwords from hashes which it can obtain (given proper access) from stand-alone Windows NT/2000 workstations, networked servers, primary domain controllers, or Active Directory. In some cases it can sniff the hashes off the wire. It also has numerous methods of generating password guesses (dictionary, brute force, etc). LC5 was discontinued by Symantec in 2006, but you can still find the LC5 installer floating around. The free trial only lasts 15 days, and Symantec won't sell you a key, so you'll either have to cease using it or find a key generator. Since it is no longer maintained, you are probably better off trying Cain and Abel, John the Ripper, or Ophcrack instead.

Airsnort : 802.11 WEP Encryption Cracking Tool
AirSnort is a wireless LAN (WLAN) tool that recovers encryption keys. It was developed by the Shmoo Group and operates by passively monitoring transmissions, computing the encryption key when enough packets have been gathered. You may also be interested in the similar Aircrack.

Also categorized as: wireless tools

SolarWinds : A plethora of network discovery/monitoring/attack tools
SolarWinds has created and sells dozens of special-purpose tools targeted at systems administrators. Security-related tools include many network discovery scanners, an SNMP brute-force cracker, router password decryption, a TCP connection reset program, one of the fastest and easiest router config download/upload applications available and more.

Also categorized as: traffic monitoring tools

Pwdump : A window password recovery tool
Pwdump is able to extract NTLM and LanMan hashes from a Windows target, regardless of whether Syskey is enabled. It is also capable of displaying password histories if they are available. It outputs the data in L0phtcrack-compatible form, and can write to an output file.

RainbowCrack : An Innovative Password Hash Cracker
The RainbowCrack tool is a hash cracker that makes use of a large-scale time-memory trade-off. A traditional brute force cracker tries all possible plaintexts one by one, which can be time consuming for complex passwords. RainbowCrack uses a time-memory trade-off to do all the cracking-time computation in advance and store the results in so-called "rainbow tables". It does take a long time to precompute the tables but RainbowCrack can be hundreds of times faster than a brute force cracker once the precomputation is finished.

#10

Brutus : A network brute-force authentication cracker
This Windows-only cracker bangs against network services of remote systems trying to guess passwords by using a dictionary and permutations thereof. It supports HTTP, POP3, FTP, SMB, TELNET, IMAP, NTP, and more. No source code is available. UNIX users should take a look at THC Hydra.

Web Vulnerability Scanners

2008-07-31T04:25:00.001-07:00

Each tool is described by one ore more attributes:

	Did not appear on the 2003 list
	Generally costs money. A free limited/demo/trial version may be available.
	Works natively on Linux
	Works natively on OpenBSD, FreeBSD, Solaris, and/or other UNIX variants
	Works natively on Apple Mac OS X
	Works natively on Microsoft Windows
	Features a command-line interface
	Offers a GUI (point and click) interface
	Source code available for inspection.

Nikto : A more comprehensive web scanner
Nikto is an open source (GPL) web server scanner which performs comprehensive tests against web servers for multiple items, including over 3200 potentially dangerous files/CGIs, versions on over 625 servers, and version specific problems on over 230 servers. Scan items and plugins are frequently updated and can be automatically updated (if desired). It uses Whisker/libwhisker for much of its underlying functionality. It is a great tool, but the value is limited by its infrequent updates. The newest and most critical vulnerabilities are often not detected.

Paros proxy : A web application vulnerability assessment proxy
A Java based web proxy for assessing web application vulnerability. It supports editing/viewing HTTP/HTTPS messages on-the-fly to change items such as cookies and form fields. It includes a web traffic recorder, web spider, hash calculator, and a scanner for testing common web application attacks such as SQL injection and cross-site scripting.

WebScarab : A framework for analyzing applications that communicate using the HTTP and HTTPS protocols
In its simplest form, WebScarab records the conversations (requests and responses) that it observes, and allows the operator to review them in various ways. WebScarab is designed to be a tool for anyone who needs to expose the workings of an HTTP(S) based application, whether to allow the developer to debug otherwise difficult problems, or to allow a security specialist to identify vulnerabilities in the way that the application has been designed or implemented.

WebInspect : A Powerful Web Application Scanner
SPI Dynamics' WebInspect application security assessment tool helps identify known and unknown vulnerabilities within the Web application layer. WebInspect can also help check that a Web server is configured properly, and attempts common web attacks such as parameter injection, cross-site scripting, directory traversal, and more.

Whisker/libwhisker : Rain.Forest.Puppy's CGI vulnerability scanner and library
Libwhisker is a Perl module geared geared towards HTTP testing. It provides functions for testing HTTP servers for many known security holes, particularly the presence of dangerous CGIs. Whisker is a scanner that used libwhisker but is now deprecated in favor of Nikto which also uses libwhisker.

Burpsuite : An integrated platform for attacking web applications
Burp suite allows an attacker to combine manual and automated techniques to enumerate, analyze, attack and exploit web applications. The various burp tools work together effectively to share information and allow findings identified within one tool to form the basis of an attack using another.

Wikto : Web Server Assessment Tool
Wikto is a tool that checks for flaws in webservers. It provides much the same functionality as Nikto but adds various interesting pieces of functionality, such as a Back-End miner and close Google integration. Wikto is written for the MS .NET environment and registration is required to download the binary and/or source code.

Acunetix Web Vulnerability Scanner : Commercial Web Vulnerability Scanner
Acunetix WVS automatically checks your web applications for vulnerabilities such as SQL Injection, cross site scripting, and weak password strength on authentication pages. Acunetix WVS boasts a comfortable GUI and an ability to create professional website security audit reports.

Watchfire AppScan : Commercial Web Vulnerability Scanner
AppScan provides security testing throughout the application development lifecycle, easing unit testing and security assurance early in the development phase. Appscan scans for many common vulnerabilities, such as cross site scripting, HTTP response splitting, parameter tampering, hidden field manipulation, backdoors/debug options, buffer overflows and more.

#10

N-Stealth : Web server scanner
N-Stealth is a commercial web server security scanner. It is generally updated more frequently than free web scanners such as Whisker/libwhisker and Nikto, but do take their web site with a grain of salt. The claims of "30,000 vulnerabilities and exploits" and "Dozens of vulnerability checks are added every day" are highly questionable. Also note that essentially all general VA tools such as Nessus, ISS Internet Scanner, Retina, SAINT, and Sara include web scanning components. They may not all be as up-to-date or flexible though. N-Stealth is Windows only and no source code is provided.