© Springer Nature Switzerland AG 2020. Security specialists have been developing and implementing many countermeasures against security threats, which is needed because the number of new security threats is further and further growing. In this chapter, we introduce an approach for identifying hidden security threats by using Uniform Resource Locators (URLs) as an example dataset, with a method that automatically detects malicious URLs by leveraging machine learning techniques. We demonstrate the effectiveness of the method through performance evaluations.

Since the 1980s, domain names and the domain name system (DNS) have been used and abused. Although legitimate Internet users rely on domain names as indispensable infrastructures for using the Internet, attackers use or abuse them as reliable, instantaneous, and distributed attack infrastructures. However, there is a lack of complete understanding of such domain-name abuses and methods for coping with them. In this study, we designed and implemented a unified analysis system combining current defense solutions to build actionable threat intelligence from malicious domain names. The basic concept underlying our system is malicious domain name chromatography. Our analysis system can distinguish among mixtures of malicious domain names for websites. On the basis of this concept, we do not create a hodgepodge of current solutions but design separation of abused domain names and offer actionable threat intelligence or defense information by considering the characteristics of malicious domain names as well as the possible defense solutions and points of defense. Finally, we evaluated our analysis system and defense-information output using a large real dataset to show the effectiveness and validity of our system.

Damage caused by malware has become a serious problem. The recent rise in the spread of evasive malware has made it difficult to detect it at the pre-infection timing. Malware detection at post-infection timing is a promising approach that fulfills this gap. Given this background, this work aims to identify likely malware-infected devices from the measurement of Internet traffic. The advantage of the traffic-measurementbased approach is that it enables us to monitor a large number of endhosts. If we find an endhost as a source of malicious traffic, the endhost is likely a malware-infected device. Since the majority of malware today makes use of the web as a means to communicate with the C&amp
C servers that reside on the external network, we leverage information recorded in the HTTP headers to discriminate between malicious and benign traffic. To make our approach scalable and robust, we develop the automatic template generation scheme that drastically reduces the amount of information to be kept while achieving the high accuracy of classification
since it does not make use of any domain knowledge, the approach should be robust against changes of malware. We apply several classifiers, which include machine learning algorithms, to the extracted templates and classify traffic into two categories: malicious and benign. Our extensive experiments demonstrate that our approach discriminates between malicious and benign traffic with up to 97.1% precision while maintaining the false positive rate below 1.0%.

Mobile app stores, such as Google Play, play a vital role in the ecosystem of mobile device software distribution platforms. When users find an app of interest, they can acquire useful data from the app store to inform their decision regarding whether to install the app. This data includes ratings, reviews, number of installs, and the category of the app. The ratings and reviews are the user-generated content (UGC) that affect the reputation of an app. Therefore, miscreants can leverage such channels to conduct promotional attacks
for example, a miscreant may promote a malicious app by endowing it with a good reputation via fake ratings and reviews to encourage would-be victims to install the app. In this study, we have developed a system called PADetective that detects miscreants who are likely to be conducting promotional attacks. Using a 1723-entry labeled dataset, we demonstrate that the true positive rate of detection model is 90%, with a false positive rate of 5.8%. We then applied our system to an unlabeled dataset of 57M reviews written by 20M users for 1M apps to characterize the prevalence of threats in the wild. The PADetective system detected 289K reviewers as potential PA attackers. The detected potential PA attackers posted reviews to 136K apps, which included 21K malicious apps. We also report that our system can be used to identify potentially malicious apps that have not been detected by anti-virus checkers.

Domain names are at the base of today’s cyber-attacks. Attackers abuse the domain name system (DNS) to mystify their attack ecosystems
they systematically generate a huge volume of distinct domain names to make it infeasible for blacklisting approaches to keep up with newly generated malicious domain names. To solve this problem, we propose DomainProfiler for discovering malicious domain names that are likely to be abused in future. The key idea with our system is to exploit temporal variation patterns (TVPs) of domain names. The TVPs of domain names include information about how and when a domain name has been listed in legitimate/popular and/or malicious domain name lists. On the basis of this idea, our system actively collects historical DNS logs, analyzes their TVPs, and predicts whether a given domain name will be used for malicious purposes. Our evaluation revealed that DomainProfiler can predict malicious domain names 220 days beforehand with a true positive rate of 0.985. Moreover, we verified the effectiveness of our system in terms of the benefits from our TVPs and defense against cyber-attacks.

Network equipment, such as routers, switches, and RA- DIUS servers, generate various log messages induced by network events such as hardware failures and protocol flaps. In large production networks, analyzing the log messages is crucial for diagnosing network anomalies
however, it has become challenging due to the following two reasons. First, the log messages are composed of unstructured text messages generated in accordance with vendor-specific rules. Second, network events that in- duce the log messages span several geographical locations, network layers, protocols, and services. We developed a method to tackle these obsta- cles consisting of two techniques: statistical template extraction (STE) and log tensor factorization (LTF). The former leverages a statistical clustering technique to automatically extract primary templates from unstructured log messages. The latter builds a statistical model that collects spatial-Temporal patterns of log messages. Such spatial-Temporal patterns provide useful in- sights into understanding the impact and patterns of hidden network events. We evaluate our techniques using a massive amount of network log mes- sages collected from a large operating network and confirm that our model fits the data well. We also investigate several case studies that validate the usefulness of our method.

There are many studies for recognizing eating moments using wide types of modality (e.g. arm motion). However, they are needed to be improved for both accuracy and robustness for practical use in daily life. In this paper, we propose a novel recognition method using bimodal heart rate responses caused by eating. Our method combines (i) short-term and (ii) long-term features of heart rate changes. The proposed method was evaluated for recognizing eating moment with the free-environment dataset (9 participants, 604 days), and achieved 98.6% accuracy and 56.9% F-score. The proposed features related to ingestion and digestion contribute to robust eating moment recognition.

Domain names and domain name system (DNS) have been used and abused for over 30 years since the 1980s. Although legitimate Internet users rely on domain names as their indispensable infrastructures for using the Internet, attackers use or abuse them as reliable, instantaneous, and distributed attack infrastructure. However, there is a lack of complete understanding of such domain name abuses and the methods for coping with them. In this paper, we design and implement a unified and objective analysis pipeline combining the existing defense solutions to realize practical and optimal defenses against today's malicious domain names. The basic concept underlying our novel analytical approach is malicious domain names' chromatography. Our new analysis pipeline can distinguish among mixtures of malicious domain names for websites. On the basis of this concept, we do not create a hodgepodge of existing solutions but design separation of abused domain names and offer defense information by considering the characteristics of malicious domain names as well as the possible defense solutions and points of defense. Finally, we evaluate our analysis pipeline and output defense information using a large and real dataset to show the effectiveness and validity of our proposed approach.

This work develops a method of detecting and classifying 'potentially unwanted applications' (PUAs) such as adware or remote monitoring tools. Our approach leverages DNS queries made by apps. Using a large sample of Android apps from third-party marketplaces, we first reveal that DNS queries can provide useful information for the detection and classification of PUAs. Next, we show that existing DNS blacklists are ineffective to perform these tasks. Finally, we demonstrate that our methodology performed with high accuracy.

Android is one of the most popular mobile device platforms. However, since Android apps can be disassembled easily, attackers inject additional advertisements or malicious codes to the original apps and redistribute them. There are a non-negligible number of such repackaged apps. We generally call those malicious repackaged apps "clones." However, there are apps that are not clones but are similar to each other. We call such apps "relatives." In this work, we developed a framework called APPraiser that extracts similar apps and classifies them into clones and relatives from the large dataset. We used the APPraiser framework to study over 1.3 million apps collected from both official and third-party marketplaces. Our extensive analysis revealed the following findings: In the official marketplace, 79% of similar apps were attributed to relatives, while in the third-party marketplace, 50% of similar apps were attributed to clones. The majority of relatives are apps developed by prolific developers in both marketplaces. We also found that in the third-party market, of the clones that were originally published in the official market, 76% of them are malware.

An enormous number of malware samples pose a major threat to our networked society. Antivirus software and intrusion detection systems are widely implemented on the hosts and networks as fundamental countermeasures. However, they may fail to detect evasive malware. Thus, setting a high priority for new varieties of malware is necessary to conduct in-depth analyses and take preventive measures. In this paper, we present a traffic model for malware that can classify network behaviors of malware and identify new varieties of malware. Our model comprises malwarespecific features and general traffic features that are extracted from packet traces obtained from a dynamic analysis of the malware. We apply a clustering analysis to generate a classifier and evaluate our proposed model using large-scale live malware samples. The results of our experiment demonstrate the effectiveness of our model in finding new varieties of malware.

We developed a novel, proof-of-concept side-channel attack framework called RouteDetector, which identifies a route for a train trip by simply reading smart device sensors: an accelerometer, magnetometer, and gyroscope. All these sensors are commonly used by many apps without requiring any permissions. The key technical components of RouteDetector can be summarized as follows. First, by applying a machine-learning technique to the data collected from sensors, RouteDetector detects the activity of a user, i.e., "walking," "in moving vehicle," or " other. "Next, it extracts departure/arrival times of vehicles from the sequence of the detected human activities. Finally, by correlating the detected departure/ arrival times of the vehicle with timetables/route maps collected from all the railway companies in the rider's country, it identifies potential routes that can be used for a trip. We demonstrate that the strategy is feasible through field experiments and extensive simulation experiments using timetables and route maps for 9,090 railway stations of 172 railway companies.

Web tracking is widely used as a means to track user's behavior on websites. While web tracking provides new opportunities of e-commerce, it also includes certain risks such as privacy infringement. Therefore, analyzing such risks in the wild Internet is meaningful to make the user's privacy transparent. This work aims to understand how the web tracking has been adopted to prominent websites. We also aim to understand their resilience to the ad-blocking techniques. Web tracking-enabled websites collect the information called the web browser fingerprints, which can be used to identify users. We develop a scalable system that can detect fingerprinting by using both dynamic and static analyses. If a tracking site makes use of many and strong fingerprints, the site is likely resilient to the ad-blocking techniques. We also analyze the connectivity of the third-party tracking sites, which are linked from multiple websites. The link analysis allows us to extract the group of associated tracking sites and understand how influential these sites are. Based on the analyses of 100,000 websites, we quantify the potential risks of the web tracking-enabled websites. We reveal that there are 226 websites that adopt fingerprints that cannot be detected with the most of off-the-shelf anti-tracking tools. We also reveal that a major, resilient third-party tracking site is linked to 50.0 % of the top-100,000 popular websites.

