Session 7-B

Network Modeling

Conference
9:00 AM — 10:30 AM EDT
Local
Jul 9 Thu, 9:00 AM — 10:30 AM EDT

Bound-based Network Tomography for Inferring Interesting Link Metrics

Huikang Li, Yi Gao, Wei Dong and Chun Chen (Zhejiang University, China)

1
Network tomography is an attractive methodology for inferring internal network states from accumulated path measurements between pairs of monitors. Motivated by previous results that identifying all link metrics can require a large number of monitors, we focus on calculating the performance bounds of a set of interesting links, i.e., bound-based network tomography. We develop an efficient solution to obtain the tightest upper bounds and lower bounds of all interesting links in an arbitrary network with a given set of end-to-end path measurements. Based on this solution, we further propose an algorithm to place new monitors over existing ones such that the bounds of interesting links can be maximally tightened. We theoretically prove the effectiveness of the proposed algorithms. We implement the algorithms and conduct extensive experiments based on real network topologies. Compared with state-of-the-art approaches, our algorithms can achieve up to 2.2-3.1 times more reduction on the bound intervals for all interesting links and reduce the number of placed monitors significantly in various network settings.

ProTO: Proactive Topology Obfuscation Against Adversarial Network Topology Inference

Tao Hou and Zhe Qu (University of South Florida, USA); Tao Wang (New Mexico State University, USA); Zhuo Lu and Yao Liu (University of South Florida, USA)

3
The topology of a network is fundamental for building network infrastructure functionalities. In many scenarios, enterprise networks may have no desire to disclose their topology information. In this paper, we aim at preventing attacks that use adversarial, active end-to-end topology inference to obtain the topology information of a target network. To this end, we propose a Proactive Topology Obfuscation (ProTO) system that adopts a detect-then-obfuscate framework: (i) a lightweight probing behavior identification mechanism based on machine learning is designed to detect any probing behavior, and then (ii) a topology obfuscation design is developed to proactively delay all identified probe packets in a way such that the attacker will obtain a structurally accurate yet fake network topology based on the measurements of these delayed probe packets, therefore deceiving the attacker and decreasing its appetency for future inference.

SpreadSketch: Toward Invertible and Network-Wide Detection of Superspreaders

Lu Tang (The Chinese University of Hong Kong, Hong Kong); Qun Huang (Peking University, China); Patrick Pak-Ching Lee (The Chinese University of Hong Kong, Hong Kong)

0
Superspreaders (i.e., hosts with numerous distinct connections) remain severe threats to production networks. How to accurately detect superspreaders in real-time at scale remains a non-trivial yet challenging issue. We present SpreadSketch, an invertible sketch data structure for network-wide superspreader detection with the theoretical guarantees on memory space, performance, and accuracy. SpreadSketch tracks candidate superspreaders and embeds estimated fan-outs in binary hash strings inside small and static memory space, such that multiple SpreadSketch instances can be merged to provide a network-wide measurement view for recovering superspreaders and their estimated fan-outs. We present formal theoretical analysis on SpreadSketch in terms of space and time complexities as well as error bounds. Trace-driven evaluation shows that SpreadSketch achieves higher accuracy and performance over state-of-the-art sketches. Furthermore, we prototype SpreadSketch in P4 and show its feasible deployment in commodity hardware switches.

Variational Information Diffusion for Probabilistic Cascades Prediction

Fan Zhou and Xovee Xu (University of Electronic Science and Technology of China, China); Kunpeng Zhang (University of Maryland, USA); Goce Trajcevski (Iowa State University, USA); Ting Zhong (University of Electronic Science and Technology of China, China)

0
Understanding in-network information diffusion is a fundamental problem in many application domains and one of the primary challenges is to predict the size of the information cascade. Most of the existing models rely either on hypothesized point process (e.g., Poisson and Hawkes process), or simply predict the information propagation via deep neural networks. However, they fail to simultaneously capture the underlying structure of a cascade graph and the propagation of uncertainty in the diffusion, which may result in unsatisfactory prediction performance.

