Search

The vast majority of today&rsquo, s mobile malware targets Android devices. An important task of malware analysis is the classification of malicious samples into known families. In this paper, we propose AndroDFA (DFA, detrended fluctuation analysis): an approach to Android malware family classification based on dynamic analysis of resource consumption metrics available from the proc file system. These metrics can be easily measured during sample execution. From each malware, we extract features through detrended fluctuation analysis (DFA) and Pearson&rsquo, s correlation, then a support vector machine is employed to classify malware into families. We provide an experimental evaluation based on malware samples from two datasets, namely Drebin and AMD. With the Drebin dataset, we obtained a classification accuracy of 82%, comparable with works from the state-of-the-art like DroidScribe. However, compared to DroidScribe, our approach is easier to reproduce because it is based on publicly available tools only, does not require any modification to the emulated environment or Android OS, and by design, can also be used on physical devices rather than exclusively on emulators. The latter is a key factor because modern mobile malware can detect the emulated environment and hide its malicious behavior. The experiments on the AMD dataset gave similar results, with an overall mean accuracy of 78%. Furthermore, we made the software we developed publicly available, to ease the reproducibility of our results.

The skyrocketing growth rate of new malware brings novel challenges to protect computers and networks. Discerning truly novel malware from variants of known samples is a way to keep pace with this trend. This can be done by grouping known malware in families by similarity and classifying new samples into those families. As malware and their families evolve over time, approaches based on classifiers trained on a fixed ground truth are not suitable. Other techniques use clustering to identify families, but they need to periodically re-cluster the whole set of samples, which does not scale well. A promising approach is based on incremental clustering, where periodically only yet unknown samples are clustered to identify new families, and classifiers are retrained accordingly. However, the latter solutions usually are not able to immediately react and identify new malware families. In this paper, we propose MalFamAware, a novel approach to malware family identification based on an online clustering algorithm, namely BIRCH, which efficiently updates clusters as new samples are fed without requiring to re-scan the entire dataset. MalFamAwareis able to both classify new malware in existing families and identify new families at runtime. We present experimental evaluations where MalFamAware outperforms both total re-clustering and incremental clustering solutions in terms of accuracy and time. We also compare our solution with classifiers retrained over time, obtaining better accuracy, in particular when samples belong to yet unknown families.

One of the main characteristics that today makes cloud services so popular is their ability to be elastic, i.e., they can adapt their provisioning to variable workloads, thus increasing resource utilization and reducing operating costs. At the core of any elastic service lies an automatic scaling mechanism that drives provisioning on the basis of a given strategy. In this paper we propose PASCAL , an architecture for Proactive Auto-SCALing of generic distributed services. PASCAL combines a proactive approach, to forecast incoming workloads, with a profiling system, to estimate required provision. Scale-in/out operations are decided according to an application-specific strategy, which aims at provisioning the minimum number of resources needed to sustain the foreseen workload. The main novelties introduced with PASCAL architecture are: (i) a strategy to proactively auto-scale a distributed stream processing system (namely, Apache Storm) with the aim of load balancing operators through an accurate system performance estimation model, and (ii) a strategy to proactively auto-scale a distributed datastore (namely, Apache Cassandra), focused on how to choose when executing scaling actions on the basis of the time needed for the activation/deactivation of storage nodes so as to have the configuration ready when needed. We provide a prototype implementation of PASCAL for both use cases and, through an experimental evaluation conducted on a private cloud, we validate our approach and demonstrate the effectiveness of the proposed strategies in terms of saved resources and response time.

A distributed event notification service (ENS) is at the core of modern messaging infrastructures providing applications with scalable and robust publish/subscribe communication primitives. Such ENSs can route events toward subscribers using multiple paths with different lengths and latencies. As a consequence, subscribers can receive events out of order. In this paper, we propose a novel solution for ordered notifications on top of an existing distributed topic-based ENS. Our solutions guarantees that each pair of events published in the system will be notified in the same order to all their target subscribers independently from the topics they are published in. It endows a distributed timestamping mechanism based on a multistage sequencer that produces timestamps whose size is dynamically adjusted to accommodate changing subscriptions in the system. An extensive experimental evaluation based on a prototype implementation shows that the timestamping mechanism is able to scale from several points of view (i.e., number of publisher and subscribers, event rate). Furthermore, it shows how the deployment flexibility of our solution makes it perform better in terms of timestamp size and timestamp generation latency when the system load exhibits geographic topic popularity, that is, matching subscriptions and publications are geographically clustered. This makes our solution particularly well suited to be deployed in geo-distributed infrastructures.

Today’s business workflows are very likely to include batch computations that periodically analyze subsets of data within specific time ranges to provide strategic information for stakeholders and other interested parties. The frequency of these batch computations provides an effective measure of data analytics freshness available to decision makers. Nevertheless, the typical amounts of data to elaborate in a batch are so large that a computation can take very long. Considering that usually a new batch starts when the previous one has completed, the frequency of such batches can thus be very low. In this paper we propose a model for batch processing based on overlapping sliding time windows that allows to increase the frequency of batches. The model is well suited to scenarios (e.g., financial, security etc.) characterized by large data volumes, observation windows in the order of hours (or days) and frequent updates (order of seconds). The model introduces multiple metrics whose aim is reducing the latency between the end of a computation time window and the availability of results, increasing thus the frequency of the batches. These metrics specifically take into account the organization of input data to minimize its impact on such latency. The model is then instantiated on the well-known Hadoop platform, a batch processing engine based on the MapReduce paradigm, and a set of strategies for efficiently arranging input data is described and evaluated.