Today, websites are exposed to various threats that exploit their vulnerabilities. A compromised website will be used as a stepping-stone and will serve attackers' evil purposes. For instance, URL redirection mechanisms have been widely used as a means to perform web based attacks covertly; i.e., an attacker injects a redirect code into a compromised website so that a victim who visits the site will be automatically navigated to a malware distribution site. Although many defense operations against malicious websites have been developed, we still encounter many active malicious websites today. As we will show in the paper, we infer that the reason is associated with the evolution of the ecosystem of malicious redirection.
Given this background, we aim to understand the evolution of the ecosystem through long-term measurement. To this end, we developed a honeypot-based monitoring system, which specializes in monitoring the behavior of URL redirections. We deployed the monitoring system across four years and collected more than 100K malicious redirect URLs, which were extracted from 776 distinct websites. Our chief findings can be summarized as follows: (1) Click-fraud has become another motivation for attackers to employ URL redirection, (2) The use of web-based domain generation algorithms (DGAs) has become popular as a means to increase the entropy of redirect URLs to thwart URL blacklisting, and (3) Both domain flux and IP-flux are concurrently used for deploying the intermediate sites of redirect chains to ensure robustness of redirection.
Based on the results, we also present practical countermeasures against malicious URL redirections. Security/network operators can leverage useful information obtained from the honeypot-based monitoring system. For instance, they can disrupt infrastructures of web based attack by taking down domain names extracted from the monitoring system. They can also collect web advertising/tracking IDs, which can be used to identify the criminals behind attacks. (C) 2017 The Author(s). Published by Elsevier Ltd.

Damage caused by malware is a serious problem that needs to be addressed. The recent rise in the spread of evasive malware has made it difficult to detect it at the pre-infection timing. Malware detection at post-infection timing is a promising approach that fulfills this gap. Given this background, this work aims to identify likely malware-infected devices from the measurement of Internet traffic. The advantage of the traffic-measurement-based approach is that it enables us to monitor a large number of clients. If we find a client as a source of malicious traffic, the client is likely a malware-infected device. Since the majority of malware today makes use of the web as a means to communicate with the C&amp
C servers that reside on the external network, we leverage information recorded in the HTTP headers to discriminate between malicious and legitimate traffic. To make our approach scalable and robust, we develop the automatic template generation scheme that drastically reduces the amount of information to be kept while achieving the high accuracy of classification
since it does not make use of any domain knowledge, the approach should be robust against changes of malware. We apply several classifiers, which include machine learning algorithms, to the extracted templates and classify traffic into two categories: malicious and legitimate. Our extensive experiments demonstrate that our approach discriminates between malicious and legitimate traffic with up to 97.1% precision while maintaining the false positive below 1.0%.

This paper reports a large-scale study that aims to understand how mobile application (app) vulnerabilities are associated with software libraries. We analyze both free and paid apps. Studying paid apps was quite meaningful because it helped us understand how differences in app development/maintenance affect the vulnerabilities associated with libraries. We analyzed 30k free and paid apps collected from the official Android marketplace. Our extensive analyses revealed that approximately 70%/50% of vulnerabilities of free/paid apps stem from software libraries, particularly from third-party libraries. Somewhat paradoxically, we found that more expensive/popular paid apps tend to have more vulnerabilities. This comes from the fact that more expensive/popular paid apps tend to have more functionality, i.e., more code and libraries, which increases the probability of vulnerabilities. Based on our findings, we provide suggestions to stakeholders of mobile app distribution ecosystems.

<p>Hardware Trojans (HT) that are implemented at the time of manufacturing ICs are being reported as a new threat that could destroy the IC or degrade its security under specific circumstances, and is becoming a key security challenge that must be addressed. On the other hand, since it is also common to use components manufactured or bought via third parties in portions outside of the substrate on which the IC is mounted or communication lines connecting the IC and the substrate, there is a possibility that HTs may also be set in the peripheral circuits of the IC in the same manner as in the IC. In this paper, we developed an HT that could be implemented in the peripheral circuits and wiring of an IC, investigated the possibility of being able to acquire information processed inside a device by measuring the electromagnetic waves generated and leaked by Intentional Electromagnetic Interference (IEMI) with HT outside the device, and investigated detection methods for cases where such HTs are implemented.</p>

This paper investigates fundamental mechanisms of brightness changes in heart rate (HR) measurement from face images through three kinds of experiments
(i) measurement of light reflection from cheek covered with/without copper film, (ii) spectroscopy measurement of reflection light from face and (iii) simultaneous measurement of face images and laser speckle images. The brightness change of the face skin are found to be caused by both the green light absorption variation by the blood volume changes and the light reflection variation by pulsatory face movements. The Real-time Pulse Extraction Method (RPEM), designed to extract the variation of light absorption by removing motion noise, is corroborated for the robustness by comparing the RPEM with the pulse wave of the ear photoplethysmography. The RPEM is also applied to heart rate measurements of seven participants during office work under non-controlled condition in order to evaluate continuous real-time HR monitoring. RMSE = 6.7 bpm is achieved as an average result of seven participants in five days with the 44% of HR measured rate with respect to the number of reference HRs from the electrocardiogram during face is detected. The result indicates that the RPEM method enables HR monitoring in daily life.

Mobile app stores, such as Google Play, play a vital role in the ecosystem of mobile apps. When users look for an app of interest, they can acquire useful data from the app store to facilitate their decision on installing the app or not. This data includes ratings, reviews, number of installs, and the category of the app. The ratings and reviews are the user-generated content (UGC) that affect the reputation of an app. Unfortunately, miscreants also exploit such channels to conduct promotional attacks (PAs) that lure victims to install malicious apps. In this paper, we propose and develop a new system called PADetective to detect miscreants who are likely to be conducting promotional attacks. Using a dataset with 1,723 of labeled samples, we demonstrate that the true positive rate of detection model is 90%, with a false positive rate of 5.8%. We then applied PADetective to a large dataset for characterizing the prevalence of PAs in the wild and find 289 K potential PA attackers who posted reviews to 21 K malicious apps.

Adoption of SSL/TLS to protect the privacy of web users has become increasingly common. In fact, as of September 2015, more than 68% of top-1M websites deploy SSL/TLS to encrypt their traffic. The transition from HTTP to HTTPS has brought a new challenge for network operators who need to understand the hostnames of encrypted web traffic for various reasons. To meet the challenge, this work develops a novel framework called SFMap, which estimates names of HTTPS servers by analyzing precedent DNS queries/responses in a statistical way. The SFMap framework introduces domain name graph, which can characterize highly dynamic and diverse nature of DNS mechanisms. Such complexity arises from the recent deployment and implementation of DNS ecosystems; i.e., canonical name tricks used by CDNs, the dynamic and diverse nature of DNS TTL settings, and incomplete and unpredictable measurements due to the existence of various DNS caching instances. First, we demonstrate that SFMap establishes good estimation accuracies and outperforms a state-of-the-art approach. We also aim to identify the optimized setting of the SFMap framework. Next, based on the preliminary analysis, we introduce techniques to make the SFMap framework scalable to large-scale traffic data. We validate the effectiveness of the approach using large-scale Internet traffic. (C) 2016 Elsevier B.V. All rights reserved.

Cyber attackers abuse the domain name system (DNS) to mystify their attack ecosystems, they systematically generate a huge volume of distinct domain names to make it infeasible for blacklisting approaches to keep up with newly generated malicious domain names. As a solution to this problem, we propose a system for discovering malicious domain names that will likely be abused in future. The key idea with our system is to exploit temporal variation patterns (TVPs) of domain names. The TVPs of domain names include information about how and when a domain name has been listed in legitimate/popular and/or malicious domain name lists. On the basis of this idea, our system actively collects DNS logs, analyzes their TVPs, and predicts whether a given domain name will be used for malicious purposes. Our evaluation revealed that our system can predict malicious domain names 220 days beforehand with a true positive rate of 0.985.

Modern web users may encounter a browser security threat called drive-by-download attacks when surfing on the Internet. Drive-by-download attacks make use of exploit codes to take control of user's web browser. Many web users do not take such underlying threats into account while clicking URLs. URL Blacklist is one of the practical approaches to thwarting browser-targeted attacks. However, URL Blacklist cannot cope with previously unseen malicious URLs. Therefore, to make a URL blacklist effective, it is crucial to keep the URLs updated. Given these observations, we propose a framework called automatic blacklist generator (AutoBLG) that automates the collection of new malicious URLs by starting from a given existing URL blacklist. The primary mechanism of AutoBLG is expanding the search space of web pages while reducing the amount of URLs to be analyzed by applying several pre-filters such as similarity search to accelerate the process of generating blacklists. AutoBLG consists of three primary components: URL expansion, URL filtration, and URL verification. Through extensive analysis using a high-performance web client honeypot, we demonstrate that AutoBLG can successfully discover new and previously unknown drive-by-download URLs from the vast web space.

Modern web users may encounter a browser security threat called drive-by-download attacks when surfing on the Internet. Drive-by-download attacks make use of exploit codes to take control of user's web browser. Many web users do not take such underlying threats into account while clicking URLs. URL Blacklist is one of the practical approaches to thwarting browser-targeted attacks. However, URL Blacklist cannot cope with previously unseen malicious URLs. Therefore, to make a URL blacklist effective, it is crucial to keep the URLs updated. Given these observations, we propose a framework called automatic blacklist generator (AutoBLG) that automates the collection of new malicious URLs by starting from a given existing URL blacklist. The primary mechanism of AutoBLG is expanding the search space of web pages while reducing the amount of URLs to be analyzed by applying several pre-filters such as similarity search to accelerate the process of generating blacklists. AutoBLG consists of three primary components: URL expansion, URL filtration, and URL verification. Through extensive analysis using a high-performance web client honeypot, we demonstrate that AutoBLG can successfully discover new and previously unknown drive-by-download URLs from the vast web space.

Since it is not hard to repackage an Android app, there are many cloned apps, which we call "clones" in this work. As previous studies have reported, clones are generated for bad purposes by malicious parties, e.g., adding malicious functions, injecting/replacing advertising modules, and piracy. Besides such clones, there are legitimate, similar apps, which we call "relatives" in this work. These relatives are not clones but are similar in nature; i.e., they are generated by the same app-building service or by the same developer using a same template. Given these observations, this paper aims to answer the following two research questions: (RQ1) How can we distinguish between clones and relatives? (RQ2) What is the breakdown of clones and relatives in the official and third-party marketplaces? To answer the first research question, we developed a scalable framework called APPraiser that systematically extracts similar apps and classifies them into clones and relatives. We note that our key algorithms, which leverage sparseness of the data, have the time complexity of O(n) in practice. To answer the second research question, we applied the APPraiser framework to the over 1 3 millions of apps collected from official and third-party marketplaces. Our analysis revealed the following findings: In the official marketplace, 79% of similar apps were attributed to relatives while, in the third-party marketplace, 50% of similar apps were attributed to clones. The majority of relatives are apps developed by prolific developers in both marketplaces. We also found that in the third-party market, of the clones that were originally published in the official market, 76% of them are malware. To the best of our knowledge, this is the first work that clarified the breakdown of "similar" Android apps, and quantified their origins using a huge dataset equivalent to the size of official market.

