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.

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.

We consider the problem of tracking the topology of a large-scale dynamic network with limited monitoring resources. By modeling the dynamics of links as independent ON-OFF Markov chains, we formulate the problem as that of maximizing the overall accuracy of tracking link states when only a limited number of network elements can be monitored at each time step. We consider two forms of sampling policies: link sampling, where we directly observe the selected links, and node sampling, where we observe states of the links adjacent to the selected nodes. We reduce the link sampling problem to a Restless Multi-armed Bandit (RMB) and prove its indexability under certain conditions. By applying the Whittle's index policy, we develop an efficient link sampling policy with methods to compute the Whittle's index explicitly. Under node sampling, we use a linear programming (LP) formulation to derive an extended policy that can be reduced to determining the nodes with maximum coverage of the Whittle's indices. We also derive performance upper bounds in both sampling scenarios. Simulations show the efficacy of the proposed policies. Compared with the myopic policy, our solution achieves significantly better tracking performance for heterogeneous links.

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.

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 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.

In this paper, a novel procedural framework for increasing the efficiency of the model composition process for the end-to-end transactional behavior of various classes of business-level computer applications is presented. The objectives of the framework are reducing the composition time and the level of engagement of domain experts in deploying business management solutions. Starting with application footprints (i.e., raw log data of various types) and without the need for a priori understanding of their syntax and semantics, the framework permits the analysis of the footprints based on an agnostic tokenization of log data. The framework then produces candidate states and relationships that form the basis for composing the transactional models via the framework's state and relationship manipulation utilities. The main architectural components of the framework are presented and their underlying principles discussed. A case study highlighting the use of the framework, based on an implementation of it, is given and a discussion regarding additional features of the framework and its relation to other research activities is also provided.

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.

The problem of tracking end-to-end service-level transactions in the absence of instrumentation support is considered. The transaction instances progress through a state-transition model and generate time-stamped footprints on entering each state in the model. The goal is to track individual transactions using these footprints even when the footprints may not contain any tokens uniquely identifying the transaction instances that generated them. Assuming a semi-Markov process model for state transitions, the transaction instances are tracked probabilistically by matching them to the available footprints according to the maximum likelihood (ML) criterion. Under the ML-rule, for a two-state system, it is shown that the probability that all the instances are matched correctly is minimized when the transition times are i.i.d. exponentially distributed. When the transition times are i.i.d. distributed, the ML-rule reduces to a minimum weight bipartite matching and reduces further to a first-in first-out match for a special class of distributions. For a multi-state model with an acyclic state transition digraph, a constructive proof shows that the ML-rule reduces to splicing the results of independent matching of many bipartite systems.

The deployment of converged services of TV, telephony, and Internet access over IP entails a significant initial investment for service providers. This investment is not only for the underlying network infrastructure but also for provisioning and managing vast data centers needed to provide sophisticated IP-based TV (IPTV) experience, including multiple camera views, live (broadcast) and on demand programming, etc., to a large number of viewers. Thus the service providers need to carefully plan and manage the IPTV service deployment to maximize the return-on-investment while providing a good quality of experience to the subscribers. In this paper, we develop a methodology to aid service providers to effectively plan for the staggered deployment of IPTV services in this fledgling market. We present the utility of this framework by demonstrating a planning tool developed from this framework.

The objectives of this paper are twofold. First, we introduce a novel policy language, called CIM-SPL (simple policy language for CIM) that complies with the CIM (common information model) Policy Model and fully incorporates CIM constructs. Currently, the CIM standards from distributed management task force (DMTF) include a policy model, but there is no satisfactory way to render this policy model. CIM-SPL is a language that has been defined for this purpose. Second, we address design and implementation issues for policy languages in general, and for CIM-SPL in particular. The design of CIM-SPL was inspired by our previous experiences in designing various policy languages (e.g., PDL from Bell Laboratories, and ACPL from IBM) and lessons learned from studying other well-known policy languages (e.g., Ponder from Imperial College). We will discuss our design choices, evaluating the pros and cons of various alternatives. The ideas presented in this paper are meant to shed light on our design decisions, and provide guidance for those who want to build a CIM-based policy system or some other policy system in the future.