To address these, in this work we propose a novel probabilistic cascade prediction framework: Variational Cascade (VaCas) graph learning networks. VaCas allows a non-linear information diffusion inference and models the information diffusion process by learning the latent representation of both the structural and temporal information. It is a pattern-agnostic model leveraging variational inference to learn the node-level and cascade-level latent factors in an unsupervised manner. In addition, VaCas is capable of capturing both the cascade representation uncertainty and node infection uncertainty, while enabling hierarchical pattern learning of information diffusion. Extensive experiments conducted on real-world datasets demonstrate that VaCas significantly improves the prediction accuracy, compared to state-of-the-art approaches, while also enabling interpretability.

Session Chair

Wei Bao (The University of Sydney)

Session 8-B

Trusted Systems

Conference
11:00 AM — 12:30 PM EDT
Local
Jul 9 Thu, 11:00 AM — 12:30 PM EDT

An Adaptive and Fast Convergent Approach to Differentially Private Deep Learning

Zhiying Xu and Shuyu Shi (University of Nanjing, China); Alex X. Liu (Ant Financial Services Group, China); Jun Zhao (Nanyang Technological University, Singapore); Lin Chen (Yale University, USA)

0
With the advent of the era of big data, deep learning has become a prevalent building block in a variety of machine learning or data mining tasks, such as signal processing, network modeling and traffic analysis, to name a few. The massive user data crowdsourced plays a crucial role in the success of deep learning models. However, it has been shown that user data may be inferred from trained neural models and thereby exposed to potential adversaries, which raises information security and privacy concerns. To address this issue, recent studies leverage the technique of differential privacy to design private-preserving deep learning algorithms. Albeit successful at privacy protection, differential privacy degrades the performance of neural models. In this paper, we develop ADADP, an adaptive and fast convergent learning algorithm with a provable privacy guarantee. ADADP significantly reduces the privacy cost by improving the convergence speed with an adaptive learning rate and mitigates the negative effect of differential privacy upon the model accuracy by introducing adaptive noise. The performance of ADADP is evaluated on real-world datasets. Experiment results show that it outperforms state-of-the-art differentially private approaches in terms of both privacy cost and model accuracy.

Enabling Execution Assurance of Federated Learning at Untrusted Participants

XiaoLi Zhang, Fengting Li, Zeyu Zhang and Qi Li (Tsinghua University, China); Cong Wang (City University of Hong Kong, Hong Kong); Jianping Wu (Tsinghua University, China)

0
Federated learning (FL), as the privacy-preserving machine learning framework, draws growing attention in both industry and academia. It can obtain a jointly accurate model by distributing training tasks into data owners without centralized data collection. However, FL faces new security problems, as it losses direct control to training processes. Thus, one fundamental demand is to ensure whether participants execute training tasks as intended.

In this paper, we propose TrustFL, a practical scheme to build assurance of participants' training execution with high confidence. We employ Trusted Execution Environments (TEEs) to attest to the correct execution. Particularly, instead of performing all training processes inside TEE, we use TEE to randomly check a small fraction of training processes with tunable levels of assurance. All processes are executed on the co-located faster processor, e.g., GPU, for efficiency. Besides, we adopt a commitment scheme and devise a specific data selection method, so as to prevent cheating like only processing TEE-requested computation or uploading old results. We prototype TrustFL using GPU and SGX, and evaluate its performance. The results show that TrustFL can achieve one/two orders of magnitude speedups compared with purely training with SGX, while assuring the correct training with a confidence level of 99%.

EncELC: Hardening and Enriching Ethereum Light Clients with Trusted Enclaves

