How can we identify live Command & Control (C2) servers for a given IoT malware binary? An effective solution to this problem constitutes a significant capability towards detecting and containing botnets. This task is not trivial because C2 servers are short-lived, and they use sophisticated and proprietary communication protocols. We propose C2Miner, a novel approach to trick IoT malware binaries into revealing their currently live C2 servers. Our approach weaponizes old disposable IoT malware binaries and uses them to probe active servers. We provide novel solutions to overcome the following challenges: (a) disambiguating the C2-bound traffic generated by the malware and (b) determining if a target IP:port is indeed a C2 server as opposed to a benign server.

How can we find other repositories on GitHub that are functionally similar to a specific repository? While GitHub offers keyword-based search functionality, there is a lack of a tool that can perform query by example to search and compare functionally similar repositories. To address this challenge, we present MetaSim: a search engine that finds similar GitHub repositories based on repository metadata features. MetaSim employs a customized technique to represent repository metadata in the embedding space for efficient indexing and searching. We construct a curated dataset of 267.6K public GitHub repositories to support our search engine. We evaluate our tool through a manual assessment on a set of 202 query by example repository and their corresponding matching pairs. Experiment results demonstrate that Readme alone can achieve high similarity precision (90.1%), which we define later. In contrast, the combined usage of Description, Topics, and Readme yields the best overall performance with similarity precision of 97.8%. To foster both research and practical applications, we open source our research artifacts through the MetaSim platform at https://metasim-app.github.io. The demonstration video of MetaSim is available at https://youtu.be/HnFnN3JclQw.

How can we model arguments and their dynamics in online forum discussions? The meteoric rise of online forums presents researchers across different disciplines with an unprecedented opportunity: we have access to texts containing discourse between groups of users generated in a voluntary and organic fashion. Most prior work so far has focused on classifying individual monological comments as either argumentative or not argumentative. However, few efforts quantify and describe the dialogical processes between users found in online forum discourse: the structure and content of interpersonal argumentation. Modeling dialogical discourse requires the ability to identify the presence of arguments, group them into clusters, and summarize the content and nature of clusters of arguments within a discussion thread in the forum. In this work, we develop ArguSense, a comprehensive and systematic framework for understanding arguments and debate in online forums. Our framework consists of methods for, among other things: (a) detecting argument topics in an unsupervised manner; (b) describing the structure of arguments within threads with powerful visualizations; and (c) quantifying the content and diversity of threads using argument similarity and clustering algorithms. We showcase our approach by analyzing the discussions of four communities on the Reddit platform over a span of 21 months. Specifically, we analyze the structure and content of threads related to GMOs in forums related to agriculture or farming to demonstrate the value of our framework.

How can we identify malicious hackers participating in different online platforms using their usernames only? Disambiguating users across online platforms (e.g. security forums, GitHub, YouTube) is an essential capability for tracking malicious hackers. Although a hacker could pick arbitrary names on different platforms, they often use the same or similar usernames as this helps them establish an online "brand". We propose GeekMAN, a systematic human-inspired approach to identify similar usernames across online platforms focusing on technogeek platforms. The key novelty consists of the development and integration of three capabilities: (a) decomposing usernames into meaningful chunks, (b) de-obfuscating technical and slang conventions, and (c) considering all the different outcomes of the two previous functions exhaustively when calculating the similarity. We conduct a study using 1.2M usernames from five security forums. Our method outperforms previous methods with a Precision of 81--86%. We see our approach as a fundamental research capability, which we made publicly available on GitHub.

How can we leverage the URLs posted on online forums to connect forum users with their profiles on other platforms? Most previous studies primarily focus on analyzing textual content and user metadata, paying limited attention to URLs. In this paper, we propose RURLMAN, a modular ensemble of methods for leveraging user-posted URLs to connect online forum users with their cross-platform profiles. Our approach has two key features: (a) we focus on user-posted URLs as the key source of information, and (b) we utilize a modular stacked ensemble integrating multiple methods, including string-matching and two ChatGPT capabilities. We show that RURLMAN effectively combines the strengths of its component methods, outperforming each individual method with an F1 score of 92.6%. We apply RURLMAN in a case study comprising 1.3M URLs posted by 250K forum users across six online security forums and consider URLs to Twitter, Facebook, GitHub, and YouTube. First, we match 30% of the users who shared URLs to these platforms with the corresponding owners of the linked social media profiles. Second, we connect 8% of these users to profiles on multiple platforms. Finally, we identify and analyze "groups" of users based on their posted URLs. To facilitate further research, we will share access to RURLMAN and its datasets with the research community.

How can we expand an initial set of keywords with a target domain in mind? A possible application is to use the expanded set of words to search for specific information within the domain of interest. Here, we focus on online forums and specifically security forums. We propose IKEA, an iterative embedding-based approach to expand a set of keywords with a domain in mind. The novelty of our approach is three-fold: (a) we use two similarity expansions in the word-word and post-post spaces, (b) we use an iterative approach in each of these expansions, and (c) we provide a flexible ranking of the identified words to meet the user needs. We evaluate our method with data from three security forums that span five years of activity and the widely-used Fire benchmark. IKEA outperforms previous solutions by identifying more relevant keywords: it exhibits more than 0.82 MAP and 0.85 NDCG in a wide range of initial keyword sets. We see our approach as an essential building block in developing methods for harnessing the wealth of information available in online forums.

How can we comprehensively understand the main concerns and beliefs of the GMO debate in online forums? Genetically Modified Organisms (GMOs) have historically been a hotly debated topic, both within and outside of the agriculture industry. Understanding the complexity of these beliefs can lend policy makers the knowledge necessary to counteract misinformation. In this paper we develop Forumlyze, a systematic framework to understand user beliefs in online discourse surrounding an issue. As a case study, we focus on data collected from Reddit between 2019–2020 from four sub-forums: farming, agriculture, horticulture, and vegetable gardening. In our approach we (a) illustrate the fundamental and temporal characteristics of the issue (b) extract and characterize sentiments surrounding the issue (c) uncover the dominate concepts prevalent in this discussion and the context surrounding these concepts. The comprehensive nature of this analysis led to the following results. (1) The dominant concepts surrounding GMOs are Climate Change, Monsanto and Soil Science. (2) The sentiment of discourse around GMOs and its related concepts indicates a polarized affective system. (3) Evidence that real-world events impact online forum communities' sentiment surrounding GMOs-related concepts.

How can we quantify the influence among repos-itories in online archives like GitHub? Determining repository influence is an essential building block for understanding the dynamics of GitHub-like software archives. The key challenge is to define the appropriate representation model of influence that captures the nuances of the concept and considers its diverse manifestations. We propose PIMan, a systematic approach to quantify the influence among the repositories in a software archive by focusing on the social level interactions. As our key novelty, we introduce the concept of Plausible Influence which considers three types of information: (a) repository level interactions, (b) author level interactions, and (c) temporal considerations. We evaluate and apply our method using 2089 malware repositories from GitHub spanning approximately 12 years. First, we show how our approach provides a powerful and flexible way to generate a plausible influence graph whose density is determined by the Plausible Influence Threshold (PIT), which is modifiable to meet the needs of a study. Second, we find that there is a significant collaboration and influence among the repositories in our dataset. We identify 28 connected components in the plausible influence graph (PIT = 0.25) with 7% of the components containing at least 15 repositories. Furthermore, we find 19 repositories that influenced at least 10 other repositories directly and spawned at least two “families” of repositories. In addition, the results show that our influence metrics capture the manifold aspects of the interactions that are not captured by the typical repository popularity metrics (e.g. number of stars). Overall, our work is a fundamental building block for identifying the influence and lineage of the repositories in online software platforms.

Online forums contain a substantial amount of data, but very few studies have focused on mining the URLs posted by users. How can we fully leverage these posted URLs to extract as much information as possible about forum users? We perform a systematic study for extracting as much information as possible about forum users via their URL posting behavior. Within this study we develop a series of tools to analyze the data. Given a forum, we extract the following information: (a) basic statistics and a profile of the forum, (b) a profile for each user based on their referral to accounts in other platforms, (c) identification of communities within the forum, and (d) detection of malicious behavior. Most prior works focus on analyzing the text found in user posts rather than on URLs themselves, as we do here. In our study, we analyze three online security forums and find interesting results: (a) we identify 7% of the users posting social media links on other platforms, (b) we detect 148 groups of users that engage in communities on external social media platforms, (c) we expose 139 malicious users that collectively posted 328 malicious URLs. Additionally, we identify 17 groups with membership spanning across multiple forums, and discover numerous other groups that engage in coordinated malicious behavior. Our work is a significant step towards an all-encompassing system for profiling forum users at large.

Where are the IoT C2 servers located? What vulnerabilities does IoT malware try to exploit? What DDoS attacks are launched in practice? In this work, we conduct a large scale study to answer these questions. Specifically, we collect and dynamically analyze 1447 malware binaries on the day that they become publicly known between March 2021 and March 2022 from VirusTotal and MalwareBazaar. By doing this, we are able to observe and profile their behavior at the network level including: (a) C2 communication, (b) proliferation, and (c) issued DDoS attacks. Our comprehensive study provides the following key observations. First, we quantify the elusive behavior of C2 servers: 91% of the time a server does not respond to a second probe four hours after a successful probe. In addition, we find that 15% of the live servers that we find are not known by threat intelligence feeds available on VirusTotal. Second, we find that the IoT malware relies on fairly old vulnerabilities in its proliferation. Our binaries attempt to exploit 12 different vulnerabilities with 9 of them more than 4 years old, while the most recent one was 5 months old. Third, we observe the launch of 42 DDoS attacks that span 8 types of attacks, with two types of attacks targeting gaming servers. The promising results indicate the significant value of using a dynamic analysis approach that includes active measurements and probing towards detecting and containing IoT botnets.

How can we detect and analyze hyperlink-driven misbehavior in online forums? Online forums contain enormous amounts of user-generated content, with threads and comments frequently supplemented by hyperlinks. These hyperlinks are often posted with malicious intention and we refer to this as 'hyperlink-driven misbehavior'. We present LinkMan, a systematic suite of capabilities, to detect and analyze hyperlink-driven misbehavior in online forums. We take a unique perspective focusing on hyperlink sharing practices of the users to spot misbehavior. LinkMan can categorize these hyperlinks as: a) phishing, b) spamming, and b) promoting malicious products. Our approach consists of three high-level phases: (a) extracting hyperlinks from the textual data, (b) identifying misbehaving hyperlinks, and (c) modeling the behavioral patterns of hyperlink sharing, where we identify key hyperlinks and analyze the collaboration dynamics of hyperlink sharing. In addition, we implement our approach as a powerful and easy-to-use open platform for practitioners. We apply LinkMan to spot misbehavior from three online security forums, where we expect the users to be more security-aware. We show that our approach works very well in terms of retrieving and classifying hyperlinks compared to previous solutions. Furthermore, we find non-trivial and often systematic misbehavior: (a) we find a total of 637 misbehaving hyperlinks, and (b) we identify 30 colluding groups of users in terms of promoting hyperlinks. Our work is a significant step towards mining online forums and detecting misbehaving users comprehensively.

How are the sentiment and stance of online users affected by real-world events? Previous studies have ignored the role of events in co-determining sentiment and stance and hence have failed to understand the relationship between these two important aspects of public opinion. In this paper, we develop SentiStance, a systematic framework to understand the intertwined change of sentiment and stance due to real-world events in online discussions. In our approach: (a) we customize state-of-the-art NLP techniques to overcome domain-specific constraints, and (b) we provide an efficient way to quantify the change of sentiment and stance in tandem. As a case study, we focus on the 2020 United States Election events and we analyze 7.5 million posts from 4chan, Reddit, and Parler over a span of three months from November 2020 to January 2021. We showcase our framework by describing the effect that the Jan 6 insurrection had on concepts "Pence" and "Trump." Parler users turn significantly against Pence with (33.1% increase in Against stance and Negative sentiment), while Reddit users' opinion improves (with a drop of 7.1% in the same combination of sentiment and stance). By contrast, the effect of the same event on the concept "Trump" shows no statistically significant change. In addition, our results suggest that conditioning on significant events strengthens the correlation between sentiment and stance, which provides a new perspective on the debate around the correlation between sentiment and stance. Overall, we see our work as a fundamental building block towards a data-driven understanding of the interplay of preferences and emotions of online forum users towards a concept.

