Virtualization software has a variety of security-critical applications, including forming an integral part of the infrastructure behind cloud computing. The software provides isolation between guests and protects each guest from unwanted access by other co-tenants. In this work, we investigate the verification of isolation properties for virtualization software. We identify some of the challenges and opportunities in using traditional formal methods to verify security properties at this level of the software stack. We present a new methodology, based on model checking, for handling one of the biggest challenges: verification in the face of very large data structures. One weakness of using model checking is that the verification result is only as good as the model; we also present a framework for validating the model against the corresponding source code. We evaluate our methodology with a number of case studies. In our largest case study, the address translation function in the Bochs x86 emulator, verification completes successfully in 70 minutes.