Since it is not hard to repackage an Android app, there are many cloned apps, which we call "clones" in this work. As previous studies have reported, clones are generated for bad purposes by malicious parties, e.g., adding malicious functions, injecting/replacing advertising modules, and piracy. Besides such clones, there are legitimate, similar apps, which we call "relatives" in this work. These relatives are not clones but are similar in nature; i.e., they are generated by the same app-building service or by the same developer using a same template. Given these observations, this paper aims to answer the following two research questions: (RQ1) How can we distinguish between clones and relatives? (RQ2) What is the breakdown of clones and relatives in the official and third-party marketplaces? To answer the first research question, we developed a scalable framework called APPraiser that systematically extracts similar apps and classifies them into clones and relatives. We note that our key algorithms, which leverage sparseness of the data, have the time complexity of O(n) in practice. To answer the second research question, we applied the APPraiser framework to the over 1 3 millions of apps collected from official and third-party marketplaces. Our analysis revealed the following findings: In the official marketplace, 79% of similar apps were attributed to relatives while, in the third-party marketplace, 50% of similar apps were attributed to clones. The majority of relatives are apps developed by prolific developers in both marketplaces. We also found that in the third-party market, of the clones that were originally published in the official market, 76% of them are malware. To the best of our knowledge, this is the first work that clarified the breakdown of "similar" Android apps, and quantified their origins using a huge dataset equivalent to the size of official market.

Most modern Internet services are carried over the web. A significant amount of web transactions is now encrypted and the transition to encryption has made it difficult for network operators to understand traffic mix. Thegoal of this study is to enable network operators to inferhostnames within HTTPS traffic because hostname information is useful to understand the breakdown of encrypted web traffic. The proposed approach correlates HTTPS flows and DNS queries/responses. Although this approach may appear trivial, recent deployment and implementation ofDNS ecosystems have made it a challenging research problem; i. e., canonical name tricks used by CDNs, the dynamic and diverse nature of DNS TTL settings, and incompletemeasurements due to the existence of various caching mechanisms. To tackle these challenges, we introduce domain name graph (DNG), which is a formal expression that characterizes the highly dynamic and diverse nature of DNS mechanisms. Furthermore, we have developed a framework called ServiceFlow map (SFMap) that works on top of the DNG. SFMap statistically estimates the hostname of an HTTPS server, given a pair of client and server IP addresses. We evaluate the performance ofSFMapthrough extensive analysis using real packet traces collected from two locations with different scales. Wedemonstrate thatSFMapestablishes good estimation accuracies and outperforms a stateoftheart approach.

A Darknet is a passive sensor system that monitors traffic routed to unused IP address space. Darknets have been widely used as tools to detect malicious activities such as propagating worms, thanks to the useful feature that most packets observed by a darknet can be assumed to have originated from non-legitimate hosts. Recent commoditization of Internet-scale survey traffic originating from legitimate hosts could overwhelm the traffic that was originally supposed to be monitored with a darknet. Based on this observation, we posed the following research question: "Can the Internet-scale survey traffic become noise when we analyze darknet traffic?" To answer this question, we propose a novel framework, ID2, to increase the darkness of darknet traffic, i.e., ID2 discriminates between Internet-scale survey traffic originating from legitimate hosts and other traffic potentially associated with malicious activities. It leverages two intrinsic characteristics of Internet-scale survey traffic: a network-level property and some form of footprint explicitly indicated by surveyors. When we analyzed darknet traffic using ID2, we saw that Internet-scale traffic can be noise. We also demonstrated that the discrimination of survey traffic exposes hidden traffic anomalies, which are invisible without using our technique.

To automate mal ware analysis, dynamic malware analysis systems have attracted increasing attention from both the industry and research communities. Of the various logs collected by such systems, the API call is a very promising source of information for characterizing mal ware behavior. This work aims to extract similar mal ware samples automatically using the concept of "API call topics;" which represents a set of API calls that are intrinsic to a specific group of malware samples. We first convert Win32 API calls into "API words." We then apply non-negative matrix factorization (NMF) clustering analysis to the corpus of the extracted API words. NMF automatically generates the API call topics from the API words. The contributions of this work can be summarized as follows. We present an unsupervised approach to extract API call topics from a large corpus of API calls. Through analysis of the API call logs collected from thousands of mal ware samples, we demonstrate that the extracted API call topics can detect similar malware samples. The proposed approach is expected to be useful for automating the process of analyzing a huge volume of logs collected from dynamic malware analysis systems.

Most modern Internet services are carried over the web. A significant amount of web transactions is now encrypted and the transition to encryption has made it difficult for network operators to understand traffic mix. Thegoal of this study is to enable network operators to inferhostnames within HTTPS traffic because hostname information is useful to understand the breakdown of encrypted web traffic. The proposed approach correlates HTTPS flows and DNS queries/responses. Although this approach may appear trivial, recent deployment and implementation ofDNS ecosystems have made it a challenging research problem; i. e., canonical name tricks used by CDNs, the dynamic and diverse nature of DNS TTL settings, and incompletemeasurements due to the existence of various caching mechanisms. To tackle these challenges, we introduce domain name graph (DNG), which is a formal expression that characterizes the highly dynamic and diverse nature of DNS mechanisms. Furthermore, we have developed a framework called ServiceFlow map (SFMap) that works on top of the DNG. SFMap statistically estimates the hostname of an HTTPS server, given a pair of client and server IP addresses. We evaluate the performance ofSFMapthrough extensive analysis using real packet traces collected from two locations with different scales. Wedemonstrate thatSFMapestablishes good estimation accuracies and outperforms a stateoftheart approach.

Modern web users are exposed to a browser security threat called drive-by-download attacks that occur by simply visiting a malicious Uniform Resource Locator (URL) that embeds code to exploit web browser vulnerabilities. Many web users tend to click such URLs without considering the underlying threats. URL blacklists are an effective countermeasure to such browser-targeted attacks. URLs are frequently updated; therefore, collecting fresh malicious URLs is essential to ensure the effectiveness of a URL blacklist. We propose a framework called automatic blacklist generator (AutoBLG) that automatically identifies new malicious URLs using a given existing URL blacklist. The key idea of AutoBLG is expanding the search space of web pages while reducing the amount of URLs to be analyzed by applying several pre-filters to accelerate the process of generating blacklists. AutoBLG comprises three primary primitives: URL expansion, URL filtration, and URL verification. Through extensive analysis using a high-performance web client honeypot, we demonstrate that AutoBLG can successfully extract new and previously unknown drive-by-download URLs.

A Darknet is a passive sensor system that monitors traffic routed to unused IP address space. Darknets have been widely used as tools to detect malicious activities such as propagating worms, thanks to the useful feature that most packets observed by a darknet can be assumed to have originated from non-legitimate hosts. Recent commoditization of Internet-scale survey traffic originating from legitimate hosts could overwhelm the traffic that was originally supposed to be monitored with a darknet. Based on this observation, we posed the following research question: "Can the Internet-scale survey traffic become noise when we analyze darknet traffic?" To answer this question, we propose a novel framework, ID2, to increase the darkness of darknet traffic, i.e., ID2 discriminates between Internet-scale survey traffic originating from legitimate hosts and other traffic potentially associated with malicious activities. It leverages two intrinsic characteristics of Internet-scale survey traffic: a network-level property and some form of footprint explicitly indicated by surveyors. When we analyzed darknet traffic using ID2, we saw that Internet-scale traffic can be noise. We also demonstrated that the discrimination of survey traffic exposes hidden traffic anomalies, which are invisible without using our technique.

Understanding the impacts and patterns of network events such as link flaps or hardware errors is crucial for diagnosing network anomalies. In large production networks, analyzing the log messages that record network events has become a challenging task due to the following two reasons. First, the log messages are composed of unstructured text messages generated by vendor-specific rules. Second, network equipment such as routers, switches, and RADIUS severs generate various log messages induced by network events that span across several geographical locations, network layers, protocols, and services. In this paper, we have tackled these obstacles by building two novel techniques: statistical template extraction (STE) and log tensor factorization (LTF). STE leverages a statistical clustering technique to automatically extract primary templates from unstructured log messages. LTF aims to build a statistical model that captures spatial-temporal patterns of log messages. Such spatial-temporal patterns provide useful insights into understanding the impacts and root cause of hidden network events. This paper first formulates our problem in a mathematical way. We then validate our techniques using massive amount of network log messages collected from a large operating network. We also demonstrate several case studies that validate the usefulness of our technique.

Understanding the impacts and patterns of network events such as link flaps or hardware errors is crucial for diagnosing network anomalies. In large production networks, analyzing the log messages that record network events has become a challenging task due to the following two reasons. First, the log messages are composed of unstructured text messages generated by vendor-specific rules. Second, network equipment such as routers, switches, and RADIUS severs generate various log messages induced by network events that span across several geographical locations, network layers, protocols, and services. In this paper, we have tackled these obstacles by building two novel techniques: statistical template extraction (STE) and log tensor factorization (LTF). STE leverages a statistical clustering technique to automatically extract primary templates from unstructured log messages. LTF aims to build a statistical model that captures spatial-temporal patterns of log messages. Such spatial-temporal patterns provide useful insights into understanding the impacts and root cause of hidden network events. This paper first formulates our problem in a mathematical way. We then validate our techniques using massive amount of network log messages collected from a large operating network. We also demonstrate several case studies that validate the usefulness of our technique. © 2014 IEEE.

We have proposed a method of identifying superspreaders by flow sampling and a method of filtering legitimate hosts from the identified superspreaders using a white list. However, the problem of how to optimally set parameters of phi, the measurement period length, m*, the identification threshold of the flow count m within phi, and H*, the identification probability for hosts with m = m*, remained unsolved. These three parameters seriously impact the ability to identify the spread of infection. Our contributions in this work are two-fold: (1) we propose a method of optimally designing these three parameters to satisfy the condition that the ratio of the number of active worm-infected hosts divided by the number of all vulnerable hosts is bound. by a given upper-limit during the time T required to develop a patch or an anti-worm vaccine, and (2) the proposed method can optimize the identification accuracy of worm-infected hosts by maximally using a limited amount of memory resource of monitors.

We have proposed a method of identifying superspreaders by flow sampling and a method of filtering legitimate hosts from the identified superspreaders using a white list. However, the problem of how to optimally set parameters of phi, the measurement period length, m*, the identification threshold of the flow count m within phi, and H*, the identification probability for hosts with m = m*, remained unsolved. These three parameters seriously impact the ability to identify the spread of infection. Our contributions in this work are two-fold: (1) we propose a method of optimally designing these three parameters to satisfy the condition that the ratio of the number of active worm-infected hosts divided by the number of all vulnerable hosts is bound. by a given upper-limit during the time T required to develop a patch or an anti-worm vaccine, and (2) the proposed method can optimize the identification accuracy of worm-infected hosts by maximally using a limited amount of memory resource of monitors.