How can we identify similar repositories and clusters among a large online archive, such as GitHub? Determining repository similarity is an essential building block in studying the dynamics and the evolution of such software ecosystems. The key challenge is to determine the right representation for the diverse repository features in a way that: (a) it captures all aspects of the available information, and (b) it is readily usable by ML algorithms. We propose Repo2Vec, a comprehensive embedding approach to represent a repository as a distributed vector by combining features from three types of information sources. As our key novelty, we consider three types of information: (a) metadata, (b) the structure of the repository, and (c) the source code. We also introduce a series of embedding approaches to represent and combine these information types into a single embedding. We evaluate our method with two real datasets from GitHub for a combined 1013 repositories. First, we show that our method outperforms previous methods in terms of precision (93 % vs 78 %), with nearly twice as many Strongly Similar repositories and 30 % fewer False Positives. Second, we show how Repo2Vec provides a solid basis for: (a) distinguishing between malware and benign repositories, and (b) identifying a meaningful hierarchical clustering. For example, we achieve 98 % precision, and 96 % recall in distinguishing malware and benign repositories. Overall, our work is a fundamental building block for enabling many repository analysis functions such as repository categorization by target platform or intention, detecting code-reuse and clones, and identifying lineage and evolution.

Malware infects thousands of systems globally each day causing millions of dollars in damages. Which disassembler should a malware analyst choose in order to get the most accurate disassembly and be able to detect, analyze and defuse malware quickly? There is no clear answer to this question: (a) the performance of disassemblers varies across configurations, and (b) most prior work on disassemblers focuses on benign software and the x86 CPU architecture. In this work, we take a different approach and ask: why not use all the disassemblers instead of picking one? We present DisCo, a novel and effective approach to harness the collective capability of a group of disassemblers combining their output into an ensemble consensus. We develop and evaluate our approach using 1760 IoT malware binaries compiled with different compilers and compiler options for the ARM and MIPS architectures. First, we show that DisCo can combine the collective wisdom of disassemblers effectively. For example, our approach outperforms the best contributing disassembler by as much as 17.8% in the F1 score for function start identification for MIPS binaries compiled using GCC with O3 option. Second, the collective wisdom of the disassemblers can be brought back to improve each disassembler. As a proof of concept, we show that byte-level signatures identified by DisCo can improve the performance of Ghidra by as much as 13.6% in terms of the F1 score. Third, we quantify the effect of the architecture, the compiler, and the compiler options on the performance of disassemblers. Finally, the systematic evaluation within our approach led to a bug discovery in Ghidra v9.1, which was acknowledged by the Ghidra team.

How can we get a security forum to “tell” us its activities and events of interest? We take a unique angle: we want to identify these activities without any a priori knowledge, which is a key difference compared to most of the previous problem formulations. Despite some recent efforts, mining security forums to extract useful information has received relatively little attention, while most of them are usually searching for specific information. We propose TenFor, an unsupervised tensor-based approach, to systematically identify important events in a three-dimensional space: (a) user, (b) thread, and (c) time. Our method consists of three high-level steps: (a) a tensor-based clustering across the three dimensions, (b) an extensive cluster profiling that uses both content and behavioral features, and (c) a deeper investigation, where we identify key users and threads within the events of interest. In addition, we implement our approach as a powerful and easy-to-use platform for practitioners. In our evaluation, we find that 83% of our clusters capture meaningful events and we find more meaningful clusters compared to previous approaches. Our approach and our platform constitute an important step towards detecting activities of interest from a forum in an unsupervised learning fashion in practice.

Online forums have been shown to contain a wealth of useful information. With a few notable exceptions, such forums have not received much attention from the research community, unlike other online social media. Our goal here is to conduct an in-depth thread-centric analysis of online forums, focusing on security forums. We propose, RThread, a comprehensive unsupervised clustering approach with a powerful visualization component, which we provide as a publicly-accessible web-based tool. Our approach leverages 92 thread features that span three groups: (a) temporal, (b) behavioral, and (c) content related. We analyze data from 8 security forums with 400k posts over a span of 8 years. First, we find that many thread-centric properties follow a log-normal distribution, which is persistent across several forums and over time. Second, we show how our approach can identify clusters of threads with similar behavior, while our visualization component provides an easy way to spot the differences between these clusters. Finally, we show how our approach can spot surprising behaviors, including a cluster, whose threads are used for Search Engine Optimization. We see our approach and our publicly available platform as a building block towards understanding forum activity and extracting interesting information in an unsupervised way.

How can we conduct dynamic analysis on IoT malware efficiently? A key challenge is that such malware target a plethora of different devices, which makes identifying the target device non-trivial. This problem does not appear nearly as much in PC and smartphones malware, where the devices are more uniform. The contribution of our work is two fold: (a) we develop RIoTMAN, a comprehensive emulation and dynamic analysis approach, and (b) we study the network behavior of 3024 IoT malware systematically. The power of our approach lies in two key novelties: (a) Iterative Adaptation, and (b) Automated Engagement. First, we employ an intelligent iterative process that incrementally "builds" the configuration of the target device. Second, our platform automates the interaction with the malware even during the C&C server communication phase. In our experiments, we first show that we achieve an activation rate of 93% for our binaries, including 173 binaries, which Virustotal fails to identify as malicious. Second, we impersonate the C&C server for 79% of the malware binaries successfully: we make the malware initiate DDoS attacks, or enter its proliferation phase. Finally, we observe several interesting malware techniques, including unusual communication behaviors. Our goal is to release our platform as an open-source tool to accelerate the efforts for understanding IoT malware in depth and at scale.

The proliferation of smartphones has lead researchers towards using them as an observational tool in psychological science. However, there is little effort towards protecting user privacy in these analyses. The overarching question of our work is: Given a set of sensitive user features, what is the minimum amount of information required to group similar users? Our contributions are two fold: we introduce privacy surfaces that combine sensitive user data at different levels of temporal granularity. Second, we introduce MIMiS, an unsupervised privacy-aware framework that clusters users as homogeneous groups with respect to their temporal signature. In addition, we explore the trade-off between intrusiveness and prediction accuracy. We extensively evaluate MIMiS on real data across a variety of privacy surfaces. MIMiS identified groups that are highly homogeneous w.r.t. user mental health scores and their academic performance.

In-memory injection attacks are extremely challenging to reverse engineer because they operate stealthily without leaving artifacts in the system or in any easily observable events from outside of a virtual machine. Because these attacks perform their actions in memory only, current malware analysis solutions cannot expose their behavior. This paper introduces FAROS^1 a reverse engineering tool for Windows malware analysis based on dynamic information flow tracking (DIFT), which can flag stealthy in-memory-only malware injection attacks by leveraging the synergy of: (i) whole-system taint analysis; (ii) per security policy-based handling of the challenge of indirect flows via the application of tags of different types, and (iii) the use of tags with fine-grained provenance information. We evaluated FAROS with six advanced in-memory-injecting malware and it flagged the attacks for all samples. We also analyzed FAROS' false positive rate with 90 non-injecting malware samples and 14 benign software from various categories. FAROS presented a very low false positive rate of 2%, which shows its potential towards practical solutions against advanced in-memory-only anti-reverse-engineering attacks.

Given the set of social interactions of a user, how can we detect changes in interaction patterns over time? While most previous work has focused on studying network-wide properties and spotting outlier users, the dynamics of individual user interactions remain largely unexplored. This work sets out to explore those dynamics in a way that is minimally invasive to privacy, thus, avoids to rely on the textual content of user posts---except for validation. Our contributions are two-fold. First, in contrast to previous studies, we challenge the use of a fixed interval of observation. We introduce and empirically validate the "Temporal Asymmetry Hypothesis", which states that appropriate observation intervals should vary both among users and over time for the same user. We validate this hypothesis using eight different datasets, including email, messaging, and social networks data. Second, we propose iNET, a comprehensive analytic and visualization framework which provides personalized insights into user behavior and operates in a streaming fashion. iNET learns personalized baseline behaviors of users and uses them to identify events that signify changes in user behavior. We evaluate the effectiveness of iNET by analyzing more than half a million interactions from Facebook users. Labeling of the identified changes in user behavior showed that iNET is able to capture a wide spectrum of exogenous and endogenous events, while the baselines are less diverse in nature and capture only 66% of that spectrum. Furthermore, iNET exhibited the highest precision (95%) compared to all competing approaches.

How much useful information can we extract from security forums? Many security initiatives and commercial entities are harnessing the readily public information, but they seem to focus on structured sources of information. Our goal here is to extract information from hacker forums, whose information is provided in ad hoc and unstructured ways. Here, we focus on the problem of identifying malicious IPs addresses, when these are being reported in the forums. We develop a method to automate the identification of malicious IPs with the design goal of being independent of external sources. A key novelty is that we use a matrix decomposition method to extract latent features of the behavioral information of the users, which we combine with textual information from the related posts. As key design feature, our technique can be applied to different language forums since it relies on a simple NLP solution in combination with behavioral features. In particular, our solution only needs a small number of keywords in the new language plus the user's behavior captured by specific features. We also develop a tool to automate the data collection from security forums. We collect approximately 600K posts from 3 different forums. Our method exhibits high classification accuracy, while the precision of identifying malicious IP in post is greater than 88% in all three sites. Furthermore, by applying our method, we find up to 3 times more potentially malicious IPs than compared to the reference blacklist VirusTotal. As the cyber-wars are becoming more intense, having early accesses to useful information becomes more imperative to remove the hackers first-move advantage, and our work is a solid step towards this direction.

Commenting platforms, such as Disqus, have emerged as a major online communication platform with millions of users and posts. Their popularity has also attracted parasitic and malicious behaviors, such as trolling and spamming. There has been relatively little research on modeling and safeguarding these platforms. As our key contribution, we develop a systematic approach to detect malicious users on commenting platforms. Our work provides two key novelties: (a) we provide a fine-grained classification of malicious behaviors, and (b) we use a comprehensive set of 73 features that span four dimensions of information. We use 7 million comments during a 9 month period, and we show that our classification methods can distinguish between benign, and malicious roles (spammers, trollers, and fanatics) with a 0.904 AUC. Our work is a solid step towards ensuring that commenting platforms are a safe and pleasant medium for the exchange of ideas.

We propose a new security paradigm that makes cross-layer personalization a premier component in the design of security solutions for computer infrastructure and situational awareness. This paradigm is based on the observation that computer systems have a personalized usage profile that depends on the user and his activities. Further, it spans the various layers of abstraction that make up a computer system, as if the user embedded his own DNA into the computer system. To realize such a paradigm, we discuss the design of a comprehensive and cross-layer profiling approach, which can be adopted to boost the effectiveness of various security solutions, e.g., malware detection, insider attacker prevention and continuous authentication. The current state-of-the-art in computer infrastructure defense solutions focuses on one layer of operation with deployments coming in a "one size fits all" format, without taking into account the unique way people use their computers. The key novelty of our proposal is the cross-layer personalization, where we derive the distinguishable behaviors from the intelligence of three layers of abstraction. First, we combine intelligence from: a) the user layer, (e.g., mouse click patterns); b) the operating system layer; c) the network layer. Second, we develop cross-layer personalized profiles for system usage. We will limit our scope to companies and organizations, where computers are used in a more routine and one-on-one style, before we expand our research to personally owned computers. Our preliminary results show that just the time accesses in user web logs are already sufficient to distinguish users from each other,with users of the same demographics showing similarities in their profiles. Our goal is to challenge today's paradigm for anomaly detection that seems to follow a monoculture and treat each layer in isolation. We also discuss deployment, performance overhead, and privacy issues raised by our paradigm.

Large graphs are prevalent in many applications and enable a variety of information dissemination processes, e.g., meme, virus, and influence propagation. How can we optimize the underlying graph structure to affect the outcome of such dissemination processes in a desired way (e.g., stop a virus propagation, facilitate the propagation of a piece of good idea, etc)? Existing research suggests that the leading eigenvalue of the underlying graph is the key metric in determining the so-called epidemic threshold for a variety of dissemination models. In this paper, we study the problem of how to optimally place a set of edges (e.g., edge deletion and edge addition) to optimize the leading eigenvalue of the underlying graph, so that we can guide the dissemination process in a desired way. We propose effective, scalable algorithms for edge deletion and edge addition, respectively. In addition, we reveal the intrinsic relationship between edge deletion and node deletion problems. Experimental results validate the effectiveness and efficiency of the proposed algorithms.

With 20 million installs a day , third-party apps are a major reason for the popularity and addictiveness of Facebook. Unfortunately, hackers have realized the potential of using apps for spreading malware and spam. The problem is already significant, as we find that at least 13% of apps in our dataset are malicious. So far, the research community has focused on detecting malicious posts and campaigns. In this paper, we ask the question: Given a Facebook application, can we determine if it is malicious? Our key contribution is in developing FRAppE-Facebook's Rigorous Application Evaluator-arguably the first tool focused on detecting malicious apps on Facebook. To develop FRAppE, we use information gathered by observing the posting behavior of 111K Facebook apps seen across 2.2 million users on Facebook. First, we identify a set of features that help us distinguish malicious apps from benign ones. For example, we find that malicious apps often share names with other apps, and they typically request fewer permissions than benign apps. Second, leveraging these distinguishing features, we show that FRAppE can detect malicious apps with 99.5% accuracy, with no false positives and a high true positive rate (95.9%). Finally, we explore the ecosystem of malicious Facebook apps and identify mechanisms that these apps use to propagate. Interestingly, we find that many apps collude and support each other; in our dataset, we find 1584 apps enabling the viral propagation of 3723 other apps through their posts. Long term, we see FRAppE as a step toward creating an independent watchdog for app assessment and ranking, so as to warn Facebook users before installing apps.

