Automated Log Analysis tasks such as root cause analysis and fault prediction play a pivotal role in maintaining the overall application health. These tasks employ log parsers to extract the dynamic (variable) and constant (template) parts of a log line to generate a template. However, our observations indicate that not all templates carry equal significance. Hence, there is a need to prioritize which templates/variables to use for log analysis. In this paper, we introduce LogMId, a Logs-based Metric Identification method, which is designed to extract critical IT metrics from logs. Through LogMId, we aim to en-hance monitoring, observability tools and in turn Site Reliability Engineers to mine better insights from log data. We showcase the effectiveness of LogMId on a popular log analysis task of anomaly detection. Our experiments indicate that integrating previously used benchmark tools with LogMId features lead to improved results. Additionally, LogMId demonstrates effectiveness even with a smaller amount of training data, emphasising its utility.

Many applications have been offloaded onto cloud environments to achieve higher agility, access to more powerful computational resources, and obtain better infrastructure management. Although cloud environments provide solid security solutions, users with highly sensitive data or regulatory compliance requirements, such as HIPAA (Health Insurance Portability and Accountability Act) and GDPR (General Data Protection Regulation), still hesitate to move such application domains to the cloud. To address these concerns, cloud service providers have started to offer solutions to protect data confidentiality and integrity through trusted execution environments (TEEs). While so far these were limited to CPU TEEs only, NVIDIA's Hopper architecture has shifted the landscape by enabling confidential computing features essential to protecting confidentiality and integrity for real-world applications offloaded to GPUs, such as large language models (LLMs). However, there lacks a sufficient study on how much performance overhead confidential computing introduces in a TEE comprised of a CPU-GPU configuration. In this paper we evaluate a confidential computing environment comprised of an Intel TDX system and NVIDIA H100 GPUs through various micro benchmarks and real workloads including BERT, LLaMA, and Granite large language models and provide discussions on the overhead incurred by confidential computing when GPUs are utilized. We show that while LLMs are sensitive to the model types and batch sizes, when larger models with pipelined processing are deployed, the performance of LLM inference in CPU-GPU TEEs can be close to par with their non-confidential setups.

Mixture of Expert (MoE) models consist of several experts, each specializing in a specific task. During inference, a subset of the experts is invoked based on their relevance to the request. MoE's modular architecture lets users compose their model from popular off-the-shelf experts. This leads to multiple MoE deployments with identical experts. The duplication of experts across model instances results in excessive GPU memory consumption and increased model serving cost. Moreover, since all experts are not invoked for each request, individual experts rarely receive enough requests to exploit the GPUs' computational capabilities, resulting in low GPU utilization. To address these problems, we propose Shared Mixture of Experts in MoEsaic. MoEsaic automatically identifies and deduplicates identical experts across model instances, thus reducing their memory footprint. Moreover, it batches the requests directed toward the identical experts belonging to different clients, which also improves the processing efficiency. We show that for Mixtral-8x7B model, when compared to deploying dedicated MoE instances, MoEsaic can serve 7X more model instances with little impact on inference performance.

This paper introduces SudokuSens, a generative framework for automated generation of training data in machine-learning-based Internet-of-Things (IoT) applications, such that the generated synthetic data mimic experimental configurations not encountered during actual sensor data collection. The framework improves the robustness of resulting deep learning models, and is intended for IoT applications where data collection is expensive. The work is motivated by the fact that IoT time-series data entangle the signatures of observed objects with the confounding intrinsic properties of the surrounding environment and the dynamic environmental disturbances experienced. To incorporate sufficient diversity into the IoT training data, one therefore needs to consider a combinatorial explosion of training cases that are multiplicative in the number of objects considered and the possible environmental conditions in which such objects may be encountered. Our framework substantially reduces these multiplicative training needs. To decouple object signatures from environmental conditions, we employ a Conditional Variational Autoencoder (CVAE) that allows us to reduce data collection needs from multiplicative to (nearly) linear, while synthetically generating (data for) the missing conditions. To obtain robustness with respect to dynamic disturbances, a session-aware temporal contrastive learning approach is taken. Integrating the aforementioned two approaches, SudokuSens significantly improves the robustness of deep learning for IoT applications. We explore the degree to which SudokuSens benefits downstream inference tasks in different data sets and discuss conditions under which the approach is particularly effective.

Foundational models have caused a paradigm shift in the way artificial intelligence (AI) systems are built. They have had a major impact in natural language processing (NLP), and several other domains, not only reducing the amount of required labeled data or even eliminating the need for it, but also significantly improving performance on a wide range of tasks. We argue foundation models can have a similar profound impact on network traffic analysis, and management. More specifically, we show that network data shares several of the properties that are behind the success of foundational models in linguistics. For example, network data contains rich semantic content, and several of the networking tasks (e.g., traffic classification, generation of protocol implementations from specification text, anomaly detection) can find similar counterparts in NLP (e.g., sentiment analysis, translation from natural language to code, out-of-distribution). However, network settings also present unique characteristics and challenges that must be overcome. Our contribution is in highlighting the opportunities and challenges at the intersection of foundation models and networking.

Recent years have seen the increasing attention and popularity of federated learning (FL), a distributed learning framework for privacy and data security. However, by its fundamental design, federated learning is inherently vulnerable to model poisoning attacks: a malicious client may submit the local updates to influence the weights of the global model. Therefore, detecting malicious clients against model poisoning attacks in federated learning is useful in safety-critical tasks.However, existing methods either fail to analyze potential malicious data or are computationally restrictive. To overcome these weaknesses, we propose a robust federated learning method where the central server learns a supervised anomaly detector using adversarial data generated from a variety of state-of-the-art poisoning attacks. The key idea of this powerful anomaly detector lies in a comprehensive understanding of the benign update through distinguishing it from the diverse malicious ones. The anomaly detector would then be leveraged in the process of federated learning to automate the removal of malicious updates (even from unforeseen attacks).Through extensive experiments, we demonstrate its effectiveness against backdoor attacks, where the attackers inject adversarial triggers such that the global model will make incorrect predictions on the poisoned samples. We have verified that our method can achieve 99.0% detection AUC scores while enjoying longevity as the model converges. Our method has also shown significant advantages over existing robust federated learning methods in all settings. Furthermore, our method can be easily generalized to incorporate newly-developed poisoning attacks, thus accommodating ever-changing adversarial learning environments.

The papers in this special section focus on secure and emerging collaborative computing and intelligent systems. The Internet, coupled with recent advances in computing and information technologies, such as IoT, mobile edge/ cloud computing, cyber-physical-social systems, and artificial intelligence/machine learning/deep learning, have paved the way for creating next-generation smart and intelligent systems and applications that can have transformative impact in our society while accelerating rapid scientific discoveries and innovations. Unprecedented cyber-social and cyber-physical infrastructures and systems that span geographic boundaries are possible because of the Internet and the growing number of collaboration-enabling technologies. With newer technologies and paradigms getting increasingly embedded in the computing platforms and networked information systems/ infrastructures that form the digital foundation for our personal, organizational, and social processes and activities, it is increasingly becoming critical that the trust, privacy, and security issues in such digital environments are holistically addressed to ensure the safety and well-being of individuals as well as our society.

Reinforcement Learning (RL) based methods have seen their paramount successes in solving serial decision-making and control problems in recent years. For conventional RL formulations, Markov Decision Process (MDP) and state-action-value function are the basis for the problem modeling and policy evaluation. However, several challenging issues still remain. Among most cited issues, the inefficiency in utilizing training data is an important factor that causes difficulties in accurately approximating the state-action-value function. We observe that although actions directly define the agents' behaviors, for many problems the next state after a state transition matters more than the action taken, in determining the return of such a state transition. In this regard, we propose a new learning paradigm, State Action Separable Reinforcement Learning (sasRL), wherein the action space is decoupled from the value function learning process for higher learning efficiency. Then, a light-weight transition model is learned to assist the agent to determine the action that triggers the associated state transition. Our convergence analysis reveals that under certain conditions, the convergence time of sasRL is O(T1/k), where T is the convergence time for updating the value function in the MDP-based formulation and k is a weighting factor. Experiments on several gaming scenarios show that sasRL outperforms state-of-the-art MDP-based RL algorithms by up to 75%.

Edge devices use neural network models learnt on cloud to predict labels of its data records, which may lead to incorrect predictions especially for records that are different from the data involved in the training process, i.e., out-of-distribution (OOD) records. However, recent efforts in OOD detection either require the retraining of the model or assume the existence of a certain amount of OOD records, thus limiting their application in practice. In this work, we propose a novel OOD detection method (named as NeuralFP) without requiring any access to OOD records, which constructs non-linear fingerprints of neural network models memorizing the information of data observed during training. The key idea of NeuralFP is to exploit the difference in how the neural network model responds to data records in its training set versus data records that are anomalous. Specifically, NeuralFP builds autoencoders for each layer of the neural network model and then carefully analyzes the error distribution of the autocoders in reconstructing the training set to identify OOD records. Through extensive experiments on multiple real-world datasets, we show the effectiveness of NeuralFP in detecting OOD records as well as its advantages over previous approaches. Furthermore, we provide useful guidelines for parameter selection in the practical adoption of NeuralFP.

While observing complex events with multiple actors, humans do not assess each actor separately, but infer from the context. The surrounding context provides essential information for understanding actions. To this end, we propose to replace region of interest(RoI) pooling with an attention module, which ranks each spatio-temporal region's relevance to a detected actor instead of cropping. We refer to these as Actor-Conditioned Attention Maps (ACAM), which amplify/dampen the features extracted from the entire scene. The resulting actor-conditioned features focus the model on regions that are relevant to the conditioned actor. For actor localization, we leverage pre-trained object detectors, which transfer better. The proposed model is efficient and our action detection pipeline achieves near real-time performance. Experimental results on AVA 2.1 and JHMDB demonstrate the effectiveness of attention maps, with improvements of 7 mAP on AVA and 4 mAP on JHMDB.

Effectively representing graph node sequences in the form of vector embeddings is critical to many applications. We achieve this by (i) first learning vector embeddings of single graph nodes and (ii) then composing them to compactly represent node sequences. Specifically, we propose SENSE-S (Semantically Enhanced Node Sequence Embedding - for Single nodes), a skip-gram based novel embedding mechanism, for single graph nodes that co-learns graph structure as well as their textual descriptions. We demonstrate that SENSE-S vectors increase the accuracy of multi-label classification tasks by up to 50% and link-prediction tasks by up to 78% under a variety of scenarios using real datasets. Based on SENSE-S, we next propose generic SENSE to compute composite vectors that represent a sequence of nodes, where preserving the node order is important. We prove that this approach is efficient in embedding node sequences, and our experiments on real data confirm its high accuracy.

