Big Data Computing: Modeling and Optimization

Abstract:
MapReduce framework is widely used to parallelize batch jobs since it exploits a high degree of multi-tasking to process them. However, it has been observed that when the number of servers increases, the map phase can take much longer than expected. This thesis analytically shows that the stochastic behavior of the servers has a negative effect on the completion time of a MapReduce job, and continuously increasing the number of servers without accurate scheduling can degrade the overall performance. We analytically model the map phase in terms of hardware, system, and application parameters to capture the effects of stragglers on the performance. Mean sojourn time (MST), the time needed to sync the completed tasks at a reducer, is introduced as a performance metric and mathematically formulated. Following that, we stochastically investigate the optimal task scheduling which leads to an equilibrium property in a datacenter with different types of servers. Our experimental results show the performance of the different types of schedulers targeting MapReduce applications. We also show that, in the case of mixed deterministic and stochastic schedulers, there is an optimal scheduler that can always achieve the lowest MST.

• Farshid Farhat, Diman Zad Tootaghaj, Anand Sivasubramaniam, Mahmut Kandemir, and Chita R. Das are with the school of electrical engineering and computer science, the Pennsylvania State University, University Park, PA, 16802, USA. Email: {fuf111,dxz149,anand,kandemir,das}@cse.psu.edu.

• Yuxiong He is with the Cloud Computing Futures group, the Microsoft Research, Redmond, WA 98052 USA. Email: yuxhe@microsoft.com.

• The work was done during my visit from MSR in June 2016 in Redmond WA.

Blind detection of low-rate embedding

Abstract:

Steganalysis of least significant bit (LSB) embedded images in spatial domain has been investigated extensively over the past decade and most well-known LSB steganography methods have been shown to be detectable. However, according to the latest findings in the area, two major issues of very low-rate (VLR) embedding and content-adaptive steganography have remained hard to resolve. The problem of VLR embedding is indeed a generic problem to any steganalyser, while the issue of adaptive embedding specifically depends on the hiding algorithm employed. The latter challenge has recently been brought up again to the area of LSB steganalysis by highly undetectable stego image steganography that offers a content-adaptive embedding scheme for grey-scale images. The authors new image steganalysis method suggests analysis of the relative norm of the image Clouds manipulated in an LSB embedding system. The method is a self-dependent image analysis and is capable of operating on low-resolution images. The proposed algorithm is applied to the image in spatial domain through image Clouding, relative auto-decorrelation features extraction and quadratic rate estimation, as the main steps of the proposed analysis procedure. The authors then introduce and use new statistical features, Clouds-Min-Sum and Local-Entropies-Sum, which improve both the detection accuracy and the embedding rate estimation. They analytically verify the functionality of the scheme. Their simulation results show that the proposed approach outperforms some well known, powerful LSB steganalysis schemes, in terms of true and false detection rates and mean squared error.

 

Modeling and Optimization of Straggling Mappers

ABSTRACT
MapReduce framework is widely used to parallelize batch jobs since it exploits a high degree of multi-tasking to process them. However, it has been observed that when the number of mappers increases, the map phase can take much longer than expected. This paper analytically shows that stochastic behavior of mapper nodes has a negative effect on the completion time of a MapReduce job, and continuously increasing the number of mappers without accurate scheduling can degrade the overall performance. We analytically capture the effects of stragglers (delayed mappers) on the performance. Based on an observed delayed exponential distribution (DED) of the response time of mappers, we then model the map phase by means of hardware, system, and application parameters. Mean sojourn time (MST), the time needed to sync the completed map tasks at one reducer, is mathematically formulated. Following that, we optimize MST by finding the task inter-arrival time to each mapper node. The optimal mapping problem leads to an equilibrium property investigated for different types of inter-arrival and service time distributions in a heterogeneous datacenter (i.e., a datacenter with different types of nodes). Our experimental results show the performance and important parameters of the different types of schedulers targeting MapReduce applications. We also show that, in the case of mixed deterministic and stochastic schedulers, there is an optimal scheduler that can always achieve the lowest MST.

[Tech Report] [Master Thesis] [IEEE Trans]

Last version > MapReduce_Performance_Optimization

Image Steganalysis of Low Rate Embedding in Spatial Domain

Abstract

LSB embedding in spatial domain with very low rate can be easily performed and its detection in spite of many researches is very hard, while BOSS competition has been held to break an adaptive embedding algorithm with low rate. Thus, proposing powerful steganalyzer of very low rate in spatial domain is highly requested. In this thesis it has been tried to present some algorithms to detect secret message with very low rate in spatial domain using eigenvalues analysis and relative auto-correlation of image.

First approach is based on the analysis of the eigenvalues of the cover correlation matrix that we used for the first time. Image partitioning, correlation function computation, constellation of the correlated data, and eigenvalues examination are major challenging parts of our analysis method. The proposed method uses the LSB plane of images in spatial domain, extendable to transform domain, for detecting low embedding rates that is a major concern in the area of the LSB steganography. Simulation results show that the proposed approach improves over some well-known LSB steganalysis methods, specifically at low embedding rates.

Our second image steganalysis method suggests analysis of the relative norm of the image parts manipulated in an LSB embedding system. Image partitioning, multidimensional cross-correlation, feature extraction, and rate estimation, as the major steps of the main analysis procedure. We then extract and use new statistical features, Parts-Min-Sum and Local-Entropies-Sum, to get a closer estimate of the embedding rate and the detection performance. Our simulation results, as compared to some recent steganographic methods show that our new approach outperforms some well-known, powerful LSB steganalysis schemes, in terms of true and false detection rates.

