Categories
Publications Technical Report

new tech report “Parametric Methods for Anomaly Detection in Aggregate Traffic”

We just posted a tech report “Parametric Methods for Anomaly Detection in Aggregate Traffic” at <ftp://ftp.isi.edu/isi-pubs/tr-663.pdf>. This paper represents quite a bit of work looking at how to apply parametric detection as part of the NSF-sponsored MADCAT project.

From the abstract:

This paper develops parametric methods to detect network anomalies using only aggregate traffic statistics in contrast to other works requiring flow separation, even when the anomaly is a small fraction of the total traffic.  By adopting simple statistical models for anomalous and background traffic in the time-domain, one can estimate model parameters in real-time, thus obviating the need for a long training phase or manual parameter tuning.  The detection mechanism uses a sequential probability ratio test, allowing for control over the false positive rate while examining the trade-off between detection time and the strength of an anomaly.  Additionally, it uses both traffic-rate and packet-size statistics, yielding a bivariate model that eliminates most false positives.  The method is analyzed using the bitrate SNR metric, which is shown to be an effective metric for anomaly detection.  The performance of the bPDM is evaluated in three ways:  first, synthetically generated traffic provides for a controlled comparison of detection time as a function of the anomalous level of traffic.  Second, the approach is shown to be able to detect controlled artificial attacks over the USC campus network in varying real traffic mixes.  Third, the proposed algorithm achieves rapid detection of real denial-of-service attacks as determined by the replay of previously captured network traces.  The method developed in this paper is able to detect all attacks in these scenarios in a few seconds or less.

Citation: Gautam Thatte, Urbashi Mitra, and John Heidemann. Parametric Methods for Anomaly Detection in Aggregate Traffic. Technical Report N. ISI-TR-2009-663, USC/Information Sciences Institute, August, 2009. http://www.isi.edu/~johnh/PAPERS/Thatte09a.html.

Categories
Announcements Collaborations Software releases

ANT extensions for bzip2-splitting to appear in Hadoop

The ANT project is happy to announce that our extensions to Hadoop to support splitting of bzip2-compressed files have been accepted to appear in the next Hadoop release (will be 0.21.0).

Support for compression is important in map/reduce because it reduces the amount of I/O, and because important input files (for us, our Internet address censuses) are provided in compressed format.

Splitting is important in map/reduce, because splitting allows many computers to process parts of a few big files.  Since the whole point of Hadoop and map/reduce is processing big files (for us, 4GB or more) with many computers (for us, dozens to hundreds), splitting is really essential.

Until now, Hadoop did not support splitting of compressed files.  Instead, if input data was compressed, you get at most one computer per file.  Some work-arounds were possible, but basically unpleasant, and often requiring that one rewrite all the input data is some other format.

Our extensions (see HADOOP-4012 and MAPREDUCE-830, plus HADOOP-3646 that went into 0.19.0) support Hadoop execution over bzip2 files with automatic splitting.  Getting this done was trickier than one might expect:  Hadoop really wants to decide where to split files, yet bzip2 can only support splits at specific locations that are different, and users don’t care about either of these but instead only about their record boundaries.  Fortunately, we were able to align all of these constraints, and deal with the corner cases that inevitably arise.  (What if the bzip2 marker appears in normal data?  What happens when markers exactly align, or are off-by-one?)

Abdul Qadeer did this work in 2008, working with Yuri Pradkin and me (John Heidemann), and continued to work with the patch through its getting committed.  We especially thank Chris Douglas at Yahoo for shepherding patch through the Hadoop bug tracking system, including helping clean it up and add test cases.  And we thank Doug Cutting for initially suggesting bzip2 as a splittable compression scheme.

This work was supported by NSF through the MR-Net research project (CNS-0823774).

Categories
Publications Technical Report

new tech report “Understanding Address Usage in the Visible Internet”

We just posted a tech report “Understanding Address Usage in the Visible Internet” at <ftp://ftp.isi.edu/isi-pubs/tr-656.pdf>.

The abstract summarizes the tech report:

Although the Internet is widely used today, there are few sound estimates of network demographics. Decentralized network management means questions about Internet use cannot be answered by a central authority, and firewalls and sensitivity to probing means that active measurements must be done carefully and validated against known data. Building on frequent ICMP probing of 1% of the Internet address space, we develop a clustering algorithm to estimate how Internet addresses are used. We show that adjacent addresses often have similar characteristics and are used for similar purposes (61% of addresses we probe are consistent blocks of 64 neighbors or more). We then apply this block-level clustering to provide data to explore several open questions in how networks are managed. First, the nearing full allocation of IPv4 addresses makes it increasingly important to estimate the costs of better management of the IPv4 space as a component of an IPv6 transition. We provide about how effectively network addresses blocks appear to be used, finding that a significant number of blocks are only lightly used (about one-fifth of /24 blocks ha
ve most addresses in use less than 10% of the time). Second, we provide new measurements about dynamically managed address space, showing nearly 40% of /24 blocks appear to be dynamically allocated, and dynamic addressing is most widely used in countries more recently to the Internet (more than 80% in China, while less then 30% in the U.S.).

Xue Cai and John Heidemann. Understanding Address Usage in the Visible Internet. Technical Report N. ISI-TR-2009-656, USC/Information Sciences Institute, February, 2009. http://www.isi.edu/~johnh/PAPERS/Cai09b.html