How do people interact with their Facebook wall? At a high level, this question captures the essence of our work. While most prior efforts focus on Twitter, the much fewer Facebook studies focus on the friendship graph or are limited by the amount of users or the duration of the study. In this work, we model Facebook user behavior: we analyze the wall activities of users focusing on identifying common patterns and surprising phenomena. We conduct an extensive study of roughly 7K users over three years during four month intervals each year. We propose PowerWall, a lesser known heavy-tailed distribution to fit our data. Our key results can be summarized in the following points. First, we find that many wall activities, including number of posts, number of likes, number of posts of type photo, etc., can be described by the PowerWall distribution. What is more surprising is that most of these distributions have similar slope, with a value close to 1! Second, we show how our patterns and metrics can help us spot surprising behaviors and anomalies. For example, we find a user posting every two days, exactly the same count of posts; another user posting at midnight, with no other activity before or after. Our work provides a solid step towards a systematic and quantitative wall-centric profiling of Facebook user activity.

Smartphone privacy and security work has focused mostly on malicious apps. We take a different angle by questioning whether good apps suffer from a lack of judgment and interact with "bad" websites. We use the term bad websites to refer to entities that engage in dangerous or annoying activities that range from distributing malware, to phishing and overly aggressive ad spamming. The focus of our work is this relatively neglected aspect of security: "Whom does an app talk to?" In this paper, we design and implement AURA, a framework for identifying the hosts that an app talks to and evaluating the risks this communication entails. AURA makes use of both static and dynamic analysis. We studied 13,500 popular free Android apps that connect to 254,022 URLs and 1,260 malicious Android apps that connect to 19,510 URLs. Our main contribution is showing that good apps pose security risks as they contact at least one website that: (a) distributes malware (8.8% of apps), (b) are in a blacklist (15% of apps) based on the classification by VirusTotal and Web of Trust. Our work can raise awareness that even good apps need to be carefully evaluated, especially as people become more concerned about smartphone security and privacy.

The Bring-Your-Own-Handheld-device (BYOH) phenomenon continues to make inroads as more people bring their own handheld devices to work or school. While convenient to device owners, this trend presents novel management challenges to network administrators. Prior efforts only focused on studying either the comparative characterization of aggregate network traffic between BYOHs and non-BYOHs or network performance issues, such as TCP and download times or mobility issues. We identify one critical question that network administrators need to answer: how do these BYOHs behave individually? In response, we design and deploy Brofiler, a behavior-aware profiling framework that improves visibility into the management of BYOHs. The contributions of our work are two-fold. First, we present Brofiler, a time-aware device-centric approach for grouping devices into intuitive behavioral groups. Second, we conduct an extensive study of BYOHs using our approach with real data collected over a year, and highlight several novel insights on the behavior of BYOHs. These observations underscore the importance of that BYOHs need to be managed explicitly as they behave in unique and unexpected ways.

Online reviews on products and services can be very useful for customers, but they need to be protected from manipulation. So far, most studies have focused on analyzing online reviews from a single hosting site. How could one leverage information from multiple review hosting sites? This is the key question in our work. In response, we develop a systematic methodology to merge, compare, and evaluate reviews from multiple hosting sites. We focus on hotel reviews and use more than 15 million reviews from more than 3.5 million users spanning three prominent travel sites. Our work consists of three thrusts: (a) we develop novel features capable of identifying cross-site discrepancies effectively, (b) we conduct arguably the first extensive study of cross-site variations using real data, and develop a hotel identity-matching method with 93% accuracy, (c) we introduce the TrueView score, as a proof of concept that cross-site analysis can better inform the end user. Our results show that: (1) we detect 7 times more suspicious hotels by using multiple sites compared to using the three sites in isolation, and (2) we find that 20% of all hotels appearing in all three sites seem to have low trustworthiness score. Our work is an early effort that explores the advantages and the challenges in using multiple reviewing sites towards more informed decision making.

This paper focuses on detecting and studying HTTP scanners, which are malicious entities that explore a website selectively for "opportunities" that can potentially be used for subsequent intrusion attempts. Interestingly, there is practically no prior work on the detection of these entities, which are different from web crawlers or machines performing network-level reconnaissance activities such as port scanning. Detecting HTTP scanners is challenging as they are stealthy and often only probe a few key places on a website, so finding them is a needle-in-the-haystack problem. At the same time, they pose serious risk because they perform the first, exploratory step to provide the seed information that may allow hackers to compromise a website. Our work makes two main contributions. First, we propose Scanner Hunter, arguably the first method to detect HTTP scanners efficiently. The novelty and success of the method lies in the use of community structure, in an appropriately constructed bipartite graph, in order to expose groups of HTTP scanners. The rationale is that the aggregated behavior makes identifying groups of scanners easier than attempting to profile and label IP addresses individually. Scanner Hunter achieves an impressive 96.5% detection precision, which is roughly twice as high as the precision of the Machine Learning-based methods that we use as reference. Second, we provide an extensive study of HTTP scanners in an effort to understand: (a) their spatial and temporal properties, (b) the techniques and tools used by the scanners, and (c) the types of resources they are looking for, which can provides hints as to what the subsequent penetration attempt may target. We use six months worth of web traffic logs collected in 2012 from a University campus, the websites hosted by which received over 1.9 billion requests from 12.8 million IPs. We found that the number of HTTP scanners is non-trivial with roughly 4,000 IPs engaging in this type of activity per week. Our work will hopefully raise the awareness of the community regarding this problem while at the same time provide a promising detection technique that can provide the basis for mitigating the risk posed by HTTP scanners.

Determining contributors' expertise, role, and individual importance are fundamental for assessing their impact on a software project. Currently-used expertise metrics are agnostic to contributor roles and can lead to incorrect characterizations. To address these issues, we operationalize contributor expertise and role. First, we revisit current expertise metrics and show that their use bundles many different aspects, creating ambiguity. Second, we introduce clearly-defined contributor roles, which capture multiple project facets. Third, we propose a graph model, based on contributor collaborations, that captures the hierarchical structure of the contributor community in a concise yet informative way. We demonstrate the model's usefulness in two ways: (a) for identifying the structure and evolution of contributor interactions, (b) for predicting contributor roles. We substantiate our study using two large open-source projects, Fire fox and Eclipse. Our systematic approach clarifies and isolates contributor role and expertise, and sheds light onto the dynamics of contributors within software projects.

As the smartphone/cellphone market has exploded, the war on which smartphone platform will dominate has become fiercer than ever. In that vain, the goal of this paper is to answer two fundamental questions: What are the adoption trends for smartphones? And how can we estimate the demand for new smartphones? We answer these two questions by collecting a dataset of 3 million subscribers from a nationwide telecom operator. A key aspect of our work is that we have demographic information per user, such as income level, and age, which we correlate with phone usage patterns. Interestingly, we find that in all demographic groups, Android is leading platform top in all age groups and income levels. A key question is whether the “social influence” affects the choice of phone, which we find more pronounced in business plans. Finally, we develop a predictor to infer the phone a user will switch to considering: (a) the type of previous phone, (b) the social influence, and (c) the demographics of the user. Compared with the reference method, our predictor is effective in: (a) reducing the prediction error in number of phones by 1/3, and (b) in the case of minimizing phone costs, the monetary cost by half. Apart from its interest in observations, our work could help telecom operator forecast their inventory more accurately by pointing to the right properties to consider.

How do people use phone calls and text messages for their communication needs? Most studies so far study each mode of communication in isolation. Here, we study the interplay of multi-modal communications. We analyze more than a billion call and text records from a Chinese city and San Francisco Area between 2007 and 2011. First, we provide some definitions towards a framework for analyzing multi-modal communications. Then,we study the relationship of the two communication modes and quantify several aspects of correlation and inference. For a communicating pair, we find that the existence of texting during the weekend is the strongest indicator that the pair will communicate at other times with texts or calls. We compare the behavior between China and the U.S. and we find several similarities and differences. For example, we find evidence of an after-lunch siesta among Chinese users. Finally, we study the evolution of the two modes over time. We find that texting has taken over in sheer number of ”events” by flipping the number of calls over that of texts from 2: 1 in 2007 to 1:2 in 2011.

Homophily refers to the phenomenon where people who are socially-connected share many characteristics including demographic and behavioral properties. The goal of this paper is to see whether homophily exists in call networks and if so, to what degree we can infer a cellphone user's demographic properties by knowing the demographic information of the people that s/he talks to. We focus on three types of demographic information: a) home location, b) age group, and c) income level. The novelty is two-folds. First, we use both communication metrics and structural properties of call graphs to identify those “important” friends for each user with whom (s)he is most likely to be in homophily. Second, we assess the importance of different time slices such as weekdays, or nights and weekends for capturing different user relationships. We conduct our study on a real data trace with 20M subscribers during one month from a nationwide cellular carrier. Our first contribution is that we quantify the extent of homophily on the call graph and identify the correlations between homophily and communication and structural features. As a second contribution, we develop effective methods to infer demographic information for a cellular user using linear regression to select the most homophily-like friend of her/him. We find that we can predict home location within 20km radius with 80% accuracy, and age group and income level with 78% and 72% accuracy, respectively.

Online social networks (OSNs) have become a popular new vector for distributing malware and spam, which we refer to as socware. Unlike email spam, which is sent by spammers directly to intended victims, socware cascades through OSNs as compromised users spread it to their friends. In this paper, we analyze data from the walls of roughly 3 million Facebook users over five months, with the goal of developing a better understanding of socware cascades.

In this paper, we study the intertwined propagation of two competing "memes" (or data, rumors, etc.) in a composite network. Within the constraints of this scenario, we ask two key questions: (a) which meme will prevail? and (b) can one influence the outcome of the propagations? Our model is underpinned by two key concepts, a structural graph model (composite network) and a viral propagation model (SI1I2S). Using this framework, we formulate a non-linear dynamic system and perform an eigenvalue analysis to identify the tipping point of the epidemic behavior. Based on insights gained from this analysis, we demonstrate an effective and accurate prediction method to determine viral dominance, which we call the EigenPredictor. Next, using a combination of synthetic and real composite networks, we evaluate the effectiveness of various viral suppression techniques by either a) concurrently suppressing both memes or b) unilaterally suppressing a single meme while leaving the other relatively unaffected.

Android uses a system of permissions to control how apps access sensitive devices and data stores. Unfortunately, we have little understanding of the evolution of Android permissions since their inception (2008). Is the permission model allowing the Android platform and apps to become more secure? In this paper, we present arguably the first long-term study that is centered around both permission evolution and usage, of the entire Android ecosystem (platform, third-party apps, and pre-installed apps). First, we study the Android platform to see how the set of permissions has evolved; we find that this set tends to grow, and the growth is not aimed towards providing finer-grained permissions but rather towards offering access to new hardware features; a particular concern is that the set of Dangerous permissions is increasing. Second, we study Android third-party and pre-installed apps to examine whether they follow the principle of least privilege. We find that this is not the case, as an increasing percentage of the popular apps we study are overprivileged. In addition, the apps tend to use more permissions over time. Third, we highlight some concerns with pre-installed apps, e.g., apps that vendors distribute with the phone; these apps have access to, and use, a larger set of higher-privileged permissions which pose security and privacy risks. At the risk of oversimplification, we state that the Android ecosystem is not becoming more secure from the user's point of view. Our study derives four recommendations for improving the Android security and suggests the need to revisit the practices and policies of the ecosystem.

Controlling the dissemination of an entity (e.g., meme, virus, etc) on a large graph is an interesting problem in many disciplines. Examples include epidemiology, computer security, marketing, etc. So far, previous studies have mostly focused on removing or inoculating nodes to achieve the desired outcome.

With 20 million installs a day, third-party apps are a major reason for the popularity and addictiveness of Facebook. Unfortunately, hackers have realized the potential of using apps for spreading malware and spam. The problem is already significant, as we find that at least 13% of apps in our dataset are malicious. So far, the research community has focused on detecting malicious posts and campaigns.