The vast majority of today's mobile malware targets Android devices. This has pushed the research effort in Android malware analysis in the last years. An important task of malware analysis is the classification of malware samples into known families. Static malware analysis is known to fall short against techniques that change static characteristics of the malware (e.g. code obfuscation), while dynamic analysis has proven effective against such techniques. To the best of our knowledge, the most notable work on Android malware family classification purely based on dynamic analysis is DroidScribe. With respect to DroidScribe, our approach is easier to reproduce. Our methodology only employs publicly available tools, does not require any modification to the emulated environment or Android OS, and can collect data from physical devices. The latter is a key factor, since modern mobile malware can detect the emulated environment and hide their malicious behavior. Our approach relies on resource consumption metrics available from the proc file system. Features are extracted through detrended fluctuation analysis and correlation. Finally, a SVM is employed to classify malware into families. We provide an experimental evaluation on malware samples from the Drebin dataset, where we obtain a classification accuracy of 82%, proving that our methodology achieves an accuracy comparable to that of DroidScribe. Furthermore, we make the software we developed publicly available, to ease the reproducibility of our results., Comment: Extended Version

Knowledge base (KB) sharing among parties has been proven to be beneficial in several scenarios. However such sharing can arise considerable privacy concerns depending on the sensitivity of the information stored in each party's KB. In this paper, we focus on the problem of exporting a (part of a) KB of a party towards a receiving one. We introduce a novel solution that enables parties to export data in a privacy-preserving fashion, based on a probabilistic data structure, namely the \emph{count-min sketch}. With this data structure, KBs can be exported in the form of key-value stores and inserted into a set of count-min sketches, where keys can be sensitive and values are counters. Count-min sketches can be tuned to achieve a given key collision probability, which enables a party to deny having certain keys in its own KB, and thus to preserve its privacy. We also introduce a metric, the γ-deniability (novel for count-min sketches), to measure the privacy level obtainable with a count-min sketch. Furthermore, since the value associated to a key can expose to linkage attacks, noise can be added to a count-min sketch to ensure controlled error on retrieved values. Key collisions and noise alter the values contained in the exported KB, and can affect negatively the accuracy of a computation performed on the exported KB. We explore the tradeoff between privacy preservation and computation accuracy by experimental evaluations in two scenarios related to malware detection.

Preserving anonymity and privacy of customer actions within a complex software system, such as a cloud computing system, is one of the main issues that should be addressed to boost private computation outsourcing. In this paper, we propose a coordination paradigm, namely oblivious assignment with m slots of a resource R (with m ≥ 1 ), allowing processes to compete in order to get a slot of R , while ensuring at the same time both fairness in the assignment of resource slots and that no process learns which slot of R is assigned to a specific process. We present a distributed algorithm solving oblivious assignment with m slots within a distributed system, assuming (1) a bounded number of crash failures f , (2) the existence of at least f + 2 honest processes, and (3) m ≤ n (where n is the number of processes). The algorithm is based on a rotating token paradigm and its correctness is formally proved. A probabilistic analysis of the average waiting time before getting a slot is also provided.

This paper studies the problem of answering aggregation queries, satisfying the interval validity semantics, in a distributed system prone to continuous arrival and departure of participants. The interval validity semantics states that the query answer must be calculated considering contributions of at least all processes that remained in the distributed system for the whole query duration. Satisfying this semantics in systems experiencing unbounded churn is impossible due to the lack of connectivity and path stability between processes. This paper presents a novel architecture, namely Virtual Tree, for building and maintaining a structured overlay network with guaranteed connectivity and path stability in settings characterized by bounded churn rate. The architecture includes a simple query answering algorithm that provides interval valid answers. The overlay network generated by the Virtual Tree architecture is a tree-shaped topology with virtual nodes constituted by clusters of processes and virtual links constituted by multiple communication links connecting processes located in adjacent virtual nodes. We formally prove a bound on the churn rate for interval valid queries in a distributed system where communication latencies are bounded by a constant unknown by processes. Finally, we carry out an extensive experimental evaluation that shows the degree of robustness of the overlay network generated by the virtual tree architecture under different churn rates.

