In recent years, a large number of on-chain attacks have emerged in the blockchain empowered Web3 ecosystem. In the year of 2023 alone, on-chain attacks have caused losses of over 585 million. Attackers use blockchain transactions to carry out on-chain attacks, for example, exploiting vulnerabilities or business logic flaws in Web3 applications. A wealth of efforts have been devoted to detecting on-chain attack transactions through expert patterns and machine learning techniques. However, in this ever-evolving ecosystem, the performance of current methods is limited in detecting new on-chain attacks, due to the obsoleting of attack recognition patterns or the reliance on on-chain attack samples. In this paper, we propose a universal approach for detecting on-chain attacks even when there are few or even no new on-chain attack samples. Specifically, an in-depth analysis of the transaction characteristics is conducted, and we propose a new insight to train a generic attack transaction detecting model, i.e., transaction reconstruction. Particularly, to overcome the over-fitting in the transaction reconstruction task, we use the web-scale function comments related to transactions as supervision information, rather than expert-confirmed labels. Experimental results demonstrate that the proposed approach surpasses the supervised state-of-the-art by 13% in AUC, with just 30 known on-chain attack samples. Moreover, without any known attack samples, our method can still detect new on-chain attacks in the wild (with a precision of 61.83%). Among attacks detected in the wild, we confirm 1,692 address poisoning attacks, a new type of on-chain attack targeting token holders. Our code is available at: https://github.com/wuzhy1ng/attack_trans_detection_www25.

Federated Learning (FL) realizes distributed machine learning training via sharing model updates rather than raw data, thus ensuring data privacy. However, an attacker may infer the client's local original data from the model parameter so that original data leakage can be caused. While Differential Privacy (DP) is designed to address data leakage issues in FL, injecting noises during training reduces model accuracy. To minimize the negative impact caused by noises on model accuracy while considering privacy protections, in this article we propose an adaptive FL model, entitledRDP-basedAdaptiveFederatedLearning inShuffle model (RAFLS). To ensure the dataset privacy of clients, we inject adaptive noises into the client's local model by leveraging the adaptive layer-wise adaptive sensitivity of the local model. Our approach shuffles all local model parameters in order to address privacy explosion concerns caused by high-dimensional aggregation and multiple iterations. We further propose a fine-grained model weight aggregation scheme to aggregate all local models and obtain a global model. Our experiment evaluations demonstrate the proposed RAFLS has a better performance than the state-of-the-art methods in reducing noise's impact on model accuracy while protecting data, i.e., showing that the accuracy of RAFLS increases by 1.54% than that of the baseline scheme when$\epsilon = 2.0$and FashionMNIST under IID setting.

Decentralized applications (DApps) have long been sitting ducks for hackers due to their valuable cryptocurrency assets, exposing them to various security risks. When a DApp is attacked, promptly identifying faults is crucial to minimizing financial losses and ensuring effective fault repair. However, existing fault localization methods, which mostly rely on code coverage, often fall short for DApps, particularly when dealing with only one fault case. Furthermore, according to a prior survey, most developers expect fault localization tools to provide reasonable explanations.In this paper, we present Malo, a method for DApp-specific explainable fault localization. It identifies fault functions throughsuspicious token transfer-guided analysis, and then employs Large Language Models (LLMs) to generate explanations for these identified fault functions. Specifically, Malo examines function call traces and source codes of fault cases to acquireinternal knowledge, and also retrieves relevant project documents from the Web to obtainexternal knowledge. By integrating internal and external knowledge, Malo generates reasonable explanations for faults in DApps. Our evaluation on a dataset of 68 real-world DApp faults demonstrates that Malo can locate 62% of faults within the Top-5, 9% higher than the state-of-the-art method. The experiment results also demonstrate a remarkable alignment accuracy of 71% between the explanations generated by Malo and the ground truth. In addition, we conduct a user study, which confirms that explanations generated by Malo can aid developers in comprehending the root cause of faults. Our code and dataset are available online: https://github.com/SodalimeZero/Malo_Code.git.

Multi-scalar multiplication (MSM) is the most computation-intensive part in proof generation of Zero-knowledge proof (ZKP). In this paper, we propose MSMAC, an FPGA accelerator for large-scale MSM. MSMAC adopts a specially designed Instruction Set Architecture (ISA) for MSM and optimizes pipelined Point Addition Unit (PAU) with hybrid Karatsuba multiplier. Moreover, a runtime system is proposed to split MSM tasks with the optimal sub-task size and orchestrate execution of Processing Elements (PEs). Experimental results show that MSMAC achieves up to 328X and 1.96X speedups compared to the state-of-the-art implementation on CPU (one core) and GPU, respectively, outperforming the state-of-the-art ASIC accelerator by 1.79X. On 4 FPGAs, MSMAC performs 1,261X faster than a single CPU core.