We exploit recent advances in analysis of graph topology to better understand software evolution, and to construct predictors that facilitate software development and maintenance. Managing an evolving, collaborative software system is a complex and expensive process, which still cannot ensure software reliability. Emerging techniques in graph mining have revolutionized the modeling of many complex systems and processes. We show how we can use a graph-based characterization of a software system to capture its evolution and facilitate development, by helping us estimate bug severity, prioritize refactoring efforts, and predict defect-prone releases. Our work consists of three main thrusts. First, we construct graphs that capture software structure at two different levels: (a) the product, i.e., source code and module level, and (b) the process, i.e., developer collaboration level. We identify a set of graph metrics that capture interesting properties of these graphs. Second, we study the evolution of eleven open source programs, including Firefox, Eclipse, MySQL, over the lifespan of the programs, typically a decade or more. Third, we show how our graph metrics can be used to construct predictors for bug severity, high-maintenance software parts, and failure-prone releases. Our work strongly suggests that using graph topology analysis concepts can open many actionable avenues in software engineering research and practice.

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

The Android platform lacks tools for assessing and monitoring apps in a systematic way. This lack of tools is particularly problematic when combined with the open nature of Google Play, the main app distribution channel. As our key contribution, we design and implement ProfileDroid, a comprehensive, multi-layer system for monitoring and profiling apps. Our approach is arguably the first to profile apps at four layers: (a) static, or app specification, (b) user interaction, (c) operating system, and (d) network. We evaluate 27 free and paid Android apps and make several observations: (a) we identify discrepancies between the app specification and app execution, (b) free versions of apps could end up costing more than their paid counterparts, due to an order of magnitude increase in traffic, (c) most network traffic is not encrypted, (d) apps communicate with many more sources than users might expect---as many as 13, and (e) we find that 22 out of 27 apps communicate with Google during execution. ProfileDroid is the first step towards a systematic approach for (a) generating cost-effective but comprehensive app profiles, and (b) identifying inconsistencies and surprising behaviors.

We revisit the problem of computing the path with the minimum cost in terms of the expected number of link layer transmissions (including retransmissions) in wireless mesh networks. Unlike previous efforts, such as the popular ETX, we account for the fact that MAC protocols (including the IEEE 802.11 MAC) incorporate a finite number of transmission attempts per packet. This in turn leads to our key observation: the performance of a path depends not only on the number of the links on the path and the quality of its links, but also, on the relative positions of the links on the path. Based on this observation, we propose ETOP, a path metric that accurately captures the expected number of link layer transmissions required for reliable end-to-end packet delivery. We analytically compute ETOP, which is not trivial, since ETOP is a noncommutative function of the link success probabilities. Although ETOP is a more involved metric, we show that the problem of computing paths with the minimum ETOP cost can be solved by a greedy algorithm. We implement and evaluate a routing approach based on ETOP on a 25-node indoor mesh network. Our experiments show that the path selection with ETOP consistently results in superior TCP goodput (by over 50 percent in many cases) compared to path selection based on ETX. We also perform an in-depth analysis of the measurements to better understand why the paths selected by ETOP improve the TCP performance.

What topologies should be used to evaluate protocols for interdomain routing? Using the most current Internet topology is not practical since its size is prohibitive for detailed, packet-level interdomain simulations. Besides being of moderate size, the topology should be policy-aware, that is, it needs to represent business relationships between adjacent nodes (that represent autonomous systems). In this paper, we address this issue by providing a framework to generate small, realistic, and policy-aware topologies. We propose HBR, a novel sampling method, which exploits the inherent hierarchy of the policy-aware Internet topology. We formally prove that our approach generates connected and legitimate topologies, which are compatible with the policy-based routing conventions and rules. Using simulations, we show that HBR generates topologies that: 1) maintain the graph properties of the real topology; 2) provide reasonably realistic interdomain simulation results while reducing the computational complexity by several orders of magnitude as compared to the initial topology. Our approach provides a permanent solution to the problem of interdomain routing evaluations: Given a more accurate and complete topology, HBR can generate better small topologies in the future.

Landmark-based routing (LR) provides a promising approach for scalable point-to-point routing in wireless sensor networks (WSNs). Though various approaches have been proposed for landmark-based routing, they either introduce significant computational complexity or are inefficient in realistic, dynamic environments. In this paper, we identify three design principles that could form the basis of efficiency: algorithmic simplicity, update efficiency, and application awareness. Motivated by these principles, we present XLR, a new, flexible and comprehensive framework that tackles the inefficiency of landmark-based routing. XLR consists of four components: Relay Selection (RS), Parametric P-Norm distance function (PPN), Efficient Update with Coordinate Difference (EUCD) and General Forwarding (GF). The key advantage of XLR is that any subset of XLR's components can be independently incorporated into most landmark-based routing protocols.We perform extensive simulations to demonstrate that: (i) RS, a simple method, yields good performance comparable with previous methods, (ii) PPN increases LR performance considerably, (iii) EUCD reduces coordinate update overhead by up to 39%, and (iv) our GF outperforms previous approaches that consider factors such as link quality, delay and power consumption independently.

Given a network of who-contacts-whom or who links-to-whom, will a contagious virus/product/meme spread and 'take-over' (cause an epidemic) or die-out quickly? What will change if nodes have partial, temporary or permanent immunity? The epidemic threshold is the minimum level of virulence to prevent a viral contagion from dying out quickly and determining it is a fundamental question in epidemiology and related areas. Most earlier work focuses either on special types of graphs or on specific epidemiological/cascade models. We are the first to show the G2-threshold (twice generalized) theorem, which nicely de-couples the effect of the topology and the virus model. Our result unifies and includes as special case older results and shows that the threshold depends on the first eigenvalue of the connectivity matrix, (a) for any graph and (b) for all propagation models in standard literature (more than 25, including H.I.V.) [20], [12]. Our discovery has broad implications for the vulnerability of real, complex networks, and numerous applications, including viral marketing, blog dynamics, influence propagation, easy answers to 'what-if' questions, and simplified design and evaluation of immunization policies. We also demonstrate our result using extensive simulations on one of the biggest available social contact graphs containing more than 31 million interactions among more than 1 million people representing the city of Portland, Oregon, USA.

Has the behavior of spammers changed over the last few years? To answer this question, we conduct a study from three recent data sources. Specifically, we focus on the following broad questions: (a) how are email addresses harvested, (b) where is spam coming from, and (c) how does spam evolve over time. First, we discuss whether spammers still use email harvesting: 34% of the honeypot accounts we publicised received spam after 72 days on average. Interestingly, we find that simple email address obfuscation is quite effective against harvesting. Second, we identify significant skew in the spatial distribution of the origin of spam in both the IP-level and AS-level of granularity. We find that 20% of the active IPs are responsible for 80% of the total volume of spam and that 10% of the spamming ASes are responsible for the 90% of the volume. Finally, we study the temporal characteristics of the spamming IPs and find that spam activity has spread to new /8 subnetworks since 2006. Considering these spatio-temporal trends, the future of anti-spam is mixed: the current skewed spatial distribution of spam sources could be helpful in filtering spam, but the fact that spam sources are spreading in the IP space is a worrisome sign.

Phishing is an increasingly sophisticated method to steal personal user information using sites that pretend to be legitimate. In this paper, we take the following steps to identify phishing URLs. First, we carefully select lexical features of the URLs that are resistant to obfuscation techniques used by attackers. Second, we evaluate the classification accuracy when using only lexical features, both automatically and hand-selected, vs. when using additional features. We show that lexical features are sufficient for all practical purposes. Third, we thoroughly compare several classification algorithms, and we propose to use an online method (AROW) that is able to overcome noisy training data. Based on the insights gained from our analysis, we propose PhishDef, a phishing detection system that uses only URL names and combines the above three elements. PhishDef is a highly accurate method (when compared to state-of-the-art approaches over real datasets), lightweight (thus appropriate for online and client-side deployment), proactive (based on online classification rather than blacklists), and resilient to training data inaccuracies (thus enabling the use of large noisy training data).

In this paper, we propose a new metric that is applicable both to routing and rate adaptation in multi-rate wireless mesh networks. Unlike many previous efforts, our metric is comprehensive; it considers several factors that affect end-to-end performance such as the effect of the relative positions of the links on a path when choosing the rates of operation and the importance of avoiding congested areas. We call our metric ETM (for Expected Transmission cost in Multi-rate wireless networks). We analytically derive the ETM metric. We show that the ETM metric can be used (a) to determine the best end-to-end path with a greedy routing approach and (b) it can be used to dynamically select the best transmission rate for each link on the path via a dynamic programming approach. Based on ETM, we design and implement the ETM-framework on an indoor wireless mesh network and compare its performance with that of the popular ETT and the recently proposed ETOP metrics. Our experiments show that the ETM-framework yields throughput improvements of up to 253% and 368% as compared with the ETT and ETOP frameworks.

In this paper, we consider a variant of packet replay attacks wherein, an attacker simply replays overheard frames as they are, or with minor manipulations in the packet header; we refer to this as the copycat attack. When routers forward such replayed packets, the levels of congestion and interference increase in large portions of the network. Our experiments indicate that even a single attacker can degrade the route throughput by up to 61%. While simple to use techniques such as digitally signing every packet can stem the dissemination of such packets, they are resource intense. Thus, we design a lightweight detection and prevention system, COPS (for Copycat Online Prevention System), that intelligently uses a combination of digital signatures and Bloom filters to cope with the attack. With our system, the task of identifying and discarding replayed packets is distributed across a plurality of nodes on a route. We implement COPS on real hardware and perform experiments on our 42 node wireless testbed. Our measurements indicate that COPS achieves its objective; it can efficiently contain the effects of replayed packets to a local neighborhood without incurring high resource consumption penalties. Specifically, we show that COPS reduces the route throughput degradation by up to 66%.

Profiling Internet backbone traffic is becoming an increasingly hard problem since users and applications are avoiding detection using traffic obfuscation and encryption. The key question addressed here is: Is it possible to profile traffic at the backbone without relying on its packet and flow level information, which can be obfuscated? We propose a novel approach, called Profiling-By-Association (PBA), that uses only the IP-to-IP communication graph and information about some applications used by few IP-hosts (a.k.a. seeds). The key insight is that IP-hosts tend to communicate more frequently with hosts involved in the same application forming communities (or clusters). Profiling few members within a cluster can "give away" the whole community. Following our approach, we develop different algorithms to profile Internet traffic and evaluate them on real-traces from four large backbone networks. We show that PBA's accuracy is on average around 90% with knowledge of only 1% of all the hosts in a given data set and its runtime is on the order of minutes (≈ 5).

Industry has responded to the ever-growing presence of spam by attacking the spam distribution infrastructure, essentially trying to prevent spam email from ever landing in the inbox of end-users. Recently, industry and academia have begun investigating the web hosting infrastructure of spam campaigns, attacking spammers where it hurts most, in their pocketbooks. Spammers have responded by introducing cooperative interme- diaries that redirect traffic, effectively decoupling the spam-advertised URL from the final destination website. In this study, we analyze not only the URLs in spam messages, but the less-studied redirection infrastructure that takes the user to a target website or other malicious host. Our initial results show that among all the hosts that can be reached directly from URLs embedded in email bodies, 64.87% are cooperative redirection hosts. However, these redirection hosts are only used to protect a small portion (11.33%) of final destination websites. Additionally, we find that around 70% of embedded URLs resolve to two ranges of IP space (61.0.0.0/8 and 124.0.0.0/8). By further analyzing the relationship between the final destinations and redirection hosts, we find that 74.19% of the final destination hosts are located in the same AS with their redirection hosts.

We address the following questions. Is there link homophily in the application layer traffic? If so, can it be used to accurately classify traffic in network trace data without relying on payloads or properties at the flow level? Our research shows that the answers to both of these questions are affirmative in real network trace data. Specifically, we define link homophily to be the tendency for flows with common IP hosts to have the same application (P2P, Web, etc.) compared to randomly selected flows. The presence of link homophily in trace data provides us with statistical dependencies between flows that share common IP hosts. We utilize these dependencies to classify application layer traffic without relying on payloads or properties at the flow level. In particular, we introduce a new statistical relational learning algorithm, called Neighboring Link Classifier with Relaxation Labeling (NLC+RL). Our algorithm has no training phase and does not require features to be constructed. All that it needs to start the classification process is traffic information on a small portion of the initial flows, which we refer to as seeds. In all our traces, NLC+RL achieves above 90% accuracy with less than 5% seed size; it is robust to errors in the seeds and various seed-selection biases; and it is able to accurately classify challenging traffic such as P2P with over 90% Precision and Recall.

The evolution of the Internet during the last years, has lead to a dramatic increase in the size of its representation as a graph at the Autonomous System (AS) level. Reproducing a smaller size snapshot of the AS graph is important for studying protocols in realistic settings. The objective of our work, is to create a generator that accurately emulates and reproduces the distinctive properties of the Internet graph. Our approach is based on (a) the incorporation of the jellyfish-like structure of the Internet and (b) the consideration of the peer-to-peer and customer-provider relations between ASs. We are the first to capture the distinctive structure of the Internet graph together with utilizing the information provided by the AS relationships in order to create a tool for generating a realistic representation. Compared with existing generators, our tool does not try to satisfy specific metrics; instead, it tries to remain faithful to the conceptual model of the Internet structure. In addition, our approach can lead to (i) the identification of important attributes and patterns in the Internet AS topology, and (ii) the extraction of valuable information on various relationships between ASs and the corresponding impact on the Internet structure.We implement our graph generator and evaluate it using one of the largest and most recent datasets for the AS topology. Our evaluations clearly show the ability of our tool to capture the structural properties of the Internet topology at the AS level with high accuracy. Finally, we discuss how our generator can not only reproduce, but also shrink the input graph while maintaining its unique structure and properties.

