Software-defined Network (SDN), presented to be a novel architecture of network because of its separation of data plane and control plane, brings centralization and extensibility to network management as well as new attacks that exploit the flexibility of SDN. OpenFlow, which is the protocol that is applied by the majority of SDN, leads to the widely used definition of the communication between the controller and the switch resulting in similar implementations regardless of different vendors. In this paper, we focus on the mechanisms of packet processing and topology discovery and their fundamental weaknesses caused by general implementations or device limitations. Despite the common vulnerabilities, the universal standard mechanisms of basic function in SDN also enlighten us to present an automated attack discovery method based on the formal verification with a generic model of SDN system. We describe the abstraction of the SDN components, their key functions, and communications along with the malicious operations that could be executed by malicious hosts and malicious switches and translate them into a formal model of the SDN system. The formal verification carried on with the assertion representing the security properties derived from the common vulnerabilities of the SDN system reports the potential attack paths each of which shows an attack process. Our evaluation shows that our method can discover feasible attack paths efficiently and effectively, with 23 attacks being identified, among which 2 are new. We further demonstrate the practicality of the 2 new attacks.

Multi-FPGA architectures have gained great interests in accelerating large-scale graph processing with great potential on high throughput and energy efficiency. As a beneficial complement, work stealing functions effectively to balance the computational workload on different FPGAs dynamically. Unfortunately, existing graph partitioning schemes originally designed in distributed settings potentially mismatch the work stealing-enabled multi-FPGA situations, where the computation is balanced while the communication overhead is unprecedentedly significant. In this paper, we present a 2-dimension balanced graph partitioning for work stealing assisted graph systems on multi-FPGAs, which can reduce communication overhead while preserving the optimal performance of work stealing. Our approach is novel by 1) exploring the tradeoff between load balance dimension and communication dimension in work-stealing-enabled graph processing system for the optimal performance, and 2) optimizing the memory access sequences to improve the granularity of graph partitioning for high-throughput graph analytics. Our experimental results show that our approach achieves 1.63x$\sim$2.56x speedups compared with state-of-the-art FPGA-based graph processing systems.

The emergence of big data applications makes efficient representation for large-scale dynamic data sets a challenge. The state-of-the-art design, i.e., the dynamic cuckoo filter (DCF), provides extensible approximate set representation by employing a novel chain based data structure which allows appending new building cuckoo filter blocks. However, such a design needs linearly increasing computation costs and memory space when a set scales. This makes it inefficient for big data sets. In this paper, we propose a novel data structure for dynamic big data sets, called logarithmic dynamic cuckoo filter (LDCF). LDCF uses a novel multi-level tree structure and reduces the worst insertion and membership testing times from O(N) to O(1), where N is the size of the set. At the same time, LDCF reduces the memory cost of DCF as the cardinality of the set increases. Comprehensive experiment results show that LDCF significantly reduces the membership checking time and the memory space cost for large-scale datasets compared to state-of-the-art designs.

Real-world stream data with skewed distributions raises unique challenges to distributed stream processing systems. Existing stream workload partitioning schemes usually use a “one size fits all” design, which leverages either a shuffle grouping or a key grouping strategy for partitioning the stream workloads among multiple processing units, leading to notable problems of unsatisfied system throughput and processing latency. In this article, we show that the key grouping based schemes result in serious load imbalance and low computation efficiency in the presence of data skewness while the shuffle grouping schemes are not scalable in terms of memory space. We argue that the key to efficient stream scheduling is the popularity of the stream data. We propose PStream, a popularity-aware differentiated distributed stream processing system which assigns the hot keys using shuffle grouping while assigns rare ones using key grouping. PStream leverages a novel light-weighted probabilistic counting scheme for identifying the currently hot keys in dynamic real-time streams. The scheme is extremely efficient in computation and memory consumption, so that the predictor based on it can be well integrated into processing instances in the system. We further design an adaptive threshold configuration scheme, which can quickly adapt to the dynamical popularity changes in highly dynamical real-time streams. We implement PStream on top of Apache Storm and conduct comprehensive experiments using large-scale traces from real-world systems to evaluate the performance of this design. Results show that PStream achieves a 2.3× improvement in terms of processing throughput and reduces the processing latency by 64 percent compared to state-of-the-art designs.