Web3 describes an idea for the next evolution of the Internet, where blockchain technology enables the Internet of Value. As Web3 software, decentralized applications (DApps) have emerged in recent years. There exists a natural link between DApps and cryptocurrencies, where faults in DApps could directly lead to monetary losses associated with cryptocurrencies. Hence, efficient fault localization technology is of paramount importance for urgent DApp rescue operations and the mitigation of financial losses. However, fault localization methods applied in traditional applications are not well-suited for this specific field, due to their inability to identify DApp-specific fault features, e.g., a substantial amount of cryptocurrency is transferred from DApps to hackers. In order to explore the root cause of DApp faults, some researchers try to identify suspicious code snippets through mutation testing. Nonetheless, applying mutation testing for DApp fault localization is time-consuming and thus limited in practice. This paper conducts the first comprehensive study of DApp fault localization. We introduce DAppFL, a learning-based DApp fault localization tool that performs reverse engineering to gather executed source code and then trace cryptocurrency flow to assist in locating faulty functions. We also present the inaugural dataset for DApp fault localization, providing a new benchmark for this domain.Our experimental results demonstrate that DAppFL locates 63% of faults within the Top-5, 23% more than the state-of-the-art method. To facilitate further research, our code and dataset are freely available online: https://github.com/xplanet-sysu/awesome-works#dappfl.

The performance bottleneck of blockchain has shifted from consensus to serial smart contract execution in transaction validation. Previous works predominantly focus on inter-contract parallel execution, but they fail to address the inherent limitations of each smart contract execution performance. In this paper, we propose PaVM, the first smart contract virtual machine that supports both inter-contract and intra-contract parallel execution to accelerate the validation process. PaVM consists of (1) key instructions for precisely recording entire runtime information at the instruction level, (2) a runtime system with a re-designed machine state and thread management to facilitate parallel execution, and (3) a read/write-operation-based receipt generation method to ensure both the correctness of operations and the consistency of blockchain data. We evaluate PaVM on the Ethereum testnet, demonstrating that it can outperform the mainstream blockchain client Geth. Our evaluation results reveal that PaVM speeds up overall validation performance by 33.4×, and enhances validation throughput by up to 46×.

Permissioned blockchains are being widely applied to solve the trust problem in enterprise collaboration. However, most of these systems suffer from low throughput and flexibility lacking issues. In this paper, we present a blockchain system SChain with scalable concurrent execution based on a flexible architecture. SChain separates the functionality of a complete "node" into three sub-functions and assigns them to different peers within every organization. Then each organization can scale each sub-function flexibly with no need for negotiation between organizations. Based on this architecture, SChain explores scalable concurrent execution from two levels. First, SChain takes the advantage of multiple peers to execute transactions collectively, while promising they make the same results as one peer does serially. Second, SChain enables concurrent transaction execution across blocks to utilize the resources of peers fully, breaking up the block-by-block process manner, based on a pipelined workflow. The extensive evaluation results demonstrate that SChain significantly outperforms the serial execution and other competing systems-level approaches.

Byzantine fault tolerant (BFT) consensus protocols are becoming an appealing solution to blockchains. As most blockchain systems are deployed on Wide Area Networks (WANs), with each node acting on behalf of its entity, partially synchronous BFT protocols that rely on network synchrony to elect a single leader can be ill-suited. In contrast, asynchronous protocols have no such timing assumptions. Existing asynchronous protocols confront challenges in terms of both flexibility and performance.

Elliptic Curve Cryptography (ECC), one of the most widely used asymmetric cryptographic algorithms, has been deployed in Transport Layer Security (TLS) protocol, blockchain, secure multiparty computation, and so on. As one of the most secure ECC curves, Curve25519 is employed by some secure protocols, such as TLS 1.3 and Diffie-Hellman Private Set Intersection (DH-PSI) protocol. High-performance implementation of ECC is required, especially for the DH-PSI protocol used in privacy-preserving platform. Point multiplication, the chief cryptographic primitive in ECC, is computationally expensive. To improve the performance of DH-PSI protocol, we propose Topgun, a novel and high-performance hardware architecture for point multiplication over Curve25519. The proposed architecture features a pipelined Finite-field Arithmetic Unit and a simple and highly efficient instruction set architecture. Compared to the best existing work on Xilinx Zynq 7000 series FPGA, our implementation with one Processing Element can achieve 3.14× speedup on the same device. To the best of our knowledge, our implementation appears to be the fastest among the state-of-the-art works. We also have implemented our architecture consisting of 4 Compute Groups, each with 16 PEs, on an Intel Agilex AGF027 FPGA. The measured performance of 4.48 Mops/s is achieved at the cost of 86 Watts power, which is the record-setting performance for point multiplication over Curve25519 on FPGAs.