We consider the mean-variance relationship of the number of flows in traffic aggregation, where flows are divided into several groups randomly, based on a predefined flow aggregation index, such as source IP address. We first derive a quadratic relationship between the mean and the variance of the number of flows belonging to a randomly chosen traffic aggregation group. Note here that the result is applicable to sampled flows obtained through packet sampling. We then show that our analytically derived mean-variance relationship fits well those in actual packet trace data sets. Next, we present two applications of the mean-variance relationship to traffic management. One is an application to detecting network anomalies through monitoring a time series of traffic. Using the mean-variance relationship, we determine the traffic aggregation level in traffic monitoring so that it meets two predefined requirements on false positive and false negative ratios simultaneously. The other is an application to load balancing among network equipments that require per-flow management. We utilize the mean-variance relationship for estimating the processing capability required in each network equipment. (C) 2013 Elsevier B.V. All rights reserved.

The transmission bandwidth consumed by delivering rich content, such as movie files, is enormous, so it is urgent for ISPs to design an efficient delivery system minimizing the amount of network resources consumed. To serve users rich content economically and efficiently, an ISP itself should provide servers with huge storage capacities at a limited number of locations within its network. Therefore, we have investigated the content deployment method and the content delivery process that are desirable for this ISP-operated content delivery network (CDN). We have also proposed an optimum cache server allocation method for an ISP-operated CDN. In this paper, we investigate the properties of the topological locations of nodes at which cache placement is effective using 31 network topologies of actual ISPs. We also classify the 31 networks into two types and evaluate the optimum cache count in each network type.

In monitoring flows at routers for flow analysis or deep packet inspection, the monitor calculates hash values from the flow ID of each packet arriving at the input port of the router. Therefore, the monitors must update the flow table at the transmission line rate, so high-speed and high-cost memory, such as SRAM, is used for the flow table. This requires the monitors to limit the monitoring target to just some of the flows. However, if the monitors randomly select the monitoring targets, multiple routers on the route will sometimes monitor the same flow, or no monitors will monitor a flow. To maximize the number of monitored flows in the entire network, the monitors must select the monitoring targets while maintaining a balanced load among them. We propose an autonomous load-balancing method where monitors exchange information on monitor load only with adjacent monitors. Numerical evaluations using the actual traffic matrix of Internet2 show that the proposed method improves the total monitored flow count by about 50% compared with that of independent sampling. Moreover, we evaluate the load-balancing effect on 36 backbone networks of commercial ISPs. (c) 2012 Elsevier B.V. All rights reserved.

Web-based malware attacks have become one of the most serious threats that need to be addressed urgently. Several approaches that have attracted attention as promising ways of detecting such malware include employing one of several blacklists. However, these conventional approaches often fail to detect new attacks owing to the versatility of malicious websites. Thus, it is difficult to maintain up-to-date blacklists with information for new malicious websites. To tackle this problem, this paper proposes a new scheme for detecting malicious websites using the characteristics of IP addresses. Our approach leverages the empirical observation that IP addresses are more stable than other metrics such as URLs and DNS records. While the strings that form URLs or DNS records are highly variable, IP addresses are less variable, i.e., IPv4 address space is mapped onto 4-byte strings. In this paper, a lightweight and scalable detection scheme that is based on machine learning techniques is developed and evaluated. The aim of this study is not to provide a single solution that effectively detects web-based malware but to develop a technique that compensates the drawbacks of existing approaches. The effectiveness of our approach is validated by using real IP address data from existing blacklists and real traffic data on a campus network. The results demonstrate that our scheme can expand the coverage/accuracy of existing blacklists and also detect unknown malicious websites that are not covered by conventional approaches.

This paper introduces our recent results on mode-division multiplexing transmission with MIMO processing. We have been studying coherent optical MIMO transmission systems and developing few-mode fibers to reduce the complexity of MIMO processing, for example, by using multi-step index fibers to control the differential mode delay (DMD) of the fibers and to compensate for the total DMD. We also investigated a transmission system using reduced-complexity MIMO processing. Finally, we review our latest 2×2 WDM-MIMO transmission experiments with low MIMO processing complexity. © 2012 SPIE.

Content services that deliver large-volume content files have been growing rapidly. In these services, it is crucial for the service provider and the network operator to minimize traffic volume in order to lower the cost charged for bandwidth and the cost for network infrastructure, respectively. To reduce the traffic, traffic localization has been discussed; network traffic is localized when requested content files are served by an other nearby altruistic client instead of the source servers. With this mechanism, the concept of the peer-assisted content delivery network (CDN) can localize the overall traffic and enable service providers to minimize traffic without deploying or borrowing distributed storage. To localize traffic effectively, content files that are likely to be requested by many clients should be cached locally. We present a traffic engineering scheme for peer-assisted CDN models. Its key idea is to control the behavior of clients by using a content-oriented incentive mechanism. This approach optimizes traffic flows by letting altruistic clients download content files that are most likely to contribute to localizing network traffic. To let altruistic clients request the desired files, we combine content files while keeping the price equal to that for a single content. We discuss the performance of our proposed algorithm considering the cache replacement algorithms.

Web-based malware attacks have become one of the most serious threats that need to be addressed urgently. Several approaches that have attracted attention as promising ways of detecting such malware include employing one of several blacklists. However, these conventional approaches often fail to detect new attacks owing to the versatility of malicious websites. Thus, it is difficult to maintain up-to-date blacklists with information for new malicious websites. To tackle this problem, this paper proposes a new scheme for detecting malicious websites using the characteristics of IP addresses. Our approach leverages the empirical observation that IP addresses are more stable than other metrics such as URLs and DNS records. While the strings that form URLs or DNS records are highly variable, IP addresses are less variable, i.e., IPv4 address space is mapped onto 4-byte strings. In this paper, a lightweight and scalable detection scheme that is based on machine learning techniques is developed and evaluated. The aim of this study is not to provide a single solution that effectively detects web-based malware but to develop a technique that compensates the drawbacks of existing approaches. The effectiveness of our approach is validated by using real IP address data from existing blacklists and real traffic data on a campus network. The results demonstrate that our scheme can expand the coverage/accuracy of existing blacklists and also detect unknown malicious websites that are not covered by conventional approaches. © 2013 Information Processing Society of Japan.

Recently, the number of users downloading video content on the Internet has dramatically increased, and it is highly anticipated that downloading huge size, rich content such as movie files will become a popular use of the Internet in the near future. The transmission bandwidth consumed by delivering rich content is enormous, so it is urgent for ISPs to design an efficient delivery system that minimizes the amount of network resources consumed. To deliver web content efficiently, a content delivery network (CDN) is often used. CDN providers collocate a huge number of servers within multiple ISPs without being informed of detailed network information, i.e., network topologies, from ISPs. Minimizing the amount of network resources consumed is difficult because a CDN provider selects a server for each request based on only rough estimates of response time. Therefore, an ordinary CDN is not suited for delivering rich content. P2Pbased delivery systems are becoming popular as scalable delivery systems. However, by using a P2P-based system, we still cannot obtain the ideal delivery pattern that is optimal for ISPs because the server locations depend on users behaving selfishly. To provide rich content to users economically and efficiently, an ISP itself should optimally provide servers with huge storage capacities at a limited number of locations within its network. In this paper, we investigate the content deployment method, the content delivery process, and the server allocation method that are desirable for this ISP-operated CDN. Moreover, we evaluate the effectiveness of the ISPoperated CDN using the actual network topologies of commercial ISPs. Copyright © 2013 The Institute of Electronics, Information and Communication Engineers.

We analyze measured traffic data to investigate the characteristics of TCP quality metrics such as packet retransmission rate, roundtrip time (RTT), and throughput of connections classified by their type (client-server (C/S) or peer-to-peer (P2P)), or by the location of the connection host (domestic or overseas). Our findings are as follows. (i) The TCP quality metrics of the measured traffic data are not necessarily consistent with a theoretical formula proposed in a previous study. However, the average RTT and retransmission rate are negatively correlated with the throughput, which is similar to this formula. Furthermore, the maximum idle time, which is defined as the maximum length of the packet interarrival times, is negatively correlated with throughput. (ii) Each TCP quality metric of C/S connections is higher than that of P2P connections. Here "higher quality" means that either the throughput is higher, or the other TCP quality metrics lead to higher throughput
for example the average RTT is lower or the retransmission rate is lower. Specifically, the median throughput of C/S connections is 2.5 times higher than that of P2P connections in the incoming direction of domestic traffic. (iii) The characteristics of TCP quality metrics depend on the location of the host of the TCP connection. There are cases in which overseas servers might use a different TCP congestion control scheme. Even if we eliminate these servers, there is still a difference in the degree of impact the average RTT has on the throughput between domestic and overseas traffic. One reason for this is thought to be the difference in the maximum idle time, and another is the fact that congestion levels of these types of traffic differ, even if their average RTTs are the same. Copyright © 2013 The Institute of Electronics, Information and Communication Engineers.

In Video on Demand (VoD) services, the demand for content items greatly changes daily over the course of the day. Because service providers are required to maintain a stable service during peak hours, they need to design system resources on the basis of peak demand time, so reducing the server load at peak times is important. To reduce the peak load of a content server, we propose to multicast popular content items to all users independently of actual requests as well as providing on-demand unicast delivery. With this solution, however, the hit ratio of pre-distributed content items is small, and large-capacity Storage is required at each set-top box (STB). We can expect to cope with this problem by limiting the number of pre-distributed content items or clustering users based on their viewing histories. We evaluated the effect of these techniques by using actual VoD access log data. We also evaluated the total cost of the multicast pre-distribution VoD system with the proposed two techniques.

Web-based malware attacks have become one of the most serious threats that need to be addressed urgently. Several approaches that have attracted attention as promising ways of detecting such malware include employing one of several blacklists. However, these conventional approaches often fail to detect new attacks owing to the versatility of malicious websites. Thus, it is difficult to maintain up-to-date blacklists with information for new malicious websites. To tackle this problem, this paper proposes a new scheme for detecting malicious websites using the characteristics of IP addresses. Our approach leverages the empirical observation that IP addresses are more stable than other metrics such as URLs and DNS records. While the strings that form URLs or DNS records are highly variable, IP addresses are less variable, i.e., IPv4 address space is mapped onto 4-byte strings. In this paper, a lightweight and scalable detection scheme that is based on machine learning techniques is developed and evaluated. The aim of this study is not to provide a single solution that effectively detects web-based malware but to develop a technique that compensates the drawbacks of existing approaches. The effectiveness of our approach is validated by using real IP address data from existing blacklists and real traffic data on a campus network. The results demonstrate that our scheme can expand the coverage/accuracy of existing blacklists and also detect unknown malicious websites that are not covered by conventional approaches. © 2013 Information Processing Society of Japan.