Efficient set representation and membership testing are important in various big data applications. The state-of-the-art Cuckoo filter design shows great advantages in both query efficiency and the support of item deletion, compared to previous Bloom filter and its variants. However, in this work, we show mathematically and experimentally that Cuckoo filter may suffer serious performance degradation during element insertion because of its random choice strategy for inserting an element into the candidate buckets. Such a random choice strategy incurs load imbalance among different buckets in Cuckoo filter and can lead to frequent relocations and the consequent long time for inserting an item. To solve this problem, we propose a novel design which leverages the principle of the power of two choices to select the better candidate bucket during inserting an element. Our design balances the load distribution among buckets in Cuckoo filter and avoids a large amount of relocations during insertion. We implement our design and apply it in real-world applications. We conduct comprehensive experiments using large-scale data sets collected from real world systems to evaluate the performance of this design. The results show that our design significantly reduces the average number of relocations of Cuckoo filter by 35%, as well as reducing item inserting latency by 25%.

Many BigData applications require to perform quick join operations on different large-scale real-time data streams. The key challenge to design an efficient stream join system is how to reasonably partition the streaming data among distributed processing nodes to avoid high density of join computation. However, the skewed distribution of real world streams raises great challenges for streaming data partitioning in distributed stream join systems. Existing hash based partitioning schemes incur significant load imbalance which leads to low system throughput and long processing latency, while shuffling based strategies incur redundant join computation and much more communication. To address this issue, in this paper, we propose and implement a scalable distributed stream join system, Simois, which shuffles the potential top heavy-load keys while hashing the others. However, how to identify the keys which lead to the heavy workload imbalance is challenging, because the heavy workload is determined by the current joint status of two streams, and the distribution of the two streams may change with time. To solve this problem, we design a novel efficient exponential counting scheme for identifying the keys with the heaviest workload in the two dynamic streams. The proposed exponential counting scheme needs extremely low computation and space cost, so that it can be well implemented in a stream processing system. Moreover, we design a popularity decline algorithm to make our design adaptive to the highly dynamic changes of streams. We implement Simois on top of Apache Storm and conduct comprehensive experiments using large-scale real world traces. Experiment results show that Simois improves the system throughput significantly by 52% and reduces the average latency by 37%, compared to existing state-of-the-art designs.

In the bigdata era, many applications are required to perform quick and accurate join operations on large-scale realtime data streams, such as stock trading and online advertisement analysis. To achieve high throughput and low latency, distributed stream join systems explore efficient stream partitioning strategies to execute the complex stream join procedure in parallel. Existing systems mainly deploy two kinds of partitioning strategies, i.e., random partitioning and hash partitioning. Random partitioning strategy partitions one data stream uniformly while broadcasting all the tuples of the other data stream. This simple strategy may incur lots of unnecessary computations for low-selectivity stream join. Hash partitioning strategy maps all the tuples of the two data streams according to their attributes for joining. However, hash partitioning strategy suffers from a serious load imbalance problem caused by the skew distribution of the attributes, which is common in real-world data. The skewed load may seriously affect the system performance. In this paper, we carefully model the load skewness problem in distributed join systems. We explore the key tuples which lead to the heavy load skewness, and propose an efficient key selection algorithm, GreedyFit to find out these key tuples. We design a lightweight tuple migration strategy to solve the load imbalance problem in real-time and implement a new distributed stream join system, FastJoin. Experimental results using real-world data show that FastJoin can significantly improve the system performance in terms of throughput and latency compared to the state-of-the-art stream join systems.

Event stream dissemination dominates the workloads in large-scale Online Social Network (OSN) systems. Based on the de facto per-user view data storage, event stream dissemination raises a large amount of inter-server traffic due to the complex interconnection among OSN users. The state-of-the-art schemes mainly explore the structure features of social graphs to reduce the inter-server communications for event stream dissemination. Different sub-graph structures are exploited for achieving approximated optimal solutions. However, such schemes incur prohibitively high cost of either computation or communication. In this work, we follow a different design philosophy by using a game theoretic approach, which decomposes the highly complex graph computation problem into rational decision making of every individual social link. Specifically, we propose a novel social piggyback game to achieve a more efficient solution. We mathematically prove the existence of the Nash Equilibrium of the social piggyback game. Moreover, we propose an efficient best response dynamic algorithm to achieve the Nash Equilibrium, which quickly converges in a small number of iterations for large-scale OSNs. We further show that the communication cost of this design achieves a 1.5-approximation of the theoretical social optimum. We conduct comprehensive experiments using large-scale real-world traces from popular OSN systems as well as implement a prototype system to evaluate the performance of this design. Results show that the social piggyback game achieves a significant 302× improvement in system efficiency compared to existing schemes.