Blockchain performance cannot meet the requirement nowadays. One of the crucial ways to improve performance is sharding. However, most blockchain sharding research focuses on the public blockchain. As for consortium blockchain, previous studies cannot support high cross-shard efficiency, multiple-shard contract calling, strict transaction atomicity, and shard availability, which are essential requirements but also challenges in consortium blockchain systems. Facing these challenges, we propose Meepo, a systematic study on sharded consortium blockchain. Meepo enhances cross-shard efficiency via the cross-epoch and cross-call. Moreover, a partial cross-call merging strategy is designed to handle the multi-state dependency in contract calls, achieving flexible multiple-shard contract calling. Meepo employs a replay-epoch to ensure strict transaction atomicity, and it also uses a backup algorithm called shadow shard based recovery to improve the shard robustness. On a test-bed of 128 AliCloud servers, setting 32 shards and 4 consortium members, Meepo-OpenEtheruem can achieve more than 140,000 cross-shard TPS under the workload of 100,000,000 asset transactions. It also shows more than 50,000 TPS under the transactions of real-world shopping behaviors.

Blockchain has attracted lots of attention in recent years. However, the performance of blockchain cannot meet the requirement of massive Internet of Things (IoT) devices. One of the important bottlenecks of blockchain is the limited computing resources on a single server while executing transactions. To address this issue, we propose Aeolus blockchain to achieve the distributed execution of blockchain transactions. There are two key challenges to achieving this for IoT blockchain: transaction structure and state consistency. Facing these challenges, we first propose a distributed blockchain transaction structure, which imports extra parameters to divide the transaction execution into different stages to enable distributed execution. Second, we propose distributed state update sharding, which equips each blockchain peer with its own master and shard servers. In this way, each blockchain peer can be considered as a cluster that distributes the transaction to shorten the processing time and reach the consensus finally. We implement Aeolus on Go-Ethereum to evaluate its feasibility, on a testbed including 132 cloud servers. Our system runs stably for more than 8 h under the workload of 190 000 000 real-world user transactions. Experimental results show the efficiency that Aeolus can achieve more than 100 000 transactions/s of blockchain transactions, which is 15.6 times the throughput of the original blockchain.

Blockchain performance cannot meet the requirement nowadays. One of the crucial ways to improve performance is sharding. However, most blockchain sharding research focuses on public blockchain. As for consortium blockchain, previous studies cannot support high cross-shard efficiency, cross-contract flexibility, shard availability, and strict transaction atomicity, which are the essential requirements but also the challenges in consortium blockchain systems. Facing these challenges, we propose Meepo, a systematic study on sharded consortium blockchain. Meepo enhances cross-shard efficiency via the cross-epoch and cross-call. Moreover, a partial cross-call merging strategy is designed to handle the multi-state dependency in contract calls, achieving cross-contract flexibility. Meepo employs a replay-epoch to ensure strict transaction atomicity, and it also uses a backup algorithm called shadow shard based recovery to improve the shard robustness. We implement Meepo on the AliCloud, using 32 shards in maximum, achieving more than 120,000 cross-shard TPS under the workload of 100,000,000 asset transactions.

We demonstrate SChain, a consortium blockchain that scales transaction processing to support large-scale enterprise applications. The unique advantage of SChain stems from the exploitation of both intra- and inter-block concurrency. The intra-block concurrency not only takes advantage of the multi-core processor on a single peer but also leverages the capacity of multiple peers. The interblock concurrency enables simultaneous processing across multiple blocks to increase the utilization of various peers. In our demonstration, we use real-time dashboards containing visualization based on the output of SChain to give the attendees interactive explorations of how SChain achieves intra- and inter-block concurrency.

Confidentiality is an indispensable requirement in financial applications of blockchain technology, and supporting it along with high performance and friendly programmability is technically challenging. In this paper, we present a system design called CONFIDE to support on-chain confidentiality by leveraging Trust Execution Environment (TEE). CONFIDE's secure data transmission protocol and data encryption protocol, together with a highly efficient virtual machine run in TEE, guarantee the confidentiality in the life cycle of a transaction from end to end. CONFIDE proposes a secure data model along with an application-driven secure protocol to guarantee data confidentiality and integrity. Its smart contract language extension offers users the flexibility to define complex confidentiality models. CONFIDE is implemented as a plugin module to Antfin Blockchain's proprietary platform, and can be plugged into other blockchain platforms as well with its universal interface design. Nowadays, CONFIDE is supporting millions of commercial transactions daily on consortium blockchain running financial applications including supply chain finance, ABS, commodity provenance, and cold-chain logistics.

Node ranking in temporal networks are often impacted by heterogeneous context from node content, temporal, and structural dimensions. This paper introduces TGNet , a deep learning framework for node ranking in heterogeneous temporal graphs. TGNet utilizes a variant of Recurrent Neural Network to adapt context evolution and extract context features for nodes. It incorporates a novel influence network to dynamically estimate temporal and structural influence among nodes over time. To cope with label sparsity, it integrates graph smoothness constraints as a weak form of supervision. We show that the application of TGNet is feasible for large-scale networks by developing efficient learning and inference algorithms with optimization techniques. Using real-life data, we experimentally verify the effectiveness and efficiency of TGNet techniques. We also show that TGNet yields intuitive explanations for applications such as alert detection and academic impact ranking, as verified by our case study.