Towards increasing spatial reuse, cellular networks may be augmented with ad hoc connectivity. In the resulting hybrid network, the coverage area of the base station (BS) is reduced and the users within this area relay packets from/to the users outside. With this approach, shorter range, higher-rate links are used; this favors an increase in spatial reuse and thus, the achievable capacity. However, multi-hop relaying overhead can hurt capacity. In this paper, we analytically compute the uplink capacity, defined as an upper bound on the achievable throughput under max-min fairness. To gage the tightness of the bound, we seek to find the optimal transmission schedule for delivering the packets from the nodes in a cell to the BS. In general, constructing the optimal uplink schedule is NP-hard. We develop a heuristic approach and show via simulations that the resulting performance is close to the derived capacity bound. Our results suggest that (a) the hybrid network can achieve up to a 200 % increase in the uplink capacity compared to a pure cellular network, and (b) the simulated throughput is close to the analytically computed capacity showing that our bound is tight.

Dense deployments of WLANs suffer from increased interference and, as a result, reduced capacity. There are three main functions used to improve the overall network capacity: 1) intelligent frequency allocation across access points (APs); 2) load-balancing of user affiliations across APs; and 3) adaptive power control for each AP. Several algorithms have been proposed in each category, but so far, their evaluation has been limited to: a) each approach in isolation; and b) simulations or small-scale testbeds. In this paper, we ask the question: What is the best way to combine these different functions? Our focus is to fully explore the interdependencies between the three functions in order to understand when and how to deploy them on a network. We follow a measurement-driven study to quantify the effects of three previously proposed optimization schemes (one for each category) on a relatively large testbed and in many different scenarios. Surprisingly, we find that blindly applying all the three optimization schemes is not always preferable; it can sometimes degrade the performance by as much as 24% compared to using only two of the schemes. We discover that there are explicit conditions that are conducive for applying specific combinations of the optimization schemes. We capture these conditions within a comprehensive framework, which we call measurement-driven guidelines (MDG). While we derive such guidelines based on measurements on one experimental testbed, we test their applicability and efficacy on a second testbed in a different location. We show that our framework improves network capacity consistently across both testbeds, with improvements ranging from 22% to 142% with 802.11a, and 103% to 274% with 802.11g.

Network traffic can be represented by a Traffic Dispersion Graph (TDG) that contains an edge between two nodes that send a particular type of traffic (e.g., DNS) to one another. TDGs have recently been proposed as an alternative way to interpret and visualize network traffic. Previous studies have focused on static properties of TDGs using graph snapshots in isolation. In this work, we represent network traffic with a series of related graph instances that change over time. This representation facilitates the analysis of the dynamic nature of network traffic, providing additional descriptive power. For example, DNS and P2P graph instances can appear similar when compared in isolation, but the way the DNS and P2P TDGs change over time differs significantly. To quantify the changes over time, we introduce a series of novel metrics that capture changes both in the graph structure (e.g., the average degree) and the participants (i.e., IP addresses) of a TDG. We apply our new methodologies to improve graph-based traffic classification and to detect changes in the profile of legacy applications (e.g., e-mail).

The Border Gateway Protocol (BGP) is one of the fundamental computer communication protocols. Monitoring and mining BGP update messages can directly reveal the health and stability of Internet routing. Here we make two contributions: firstly we find patterns in BGP updates, like self-similarity, power-law and lognormal marginals; secondly using these patterns, we find anomalies. Specifically, we develop BGP-lens, an automated BGP updates analysis tool, that has three desirable properties: (a) It is effective, able to identify phenomena that would otherwise go unnoticed, such as a peculiar 'clothesline' behavior or prolonged 'spikes' that last as long as 8 hours; (b) It is scalable, using algorithms are all linear on the number of time-ticks; and (c) It is admin-friendly, giving useful leads for phenomenon of interest.

Recent research on Internet traffic classification algorithms has yield a flurry of proposed approaches for distinguishing types of traffic, but no systematic comparison of the various algorithms. This fragmented approach to traffic classification research leaves the operational community with no basis for consensus on what approach to use when, and how to interpret results. In this work we critically revisit traffic classification by conducting a thorough evaluation of three classification approaches, based on transport layer ports, host behavior, and flow features. A strength of our work is the broad range of data against which we test the three classification approaches: seven traces with payload collected in Japan, Korea, and the US. The diverse geographic locations, link characteristics and application traffic mix in these data allowed us to evaluate the approaches under a wide variety of conditions. We analyze the advantages and limitations of each approach, evaluate methods to overcome the limitations, and extract insights and recommendations for both the study and practical application of traffic classification. We make our software, classifiers, and data available for researchers interested in validating or extending this work.

Spelling errors when typing a URL can be exploited by website-squatters: users are led to phony sites in a phenomenon we call parasitic URL naming. These phony sites imitate popular websites and try to extract personal information from unsuspecting users, or simply advertise and sell products to users. In this paper, we conduct a massive study in order to quantify the extent of this parasitic URL naming We start with a corpus of 900 popular websites, which we refer to as original URLs, and generate roughly 3 million URLs by varying the original names systematically and exhaustively. Over a period of 60 days, we analyze how many sites have URLs very similar to our original URLs. We find that parasitic URL naming is a wide-spread problem and quantify the extent of this issue. We believe that this work will provide the first step towards research and tools to combat web-fraud.

The Internet community has not reached a consensus on an appropriate topological model for evaluating the performance of inter-domain routing protocols. Using the current Internet topology is not realistic, since its size is prohibitively large for, say, a packet-level BGP simulation. Furthermore, routing policies, which play a critical role in inter-domain routing, are often ignored in many simulation studies. In this paper, we address this issue by designing an algorithm to generate small-scale, realistic, and policy-aware topologies. We propose HBR, a network sampling method, which produces topologies that preserve the fundamental properties of the Internet graph, including, in particular, its hierarchical structure. Our approach provides a long-term solution to the difficult problem of AS-level routing evaluations: it can be used to generate small realistic topologies in the future, starting from any newer or more complete Internet instance.

We revisit the problem of computing the path with the minimum cost in terms of the expected number of link layer transmissions (including retransmissions) in wireless mesh networks. Unlike previous efforts, such as the popular ETX, we account for the fact that MAC protocols (including the IEEE 802.11 MAC) incorporate a finite number of transmission attempts per packet. This in turn leads to our key observation: the performance of a path depends not only on the number of the links on the path and the quality of its links, but also, on the relative positions of the links on the path. Based on this observation, we propose ETOP, a path metric that accurately captures the expected number of link layer transmissions required for reliable end-to-end packet delivery. We analytically compute ETOP, which is not trivial, since ETOP is a noncommutative function of the link success probabilities. Although ETOP is a more involved metric, we show that the problem of computing paths with the minimum ETOP cost can be solved by a greedy algorithm. We implement and evaluate a routing approach based on ETOP on a 25-node indoor mesh network. Our experiments show that the path selection with ETOP consistently results in superior TCP goodput (by over 50% in many cases) compared to path selection based on ETX. We also perform an in-depth analysis of the measurements to better understand why the paths selected by ETOP improve the TCP performance.

In this paper, towards improving spatial reuse in a cellular network, we consider augmenting it with wireless ad hoc connectivity. The coverage area of each base-station is reduced and the users that are within the area relay traffic to nodes outside the area; these users further relay data to more distant users within the cell. The resulting network is referred to as a hybrid network. While this approach can result in shorter range higher-rate links and improved spatial reuse which, together favor a capacity increase, it relies on multi-hop forwarding which is detrimental to the overall capacity. Our objective in this work is to evaluate the impact of these conflicting factors on the capacity of the hybrid network and determine if this capacity is higher than that of the original cellular network. We formally define the capacity of the network as the maximum possible downlink throughput under the conditions of max-min fairness. We analytically compute the capacity of a two-dimensional hybrid network withregularplacements of base-stations (BSs) and users. We validate our analytical results via simulations. Our studies demonstrate that capacity improvements are possible in certain parametric regimes in which the penalty due to multi-hop relaying does not outweigh the gains due to spatial reuse and shorter higher-rate links. Our simulations also demonstrate that if the users are placed randomly, the behavioral results are similar to that with regular placements of users.

The AS-level Internet topology has shown significant clustering features. We propose a new set of clustering metrics and conduct extensive measurement on the AS- level Internet topology. We give a thorough characterization on the clustering features and their evolution. We also study the clustering features of different topological structures by comparing the Internet with various topology models. Due to the limitation of existing topology models on capturing clustering features, we design a new topology model based on clustering. Through extensive evaluations, we claim that our model can closely capture the clustering features as well as other common topological properties.

The accurate determination of the link quality is critical for ensuring that functionalities such as intelligent routing, load-balancing, power control and frequency selection operate efficiently. There are 4 primary metrics for capturing the quality of a wireless link: RSSI (Received Signal Strength Indication), SINR (Signal-to-Interference-plus-Noise Ratio), PDR (Packet-Delivery Ratio), and BER (Bit-Error Rate). In this paper, we perform a measurement-based study in order to answer the question: which is the appropriate metric to use, and under what conditions? We evaluate the relative accuracy of each metric by conducting experiments with multiple transmission rates and varying levels of interference on a large set of links. We observe that each metric has advantages and projects one or more limitations. Our study suggests that a careful consideration of these limitations is essential, and provides guidelines on the applicability of each metric.

We propose the first practical solution to the longstanding problem of secure wireless routing in the presence of colluding attackers. Our secure routing protocol, Sprout, continuously tries new routes to the destination. Routes are probabilistically generated, with complete disregard for performance metrics. This makes Sprout uniquely resilient to attack: it cannot be tempted by shortcuts. In order to avoid compromised routes, and to ensure good overall performance, the quality of each active route is monitored by means of signed end-to-end acknowledgments. The amount of traffic sent on each route is adjusted accordingly. Sprout effectively mitigates the vast majority of known routing layer attacks, even when under assault from a large number of colluding attackers. Experiments on our 31-node testbed demonstrates the real-world performance of Sprout in terms of packet delivery ratio, round-trip times and TCP throughput. Our security analysis and simulation results show that Sprout is able to quickly find working paths in networks of hundreds of nodes and dozens or more attackers. For example, in a network of 200 nodes and an astounding 64 attackers, Sprout, on average, found a successful route within less than 10 attempts. Yet, in benign settings, Sprout provides TCP throughput within 15% of the shortest path throughput Overall, Sprout consistently delivers high, reliable performance in benign as well as hostile environments.

Monitoring network traffic and detecting unwanted applications has become a challenging problem, since many applications obfuscate their traffic using unregistered port numbers or payload encryption. Apart from some notable exceptions, most traffic monitoring tools use two types of approaches: (a) keeping traffic statistics such as packet sizes and interarrivals, flow counts, byte volumes, etc., or (b) analyzing packet content. In this paper, we propose the use of Traffic Dispersion Graphs (TDGs) as a way to monitor, analyze, and visualize network traffic. TDGs model the social behavior of hosts ("who talks to whom"), where the edges can be defined to represent different interactions (e.g. the exchange of a certain number or type of packets). With the introduction of TDGs, we are able to harness a wealth of tools and graph modeling techniques from a diverse set of disciplines.

Consider a network of, say, sensors, or P2P nodes, or Bluetooth-enabled cell-phones, where nodes transmit information to each other and where links and nodes can go up or down. Consider also a 'datum', that is, a piece of information, like a report of an emergency condition in a sensor network, a national traditional song, or a mobile phone virus. How often should nodes transmit the datum to each other, so that the datum can survive (or, in the virus case, under what conditions will the virus die out)? Clearly, the link and node fault probabilities are important - what else is needed to ascertain the survivability of the datum? We propose and solve the problem using non-linear dynamical systems and fixed point stability theorems. We provide a closed-form formula that, surprisingly, depends on only one additional parameter, the largest eigenvalue of the connectivity matrix. We illustrate the accuracy of our analysis on realistic and real settings, like mote sensor networks from Intel and MIT, as well as Gnutella and P2P networks.