Many security and software testing applications require checking whether certain properties of a program hold for any possible usage scenario. For instance, a tool for identifying software vulnerabilities may need to rule out the existence of any backdoor to bypass a program's authentication. One approach would be to test the program using different, possibly random inputs. As the backdoor may only be hit for very specific program workloads, automated exploration of the space of possible inputs is of the essence. Symbolic execution provides an elegant solution to the problem, by systematically exploring many possible execution paths at the same time without necessarily requiring concrete inputs. Rather than taking on fully specified input values, the technique abstractly represents them as symbols, resorting to constraint solvers to construct actual instances that would cause property violations. Symbolic execution has been incubated in dozens of tools developed over the last four decades, leading to major practical breakthroughs in a number of prominent software reliability applications. The goal of this survey is to provide an overview of the main ideas, challenges, and solutions developed in the area, distilling them for a broad audience. The present survey has been accepted for publication at ACM Computing Surveys. If you are considering citing this survey, we would appreciate if you could use the following BibTeX entry: http://goo.gl/Hf5Fvc, Comment: This is the authors pre-print copy. If you are considering citing this survey, we would appreciate if you could use the following BibTeX entry: http://goo.gl/Hf5Fvc

Many organizations today still manage mid or large in-house data centers that require very expensive maintenance efforts, including fault detection. Common monitoring frameworks used to quickly detect faults are complex to deploy/maintain, expensive, and intrusive as they require the installation of probes on monitored hw/sw to collect raw data. Such intrusiveness can be problematic as it imposes installation/management overhead and may interfere with security/privacy policies. In this paper we introduce NIRVANA, a novel monitoring system for fault detection that works at rack-level and is (i) non-intrusive, i.e., it does not require the installation of software probes on the hosts to be monitored and (ii) black-box, i.e., agnostic with respect to monitored applications. At the core of our solution lies the observation that aggregated features that can be monitored at rack-level in a non-intrusive and black-box way, show predictable behaviors while the system works in both fault-free and faulty states, it is therefore possible to detect and identify faults by monitoring and analyzing any perturbations to these behaviors. An extensive experimental evaluation shows that non-intrusiveness does not significantly hamper the fault detection capabilities of the monitoring system, thus validating our approach.

Low-latency data delivery is an important requirement for achieving effective monitoring through wireless sensor networks. When sensor nodes employ duty cycling, sending a message along the shortest path, however, does not necessarily result in minimum delay. In this paper, we first study the lowest latency path problem, i.e., the characteristics of a path with minimum delay that connects a source node to the sink under random duty cycling nodes. Then, we propose a forwarding protocol based on biased random walks, where nodes only use local information about neighbors and their next active period to make forwarding decisions. We refer to this as lukewarm potato forwarding. Our analytical model and simulation experiments show that it is possible to reduce path latency without significantly increasing the number of transmissions (energy efficiency) needed to deliver the message to the destination. In particular, although deviating from the shortest path requires additional transmissions, and hence, higher energy consumption, this increase is compensated by a lighter duty cycle. Our experiments show that, overall, we can save up to 15 percent of energy while obtaining the same data delivery delay as shortest path routing. Additionally, the proposed solution is tunable. By changing the value of just one threshold parameter, it can be tuned to operate anywhere in the continuum from hot potato/random walk forwarding protocol to a deterministic shortest path forwarding protocol.

An in-depth review of service discovery protocols (SDPs) in multihop mobile ad hoc networks analyzes SDP building blocks and determines SDP suitability based on architecture, mobility, and network size. Mobile ad hoc networks (manets) include a variety of devices, such as cell phones, PDAs, laptops, and other relatively larger devices. These devices can move at high or low speeds or even remain stationary, entering and leaving the system when switched on or off. Such a variety of devices also offers a variety of services. A service is any tangible or intangible facility a device provides that can be useful for any other device. Services comprise those for software and hardware. A software service, for example, can be a simple file, such as an MP3 file, or a software implementation of an algorithm, such as converting one audio file format to another. A hardware service, for example, can be a printer that a mobile device can use wirelessly. To benefit from these services, a device must be able to both locate them in the network and invoke them. Service discovery protocols (SDPs) enable these capabilities.

Peer-to-peer systems (P2P) have become a popular technique to design large-scale distributed applications in unmanaged inter-domain settings, such as file sharing or chat systems, thanks to their capabilities to self-organize and evenly split the load among peers. Recently, enterprises owning a large IT hardware and software infrastructure started looking at these P2P technologies as a means both to reduce costs and to help their technical divisions to manage huge number of devices characterized by a high level of cooperation and a relatively low churn. Gaining a quick exclusive access to the system for maintenance or auditing purposes in these enterprise infrastructures is a fundamental operation to be implemented. Conversely, this kind of operation is usually not an issue in the previously mentioned inter-domain setting, where peers are inherently independent and cannot be managed. In the context of classical distributed applications, quorum systems have been considered as a major building block for implementing many paradigms, from distributed mutual exclusion to data replication management. In this paper, we explore how to architect decentralized protocols implementing quorum systems in Distributed Hash Table based cooperative P2P networks. Our results show that quorum systems taken ''as is'' from the literature and directly applied to such networks are not scalable due to the high load imposed onto the underlying network. This paper introduces some design principles for both quorum systems and protocols using them that boost their scalability and performance. These design principles consist in a dynamic and decentralized selection of quorums and in the exposition and exploitation of internals of the DHT. As a third design principle it is also shown how to redesign quorum systems to enable efficient decentralization. We show that by combining these design principles in a cooperative environment with relatively low churn it is possible to minimize the imposed load in the system, in terms of sites contacted to obtain a quorum, and the latency of quorum acquisition.