Real-world stream data with skewed distribution raises unique challenges to distributed stream processing systems. Existing stream workload partitioning schemes usually use a “one size fits all” design, which leverage either a shuffle grouping or a key grouping strategy for partitioning the stream workloads among multiple processing units, leading to notable problems of unsatisfied system throughput and processing latency. In this paper, we show that the key grouping based schemes result in serious load imbalance and low computation efficiency in the presence of data skewness while the shuffle grouping schemes are not scalable in terms of memory space. We argue that the key to efficient stream scheduling is the popularity of the stream data. We propose and implement a differentiated distributed stream processing system, call DStream, which assigns the popular keys using shuffle grouping while assigns unpopular ones using key grouping. We design a novel efficient and light-weighted probabilistic counting scheme for identifying the current hot keys in dynamic real-time streams. Two factors contribute to the power of this design: 1) the probabilistic counting scheme is extremely computation and memory efficient, so that it can be well integrated in processing instances in the system; 2) the scheme can adapt to the popularity changes in the dynamic stream processing environment. We implement the DStream system on top of Apache Storm. Experiment results using large-scale traces from real-world systems show that DStream achieves a 2.3× improvement in terms of processing throughput and reduces the processing latency by 64% compared to state-of-the-art designs.

Retrieving relevant data for users in online social network (OSN) systems is a challenging problem. Cassandra, a storage system used by popular OSN systems, such as Facebook and Twitter, relies on a DHT-based scheme to randomly partition the personal data of users among servers across multiple data centers. Although DHT is highly scalable for hosting a large number of users (personal data), it leads to costly inter-server communications across data centers due to the complex interconnection and interaction among OSN users. In this paper, we explore how to retrieve the OSN content in a cost-effective way by retaining the simple and robust nature of OSNs. Our approach exploits a simple, yet powerful principle called Community-Based Locality (CBL), which posits that if a user has a one-hop neighbor within a particular community, it is very likely that the user has other one-hop neighbors inside the same community. We demonstrate the existence of community-based locality in diverse traces of popular OSN systems such as Facebook, Orkut, Flickr, Youtube, and Livejournal. Based on the observation, we design a CBL-based algorithm to build the content index in OSN systems. By partitioning and indexing the relevant data of users within a community on the same server in the data center, the CBL-based index avoids a significant amount of inter-server communications during searching, making retrieving relevant data for a user in large-scale OSNs efficient. In addition, by using CBL-based scheme we can provide much faster search response and balanced loads. We conduct comprehensive trace-driven simulations to evaluate the performance of the proposed scheme. Results show that ourscheme significantly reduces the network traffic by 73 percent while reduces the query latency by 35 percent compared with existing schemes.

Event stream dissemination dominates the workloads in large-scale Online Social Network (OSN) systems. Based on the de facto per-user view data storage, event stream dissemination raises a large amount of inter-server traffics due to the complex interconnection among OSN users. The state-of-the-art schemes mainly explore the structure features of social graphs to reduce the inter-server messages for event stream dissemination. Different sub-graph structures are exploited for achieving the approximated optimal assignment. However, such schemes incur high costs of computation or communication. In this work, we follow a different design philosophy by using a game theoretic approach, which decomposes the high complex graph computation problem into individuals' rational strategy selection of each node. Specifically, we propose a novel social piggyback game to achieve a more efficient solution. We mathematically prove the existing of the Nash Equilibrium of the social piggyback game. Moreover, we propose an efficient best response dynamic algorithm to achieve the Nash Equilibrium, which quickly converges in a small number of iterations for large-scale OSNs. We further show that the communication cost of this design achieves a 1.5-approximation of the theoretical social optimal. We conduct comprehensive experiments to evaluate the performance of this design using large-scale real-world traces from popular OSN systems. Results show that the social piggyback game achieves a significant 302× improvement in system efficiency compared to existing schemes.

Retrieving relevant data for users in online social network (OSN) systems is a challenging problem. Cassandra, a storage system used by popular OSN systems, such as Facebook and Twitter, relies on a DHT-based scheme to randomly partition the personal data of users among servers across multiple data centers. Although DHT is highly scalable for hosting a large number of users (personal data), it leads to costly inter-server communications across data centers due to the complex interconnection and interaction among OSN users. In this paper, we explore how to retrieve the OSN content in a cost-effective way by retaining the simple and robust nature of OSNs. Our approach exploits a simple, yet powerful principle called Community-Based Locality (CBL), which posits that if a user has an one-hop neighbor within a particular community, it is very likely that the user has other one-hop neighbors inside the same community. We demonstrate the existence of community-based locality in diverse traces of popular OSN systems such as Facebook, Orkut, Flickr, Youtube, and Livejournal.