Protecting BGP routing from errors and malice is one of the next big challenges for Internet routing. Several approaches have been proposed that attempt to capture and block routing anomalies in a proactive way. In practice, the difficulty of deploying such approaches limits their usefulness. We take a different approach: we start by requiring a solution that can be easily implemented now. With this goal in mind, we consider ourselves situated at an AS, and ask the question: how can I detect erroneous or even suspicious routing behavior? We respond by developing a systematic methodology and a tool to identify such updates by utilizing existing public and local information. Specifically, we process and use the allocation records from the Regional Internet Registries (RIR), the local policy of the AS, and records used to generate filters from Internet Routing Registries (IRR). Using our approach, we can automatically detect routing leaks. Additionally, we identify some simple organizational and procedural issues that would significantly improve the usefulness of the information of the registries. Finally, we propose an initial set of rules with which an ISP can react to routing problems in a way that is systematic, and thus, could be automated.

Dense deployments of WLANs suffer from increased interference and as a result, reduced capacity. There are three main functions used to improve the overall network capacity: a) intelligent frequency allocation across APs, b) load-balancing of user affiliations across APs, and c) adaptive power-control for each AP. Several algorithms have been proposed in each category, but so far, their evaluation has been limited to: (a) each approach in isolation and, (b)simulations or small-scale testbeds. In this paper, we ask the question: what is the best way to combine these different functions? Our focus is to fully explore the interdependencies between the three functions in order to understand when and how to deploy them on a network. We follow a measurement-driven study to quantify the effects of three previously proposed optimization schemes (one for each category) on a relatively large testbed and in many different scenarios. Surprisingly, we find that blindly applying all the three optimization schemes is not always preferable; it can sometimes degrade the performance by as much as 24% compared to using only two of the schemes. We discover that there are explicit conditions that are conducive for applying specific combinations of the optimization schemes. We capture those conditions within a comprehensive framework, which we call MDG (Measurement-Driven Guidelines). While we derive suchguidelines based on measurements on one experimental testbed, we test their applicability and efficacy on a second testbed in a different location. We show that our framework improves network capacity consistently acrossboth testbeds, with improvements ranging from 22% to 142% with 802.11a, and 103% to 274% with 802.11g.

We revisit the problem of computing the path with the minimum cost in terms of the expected number of link layer retransmissions in wireless mesh networks. Unlike previous efforts (such as the popular ETX) we account for the fact that link layer protocols (such as the IEEE 802.11 MAC) incorporate a non-zero but finite number of retransmission attempts per packet. A key observation that motivates this work is that the performance of a path depends not only on the number of links on the path and their qualities, but also on the relative positions of the links on the path. In particular, the closer a lossy link to the destination, the higher is its impact on the performance of that path. We design a new path metricthat captures all of the above factors and we call this metric ETOP. In this paper, we provide a synopsis of the analytical computation of ETOP. We also implement a routing strategy based on ETOP on a 25-node experimental testbed and provide sample results to showcase the performance with ETOP.

MOTIVATION: Much research has been dedicated to large-scale protein interaction networks including the analysis of scale-free topologies, network modules and the relation of domain-domain to protein-protein interaction networks. Identifying locally significant proteins that mediate the function of modules is still an open problem. METHOD: We use a layered clustering algorithm for interaction networks, which groups proteins by the similarity of their direct neighborhoods. We identify locally significant proteins, called mediators, which link different clusters. We apply the algorithm to a yeast network. RESULTS: Clusters and mediators are organized in hierarchies, where clusters are mediated by and act as mediators for other clusters. We compare the clusters and mediators to known yeast complexes and find agreement with precision of 71% and recall of 61%. We analyzed the functions, processes and locations of mediators and clusters. We found that 55% of mediators to a cluster are enriched with a set of diverse processes and locations, often related to translocation of biomolecules. Additionally, 82% of clusters are enriched with one or more functions. The important role of mediators is further corroborated by a comparatively higher degree of conservation across genomes. We illustrate the above findings with an example of membrane protein translocation from the cytoplasm to the inner nuclear membrane. AVAILABILITY: All software is freely available under Supplementary information.

Cooperative diversity facilitates spatio-temporal communications without requiring the deployment of physical antenna arrays. While physical layer studies on cooperative diversity have been extensive, higher layer protocols which translate the achievable reduction in the SNR per bit for a given target BER, into system wide performance enhancements are yet to mature. The challenge is that appropriate higher layer functions are needed in order to enable cooperative diversity at the physical layer. We focus on network-wide broadcasting with the use of cooperative diversity in ad hoc networks. We design a novel distributed network-wide broadcasting protocol that takes into account the physical layer dependencies that arise with cooperative diversity. We perform extensive simulations that show that our protocol can outperform the best of the noncooperative broadcasting protocols by: (a) achieving up to a threefold increase in network coverage and, (b) by decreasing the latency incurred during the broadcast by about 50%. We also construct an analytical model that captures the behavior of our protocol. Furthermore, we show that computing the optimal solution to the cooperative broadcast problem is NP-complete and construct centralized approximation algorithms. Specifically, we construct an O(Nepsi)-approximation algorithm with a computational complexity of O(N4/epsi); we also construct a simpler greedy algorithm.. The costs incurred with these algorithms serve as benchmarks with which one can compare that achieved by any distributed protocol

We propose a MAC protocol for use in multihop wireless networks that deploy an underlying UWB (ultra wide band)-based physical layer. We consider a multiband approach to better utilize the available spectrum, where each transmitter sends longer pulses in one of many narrower frequency bands. The motivation comes from the observation that, in the absence of a sophisticated equalizer, the size of a slot for transmitting a UWB pulse is typically dictated by the delay spread of the channel. Therefore, using a wider frequency band to shorten the transmission time for each pulse does not increase the data rate in proportion to the available bandwidth. Our approach allows data transmissions to be contiguous and practically interference free, and, thus, highly efficient. For practicality, we ensure the conformance of our approach to FCC-imposed emission limits. We evaluate our approach via extensive simulations, and our results demonstrate the significant advantages of our approach over single-band solutions: the throughput increases significantly and the number of collisions decreases considerably. Finally, we analyze the behavior of our MAC protocol in a single-hop setting in terms of its efficiency in utilizing the multiple bands

Space-time communications can help combat fading and, hence, can significantly increase the capacity of ad hoc networks. Cooperative diversity or virtual antenna arrays facilitate spatio-temporal communications without actually requiring the deployment of physical antenna arrays. Virtual MISO entails the simultaneous transmission of appropriately encoded information by multiple nodes to effectively emulate a transmission on an antenna array. We present a novel multilayer approach for exploiting virtual MISO links in ad hoc networks. The approach spans the physical, medium access control and routing layers, and provides 1) a significant improvement in the end-to-end performance in terms of throughput and delay and 2) robustness to mobility and interference-induced link failures. The key physical layer property that we exploit is an increased transmission range due to achieved diversity gain. Except for space-time signal processing capabilities, our design does not require any additional hardware. We perform extensive simulations to quantify the benefits of our approach using virtual MISO links. As compared to using only SISO links, we achieve an increase of up to 150 percent in terms of the end-to-end throughput and a decrease of up to 75 percent in the incurred end-to-end delay. Our results also demonstrate a reduction in the route discovery attempts due to link failures by up to 60 percent, a direct consequence of the robustness that our approach provides to link failures

We find that current group communications protocols are far from "one size fits all", they are typically geared toward and optimized for particular scenarios. Multicasting, in general, works well if the density of group members is sparse and in low mobility; broadcasting, in contrast, works well with a high density of group members and in high mobility. Due to the dynamics of the network, one strategy may be preferable to the other at different times and in different localized regions. In this paper, we first quantify the trade-offs between broadcasting and multicasting and evaluate the suitability of a strategy in various scenarios of deployment. Based on the lessons learned, we design a protocol that adapts in response to the dynamics of the network. We named our protocol Fireworks. Fireworks is a hybrid two-tier multicast/broadcast protocol that provides efficient and lightweight multicast dissemination and self-adapts in response to variations in the density and distribution of group members to provide efficient performance. Fireworks creates pockets of broadcast distribution in areas with many members, while it creates and maintains a multicast backbone to interconnect these dense pockets. Fireworks offers packet delivery statistics comparable to that of a pure multicast scheme but with significantly lower overheads. We also show that Fireworks has a lower level of degrading influence on the performance of coexisting unicast sessions than either traditional multicast or broadcast methods

Peer to peer (P2P) flows constitute a large portion of Internet traffic meandering through different ISP domains. Hence, it is of prime concern for ISPs to try and gauge the number of active P2P users and where they are located, both inside and outside their respective domains. An analysis of where P2P users are located in the Internet provides an insight into understanding which ISPs harbor a majority of P2P peers, which ones afford most transit to P2P flows, and possibly which ISPs should focus on anti-P2P policies the most. We observe an extremely skewed distribution, approximately 92 to 98% of P2P flows ending in tier 1 and tier 4 ISPs, and just 2 to 8% ending in tier 2 and 3 ISPs. We quantify the role of ISPs in allowing P2P flows to traverse through their domains and observe a similar skewed distribution wherein tier 1 and tier 4 ISPs contribute 92 to 95 % of all hops on most P2P flows. Moreover, we compare P2P traffic with http and Internet radio traces to uncover potential parameters to differentiate between these types of flows. We present detailed results based on active measurements taken over a 30 day period, spanning over half a million P2P flows, collected from measurements employing a number of popular P2P clients hosted inside two popular ISPs.

In a wormhole attack, wireless transmissions are recorded at one location and replayed at another, creating a virtual link under attacker control. Proposed counter-measures to this attack use tight clock synchronization, specialized hardware, or overhearing, making them difficult to realize in practice. TrueLink is a timing based countermeasure to the wormhole attack. Using TrueLink, a node i can verify the existence of a direct link to an apparent neighbor, j. Verification of a link i harr j operates in two phases. In the rendezvous phase, the nodes exchange nonces alphajand betai. This is done with tight timing constraints, within which it is impossible for attackers to forward the exchange between distant nodes. In the authentication phase, i and j transmit a signed message (alphaj,betai), mutually authenticating themselves as the originator of their respective nonce. TrueLink does not rely on precise clock synchronization, GPS coordinates, overhearing, geometric inconsistencies, or statistical methods. It can be implemented using only standard IEEE 802.11 hardware with a minor backwards compatible firmware update. TrueLink is meant to be used together with a secure routing protocol. Such protocols require an authentication mechanism, which will also be used by TrueLink. TrueLink is virtually independent of the routing protocol used. Our performance evaluation shows that TrueLink provides effective protection against potentially devastating wormhole attacks.

Space-time communications can help combat fading and hence can significantly increase the capacity of ad hoc networks. Cooperative diversity or virtual antenna arrays facilitate spatio-temporal communications without actually requiring the deployment of physical antenna arrays. Virtual MISO entails the simultaneous transmission of appropriately encoded information by multiple nodes to effectively emulate a transmission on an antenna array. We present a novel multi-layer approach for exploiting virtual MISO links in ad hoc networks. The approach spans the physical, medium access control and routing layers and provides: (a) a significant improvement in the end-to-end performance in terms of throughput and delay and, (b) robustness to mobility and interference induced link failures. The key physical layer property that we exploit is an increased transmission range due to achieved the diversity gain. Except for space-time signal processing capabilities, our design does not require any additional hardware. We perform extensive simulations to quantify the benefits of our approach using virtual MISO links. As compared to using only SISO links, we achieve an increase of up to 150% in terms of the end-to-end throughput and a decrease of up to 75% in the incurred end-to-end delay. Our results also demonstrate a reduction in the route discovery attempts due to link failures by up to 60%, a direct consequence of the robustness that our approach provides to link failures.

BitTorrent (BT) in the last years has been one of the most effective mechanisms for P2P content distribution. Although BT was created for distribution of time insensitive content, in this work we try to identify what are the minimal changes needed in the BT's mechanisms in order to support streaming. The importance of this capability is that the peer will now have the ability to start enjoying the video before the complete download of the video file. This ability is particularly important in highly polluted environments, since the peer can evaluate the quality of the video content early and thus preserve its valuable resources. In a nutshell, our approach gives higher download priority to pieces that are close to be reproduced by the player. This comes in contrast to the original BT protocol, where pieces are downloaded in an out-of-order manner based solely on their rareness. In particular, our approach tries to strike the balance between downloading pieces in: (a) playing order, enabling smooth playback, and (b) the rarest first order, enabling the use of parallel downloading of pieces. In this work, we introduce three different Piece Selection mechanisms and we evaluate them through simulations based on how well they deliver streaming services to the peers.

The secure operation of ad hoc networks faces the novel challenge of location verification on top of the security challenges that wireline networks face. The novelty lies in the fact that a node can correctly validate who it is, but lie about its location and exploit this to create problems to the network. There are three main factors that make ad hoc networks more vulnerable: (a) nodes can overhear other nodes announcements, (b) nodes can lie about their location, and (c) nodes can avoid detection and isolation by moving. As a result, malicious nodes can fake their position and this way obstruct the routing. In this work, we explain how location and topology related malice can affect the security of wireless ad hoc networks. First, we present the most important attacks that can stem from misuse of location information. Second, we provide an overview of security routing approaches. Although several of the current techniques are promising, we conclude that there does not exist a bulletproof approach as of yet