In safety-critical systems such as Air Traffic Control system, SCADA systems, Railways Control Systems, there has been a rapid transition from monolithic systems to highly modular ones, using off-the-shelf hardware and software applications possibly developed by different manufactures. This shift increased the probability that a fault occurring in an application propagates to others with the risk of a failure of the entire safety-critical system. This calls for new tools for the on-line detection of anomalous behaviors of the system, predicting thus a system failure before it happens, allowing the deployment of appropriate mitigation policies.The paper proposes a novel architecture, namely CASPER, for online failure prediction that has the distinctive features to be (i) black-box: no knowledge of applications internals and logic of the system is required (ii) non-intrusive: no status information of the components is used such as CPU or memory usage; The architecture has been implemented to predict failures in a real Air Traffic Control System. CASPER exhibits high degree of accuracy in predicting failures with low false positive rate. The experimental validation shows how operators are provided with predictions issued a few hundred of seconds before the occurrence of the failure. Non-intrusive and black box effective online failure prediction.We monitor network traffic, only, to perform online failure prediction.Application agnostic: no knowledge of application logic is required.We use complex event processing to produce a representation of the system state.We use hidden Markov models in order to create a state recognizer.

Keeping strongly consistent the state of the replicas of a software service deployed across a distributed system prone to crashes and with highly unstable message transfer delays (e.g., the Internet), is a real practical challenge. The solution to this problem is subject to the FLP impossibility result, and thus there is a need for "long enough" periods of synchrony with time bounds on process speeds and message transfer delays to ensure deterministic termination of any run of agreement protocols executed by replicas. This behavior can be abstracted by a partially synchronous computational model. In this setting, before reaching a period of synchrony, the underlying network can arbitrarily delay messages and these delays can be perceived as false failures by some timeout-based failure detection mechanism leading to unexpected service unavailability. This paper proposes a fully distributed solution for active software replication based on a three-tier software architecture well-suited to such a difficult setting. The formal correctness of the solution is proved by assuming the middle-tier runs in a partially synchronous distributed system. This architecture separates the ordering of the requests coming from clients, executed by the middle-tier, from their actual execution, done by replicas, i.e., the end-tier. In this way, clients can show up in any part of the distributed system and replica placement is simplified, since only the middle-tier has to be deployed on a well-behaving part of the distributed system that frequently respects synchrony bounds. This deployment permits a rapid timeout tuning reducing thus unexpected service unavailability

During the last two decades the design and development of total order (TO) communications has been one of the main research topics in dependable distributed computing. The huge amount of research work has produced several TO specifications and a wide variety of TO implementations with different guarantees whose differences are often left hidden or unclear. This paper presents a systematic classification of six distinct TO specifications based on a well-defined formal framework. The classification allows us (i) to define in a formal way the differences among the behaviors of faulty and correct processes admitted by each specification, and (ii) to easily match TO implementations with respect to their enforced specification. The classification is applied to study the properties of eight variations of TO implementations based on a fixed sequencer given in a well-known context, namely primary component group communication systems.

The most critical property exhibited by a heavy-tailed workload distribution (found in many WWW workloads) is that a very small fraction of tasks make up a large fraction of the workload, making the load very difficult to distribute in a distributed system. Load balancing and load sharing are the two predominant load distribution strategies used in such systems. Load sharing generally has better response time than load balancing because the latter can exhibit excessive overheads in selecting servers and partitioning tasks. We therefore further explored the least-loaded-first (LLF) load sharing approach and found two important limitations: (a) LLF does not consider the order of processing, and (b) when it assigns a task, LLF does not consider the processing capacity of servers. The high task size variation that exists in heavy-tailed workloads often causes smaller tasks to be severely delayed by large tasks. This paper proposes a size-based approach, called the least flow-time first (LFF-SIZE), which reduces the delay caused by size variation while maintaining a balanced load in the system. LFF-SIZE takes the relative processing time of a task into account and dynamically assigns a task to the fittest server with a lighter load and higher processing capacity. LFF-SIZE also uses a multi-section queue to separate larger tasks from smaller ones. This arrangement effectively reduces the delay of smaller tasks by larger ones as small tasks are given a higher priority to be processed. The performance results performed on the LFF-SIZE implementation shows a substantial improvement over existing load sharing and static size-based approaches under realistic heavy-tailed workloads.

In cooperative information systems, the quality of data exchanged and provided by different data sources is extremely important. A lack of attention to data quality can imply data of low quality to spread all over the cooperative system. At the same time, improvement can be based on comparing data, correcting them and thus disseminating high quality data. In this paper, we present an architecture for managing data quality in cooperative information systems, by focusiag on two specific modules, the Data Quality Broker and the Quality Notification Service. The Data Quality Broker allows for querying and improving data quality values. The Quality Notification Service is specifically targeted to the dissemination of changes on data quality values.