Chengjun Cai (City University of Hong Kong, Hong Kong); Lei Xu (City University of Hong Kong, China & Nanjing University of Science and Technology, Hong Kong); Zhou Anxin, Ruochen Wang and Cong Wang (City University of Hong Kong, Hong Kong); Qian Wang (Wuhan University, China)

0
The rapid growth of Ethereum blockchain has brought extremely heavy overhead for coin owners or developers to bootstrap and access transactions on Ethereum. To address this, light client is enabled, which only stores a small fraction of blockchain data and relies on bootstrapped full nodes for transaction retrievals. However, because the retrieval requests are outsourced, it raises several severe concerns about the integrity of returned results and the leakage of sensitive blockchain access histories, largely hindering the wider adoption of this important lightweight design. From another perspective, the continuously increasing blockchain storage also urges for more effective query functionalities for the Ethereum blockchain, so as to allow flexible and precise transaction retrievals.

In this paper, we propose EncELC, a new Ethereum light client design that enforces full-fledged protections for clients and enables rich queries over the Ethereum blockchain. EncELC leverages trusted hardware (e.g., Intel SGX) as a starting point for building efficient yet secure processing, and further crafts several crucial performance and security refinement designs to boost query efficiency and conceal leakages inside and outside SGX enclave. We implement a prototype of EncELC and test its performance in several real settings, and the results have confirmed the practicality of EncELC.

Mneme: A Mobile Distributed Ledger

Dimitris Chatzopoulos (Hong Kong University of Science and Technology, Hong Kong); Sujit Gujar (International Institute of Information Technology, Hyderabad, India); Boi Faltings (Swiss Federal Institute of Technology (EPFL), Switzerland); Pan Hui (Hong Kong University of Science and Technology & University of Helsinki, Hong Kong)

0
Advances in mobile computing have paved the way for new types of distributed applications that can be executed solely by mobile devices on device-to-device (D2D) ecosystems (e.g., crowdsensing). More sophisticated applications, like cryptocurrencies, need distributed ledgers to function. Distributed ledgers, such as blockchains and directed acyclic graphs (DAGs), employ consensus protocols to add data in the form of blocks. However such protocols are designed for resourceful devices that are interconnected via the Internet. Moreover, existing distributed ledgers are not deployable to D2D ecosystems since their storage needs are continuously increasing. In this work, we introduce Mneme, a DAG-based distributed ledger that can be maintained solely by mobile devices and operates via two consensus protocols: Proof-of-Context (PoC) and Proof-of-Equivalence (PoE). PoC employs users' context to add data on Mneme. PoE is executed periodically to summarize data and produce equivalent blocks that require less storage. We analyze the security of Mneme and justify the ability of PoC and PoE to guarantee the characteristics of distributed ledgers: persistence and liveness. Furthermore, we analyze potential attacks from malicious users and prove that the probability of a successful attack is inversely proportional to the square of the number of mobile users who maintain Mneme.

Session Chair

Kai Zeng (George Mason University)

Session 9-B

Data Management

Conference
2:00 PM — 3:30 PM EDT
Local
Jul 9 Thu, 2:00 PM — 3:30 PM EDT

A Randomly Accessible Lossless Compression Scheme for Time-Series Data

Rasmus Vestergaard, Daniel E. Lucani and Qi Zhang (Aarhus University, Denmark)

0
We detail a practical compression scheme for lossless compression of time-series data, based on the emerging concept of generalized deduplication. As data is no longer stored for just archival purposes, but needs to be continuously accessed in many applications, the scheme is designed for low-cost random access to its compressed data, avoiding decompression. With this method, an arbitrary bit of the original data can be read by accessing only a few hundred bits in the worst case, several orders of magnitude fewer than state-of-the-art compression schemes. Subsequent retrieval of bits requires visiting at most a few tens of bits. A comprehensive evaluation of the compressor on eight real-life data sets from various domains is provided. The cost of this random access capability is a loss in compression ratio compared with the state-of-the-art compression schemes BZIP2 and 7z, which can be as low as 5% depending on the data set. Compared to GZIP, the proposed scheme has a better compression ratio for most of the data sets. Our method has massive potential for applications requiring frequent random accesses, as the only existing approach with comparable random access cost is to store the data without compression.