Hardware manufacturers are increasingly outsourcing their IC fabrication work overseas due to their much lower cost structure. This poses a significant security risk for ICs used for critical military and business applications. Attackers can exploit this loss of control to substitute Trojan ICs for genuine ones or insert a Trojan circuit into the design or mask used for fabrication. We show that a technique borrowed from side-channel cryptanalysis can be used to mitigate this problem. Our approach uses noise modeling to construct a set of fingerprints/or an IC family utilizing side- channel information such as power, temperature, and electromagnetic (EM) profiles. The set of fingerprints can be developed using a few ICs from a batch and only these ICs would have to be invasively tested to ensure that they were all authentic. The remaining ICs are verified using statistical tests against the fingerprints. We describe the theoretical framework and present preliminary experimental results to show that this approach is viable by presenting results obtained by using power simulations performed on representative circuits with several different Trojan circuitry. These results show that Trojans that are 3-4 orders of magnitude smaller than the main circuit can be detected by signal processing techniques. While scaling our technique to detect even smaller Trojans in complex ICs with tens or hundreds of millions of transistors would require certain modifications to the IC design process, our results provide a starting point to address this important problem.

The authors correct a mathematical equation contained in the correspondence "Multiple-antenna signal constellations for fading channels," previously published in the IEEE Transactions on Information Theory

The MIX technique forms the basis of many popular services that offer anonymity of communication in open and shared networks such as the Internet. In this paper, fundamental limits on the anonymity provided by the MIX technique are found by considering two different settings. First, we consider an information theoretic setting to determine the extent of information inherent in observations of the traffic passing through the MIX. We show that if the size of sender anonymity sets is less than the total user population, the information contained in traffic observations is sufficient to deduce all communication relationships between senders and receivers using the MIX. More importantly, we show that even if every user sends a message in each communication round, it is possible to compromise the anonymity significantly. We precisely characterize the extent of compromised anonymity in each case. In the second setting, we assume that the attacker has unlimited computational resources and is free to choose any attack algorithm. We derive tight upper and lower bounds on the minimum number of observations required to deduce all recipient peer-partners of a targeted user. The analysis done in these two settings reveals many discrete mathematical structures inherent in anonymity sets, and the intuition gained from these structures can be used when designing or using a MIX based anonymity technique.

In this paper, we present a novel policy middleware architecture for managing IT systems and applications that span multiple networks and administrative domains. The proposed policy middleware provides a standard infrastructure for the creation, storage, distribution, and execution of policies, and helps in reducing the cost of making IT systems policy-aware. In particular, we focus on three aspects of the proposed policy middleware that help in making the middleware fully general: (1) a platform-neutral and extensible specification of policies; (2) the local ratification of policies, which lets system administrators accept, reject, or flag an incoming policy; and (3) the transformation of policies, which allows system administrators to transform incoming policies to match their local environment. We present our experience in building an application on the proposed middleware to audit the configuration of a storage area network. We also present performance results from a prototype and show that our policy middleware design can scale to handle a large number of policies.

As businesses continue to grow their World Wide Web presence, it is becoming increasingly vital for them to have quantitative measures of the mean client perceived response times of their web services. We present Certes (CliEnt Response Time Estimated by the Server), an online server-based mechanism that allows web servers to estimate mean client perceived response time, as if measured at the client. Certes is based on a model of TCP that quantifies the effect that connection drops have on mean client perceived response time by using three simple server-side measurements: connection drop rate, connection accept rate and connection completion rate. The mechanism does not require modifications to HTTP servers or web pages, does not rely on probing or third party sampling, and does not require client-side modifications or scripting. Certes can be used to estimate response times for any web content, not just HTML. We have implemented Certes and compared its response time estimates with those obtained with detailed client instrumentation. Our results demonstrate that Certes provides accurate server-based estimates of mean client response times in HTTP 1.0/1.1 environments, even with rapidly changing workloads. Certes runs online in constant time with very low overhead. It can be used at websites and server farms to verify compliance with service level objectives.