In content services where people purchase and download large-volume contents, minimizing network traffic is crucial for the service provider and the network operator since they want to lower the cost charged for bandwidth and the cost for network infrastructure, respectively. Traffic localization is an effective way of reducing network traffic. Network traffic is localized when a client can obtain the requested content files from other a near-by altruistic client instead of the source servers. The concept of the peer-assisted content distribution network (CDN) can reduce the overall traffic with this mechanism and enable service providers to minimize traffic without deploying or borrowing distributed storage. To localize traffic effectively, content files that are likely to be requested by many clients should be cached locally. This paper presents a novel traffic engineering scheme for peer-assisted CDN models. Its key idea is to control the behavior of clients by using content-oriented incentive mechanism. This approach enables us to optimize traffic flows by letting altruistic clients download content files that are most likely contributed to localizing traffic among clients. In order to let altruistic clients request the desired files, we combine content files while keeping the price equal to the one for a single content. This paper presents a solution for optimizing the selection of content files to be combined so that cross traffic in a network is minimized. We also give a model for analyzing the upper-bound performance and the numerical results.

We investigate the impact of traffic on the performance of large-scale NAT (LSN). since it has been attracting attention as a means of better utilizing the limited number of global IPv4 addresses. We focus on the number of active flows because they drive up the LSN memory requirements in two ways; more flows must be held in LSN memory, and more global IPv4 addresses must be prepared. Through traffic measurement data analysis, we found that more than 1% of hosts generated more than 100 TCP flows or 486 UDP flows at the same time, and on average, there were 1.43-3.99 active TCP flows per host, when the inactive timer used to clear the flow state from a flow table was set to 15s. When the timer is changed from 15 s to 10 min, the number of active flows increases more than tenfold. We also investigate how to reduce the above impact on LSN in terms of saving memory space and accommodating more users for each global IPv4 address. We show that to save memory space, regulating network anomalies can reduce the number of active TCP flows on an LSN by a maximum of 48.3% and by 29.6% on average. We also discuss the applicability of a batch flow-arrival model for estimating the variation in the number of active flows, when taking into account that the variation is needed to prepare an appropriate memory space. One way to allow each global IPv4 address to accommodate more users is to better utilize destination IP address information when mapping a source IP address from a private address to a global IPv4 address. This can effectively reduce the required number of global IPv4 addresses by 85.9% for TCP traffic and 91.9% for UDP traffic on average.

Internet threats caused by botnets/worms are one of the most important security issues to be addressed. Darknet, also called a dark IP address space, is one of the best solutions for monitoring anomalous packets sent by malicious software. However, since darknet is deployed only on an inactive IP address space, it is an inefficient way for monitoring a Working network that has a considerable number of active IP addresses. The present paper addresses this problem. We propose a scalable, lightweight malicious packet monitoring system based on a multi-dimensional IP/port analysis. Our system significantly extends the monitoring scope of darknet. In order to extend the capacity of darknet, our approach leverages the active IP address space without affecting legitimate traffic. Multidimensional monitoring enables the monitoring of TCP ports with firewalls enabled on each of the IP addresses. We focus on delays of TCP syn/ack responses in the traffic. We locate syn/ack delayed packets and forward them to sensors or honeypots for further analysis. We also propose a policy-based flow classification and forwarding mechanism and develop a prototype of a monitoring system that implements our proposed architecture. We deploy our system on a campus network and perform several experiments for the evaluation of our system. We verify that our system can cover 89% of the IP addresses while darknet-based monitoring only covers 46%. On our campus network, our system monitors twice as many IP addresses as darknet.

We quantitatively evaluate how sampling and spatio/temporal granularity in traffic monitoring affect the detectability of anomalous traffic. Those parameters also affect the monitoring burden, so network operators face a trade-off between the monitoring burden and detectability and need to know which are the optimal paramter values. We derive equations to calculate the false positive ratio and false negative ratio for given values of the sampling rate, granularity, statistics of normal traffic, and volume of anomalies to be detected. Specifically, assuming that the normal traffic has a Gaussian distribution, which is parameterized by its mean and standard deviation, we analyze how sampling and monitoring granularity change these distribution parameters. This analysis is based on observation of the backbone traffic, which exhibits spatially uncorrelated and temporally long-range dependence. Then we derive the equations for delectability. With those equations, we can answer the practical questions that arise in actual network operations: what sampling rate to set to find the given volume of anomaly, or, if the sampling is too high for actual operation, what granularity is optimal to find the anomaly for a given lower limit of sampling rate.

Web-based malware attacks have become one of the most serious threats that need to be addressed urgently. Several approaches that have attracted attention as promising ways of detecting such malware include employing various blacklists. However, these conventional approaches often fail to detect new attacks owing to the versatility of malicious websites. Thus, it is difficult to maintain up-to-date blacklists with information regarding new malicious websites. To tackle this problem, we propose a new method for detecting malicious websites using the characteristics of IP addresses. Our approach leverages the empirical observation that IP addresses are more stable than other metrics such as URL and DNS. While the strings that form URLs or domain names are highly variable, IP addresses are less variable, i.e., IPv4 address space is mapped onto 4-bytes strings. We develop a lightweight and scalable detection scheme based on the machine learning technique. The aim of this study is not to provide a single solution that effectively detects web-based malware but to develop a technique that compensates the drawbacks of existing approaches. We validate the effectiveness of our approach by using real IP address data from existing blacklists and real traffic data on a campus network. The results demonstrate that our method can expand the coverage/accuracy of existing blacklists and also detect unknown malicious websites that are not covered by conventional approaches.

Monitoring flows at routers for flow analysis or deep packet inspection requires the monitors to update monitored flow information at the transmission line rate and needs to use highspeed memory such as SRAM. Therefore, it is difficult to measure all flows, and the monitors need to limit the monitoring target to a part of the flows. However, if monitoring targets are randomly selected, an identical flow will be monitored at multiple routers on its route, or a flow will not be monitored at any routers on its route. To maximize the number of flows monitored in the entire network, the monitors are required to select the monitoring targets while maintaining a balanced load among the monitors. In this paper, we propose an autonomous load balancing method where monitors exchange monitor load information with only adjacent monitors.

A sophisticated ad hoc cloud computing environment (SpACCE) providing calculation capacity of PCs is proposed to facilitate distributed collaboration. Distributed collaboration is now indispensable in daily work and mainly occurs ad hoc in offices and laboratories. However, computer resources in offices and laboratories are under-utilized, while conventional cloud computing environments composed of dedicated servers are not suited to flexibly deploying applications ad hoc. A SpACCE can be built according to the needs that occur at any given time on a set of personal, i.e., non-dedicated, PCs and dynamically migrate a server for application sharing to another PC. CollaboTray, an application-sharing system, indispensable to share any application without modification, is employed to realize the migration of a server. By migrating a server, the redundant calculation capacity of PCs used for individual work can be utilized to produce a sophisticated ad hoc cloud computing environment, where the response time of the application shared among the users is improved. The level of calculation capacity required to execute the migration of a server and the effectiveness of the migration were clarified by building a SpACCE in a university research room. © 2012 IEEE.

We investigated the detection accuracy of network anomalies when using flow statistics obtained through packet sampling. Through a case study based on measurement data, we showed that network anomalies generating a large number of small flows, such as network scans or SYN flooding, become difficult to detect during packet sampling. We then developed an analytical model that enables us to quantitatively evaluate the effect of packet sampling and traffic conditions, such as anomalous traffic volume, on detection accuracy. We also investigated how the detection accuracy worsens when the packet sampling rate decreases. In addition, we show that, even with a low sampling rate, spatially partitioning monitored traffic into groups makes it possible to increase detection accuracy. We also developed a method of determining an appropriate number of partitioned groups, and we show its effectiveness. Copyright (C) 2011 John Wiley & Sons, Ltd.

In the Internet, video streaming services, in which users can enjoy videos at home, are becoming popular. Video streaming with high definition TV (HDTV) or ultra high definition video (UHDV) quality will be also provided and widely demanded in the future. However, the transmission bit-rate of high-quality video streaming is quite large, so generated traffic flows will cause link congestion. In the Internet, routes that packets take are determined using static link weights, so the network productivity, i.e., the maximum achievable throughout by the network, is determined by the capacity of a bottleneck link with the maximum utilization, although utilizations of many links remain low level. Therefore, when providing streaming services of rich content, i.e., videos with HDTV or UHDV quality, it is important to flatten the link utilization, i.e., reduce the maximum link utilization. We propose that ISPs use multiple servers to deliver rich content to balance the link utilization and propose server allocation and server selection methods for parallel delivery. We evaluate the effect of parallel delivery using 23 actual commercial ISP networks. (C) 2010 Elsevier B.V. All rights reserved.

MapReduceを実行する大規模分散システムの性能評価モデルの構築に向け,MapReduceによる大規模データ処理を実行した際にシステム全体に生じる負荷をネットワークの観点から分析したケーススタディを紹介する.

Traffic caused by P2P services dominates a large part of traffic on the Internet and imposes significant loads on the Internet, so reducing P2P traffic within networks is an important issue for ISPs. In particular, a huge amount of traffic is transferred within backbone networks; therefore reducing P2P traffic is important for transit ISPs to improve the efficiency of network resource usage and reduce network capital cost. To reduce P2P traffic, it is effective for ISPs to implement cache devices at some router ports and reduce the hop length of P2P flows by delivering the required content from caches. However, the design problem of cache locations and capacities has not been well investigated, although the effect of caches strongly depends on the cache locations and capacities. We propose an optimum design method of cache capacity and location for minimizing the total amount of P2P traffic based on dynamic programming, assuming that transit ISPs provide caches at transit links to access ISP networks. We apply the proposed design method to 31 actual ISP backbone networks and investigate the main factors determining cache efficiency. We also analyze the property of network structure in which deploying caches are effective in reducing P2P traffic for transit ISPs. We show that transit ISPs can reduce the P2P traffic within their networks by about 50-85% by optimally designing caches at the transit links to the lower networks. (C) 2010 Elsevier B.V. All rights reserved.

Due to integrated high-speed networks accommodating various types of services and applications, the quality of service (QoS) requirements for those networks have also become diverse. The network resources are shared by the individual service traffic in the integrated network. Thus, the QoS of all the services may be degraded indiscriminately when the network becomes congested due to a sudden increase in traffic for a particular service if there is no traffic engineering taking into account each service's QoS requirement. To resolve this problem, we present a method of controlling individual service traffic by using an overlay network, which makes it possible to flexibly add various functionalities. The overlay network provides functionalities to control individual service traffic, such as constructing an overlay network topology for each service, calculating the optimal route for the service's QoS, and caching the content to reduce traffic. Specifically, we present a method of overlay routing that is based on the Hedge algorithm, an online learning algorithm to guarantee an upper bound in the difference from the optimal performance. We show the effectiveness of our overlay routing through simulation analysis for various network topologies. © 2011 IEEE.