Several mobile computing applications require that both the order and location of occurrence of events be taken into account during decision making. Thus, processes need to track the location of nodes and synchronize their clocks. The Global Positioning System can be employed to mimic a global virtual clock that keeps the local clocks of participating nodes in synchrony with each other. The global virtual clock in conjunction with a space–time vector can track the mobility of nodes. Nodes can prioritize resource requests on the basis of request time as well as the requester's distance from the resource. Two distributed mutual exclusion algorithms that employ the space–time vector are presented. The error in the estimates of a mobile node, due to clock drift, about the region in which other mobile nodes may be present is formulated. Various resource allocation policies can react differently to such errors leading to performance differences. However, every policy should ensure that resource allocation has the properties of safety, deadlock freedom, liveness, and fairness.

Enforcing strong replica consistency among a set of replicas of a service deployed across an asynchronous distributed system in the presence of crash failures is a real practical challenge. If each replica runs the consistency protocol bundled with the actual service implementation, this target cannot be achieved, as replicas need to be located over a partially synchronous distributed system to solve the distributed agreement problems underlying strong replica consistency.A three-tier architecture for software replication enables the separation of the replication logic, i.e. protocols and mechanisms necessary for managing software replication, from both clients and server replicas. The replication logic is embedded in a middle-tier that confines the need of partial synchrony and thus frees replica deployment.In this paper we first introduce the basic concepts underlying three-tier replication. Then we present the interoperable replication logic (IRL) architecture, a fault-tolerant CORBA compliant infrastructure. IRL exploits a three-tier approach to replicate stateful deterministic CORBA objects and allows object replicas to run on object request brokers from different vendors. A description of an IRL prototype developed in our department is proposed along with an extensive performance analysis.

Interceptors are an emerging middleware technology enabling the addition of specific network-oriented capabilities to distributed applications. By exploiting interceptors, developers can register code within interception points, extending the basic middleware mechanisms with specific functionality, e.g. authentication, flow control, caching, etc. Notably, these extensions can be achieved without modifying either the application or the middleware code. In this paper we report the results of our experiences with CORBA request portable interceptors. In particular, we point out (i) the basic mechanisms implementable by these interceptors, i.e. request redirection and piggybacking and (ii) we analyze their limitations. We then propose a proxy-based technique to overcome the interceptors' limitations. Successively, we present a performance analysis carried out on three Java-CORBA platforms currently implementing the portable interceptors specification. Finally, we conclude our work with a case study in which portable interceptors are used to implement the fault-tolerant CORBA client invocation semantic without impacting on the client application code and on the CORBA ORB. We also release fragments of Java code for implementing the described techniques. Copyright © 2003 John Wiley & Sons, Ltd.

In this paper we propose a monitoring system of a data center that is able to infer when the data center is getting into an anomalous behavior by analyzing the power consumption at each server and the data center network traffic. The monitoring system is non-intrusive in the sense that there is no need to install software on the data center servers. The monitoring architecture embeds two Elman Recurrent Networks (RNNs) to predict power consumed by each data center component starting from data center network traffic and viceversa. Results obtained along six mounts of experiments, within a data center, show that the architecture is able to classify anomalous system behaviors and normal ones by analyzing the error between the actual values of power consumption and network traffic and the ones inferred by the two RNNs.

In this paper we investigate the problem of counting the size of a network where processes are anonymous (i.e., they share the same identifier) and the network topology constantly changes controlled by an adversary able to look internal process states and add and remove edges in order to contrast the convergence of the algorithm to the correct count. It is easy to show that, if the adversary can generate graphs without any constraint on the connectivity (i.e. it can generate topologies where there exist nodes not able to influence the others), counting is impossible. In this paper we consider a synchronous round based computation and the dynamicity is governed by a worst-case adversary that generates a sequence of graphs, one for each round, with the only constraint that each graph must be connected (1-interval connectivity property). It has been conjectured that counting in a finite time against such adversary is impossible and the existing solutions consider that each process has some knowledge about network topologies generated by the adversary, i.e. at each round, each node has a degree lesser than D. Along the path of proving the validity (or not) of the conjecture, this paper presents an algorithm that counts in a finite time against the worst-case adversary assuming each process is equipped with an oracle. The latter provides a process at each round r with an estimation of the process degree in the graph generated by the adversary at round r. To the best of our knowledge, this is the first counting algorithm (terminating in a finite time) where processes exploit the minimal knowledge about the behavior of the adversary. Interestingly, such oracle can be implemented in a wide range of real systems.

Organizations must protect their information systems from a variety of threats. Usually they employ isolated defenses such as firewalls, intrusion detection and fraud monitoring systems, without cooperating with the external world. Organizations belonging to the same markets (e.g., financial organizations, telco providers) typically suffer from the same cyber crimes. Sharing and correlating information could help them in early detecting those crimes and mitigating the damages.The paper discusses the Semantic Room (SR) abstraction which enables the development of collaborative event-based platforms, on the top of Internet, where data from different information systems are shared, in a controlled manner, and correlated to detect and timely react to coordinated Internet-based security threats (e.g., port scans, botnets) and frauds. In order to show the flexibility of the abstraction, the paper proposes the design, implementation and validation of two SRs: an SR that detects inter-domain port scan attacks and an SR that enables an online fraud monitoring over the Italian territory. In both cases, the SRs use real data traces for demonstrating the effectiveness of the proposed approach. In the first SR, high detection accuracy and small detection delays are achieved whereas in the second, new fraud evidence and investigation instruments are provided to law enforcement agencies.

