Being the anchor points for building social relationships in the cyberspace, online social networks (OSNs) play an integral part of modern peoples life. Since different OSNs are designed to address specific social needs, people take part in multiple OSNs to cover different facets of their life. While the fragmented pieces of information about a user in each OSN may be of limited use, serious privacy issues arise if a sophisticated adversary pieces information together from multiple OSNs. To this end, we undertake the role of such an adversary and demonstrate the possibility of “splicing” user profiles across multiple OSNs and present associated security risks to users. In doing so, we develop a scalable and systematic profile joining scheme, Splicer, that focuses on various aspects of profile attributes by simultaneously performing exact, quasi-perfect and partial matches between pairs of profiles. From our evaluations on three real OSN data, Splicer not only handles large-scale OSN profiles efficiently by saving 87% computation time compared to all-pair profile comparisons, but also far exceeds the recall of generic distance measure based approach at the same precision level by 33%. Finally, we quantify the amount of information “lift” attributed to joining of OSNs, where on average 22% additional profile attributes can be added to 24% of users.

There are network management, traffic engineering, and security practices adopted in today's networking that rely on the knowledge about what applications' traffic is passing through the networks. These practices might fail with mobile apps whose identity remains hidden in generic HTTP traffic. The main reason is that unlike traditional applications, most mobile apps do not use specific protocols or IP ports with distinctive features. Many enterprises and service providers are in a great need of regaining control over their networks that increasingly carry mobile traffic. In this paper we propose FLOWR, a system that automatically identifies mobile apps by continually learning the apps' distinguishing features via traffic analysis. FLOWR focuses solely on key-value pairs in HTTP headers and intelligently identifies the pairs suitable for app signatures. Our system employs a custom supervised learning approach that leverages a very limited knowledge of app-signature seeds and autonomously grows its capacity for app identification. The approach is motivated by a simple but effective hypothesis that unknown app-identifying features should co-occur with the known signatures. Our experimental results show a significant growth in flow identification coverage provided by FLOWR. Specifically, we show that FLOWR can achieve identification of 86-95% of flows related to their generating apps.

This paper considers an approach to identify previously undetected malicious clients in Internet Service Provider (ISP) networks by combining flow classification with a graph-based score propagation method. Our approach represents all HTTP communications between clients and servers as a weighted, near-bipartite graph, where the nodes correspond to the IP addresses of clients and servers while the links are their interconnections, weighted according to the output of a flow-based classifier. We employ a two-phase alternating score propagation algorithm on the graph to identify suspicious clients in a monitored network. Using a symmetrized weighted adjacency matrix as its input, we show that our score propagation algorithm is less vulnerable towards inflating the malicious scores of popular Web servers with high in-degrees compared to the normalization used in PageRank, a widely used graph-based method. Experimental results on a 4-hour network trace collected by a large Internet service provider showed that incorporating flow information into score propagation significantly improves the precision of the algorithm.

The web has become a platform that attackers exploit to infect vulnerable hosts, or deceive victims into buying rogue software. To accomplish this, attackers either inject malicious scripts into popular web sites or manipulate content delivered by servers to exploit vulnerabilities in users' browsers. To hide malware distribution servers, attackers employ HTTP redirections, which automatically redirect users' requests through a series of intermediate web sites, before landing on the final distribution site. In this paper, we develop a methodology to identify malicious chains of HTTP redirections. We build per-user chains from passively collected traffic and extract novel statistical features from them, which capture inherent characteristics from malicious redirection cases. Then, we apply a supervised decision tree classifier to identify malicious chains. Using a large ISP dataset, with more than 15K clients, we demonstrate that our methodology is very effective in accurately identifying malicious chains, with recall and precision values over 90% and up to 98%.

No abstract available.

Malware is one of the most damaging security threats facing the Internet today. Despite the burgeoning literature, accurate detection of malware remains an elusive and challenging endeavor due to the increasing usage of payload encryption and sophisticated obfuscation methods. Also, the large variety of malware classes coupled with their rapid proliferation and polymorphic capabilities and imperfections of real-world data (noise, missing values, etc) continue to hinder the use of more sophisticated detection algorithms. This paper presents a novel machine learning based framework to detect known and newly emerging malware at a high precision using layer 3 and layer 4 network traffic features. The framework leverages the accuracy of supervised classification in detecting known classes with the adaptability of unsupervised learning in detecting new classes. It also introduces a tree-based feature transformation to overcome issues due to imperfections of the data and to construct more informative features for the malware detection task. We demonstrate the effectiveness of the framework using real network data from a large Internet service provider.