Cyber phyiscal systems are increasingly connected to the Internet for reasons of convenience and efficiency. However, such cyber-physical systems are exposed to new vulnerabilities since they may be compromised by an attack from the Internet. In addition to traditional network security mechanisms, such systems need additional mechanism which can prevent the exploitation of their physical vulnerabilities. We propose an architecture in which the behavior of the system can be controlled by having it generate the policies for its own protection automatically.

Despite its remarkable success, deep learning currently typically operates as a black-box. Instead, can models produce explicit reasons to explain their decisions? To address that question, we propose to exploit probabilistic graphical models which are declarative representations of our understanding of the world (e.g., what the relevant variables are, and how they interact with each other), and are commonly used to perform causal inference. More specifically, we propose a novel architecture called Deep Explainable Bayesian Networks whose main idea consists in concatenating a deep network with a Bayesian network, and to rely on the latter one to provide the explanations. We conduct extensive experiments on classical image, and text classification tasks. First, the results show that deep explainable Bayesian networks can achieve comparable accuracy than models that are trained on the same datasets but without producing explanations. Second, the experiments show promising results: The average accuracy of the explanation ranges from 68.3% to 84.8%.

Expert networks are formed by a group of expert-professionals with different specialties to collaboratively resolve specific queries posted to the network. In such networks, when a query reaches an expert who does not have sufficient expertise, this query needs to be routed to other experts for further processing until it is completely solved; therefore, query answering efficiency is sensitive to the underlying query routing mechanism being used. Among all possible query routing mechanisms, decentralized search, operating purely on each expert’s local information without any knowledge of network global structure, represents the most basic and scalable routing mechanism, which is applicable to any network scenarios even in dynamic networks. However, there is still a lack of fundamental understanding of the efficiency of decentralized search in expert networks. In this regard, we investigate decentralized search by quantifying its performance under a variety of network settings. Our key findings reveal the existence of network conditions, under which decentralized search can achieve significantly short query routing paths (i.e., between O (log n ) and O (log 2 n ) hops, n : total number of experts in the network). Based on such theoretical foundation, we further study how the unique properties of decentralized search in expert networks are related to the anecdotal small-world phenomenon. In addition, we demonstrate that decentralized search is robust against estimation errors introduced by misinterpreting the required expertise levels. The developed performance bounds, confirmed by real datasets, are able to assist in predicting network performance and designing complex expert networks.

With the widespread use of GPS-equipped smartphones and Internet of Things devices, a huge amount of data with location information is being generated at an unprecedented rate. To gain a deeper insight into such a plethora of spatial data, scientists and engineers are widely using spatial queries for their big data applications. However, because of not only the massive spatial data size but also the complexity of spatial query processing, they are struggling to efficiently process the spatial queries. In this paper, we propose lightweight and scalable indexing and querying services for big spatial data stored in distributed storage systems or graph-based systems. Our spatial services have several advantages over existing approaches. First, our services can be easily applied to existing storage systems or graph-based models without modifying the internal implementation of existing systems/models. Second, our services achieve high pruning power by efficiently selecting only relevant spatial objects based on a simple yet effective filter. Third, our services support a customizable and easy-to-use control of index data size by adjusting the precision of indexed geometries. Lastly, our services support efficient updates of spatial data. Our experimental results using real-world datasets validate the effectiveness and efficiency of our spatial services.

Privacy becomes one of the important issues in data-driven applications. The advent of non-PC devices such as Internet-of-Things (IoT) devices for data-driven applications leads to needs for light-weight data anonymization. In this paper, we develop an anonymization framework that expedites model learning in parallel and generates deployable models for devices with low computing capability. We evaluate our framework with various settings such as different data schema and characteristics. Our results exhibit that our framework learns anonymization models up to 16 times faster than a sequential anonymization approach and that it preserves enough information in anonymized data for data-driven applications.

Managing large-scale distributed systems is a difficult task. System administrators are responsible for the upkeep and maintenance of numerous components with complex dependencies. With the shift to microservices-based architectures, these systems can consist of 100s to 1000s of interconnected nodes. To combat this difficulty, administrators rely on analyzing logs and metrics collected from the different services. However, the number of available metrics for large systems presents complexity and scaling issues. To combat these issues, we present Minerva, an unsupervised Machine Learning (ML) framework for performing network diagnosis analysis. Minerva is composed of a multi-stage pipeline, where each component can act individually or cohesively to perform various management tasks. Our system offers a unified and extensible framework for managing the complexity of large networks, and presents administrators with a swiss-army knife for diagnosing the overall health of their systems. To demonstrate the feasibility of Minerva, we evaluate its performance on a production-scale system. We present use cases for the various management tools made available by Minerva, and show how these tools can be used to make strong inferences about the system using unsupervised techniques.

Vector space representations of text have increased in popularity and are used in various text classification problems. We present Doc2Img, a new approach to create document vectors that improves upon existing approaches such as Word2Vec and Doc2Vec in capturing similarities between words within a document and the differences across documents. We apply this new vector space representation to the problem of deriving the sensor requirements of apps (for smartphones and IoT devices) by learning a classification model using document vectors. We show that this learned model outperforms existing vector space representations (Word2Vec and Doc2Vec) by more than 10%. Further, this model can predict with an average accuracy of 75% and greater than 85% on the top-20 sensor requirements for 300 different applications.

Recent advances in computing infrastructure constitute edge nodes prominently (e.g., smartphones, cars) in their computation pipeline. Applications that combine sensor/IoT data from edge devices in a distributed fashion are growing. Dynamically composed applications that combine resources from edge nodes and the cloud are becoming common in various domains including urban and military settings. A key challenge in such applications is to bridge the gap between the application's description and its IoT resource requirements, where the application description is unstructured text and its IoT requirements are structured. In this paper, we describe an approach that develops a model which given unstructured text description of the service predicts its IoT sensor requirements. Our model can predict with an average accuracy of 77% and up to 88% on the top-20 sensor requirements for 300 different applications.

This paper presents improved results on classifying electroencephalography (EEG) recordings using deep learning. The task is to classify movements that the subject is thinking about (motor imagery), using only the recorded electrical activities on the scalp. The challenges are: poor signal-to-noise ratio; interference from numerous sources such as electrical line noise, muscle activity, and eye movements; considerable variability between individuals and even recording sessions. Traditional signal processing techniques such as frequency band analysis, common spatial pattern (CSP) algorithm or independent component analysis (ICA) fall short due to their limited capacity. Thanks to the rise of big data in healthcare, medical recordings now come in abundance. Therefore deep learning which relies on large amounts of training data is becoming the new cutting edge tool. We present a significant improvement of classification accuracy on the Brain-Computer Interfaces Competition IV dataset (2a), and compare the results of various state of the art neural network structures.

Trajectory clustering techniques help discover interesting insights from moving object data, including common routes for people and vehicles, anomalous sub-trajectories, etc. Existing trajectory clustering techniques fail to take in to account the uncertainty present in location data. In this paper, we investigate the problem of clustering trajectory data and propose a novel algorithm for clustering similar full and sub-trajectories together while modeling uncertainty in this data. We describe the necessary pre-processing techniques for clustering trajectory data, namely techniques to discretize raw location data using Possible World semantics to capture the inherent uncertainty in location data, and to segment full trajectories in to meaningful sub-trajectories. As a baseline, we extend the well known K-means algorithm to cluster trajectory data. We then describe and evaluate a new trajectory clustering algorithm, SOM-TC (Self-Organizing Map Based Trajectory Clustering), that is inspired from the self-organizing map technique and is at least 4x faster than the baseline K-means and current density based clustering approaches.

Emerging distributed in-memory computing frameworks, such as Apache Spark, can process a huge amount of cached data within seconds. This remarkably high efficiency requires the system to well balance data across tasks and ensure data locality. However, it is challenging to satisfy these requirements for applications that operate on a collection of dynamically loaded and evicted datasets. The dynamics may lead to time-varying data volume and distribution, which would frequently invoke expensive data re-partition and transfer operations, resulting in high overhead and large delay. To address this problem, we present Stark, a system specifically designed for optimizing in-memory computing on dynamic dataset collections. Stark enforces data locality for transformations spanning multiple datasets (e.g., join and cogroup) to avoid unnecessary data replications and shuffles. Moreover, to accommodate fluctuating data volume and skeweddata distribution, Stark delivers elasticity into partitions to balance task execution time andreduce job makespan. Finally, Stark achieves bounded failure recovery latency byoptimizing the data checkpointing strategy. Evaluations on a 50-server cluster show that Stark reduces the job makespan by 4X and improves system throughput by 6X compared to Spark.

Location data collection at a societal scale is increasingly becoming common - examples of this are call and data detail records in telecommunication companies, GPS samples collected by car companies, and GPS samples from mobile devices in mapping companies (e.g., Google, Microsoft). Such large scale mobility datasets have applications in urban planning, network planning, surveillance, and real-time traffic estimations. This paper addresses the problem of subsampling location traces while preserving the amount of information present in such datasets. We present a novel subsampling technique that is based on a hierarchical geographical encoding mechanism (geohash), that allows for efficient spatial cluster sampling. We analyze this subsampling technique through various information theoretic measures to quantify the total "amount" of information in a dataset from a location trace perspective and evaluate these metrics in the context of two large scale mobility datasets from telecommunication companies - one is that of call detail records and the second is that of data detail records. We show that subsampling data in both these cases by as much as 75% does not significantly reduce the total amount of information, i.e. the dataset can be used similar to the original version. This paves way for the creation of better space and CPU efficient models that can support various applications reliant on collective location traces.

When modeling geo-spatial data, it is critical to capture spatial correlations for achieving high accuracy. Spatial Auto-Regression (SAR) is a common tool used to model such data, where the spatial contiguity matrix (W) encodes thespatial correlations. However, the efficacy of SAR is limited by two factors. First, it depends on the choice of contiguity matrix, which is typically not learnt from data, but instead, is assumed to be known apriori. Second, it assumes that the observations can be explained by linear models. In this paper, we propose a Convolutional Neural Network (CNN) framework to model geo-spatial data (specifically housing prices), to learn the spatial correlations automatically. We show that neighborhood information embedded in satellite imagery can be leveraged to achieve the desired spatial smoothing. An additional upside of our framework is the relaxation of linear assumption on the data. Specific challenges we tackle while implementing our framework include, (i) how much of the neighborhood is relevant while estimating housing prices? (ii) what is the right approach to capture multiple resolutions of satellite imagery? and (iii) what other data-sources can help improve the estimation of spatial correlations? We demonstrate a marked improvement of 57% on top of the SAR baseline through the use of features from deep neural networks for the cities of London, Birmingham and Liverpool.