A global record (i.e. a set of local records, one for each process of an asynchronous computation) abstracts what is usually called global state, global checkpoint or global snapshot in particular problems. Consistent global records are important in many applications. This paper addresses the following question: “Given a set of local records, is it possible that these records belong to the same consistent global record?”. This question has been answered by Netzer and Xu in the particular context of message passing systems. This paper extends their result to a very general asynchronous computational model that encompasses shared memory systems and various message passing systems (with reliable or unreliable and point-to-point or multicast or broadcast communications).

In this paper, the correctness of the mutual exclusion algorithm proposed by Goscinski (J. Parallel Distribut. Comput.9(7), 77-82 (1990)), hereafter G, is discussed and its features are compared with other token-based algorithms already published. In particular, we show that G works correctly only using a communication system that guarantees a total ordering of messages, otherwise it is incorrect. We further give a modified version of G, hereafter BCC, and show that BCC is actually a simple modification of the Suzuki-Kasami algorithm (ACM Trans. Comput. Systems3(5), 344-349 (1985)).

This paper introduces a novel approach to failure prediction for mission critical distributed systems that has the distinctive features to be black-box, non-intrusive and online. The approach combines Complex Event Processing (CEP) and Hidden Markov Models (HMM) so as to analyze symptoms of failures that might occur in the form of anomalous conditions of performance metrics identified for such purpose. The paper describes an architecture named CASPER, based on CEP and HMM, that relies on sniffed information from the communication network of a mission critical system, only, for predicting anomalies that can lead to software failures. An instance of CASPER has been implemented, trained and tuned to monitor a real Air Traffic Control (ATC) system. An extensive experimental evaluation of CASPER is presented. The obtained results show (i) a very low percentage of false positives over both normal and under stress conditions, and (ii) a sufficiently high failure prediction time that allows the system to apply appropriate recovery procedures.

Large enterprises are nowadays complex interconnected software systems spanning over several domains. This new dimension makes difficult for enterprises the task of enabling efficient security defenses. This paper addresses the problem of detecting inter-domain stealthy port scans and proposes an architecture of an Intrusion Detection System which uses, for such purpose, an open source Complex Event Processing engine named Esper. Esper provides low cost of ownership and high flexibility. The architecture consists of software sensors deployed at different enterprise domains. Each sensor sends events to the Esper event processor for correlation. We implemented an algorithm for the detection of interdomain SYN port scans named Rank-based SYN (R-SYN) port scan detection algorithm. It combines and adapts three detection techniques in order to obtain a unique global statement about the malicious behavior of host activities. An evaluation of the accuracy of our approach has been carried out using several traces, some of which including original traffic dumps, some others altered by injecting packets that simulate port scan activities. Accuracy results show that our algorithm is able to produce a list of scanners characterized by high detection and low false positive rates.

International audience; Consider a group of peers, an ideal random peer sampling service should return a peer, which is a uniform independent random sample of the group. This paper focuses on the implementation and analysis of a peer sampling service based on symmetric view shuffling, where each peer is equipped with a local view of size c, representing a uniform random sample of size c of the whole system. To this end, pairs of peers regularly and continuously swap a part of their local views (shuffle operation). The paper provides the following formal proofs: (i) starting from any non-uniform distribution of peers in the peers' local views, after a sequence of pairwise shuffle operations, each local view eventually represents a uniform sample of size c; (ii) once previous property holds, any successive sequence of shuffle operations does not modify this uniformity property and (iii) a lower bound for convergence speed. This paper also presents some numerical results concerning the speed of convergence to uniform samples of the local views.

In this paper, we present Esteem (Emergent Semantics and cooperaTion in multi-knowledgE EnvironMents), a community-based P2P platform for supporting semantic collaboration among a set of independent peers, without prior reciprocal knowledge and no predefined relationships. Goal of Esteem is to go beyond the existing state-of-the-art solutions for P2P knowledge sharing and to provide an integrated platform for both data and service discovery. A distinguishing feature of Esteem is the use of semantic communities to explicitly give shape to the collective knowledge and expertise of peer groups with similar interests. Key techniques of Esteem will be presented in the paper and concern: shuffling-based communication, ontology and service matchmaking, context management, and quality-aware data integration. An application example of data and service discovery in the health-care domain will be presented, by also discussing results of system and user evaluation.

This paper introduces a shared object, namely a set object that allows processes to add and remove values as well as take a snapshot of its content. A new consistency condition suited to such an object is introduced. This condition, named value-based sequential consistency, is weaker than linearizability. The paper also addresses the construction of a set object in a synchronous anonymous distributed system where participants can continuously join and leave the system. Interestingly, the protocol is proved correct under the assumption that some constraint on the churn is satisfied. This shows that the notion of "provably correct software" can be applied to dynamic systems.