Network operators need to have a clear visibility into the applications running in their network. This is critical for both security and network management. Recent years have seen an exponential growth in the number of smart phone apps which has complicated this task. Traditional methods of traffic classification are no longer sufficient as the majority of this smart phone app traffic is carried over HTTP/HTTPS. Keeping up with the new applications that come up everyday is very challenging and time-consuming. We present a novel technique for automatically generating network profiles for identifying Android apps in the HTTP traffic. A network profile consists of fingerprints, i.e., unique characteristics of network behavior, that can be used to identify an app. To profile an Android app, we run the app automatically in an emulator and collect the network traces. We have developed a novel UI fuzzing technique for running the app such that different execution paths are exercised, which is necessary to build a comprehensive network profile. We have also developed a light-weight technique, for extracting fingerprints, that is based on identifying invariants in the generated traces. We used our technique to generate network profiles for thousands of apps. Using our network profiles we were able to detect the presence of these apps in real-world network traffic logs from a cellular provider.

Real-world data are often riddled with data quality problems such as noise, outliers and missing values, which present significant challenges for supervised learning algorithms to effectively classify them. This paper explores the ill-effects of inapplicable features on the performance of supervised learning algorithms. In particular, we highlight the difference between missing and inapplicable feature values. We argue that the current approaches for dealing with missing values, which are mostly based on single or multiple imputation methods, are insufficient to handle inapplicable features, especially those that are continuous valued. We also illustrate how current tree-based and kernel-based classifiers can be adversely affected by the presence of such features if not handled appropriately. Finally, we propose methods to extend existing tree-based and kernel-based classifiers to deal with the inapplicable continuous-valued features.

With the proliferation of online social networking (OSN) and mobile devices, preserving user privacy has become a great challenge. While prior studies have directly focused on OSN services, we call attention to the privacy leakage in mobile network data. This concern is motivated by two factors. First, the prevalence of OSN usage leaves identifiable digital footprints that can be traced back to users in the real-world. Second, the association between users and their mobile devices makes it easier to associate traffic to its owners. These pose a serious threat to user privacy as they enable an adversary to attribute significant portions of data traffic including the ones with NO identity leaks to network users' true identities. To demonstrate its feasibility, we develop the Tessellation methodology. By applying Tessellation on traffic from a cellular service provider (CSP), we show that up to 50% of the traffic can be attributed to the names of users. In addition to revealing the user identity, the reconstructed profile, dubbed as "mosaic," associates personal information such as political views, browsing habits, and favorite apps to the users. We conclude by discussing approaches for preventing and mitigating the alarming leakage of sensitive user information.

In this paper, we address the problem of large population speaker identification under noisy conditions. Major techniques for speaker identification is based on Mel-Frequency Cepstral Coefficients (MFCC), Gaussian Mixture Model (GMM) and Universal Background Model (UBM) which we call MFCC+GMM and MFCC+GMM+UBM. The approaches are known to perform very well for small population identification under low-noise conditions. However, the increase of population size can cause performance degradation of these schemes under noisy conditions. To mitigate this limitation, we propose a fuzzy-clustering-based decision tree approach. The key idea of our approach is to 1) use a decision tree to hierarchically partition the whole population into groups of small size, and determine which speaker group at the leaf node a speaker under test belongs to, and 2) apply MFCC+GMM to the selected speaker group for speaker identification. The advantage of our approach is that we use features that are independent from MFCC to partition speakers into groups and only apply MFCC+GMM to speaker groups at the leaf level. The key challenge in our design is how to achieve a low error probability of decision-tree-based classification. To address this, we adopt fuzzy clustering in constructing the tree for population partitioning, i.e., at each level, a speaker may belong to multiple groups. Such redundancy increases the probability of classifying a speaker under test into a correct group/node on the tree. Another novelty of this paper is that we use pitch and five vocal source features to construct a six-level decision tree. Experimental results demonstrate that our approach outperforms MFCC+ GMM and MFCC+ GMM+ UBM with higher accuracy and lower complexity for large population identification under additive white Gaussian noise (AWGN) conditions.

Malware detection from network traffic flows is a challenging problem due to data irregularity issues such as imbalanced class distribution, noise, missing values, and heterogeneous types of features. To address these challenges, this paper presents a two-stage classification approach for malware detection. The framework initially employs random forest as a macro-level classifier to separate the malicious from non-malicious network flows, followed by a collection of one-class support vector machine classifiers to identify the specific type of malware. A novel tree-based feature construction approach is proposed to deal with data imperfection issues. As the performance of the support vector machine classifier often depends on the kernel function used to compute the similarity between every pair of data points, designing an appropriate kernel is essential for accurate identification of malware classes. We present a simple algorithm to construct a weighted linear kernel on the tree transformed features and demonstrate its effectiveness in detecting malware from real network traffic data.

Among different traffic classification approaches, Deep Packet Inspection (DPI) methods are considered as the most accurate. These methods, however, have two drawbacks: (i) they are not efficient since they use complex regular expressions as protocol signatures, and (ii) they require manual intervention to generate and maintain signatures, partly due to the signature complexity. In this paper, we present CUTE, an automatic traffic classification method, which relies on sets of weighted terms as protocol signatures. The key idea behind CUTE is an observation that, given appropriate weights, the occurrence of a specific term is more important than the relative location of terms in a flow. This observation is based on experimental evaluations as well as theoretical analysis, and leads to several key advantages over previous classification techniques: (i) CUTE is extremely faster than other classification schemes since matching flows with weighed terms is significantly faster than matching regular expressions; (ii) CUTE can classify network traffic using only the first few bytes of the flows in most cases; and (iii) Unlike most existing classification techniques, CUTE can be used to classify partial (or even slightly modified) flows. Even though CUTE replaces complex regular expressions with a set of simple terms, using theoretical analysis and experimental evaluations (based on two large packet traces from tier-one ISPs), we show that its accuracy is as good as or better than existing complex classification schemes, i.e. CUTE achieves precision and recall rates of more than 90%. Additionally, CUTE can successfully classify more than half of flows that other DPI methods fail to classify.