The number of users of VoD services in which users can request content delivery on demand has increased dramatically. In VoD services, the demand for content changes greatly daily. Because service providers are required to maintain a stable service during peak hours, they need to design the system resources based on the demand at the peak time, so reducing the server load at the peak time is an important issue. Although multicast delivery in which multiple users requesting the same content are supported by one delivery session is effective for suppressing the server load during peak hours, the response time of users seriously increases. A P2P-assisted delivery system in which users download content from other users watching the same content is also effective for reducing the server load. However, the system performance depends on selfish user behavior, and optimizing the usage of system resources is difficult. Moreover, complex operation, i.e., switching the delivery multicast tree or source peers, is necessary to support VCR operation. In this paper, we propose to reduce the server load without increasing user response time by multicasting popular content to all users independently of actual requests as well as providing on-demand unicast delivery. Through numerical evaluation using actual VoD access log data, we clarify the effectiveness of the proposed method. © 2011 IEEE.

Peer-assisted content distribution technologies have been attracting attention. By using not only server resources but also the resources of end hosts (i.e., peers), we can reduce the offered load on servers as well as utilization of the access bandwidth of the servers. However, offered traffi to the network may increase because the traffi exchanged between peers passes across the network. Specificall, if individual peers send traffi disregarding underlay network topology and traffi conditions, the peer-assisted content distribution method may cause excessive traffi offered to the network and poor application performance. We thus investigated the impact of traffi caused by peer-assisted content distribution on the underlay network. We found that although peer-assisted content distribution disregarding underlay network topology causes 80120% additional traffi compared with the optimal case, i.e., content distribution using cache servers allocated optimally in the network, using underlay network topology enables us to achieve almost the same efficien network resource utilization as the optimal case. We also found that the peer-assisted approach can adaptively cope with change in the traffi demand matrix because uploaders in the network are generated according to the demand matrix in a self-organizing manner. This is because peers that have downloaded the content become uploaders so many uploaders are generated in the area where a large number of content requests exist according to the traffi condition
therefore, the content delivery traffi can be localized. © 2011 IEEE.

In Video on Demand (VoD) services, the demand for content items greatly changes daily, so reducing the server load at the peak time is an important issue for ISPs to reduce the server cost. To achieve this goal, we proposed to reduce the server load by multicasting popular content items to all users independently of actual requests as well as providing on-demand unicast delivery. In this solution, however, the hit ratio of pre-distributed content items is small, and a large-capacity storage is required at set-top box (STB). We might be able to cope with this problem by limiting the number of pre-distributed content items or clustering users based on the history of viewing. We evaluate the effect of these techniques using actual VoD access log data. We clarify that the required storage capacity at STB can be halved while keeping the effect of server load reduction to about 80% by limiting pre-distributed content items, and user clustering is effective only when the cluster count is about two. © 2011 IEEE.

Due to integrated high-speed networks accommodating various types of services and applications, the quality of service (QoS) requirements for those networks have also become diverse. The network resources are shared by the individual service traffic in the integrated network. Thus, the QoS of all the services may be degraded indiscriminately when the network becomes congested due to a sudden increase in traffic for a particular service if there is no traffic engineering taking into account each service's QoS requirement. To resolve this problem, we present a method of controlling individual service traffic by using an overlay network, which makes it possible to flexibly add various functionalities. The overlay network provides functionalities to control individual service traffic, such as calculating the optimal route for each service's QoS. Specifically, we present a method of overlay routing that is based on the Hedge algorithm, an online learning algorithm to guarantee an upper bound in the difference from the optimal performance. We show the effectiveness of our overlay routing through simulation analysis for various network topologies.

E-mail sender authentication is a promising way of verifying the sources of e-mail messages. Since today's primary e-mail sender authentication mechanisms are designed as fully decentralized architecture, it is crucial for e-mail operators to know how other organizations are using and misusing them. This paper addresses the question "How is the DNS Sender Policy Framework (SPF), which is the most popular e-mail sender authentication mechanism, used and misused in the wild?" To the best of our knowledge, this is the first extensive study addressing the fundamental question. This work targets both legitimate and spamming domain names and correlates them with multiple data sets, including the e-mail delivery logs collected from medium-scale enterprise networks and various IP reputation lists. We first present the adoption and usage of DNS SPF from both global and local viewpoints. Next, we present empirically why and how spammers leverage the SPF mechanism in an attempt to pass a simple SPF authentication test. We also present that non-negligible volume of legitimate messages originating from legitimate senders will be rejected or marked as potential spam with the SPF policy set by owners of legitimate domains. Our findings will help provide (1) e-mail operators with useful insights for setting adequate sender or receiver policies and (2) researchers with the detailed measurement data for understanding the feasibility, fundamental limitations, and potential extensions to e-mail sender authentication mechanisms. Copyright © 2011 ACM.

In this paper, we quantitatively evaluate how temporal granularity in traffic monitoring (monitoring interval) affects the detectability of anomalous traffic. We build equations to calculate False Negative Ratio (FNR) with given sampling rate, statistics of normal traffic and volume of anomaly to be detected. With those equations, we can provide answers to the questions that arise in actual network operators, and had not been answered yet, such as which monitoring granularity is appropriate to find the given volume of anomaly. We also evaluate how the equations well estimate the FNR by using the actual traffic data.

The transmission bandwidth consumed by delivering rich content, such as movie files, is enormous, so it is urgent for ISPs to design an efficient delivery system minimizing the amount of network resources consumed. To serve users rich content economically and efficiently, an ISP itself should provide servers with huge storage capacities at a limited number of locations within its network. Therefore, we have investigated the content deployment method and the content delivery process that are desirable for this ISP-operated content delivery network (CDN). We have also proposed an optimum cache server allocation method for an ISP-operated CDN. In this paper, we investigate the properties of the topological locations of nodes at which cache placement is effective using 31 network topologies of actual ISPs. We also classify the 31 networks into two types and evaluate the optimum cache count in each network type. ©2010 IEEE.

Traffic caused by P2P services dominates a large part of traffic on the Internet and imposes significant loads on the Internet, so reducing P2P traffic within networks is an important issue for ISPs. In particular, a huge amount of traffic is transferred within backbone networks
therefore reducing P2P traffic is important for transit ISPs to improve the efficiency of network resource usage and reduce network capital cost. To reduce P2P traffic, it is effective for ISPs to implement cache devices at some router ports and reduce the hop length of P2P flows by delivering the required content from caches. However, the design problem of cache locations and capacities has not been well investigated, although the effect of caches strongly depends on the cache locations and capacities. We propose an optimum design method of cache capacity and location for minimizing the total amount of P2P traffic based on dynamic programming, assuming that transit ISPs provide caches at transit links to access ISP networks. We apply the proposed design method to 31 actual ISP backbone networks. ©2010 IEEE.

This work attempts to characterize network traffic flows originating from large-scale video sharing services such as YouTube. The key technical contributions of this paper are twofold. We first present a simple and effective methodology that identifies traffic flows originating from video hosting servers. The key idea behind our approach is to leverage the addressing/naming conventions used in large-scale server farms. Next, using the identified video flows, we investigate the characteristics of network traffic flows of video sharing services from a network service provider view. Our study reveals the intrinsic characteristics of the flow size distributions of video sharing services. The origin of the intrinsic characteristics is rooted on the differentiated service provided for free and premium membership of the video sharing services. We also investigate temporal characteristics of video traffic flows.

A Honeypot is a system that aims to detect and analyze malicious attacks attempted on a network in an interactive manner. Because the primary objective of a honeypot is to detect enemies without being known to them, it is important to hide its existence. However, as several studies have reported, exploiting the unique characteristics of hosts working on a consecutive IP addresses range easily reveals the existence of honeypots. In fact, there exist some anti-honeypot tools that intelligently probe IP address space to locate Internet security sensors including honeypots. In order to tackle this problem, we propose a system called DarkPots, that consists of a large number of virtualized honeypots using unused and nonconsecutive IP addresses in a production network. DarkPots enables us to deploy a large number of honeypots within an active IP space used for a production network
thus detection is difficult using existing probing techniques. In addition, by virtually classifying the unused IP addresses into several groups, DarkPots enables us to perform several monitoring schemes simultaneously. This function is meaningful because we can adopt more than one monitoring schemes and compare their results in an operating network. We design and implement a prototype of DarkPots and empirically evaluate its effectiveness and feasibility by concurrently performing three independent monitoring schemes in a high-speed campus network. The system successfully emulated 7,680 of virtualized honeypots on a backbone link that carries 500 Mbps - 1 Gbps of traffic without affecting legitimate traffic. Our key findings suggest: (1) active and interactive monitoring schemes provide more in-depth insights of malicious attacks, compared to passive monitoring approach in a quantitative way, and (2) randomly distributed allocation of IP addresses has an advantage over the concentrated allocation in that it can collect more information from malwares. These features are crucial in monitoring the security threats. © 2010 IEEE.

Video streaming with HDTV or UHDV quality will be provided and widely demanded in the future. However, the transmission bit-rate of high-quality video streaming is quite large, so generated traffic flows will cause link congestion. Therefore, when providing streaming services of rich content, it is important to flatten the link utilization, i.e., reduce the maximum link utilization. To achieve this goal, parallel video streaming in which ISPs use multiple servers to deliver rich content is effective. However, the effect of parallel video streaming depends on the network topology and link capacities. In this paper, we investigate the impact of network topologies on the effect of parallel video streaming using 23 actual commercial ISP networks, when optimally designing server locations and optimally selecting servers.

Traffic caused by P2P services dominates a large part of traffic on the Internet and imposes significant loads on the Internet, so reducing P2P traffic within networks is an important issue for ISPs. In particular, a huge amount of traffic is transferred within backbone networks; therefore reducing P2P traffic is important for transit ISPs to improve the efficiency of network resource usage and reduce network capital cost. To reduce P2P traffic, it is effective for ISPs to implement cache devices at some router ports and reduce the hop length of P2P flows by delivering the required content from caches. However, the design problem of cache locations and capacities has not been well investigated, although the effect of caches strongly depends on the cache locations and capacities. We propose an optimum design method of cache capacity and location for minimizing the total amount of P2P traffic based on dynamic programming, assuming that transit ISPs provide caches at transit links to access ISP networks. We apply the proposed design method to 31 actual ISP backbone networks.

We describe a method of adaptively controlling bandwidth allocation to flows for reducing the file transfer time of short flows without decreasing throughput of long-duration large flows. According to the rapid increase in Internet traffic volume, effective traffic engineering is increasingly required. Specifically, the traffic of long-duration large flows due to the use of peer-to-peer applications, for example, is a problem. Most conventional QoS controls allocate a fair-share bandwidth to each flow regardless of its duration. Thus, a long-duration large flow (such as a P2P flow) is allocated the same bandwidth as a short-duration flow (such as data from a Web page) in which the user is more sensitive to response time, i.e., file transfer time. As a result, long-duration large flows consume bandwidth over a long period and increase response times of short-duration flows, and conventional QoS methods do nothing to prevent this. In this paper, we therefore investigate a different approach, that is, a new form of bandwidth control that enables us to achieve better performance when handling short-duration flows while maintaining performance when handling long-duration flows. The basic idea is to tag packets of long-duration large flows according to traffic conditions and to give temporarily higher priority to nontagged packets during network congestion. We also show the effectiveness of our method through simulation. ©2009 IEEE.