In the present global society, information has to be exchangeable in open and dynamic environments, where interacting users do not necessarily share a common understanding of the world at hand. This is particularly true in P2P scenarios, where millions of autonomous users (peers) need to cooperate by sharing their resources (such as data and services). We propose the Esteem approach (Emergent Semantics and cooperaTion in multi-knowledgE EnvironMents), where a comprehensive framework and a platform for data and service discovery in P2P systems are proposed, with advanced solutions for trust and quality-based data management, P2P infrastructure definition, query processing and dynamic service discovery in a context-aware scenario. In Esteem, semantic communities are built around declared interests in the form of manifesto ontologies and their autonomous nature is preserved by allowing a shared semantics to naturally emerge from the peer interactions. Inside the borders of semantic communities data and services are discovered, queried and invoked in a resource sharing scenario, where the context in which users interoperate and the trust of exchanged information are also relevant aspects to take into account.

Utility computing can occur at different levels. Prom Software- as-a-Service (SaaS) paradigm, Desktop-as-a-Service (DaaS) paradigm can be derived: desktops can be transformed into a cost-effective, scalable and comfortable subscription service. In VDD, desktop virtual machines are instantiated on a server and then provided to clients as a whole, on demand, across a network. Since the first release and publication, new features have been implemented and performance improvements achieved. As visualization holds a critical role in the system, research and tests have been done for implementing the best virtualization solution. A comprehensive performance analysis is presented, depicting results that encourage to go on with the research and towards a real-life use. Operational costs analysis showed further economic and ecological advantages. The possibility to project operating systems not natively supporting the Xorg X11 has been introduced, opening the way to the projection of widespread though proprietary operating systems.

Recently, enterprises owning a large IT hardware and software infrastructure have started looking at Peer-to-peer technologies as a mean both to reduce costs and to help their technical divisions to manage huge number of devices characterized by a high level of cooperation and a relatively low churn. Obtaining the complete and exclusive control of the system for maintenance or auditing purposes in these enterprise infrastructures is a fundamental operation to be implemented. In the context of classical distributed applications, quorum systems have been considered as a major building block for implementing many paradigms, from distributed mutual exclusion to data replication management. In this paper, we explore how to architect decentralized protocols implementing quorum systems in Distributed Hash Table based cooperative P2P networks. This paper introduces some design principles for both quorum systems and protocols using them that boost their scalability and performance. These design principles consist of a dynamic and decentralized selection of quorums and in the exposure and exploitation of internals of the DHT. As a third design principle it is also shown how to redesign quorum systems to enable efficient decentralization.

Nowadays, there are many protocols able to cope with process crashes, but, unfortunately, a process crash represents only a particular faulty behavior. Handling tougher failures (e.g. sending omission failures, receive omission failures, arbitrary failures) is a real practical challenge due to malicious attacks or unexpected software errors. This is usually achieved either by changing, in an ad hoc manner, the code of a crash resilient protocol or by devising a new protocol from scratch. This paper proposes an alternative methodology to detect processes experiencing arbitrary failures. On this basis, it introduces the notions of liveness failure detector and safety failure detector as two independent software components. With this approach, the nature of failures experienced by processes becomes transparent to the protocol using the components. This methodology brings a few advantages: it makes possible to increase the resilience of a protocol designed in a crash failure context without changing its code by concentrating only on the design of a few well-specified components, and second, it clearly separates the task of designing the protocol from the task of detecting faulty processes, a methodological improvement. Finally, the feasibility of this approach is shown, by providing an implementation of liveness failure detectors and of safety failure detectors for two protocols: one solving the consensus, and the second solving the problem of global data computation.

Random walk (RW) based algorithms are often proposed to solve many problems in wireless networks. The implementation of such algorithms are usually done at the application layer so that many characteristics of the wireless transmissions are not exploited. In this paper, we show that we can greatly reduce the energy requirements to perform a RW by better exploiting the broadcast nature of the transmissions. We propose a broadcast based distributed next hop selection algorithm and compare it with a standard unicast based next hop selection algorithm. To evaluate the algorithms, we present a simulation study performed with ns-2. We found that the proposed algorithm is energy efficient, results in less source to destination delay, incurs less number of hops or transmissions and more robust in mobility as compared to a standard unicast based implementation of next hop selection algorithm for RW.

Communication-induced checkpointing protocols are mechanisms used to produce checkpoints and communication patterns which enjoy desirable properties, such as No-Z-Cycle (NZC). NZC guarantees that each checkpoint can be part of a global consistent checkpoint. It would be nice to define communication-induced checkpointing protocols that enforce NZC, adding a minimum number of checkpoints to remove all the Z-cycles from the distributed computation. In this paper, we prove that this is impossible by formulating the minimum Z-cycle removal (MinZCR) problem and showing that there are no online competitive protocols for it. Moreover, we prove that the problem of enforcing NZC with an optimal number of checkpoints is difficult even if the whole input instance is known because its decision version is NP-complete. Finally, we also prove that MinZCR is difficult to approximate: it is APX-hard and this implies that no polynomial time approximation scheme exists for the problem