A careful perusal of the Internet evolution reveals two major trends - explosion of cloud-based services and video streaming applications. In both of the above cases, the owner (e.g., CNN, YouTube, or Zynga) of the content and the organization serving it (e.g., Akamai, Limelight, or Amazon EC2) are decoupled, thus making it harder to understand the association between the content, owner, and the host where the content resides. This has created a tangled world wide web that is very hard to unwind, impairing ISPs' and network administrators' capabilities to control the traffic flowing in their networks.

Many research efforts propose the use of flow-level features (e.g., packet sizes and inter-arrival times) and machine learning algorithms to solve the traffic classification problem. However, these statistical methods have not made the anticipated impact in the real world. We attribute this to two main reasons: (a) training the classifiers and bootstrapping the system is cumbersome, (b) the resulting classifiers have limited ability to adapt gracefully as the traffic behavior changes. In this paper, we propose an approach that is easy to bootstrap and deploy, as well as robust to changes in the traffic, such as the emergence of new applications. The key novelty of our classifier is that it learns to identify the traffic of each application in isolation, instead of trying to distinguish one application from another. This is a very challenging task that hides many caveats and subtleties. To make this possible, we adapt and use subspace clustering, a powerful technique that has not been used before in this context. Subspace clustering allows the profiling of applications to be more precise by automatically eliminating irrelevant features. We show that our approach exhibits very high accuracy in classifying each application on five traces from different ISPs captured between 2005 and 2011. This new way of looking at application classification could generate powerful and practical solutions in the space of traffic monitoring and network management.

Abstract In this paper, we address the speech‐based gender identification problem. Mel‐Frequency Cepstral Coefficients (MFCC) of voice samples are typically used as the features for gender identification. However, MFCC‐based classification incurs high complexity. This paper proposes a novel pitch‐based gender identification system with a two‐stage classifier to ensure accurate identification and low complexity. The first stage of the classifier identifies and labels all the speakers whose pitch clearly indicates the gender of the speaker; the complexity of this stage is very low since only threshold‐based decision rule on a scalar (i.e., pitch) is used. The ambiguous voice samples from all the other speakers (which cannot be classified with high accuracy by the first stage, and can be regarded as suspicious speakers or difficult cases) are forwarded to the second‐stage for finer examination; the second‐stage of our classifier uses Gaussian Mixture Model to accurately isolate voice samples based on gender. Experiment results show that our system is speech language/content independent, microphone independent, and robust against noisy recording conditions. Our system is extremely accurate with probability of correct classification of 98.65%, and very efficient with about 5 s required for feature extraction and classification. Copyright © 2011 John Wiley & Sons, Ltd.

Human communication has changed by the advent of smartphones. Using commonplace mobile device features, they started uploading large amounts of content that increases. This increase in demand will overwhelm capacity and limits the providers' ability to provide the quality of service demanded by their users. In the absence of technical solutions, cellular network providers are considering changing billing plans to address this. Our contributions are twofold. First, by analyzing user content upload behavior, we find that the user-generated content problem is a user behavioral problem. Particularly, by analyzing user mobility and data logs of 2 million users of one of the largest US cellular providers, we find that: 1) users upload content from a small number of locations; 2) because such locations are different for users, we find that the problem appears ubiquitous. However, we find that: 3) there exists a significant lag between content generation and uploading times, and 4) with respect to users, it is always the same users to delay. Second, we propose a cellular network architecture. Our approach proposes capacity upgrades at a select number of locations called Drop Zones. Although not particularly popular for uploads originally, Drop Zones seamlessly fall within the natural movement patterns of a large number of users. They are therefore suited for uploading larger quantities of content in a postponed manner. We design infrastructure placement algorithms and demonstrate that by upgrading infrastructure in only 963 base stations across the entire US, it is possible to deliver 50% of content via Drop Zones.

Although 3G networks have been largely deployed to cope with the increasing demand of wireless data services, little is known on how these networks are used from the network perspective. In this paper, we present analysis of data services based on a nation-wide 3G network trace collected from one of the largest cellular network service providers in North America. Our work differentiates from previous studies by examining data service usage and mobility patterns from various dimensions including application breakdown, user roles, device types and diurnal characteristics. We also look into various access issues such as termination failures and frequent registrations to better understand how the network performs. Our results are important for cellular network operators and protocol designers to improve data service performance and user satisfaction.