Expert networks are formed by a group of expert-profes\-sionals with different specialties to collaboratively resolve specific queries. In such networks, when a query reaches an expert who does not have sufficient expertise, this query needs to be routed to other experts for further processing until it is completely solved; therefore, query answering efficiency is sensitive to the underlying query routing mechanism being used. Among all possible query routing mechanisms, decentralized search, operating purely on each expert's local information without any knowledge of network global structure, represents the most basic and scalable routing mechanism. However, there is still a lack of fundamental understanding of the efficiency of decentralized search in expert networks. In this regard, we investigate decentralized search by quantifying its performance under a variety of network settings. Our key findings reveal the existence of network conditions, under which decentralized search can achieve significantly short query routing paths (i.e., between O(log n) and O(log2 n) hops, n: total number of experts in the network). Based on such theoretical foundation, we then study how the unique properties of decentralized search in expert networks is related to the anecdotal small-world phenomenon. To the best of our knowledge, this is the first work studying fundamental behaviors of decentralized search in expert networks. The developed performance bounds, confirmed by real datasets, can assist in predicting network performance and designing complex expert networks.

We present a semi-automated framework for constructing factoid question answering (QA) datasets, where an array of question characteristics are formalized, including structure complexity, function, commonness, answer cardinality, and paraphrasing.Instead of collecting questions and manually characterizing them, we employ a reverse procedure, first generating a kind of graph-structured logical forms from a knowledge base, and then converting them into questions.Our work is the first to generate questions with explicitly specified characteristics for QA evaluation.We construct a new QA dataset with over 5,000 logical form-question pairs, associated with answers from the knowledge base, and show that datasets constructed in this way enable finegrained analyses of QA systems.The dataset can be found in https://github.com/ysu1989/GraphQuestions.

In this work, we show the possibility of inferring the answer type before solving a factoid question and leveraging the type information to improve semantic parsing.By replacing the topic entity in a question with its type, we are able to generate an abstract form of the question, whose answer corresponds to the answer type of the original question.A bidirectional LSTM model is built to train over the abstract form of questions and infer their answer types.It is also observed that if we convert a question into a statement form, our LSTM model achieves better accuracy.Using the predicted type information to rerank the logical forms returned by AgendaIL, one of the leading semantic parsers, we are able to improve the F1-score from 49.7% to 52.6% on the WE-BQUESTIONS data.

As location sensing devices are becoming ubiquitous, overwhelming amounts of data are being produced by the Internet-of-Things-That-Move. Though analyzing this data presents significant business opportunities, new techniques are needed to attain adequate levels of processing performance. One example is the recently introduced geohash geographical coordinate system that is mainly used for indexing. While geohash codes provide useful inherent properties such as hierarchical and variable-precision coding, traditional spatial algorithms operate on data represented using the conventional latitude/longitude geographical coordinate system, and as such do not take advantage of geohash coding. This paper tackles the evaluation of spatial predicates on geometries defined in the geohash domain, as an alternative to the standard Dimensionally Extended Nine-Intersection Model (DE-9IM). We present the first hardware architecture to efficiently evaluate "contain" and "touch" (internal, external, corner) relations between streams of pairs of geohash codes, in a high throughput (no stall) fashion. Employing FPGAs for exploiting the bit-level granularity of geohash codes, experimental results show (end-to-end) speedup of more than 20× and 90× over highly optimized single-threaded DE-9IM implementations of the contain and touch predicates, respectively. Furthermore, the PCIe-bound FPGA-based solution outperforms a geohash-based multithreaded CPU implementation by ≈1.8× (touch predicate) while using minimal FPGA resources.

Expert networks are formed by a group of expert-professionals with different specialties to collaboratively resolve specific queries posted to the network. In expert networks, decentralized search, operating purely on each expert's local information without any knowledge of network global structure, represents the most basic and scalable routing mechanism. However, there is still a lack of fundamental understanding of the efficiency of decentralized search. In this regard, we investigate decentralized search by quantifying its performance under a variety of network settings. Our key findings reveal that under certain network conditions, decentralized search can achieve significantly small query routing steps (i.e., between O(log n) and O(log2n), n: total number of experts in the network). To the best of our knowledge, this is the first work studying fundamental behaviors of decentralized search in expert networks.

We investigate the problem of query answering in expert networks, which are composed of inter-connected experts with various specialties. Upon receiving a query, the expert network is tasked to route this query to experts with sufficient expertise in a timely and reliable manner. However, the efficiency of query answering depends on the underlying query routing protocol being used. Among all possible query routing protocols, decentralized search, operating purely on each expert's local information without any network global knowledge, represents the most basic and scalable routing protocol. However, there is still a lack of fundamental understanding on the efficiency of decentralized search in different expert networks. In this regard, we establish a generic model that can abstract diversified social and structural attributes in various expert networks into a common framework, thus applicable to a wide range of network scenarios. On top of such generic network model, we then study decentralized search by quantifying its performance under a variety of network parameters. Our key findings reveal the existence of network conditions, under which decentralized search can achieve significantly short query routing paths (i.e., between O(log n) and O(log2n) hops, n: total number of experts in the network). To the best of our knowledge, this is the first work studying fundamental behaviors of decentralized search without relying on strict underlying network structures in expert networks. Experiments in both synthetic and real expert networks confirm the efficacy of the developed performance bounds in understanding and reasoning the network performance.

IoT enabled smart environments are expected to proliferate significantly in the near future, particularly in the context of monitoring services for wellness living, patient healthcare and elderly care. Timely maintenance of failed sensors is of critical importance in such deployments to ensure minimal disruption to monitoring services. However, maintenance of large and geographically spread deployments can be a significant challenge. We present Idea that significantly increases the vtime-before-repair for a smart home deployment, thereby reducing the maintenance overhead. Specifically, our approach leverages the facts that (a) there is inherent sensor redundancy when combinations of sensors monitor activities of daily living (ADLs) in smart environments, and (b) the impact of each sensor failure depends on the activities being monitored and the functional redundancy afforded by rest of the heterogeneous sensors available for detecting the activities. Consequently, Idea identifies homes that need to be fixed based on expected degradation in ADL detection performance, and optimizes maintenance scheduling accordingly. We demonstrate that our approach leads to 3--40 times fewer maintenance personnel than a scheme in which failed sensors are fixed without considering their impact.

Collaborative networks are common in real life, where domain experts work together to solve tasks issued by customers. How to model the proficiency of experts is critical for us to understand and optimize collaborative networks. Traditional expertise models, such as topic model based methods, cannot capture two aspects of human expertise simultaneously: Specialization (what area an expert is good at?) and Proficiency Level (to what degree?). In this paper, we propose new models to overcome this problem. We embed all historical task data in a lower dimension space and learn vector representations of expertise based on both solved and unsolved tasks. Specifically, in our first model, we assume that each expert will only handle tasks whose difficulty level just matches his/her proficiency level, while experts in the second model accept tasks whose levels are equal to or lower than his/her proficiency level. Experiments on real world datasets show that both models outperform topic model based approaches and standard classifiers such as logistic regression and support vector machine in terms of prediction accuracy. The learnt vector representations can be used to compare expertise in a large organization and optimize expert allocation.

When people utilize social applications and services, their privacy suffers a potential serious threat. In this article, we present a novel, robust, and effective de-anonymization attack to mobility trace data and social data. First, we design a Unified Similarity (US) measurement, which takes account of local and global structural characteristics of data, information obtained from auxiliary data, and knowledge inherited from ongoing de-anonymization results. By analyzing the measurement on real datasets, we find that some data can potentially be de-anonymized accurately and the other can be de-anonymized in a coarse granularity. Utilizing this property, we present a US-based De-Anonymization (DA) framework, which iteratively de-anonymizes data with accuracy guarantee. Then, to de-anonymize large-scale data without knowledge of the overlap size between the anonymized data and the auxiliary data, we generalize DA to an Adaptive De-Anonymization (ADA) framework. By smartly working on two core matching subgraphs , ADA achieves high de-anonymization accuracy and reduces computational overhead. Finally, we examine the presented de-anonymization attack on three well-known mobility traces: St Andrews, Infocom06, and Smallblue, and three social datasets: ArnetMiner, Google+, and Facebook. The experimental results demonstrate that the presented de-anonymization framework is very effective and robust to noise. The source code and employed datasets are now publicly available at SecGraph [2015].

In this paper, we study the quantification, practice, and implications of structural data de-anonymization, including social data, mobility traces, and so on. First, we answer several open questions in structural data de-anonymization by quantifying perfect and (1 - ε)-perfect structural data de-anonymization, where ε is the error tolerated by a de-anonymization scheme. To the best of our knowledge, this is the first work on quantifying structural data de-anonymization under a general data model, which closes the gap between the structural data de-anonymization practice and theory. Second, we conduct the first large-scale study on the de-anonymizability of 26 real world structural data sets, including social networks, collaborations networks, communication networks, autonomous systems, peer-to-peer networks, and so on. We also quantitatively show the perfect and (1 - ε)-perfect de-anonymization conditions of the 26 data sets. Third, following our quantification, we present a practical attack [a novel single-phase cold start optimization-based de-anonymization (ODA) algorithm]. An experimental analysis of ODA shows that ~77.7%-83.3% of the users in Gowalla (196 591 users and 950 327 edges) and 86.9%-95.5% of the users in Google+ (4692 671 users and 90751 480 edges) are de-anonymizable in different scenarios, which implies that the structure-based de-anonymization is powerful in practice. Finally, we discuss the implications of our de-anonymization quantification and our ODA attack and provide some general suggestions for future secure data publishing.

Choosing a hard-to-guess secret is a prerequisite in many security applications. Whether it is a password for user authentication or a secret key for a cryptographic primitive, picking it requires the user to trade-off usability costs with resistance against an adversary: a simple password is easier to remember but is also easier to guess, likewise, a shorter cryptographic key may require fewer computational and storage resources but it is also easier to attack. A fundamental question is how one can optimally resolve this trade-off. A big challenge is the fact that an adversary can also utilize the knowledge of such usability vs. security trade-offs to strengthen its attack. In this paper, we propose a game-theoretic framework for analyzing the optimal trade-offs in the face of strategic adversaries. We consider two types of adversaries: those limited in their number of tries, and those that are ruled by the cost of making individual guesses. For each type, we derive the mutually-optimal decisions as Nash Equilibria, the strategically pessimistic decisions as maximin, and optimal commitments as Strong Stackelberg Equilibria of the game. We establish that when the adversaries are faced with a capped number of guesses, the user's optimal trade-off is a uniform randomization over a subset of the secret domain. On the other hand, when the attacker strategy is ruled by the cost of making individual guesses, Nash Equilibria may completely fail to provide the user with any level of security, signifying the crucial role of credible commitment for such cases. We illustrate our results using numerical examples based on real-world samples and discuss some policy implications of our work.

