  Big data processing is often outsourced to powerful, but untrusted cloud
service providers that provide agile and scalable computing resources to weaker
clients. However, untrusted cloud services do not ensure the integrity of data
and computations while clients have no control over the outsourced computation
or no means to check the correctness of the execution. Despite a growing
interest and recent progress in verifiable computation, the existing techniques
are still not practical enough for big data processing due to high verification
overhead. In this paper, we present a solution called V-MR (Verifiable
MapReduce), which is a framework that verifies the integrity of MapReduce
computation outsourced in the untrusted cloud via partial re-execution. V-MR is
practically effective and efficient in that (1) it can detect the violation of
MapReduce computation integrity and identify the malicious workers involved in
the that produced the incorrect computation. (2) it can reduce the overhead of
verification via partial re-execution with carefully selected input data and
program code using program analysis. The experiment results of a prototype of
V-MR show that V-MR can verify the integrity of MapReduce computation
effectively with small overhead for partial re-execution.