Spam over Internet Telephony (SPIT) is a new form of spam delivered using the phone network. With the low cost of Internet telephony, SPIT has become an attractive alternative for spammers to carry out unsolicited marketing and phishing. SPIT is more intrusive than email spam as it demands immediate recipient attention. In this paper, we study characteristics of communications in a phone network with the objective of identifying “SPITters”. We collect and analyze the data from one of the largest phone providers in North America. First, we propose a new technique, Loose Tie Detection (LTD), to identify outliers based on social ties. Second, we introduce Enhanced Progressive Multi Grey-Leveling (EPMG), which identifies outliers based on call density and reciprocity. Finally, we propose SymRank, an adaptation of the PageRank algorithm that computes the reputation of subscribers based on both incoming and outgoing calls.We evaluate the three techniques and find that they compute an overlapping set of outliers. Our experiments reveal that LTD and SymRank - although seemingly independent approaches - closely match with regard to outliers, thus showing that our techniques are effective in identifying SPITters.

Smartphones have changed the way people communicate. Most prominently, using commonplace mobile device features (e.g., high resolution cameras), they started producing and uploading large amounts of content that increases at an exponential pace. In the absence of viable technical solutions, some cellular network providers are considering to start charging special usage fees to address the problem. Our contributions are twofold. First, we find that the user-generated content problem is a user-behavioral problem. By analyzing user mobility and data logs of close to 2 million users of a cellular network, we find that (i) users upload content from a small number of locations, typically corresponding to their home or work locations; (ii) because such locations are different for different users, we find that the problem appears ubiquitous, since user-generated content uploads grow exponentially at most locations. However, we also find that (Hi) there exists a significant lag between content generation and uploading times. For example, we find that 55% of content that is uploaded via mobile phones is at least 1 day old. Second, based on the above insights, we propose a new cellular network architecture. Our approach proposes capacity upgrades at a select number of locations called Drop Zones. Although not particularly popular for uploads originally, Drop Zones seamlessly fall within the natural movement patterns of a large number of users. They are therefore better suited for uploading larger quantities of content in a postponed manner. We design infrastructure placement algorithms and demonstrate that by upgrading infrastructure in only 963 base-stations across the entire United States, it is possible to deliver 50% of total content via the Drop Zones.

Abstract Voice and video over IP are becoming increasingly popular and represent the largest source of profits as consumer interest in online voice and video services increases, and as broadband deployments proliferate. In order to tap the potential profits that VoIP and IPTV offer, carrier networks have to efficiently and accurately manage and track the delivery of IP services. The traditional approach of using port numbers to classify traffic is infeasible due to the usage of dynamic port number. In this paper, we focus on a statistical pattern classification technique to identify multimedia traffic. Based on the intuitions that voice and video data streams show strong regularities in the packet inter‐arrival times (IATs) and the associated packet sizes when combined together in one single stochastic process, we propose a system, called VOVClassifier, for voice and video traffic classification. VOVClassifier is an automated self‐learning system that classifies traffic data by extracting features from frequency domain using Power Spectral Density (PSD) analysis and grouping features using Subspace Decomposition. We applied VOVClassifier to real packet traces collected from different network scenarios. Results demonstrate the effectiveness and robustness of our approach that is capable of achieving a detection rate of up to 100% for voice and 96.5% for video while keeping the false positive rate close to 0%. Copyright © 2009 John Wiley & Sons, Ltd.

With widespread popularity of smart phones, more and more users are accessing the Internet on the go. Understanding mobile user browsing behavior is of great significance for several reasons. For example, it can help cellular (data) service providers (CSPs) to improve service performance, thus increasing user satisfaction. It can also provide valuable insights about how to enhance mobile user experience by providing dynamic content personalization and recommendation, or location-aware services.

The popularity of a new generation of smart peer-to-peer applications has resulted in several new challenges for accurately classifying network traffic. In this paper, we propose a novel 2-stage P2P traffic classifier, called self learning traffic classifier (SLTC), that can accurately identify P2P traffic in high speed networks. The first stage classifies P2P traffic from the rest of the network traffic, and the second stage automatically extracts application payload signatures to accurately identify the P2P application that generated the P2P flow. For the first stage, we propose a fast, light-weight algorithm called time correlation metric (TCM), that exploits the temporal correlation of flows to clearly separate peer-to-peer (P2P) traffic from the rest of the traffic. Using real network traces from tier-1 ISPs that are located in different continents, we show that the detection rate of TCM is consistently above 95 % while always keeping the false positives at 0%. For the second stage, we use the LASER signature extraction algorithm to accurately identify signatures of several known and unknown P2P protocols with very small false positive rate (< 1%). Using our prototype on tier-1 ISP traces, we demonstrate that SLTC automatically learns signatures for more than 95% of both known and unknown traffic within 3 minutes.