Categories
Papers Publications

new paper “Uses and Challenges for Network Datasets”

We just posted a pre-print of the paper “Uses and Challenges for Network Datasets”, to appear at IEEE CATCH in March.  The pre-print is at <http://www.isi.edu/~johnh/PAPERS/Heidemann09a.html>.

The abstract summarizes the paper:

Network datasets are necessary for many types of network research.  While there has been significant discussion about specific datasets, there has been less about the overall state of network data collection.  The goal of this paper is to explore the research questions facing the Internet today, the datasets needed to answer those questions, and the challenges to using those datasets.  We suggest several practices that have proven important in use of current data sets, and open challenges to improve use of network data.

More specifically, the paper tries to answer the question Jody Westby put to PREDICT PIs, which is “why take data, what is it good for”?  While a simple question, it’s not easy to answer (at least, my attempt to dash of a quick answer in e-mail failed).  The paper is an attempt at a more thoughtful answer.

The paper tries to summarize and point to a lot of ongoing work, but I know that our coverage was insufficient.  We welcome feedback about what we’re missing.

John Heidemann and Christos Papadopoulos. Uses and Challenges for Network Datasets. In Proceedings of the IEEE Cybersecurity Applications and Technologies Conference for Homeland Security (CATCH), pp. 73-82. Washington, DC, USA, IEEE. March, 2009. http://www.isi.edu/~johnh/PAPERS/Heidemann09a.html

Categories
Papers Publications

IMC paper on Internet Census described in MIT Tech Review

The IMC paper “Census and Survey of the Visible Internet” was described in an article “Probe Sees Unused Internet” in the MIT Technology Review by Robert Lemos.

The article provides a nice summary of the issues, but it reaches a conclusion that is stronger supported by the study.  The subhead of the article is “A survey shows that addresses are not running out as quickly as we’d thought”, and the article draws the conclusion: “the problem [of IPv4 address exhaustion] may not be as bad as many fear.”

The article’s conclusion, I think, overly simplifies matters—it is only true if the “better things we should be doing in managing the IPv4 address space” are free. The Internet Census we carried out supports the opportunity for better IPv4 address space management.  But an open question is the cost of such management.  Historically, with plentiful IPv4 addresses, IPv4 management costs have been small, but potential better IPv4 management will likely be much more costly.  This cost of ongoing IPv4 management needs to be weighed against the costs of one-time conversion cost to IPv6 coupled followed lower IPv6 management costs.

To me, one exciting conclusion from the Internet Census we carried out is that we now have data that allows us to start evaluating these trade-offs.  The answer may be more careful IPv4 gets us a few years, or that the cost of more careful IPv4 makes IPv6 an obvious choice.  In either case, resolving this transition is important for the Internet community.

Categories
Papers Publications

new paper about Internet address space census and survey

We are happy to report that the paper “Census and Survey of the Visible Internet” has been accepted to appear at the Internet Measurement Conference in Vouliagmeni, Greece in October 2008.

A preprint is available at http://www.isi.edu/~johnh/PAPERS/Heidemann08c.html, and an extended version is available as an updated technical report at http://www.isi.edu/~johnh/PAPERS/Heidemann08a.html.

Citation: John Heidemann, Yuri Pradkin, Ramesh Govindan, Christos Papadopoulos, Genevieve Bartlett, and Joseph Bannister. Census and Survey of the Visible Internet. In Proceedings of the ACM Internet Measurement Conference, pp. 169-182. Vouliagmeni, Greece, ACM. October, 2008. http://doi.acm.org/10.1145/1452520.1452542

Categories
Papers Publications

Internet address space: new technical paper and browsable map

A number of folks expressed interest in our ANT census of the Internet address space at <http://www.isi.edu/ant/address/>.

We have three recent updates, a new TECHNICAL REPORT and a BROWSABLE INTERNET ADDRESS MAP, and a PROJECT BLOG.

We have have released a new TECHNICAL REPORT describing the methodology,  ISI-TR-2008-649 at <http://www.isi.edu/~johnh/PAPERS/Heidemann08a.html>.
This report should completely supersede our previous report (#640), adding:

  • evaluation in ping accuracy, both absolutely and relative to TCP probing
  • estimation of error in our evaluations of hosts and server counts
  • validation of our approach to firewall detection
  • significant improvements in organization and presentation

We have also put up a BROWSABLE INTERNET ADDRESS MAP at <http://www.isi.edu/ant/address/browse/>.

With the Google maps engine, this map lets you zoom from an overview to any part of the address space, including showing individual hosts (permuted for anonymization).

Finally, we now have a PROJECT BLOG to allow folks to track future developments: <http://ant.isi.edu/blog/>.  We plan to do all future announcements via the blog rather than with general e-mail messages, so folks can opt-in to what they want to hear.

We welcome any comments about the map or technical report, either to our group mailing list (ant, then at isi.edu), or to individuals.

-ANT folks (John Heidemann, Yuri Pradkin, Ramesh Govindan, Christos Papadopoulos, Genevieve Bartlett, Joseph Bannister)

Categories
Announcements

Hello world!

Welcome to the ANT Project Blog.  Folks are welcome to subscribe to the RSS feed for this blog if they wish to track research related to the analysis of Internet traffic in the ANT group at ISI, USC, and CSU.  We expect this blog to be very low traffic (research takes time!).