Abstract Ultra wide band (UWB) technology offers a promising high capacity solution for short‐range wireless ad hoc networks, as in home networks or in wearable ad hoc networks. In this paper, we propose a novel multi‐band MAC protocol for use in small ad hoc networks that deploy an underlying UWB based physical layer. In our approach, we divide the available UWB bandwidth into multiple simultaneously usable bands. In the absence of a sophisticated equalizer, the size of a slot for transmitting a UWB pulse is typically dictated by thedelay spreadof the channel. Therefore, using a wider frequency band to shorten the transmission time for each pulse does not increase the data rate in proportion to the available bandwidth. A multi‐band approach that uses a plurality of bands that adhere to FCC specifications, with slightly elongated pulse durations, provides a solution that can effectively utilize the UWB spectrum. Our approach is based on the idea of conflict resolution using binary ‘something’/‘nothing’ feedback, which has not been widely studied in wireless and specifically in UWB networks. Our protocol unites binary conflict resolution and multi‐band utilization to effectively utilize the available bandwidth. To ensure that our proposed approach is tightly knit with the underlying physical layer, we discuss physical–layer dependencies and the conformance to FCC‐imposed emission limits. We evaluate our approach via extensive simulations. Our simulation results demonstrate the significant advantages of our approach over single‐band solutions: the throughput increases significantly, and the number of collisions decreases considerably. Copyright © 2006 John Wiley & Sons, Ltd.

Routing asymmetry in the Internet can significantly affect the manner in which we model and simulate its behavior. In this paper, we study routing asymmetry in the Internet and present quantitative evaluations on the extent of such asymmetry today. Our quantitative evaluations provide a measure of the difference between the forward and reverse paths between two end points. Routing asymmetry has not been studied extensively before; this is primarily due to the lack of a systematic approach for quantifying asymmetry except for simply computing the difference between the forward and reverse path lengths. By applying our framework for representing asymmetry, we quantify routing asymmetry for both US higher education academic networks and general commercial networks at two different levels: the autonomous system (AS) level and the router (or link) level. We take into consideration, not only the difference in the forward and reverse path lengths, but also the AS and link identities and the sequence in which these entities appear on the paths. We measure the AS level routing asymmetry, and provide upper lower bounds on link level routing asymmetry. Our studies show that academic networks appear to be more symmetric than general commercially deployed networks. Furthermore, our studies demonstrate that routing asymmetry exhibits a skewed distribution i.e., a few end-points seem to display a higher extent of participation on asymmetric routes.

Abstract — Ultra Wide Band (UWB) technology offers a promising high capacity solution for wireless networks with short-range links. However, MAC and higher-layer ad hoc network protocols that exploit the UWB technology are yet to mature. In this paper, we propose a MAC protocol for use in multi-hop wireless networks that deploy an underlying UWB based physical layer. We adopt a multi-band approach wherein we divide the available UWB bandwidth into multiple simultaneously usable bands. The motivation comes from the following observation: in the absence of a sophisticated equalizer, the size of a slot for transmitting a UWB pulse is typically dictated by the delay spread of the channel. Therefore, using a wider frequency band to shorten the transmission time for each pulse may not increase the data rate in proportion to the available bandwidth. Thus, we consider a multi-band approach to better utilize the available spectrum, where each transmitter sends longer pulses in one of many narrower frequency bands. Unlike previous single hopped schemes that rely on timehopping, our approach allows data transmissions to be contiguous, and thus, highly efficient. The approach also ensures that data communications are practically interference free and are only subject to thermal noise effects. To ensure that our proposed approach is tightly knit with the underlying physical layer, we discuss physical-layer dependencies and the conformance of our approach to FCC-imposed emission limits. We evaluate our approach via extensive simulations. Our simulation results demonstrate the significant advantages of our approach over single-band solutions: the throughput increases significantly, and the number of collisions decreases considerably.

We present a fundamentally different approach to classifying traffic flows according to the applications that generate them. In contrast to previous methods, our approach is based on observing and identifying patterns of host behavior at the transport layer. We analyze these patterns at three levels of increasing detail (i) the social, (ii) the functional and (iii) the application level. This multilevel approach of looking at traffic flow is probably the most important contribution of this paper. Furthermore, our approach has two important features. First, it operates in the dark, having (a) no access to packet payload, (b) no knowledge of port numbers and (c) no additional information other than what current flow collectors provide. These restrictions respect privacy, technological and practical constraints. Second, it can be tuned to balance the accuracy of the classification versus the number of successfully classified traffic flows. We demonstrate the effectiveness of our approach on three real traces. Our results show that we are able to classify 80%-90% of the traffic with more than 95% accuracy.

Broadcasting is an ad hoc network critical function component, and, in many deployments, making it power efficient is extremely important. Current power adaptive approaches proposed for broadcasting can be grouped into (a) centralized or omniscient schemes, and (b) decentralized or localized schemes. Due to the absence of global information, localized algorithms may not produce optimal or near-optimal solutions. On the other hand, global knowledge is not typically available to nodes and may be extremely expensive to disseminate. We examine the importance of the lack of global information on the performance of localized approaches. We have performed extensive simulations and compare the performance of localized power adaptive broadcasting with the performance of the well-known broadcast incremental power (BIP), an omniscient algorithm. We analyze the behaviors of the two protocols and identify the reasons for the differences in behavior. We observe that while the global state does provide better performance in terms of energy efficiency, the localized scheme performs better in terms of the latency incurred in the broadcast. Based on the observed behavioral traits of the two protocols, we suggest changes by which the energy consumption with the localized scheme is reduced by as much as 20%, while incurring almost no penalty in terms of latency.

Our objective is to quantify the extent of routing asymmetry in the Internet: the measure of the difference between the forward and backward paths between two end points. Routing asymmetry has not been studied extensively. Most previous studies only consider asymmetry in terms of length and there is a lack of a systematic approach for quantifying asymmetry. One of the challenges in quantifying asymmetry is the formulation of an appropriate set of metrics that can effectively capture various notions of asymmetry. We point out that asymmetry could be of various types. We propose a framework to quantify the routing asymmetry between end hosts and propose two new metrics: absolute asymmetry and length-based normalized asymmetry. Our metrics capture the differences in router/AS identities, their appearing sequences and path lengths in a seamless way. We apply our framework to real Internet measurement data and examine routing asymmetry at the autonomous system (AS) level. We deduce the routing asymmetry distribution based on our framework, and we find that about 14% of pairs of routes considered display AS level routing asymmetry. Furthermore, our studies demonstrate that the routing asymmetry exhibits a skewed distribution, since a few end-points are consistently members of asymmetric pairs.

Recent reports in the popular media suggest a significant decrease in peer-to-peer (P2P) file-sharing traffic, attributed to the public's response to legal threats. Have we reached the end of the P2P revolution? In pursuit of legitimate data to verify this hypothesis, in this paper, we embark on a more accurate measurement effort of P2P traffic at the link level. In contrast to previous efforts, we introduce two novel elements in our methodology. First, we measure traffic of all known popular P2P protocols. Second, we go beyond the "known port" limitation by reverse engineering the protocols and identifying characteristic strings in the payload. We find that, if measured accurately, P2P traffic has never declined; indeed we have never seen the proportion of P2P traffic decrease over time (any change is an increase) in any of our data sources.

Since the emergence of peer-to-peer (P2P) networking in the late '90s, P2P applications have multiplied, evolved and established themselves as the leading `growth app' of Internet traffic workload. In contrast to first-generation P2P networks which used well-defined port numbers, current P2P applications have the ability to disguise their existence through the use of arbitrary ports. As a result, reliable estimates of P2P traffic require examination of packet payload, a methodological landmine from legal, privacy, technical, logistic, and fiscal perspectives. Indeed, access to user payload is often rendered impossible by one of these factors, inhibiting trustworthy estimation of P2P traffic growth and dynamics. In this paper, we develop a systematic methodology to identify P2P flows at the transport layer, i.e., based on connection patterns of P2P networks, and without relying on packet payload. We believe our approach is the first method for characterizing P2P traffic using only knowledge of network dynamics rather than any user payload. To evaluate our methodology, we also develop a payload technique for P2P traffic identification, by reverse engineering and analyzing the nine most popular P2P protocols, and demonstrate its efficacy with the discovery of P2P protocols in our traces that were previously unknown to us. Finally, our results indicate that P2P traffic continues to grow unabatedly, contrary to reports in the popular media.

We show that the use of dynamic addressing can enable scalable routing in ad hoc networks. It is well known that the current ad hoc protocol suites do not scale to work efficiently in networks of more than a few hundred nodes. Most current ad hoc routing architectures use flat static addressing and thus, need to keep track of each node individually, creating a massive overhead problem as the network grows. Could dynamic addressing alleviate this problem? To begin to answer this question, we provide an initial design of a routing layer based on dynamic addressing, and evaluate its performance. Each node has a unique permanent identifier and a transient routing address, which indicates its location in the network at any given time. The main challenge is dynamic address allocation in the face of node mobility. We propose mechanisms to implement dynamic addressing efficiently. Our initial evaluation suggests that dynamic addressing is a promising approach for achieving scalable routing in meganode ad hoc networks.

In this work, we study and quantify the effects of hotspots in wireless cellular networks. Hotspots are caused when the bandwidth resources available at some location in the network are not enough to sustain the needs of the users, which are then blocked or dropped. A deeper understanding of hotspots can help in conducting more realistic simulations and enable improved network design. We identify some causes for the formation of hotspots and based on them, categorize hotspots into three different types: a) capacity based, b) delay based, and c) preferential mobility based. We show how these types have different effects on network performance. We also consider the effects of hotspots from various perspectives such as the number of hotspots, the placement of hotspots, etc. We also develop a fluid flow model and an analytical model to study hotspots. The fluid flow model is surprisingly simple yet effective in helping us understand hotspots and their properties. We also describe an analytical model in which we consider a cell as an M/M/B/B queue. We use these models to substantiate some of the observations from the simulations.

Since the identification of long-range dependence in network traffic ten years ago, its consistent appearance across numerous measurement studies has largely discredited Poisson-based models. However, since that original data set was collected, both link speeds and the number of Internet-connected hosts have increased by more than three orders of magnitude. Thus, we now revisit the Poisson assumption, by studying a combination of historical traces and new measurements obtained from a major backbone link belonging to a Tier 1 ISP. We show that unlike the older data sets, current network traffic can be well represented by the Poisson model for sub-second time scales. At multisecond scales, we find a distinctive piecewise-linear nonstationarity, together with evidence of long-range dependence. Combining our observations across both time scales leads to a time-dependent Poisson characterization of network traffic that, when viewed across very long time scales, exhibits the observed long-range dependence. This traffic characterization reconciliates the seemingly contradicting observations of Poisson and long-memory traffic characteristics. It also seems to be in general agreement with recent theoretical models for large-scale traffic aggregation

The robustness of the Internet relies heavily on the robustness of BGP routing. BGP is the glue that holds the Internet together: it is the common language of the routers that interconnect networks or autonomous systems (AS). The robustness of BGP and our ability to manage it effectively is hampered by the limited global knowledge and lack of coordination between autonomous systems. One of the few efforts to develop a globally analyzable and secure Internet is the creation of the Internet routing registries (IRRs). IRRs provide a voluntary detailed repository of BGP policy information. The IRR effort has not reached its full potential because of two reasons: a) extracting useful information is far from trivial, and b) its accuracy of the data is uncertain. In this paper, we develop a methodology and a tool (Nemecis) to extract and infer information from IRR and validate it against BGP routing tables. In addition, using our tool, we quantify the accuracy of the information of IRR. We find that IRR has a lot of inaccuracies, but also contains significant and unique information. Finally, we show that our tool can identify and extract the correct information from IRR discarding erroneous data. In conclusion, our methodology and tool close the gap in the IRR vision for an analyzable Internet repository at the BGP level

We focus on self-contention: contention between packets of the same transport layer connection along the path from source to destination. We observe that self-contention plays an important role in degrading TCP performance in multi-hop wireless networks and that the use of the popular IEEE 802.11 MAC protocol exacerbates self-contention. We propose and study two MAC-layer approaches to alleviate self-contention. The first approach, called quick-exchange (QE), is designed with the intent of reducing the effects of inter-flow self-contention (e.g. between packets of the same connection traveling in opposite directions). The design of our second mechanism, called fast-forward (FF), is geared towards decreasing intra-flow self-contention (e.g. between packets of the same connection traveling in the same direction). We simulate and study our proposed schemes and observe that quick-exchange consistently improves net-work aggregate goodput (by as much as 20% in string topologies, 15% in random static scenarios, and 10% in random mobile scenarios). In contrast to our expectations, fast-forward causes sporadic and often negative effects on goodput for TCP connections. Upon investigation we find that while the MAC is, in some respect, operating more efficiently, as demonstrated by improved UDP throughput; interactions with TCPs congestion control mechanism cause the goodput to degrade. We analyze various effects that cause the respective behaviors with QE and FF in detail.