Characterizing the relationship that exists between people's application interests and mobility properties is the core question relevant for location-based services, in particular those that facilitate serendipitous discovery of people, businesses and objects. In this paper, we apply rule mining and spectral clustering to study this relationship for a population of over 280,000 users of a 3G mobile network in a large metropolitan area. Our analysis reveals that (i) People's movement patterns are correlated with the applications they access, e.g., stationary users and those who move more often and visit more locations tend to access different applications. (ii) Location affects the applications accessed by users, i.e., at certain locations, users are more likely to evince interest in a particular class of applications than others irrespective of the time of day. (iii) Finally, the number of serendipitous meetings between users of similar cyber interest is larger in regions with higher density of hotspots. Our analysis demonstrates how cellular network providers and location-based services can benefit from knowledge of the inter-play between users and their locations and interests.

Recently, cellular phone networks have begun allowing third-party applications to run over certain open-API phone operating systems such as Windows Mobile, Iphone and Google's Android platform. However, with this increased openness, the fear of rogue programs written to propagate from one phone to another becomes ever more real. This paper proposes a counter-mechanism to contain the propagation of a mobile worm at the earliest stage by patching an optimal set of selected phones. The counter-mechanism continually extracts a social relationship graph between mobile phones via an analysis of the network traffic. As people are more likely to open and download content that they receive from friends, this social relationship graph is representative of the most likely propagation path of a mobile worm. The counter mechanism partitions the social relationship graph via two different algorithms, balanced and clustered partitioning and selects an optimal set of phones to be patched first as those which have the capability to infect the most number of other phones. The performance of these partitioning algorithms is compared against a benchmark random partitioning scheme. Through extensive trace-driven experiments using real IP packet traces from one of the largest cellular networks in the US, we demonstrate the efficacy of our proposed counter-mechanism in containing a mobile worm.

This paper proposes IPzip, a comprehensive suite of algorithms for compressing IP network packet headers and payloads. We propose an online algorithm for compressing packets in real-time for efficient transfer and an offline algorithm for efficient storage of the network data. In contrast to related approaches, IPzip achieves better compression by exploiting the correlations exhibited by (i) packets that are similar such as those belonging to the same layer-4 flow or those with the same destination port (inter-packet correlation) and (ii) header fields that are correlated to each other (intra-packet correlation). Since reordering of packets and fields is resource intensive, IPzip generates a near-optimal compression plan in an offline phase. Moreover, we propose a methodology to monitor over time the effectiveness of the compression plan being used and switch to a new compression plan when performance of the current compression plan decreases due to changes in the intrinsic traffic structure. Finally, via trace-driven experiments on network traffic obtained from Tier-1 ISPs, we validate that IPzip achieves better performance compared to related approaches.

Understanding Internet access trends at a global scale, i.e., what do people do on the Internet, is a challenging problem that is typically addressed by analyzing network traces. However, obtaining such traces presents its own set of challenges owing to either privacy concerns or to other operational difficulties. The key hypothesis of our work here is that most of the information needed to profile the Internet endpoints is already available around us - on the web.

Abstract Despite the rapid advance in networking technologies, detection of network anomalies at high‐speed switches/routers is still far from maturity. To push the frontier, two major technologies need to be addressed. The first one is efficient feature‐extraction algorithms/hardware that can match a line rate in the order of Gb/second; the second one is fast and effective anomaly detection schemes. In this paper, we focus on design of efficient data structure and algorithms for feature extraction. Specifically, we propose a novel data structure that extracts the so‐called two‐directional (2D) matching features, which are shown to be effective indicators of network anomalies. Our key idea is to use a Bloom filter array (BFA) to trade‐off a small amount of accuracy in feature extraction, for much less space and time complexity, so that our data structure can catch up with a line rate in the order of Gb/second. Different from the existing work, our data structure has the following properties: (1) it dynamic Bloom filter, (2) combination of a it sliding window with Bloom filter, and (3) using an insertion–removal pair to enhance Bloom filter with a removal operation. Our analysis and simulation demonstrate that the proposed data structure has a better space/time trade‐off than conventional algorithms. For example, for a fixed time complexity, the conventional algorithm (i.e., hash table [1—8]) requires a memory of 1.01 Gbits while our data structure requires a memory of only 62.9 Mbits, at the cost of losing 1% accuracy in feature extraction. Copyright © 2008 John Wiley & Sons, Ltd.

Data synopsis is a lossy compressed representation of data stored into databases that helps the query optimizer to speed up the query process, e.g. time to retrieve the data from the database. An efficient data synopsis must provide accurate information about the distribution of data to the query optimizer at any point in time. Due to the fact that some data will be queried more often than others, a good data synopsis should consider the use of nonuniform accuracy, e.g. provide better approximation of data that are queried the most. Although, the generation of data synopsis is a critical step to achieve a good approximation of the initial data representation, data synopsis must be updated over time when dealing with time varying data. In this paper, we introduce new Haar wavelet synopses for nonuniform accuracy and time-varying data that can be generated in linear time and space, and updated in sublinear time. The efficiency of our new data synopses is validated against other linear methods by using both synthetic and real data sets