Insights extracted from spatial queries in geodatabase systems introduce significant opportunities for business intelligence. However, geodatabases are unable to keep up with the required performance due to the massive (and sky-rocketing) amounts of data generated from embedded location-enabled devices. In this paper, we focus on geographic information systems that make use of geohash, specifically, we tackle the kernel of converting geohash codes to and from longitude/latitude pairs. We present the first hardware implementation of a geohash conversion engine operating at wire speed. The presented geohash converter is further enhanced with runtime flexibility with respect to characteristics of the data it can process, furthermore, the architecture allows the user to compromise on performance when limited by hardware resources (design time flexibility). Experimental results of the geohash conversion engine on a Xilinx XC7K325T FPGA show >13X (end-to-end) speedup compared to optimized industry-grade software running on 16 CPU hardware threads.

Recent advances in the manufacturing and commercialization of passive optical components are now extending the capabilities of fiber to edge and campus networks. This paper presents a comparison between Passive Optical LAN (POL) and copper-based LAN solution, and demonstrate the benefits of PON such as reduced infrastructure footprint and cost, reduced power requirements, future-proof bandwidth, greener infrastructure, safer, higher security and higher reliability.

The big data era is witnessing a prevalent shift of data from homogeneous to heterogeneous, from isolated to linked. Exemplar outcomes of this shift are a wide range of graph data such as information, social, and knowledge graphs. The unique characteristics of graph data are challenging traditional search techniques like SQL and keyword search. Graph query is emerging as a promising complementary search form. In this paper, we study how to improve graph query by relevance feedback. Specifically, we focus on knowledge graph query, and formulate the graph relevance feedback (GRF) problem. We propose a general GRF framework that is able to (1) tune the original ranking function based on user feedback and (2) further enrich the query itself by mining new features from user feedback. As a consequence, a query-specific ranking function is generated, which is better aligned with the user search intent. Given a newly learned ranking function based on user feedback, we further investigate whether we shall re-rank the existing answers, or choose to search from scratch. We propose a strategy to train a binary classifier to predict which action will be more beneficial for a given query. The GRF framework is applied to searching DBpedia with graph queries derived from YAGO and Wikipedia. Experiment results show that GRF can improve the mean average precision by 80% to 100%.

In collaborative environments, members may try to acquire similar information on the web in order to gain knowledge in one domain. For example, in a company several departments may successively need to buy business intelligence software and employees from these departments may have studied online about different business intelligence tools and their features independently. It will be productive to get them connected and share learned knowledge. We investigate fine-grained knowledge sharing in collaborative environments. We propose to analyze members' web surfing data to summarize the fine-grained knowledge acquired by them. A two-step framework is proposed for mining fine-grained knowledge: (1) web surfing data is clustered into tasks by a nonparametric generative model; (2) a novel discriminative infinite Hidden Markov Model is developed to mine fine-grained aspects in each task. Finally, the classic expert search method is applied to the mined results to find proper members for knowledge sharing. Experiments on web surfing data collected from our lab at UCSB and IBM show that the fine-grained aspect mining framework works as expected and outperforms baselines. When it is integrated with expert search, the search accuracy improves significantly, in comparison with applying the classic expert search method directly on web surfing data.

In this paper, we study the quantification, practice, and implications of structural data (e.g., social data, mobility traces) De-Anonymization (DA). First, we address several open problems in structural data DA by quantifying perfect and (1-ε)-perfect structural data DA}, where ε is the error tolerated by a DA scheme. To the best of our knowledge, this is the first work on quantifying structural data DA under a general data model, which closes the gap between structural data DA practice and theory. Second, we conduct the first large-scale study on the de-anonymizability of 26 real world structural datasets, including Social Networks (SNs), Collaborations Networks, Communication Networks, Autonomous Systems, and Peer-to-Peer networks. We also quantitatively show the conditions for perfect and (1-ε)-perfect DA of the 26 datasets. Third, following our quantification, we design a practical and novel single-phase cold start Optimization based DA} (ODA) algorithm. Experimental analysis of ODA shows that about 77.7% - 83.3% of the users in Gowalla (.2M users and 1M edges) and 86.9% - 95.5% of the users in Google+ (4.7M users and 90.8M edges) are de-anonymizable in different scenarios, which implies optimization based DA is implementable and powerful in practice. Finally, we discuss the implications of our DA quantification and ODA and provide some general suggestions for future secure data publishing.

This paper complements the large body of social sensing literature by developing means for augmenting sensing data with inference results that "fill-in" missing pieces. Unlike trend-extrapolation methods, we focus on prediction in disaster scenarios where disruptive trend changes occur. A set of prediction heuristics (and a standard trend extrapolation algorithm) are compared that use either predominantly-spatial or predominantly-temporal correlations for data extrapolation purposes. The evaluation shows that none of them do well consistently. This is because monitored system state, in the aftermath of disasters, alternates between periods of relative calm and periods of disruptive change (e.g., aftershocks). A good prediction algorithm, therefore, needs to intelligently combine time-based data extrapolation during periods of calm, and spatial data extrapolation during periods of change. The paper develops such an algorithm. The algorithm is tested using data collected during the New York City crisis in the aftermath of Hurricane Sandy in November 2012. Results show that consistently good predictions are achieved. The work is unique in addressing the bi-modal nature of damage propagation in complex systems subjected to stress, and offers a simple solution to the problem.

Spatial queries are widely used in many data mining and analytics applications. However, a huge and growing size of spatial data makes it challenging to process the spatial queries efficiently. In this paper we present a lightweight and scalable spatial index for big data stored in distributed storage systems. Experimental results show the efficiency and effectiveness of our spatial indexing technique for different spatial queries.

The proliferation of location sensors has resulted in the wide availability of historical location and time data. A prominent use of such data is to develop models to estimate travel-times (between arbitrary points in a city) accurately. The problem of travel-time estimation/prediction has been well studied in the past, where the proposed techniques span a spectrum of statistical methods, such as k-nearest neighbors, Gaussian regression, Artificial Neural Networks, and Support Vector Machines. In this paper, we demonstrate that, contrary to popular intuition, empirical data suggests that simple travel time predictors come very close to the fundamental error bounds achievable in delay prediction. We derive such bounds by estimating entropy that remains in travel time distributions, even after all spatio-temporal delay-influencing factors have been accounted for. Our results are based on analysis of cab traces from New York City, that feature 15 million trips. While we cannot claim generalizability to other cities, the results suggest the diminishing return of complex travel-time predictors due to the inherent nature of uncertainty in trip delays. We demonstrate a simple travel-time predictor, whose error approaches the uncertainty bound. It predicts delay based only on total distance traveled and time-of-day and is close to the optimal solution.

Fast service placement, finding a set of nodes with enough free capacity of computation, storage, and network connectivity, is a routine task in daily cloud administration. In this work, we formulate this as a subgraph matching problem. Different from the traditional setting, including approximate and probabilistic graphs, subgraph matching on data-center networks has two unique properties. (1) Node/edge labels representing vacant CPU cycles and network bandwidth change rapidly, while the network topology varies little. (2) There is a partial order on node/edge labels. Basically, one needs to place service in nodes with enough free capacity. Existing graph indexing techniques have not considered very frequent label updates, and none of them supports partial order on numeric labels. Therefore, we resort to a new graph index framework, Gradin, to address both challenges. Gradin encodes subgraphs into multi-dimensional vectors and organizes them with indices such that it can efficiently search the matches of a query's subgraphs and combine them to form a full match. In particular, we analyze how the index parameters affect update and search performance with theoretical results. Moreover, a revised pruning algorithm is introduced to reduce unnecessary search during the combination of partial matches. Using both real and synthetic datasets, we demonstrate that Gradin outperforms the baseline approaches up to 10 times.

Collaborative networks are composed of experts who cooperate with each other to complete specific tasks, such as resolving problems reported by customers. A task is posted and subsequently routed in the network from an expert to another until being resolved. When an expert cannot solve a task, his routing decision (i.e., where to transfer a task) is critical since it can significantly affect the completion time of a task. In this work, we attempt to deduce the cognitive process of task routing, and model the decision making of experts as a generative process where a routing decision is made based on mixed routing patterns.

In mobile opportunistic networks, most existing research focuses on how to choose appropriate relays to carry and forward data. Although relay selection is an important issue, other issues such as finding content from people with the right expertise are also very important since the ultimate goal of using mobile opportunistic network is to provide the right content to mobile users (nodes). In this paper, we study expertise-based data access in content-centric mobile opportunistic networks, where the objective is to minimize the average query delay given a sequence of queries considering node expertise, node queuing delay and communication delay. To solve this problem, we propose various query forwarding approaches under deterministic and probabilistic expertise models. Specifically, we propose centralized approaches to assign queries based on a modified Dijkstra's shortest path algorithm and distributed approaches in which query forwarding is based on a utility metric. Extensive simulations on both synthetic and realistic traces demonstrate that our solutions outperform existing approaches.

The continued explosion of Twitter data has opened doors for many applications, such as location-based advertisement and entertainment using smartphones. Unfortunately, only about 0.58 percent of tweets are geo-tagged to date. To tackle the location sparseness problem, this paper presents a methodic

Disruption tolerant networks (DTNs) are characterized by low node density, unpredictable node mobility, and lack of global network information. Most of current research efforts in DTNs focus on data forwarding, but only limited work has been done on providing efficient data access to mobile users. In this paper, we propose a novel approach to support cooperative caching in DTNs, which enables the sharing and coordination of cached data among multiple nodes and reduces data access delay. Our basic idea is to intentionally cache data at a set of network central locations (NCLs), which can be easily accessed by other nodes in the network. We propose an efficient scheme that ensures appropriate NCL selection based on a probabilistic selection metric and coordinates multiple caching nodes to optimize the tradeoff between data accessibility and caching overhead. Extensive trace-driven simulations show that our approach significantly improves data access performance compared to existing schemes.

Large scale adoption of MapReduce computations on public clouds is hindered by the lack of trust on the participating virtual machines, because misbehaving worker nodes can compromise the integrity of the computation result. In this paper, we propose a novel MapReduce framework, Cross Cloud MapReduce (CCMR), which overlays the MapReduce computation on top of a hybrid cloud: the master that is in control of the entire computation and guarantees result integrity runs on a private and trusted cloud, while normal workers run on a public cloud. In order to achieve high accuracy, CCMR proposes a result integrity check scheme on both the map phase and the reduce phase, which combines random task replication, random task verification, and credit accumulation, and CCMR strives to reduce the overhead by reducing cross-cloud communication. We implement our approach based on Apache Hadoop MapReduce and evaluate our implementation on Amazon EC2. Both theoretical and experimental analysis show that our approach can guarantee high result integrity in a normal cloud environment while incurring non-negligible performance overhead (e.g., when 16.7% workers are malicious, CCMR can guarantee at least 99.52% of accuracy with 33.6% of overhead when replication probability is 0.3 and the credit threshold is 50).