Administrators of most user-facing systems depend on periodic log data to get an idea of the health and status of production applications. Logs report information, which is crucial to diagnose the root cause of complex problems. In this paper, we present a real-time log analysis system called LogLens that automates the process of anomaly detection from logs with no (or minimal) target system knowledge and user specification. In LogLens, we employ unsupervised machine learning based techniques to discover patterns in application logs, and then leverage these patterns along with the real-time log parsing for designing advanced log analytics applications. Compared to the existing systems which are primarily limited to log indexing and search capabilities, LogLens presents an extensible system for supporting both stateless and stateful log analysis applications. Currently, LogLens is running at the core of a commercial log analysis solution handling millions of logs generated from the large-scale industrial environments and reported up to 12096x man-hours reduction in troubleshooting operational problems compared to the manual approach.

Cloud infrastructures provide a rich set of management tasks that operate computing, storage, and networking resources in the cloud. Monitoring the executions of these tasks is crucial for cloud providers to promptly find and understand problems that compromise cloud availability. However, such monitoring is challenging because there are multiple distributed service components involved in the executions. CloudSeer enables effective workflow monitoring. It takes a lightweight non-intrusive approach that purely works on interleaved logs widely existing in cloud infrastructures. CloudSeer first builds an automaton for the workflow of each management task based on normal executions, and then it checks log messages against a set of automata for workflow divergences in a streaming manner. Divergences found during the checking process indicate potential execution problems, which may or may not be accompanied by error log messages. For each potential problem, CloudSeer outputs necessary context information including the affected task automaton and related log messages hinting where the problem occurs to help further diagnosis. Our experiments on OpenStack, a popular open-source cloud infrastructure, show that CloudSeer's efficiency and problem-detection capability are suitable for online monitoring.

In mission critical IT services, system failure prediction becomes increasingly important; it prevents unexpected system downtime, and assures service reliability for end users. While operational console logs record rich and descriptive information on the health status of those IT systems, existing system management technologies mostly use them in a labor-intensive forensics approach, i.e., identifying what went wrong after the fact. Recent efforts on log-based system management take an automation approach with text mining techniques, such as term frequency - inverse document frequency (TF-IDF). However, those techniques lead to a high-dimensional feature space, and are not easily generalizable to heterogeneous log formats. In this paper, we present a novel system that automatically parses streamed console logs and detects early warning signals for IT system failure prediction. In particular, our solution includes a log pattern extraction method by clustering together logs with similar format and content. We then resemble the TF-IDF idea by considering each pattern as a word and the set of patterns in each discretized epoch as a document. This leads to a feature space with significantly lower dimensionality that can provide robust signals for the status of the system. As system failures tend to occur very rare, we apply a recurrent neural network, namely, Long Short-Term Memory (LSTM), to deal with the “rarity” of labeled data in the training process. LSTM is able to capture the long-range dependency across sequences, therefore outperforms traditional supervised learning methods in our application domain. We evaluated and compared our proposed technology with state-of-the-art machine learning approaches using real log traces from two large enterprise systems. The results showed the advantage and potentials of our system in prediction of complex IT failures. To our knowledge, our work is the first that employs LSTM for log-based system failure prediction.

Modern engineering incorporates smart technologies in all aspects of our lives. Smart technologies are generating terabytes of log messages every day to report their status. It is crucial to analyze these log messages and present usable information (e.g. patterns) to administrators, so that they can manage and monitor these technologies. Patterns minimally represent large groups of log messages and enable the administrators to do further analysis, such as anomaly detection and event prediction. Although patterns exist commonly in automated log messages, recognizing them in massive set of log messages from heterogeneous sources without any prior information is a significant undertaking. We propose a method, named LogMine, that extracts high quality patterns for a given set of log messages. Our method is fast, memory efficient, accurate, and scalable. LogMine is implemented in map-reduce framework for distributed platforms to process millions of log messages in seconds. LogMine is a robust method that works for heterogeneous log messages generated in a wide variety of systems. Our method exploits algorithmic techniques to minimize the computational overhead based on the fact that log messages are always automatically generated. We evaluate the performance of LogMine on massive sets of log messages generated in industrial applications. LogMine has successfully generated patterns which are as good as the patterns generated by exact and unscalable method, while achieving a 500× speedup. Finally, we describe three applications of the patterns generated by LogMine in monitoring large scale industrial systems.

Performance bugs which manifest in a production cloud computing infrastructure are notoriously difficult to diagnose because of both the difficulty of reproducing those bugs and the lack of debugging information. In this paper, we present PerfScope, a practical online performance bug inference tool to help the developer understand how a performance bug happened during the production run. PerfScope achieves online bug inference to obviate the need for offline bug reproduction. PerfScope does not require application source code or any runtime instrumentation to the production system. PerfScope is application-agnostic, which can support both interpreted and compiled programs running inside a cloud infrastructure.