Enterprise networks are increasingly offloading the responsibility for worm detection and containment to the carrier networks. However, current approaches to the zero-day worm detection problem such as those based on content similarity of packet payloads are not scalable to the carrier link speeds (OC-48 and up-wards). In this paper, we introduce a new system, namely DoWitcher, which in contrast to previous approaches is scalable as well as able to detect the stealthiest worms that employ low-propagation rates or polymorphisms to evade detection. DoWitcher uses an incremental approach toward worm detection: First, it examines the layer-4 traffic features to discern the presence of a worm anomaly; Next, it determines a flow-filter mask that can be applied to isolate the suspect worm flows and; Finally, it enables full-packet capture of only those flows that match the mask, which are then processed by a longest common subsequence algorithm to extract the worm content signature. Via a proof-of-concept implementation on a commercially available network analyzer processing raw packets from an OC-48 link, we demonstrate the capability of DoWitcher to detect low-rate worms and extract signatures for even the polymorphic worms.

Despite the rapid advance in networking technologies, detection of network anomalies at high-speed switches/routers is still far from maturity. To push the frontier, two major technologies need to be addressed. The first one is efficient feature-extraction algorithms/hardware that can match a line rate in the order of Gb/s; the second one is fast and effective anomaly detection schemes. In this paper, we focus on design of efficient data structure and algorithms for feature extraction. Specifically, we propose a novel data structure that extracts so-called two-directional (2D) matching features, which are shown to be effective indicators of network anomalies. Our key idea is to use a Bloom filter array to trade off a small amount of accuracy in feature extraction, for much less space and time complexity, so that our data structure can catch up with a line rate in the order of Gb/s. Different from the existing work, our data structure has the following properties: 1) dynamic Bloom filter, 2) combination of a sliding window with the Bloom filter, and 3) using an insertion-removal pair to enhance the Bloom filter with a removal operation. Our analysis and simulation demonstrate that the proposed data structure has a better space/time trade-off than conventional algorithms. For example, for a fixed time complexity, the conventional algorithm (i.e., hash table [1]) requires a memory of 1.01G bits while our data structure requires a memory of only 62.9M bits, at the cost of losing 1% accuracy in feature extraction.

Abstract — With the explosive growth of the Internet over the last 10 years, a lot of work has been dedicated to understanding the underlying mechanisms of wired IP traffic. Recently, the rapid deployment of large-scale wireless infrastructures in various environments and the interesting mixture of traffic carried coupled with the large diversity of devices accessing the medium (Cellphones, Laptops, PDAs) have triggered the attention and curiosity of the research community. This paper analyzes in depth the properties of several large traces of packet data collected between the wireless access point and the IP cloud from an operational wireless service provider. We determine unambiguously the influence of network variables such as the arrival patterns of packet and flows, flow durations and flow interactions, on the aggregate statistics of TCP traffic. In doing so, we highlight the main differences and similarities between wireless and wired IP traffic, and between the two directions (from wireless devices to IP cloud and vice-versa), and show how they can be distinguished. The resulting insights provide a foundation for models of such traffic, necessary for improved resource allocation schemes as well as for the effectiveness of future services and applications. Index Terms—wireless traffic characterization, Internet traffic, wavelets, semi-experiments I.

Owing to the inter-domain aspects of BGP routing, it is difficult to correlate information across multiple domains in order to analyze the root cause of the routing outages. We present BGP Eye, a tool for visualization-aided root-cause analysis of BGP anomalies. In contrast to previous approaches, BGP Eye performs real-time analysis of BGP anomalies through hierarchical analysis. First, BGP updates are clustered to obtain BGP events that are more representative of an anomaly. These events are then correlated across all border routers to ascertain the extent of the anomaly. Furthermore, BGP Eye provides both the capability to analyze BGP anomalies from an Internet-Centric View through multiple vantage points as well as from a Home-Centric View of a particular Autonomous System. We present the capability for scalable and real-time root-cause analysis provided by BGP Eye through the analysis of two very different anomalies. First, we provide an Internet-Centric view from AS568 of the routing outages during the spread of the Slammer Worm on January 25th, 2003. Second, we provide a Home-Centric view from AS6458 of the routing outages caused by the inadvertent prefix hijacking by AS9121 on December 24th, 2004.

In this paper, we address the problem of determining an optimal topology for Bluetooth wireless personal area networks (BT-WPANs). In BT-WPANs, multiple communication channels are available, through a frequency hopping technique. The way network nodes are grouped to share the same channel, and which nodes are selected to bridge traffic from a channel to another, has a significant impact on the capacity and throughput of the system, as well as the nodes' battery lifetime. The determination of an optimal topology is thus extremely important. Our approach is based on a min-max formulation of the optimization problem, which produces topologies that minimize the traffic load of the most congested node in the network (thus also minimizing energy consumption) while meeting the traffic requirements and the constraints posed by the BT-WPAN technology. We investigate the performance of the topologies produced by our optimization approach as the system requirements vary, and evaluate the trade-offs existing between system complexity and network efficiency. Results show that a topology optimized for some traffic requirements is remarkably robust to changes in the traffic pattern. Due to the problem complexity, the optimal solution is attained in a centralized manner. Although this implies severe limitations, a centralized solution can be applied whenever a network coordinator is elected, and provides a useful term of comparison for any distributed heuristics.