Big data analytics and knowledge management is becoming a hot topic with the emerging techniques of cloud computing and big data computing model such as MapReduce. However, large-scale adoption of MapReduce applications on public clouds is hindered by the lack of trust on the participating virtual machines deployed on the public cloud. In this paper, we extend the existing hybrid cloud MapReduce architecture to multiple public clouds. Based on such architecture, we propose IntegrityMR, an integrity assurance framework for big data analytics and management applications. We explore the result integrity check techniques at two alternative software layers: the MapReduce task layer and the applications layer. We design and implement the system at both layers based on Apache Hadoop MapReduce and Pig Latin, and perform a series of experiments with popular big data analytics and management applications such as Apache Mahout and Pig on commercial public clouds (Amazon EC2 and Microsoft Azure) and local cluster environment. The experimental result of the task layer approach shows high integrity (98% with a credit threshold of 5) with non-negligible performance overhead (18% to 82% extra running time compared to original MapReduce). The experimental result of the application layer approach shows better performance compared with the task layer approach (less than 35% of extra running time compared with the original MapReduce).

Hidden Markov Models (HMMs) based map matching - that matches a sequence of location samples to a road network - has received a lot of traction in recent years. In this paper we revisit the basic assumption underlying HMM-based map matching algorithms, namely, the hypothesis that the true mobility is Markovian. We use the Chapman-Kolmogorov test and argue that mobility is non-Markovian (especially when the moving object has an intent to reach a specific destination) using thousands of real taxicab mobility datasets spanning several weeks. Based on these observations we present an alternate approach to the map matching problem that relies exclusively on shortest path computations, which are at most linear in the number of road segments, and thus avoids expensive complexity of HMM-based map matching algorithms (e.g., using a Viterbi decoder). We present extensive experimental results to show that our approach vastly outperforms HMM-based approaches in terms of both computational complexity and accuracy.

Multipath TCP (MPTCP) allows the concurrent use of multiple paths between two end points, and as such holds great promise for improving application performance. However, in this paper, we report a newly discovered class of attacks on MPTCP that may jeopardize and hamper its wide-scale adoption. The attacks stem from the interdependence between the multiple subflows in an MPTCP connection. MPTCP congestion control algorithms are designed to achieve resource pooling and fairness with single-path TCP users at shared bottlenecks. Therefore, multiple MPTCP subflows are inherently coupled with each other, resulting in potential side-channels that can be exploited to infer cross-path properties. In particular, an ISP monitoring one or more paths used by an MPTCP connection can infer sensitive and proprietary information (e.g., level of network congestion, end-to-end TCP throughput, packet loss, network delay) about its competitors. Since the side-channel information enabled by the coupling among the subflows in an MPTCP connection results directly from the design goals of MPTCP congestion control algorithms, it is not obvious how to circumvent this attack easily. We believe our findings provide insights that can be used to guide future security-related research on MPTCP and other similar multipath extensions.

Taxicabs equipped with real-time location sensing devices are increasingly becoming popular. Such location traces are a rich source of information and can be used for congestion pricing, taxicab placement, and improved city planning. An important problem to enable these application is to identify human mobility patterns from the taxicab traces, which translates to being able to identify pickup and dropoff points for a particular trip. In this paper, we show that while past approaches are effective in detecting hotspots using location traces, they are largely ineffective in identifying trips (pairs of pickup and dropoff points). We propose the use of a graph theory concept - stretch factor in a novel manner to identify trip(s) made by a taxicab and show that a Hidden Markov Model based algorithm can identify trips (using real datasets from taxicab deployments in Shanghai and partially simulated datasets from Stockholm) with precision and recall of 90-94%, a significant improvement over past approaches that result in a precision and recall of about 50-60%.

One of the key challenges in operational trust management is to continually monitor the behavior of a node and update its trust score accordingly - evidently, both speed and accuracy is of great importance here. To achieve these goals, several papers have explored the concept of mutual revocation (sometimes termed suicide) wherein the trust value of both the accuser and the accused node are temporarily set to zero without involving a quorum. In this paper we explore a partial mutual revocation approach wherein we design a class of trust update functions to temporarily punish both the accuser and accused node (without involving a quorum) - however, the trust update function does not essentially set their trust values to zero; instead it partially lowers the trust values of both the accuser and the accused. In addition, we allow a trusted authority or a quorum may (periodically) review such partial mutual revocations and update the trust values of the accuser and the accused nodes accordingly (e.g., reward the accuser and punish the accused if the accusation was deemed true). We present a detailed design of the trust update functions for partial mutual revocation. Through both analysis and simulations, we evaluate the effectiveness of partial revocation under different attack strategies and report its performance in terms of revocation immediacy, revocation accuracy and abuse resistance.

This paper explores the idea of knowledge-based security policies, which are used to decide whether to answer queries over secret data based on an estimation of the querier's (possibly increased) knowledge given the results. Limiting knowledge is the goal of existing information release policies that employ mechanisms such as noising, anonymization, and redaction. Knowledge-based policies are more general: they increase flexibility by not fixing the means to restrict information flow. We enforce a knowledge-based policy by explicitly tracking a model of a querier's belief about secret data, represented as a probability distribution, and denying any query that could increase knowledge above a given threshold. We implement query analysis and belief tracking via abstract interpretation, which allows us to trade off precision and performance through the use of abstraction. We have developed an approach to augment standard abstract domains to include probabilities, and thus define distributions. We focus on developing probabilistic polyhedra in particular, to support numeric programs. While probabilistic abstract interpretation has been considered before, our domain is the first whose design supports sound conditioning, which is required to ensure that estimates of a querier's knowledge are accurate. Experiments with our implementation show that several useful queries can be handled efficiently, particularly compared to exact (i.e., sound) inference involving sampling. We also show that, for our benchmarks, restricting constraints to octagons or intervals, rather than full polyhedra, can dramatically improve performance while incurring little to no loss in precision.

Keyword search has been popularly used to query graph data. Due to the lack of structure support, a keyword query might generate an excessive number of matches, referred to as "answer graphs", that could include different relationships among keywords. An ignored yet important task is to group and summarize answer graphs that share similar structures and contents for better query interpretation and result understanding. This paper studies the summarization problem for the answer graphs induced by a keyword query Q . (1) A notion of summary graph is proposed to characterize the summarization of answer graphs. Given Q and a set of answer graphs G, a summary graph preserves the relation of the keywords in Q by summarizing the paths connecting the keywords nodes in G. (2) A quality metric of summary graphs, called coverage ratio, is developed to measure information loss of summarization. (3) Based on the metric, a set of summarization problems are formulated, which aim to find minimized summary graphs with certain coverage ratio. (a) We show that the complexity of these summarization problems ranges from ptime to NP-complete. (b) We provide exact and heuristic summarization algorithms. (4) Using real-life and synthetic graphs, we experimentally verify the effectiveness and the efficiency of our techniques.

Cooperation between nodes is essential for the functionality of a mobile ad-hoc network (MANET). However, since the nodes in a MANET are generally resource limited, some nodes could refuse service to other nodes to conserve their resources, thereby exhibiting selfish behavior. Also, since a MANET is often deployed in uncontrolled environments, some nodes could be compromised by an adversary and directed to act maliciously. A trust management framework in a MANETis useful to infer if nodes behave in a selfish or malicious manner, so that appropriate action could be taken, in order to maximize network performance. In this paper, we propose a scalable trust management scheme to partition and store an information network of trust metadata of nodes in a MANET. The simplicity of our scheme for trust metadata propagation and retrieval and its robustness to node failures, membership changes and mobility, make it a promising choice for trust management in a MANET. Simulation results that evaluate our scheme based on the trust management metrics we have defined demonstrate its performance benefits.

Location-based services, which employ data from smartphones, vehicles, etc., are growing in popularity. To reduce the threat that shared location data poses to a user's privacy, some services anonymize or obfuscate this data. In this paper, we show these methods can be effectively defeated: a set of location traces can be deanonymized given an easily obtained social network graph. The key idea of our approach is that a user may be identified by those she meets: a "contact graph" identifying meetings between anonymized users in a set of traces can be structurally correlated with a social network graph, thereby identifying anonymized users. We demonstrate the effectiveness of our approach using three real world datasets: University of St Andrews mobility trace and social network (27 nodes each), SmallBlue contact trace and Facebook social network (125 nodes), and Infocom 2006 bluetooth contact traces and conference attendees' DBLP social network (78 nodes). Our experiments show that 80% of users are identified precisely, while only 8% are identified incorrectly, with the remainder mapped to a small set of users.

Opportunistic mobile networks consist of personal mobile devices which are intermittently connected with each other. Data access can be provided to these devices via cooperative caching without support from the cellular network infrastructure, but only limited research has been done on maintaining the freshness of cached data which may be refreshed periodically and is subject to expiration. In this paper, we propose a scheme to efficiently maintain cache freshness. Our basic idea is to let each caching node be only responsible for refreshing a specific set of caching nodes, so as to maintain cache freshness in a distributed and hierarchical manner. Probabilistic replication methods are also proposed to analytically ensure that the freshness requirements of cached data are satisfied. Extensive trace driven simulations show that our scheme significantly improves cache freshness, and hence ensures the validity of data access provided to mobile users.

The explosion of data consumption has led to a renewed interest in byte caching. With studies showing potential reductions in network traffic of 50%, this fine grained caching technique looks like a very good and attractive solution for mobile wireless operators. However, properties of wireless networks actually present new challenges. We first show that a single packet loss, re-ordering or corruption -- all common conditions over the air interface -- can result in circular dependencies and cause existing byte caching algorithms to loop endlessly. To remedy the problem, we then explore a new set of encoding algorithms. Third, we assess the impact of packet losses on byte caching performances, both in terms of byte savings and delay reduction. We found that a mere 1% packet loss can already nullify any delay reduction and instead cause significant increases that users may not be willing to tolerate. Finally, we shared several insights, including interactions between transport layer protocol's mechanisms (e.g., TCP window congestion) and byte caching operations that can cause sophisticated encoding algorithms to perform poorly. We believe that these insights are important for designing more efficient and robust byte caching encoding algorithms.