Network wide broadcasting is an energy intensive function. In this paper we propose a new method that performs transmission power adaptations based on information available locally, to reduce the overall energy consumed per broadcast. In most of the prior work on energy efficient broadcasting it is assumed that the originator of the broadcast has global network information (both topology information as well as the geographical distance between nodes). This can be prohibitive in terms of the consumed overhead. In our protocol, each node attempts to tune its transmit power based on local information (of up to two hops from the transmitting node). We perform extensive simulations to evaluate our protocol. Our simulations take into account the possible loss of packets due to collision effects and the additional re-broadcasts that are necessary due to lower power transmissions. We show that our protocol achieves almost the same coverage as other non power-adaptive broadcast schemes hut with a reduction of approximately 40% in terms of the consumed power as compared to a scheme that does not adapt its power.

In this paper, we measure and model the distribution of multicast group members. Multicast research has traditionally been plagued by a lack of real data and an absence of a systematic simulation methodology. Although temporal group properties have received some attention, the location of group members has not been measured and modelled. However, the placement of members can have significant impact on the design and evaluation of multicast schemes and protocols as shown in previous studies. In our work, we identify properties of members that reflect their spatial clustering and the correlation among them (such as participation probability, and pairwise correlation). Then, we obtain values for these properties by monitoring the membership of network games and large audio-video broadcasts from IETF and NASA. Finally, we provide a comprehensive model that can generate realistic groups. We evaluate our model against the measured data with excellent results. A realistic group membership model can help us improve the effectiveness of simulations and guide the design of group-communication protocols.

We study and characterize the topology of the Internet at the autonomous system (AS) level. First, we show that the topology can be described efficiently with power laws. The elegance and simplicity of the power laws provide a novel perspective into the seemingly uncontrolled Internet structure. Second, we show that power laws have appeared consistently over the last five years. We also observe that the power laws hold even in the most recent and more complete topology with correlation coefficient above 99% for the degree-based power law. In addition, we study the evolution of the power-law exponents over the five-year interval and observe a variation for the degree-based power law of less than 10%. Thirdly, we provide relationships between the exponents and other topological metrics.

IP multicast suffers from scalability problems as the number of concurrent active multicast groups increases, since it requires a router to keep a forwarding state for every multicast tree passing through it. In QoS multicast provisioning, the problem is exacerbated, since not only the forwarding state but also the resource requirement of a multicast group must be kept at the router. To provide scalable QoS multicast support, in this paper, we propose a novel architecture, called Aggregated QoS Multicast (AQoSM). Using the concept of aggregated multicast, AQoSM can support QoS multicast scalably and efficiently in DiffServ-supported MPLS networks. In this paper, we develop the framework for the architecture and provide a feasibility check from an implementation point of view. The architecture is flexible and can be customized to the needs and the existing protocols of a domain. Our simulations indicate that the architecture performs well in several common scenarios. It achieves smaller blocking of users with strong QoS requirements because of its load balancing capability. It also achieves up to 85% reduction in state with a modest 10% of bandwidth overhead.

Over the last few years, the network community has started to make heavy use of novel concepts such as self-similarity and long-range dependence (LRD). Despite their wide use, there is still much confusion regarding the identification of such phenomena in real network traffic data. We show that estimating long-range dependence is not straightforward: there is no systematic or definitive methodology. There exist several estimating methodologies, but they can give misleading and conflicting estimates. More specifically, we arrive at several conclusions that could provide guidelines for a systematic approach to LRD. First, long-range dependence may exist, even if the estimators have different estimates of the Hurst exponent in the interval 0.5-1. Second, long-range dependence is unlikely to exist, if there are several estimators that fail to estimate the Hurst exponent. Third, we show that periodicity can obscure the analysis of a signal giving partial evidence of long-range dependence. Fourth, the Whittle estimator is the most accurate in finding the exact value when LRD exists, but it can be fooled easily by periodicity. As a case-study, we analyze real round-trip time data. We find and remove a periodic component from the signal, before we can identify long-range dependence in the remaining signal.

The fairness and throughput of TCP suffer when it is used in mobile ad hoc networks. This is because TCP wrongly attributes packet losses due to link failures (a consequence of mobility) to congestion. The resulting overall degradation of throughput especially affects connections with a large number of hops, where link failures are more likely; thus, short connections enjoy an unfair advantage. Furthermore, if the IEEE 802.11 MAC protocol is used, the problems are exacerbated due to the protocol-induced capture effect, leading to greater unfairness and a further throughput degradation. We develop a scheme, called split TCP, which separates the TCP functions of congestion control and reliable packet delivery. For any TCP connection, certain nodes along the route take up the role of being proxies for that connection. The proxies buffer packets upon receipt and administer rate control. The buffering enables dropped packets to be recovered from the most recent proxy. The rate control helps in controlling congestion on inter-proxy segments. Thus, we emulate shorter TCP connections and can thereby achieve better parallelism in the network. Simulations show that the use of proxies improves the total throughput by as much as 30% in typical scenarios and reduces unfairness significantly. In terms of an unfairness metric that we introduce, the unfairness decreases from 0.8 to 0.2 (1.0 being the maximum unfairness). We conclude that incorporating TCP proxies is beneficial in terms of improving TCP performance in ad hoc networks.

We conduct a longterm analysis of BGP routing properties, such as path stability. Our work complements previous studies that examine the BGP routing behavior at smaller time scales, such as its convergence to a routing update. We focus on properties that would reflect the BGP evolution due to growth, policy, and business reasons. We use daily snapshots of a number of BGP tables and we study the evolution of the paths for every IP-prefix advertised between two autonomous systems (source AS, destination AS, IP-prefix). In a high level, we observe that BGP routing is characterized by a) fairly robust routing with usually few dominating paths per prefix, b) routing richness in the advertised paths and c) a significant number of short lived IP-prefix advertisements.

One of the main problems of the current Internet infrastructure is its inability to provide services at consistent quality-of-service (QoS) levels. At the same time, many emerging Internet applications, such as teleeducation, and teleconferencing, require multicast protocols that will provide the necessary QoS. In this paper, we propose QoSMIC, a multicast routing protocol for the Internet, that provides QoS-sensitive paths in a scalable, resource-efficient, and flexible way. QoSMIC differs from the previous protocols in that it identifies multiple paths and selects the one that can provide the required QoS. Two other key advantages of QoSMIC are its flexibility and adaptivity. First, the distribution tree does not have to be rooted at a preselected core router. Second, we can tradeoff between efficiency metrics depending on our needs; for example, we can tradeoff routing efficiency for a reduction in the control messages. Extensive simulations show that our protocol improves the resources utilization and the end-to-end performance compared to the current protocols. Specifically, our protocol reduces the call blocking probability by a factor of six and reduces the end-to-end delay by as much as 90% compared to the PIM protocol.

Abstract We examine the extent to which statistical mobility information can increase the reliability of the service experienced by users in mobile networks. Interrupted or dropped calls are an aspect of reliability that stems from the mobility of users. An existing user can move to a cell where there are no resources available to support their call. A natural solution is the reservation of resources in multiple cells that the user is likely to move to. This scheme is calledselective reservationsand it relies on predicting the next move of the user. Recently, there has been some work on estimating the movement probabilities (also known as themobility profile) of the user. In this paper, we quantify the usefulness of the mobility profile to improve the reliability of the service perceived by the mobile users. We identify two parameters which characterize the profile:Accuracy and Focus. Accuracy expresses the probability that the host will move as we expect it to. Focus describes how well we can identify patterns in the movement of the users. In our simulations, we examine the effect of the quality of the predictions on the performance of the system. We show that Accuracy and Focus have great impact on the performance of selective reservations. We also show how flexibility in hand‐offs can help in decreasing the dropping probability, and how this can be facilitated by letting the users make a second try at moving in case it fails the first time. Copyright © 2001 John Wiley & Sons, Ltd.

IP multicast suffers from a scalability problem with the number of concurrently active multicast groups because it requires a router to keep the forwarding state for every multicast tree passing through it and the number of forwarding entries grows with the number of groups. In this paper, we propose an approach to reduce the multicast forwarding state. In our approach, multiple groups are forced to share a single delivery tree. We discuss the advantages and some implementation issues of our approach, and conclude that it is feasible and promising. We then propose metrics to quantify state reduction and analyze the bounds on state reduction of our approach. Finally, we use simulations to verify our analytical bounds and quantify the state reduction. These initial simulation results suggest that our method can reduce multicast state significantly.

In this paper, we develop a conceptual visual model for the Internet inter-domain topology. Recently, power-laws were used to describe the topology concisely. Despite their success, the power-laws do not help us visualize the topology, ie, draw the topology on paper by hand. In this paper, we deal with the following questions: can we identify a hierarchy in the Internet; how can I represent the network in an abstract graphical way? The focus of this paper is threefold. First, we characterize nodes using three metrics of topological "importance"', which we later use to identify a sense of hierarchy. Second, we identify some new topological properties. We then find that the Internet has a highly connected core and identify layers of nodes in decreasing importance surrounding the core. Finally, we show that our observations suggest an intuitive model. The topology can be seen as a jellyfish, where the core is in the middle of the cap, and one-degree nodes form its legs.

We propose a methodology to simplify the analysis of wireless network simulations. Wireless simulation models are plagued by a vast parameter space. Consequently, performance studies are not easy to interpret or compare across different models. We reduce this parameter space by proposing a set of parameters that describe the network at a higher level of abstraction.

Despite the apparent randomness of the Internet, we discover some surprisingly simple power-laws of the Internet topology. These power-laws hold for three snapshots of the Internet, between November 1997 and December 1998, despite a 45% growth of its size during that period. We show that our power-laws fit the real data very well resulting in correlation coefficients of 96% or higher.Our observations provide a novel perspective of the structure of the Internet. The power-laws describe concisely skewed distributions of graph properties such as the node outdegree. In addition, these power-laws can be used to estimate important parameters such as the average neighborhood size, and facilitate the design and the performance analysis of protocols. Furthermore, we can use them to generate and select realistic topologies for simulation purposes.

In this paper, we present, QoSMIC, a multicast protocol for the Internet that supports QoS-sensitive routing, and minimizes the importance of a priori configuration decisions (such as core selection). The protocol is resource-efficient, robust, flexible, and scalable. In addition, our protocol is provably loop-free.Our protocol starts with a resources-saving tree (Shared Tree) and individual receivers switch to a QoS-competitive tree (Source-Based Tree) when necessary. In both trees, the new destination is able to choose the most promising among several paths. An innovation is that we use dynamic routing information without relying on a link state exchange protocol to provide it. Our protocol limits the effect of pre-configuration decisions drastically, by separating the management from the data transfer functions; administrative routers are not necessarily part of the tree. This separation increases the robustness, and flexibility of the protocol. Furthermore, QoSMIC is able to adapt dynamically to the conditions of the network.The QoSMIC protocol introduces several new ideas that make it more flexible than other protocols proposed to date. In fact, many of the other protocols, (such as YAM, PIMSM, BGMP, CBT) can be seen as special cases of QoSMIC. This paper presents the motivation behind, and the design of QoSMIC, and provides both analytical and experimental results to support our claims.

Since Gallager, Humblet and Spira first introduced the distributed Minimum Spanning Tree problem, many authors have suggested ways to enhance their basic algorithm to improve its performance. Most of these improved algorithms have even been shown to be very efficient in terms of reducing their worst-case communications and/or time complexity measures. In this paper, however, we take a different approach, basing our comparisons on measurements of the actual running times, numbers of messages sent, etc., when various algorithms are run on large numbers of test networks. We also propose the Distributed Information idea, that yields several new techniques for performance improvement. Simulation results show that contrary to the theoretical analysis, some of the techniques in the literature degrade the performance. Moreover, a simple technique that we propose seems to achieve the best time and message complexity among several algorithms tested.

In an earlier paper, Awerbuch presented an innovative distributed algorithm for solving minimum spanning tree (MST) problems that achieved optimal time and message complexity through the introduction of several advanced features. In this paper, we show that there are some cases where his algorithm can create cycles or fail to achieve optimal time complexity. We then show how to modify the algorithm to avoid these problems, and demonstrate both the correctness and optimality of the revised algorithm. 1 Introduction Given an undirected graph G with N nodes and E edges, with weights assigned to each edge, we want to find a spanning tree for which the combined weight of all its edges is minimized, denoted an MST in the sequel. Furthermore, we want to use a distributed algorithm to find that MST by placing a processor at each node and treating each edge as a bidirectional and error-free communication channel, over which the nodes can exchange messages among themselves. We assume that ini...