Obsolete hardware can be effectively reused through intelligent software optimization, which is possible only when source code is available. Virtual Distro Dispatcher (VDD) is a system that produces virtual machines on a central server and projects them on a number of costless physical terminals. VDD is the result of an extreme software optimisation based on virtualization and terminal servers. VDD creates and projects Linux distros that are completely customizable and different from each other. They are virtual desktop machines that can be used for testing or developing and are completely controllable directly from each terminal. Memory consumption has been strongly reduced without sacrificing performances. Test results are encouraging to proceed with the research towards clustering.

Software replication of stateful services is typically implemented using two-tier architectures, in which clients directly interact with replicas running distributed agreement protocols for ensuring consistency. In general, performance of these protocols is sensitive to network delays, which might consequently reduce service availability. Therefore, in previous works we introduced three-tier software replication, in which agreement protocols run in an apposite tier (detached from clients and replicas) that can be independently deployed in a controlled and stable part of the network. In this paper, we analyze the performance of replication protocols implemented using two- and three-tier architectures using a simplified wide-area network model that considers two types of behaviors for channels, i.e., normal (small and predictable latency variations), and slow (high and unpredictable latency variations). This channel model is instantiated using traces of real Internet latencies measured sending HTTP requests to Internet web-sites at varying rates. Then, by exploiting traces, we simulate simplified versions of three replication protocols (i.e., active, passive, and three-tier replication), and we show how the end-to-end latency of each protocol is related to the number of slow channels. Results mainly demonstrate that the availability of a service replicated through a three-tier architecture is less affected from channel slow-downs.

SUMMARY This paper presents a formal framework of a distributed computation based on a publish/subscribesystem. The framework abstracts the system through two delays, namely the subscription/unsubscription delay and the diffusion delay. This abstraction allows one to model concurrent execution of publication and subscriptionoperations withoutwaitingfor the stabilityofthesystem state and to definea Liveness property which gives the conditions for the presence of a notification event in the global history of the system. This formal framework allows us to analytically define a measure of the effectiveness of a publish/subscribe system, which reflects the percentage of notifications guaranteed by the system to subscribers. A simulation study confirms the validity of the analytical measurements. Copyright c � 2005 John Wiley & Sons, Ltd.

Point-to-point transmissions represent a fundamental primitive in any communication network. Despite many proposals have appeared in the literature, providing an efficient implementation of such an abstraction in Mobile Ad Hoc Networks (MANETs) still remains an open issue. This paper proposes a probabilistic protocol for unicast packet delivery in a MANET. Unlike the classical routing protocols, in our proposal packet forwarding is not driven by a previously computed path. Rather, the nodes of the network exploit a set of routing meta-information (called hints ) to discover a path to the destination on-the-fly. This assure robustness against topological changes, while requiring a very low overhead. A node gathers hints from the nodes located within a small number of hops (called the protocol’s lookahead) from itself. As showed through simulations, very good performance can be obtained with small lookahead. The main statistical properties of hints have been investigated through an analytical model, which is also reported in the paper.

The deployment of server replicas of a service across an asynchronous distributed system (e.g., Internet) is a real practical challenge. This target cannot be indeed achieved by classical software replication techniques (e.g., passive and active replication) as these techniques usually rely on group communication toolkits that require server replicas to run over a partially synchronous distributed system to solve the underlying agreement problem. This paper proposes a three-tier architecture for software replication that encapsulates the need of partial synchrony in a specific software component of a mid-tier to free replicas and clients from the need of underlying partial synchrony assumptions. Then we propose how to specialize the mid-tier in order to manage active replication of server replicas.

A large class of routing protocols for MANETs, namely, reactive protocols employ some form of caching to reduce the number of route discoveries. The simplest form of caching is based on associating a timeout with each cache entry. Such timer-based cache schemes can increase the protocol efficiency. However, if the timeout is not well-tuned, a severe performance degradation arises as entries are removed either too early or too late from the cache. We address the problem of designing a proactive cache scheme that does not rely on any timer-based mechanism. This scheme guarantees that valid cached routes are never removed while stale routes are removed aggressively. This proactive cache scheme has been embedded in the Zone Routing Protocol (ZRP) framework and evaluated by an extensive simulation study.

In this paper we present a performance evaluation of three Java group toolkits (JavaGroups, Spread and Appia) with respect to a specific application scenario: software replication using a three-tier architecture. We also compare performances of these Java group toolkits with Maestro/Ensemble which has been developed in C++. Results show that performances of Java group toolkits are becoming comparable with the ones of Maestro/Ensemble, once selected a well tailored configuration for a given application.

This paper is a first attempt to study the problem of handling software replication in three tiers architectures. In particular a study based on synchronization and communication patterns imposed by replication is presented. We show how the complexity of the replication scheme is affected by the deterministic (or not) behavior of the members of the backtier We also give two generic synchronization and communication patterns used in two and three tiers replication. Well-known schemes such us active and passive replication are particular instances of these generic patterns.

A home is smart when, being aware of its own state and that of its users, is capable of controlling itself in order to support the user wishes and thus improving their quality of life. This holds both for users with special needs and for those with ordinary domestic needs. In this paper, we overview the Smart Homes for All project which represents the current state of the art with respect to software control and user interfaces in the smart homes arena.