To diagnose performance problems in production systems, many OS kernel-level monitoring and analysis tools have been proposed. Using low level kernel events provides benefits in efficiency and transparency to monitor application software. On the other hand, such approaches miss application-specific semantic information which can be effective to differentiate the trace patterns from distinct application logic. This paper introduces new trace analysis techniques based on event features to improve kernel event based performance diagnosis tools. Our prototype, AppDiff, is based on two analysis features: system resource features convert kernel events to resource usage metrics, thereby enabling the detection of various performance anomalies in a unified way; program behavior features infer the application logic behind the low level events. By using these features and conditional probability, AppDiff can detect outliers and improve the diagnosis of application performance.

Unified tracing is the process of collecting trace logs across the boundary of kernel and user spaces, and has been used to understand the in-depth correspondence between low level events and application program context for diagnosing system failures and performance problems. Crossing the boundary from the kernel space to a user space to collect trace events from dual spaces imposes challenges compared to crossing the boundary in the other way from a user space to the kernel space due to multiple scheduled programs and diverse code layouts in the user space regarding the tracing target. In this paper, we propose a novel unified tracing system called Uscope to systematically trace kernel and unprecedented user code with low overhead. The key idea is to use an efficient variant of stack walking. Uscope lowers stack walking overhead by adjusting the scope of walking in two ways: (1) a highly configurable focus within the call stack, and (2) a per-application tracing that systematically tracks a dynamic set of new, exiting, or transforming processes and threads of an application software. This system is realized by using a flexible stack walking algorithm and a runtime kernel structure, Trace Map. These key features lead to low run-time overhead under 6% relative to native execution on a set of widely used benchmarks.

In this paper, we present CLUE, a system event analytics tool for black-box performance diagnosis in production Cloud Computing systems. CLUE provides an unified and extensible means of profiling service transactional behaviors, and builds structured data called event sketches. CLUE further offers a set of analytic tools for summarizing and analyzing event sketches by integrating data mining and statistical analysis. CLUE has been developed in NEC as an internal tool and applied in diagnosing a diverse set of real performance problems for multi-tiered IT applications running on multi-core servers of major platforms including Linux (Redhat, Fedora), Unix (HP-UX), and Windows (Windows Server 2008). We demonstrated the evaluation of our framework on real-world IT systems, and showed how it can enable visibility and effective diagnosis of service system performance problems.

Performance bugs are frequently observed in commodity software. While profilers or source code-based tools can be used at development stage where a program is diagnosed in a well-defined environment, many performance bugs survive such a stage and affect production runs. OS kernel-level tracers are commonly used in post-development diagnosis due to their independence from programs and libraries; however, they lack detailed program-specific metrics to reason about performance problems such as function latencies and program contexts. In this paper, we propose a novel performance inference system, called IntroPerf, that generates fine-grained performance information -- like that from application profiling tools -- transparently by leveraging OS tracers that are widely available in most commodity operating systems. With system stack traces as input, IntroPerf enables transparent context-sensitive performance inference, and diagnoses application performance in a multi-layered scope ranging from user functions to the kernel. Evaluated with various performance bugs in multiple open source software projects, IntroPerf automatically ranks potential internal and external root causes of performance bugs with high accuracy without any prior knowledge about or instrumentation on the subject software. Our results show IntroPerf's effectiveness as a lightweight performance introspection tool for post-development diagnosis.

The hindrances to the adoption of public cloud computing services include service reliability, data security and privacy, regulation compliant requirements, and so on. To address those concerns, we propose a hybrid cloud computing model which users may adopt as a viable and cost-saving methodology to make the best use of public cloud services along with their privately-owned (legacy) data centers. As the core of this hybrid cloud computing model, an intelligent workload factoring service is designed for proactive workload management. It enables federation between on- and off-premise infrastructures for hosting Internet-based applications, and the intelligence lies in the explicit segregation of base workload and flash crowd workload, the two naturally different components composing the application workload. The core technology of the intelligent workload factoring service is a fast frequent data item detection algorithm, which enables factoring incoming requests not only on volume but also on data content, upon a changing application data popularity. Through analysis and extensive evaluation with real-trace driven simulations and experiments on a hybrid testbed consisting of local computing platform and Amazon Cloud service platform, we showed that the proactive workload management technology can enable reliable workload prediction in the base workload zone (with simple statistical methods), achieve resource efficiency (e.g., 78% higher server capacity than that in base workload zone) and reduce data cache/replication overhead (up to two orders of magnitude) in the flash crowd workload zone, and react fast (with an X^2 speed-up factor) to the changing application data popularity upon the arrival of load spikes.