The immensity and variety of personal information (e.g., profile, photo, and microblog) on social sites require access control policies tailored to individuals' privacy needs. Today such policies are still mainly specified manually by ordinary users, which is usually coarse-grained, tedious, and error-prone. This paper presents the design, implementation, and evaluation of an automated access control policy specification tool, XACCESS, that helps non-expert users effectively specify who should have access to which part of their data. A series of key features distinguish XACCESS from prior work: 1) it adopts a role-based access control model (instead of the conventional rule-based paradigm) to capture the implicit privacy/interest preference of social site users; 2) it employs a novel hybrid mining method to extract a set of semantically interpretable, functional "social roles", from both static network structures and dynamic historical activities; 3) based on the identified social roles, confidentiality setting of personal data, and (optional and possibly inconsistent) predefined user-permission assignments, it recommends a set of high-quality privacy settings; 4) it allows user feedback in every phase of the process to further improve the quality of the suggested privacy policies. A comprehensive experimental evaluation is conducted over real social network and user study data to validate the efficacy of XACCESS.

Social influences, the phenomena that one individual's actions can induce similar behaviors among his/her friends via their social ties, have been observed prevailingly in socially networked systems. While most existing work focuses on studying general, macro-level influence (e.g., diffusion); equally important is to understand social influence at microscopic scales (i.e., at the granularity of single individuals, actions, and time-stamps), which may benefit a range of applications. We propose μSI, a microscopic social-influence model wherein: individuals' actions are modeled as temporary interactions between social network (formed by individuals) and object network (formed by targets of actions); one individual's actions influence his/her friends in a dynamic, network-wise manner (i.e., dependent on both social and object networks). We develop for μSI a suite of novel inference tools that enable to answer questions of the form: How may an occurred interaction trigger another? More importantly, when and where may a new interaction be observed? We carefully address the computational challenges for inferencing over such semantically rich models by dynamically identifying sub-domains of interest and varying the precision of solutions over different sub-domains. We demonstrate the breadth and generality of μSI using two seemingly disparate applications. In the context of social tagging service, we show how it can help improve the accuracy and freshness of resource recommendation; in the context of mobile phone call service, we show how it can help improve the efficiency of paging operation.

In coalition operations, information from different sources belong to different organisations have to be gathered and aggregated. The information from these resources may not be consistent. Inconsistencies in the gathered information creates severe uncertainties that hinders the usefulness of the information. In this paper, we have propose a Subjective Logic based approach for modelling the trustworthiness of information sources within a specific context. This model is used to handle inconsistencies through filtering information from less trustworthy sources.

Recently, many research studies have explored the use of wireless fading to generate an information-theoretic shared secret key over an open wireless channel. While this line of research is now mature enough to be built into demonstrative working systems for scenarios involving a (limited) passive/eavesdropping adversary model, the case of an active (jamming) adversary has not been sufficiently studied. Under an active adversary, information-bits that need to be exchanged during the process of key setup will not only be subject to eavesdropping, but also message disruptions that could lead to a high communication cost per bit of secret key generated. Measuring efficiency of key exchange as the ratio of communication cost to the size of secret key generated, in this paper, we address the following question: Is generating a secret key by exploiting wireless fading an efficient process? We obtain analytical results that quantify the minimum number of information-bits that must be exchanged to obtain one bit of shared secret key and show that this number rapidly increases with an active adversary's signal power. Thus, through our analysis, we conclude that the effectiveness of generating a secret key from wireless fading is limited when considering active adversaries.

This paper explores the idea of knowledge-based security policies, which are used to decide whether to answer queries over secret data based on an estimation of the querier's (possibly increased) knowledge given the results. Limiting knowledge is the goal of existing information release policies that employ mechanisms such as noising, anonymization, and redaction. Knowledge-based policies are more general: they increase flexibility by not fixing the means to restrict information flow. We enforce a knowledge-based policy by explicitly tracking a model of a querier's belief about secret data, represented as a probability distribution, and denying any query that could increase knowledge above a given threshold. We implement query analysis and belief tracking via abstract interpretation using a novel probabilistic polyhedral domain, whose design permits trading off precision with performance while ensuring estimates of a querier's knowledge are sound. Experiments with our implementation show that several useful queries can be handled efficiently, and performance scales far better than would more standard implementations of probabilistic computation based on sampling.

Information flow analysis is a powerful technique for reasoning about the sensitive information exposed by a program during its execution. While past work has proposed information theoretic metrics (e.g., Shannon entropy, min-entropy, guessing entropy, etc.) to quantify such information leakage, we argue that some of these measures not only result in counter-intuitive measures of leakage, but also are inherently prone to conflicts when comparing two programs P1and P2- say Shannon entropy predicts higher leakage for program P1, while guessing entropy predicts higher leakage for program P2. This paper presents the first attempt towards addressing such conflicts and derives solutions for conflict-free comparison of finite order deterministic programs.

Disruption Tolerant Networks (DTNs) are characterized by the low node density, unpredictable node mobility and lack of global network information. Most of current research efforts in DTNs focus on data forwarding, but only limited work has been done on providing effective data access to mobile users. In this paper, we propose a novel approach to support cooperative caching in DTNs, which enables the sharing and coordination of cached data among multiple nodes and reduces data access delay. Our basic idea is to intentionally cache data at a set of Network Central Locations (NCLs), which can be easily accessed by other nodes in the network. We propose an effective scheme which ensures appropriate NCL selection based on a probabilistic selection metric, and coordinate multiple caching nodes to optimize trade off between data accessibility and caching overhead. Extensive trace-driven simulations show that our scheme significantly improves data access performance compared to existing schemes.

Information leakage via the networks formed by subjects (e.g., Facebook, Twitter) and objects (e.g., blogosphere) - some of whom may be controlled by malicious insiders - often leads to unpredicted access control risks. While it may be impossible to precisely quantify information flows between two entities (e.g., two friends in a social network), this paper presents a first attempt towards leveraging recent advances in modeling socio-information networks to develop a statistical risk estimation paradigm for quantifying such insider threats. In the context of socio-information networks, our models estimate the following likelihoods: prior flow - has a subject $s$ acquired covert access to object o via the networks? posterior flow - if s is granted access to o, what is its impact on information flows between subject s' and object o'? network evolution - how will a newly created social relationship between s and s' influence current risk estimates? Our goal is not to prescribe a one-size-fits-all solution; instead we develop a set of composable network-centric risk estimation operators, with implementations configurable to concrete socio-information networks. The efficacy of our solutions is empirically evaluated using real-life datasets collected from the IBM SmallBlue project and Twitter.

Publish-subscribe (pub-sub) is an emerging paradigm for building a large number of distributed systems. A wide area pub-sub system is usually implemented on an overlay network infrastructure to enable information dissemination from publishers to subscribers. Using an open overlay network raises several security concerns such as: confidentiality and integrity, authentication, authorization and Denial-of-Service (DoS) attacks. In this article we present EventGuard, a framework for building secure wide-area pub-sub systems. The EventGuard architecture is comprised of three key components: (1) a suite of security guards that can be seamlessly plugged-into a content-based pub-sub system, (2) a scalable key management algorithm to enforce access control on subscribers, and (3) a resilient pub-sub network design that is capable of scalable routing, handling message dropping-based DoS attacks, and node failures. The design of EventGuard mechanisms aims at providing security guarantees while maintaining the system’s overall simplicity, scalability, and performance metrics. We describe an implementation of the EventGuard pub-sub system to show that EventGuard is easily stackable on any content-based pub-sub core. We present detailed experimental results that quantify the overhead of the EventGuard pub-sub system and demonstrate its resilience against various attacks.