Typically, each autonomous system (AS) tunes its local IS-IS or OSPF metrics without any coordination with other ASes. Such local optimizations can lead to sub-optimal end-to-end network performance, as suggested by the performance enhancements achieved by some overlay routing projects. We study the interaction of local IGP engineering in an ISP network with interdomain routing policies. Specifically, (a) how does hot-potato routing (the BGP policy of choosing the closest egress) influence the selection of IGP link metrics? and (b) how does traffic to neighboring ASes shift due to changes in the local AS's IGP link metrics? In our measurement study, we find that the hot-potato routing policy interacts significantly with IGP engineering -ignoring this interaction resulted in metrics sub-optimal by as much as 20% of link utilization. Further, the impact on neighboring ASes depends on peering locations and policies, and as much as 25% of traffic to a neighboring AS can shift the exit point. Such interdomain shifts can be detrimental to the performance of neighboring ASes. We rely on the actual measured network topology, IGP metrics, traffic matrix and delay bounds. Even though our results are specific to a single ISP, they show significant interaction between local IGP engineering and interdomain routing policies, and thus motivate further work on global network optimization and coordination among ISPs.

Active probing heuristics are usually based on queuing systems. However, a rigorous probabilistic treatment of probing methods has been lacking. For instance, it is not known even in principle, what can and cannot be measured in general, nor the true limitations of existing methods. We provide a probabilistic treatment for the measurement of cross traffic in the 1-hop case. We derive inversion formulae for the cross traffic process, and explain their fundamental limits, using an intuitive geometric framework.

International audience

We consider the traffic matrix estimation problem in IP backbone networks, whose goal is to accurately estimate the volume of traffic traveling between network endpoints. Previous approaches to this problem involve measuring the volume of traffic on each link in the network during a time interval where the routing configuration is fixed, and exploit a statistical model of the traffic in order to obtain an estimate of the traffic matrix. These previous approaches are prone to large estimation errors because the link measurements from a fixed muting scenario constitute a data set that is simply too limited to provide enough data to enable estimation procedures that yield very small errors. We propose the idea of collecting link measurements under multiple routing scenarios so that the traffic matrix can be determined very accurately. We present an algorithm for determining a sequence of routing configurations, each of which is specified by a set of link weights. We incorporate carrier requirements into our algorithm so that our proposed routing configurations are operationally viable. We present the results of applying our algorithm to some representative IP backbone topologies and discuss the performance trade-offs that arise.

In this paper we investigate a new idea for traffic matrix estimation that makes the basic problem less under-constrained, by deliberately changing the routing to obtain additional measurements. Because all these measurements are collected over disparate time intervals, we need to establish models for each Origin-Destination (OD) pair to capture the complex behaviours of internet traffic. We model each OD pair with two components: the diurnal pattern and the fluctuation process. We provide models that incorporate the two components above, to estimate both the first and second order moments of traffic matrices. We do this for both stationary and cyclo-stationary traffic scenarios. We formalize the problem of estimating the second order moment in a way that is completely independent from the first order moment. Moreover, we can estimate the second order moment without needing any routing changes (i.e., without explicit changes to IGP link weights). We prove for the first time, that such a result holds for any realistic topology under the assumption of minimum cost routing and strictly positive link weights. We highlight how the second order moment helps the identification of the top largest OD flows carrying the most significant fraction of network traffic. We then propose a refined methodology consisting of using our variance estimator (without routing changes) to identify the top largest flows, and estimate only these flows. The benefit of this method is that it dramatically reduces the number of routing changes needed. We validate the effectiveness of our methodology and the intuitions behind it by using real aggregated sampled netflow data collected from a commercial Tier-1 backbone.

In this paper, we present a new methodology for the design of fault-tolerant logical topologies in wavelength-routed optical networks supporting Internet protocol (IP) datagram flows. Our design approach generalizes the "design protection" concepts, and relies on the dynamic capabilities of IP to reroute datagrams when faults occur, thus achieving protection and restoration, and leading to high-performance cost-effective fault-tolerant logical topologies. In this paper, for the first time we consider resilience properties during the logical topology optimization process, thus extending the optimization of the network resilience also to the space of logical topologies. Numerical results clearly show that our approach outperforms previous ones, being able to obtain very effective survivable logical topologies with limited computational complexity.

We study an approach to quality-of-service (QoS) that offers end-users the choice between two service classes defined according to their level of transmission protection. The fully protected (FP) class offers end-users a guarantee of survivability in the case of a single-link failure; all FP traffic is protected using a 1:1 protection scheme at the wavelength-division multiplexing (WDM) layer. The best effort protected (BEP) class is not protected; instead restoration at the IP layer is provided. The FP service class mimics what Internet users receive today. The BEP traffic is designed to run over the large amounts of unused bandwidth that exist in today's Internet. The goal is to increase the load carried on backbone networks without reducing the QoS received by existing customers. To support two such services, we have to solve two problems: the off-line problem of mapping logical links to pairs of disjoint fiber paths, and an on-line scheduling problem for differentiating packets from two classes at the IP layer. We provide an algorithm based on a Tabu Search meta-heuristic to solve the mapping problem, and a simple but efficient scheduler based on weighted fair queueing for service differentiation at the IP layer. We consider numerous requirements that carriers face and illustrate the tradeoffs they induce. We demonstrate that we can successfully increase the total network load by a factor between three and ten and still meet all the carrier requirements.