The transmission bandwidth consumed by delivering rich content, such as movie files, is enormous, so it is urgent for ISPs to design an efficient delivery system minimizing the amount of network resources consumed. To efficiently deliver web content, a content delivery networks (CDNs) have been widely used. CDN providers collocate a huge number of servers within multiple ISPs without being informed the detailed network information, i.e., network topologies, from ISPs. Minimizing the amount of network resources consumed is difficult because a CDN provider selects a server for each request based on only rough estimates of response time. To serve users rich content economically and efficiently; an ISP itself should optimally provide servers with huge storage capacities at a limited number of locations within its network. In this paper, we investigate the content deployment method, the content delivery process, and the server allocation method that are desirable for this ISP-operated CDN. Moreover, we evaluate the effectiveness of the ISP-operated CDN using network topologies of actual ISPs.

We describe a method of adaptively controlling bandwidth allocation to flows for reducing the file transfer time of short flows without decreasing throughput of long-duration large flows. According to the rapid increase in Internet traffic volume, effective traffic engineering is increasingly required. Specifically, the traffic of long-duration large flows due to the use of peer-to-peer applications, for example, is a problem. Most conventional QoS controls allocate a fair-share bandwidth to each flow regardless of its duration. Thus, a long-duration large flow (such as a P2P flow) is allocated the same bandwidth as a short-duration flow (such as data from a Web page) in which the user is more sensitive to response time, i.e., file transfer time. As a result, long-duration large flows consume bandwidth over a long period and increase response times of short-duration flows, and conventional QoS methods do nothing to prevent this. In this paper, we therefore investigate a different approach, that is, a new form of bandwidth control that enables us to achieve better performance when handling short-duration flows while maintaining performance when handling long-duration flows. The basic idea is to tag packets of long-duration large flows according to traffic conditions and to give temporarily higher priority to nontagged packets during network congestion. We also show the effectiveness of our method through simulation.

As a promising solution to manage the huge workload of large-scale VoD services, managed peer-assisted CDN systems, such as P4P [25] has attracted attention. Although the approach works well in theory or in a controlled environment, to our best knowledge, there have been no general studies that address how actual peers can be incentivized in the wild Internet; thus, deployablity of the system with respect to incentives to users has been an open issue. With this background in mind, we propose a new business model that aims to make peer-assisted approaches more feasible. The key idea of the model is that users sell their idle resources back to ISPs. In other words, ISPs can leverage resources of cooperative users by giving them explicit incentives, e.g., virtual currency. We show the high-level framework of designing optimal incentive amount to users. We also analyze how incentives and other external factors affect the efficiency of the system through simulation. Finally, we discuss other fundamental factors that are essential for the deployability of managed peer-assisted model. We believe that the new business model and the insights obtained through this work are useful for assessing the practical design and deployment of managed peer-assisted CDNs.

インターネット上においてネットワークリソースの浪費や品質劣化を引き起こす異常トラヒックをトラヒック測定を通じて検知・制御する技術は,安心で快適な通信サービスを提供するために不可欠となっている.一方,ネットワークの大規模化・高速化に伴い,パケットサンプリングによる測定が注目されている.本稿では,サンプルパケット情報から異常トラヒックを検出するためのトラヒック測定分析手法について,関連研究動向の紹介を交えながら筆者らの研究内容について紹介する.また,各手法の実データ評価結果も示す.

We propose an algorithm for finding heavy hitters in terms of cardinality (the number of distinct items in a set) in massive traffic data using a small amount of memory. Examples of such cardinality heavy-hitters are hosts that send large numbers of flows, or hosts that communicate with large numbers of other hosts. Finding these hosts is crucial to the provision of good communication quality because they significantly affect the communications of other hosts via either malicious activities such as worm scans, spam distribution, or botnet control or normal activities such as being a member of a flash crowd or performing peer-to-peer (P2P) communication. To precisely determine the cardinality of a host we need tables of previously seen items for each host (e.g., flow tables for every host) and this may infeasible for a high-speed environment with a massive amount of traffic. In this paper, we use a cardinality estimation algorithm that does not require these tables but needs only a little information called the cardinality summary. This is made possible by relaxing the goal from exact counting to estimation of cardinality. In addition, we propose an algorithm that does not need to maintain the cardinality summary for each host, but only for partitioned addresses of a host. As a result, the required number of tables can be significantly decreased. We evaluated our algorithm using actual backbone traffic data to find the heavy-hitters in the number of flows and estimate the number of these flows. We found that while the accuracy degraded when estimating for hosts with few flows, the algorithm could accurately find the top-100 hosts in terms of the number of flows using a limited-sized memory. In addition, we found that the number of tables required to achieve a pre-defined accuracy increased logarithmically with respect to the total number of hosts, which indicates that our method is applicable for large traffic data for a very large number of hosts. We also introduce an application of our algorithm to anomaly detection. With actual traffic data, our method could successfully detect a sudden network scan.

Managing the performance at the flow level through traffic measurement is crucial for effective network management. With the rapid rise in link speeds, collecting all packets has become difficult, so packet sampling has been attracting attention as a scalable means of measuring flow statistics. In this paper, we firstly propose a method of estimating TCP flow rates of sampled flows through packet sampling, and then develop a method of detecting performance degradation at the TCP flow level from the estimated flow rates. In the method of estimating flow rates, we use sequence numbers of sampled packets, which make it possible to improve markedly the accuracy of estimating the flow rates of sampled flows. Using both an analytical model and measurement data, we show that this method gives accurate estimations. We also show that, by observing the estimated rates of sampled flows, we can detect TCP performance degradation. The method of detecting performance degradation is based on the following two findings: (i) sampled flows tend to have high flow-rates and (ii) when a link becomes congested, the performance of high-rate flows becomes degraded first. These characteristics indicate that sampled flows are sensitive to congestion, so we can detect performance degradation of flows that are sensitive to congestion by observing the rate of sampled flows. We also show the effectiveness of our method using measurement data.

Multicast is efficient transfer scheme for contents distribution to a large number of clients, but it is necessary to meet security issues. On the other hand, source authentication is one of the important techniques for protecting from malicious users that plot eavesdropping, masquerading and so on. Though many authentication schemes have been proposed, most of them are not suitable for practical multicast network. The design of scheme should meet robustness against unreliable network. In this paper, we expand the existent authentication scheme using erasure code, and propose the novel control mechanism that cooperates with data reconstruction process. In addition, we show the effectiveness of our proposal by computer simulation. ©2008 IEEE.

The authors have proposed a method of identifying superspreaders by flow sampling and a method of extracting worm-infected hosts from the identified superspreaders using a white list. However, the problem of how to optimally set parameters, phi, the measurement period length, m*, the identification threshold of the flow count m within phi, and H*, the identification probability for hosts with m = m*, remains unsolved. These three parameters seriously affect the worm-spreading property. In this paper, we propose a method of optimally designing these three parameters to satisfy the condition that the ratio of the number of active worm-infected hosts divided by the number of all the vulnerable hosts is bound by a given upper-limit during the time T required to develop a patch or an anti-worm vaccine.

We present a method of detecting network anomalies, such as DDoS (distributed denial of service) attacks and flash crowds, automatically in real time. We evaluated this method using measured traffic data and found that it successfully differentiated suspicious traffic. In this paper, we focus on cyclic traffic, which has a daily and/or weekly cycle, and show that the differentiation accuracy is improved by utilizing such a cyclic tendency in anomaly detection. Our method differentiates suspicious traffic that has different statistical characteristics from normal traffic. At the same time, it learns about cyclic large-volume traffic, such as traffic for network operations, and finally considers it to be legitimate.

With the rapid increase of link speed in recent years, packet sampling has become a very attractive and scalable means in collecting flow statistics; however, it also makes inferring original flow characteristics much more difficult. In this paper, we develop techniques and schemes to identify flows with a very large number of packets (also known as heavy-hitter flows) from sampled flow statistics. Our approach follows a two-stage strategy: We first parametrically estimate the original flow length distribution from sampled flows. We then identify heavy-hitter flows with Bayes' theorem, where the flow length distribution estimated at the first stage is used as an a priori distribution. Our approach is validated and evaluated with publicly available packet traces. We show that our approach provides a very flexible framework in striking an appropriate balance between false positives and false negatives when sampling frequency is given.

In this paper, we quantitatively evaluate how sampling decreases the detect-ability of anomalous traffic. We build equations to calculate the false positive ratio (FPR) and false negative ratio (FNR) for given values of the sampling rate, statistics of normal traffic, and volume of anomalies to be detected. We show that by changing the measurement granularity, we can detect anomalies even with a low sampling rate and give the equation to derive optimal granularity by using the relationship between the mean and variance of aggregated flows. With those equations, we can answer for the practical questions that arise in actual network operations; what sampling rate to set in order to find the given volume of anomaly, or, if the sampling is too high for actual operation, then what granularity is optimal to find the anomaly for a given lower limit of sampling rate.

Autonomous distributed systems comprising an overlay network on the Internet are proliferating as a new technology responsible for the next-generation Web. Due to the properties of such a large-scale system, it is difficult to measure the characteristics of the entire system without modifying the internal protocol of the applications. In this paper, by using a measurement method applicable to P2P applications and measured results obtained by applying this measurement method in part, a general-purpose method for estimating the size and behavior of the entire P2P network is proposed. Further, the present method is applied to a real P2P network and its effectiveness is presented by a specific example. (C) 2006 Wiley Periodicals, Inc.

We propose a tool for summarizing communication patterns between multiple hosts from traffic data with a small memory space, using a 2-D bitmap. Here, we focus on the communication pattern between pairs of source-destination hosts
these represents spatial communication patterns. By analyzing communication patterns using a bitmap, we can identify a super spreader, which is a host that sends packets to many destinations, or analyze the relationship between two source hosts. For the latter purpose, we present an application of the bitmap to calculate the similarity of hosts based on their peer-hosts patterns. © 2007 IEEE.

We investigate how to detect network anomalies using flow statistics obtained through packet sampling. First, we show that network anomalies generating a huge number of small flows, such as network scans or SYN flooding, become difficult to detect when we execute packet sampling. This is because such flows are more unlikely to be sampled than normal flows. As a solution to this problem, we then show that spatially partitioning the monitored traffic into groups and analyzing the traffic of individual groups can increase the detectability of such anomalies: We also show the effectiveness of the partitioning method using network measurement data. © 2007 IEEE.