(A short version of this paper appears in IEEE INFOCOM 2009: http://www.research.ibm.com/people/i/iyengar/INFOCOM2009-kanon.pdf.) Peer-to-peer VoIP (voice over IP) networks, exemplified by Skype, are becoming increasingly popular due to their significant cost advantage and richer call forwarding features than traditional public switched telephone networks. One of the most important features of a VoIP network is privacy (for VoIP clients). Unfortunately, most peer-to-peer VoIP networks neither provide personalization nor guarantee a quantifiable privacy level. In this paper, we propose novel flow analysis attacks that demonstrate the vulnerabilities of peer-to-peer VoIP networks to privacy attacks. We then address two important challenges in designing privacy-aware VoIP networks: Can we provide personalized privacy guarantees for VoIP clients that allow them to select privacy requirements on a per-call basis? How to design VoIP protocols to support customizable privacy guarantee? This paper proposes practical solutions to address these challenges using a quantifiable k-anonymity metric and a privacy-aware VoIP route setup and route maintenance protocols. We present detailed experimental evaluation that demonstrates the performance and scalability of our protocol, while meeting customizable privacy guarantees.

Decision makers (humans or software agents alike) are faced with the challenge of examining large volumes of information originating from heterogeneous sources with the goal of ascertaining trust in various pieces of information. In this paper we argue (using examples) that traditional trust models are limited in their data model by assuming a pair-wise numeric rating between two entities (e.g., eBay recommendations, Netflix movie rating, etc). We present a novel trust computational model for rich, complex and uncertain information encoded using Bayesian Description Logics. We present security and scalability tradeoffs that arise in the new model, and the results of an evaluation of the first prototype implementation under a variety attack scenarios.

Operational networks typically generate massive monitoring data that consist of local (in both space and time) observations of the status of the networks. It is often hypothesized that such data exhibit both spatial and temporal correlation based on the underlying network topology and time of occurrence; identifying such correlation patterns offers valuable insights into global network phenomena (e.g., fault cascading in communication networks). In this paper we introduce a new class of models suitable for learning, indexing, and identifying spatio-temporal patterns in network monitoring data. We exemplify our techniques with the application of fault diagnosis in enterprise networks. We show how it can help network management systems (NMSes) to effciently detect and localize potential faults (e.g., failure of routing protocols or network equipments) by analyzing massive operational event streams (e.g., alerts, alarms, and metrics). We provide results from extensive experimental studies over real network event and topology datasets to explore the effcacy of our solution.

In this paper we present a new key-revocation scheme for ad hoc network environments with the following characteristics:

In both commercial and defense sectors a compelling need is emerging for rapid, yet secure, dissemination of information to the concerned actors. Traditional approaches to information sharing that rely on security labels (e.g., Multi-Level Security (MLS)) suffer from at least two major drawbacks. First, static security labels do not account for tactical information whose value decays over time. Second, MLS-like approaches have often ignored information transform semantics when deducing security labels (e.g., output security label = max over all input security labels). While MLS-like label deduction appears to be conservative, we argue that this approach can result in both underestimation and overestimation of security labels. We contend that overestimation may adversely throttle information flows, while underestimation incites information misuse and leakage.

Peer-to-peer VoIP (voice over IP) networks, exemplified by Skype, are becoming increasingly popular due to their significant cost advantage and richer call forwarding features than traditional public switched telephone networks. One of the most important features of a VoIP network is privacy (for VoIP clients). Unfortunately, most peer-to-peer VoIP networks neither provide personalization nor guarantee a quantifiable privacy level. In this paper we propose novel flow analysis attacks that demonstrate the vulnerabilities of peer-to-peer VoIP networks to privacy attacks. We present detailed experimental evaluation that demonstrates these attacks quantifying performance and scalability degradation.

Modern communication networks generate massive volume of operational event data, e.g., alarm, alert, and metrics, which can be used by a network management system (NMS) to diagnose potential faults. In this work, we introduce a new class of indexable fault signatures that encode temporal evolution of events generated by a network fault as well as topological relationships among the nodes where these events occur. We present an efficient learning algorithm to extract such fault signatures from noisy historical event data, and with the help of novel space-time indexing structures, we show how to perform efficient, online signature matching. We provide results from extensive experimental studies to explore the efficacy of our approach and point out potential applications of such signatures for many different types of networks including social and information networks.

In both the commercial and defense sectors a compelling need is emerging for highly dynamic, yet risk optimized, sharing of information across traditional organizational boundaries. Risk optimal decisions to disseminate mission critical tactical intelligence information to the pertinent actors in a timely manner is critical for a mission's success. In this paper1, we argue that traditionally decision support mechanisms for information sharing (such as Multi-Level Security (MLS)) besides being rigid and situation agnostic, do not offer explanations and diagnostics for non-shareability. This paper exploits rich security metadata and semantic knowledgebase that captures domain specific concepts and relationships to build a logic for risk optimized information sharing. We show that the proposed approach is: (i) flexible: e.g., sensitivity of tactical information decays with space, time and external events, (ii) situation-aware: e.g., encodes need-to-know based access control policies, and more importantly (iii) supports explanations for non-shareability; these explanations in conjunction with rich security metadata and domain ontology allows a sender to intelligently transform information (e.g., downgrade information, say, by deleting participant list in a meeting) with the goal of making transformed information shareable with the recipient. In this paper, we will describe an architecture for secure information sharing using a publicly available hybrid semantic reasoner and present several illustrative examples that highlight the benefits of our proposal over traditional approaches.

As the size of a centrally managed IP network increases, the cost of monitoring network devices and the number of reported events increase super-linearly. This in turn degrades the performance of the event correlation engine that is responsible for suppressing dependent events and escalating root cause events to a network administrator. To solve this scalability problem, we propose a distributed framework that partitions the network into smaller management domains and enables concurrent monitoring and event correlation in those domains. The gain in performance, however, comes with the challenge of correlating cross-domain events which occurs when failure in one domain induces events in other domain(s). In this paper, we investigate such situations and show in the worst case it would be impossible to determine the root cause. We propose a two step approach to solve this problem. First, we define a property called route-closure, which if satisfied by every partition not only minimizes the number of cross-domain events but also eliminates cases wherein root cause analysis may be inconclusive. We also describe a technology-centric partitioning mechanism that constructs partitions satisfying the route-closure property. Next, we propose a distributed architecture to efficiently identify and correlate cross-domain events. We use a commercial network management system to implement our distributed framework and run experiments by injecting synthetic events on large, real network topologies. Our experimental results show that our approach can manage over 200,000 managed entities and handle event bursts of size 15,000 in under five minutes without compromising the efficacy of event correlation.

Serverless distributed computing has received significant attention from both the industry and the research community. Among the most popular applications are the wide area network file systems, exemplified by CFS, Farsite and OceanStore. These file systems store files on a large collection of untrusted nodes that form an overlay network. They use cryptographic techniques to maintain file confidentiality and integrity from malicious nodes. Unfortunately, cryptographic techniques cannot protect a file holder from a Denial-of-Service (DoS) or a host compromise attack. Hence, most of these distributed file systems are vulnerable to targeted file attacks, wherein an adversary attempts to attack a small (chosen) set of files by attacking the nodes that host them. This paper presents LocationGuard - a location hiding technique for securing overlay file storage systems from targeted file attacks. LocationGuard has three essential components: (i) location key, (ii) routing guard, a secure algorithm that protects accesses to a file in the overlay network given its location key, and (iii) a set of location inference guards. Our experimental results quantify the overhead of employing LocationGuard and demonstrate its effectiveness against DoS attacks, host compromise attacks and various location inference attacks.

With fast-paced growth of digital data and exploding storage management costs, enterprises are looking for new ways to effectively manage their data. One such cost-effective paradigm is the cloud storage model also referred to as Storage-as-a-Service, in which enterprises outsource their storage to a storage service provider (SSP) by storing data (usually encrypted) at a remote SSP-managed site and accessing it over a high speed network. Along with storage capacity used, the SSP often charges clients on the amount of data that is accessed from the SSP site. Thus, it is in the interest of the client enterprise to download only relevant content. This makes search over outsourced storage an important capability. Searching over encrypted outsourced storage, however, is a complex challenge. Each enterprise has different access privileges for different users and this access control needs to be preserved during search (for example, ensuring that a user cannot search through data that is inaccessible from the filesystem due to its permissions). Secondly, the search mechanism has to preserve confidentiality from the SSP and indices can not be stored in plain text. In this article, we present a new filesystem search technique that integrates access control and indexing/search mechanisms into a unified framework to support access control aware search. Our approach performs indexing within the trusted enterprise domain and uses a novel access control barrel (ACB) primitive to encapsulate access control within these indices. The indices are then systematically encrypted and shipped to the SSP for hosting. Unlike existing enterprise search techniques, our approach is resilient to various common attacks that leak private information. Additionally, to the best of our knowledge, our approach is a first such technique that allows search indices to be hosted at the SSP site, thus effectively providing search-as-a-service . This does not require the client enterprise to fully trust the SSP for data confidentiality. We describe the architecture and implementation of our approach and a detailed experimental analysis comparing with other approaches.

In both the commercial and defence sectors a compelling need is emerging for the rapid, yet secure, dissemination of information across traditional organisational boundaries. In this paper we present a novel trust management paradigm for securing pan-organisational information flows that aims to address the threat of information leakage. Our trust management system is built around an economic model and a trust-based encryption primitive wherein: (i) entities purchase a key from a Trust Authority (TA) which is bound to a voluntarily reported trust score r, (ii) information flows are encrypted such that a flow tagged with a recipient trust score R can be decrypted by the recipient only if it possesses the key corresponding to a voluntarily reported score r < = R, (iii) the economic model (the price of keys) is set such that a dishonest entity wishing to maximise information leakage is incentivised to report an honest trust score r to the TA. This paper makes two important contributions. First, we quantify fundamental tradeoffs on information flow rate, information leakage rate and error in estimating recipient trust score R. Second, we present a suite of encryption schemes that realise our trust-based encryption primitive and identify computation and communication tradeoffs between them.

A growing class of applications, including VoIP, IM and presence, are enabled by the session initiation protocol (SIP). Requests in SIP typically traverse through multiple proxies. The availability of multiple proxies offers the flexibility to distribute proxy functionality across several nodes. In particular, after experimentally demonstrating that the resource consumption of maintaining state is significant, we define the problem of state distribution across multiple nodes when the goal is to increase overall call throughput. We first formulate this as an optimization problem and then derive a distributed algorithm from it. This distributed algorithm leads to the design and evaluation of SERvartuka, a more scalable SIP server that dynamically determines the number of SIP requests for which the server is stateful while delegating state maintenance for the remainder of the requests to a server further downstream. This design is in contrast to existing SIP servers that are statically configured to either be stateless or stateful and therefore result in sub-optimal call throughput. We implement SERvartuka on top of OpenSER, a commercial SIP proxy server and measure performance benefits of different server configurations. An example of our results is a 20% percent increase in call throughput when using our algorithm for a configuration of two servers in series.

One important problem for public broadcast Location-Based Services (LBS) is to enforce access control on a large number of subscribers. In such a system a user typically subscribes to a LBS for a time interval (a, b) and a spatial region (xbl, ybl, xir, ytr) according to a 3-dimensional spatial-temporal authorization model. In this paper, we argue that current approaches to access control using group key management protocols are not scalable. Our proposal STauth minimizes the number of keys which needs to be distributed and is thus scalable to a much higher number of subscribers and the dimensionality of the authorization model. We analytically and experimentally demonstrate the performance and scalability benefits of our approach against other group key management protocols.

Recently, risk-based information trading has emerged as a new paradigm for securely sharing information across traditional organizational boundaries. In this paradigm, the risk of sharing information between organizations is characterized using expected losses (due, for example, to (un)intended information disclosure) and billed to a recipient. However, within risk-based information trading systems, quantifying the risks associated with sharing information is a non-trivial task, particularly when risk calculations depend on a number of factors. In this paper we introduce a data-centric metadata framework that extends risk-based information trading approaches by allowing one or more domains to exchange sensitive information based on metadata evaluated against internal risk assessments of the domains. We present a use case of our metadata framework using a coalition military scenario, wherein information flows can be controlled and regulated by our framework whilst allowing sufficiently high-quality tactical information to be disseminated.

Applications such as VoIP need to provide anonymity to clients while maintaining low latency to satisfy quality of service (QoS) requirements. Existing solutions for providing anonymity such as mix networks are not well suited to applications like VoIP, SSH, and gaming which require low communication latency. This paper investigates the problem of on-demand construction of QoS sensitive routes on anonymizing networks using the VoIP application. We first describe triangulation based timing analysis attacks on shortest path route set up protocols. We show that even when a small fraction (~1%) of the network is malicious, the adversary can infer the source (caller) with reasonably high probability. Second, we describe random walk based route set up protocols that significantly improve anonymity while satisfying latency- based QoS guarantees. We describe a prototype implementation of our proposal and show that our protocols can significantly reduce the probability of inferring the caller. We present a detailed experimental evaluation to demonstrate our attacks and quantify the performance and scalability of our guards.

Discovering the topology of a network and detecting link state changes (e.g.: link failures) is an essential element for various network management and monitoring tasks. In this paper, we investigate scalable mechanisms to monitor the topology and link states of networks based on information available in network nodes' routing tables. We first present an algorithm that infers the network topology based on the full or partial information about network distances between nodes, based on which we obtain a scalable network topology discovery solution via a novel use of random walk in graphs. We then present scalable algorithms to detect the state changes of remote links by monitoring the routing tables of a small fraction of the routers, where the routers to be monitored are selected by a greedy approach to an NP-complete Tree Cover problem. We show the efficacy and scalability of our topology monitoring algorithms through experimental evaluation performed both on synthetic topologies and on a large topology data-set from a real enterprise network.

An enterprise typically operates multiple data center sites, each handling workloads according to an enterprise-level strategy. Sharing resources across multiple sites (or enterprises) brings up several important problems. Each site may have its own policies that govern its interactions with other remote sites. Different policies impact the system performance in different ways. The site administrators and system designers need to understand the effects of a given set of policies on different workloads. In this paper, we describe an analysis methodology that determines the impact of policies on the workloads, and we present results and validation for a prototypical multi-site resource sharing system. Our analytical tool is capable of evaluating complex policies on a large scale system and permits independent policies for each site, so that policy makers can quickly evaluate several alternatives and their effects on the workloads before deploying them.

Recently, we have seen increasing numbers of denial of service (DoS) attacks against online services and Web applications either for extortion reasons or for impairing and even disabling the competition. These DoS attacks have increasingly targeted the application level. Application-level DoS attacks emulate the same request syntax and network-level traffic characteristics as those of legitimate clients, thereby making the attacks much harder to detect and counter. Moreover, such attacks often target bottleneck resources such as disk bandwidth, database bandwidth, and CPU resources. In this article, we propose handling DoS attacks by using a twofold mechanism. First, we perform admission control to limit the number of concurrent clients served by the online service. Admission control is based on port hiding that renders the online service invisible to unauthorized clients by hiding the port number on which the service accepts incoming requests. Second, we perform congestion control on admitted clients to allocate more resources to good clients. Congestion control is achieved by adaptively setting a client's priority level in response to the client's requests in a way that can incorporate application-level semantics. We present a detailed evaluation of the proposed solution using two sample applications: Apache HTTPD and the TPCW benchmark (running on Apache Tomcat and IBM DB2). Our experiments show that the proposed solution incurs low performance overhead and is resilient to DoS attacks.

Secure event dissemination in a pub-sub network refers to secure distribution of events to clients subscribing to those events without revealing the secret attributes in the event to the unauthorized subscribers and the routing nodes in a pub-sub network. A common solution to provide confidentiality guarantees for the secret attributes in an event is to encrypt so that only authorized subscribers can read them. The key challenge here is to build a secure and scalable content-based event dissemination infrastructure that can handle complex and flexible subscription models while preserving the efficiency and scalability of key management algorithms. In this paper, we describe the design and implementation of PSGuard, for secure event dissemination in pub-sub networks. PSGuard exploit hierarchical key derivation algorithms to encode publication-subscription matching semantics for scalable key management. An experimental evaluation of our prototype system shows that PSGuard meets the security requirements while maintaining the performance and scalability of a pub-sub network.

We describe DSphere - a decentralized system for crawling, indexing, searching and ranking of documents in the World Wide Web. Unlike most of the existing search technologies that depend heavily on a page-centric view of the Web, we advocate a source-centric view of the Web and propose a decentralized architecture for crawling, indexing and searching the Web in a distributed source-specific fashion. A fully decentralized crawler is developed to crawl the World Wide Web where each peer is assigned the responsibility of crawling a specific set of documents referred to as a source collection. Link analysis techniques are used for ranking documents. Traditional link analysis techniques suffer from problems like slow refresh rate and vulnerabilities to Web Spam. We propose a source-based link analysis approach, which computes fast and accurate ranking scores for all crawled documents.

With fast paced growth of digital data, keyword based search has become a critical enterprise application. Research has shown that nearly 85% of enterprise data lies in flat filesystems [10] that allow multiple users with different access privileges. Any search tool for such systems needs to be efficient and yet cognizant of access control semantics imposed by the underlying filesystem. Current enterprise search techniques use two disjoint search and access- control components by creating a single system-wide index and filtering search results for access control. This approach is ineffective as index and query statistics subtly leak private information. The other approach of using separate indices for each user is undesirable as it not only increases disk consumption due to shared files, but also increases overheads of updating indices whenever a file changes. We propose a distributed approach that couples search and access-control into a unified framework and pro vides secure multiuser search. Our scheme (logically) divides data into independent access-privileges based chunks, called access-control barrels (ACB). ACBs not only manage security but also improve overall efficiency as they can be indexed and searched in parallel by distributing them to multiple enterprise machines. We describe the architecture of ACBs based search and propose an optimization that ensures the scalability of our approach. We validate our design with a detailed evaluation using industry benchmarks and datasets. Our initial experiments show secure search with 38% improved indexing efficiency and low overheads for ACB processing.

Service composition has emerged as a fundamental technique for developing Web applications. Multiple services, often from different organizations or trust domains, may be dynamically composed to satisfy a user's request. Access control in the presence of service compositions is a challenging security problem. In this paper, we present an access control model and techniques for specifying and enforcing access control rules on Web service compositions. A key advantage of our approach is that past histories of service invocations can be used to make access control decisions. Our approach allows role hierarchies and separation of duty constraints. Access controls rules may be parameterized by one or more arguments. We have implemented our access control model via a declarative policy specification language which uses pure-past linear temporal logic (PPLTL). We describe an implementation of our approach using a supply chain management (SCM) application. Our experiments show that our approach can enforce expressive and flexible access control policies while incurring reasonable performance overhead on the application.

Denial of service (DoS) attacks attempt to consume a server's resources (network bandwidth, computing power, main memory, disk bandwidth etc.) to near exhaustion so that there are no resources left to handle requests from legitimate clients. An effective solution to defend against DoS attacks is to filter DoS attack requests at the earliest point (say, the Web site's firewall), before they consume much of the server's resources. Most defenses against DoS attacks attempt to filter requests from inauthentic clients before they consume much of the server's resources. Client authentication using techniques like IPSec or SSL may often require changes to the client-side software and may additionally require superuser privileges at the client for deployment. Further, using digital signatures (as in SSL) makes verification very expensive, thereby making the verification process itself a viable DoS target for the adversary. In this paper, we propose a light-weight client transparent technique to defend against DoS attacks with two unique features: (i) Our technique can be implemented entirely using JavaScript support provided by a standard client-side browser like Mozilla FireFox or Microsoft Internet Explorer. Client transparency follows from the fact that: (i) no changes to client-side software are required, (ii) no client-side superuser privileges are required, and (iii) clients (human beings or automated clients) can browse a DoS protected Web site in the same manner that they browse other Web sites, (ii) Although we operate using the client-side browser (HTTP layer), our technique enables fast IP level packet filtering at the server's firewall and requires no changes to the application(s) hosted by the Web server. In this paper we present a detailed design of our technique along with a detailed security analysis. We also describe a concrete implementation of our proposal on the Linux kernel and present an evaluation using two applications: bandwidth intensive Apache HTTPD and database intensive TPCW. Our experiments show that our approach incurs a low performance overhead and is resilient to DoS attacks