There are two fundamental technology issues that challenge the robustness of IP backbones. First, SONET protection is gradually being removed because of its high cost (while SONET framing is kept for failure detection purposes). Protection and restoration are provided by the IP layer that operates directly over a DWDM infrastructure. Second, ISPs are systematically forced to use the shortest distance path between two points of presence in order to meet their promised SLAs. In this context, IP backbones are extremely vulnerable to fiber cuts that can bring down a significant fraction of the IP routes. We propose two solutions (an ILP model and a heuristic algorithm) to optimally map a given IP topology onto a fiber infrastructure. The version of the mapping problem that we address incorporates a number of real constraints and requirements faced by carriers today. The optimal mapping maximizes the robustness of the network while maintaining the ISP's SLA delay requirements. In addition, our heuristic takes into consideration constraints such as a shortage of wavelengths and priorities among POPs and routes. The heuristic is evaluated on the Sprint backbone network. We illustrate the tradeoffs between the many requirements.

In this paper, we address the problem of determining an optimal topology for Bluetooth wireless personal area networks (BT-WPAN). In BT-WPAN, multiple communication channels are available, thanks to the use of a frequency hopping technique. The way network nodes are grouped to share the same channel, and which nodes are selected to bridge traffic from a channel to another, has a significant impact on the capacity and the throughput of the system, as well as the nodes' battery lifetime. The determination of an optimal topology is thus extremely important; nevertheless, to the best of our knowledge, this problem is tackled here for the first time. Our optimization approach is based on a model derived from constraints that are specific to the BT-WPAN technology, but the level of abstraction of the model is such that it can be related to the more general field of ad hoc networking. By using a min-max formulation, we find the optimal topology that provides full network connectivity, fulfills the traffic requirements and the constraints posed by the system specification, and minimizes the traffic load of the most congested node in the network, or equivalently its energy consumption. Results show that a topology optimized for some traffic requirements is also remarkably robust to changes in the traffic pattern. Due to the problem complexity, the optimal solution is attained in a centralized manner. Although this implies severe limitations, a centralized solution can be applied whenever a network coordinator is elected, and provides a useful term of comparison for any distributed heuristics.

We consider all-optical TDM/WDM broadcast and select networks. We assume that each network node is equipped with one fixed transmitter and one tunable receiver; tuning times are assumed to be not negligible with respect to the slot time. We discuss efficient scheduling algorithms to assign TDM/WDM slots to multicast traffic in such networks. Given the problem complexity, heuristic algorithms based on the Tabu Search methodology are proposed, and their performance is assessed using randomly created request matrices based on two types of multicast traffic patterns: a video-conference, and a server distribution traffic pattern. The considered performance index is the frame length required to schedule a given traffic request matrix.

In this paper we discuss the optimal design of logical topologies in wavelength-routed WDM networks supporting unicast and multicast transfer of IP datagrams. We first explain the key aspects of the problem, emphasizing the fact that in IP networks the routing algorithms are an input to the optimization problem, not an optimization target. We then provide a mixed integer linear programming formulation of the optimization problem., which however leads to unacceptably high complexity for networks of non-trivially small size. We then propose both greedy and metaheuristic approaches for the sub-optimal design of logical topologies with acceptable complexity. Finally, we derive lower bounds that allow the assessment of the performance of the proposed algorithms. Some numerical results indicate that the proposed metaheuristics largely outperform the greedy approaches, and are able to obtain very good logical topologies.

In this paper we illustrate a new methodology for the design of fault-tolerant logical topologies in wavelength-routed optical networks exploiting wavelength division multiplexing, and supporting both unicast and multicast IP datagram flows. Our approach to protection and restoration generalizes the "design protection" concepts, and relies on the dynamic capabilities of IP routing to re-route IP datagrams when faults occur, thus leading to high-performance cost-effective fault-tolerant logical topologies. Our design methodology for the first time considers the resilience properties or the topology during the logical topology optimization process, thus extending the optimization of the network resilience performance also on the space of the logical topologies. Numerical results clearly show that our approach is able to obtain very good logical topologies with limited complexity.

This paper addresses the design of packet transmission schedules in photonic slotted wavelength-division multiplexing/time-division multiplexing broadcast-and-select networks with W wavelengths and N nodes. Nodes are equipped with one tunable-wavelength transmitter with nonnegligible tuning times and one fixed-wavelength receiver. A new scheduling algorithm that exploits multihop packet transfer to shorten the duration of scheduling periods is first proposed. A single-hop scheduling algorithm that performs slightly better than previous proposals is then described. A simulation-based analysis of the two algorithms shows that they jointly lead to significant improvements in both throughput and delay with respect to previous single-hop schedules.