In recent years, the problem of indexing mobile objects has assumed great importance because of its relevance to a wide variety of applications. Most previous results in this area have proposed indexing schemes for objects with linear trajectories in one or two dimensions. In this paper, we present methods for indexing objects with nonlinear trajectories. Specifically, we identify a useful condition called the convex hull property and show that any trajectory satisfying this condition can be indexed by storing a careful representation of these objects in a traditional index structure. Since a wide variety of relevant nonlinear trajectories satisfy this condition, our result significantly expands the class of trajectories for which nearest neighbor indexing schemes can be devised. We also show that even though many non-linear trajectories do not satisfy the convex hull condition, an approximate representation can often be found which satisfies it. We discuss examples of techniques which can be utilized to find representations that satisfy the convex hull property. We present empirical results to demonstrate the effectiveness of our indexing method.

The goal of anonymity providing techniques is to preserve the privacy of users, who has communicated with whom, for how long, and from which location, by hiding traffic information. This is accomplished by organizing additional traffic to conceal particular communication relationships and by embedding the sender and receiver of a message in their respective anonymity sets. If the number of overall participants is greater than the size of the anonymity set and if the anonymity set changes with time due to unsynchronized participants, then the anonymity technique becomes prone to traffic analysis attacks. We are interested in the statistical properties of the disclosure attack, a newly suggested traffic analysis attack on the MIXes. Our goal is to provide analytical estimates of the number of observations required by the disclosure attack and to identify fundamental (but avoidable) 'weak operational modes' of the MIXes and thus to protect users against a traffic analysis by the disclosure attack.

The paper contains a systematic investigation of practical coding strategies for noncoherent communication over fading channels, guided by explicit comparisons with information-theoretic benchmarks. Noncoherent reception is interpreted as joint data and channel estimation, assuming that the channel is time varying and a priori unknown. We consider iterative decoding for a serial concatenation of a standard binary outer channel code with an inner modulation code amenable to noncoherent detection. For an information rate of about 1/2 bit per channel use, the proposed scheme, using a quaternary phase-shift keying (QPSK) alphabet, provides performance within 1.6-1.7 dB of Shannon capacity for the block fading channel, and is about 2.5-3 dB superior to standard differential demodulation in conjunction with an outer channel code. We also provide capacity computations for noncoherent communication using standard phase-shift keying (PSK) and quadrature amplitude modulation (QAM) alphabets; comparing these with the capacity with unconstrained input provides guidance as to the choice of constellation as a function of the signal-to-noise ratio. These results imply that QPSK suffices to approach the unconstrained capacity for the relatively low information and fading rates considered in our performance evaluations, but that QAM is superior to PSK for higher information or fading rates, motivating further research into efficient noncoherent coded modulation with QAM alphabets.

As businesses continue to grow their World Wide Web presence, it is becoming increasingly vital for them to have quantitative measures of the client perceived response times of their web services. We present Certes (CliEnt Response Time Estimated by the Server), an online server-based mechanism for web servers to measure client perceived response time, as if measured at the client. Certes is based on a model of TCP that quantifies the effect that connection drops have on perceived client response time, by using three simple server-side measurements: connection drop rate, connection accept rate and connection completion rate. The mechanism does not require modifications to http servers or web pages, does not rely on probing or third party sampling, and does not require client-side modifications or scripting. Certes can be used to measure response times for any web content, not just HTML. We have implemented Certes and compared its response time measurements with those obtained with detailed client instrumentation. Our results demonstrate that Certes provides accurate server-based measurements of client response times in HTTP 1.0/1.1 [14] environments, even with rapidly changing workloads. Certes runs online in constant time with very low overhead. It can be used at web sites and server farms to verify compliance with service level objectives.