Peer-to-peer (P2P) file sharing systems such as Gnutella have been widely acknowledged as the fastest-growing Internet applications ever. The P2P model has many potential advantages, including high flexibility and serverless management. However, these systems suffer from the well-known performance mismatch between the randomly constructed overlay network topology and the underlying IP-layer topology. This paper proposes to structure the P2P overlay topology using a heterogeneity-aware multitier topology to better balance the load at peers with heterogeneous capacities and to prevent low-capability nodes from throttling the performance of the system. An analytical model is developed to enable the construction and maintenance of heterogeneity-aware overlay topologies with good node connectivity and better load balance. We also develop an efficient routing scheme, called probabilistic selective routing, that further utilizes heterogeneity-awareness to enhance the routing performance. We evaluate our design through simulations. The results show that our multitier topologies alone can provide eight to 10 times improvement in the messaging cost, two to three orders of magnitude improvement in terms of load balancing, and seven to eight times lower topology construction and maintenance costs when compared to Gnutella's random power-law topology. Moreover, our heterogeneity-aware routing scheme provides further improvements on all evaluation metrics, when used with our heterogeneity-aware overlay topologies.

A publish-subscribe overlay service is a wide-area communication infrastructure that enables information dissemination across geographically scattered and potentially unlimited number of publishers and subscribers. A wide-area publish-subscribe (pub-sub) system is often implemented as a collection of spatially disparate nodes communicating on top of a peer to peer overlay network. Such a model presents many inherent benefits such as scalability and performance, as well as potential challenges such as: (i) confidentiality & integrity, (ii) authentication, and (iii) denial-of-service (DoS) attacks. In this paper we present EventGuard for securing pub-sub overlay services. EventGuard comprises of a suite of security guards that can be seamlessly plugged-into a content-based pub-sub system. EventGuard mechanisms aim at providing security guarantees while maintaining the system's overall simplicity, scalability and performance metrics. We present an implementation which shows that EventGuard is easily stackable on any content-based pub-sub core. Finally, our experimental results show that EventGuard can secure a pub-sub system with minimal performance penalty.

In a distributed Web service integration environment, the selection of Web services should be based on their reputation and quality-of-service (QoS). Various trust models for web services have been proposed to evaluate the reputation of Web services/service providers. Current mechanisms are based on tracing the feedbacks to the past behaviors of Web services. However, very few of them consider the robustness and attack-resiliency of the trust models. In this paper, we present an attack resilient distributed trust management system in a Web service management environment. The proposed attack resilient trust model uses two vectors to capture the behavior and the trustworthiness of a Web service/service provider based on our analysis on the possible attacks against the trust models. We also present a set of experiments that show the effectiveness of our trust model in detecting malicious behavior of service providers.

Reputation systems have been popular in estimating the trustworthiness and predicting the future behavior of nodes in a large-scale distributed system where nodes may transact with one another without prior knowledge or experience. One of the fundamental challenges in distributed reputation management is to understand vulnerabilities and develop mechanisms that can minimize the potential damages to a system by malicious nodes. In this paper, we identify three vulnerabilities that are detrimental to decentralized reputation management and propose TrustGuard - a safeguard framework for providing a highly dependable and yet efficient reputation system. First, we provide a dependable trust model and a set of formal methods to handle strategic malicious nodes that continuously change their behavior to gain unfair advantages in the system. Second, a transaction based reputation system must cope with the vulnerability that malicious nodes may misuse the system by flooding feedbacks with fake transactions. Third, but not least, we identify the importance of filtering out dishonest feedbacks when computing reputation-based trust of a node, including the feedbacks filed by malicious nodes through collusion. Our experiments show that, comparing with existing reputation systems, our framework is highly dependable and effective in countering malicious nodes regarding strategic oscillating behavior, flooding malevolent feedbacks with fake transactions, and dishonest feedbacks.

A number of recent applications have been built on distributed hash tables (DHTs) based overlay networks. Almost all DHT-based schemes employ a tight deterministic data placement and ID mapping schemes. This feature on one hand provides assurance on location of data if it exists, within a bounded number of hops, and on the other hand, opens doors for malicious nodes to lodge attacks that can potentially thwart the functionality of the overlay network. This paper studies several serious security threats in DHT-based systems through two targeted attacks at the overlay network's protocol layer. The first attack explores the routing anomalies that can be caused by malicious nodes returning incorrect lookup routes. The second attack targets the ID mapping scheme. We disclose that the malicious nodes can target any specific data item in the system; and corrupt/modify the data item to its favor. For each of these attacks, we provide quantitative analysis to estimate the extent of damage that can be caused by the attack; followed by experimental validation and defenses to guard the overlay networks from such attacks.