Ethereum Virtual Machine (EVM) is the run-time environment for smart contracts and its vulnerabilities may lead to serious problems to the Ethereum ecology. With lots of techniques being developed for the validation of smart contracts, the security problems of EVM have not been well-studied. In this paper, we propose EVMFuzz, aiming to detect vulnerabilities of EVMs with differential fuzz testing. The core idea of EVMFuzz is to continuously generate seed contracts for different EVMs' execution, so as to find as many inconsistencies among execution results as possible, eventually discover vulnerabilities with output cross-referencing. First, we present the evaluation metric for the internal inconsistency indicator, such as the opcode sequence executed and gas used. Then, we construct seed contracts via a set of predefined mutators and employ dynamic priority scheduling algorithm to guide seed contracts selection and maximize the inconsistency. Finally, we leverage different EVMs as crossreferencing oracles to avoid manual checking of the execution output. For evaluation, we conducted large-scale mutation on 36,295 real-world smart contracts and generated 253,153 smart contracts. Among them, 66.2% showed differential performance, including 1,596 variant contracts triggered inconsistent output among EVMs. Accompanied by manual root cause analysis, we found 5 previously unknown security bugs in four widely used EVMs, and all had been included in Common Vulnerabilities and Exposures (CVE) database.