MapReduce, a cloud computing paradigm, is gaining popularity. However, like all open distributed computing frameworks, MapReduce suffers from the integrity assurance vulnerability: it takes merely one malicious worker to render the overall computation result useless. Existing solutions are effective in defeating the malicious behavior of non-collusive workers, but are futile in detecting collusive workers. In this paper, we focus on the mappers, which typically constitute the majority of workers, and propose the Verification-based Integrity Assurance Framework (VIAF) to detect both non-collusive and collusive mappers. The basic idea of VIAF is to combine task replication with non-deterministic verification, in which consistent but malicious results from collusive mappers can be detected by a trusted verifier. We have implemented VIAF in Hadoop, an open source MapReduce implementation. Our theoretical analysis and experimental result show that VIAF can achieve high task accuracy while imposing acceptable overhead.