On the Optimal Repair-Scaling Trade-off in Locally Repairable Codes

Si Wu and Zhirong Shen (The Chinese University of Hong Kong, China); Patrick Pak-Ching Lee (The Chinese University of Hong Kong, Hong Kong)

0
How to improve the repair performance of erasure-coded storage is a critical issue for maintaining high reliability of modern large-scale storage systems. Locally repairable codes (LRC) are one popular family of repair-efficient erasure codes that mitigate the repair bandwidth and are deployed in practice. To adapt to the changing demands of access efficiency and fault tolerance, modern storage systems also conduct frequent scaling operations on erasure-coded data. In this paper, we analyze the optimal trade-off between the repair and scaling performance of LRC in clustered storage systems. Specifically, we design placement strategies that operate along the optimal repair-scaling trade-off curve subject to the fault tolerance constraints. We prototype and evaluate our placement strategies on a LAN testbed, and show that they outperform the conventional placement scheme in repair and scaling operations.

URSAL: Ultra-Efficient, Reliable, Scalable, and Available Block Storage at Low Cost

Huiba Li (NiceX Lab, China); Yiming Zhang (NUDT & NiceX Lab, China); Haonan Wang (NiceX Lab, China); Ping Zhong (CSU, China)

0
In this paper we design URSAL, an HDD-only block store which provides ultra efficiency, reliability, scalability and availability at low cost. First, we unveil that parallelism is harmful to the performance of HDDs, and thus URSAL designs its storage servers which conservatively performs parallel I/O on HDDs to reduce tail latency. Second, the effectiveness of HDD journals for backup writes varies over different workloads, and thus URSAL collaboratively performs direct block I/O on raw disks and transforms small writes into sequential journal appends. Third, software failure ratios are nontrivial in large-scale block stores, and thus URSAL designs the (software) fault-tolerance mechanism for high availability. Micro benchmarks show that URSAL significantly outperforms state-of-the-art systems for providing HDD-only block storage.

Working Set Theorems for Routing in Self-Adjusting Skip List Networks

Chen Avin (Ben-Gurion University of the Negev, Israel); Iosif Salem and Stefan Schmid (University of Vienna, Austria)

2
This paper explores the design of dynamic network topologies which adjust to the workload they serve, in a demand-aware and online manner. Such self-adjusting networks (SANs) are enabled by emerging optical technologies, and can be found, e.g., in datacenters. SANs can be used to reduce routing costs by moving frequently communicating nodes topologically closer. However, such reconfigurations also come at a cost, introducing a need for online algorithms which strike an optimal balance between the benefits and costs of reconfigurations.

This paper presents SANs which provide, for the first time, provable working set guarantees: the routing cost between node pairs is proportional to how recently these nodes communicated last time. Our SANs rely on a distributed implementation of skip lists (which serves as the topology) and provide additional interesting properties such as local routing. Our first contribution is SASL^2, which is a randomized and sequential SAN algorithm that achieves the working set property. Then we show how SASL^2 can be converted to a distributed algorithm that handles concurrent communication requests and maintains SASL^2's properties. Finally, we present deterministic SAN algorithms.

Session Chair

Chunsheng Xin (Old Dominion University)

Session 10-B

Adaptive Algorithms

Conference
4:00 PM — 5:30 PM EDT
Local
Jul 9 Thu, 4:00 PM — 5:30 PM EDT

Automatically and Adaptively Identifying Severe Alerts for Online Service Systems

Nengwen Zhao (Tsinghua University, China); Panshi Jin, Lixin Wang and Xiaoqin Yang (China Construction Bank, China); Rong Liu (Stevens Institute of Technology, USA); Wenchi Zhang and Kaixin Sui (Bizseer Technology Co., Ltd., China); Dan Pei (Tsinghua University, China)