Abusive traffic caused by worms is increasing severely in the Internet. In many cases, worm-infected hosts generate a huge number of flows of small size during a short time. To suppress the abusive traffic and prevent worms from spreading, identifying these "superspreaders" as soon as possible and coping with them, e.g., disconnecting them from the network, is important. This paper proposes a simple and adaptive method of identifying superspreaders by flow sampling. By satisfying the given memory size and the requirement for the processing time, the proposed method can adaptively optimize parameters according to changes in traffic patterns.

Traffic flow measurement is essential to implement QOS control in the Internet. Flow monitoring system collects and stores sampled How states in a flow table (FT) and the entries are renewed at every packet sampling. Entries in the FT are checked and removed when no packets are sampled within a predetermined timeout. We propose an efficient timeout checking mechanism based on checking a small number of entries selected randomly from the FT. Our proposed method aims to reduce the number of memory accesses dramatically and keep the memory size small. We evaluate our method and compare with the conventional method that checks all flow entries of the FT periodically. Our simulation and comparison results show that our method is able to reduce the number of memory access at a factor of 1000 with a small increase in memory size of approximately 10 percent.

We investigate the detection accuracy of network anomalies when we use flow statistics obtained through packet sampling. We have already shown, through a case study based on measurement data, that network anomalies generating a huge number of small flows, such as network scans or SYN flooding, become hard to detect when we perform packet sampling. In this paper, we first develop an analytical model that enables us to quantitatively evaluate the effect of packet sampling on the detection accuracy and then investigate why detection accuracy worsens when the packet sampling rate decreases. In addition, we show that, even with a low sampling rate, spatially partitioning the monitored traffic into groups makes it possible to increase the detection accuracy. We also develop a method of determining an appropriate number of partitioned groups and show its effectiveness.

A method of controlling the rate of long-duration large flows and its performance evaluation is described in this paper. Most conventional QoS controls allocate a fair-share bandwidth to each flow regardless of its duration. Thus, a long-duration large flow (such as a P2P flow) is allocated the same bandwidth as a short-duration flow (such as data from a Web page) in which the user is more sensitive to response time. As a result, long-duration flows will occupy the bandwidth over the long period and worsen response times of short-duration flows, and the conventional QoS methods do nothing to prevent this. We have, therefore, proposed a new form of QoS control that takes flow duration into account and assigns higher priority to the acceptance of shorter-duration flows. In this paper, we show through simulation that our method achieves high performance for short-duration flows without degrading the performance of long-duration flows. We also explain how to set parameters used in our method. Furthermore, we discuss the applicability of a packet-sampling technique to improve the method's scalability. © 2006 IEEE.

Unfairness among best-effort flows is a serious problem on the Internet. In particular, UDP flows or unresponsive flows that do not obey the TCP flow control mechanism can consume a large share of the available bandwidth. High-rate flows seriously affect other flows, so it is important to identify them and limit their throughput by selectively dropping their packets. As link transmission capacity increases and the number of active flows increases, however, capturing all packet information becomes more difficult. In this paper, we propose a novel method of identifying high-rate flows by using sampled packets. The proposed method simply identifies flows from which Y packets are sampled without timeout. The identification principle is very simple and the implementation is easy. We derive the identification probability for flows with arbitrary flow rates and obtain an identification curve that clearly demonstrates the accuracy of identification. The characteristics of this method are determined by three parameters: the identification threshold Y, the timeout coefficient K, and the sampling interval N. To match the experimental identification probability to the theoretical one and to simplify the identification mechanism, we should set K to the maximum allowable value. Although increasing Y improves the identification accuracy, both the required memory size and the processing power grow as Y increases. Numerical evaluation using an actual packet trace demonstrated that the proposed method achieves very high identification accuracy with a much simpler mechanism than that of previously proposed methods.

We propose a method to find N hosts that have the N highest cardinalities, where cardinality is the number of distinct items such as the number of flows, ports, or peer hosts. The method also estimates their cardinalities. While existing algorithms to find the top N frequent items can be directly applied to find N hosts that send the N largest numbers of packets through packet data stream, finding hosts that have the N highest cardinalities requires tables of previously seen items for each host to check whether an item of an arrival packet is new, which requires a lot of memory. Even if we use the existing cardinality estimation methods, we still need to have cardinality information about each host. In this paper, we use the property of cardinality estimation, in which the cardinality of intersections of multiple data sets can be estimated with cardinality information of each data set. Using the property, we propose an algorithm that does not need to maintain tables for each host, but only for partitioned addresses of a host and estimate the cardinality of a host as the intersection of cardinalities of partitioned addresses. We also propose a method to find top N hosts in cardinalities which is to be monitored to detect anomalous behavior in networks. We evaluate our algorithm through actual backbone traffic data. While the estimation accuracy of our scheme degrades for small cardinalities, as for the top 100 hosts, the accuracy of our algorithm with 4, 096 tables is almost the same as having tables of every hosts.

A method of controlling the rate of long-duration large flows and its performance evaluation is described in this paper. Most conventional QoS controls allocate a fair-share bandwidth to each flow regardless of its duration. Thus, a long-duration large flow (such as a P2P flow) is allocated the same bandwidth as a short-duration flow (such as data from a Web page) in which the user is more sensitive to response time. As a result, long-duration flows will occupy the bandwidth over the long period and worsen response times of short-duration flows, and the conventional QoS methods do nothing to prevent this. We have, therefore, proposed a new form of QoS control that takes flow duration into account and assigns higher priority to the acceptance of shorter-duration flows. In this paper, we show through simulation that our method achieves high performance for short-duration flows without degrading the performance of long-duration flows. We also explain how to set parameters used in our method. Furthermore, we discuss the applicability of a packet-sampling technique to improve the method&apos;s scalability.

A method of estimating TCP flow-rates of sampled flows through packet sampling is described in this paper. We use sequence numbers of sampled packets, which make it possible to improve markedly the accuracy of estimating the flow rates. Using an analytical model, we investigate how to set parameters such as packet sampling probability used in this method of estimation. As a remarkable result, we show that the estimation accuracy improves as the sampling probability decreases. Using measured data, we also show that this method gives accurate estimations. We also show that this estimation method enables us to detect performance degradation at the TCP flow level.

We propose a method of dimensioning and managing the bandwidth of a link on which flows with heterogeneous access-link bandwidths are aggregated. We use a processor-sharing queue model to develop a formula approximating the mean TCP file-transfer time of flows on an access link in such a situation. This only requires the bandwidth of the access link carrying the flows on which. we are focusing and the bandwidth and utilization of the aggregation link, each of which is easy to set or measure. We then extend the approximation to handle various factors affecting actual TCP behavior, such as the round-trip time and restrictions other than the access-link bandwidth and the congestion of the aggregation link. To do this, we define the virtual access-link bandwidth as the file-transfer speed of a flow when the utilization of the aggregation link is negligibly small. We apply the virtual access-link bandwidth in our approximation to estimate the TCP performance of a flow with increasing utilization of the aggregation link. This method of estimation is used as the basis for a method of dimensioning the bandwidth of a link such that the TCP performance is maintained, and for a method of managing the bandwidth by comparing the measured link utilization with an estimated threshold indicating degradation of the TCP performance. The accuracy of the estimates produced by our method is estimated through both computer simulation and actual measurement.

Peer-to-peer (P2P) applications have been expanding rapidly in recent years, and the contribution of P2P to present Internet traffic is close to that of the World Wide Web (WWW). In this study, the flow of WWW and P2P traffic is analyzed by network measurement. The characteristics of WWW and P2P are examined, especially in terms of the flow arrival interval, flow duration, flow size, and flow rate. Based on the results of the analysis, the effect of a P2P flow increase on the overall traffic characteristics is investigated. The results of this study will be utilized in network design, proposals for control procedures, and traffic modeling, considering the traffic characteristics of particular applications. © 2005 Wiley Periodicals, Inc.

Managing the performance at the flow level through traffic measurement is crucial for effective network management. On the other hand, with the rapid rise in link speeds, collecting all packets has become difficult, so packet sampling has been attracting attention as a scalable means of measuring flow statistics. We have therefore established a method of detecting performance degradation at the TCP flow level from sampled flow behaviors. The proposed method is based on the following two flow characteristics: (i) sampled flows tend to have high flowrates and (ii) when a link becomes congested, the performance of high-rate flows becomes degraded first. These characteristics indicate that sampled flows are sensitive to congestion, so we can detect performance degradation of flows that are sensitive to congestion by observing the rate of sampled flows. We also show the effectiveness of our method using measured data.

Analysing and modeling of traffic play a vital role in designing and controlling of networks effectively. To construct a practical traffic model that can be used for various networks, it is necessary to characterize aggregated traffic and user traffic. This paper investigates these characteristics and their relationship. Our analyses are based on a huge number of packet traces from five different networks on the Internet. We found that: (1) marginal distributions of aggregated traffic fluctuations follow positively skewed (non-Gaussian) distributions, which leads to the existence of "spikes", where spikes correspond to an extremely large value of momentary throughput, (2) the amount of user traffic in a unit of time has a wide range of variability, and (3) flows within spikes are more likely to be "elephant flows", where an elephant flow is an IP flow with a high volume of traffic. These findings are useful in constructing a practical and realistic Internet traffic model.

We propose a method of dimensioning and managing the bandwidth of a link on which flows arriving on access links that have heterogeneous bandwidths are aggregated. We start by developing a formula that approximates the mean TCP file-transfer time of a flow in such a situation. This only requires the bandwidth of the access link carrying the flow and the bandwidth and utilization of the aggregation link, each of which is easy to set or measure. We then extend the approximation to handle various factors that affect actual TCP behavior, such as round-trip time and restrictions other than the access-link bandwidth and congestion of the aggregation link in the end-to-end path of the flow. To do this, we define the virtual access-link bandwidth as the file-transfer speed of the flow when utilization of the aggregation link is negligibly small. We apply the virtual access-link bandwidth in the approximation to estimate the TCP performance of the flow with increasing utilization of the aggregation link. We use this method of estimation as the basis for a method of dimensioning the bandwidth of the link such that TCP performance is maintained and a method of managing bandwidth by comparing measured link utilization with the estimated threshold that indicates degradation of TCP performance. We also use simulation to analyze the accuracy of the estimates produced by our method.

Analysing and modeling of traffic play a vital role in designing and controlling of networks effectively. To construct a practical traffic model that can be used for various networks, it is necessary to characterize aggregated traffic and user traffic, This paper investigates these characteristics and their relationship. Our analyses are based on a huge number of packet traces from five different networks on the Internet. We found that: (1) marginal distributions of aggregated traffic fluctuations follow positively skewed (non-Gaussian) distributions, which leads to the existence of "spikes", where spikes correspond to an extremely large value of momentary throughput, (2) the amount of user traffic in a unit of time has a wide range of variability, and (3) flows within spikes are more likely to be "elephant flows", where an elephant flow is an IP flow with a high volume of traffic. These findings are useful in constructing a practical and realistic Internet traffic model.