Keywords: Image Steganalysis, Eigenvalues Analysis, LSB Embedding, Relative Autocorrelation, Parts Min Sum, Embedding Rate Estimation, Local Entropies Sum.

Image Steganalysis of Low Bit-rate Embedding

Performance Modeling and Optimization of MapReduce

Abstract:
MapReduce framework is widely used to parallelize batch jobs of great companies. MapReduce splits the job for each mapper in the map phase and then intermediate tasks are synced in reducers to be processed in the next stage. It exploits a high degree of multi-tasking to process the jobs as soon as possible. However map and reduce phases are done by many parallel nodes, it has been realized that when the number of mappers increase map phase takes longer than usual. This problem known as stragglers issue has been observed in CDF of completion times of mapper nodes.
This paper shows that stochastic behavior of mapper nodes has a negative effect on the completion time of MapReduce framework, i.e. increasing the number of mapper nodes blindly not only manages resources effectively but also can degrade the performance. To the best of our knowledge this is the first time in this paper MapReduce framework is modeled as fork-join queues from HDFS storage to one reducer. We capture the stragglers problem and based on observed delayed exponential CDF of response time of mappers we model task inter-arrival and service rate of each mapper node. Mean sojourn time (MST) which is the time needed to sync the completed map tasks at one reducer is formulated. Then we minimize MST by finding the input mapping of jobs to each mapper node. Equilibrium of means as a property of MST minimization problem can be generalized to some other inter-arrival and service time distributions. In the case of mixed deterministic and stochastic modeling optimal solution can always show the lowest MST. This approach not only can capture the optimal mapping of mapper nodes but also can address the optimal number of mapper nodes to get the lowest response time by MapReduce framework.

Performance Modeling and Optimization of MapReduce

Eigenvalues-based LSB steganalysis

Abstract:
So far, various components of image characteristics have been used for steganalysis, including the histogram characteristic function, adjacent colors distribution, and sample pair analysis. However, some certain steganography methods have been proposed that can thwart some analysis approaches through managing the embedding patterns. In this regard, the present paper is intended to introduce a new analytical method for detecting stego images, which is robust against some of the embedding patterns designed specifically to foil steganalysis attempts. The proposed approach is based on the analysis of the eigenvalues of the cover correlation matrix used for the purpose of the study. Image cloud partitioning, vertical correlation function computation, constellation of the correlated data, and eigenvalues examination are the major challenging stages of this analysis method. The proposed method uses the LSB plane of images in spatial domain, extendable to transform domain, to detect low embedding rates-a major concern in the area of the LSB steganography. The simulation results based on deviation detection and rate estimation methods indicated that the proposed approach outperforms some well-known LSB steganalysis methods, specifically at low embedding rates.

Eigenvalues-based LSB steganalysis

SVD and Noise Estimation based Image Steganalysis

Abstract:
We propose a novel image steganalysis method, based on singular value decomposition and noise estimation, for the spatial domain LSB embedding families. We first define a content independence parameter, DS, that is calculated for each LSB embedding rate. Next, we estimate the DS curve and use noise estimation to improve the curve approximation accuracy. It is shown that the proposed approach gives an estimate of the LSB embedding rate, as well as information about the existence of the embedded message (if any). The proposed method can effectively be applied to a wide range of the image LSB steganography families in spatial domain. To evaluate the proposed scheme, we applied the method to a large image database. Using a large image database, simulation results of our steganalysis scheme indicate significant improvement to both true detection and false alarm rates.

Full text > SVD and noise estimation based image steganalysis

Multi-dimensional correlation steganalysis

Abstract:
Multi-dimensional spatial analysis of image pixels have not been much investigated for the steganalysis of the LSB Steganographic methods. Pixel distribution based steganalysis methods could be thwarted by intelligently compensating statistical characteristics of image pixels, as reported in several papers. Simple LSB replacement methods have been improved by introducing smarter LSB embedding approaches, e.g. LSB matching and LSB+ methods, but they are basically the same in the sense of the LSB alteration. A new analytical method to detect LSB stego images is proposed in this paper. Our approach is based on the relative locations of image pixels that are essentially changed in an LSB embedding system. Furthermore, we introduce some new statistical features including “local entropies sum” and “clouds min sum” to achieve a higher performance. Simulation results show that our proposed approach outperforms some well-known LSB steganalysis methods, in terms of detection accuracy and the embedding rate estimation.

Multi-dimensional correlation steganalysis

Game-theoretic model to mitigate packet dropping

Abstract:
Performance of routing is severely degraded when misbehaving nodes drop packets instead of properly forwarding them. In this paper, we propose a Game-Theoretic Adaptive Multipath Routing (GTAMR) protocol to detect and punish selfish or malicious nodes which try to drop information packets in routing phase and defend against collaborative attacks in which nodes try to disrupt communication or save their power. Our proposed algorithm outranks previous schemes because it is resilient against attacks in which more than one node coordinate their misbehavior and can be used in networks which wireless nodes use directional antennas. We then propose a game theoretic strategy, ERTFT, for nodes to promote cooperation. In comparison with other proposed TFT-like strategies, ours is resilient to systematic errors in detection of selfish nodes and does not lead to unending death spirals.

Website > Game-Theoretic Network Simulator (GTNS)

Full text > Game-theoretic approach to mitigate packet dropping in wireless ad-hoc networks

Code > GTNS