1
In large-scale online service system, to enhance the quality of services, engineers need to collect various monitoring data and write many rules to trigger alerts. However, the number of alerts is way more than what on-call engineers can investigate. Thus, in practice, alerts are classified into several priority levels using manual rules, and on-call engineers primarily focus on handling the alerts with the highest priority level (i.e., severe alerts). Unfortunately, due to the complex and dynamic nature of the online services, this rule-based approach results in missed severe alerts or wasted troubleshooting time on non-severe alerts. In this paper, we propose AlertRank, an automatic and adaptive framework for identifying severe alerts. Specifically, AlertRank extracts a set of powerful and interpretable features (textual and temporal alert features, univariate and multivariate anomaly features for monitoring metrics), adopts an XGBoost ranking algorithm to identify the severe alerts out of all incoming alerts, and uses novel methods to obtain labels for both training and testing. Experiments on the datasets from a top global commercial bank demonstrate that AlertRank is effective and achieves the F1-score of 0.89 on average, outperforming all baselines, and reduces the number of alerts to be investigated by more than 80%.

On the impact of accurate radio link modeling on the performance of WirelessHART control networks

Yuriy Zacchia Lun (IMT School for Advanced Studies Lucca, Italy); Claudia Rinaldi, Amal Alrish and Alessandro D'Innocenzo (University of L'Aquila, Italy); Fortunato Santucci (University of l'Aquila, Italy)

2
The challenges in analysis and co-design of wireless networked control systems are well highlighted by considering wireless industrial control protocols. In this perspective, this paper addresses the modeling and design challenge by focusing on WirelessHART, which is a networking protocol stack widely adopted for wireless industrial automation. Specifically, we first develop and validate a Markov channel model that abstracts the WirelessHART radio link subject to channel impairments and interference. The link quality metrics introduced in the theoretical framework are validated in order to enable the accurate representation of the average and extreme behavior of the radio link. By adopting these metrics, it is straightforward to handle a consistent finite-state abstraction. On the basis of such a model, we then derive a stationary Markov jump linear system model that captures the dynamics of a control loop closed over the radio link. Subsequently, we show that our modeling framework is able to discover and manage the challenging subtleties arising from bursty behavior. A relevant theoretical outcome consists in designing a controller that guarantees stability and improves control performance of the closed-loop system, where other approaches based on a simplified channel model fail.

Online Spread Estimation with Non-duplicate Sampling

Yu-e Sun and He Huang (Soochow University, China); Chaoyi Ma and Shigang Chen (University of Florida, USA); Yang Du (University of Science and Technology of China, China); Qingjun Xiao (SouthEast University of China, China)

1
Per-flow spread measurement in high-speed networks has many practical applications. Most prior work is sketch-based, focusing on reducing their space requirements to fit in on-chip memory. This design allows measurement to be performed at the line rate, but it has to accept tradeoff with expensive computation for spread queries (unsuitable for online operations) and large estimation errors for small flows. This paper complements the prior art with a new spread estimator design based on an on-chip/off-chip model which is common in practice. The new estimator supports online queries in real-time and produces spread estimation with better accuracy. By storing traffic data in off-chip memory, our design faces a key technical challenge of efficient non-duplicate sampling. We propose a two-stage solution with on-chip/off-chip data structures and algorithms, which are not only efficient but also highly configurable for a variety of probabilistic performance guarantees. We implemented our estimator in hardware using FPGA. The experiment results based on real traces show that our estimator increases the query throughput by around three orders of magnitude, reduces the mean relative (absolute) error by around two (one) orders of magnitude, and saves 84% on-chip memory for probabilistic guarantee in flow classification compared to the prior art.

Session Chair

Evgeny Khorov (IITP RAS)

Made with in Toronto · Privacy Policy · © 2020 Duetone Corp.