The increasing ability to track and collect large amounts of data with the use of current hardware technology has lead to an interest in the development of data mining algorithms which preserve user privacy. A recently proposed technique addresses the issue of privacy preservation by perturbing the data and reconstructing distributions at an aggregate level in order to perform the mining. This method is able to retain privacy while accessing the information implicit in the original attributes. The distribution reconstruction process naturally leads to some loss of information which is acceptable in many practical situations. This paper discusses an Expectation Maximization (EM) algorithm for distribution reconstruction which is more effective than the currently available method in terms of the level of information loss. Specifically, we prove that the EM algorithm converges to the maximum likelihood estimate of the original distribution based on the perturbed data. We show that when a large amount of data is available, the EM algorithm provides robust estimates of the original distribution. We propose metrics for quantification and measurement of privacy-preserving data mining algorithms. Thus, this paper provides the foundations for measurement of the effectiveness of privacy preserving data mining algorithms. Our privacy metrics illustrate some interesting results on the relative effectiveness of different perturbing distributions.

In this correspondence, we show that the problem of designing efficient multiple-antenna signal constellations for fading channels can be related to the problem of finding packings with large minimum distance in the complex Grassmannian space. We describe a numerical optimization procedure for finding good packings in the complex Grassmannian space and report the best signal constellations found by this procedure. These constellations improve significantly upon previously known results.

This paper analyzes phase trajectories and fixed points of the turbo decoding algorithm as a function of the signal-to-noise ratio (SNR). By exploiting the large length of turbo codes, the turbo decoding algorithm is treated as a single-parameter dynamical system, parameterized (approximately) by the SNR. This parameterization, along "with" extensive simulations at practical SNRs and asymptotic analysis as SNR goes to zero and infinity, is used to subdivide the entire SNR range into three regions with the "waterfall region" in the middle. The turbo decoding algorithm has distinctive phase trajectories and convergence properties in these three SNR regions. This paper also investigates existence and properties of fixed points in these SNR regions. The main fixed points of the turbo decoding algorithm are classified into two categories. In a wide range of SNRs (corresponding to bit-error rates less than 10/sup -1/), the decoding algorithm has "unequivocal" fixed points which correspond to mostly correct decisions on the information bits. Within this range, toward the lower values of SNR, there is another fixed point which corresponds to many erroneous decision on the information bits. Fixed points of this type are referred to as "indecisive" fixed points. It turns out that the indecisive fixed points bifurcate and disappear for SNRs in the waterfall region. This paper associates the qualitative transition of phase trajectories in the waterfall region to the bifurcation of indecisive fixed points. These bifurcations also explain empirically observed quasi-periodic and periodic phase trajectories of the turbo decoding algorithm.

We present a detailed analysis of generalized minimum distance (GMD) decoding algorithms for Euclidean space codes. In particular, we completely characterize GMD decoding regions in terms of receiver front-end properties. This characterization is used to show that GMD decoding regions have intricate geometry. We prove that although these decoding regions are polyhedral, they are essentially always nonconvex. We furthermore show that conventional performance parameters, such as error-correction radius and effective error coefficient, do not capture the essential geometric features of a GMD decoding region, and thus do not provide a meaningful measure of performance. As an alternative, probabilistic estimates of, and upper bounds upon, the performance of GMD decoding are developed. Furthermore, extensive simulation results, for both low-dimensional and high-dimensional sphere-packings, are presented. These simulations show that multilevel codes in conjunction with multistage GMD decoding provide significant coding gains at a very low complexity. Simulated performance, in both cases, is in remarkably close agreement with our probabilistic approximations.

Given a 2D-symmetric lattice /spl Lambda/, it was conjectured by Forney (1989) that the projection of the Voronoi region R(/spl Lambda/) onto two coordinates equals the Voronoi region of the constituent 2D-sublattice /spl Lambda//spl nu//sub 2/. We present a three-dimensional counterexample.>