Effective consolidation of different applications on common resources is often akin to black art as application performance interference may result in unpredictable system and workload delays. In this paper we consider the problem of fair load balancing on multiple servers within a virtualized data center setting. We especially focus on multi-tiered applications with different resource demands per tier and address the problem on how to best match each application tier on each resource, such that performance interference is minimized. To address this problem, we propose a two-step approach. First, a fair load balancing scheme assigns different virtual machines (VMs) across different servers; this process is formulated as a multi-dimensional vector scheduling problem that uses a new polynomial-time approximation scheme (PTAS) to minimize the maximum utilization across all server resources and results in multiple load balancing solutions. Second, a queueing network analytic model is applied on the proposed min-max solutions in order to select the optimal one. We experimentally evaluate the proposed two-stage mechanism using a Xen virtualization testbed that hosts multiple RUBiS multi-tier applications. Experimental results show that the proposed mechanism is robust as it always predicts the optimal consolidation strategy.

We introduce a new hybrid instrumentation tool for dynamic application instrumentation called iProbe, which is flexible and has low overhead. iProbe takes a novel 2-stage design, and offloads much of the dynamic instrumentation complexity to an offline compilation stage. It leverages standard compiler flags to introduce “place-holders” for hooks in the program executable. Then it utilizes an efficient user-space “HotPatching” mechanism which modifies the functions to be traced and enables execution of instrumented code in a safe and secure manner. In its evaluation on a micro-benchmark and SPEC CPU2006 benchmark applications, the iProbe prototype achieved the instrumentation overhead an order of magnitude lower than existing state-of-the-art dynamic instrumentation tools like SystemTap and DynInst.

In this paper, we undertake the problem of server consolidation in virtualized data centers from the perspective of approximation algorithms. We formulate server consolidation as a stochastic bin packing problem, where the server capacity and an allowed server overflow probability p are given, and the objective is to assign VMs to as few physical servers as possible, and the probability that the aggregated load of a physical server exceeds the server capacity is at most p.

Today's networked systems are extensively instrumented for collecting a wealth of monitoring data. In this paper, we propose a framework called System-wide Similarity Query (S2Q) to support a new type of similarity queries on monitoring data for managing complex networked systems. The similarity queries are defined on a novel data model that captures system states, and the implementation includes a streaming algorithm for online state-modeling computation and a companion graph-based indexing technique for fast retrieval of historical system states. S2Q simplifies many systems management tasks through a simple and intuitive query interface available to operators, and two applications are evaluated in the paper: (i) fast diagnosis of repeated failures in enterprise IT systems, and (ii) automated application traffic profiling on computer networks. For the first application, the diagnosis accuracy can reach 95% on a multi-tier web service testbed. For the second application, major network applications were automatically identified in the traffic logs from a large campus wireless network.

With the growing scale of current computing systems, traditional configuration tuning methods become less effective because they usually assume a small number of parameters in the system. In order to handle the scalability issue of configuration tuning, this paper proposes a cooperative optimization framework, which mimics the behavior of team playing to discover the optimal configuration setting in computing systems. We follow a `best of the best' rule to decompose the tuning task into a number of small subtasks with manageable size and complexity. While each decomposed module is responsible for the optimization of its own configuration parameters, all the modules share the performance evaluations of new samples as common feedbacks to enhance their optimization objectives. As a result, the qualities of generated samples become improved during the search, and the cooperative sampling will eventually discover the optimal configurations in the system. Experimental results demonstrate that our proposed cooperative optimization can identify better solutions within limited time periods compared with other state of the art configuration search methods. Such advantage becomes more significant when the number of configuration parameters increases.

Load balancing in publish/subscribe (pub/sub) broker networks is challenging as the workload is multi-dimensional and content-dependent. In this paper we present the framework design of a middleware, called Shuffle, to achieve optimal load balancing in a pub/sub broker network. Shuffle features a suite of active workload management schemes within a single overlay topology on message parsing, matching, delivery, and forwarding, the four types of workload in a publish/subscribe service affected by two inputs-streaming events and stored subscriptions. Shuffle leverages its traffic randomization scheme and Chord, a DHT substrate, to build overlay trees for active workload aggregation and distribution, and we show the optimality property of the load balancing scheme upon any input traffic distribution on individual Shuffle aggregation trees. We also show the NP-hardness of the workload management problem when it has to be done among multiple correlated aggregation trees, and present a heuristic accordingly. Through extensive simulations we validated the design of Shuffle upon dynamic and heavy workload.

"Alice has a piece of valuable information which she is willing to sell to anyone who is interested in; she is too busy and wants to ask Bob, a professional broker, to sell that information for her; but Alice is in a dilemma where she cannot trust Bob with that information but Bob cannot help her find her customers without knowing that information." In this paper, we propose a security mechanism called information foiling to address new confidentiality problems arising in pub/sub overlay services [1]. Information foiling extends Rivest's "Chaffing and Winnowing" [2], and its basic idea is to carefully generate a set of fake messages to hide an authentic message. Information foiling requires no modification inside the broker network so that the routing/filtering capabilities of broker nodes remains intact. We formally present the information foiling mechanism in the context of publish/subscribe overlay services, and discuss its applicability in other Internet applications. For publish/subscribe applications, we propose a suite of optimal schemes for fake message generation in different scenarios. Real-world data are used in our evaluation to demonstrate the effectiveness of the proposed schemes.

In this paper we measured and analyzed the workload on Yahoo! Video, the 2nd largest U.S. video sharing site, to understand its nature and the impact on online video data center design. We discovered interesting statistical properties on both static and temporal dimensions of the workload; they include file duration and popularity distributions, arrival rate dynamics and predictability, and workload stationarity and burstiness. Complemented with queueing-theoretic techniques, we extended our understanding on the measurement data with a virtual data center design assuming the same workload as measured, which reveals results regarding the impact of workload arrival distribution, service level agreements (SLAs) and workload scheduling schemes on the design and operations of such large-scale video distribution systems.

The behavior of network entities, such as flows, sessions, hosts, and users, can often be described by communication event sequences in the time domain. For the purpose of many network measurement and monitoring tasks, it is desirable to have an accurate yet information-compact profiling of the behavior of massive event sequences. This paper proposes a new method to achieve this goal. On a given set of event sequences, the proposed method automatically learns a mixture model which fully captures the sequence behavior including both event pattern and duration between events. The learned mixture model is information-compact as it classifies sequences into a set of behavior templates, each of which is described by a Markov Chain. The model parameters are estimated in an iterative procedure which is developed from the Expectation Maximization algorithm. Two network management applications are proposed based on the method: a visualization tool for network administrators to conduct exploratory traffic analysis, and an efficient anomaly detection mechanism. In the evaluation, we validate the method accuracy as well as the usefulness of the two applications by using three networking datasets with different types: TCP packet traces, VoIP calls, and syslog traces in wireless networks.

In this paper we measured and analyzed the workload on Yahoo! Video, the 2nd largest U.S. video sharing site, to understand its nature and the impact on online video data center design. We discovered interesting statistical properties on both static and temporal dimensions of the workload including file duration and popularity distributions, arrival rate dynamics and predictability, and workload stationarity and burstiness. Complemented with queueing-theoretic techniques, we further extended our understanding on the measurement data with a virtual design on the workload and capacity management components of a data center assuming the same workload as measured, which reveals key results regarding the impact of Service Level Agreements (SLAs) and workload scheduling schemes on the design and operations of such large-scale video distribution systems.

Service hosting platforms typically run a large number of third-party applications that are composed of multiple communicating components distributed on a dynamic set of hosting servers. Understanding the real-time behaviors of these applications and the intricate interactions/dependency relationships among these application components is very important to service management tasks such as load balancing, capacity planning, performance debugging and fault diagnosis. In this paper, we present the scalable real-time application monitoring and diagnosis (SRAMD) tool, for applications consisting of "black box" components: software without source code available, and usually without desired logging instrumentation. SRAMD runs at application layer and requires no modification to existing applications, middleware, or messages. For each application component collocated at its hosting server, a SRAMD monitor traces the component's packet-level traffic unobtrusively, summarizes its local resource utilization and performance (e.g. response time) online, performs interactive queries (e.g. per- request resource utilization) to locate possible bottlenecks on- demand, and discovers inter-component dependence relationships statistically. The SRAMD controller simply aggregates reports from distributed monitors to construct real-time application topologies with rich runtime information. We have developed mechanisms to decentralize the computation overhead and minimize the communication cost in the monitoring and diagnosis process, and two schemes to discover application component dependency relationships in different scenarios. The SRAMD tool offers an alternative to server logs and message-level traces for service monitoring and performance diagnosis.

Fast IP flow rate estimation has many potential applications in network management, monitoring, security, and traffic engineering. Recently, low cost and memory efficient techniques to accurately estimate flow-rates in real-time have been developed. These techniques rely on flow definitions being constrained to being subsets of the fields in the packet header making flow-membership tests relatively inexpensive. In this paper, we consider a more general flow-rate estimation problem where flow membership testing is non-trivial and may involve more complex processing such as packet-payload based tests. An example is to estimate the amount of traffic that contains a given set of patterns (e.g., virus or worm signatures). We design new flow estimation techniques to reduce the number of membership tests. These techniques track pairs of arrivals that have the given property of interest and use lazy membership testing to avoid complex property testing unless absolutely necessary. The efficiency of the new schemes is evaluated by both analysis and simulation. I.

Detecting coordinated attacks on Internet resources requires a distributed network monitoring infrastructure. Such an infrastructure will have two logically distinct elements: distributed monitors that continuously collect traffic information, and a distributed query system that allows network operators to efficiently correlate information from different monitors in order to detect anomalous traffic patterns. In this paper, we discuss the design and implementation of MIND, a distributed index management system that supports the creation and querying of multiple distributed indices. We validate MIND using traffic traces from two large backbone networks, then examine the performance of a MIND prototype on more than 100 PlanetLab machines. Our experiments show that MIND can detect and report network anomalies in about one second on an inter-continental backbone. We also analyze the efficiency of our load balancing mechanism and evaluate the robustness of MIND to node failure. I.

Real-time IP flow estimation has many potential applications in network management, monitoring, security, and traffic engineering. Existing techniques typically rely on flow definitions being constrained as subsets of the fields in packet headers. This makes flow-membership tests relatively inexpensive. In this paper, we consider a more general flow estimation problem that needs complex packet-payload based tests for flow-membership. An example is to estimate traffic with common strings in the payload and detect potential virus signatures for early alarm generation. We develop a fast, memory efficient algorithm for solving this problem as a variant of the longest common subsequence problem. This is done via an application of Rabin fingerprinting in combination with bloom filters. Both analysis and simulation show the effectiveness of the developed method.

We consider the problem of fast, estimation of flow rates in backbone network links with possibly millions of flows. Accurate flow rate estimation is necessary for network traffic management, network planning, measuring compliance to service level agreements, and network security. Ideally, a rate estimation scheme should have short estimation times with provable bounds on estimation error, be low in memory usage, and be easily implementable in hardware for operation at high speeds. We develop such a scheme, and achieve up to two orders of magnitude speed-up in estimation time over the previously proposed two-runs-based RATE scheme [Kodialam, M et al., 2004]. The speedups are achieved without a significant increase in memory usage, by using coincidences instead of runs. Counting coincidences has a higher processing overhead than detecting two-runs, but this higher overhead is not significant for a hardware implementation. We show that the proposed scheme is faster and more accurate than other recently proposed schemes such as ACCEL-RATE [Hao, F et al., 2004] and smart sampling [Duffield, N et al., 2004]. The faster estimation time of the new scheme has many benefits including quicker detection of incipient denial of service attacks. We prove bounds on the scheme's accuracy, memory needs, and also show that it performs well by simulations that use both synthetic and real traffic traces.

Distributed hash table (DHT) systems are an important class of peer-to-peer routing infrastructures. They enable scalable wide-area storage and retrieval of information, and will support the rapid development of a wide variety of Internet-scale applications ranging from naming systems and file systems to application-layer multicast. DHT systems essentially build an overlay network, but a path on the overlay between any two nodes can be significantly different from the unicast path between those two nodes on the underlying network. As such, the lookup latency in these systems can be quite high and can adversely impact the performance of applications built on top of such systems. In this paper, we discuss a random sampling technique that incrementally improves lookup latency in DHT systems. Our sampling can be implemented using information gleaned from lookups traversing the overlay network. For this reason, we call our approach lookup-parasitic random sampling (LPRS). LPRS converges quickly, and requires relatively few modifications to existing DHT systems. For idealized versions of DHT systems like Chord, Tapestry, and Pastry, we analytically prove that LPRS can result in lookup latencies proportional to the average unicast latency of the network, provided the underlying physical topology has a power-law latency expansion. We then validate this analysis by implementing LPRS in the Chord simulator. Our simulations reveal that LPRS-Chord exhibits a qualitatively better latency scaling behavior relative to unmodified Chord. The overhead of LPRS is one sample per lookup hop in the worst case. Finally, we provide evidence which suggests that the Internet router-level topology resembles power-law latency expansion. This finding implies that LPRS has significant practical applicability as a general latency reduction technique for many DHT systems. This finding is also of independent interest since it might inform the design of latency-sensitive topology models for the Internet.

Distributed hash table (DHT) systems are an important class of peer-to-peer routing infrastructures. They enable scalable wide-area storage and retrieval of information, and will support the rapid development of a wide variety of Internet-scale applications ranging from naming systems and file systems to application-layer multicast. DHT systems essentially build an overlay network, but a path on the overlay between any two nodes can be significantly di#erent from the unicast path between those two nodes on the underlying network. As such, the lookup latency in these systems can be quite high and can adversely impact the performance of applications built on top of such systems.

Efficient data retrieval in a peer-to-peer system like Freenet is a challenging problem. We study the impact of cache replacement policy on the performance of Freenet. We find that, with Freenet's LRU (least recently used) cache replacement, there is a steep reduction in the hit ratio with increasing load. Based on intuition from the small-world models and the recent theoretical results by Kleinberg, we propose an enhanced-clustering cache replacement scheme for use in place of LRU. Such a replacement scheme forces the routing tables to resemble neighbor relationships in a small-world acquaintance graph - clustering with light randomness. In our simulation, this new scheme improved the request hit ratio dramatically while keeping the small average hops per successful request comparable to LRU. A simple, highly idealized model of Freenet under clustering with light randomness proves that the expected message delivery time in Freenet is O(log/sup 2/n) if the routing tables satisfy the small-world model and have the size /spl theta/(log/sup 2/n).