The described embodiments perform a method for handling memory accesses by virtual machines in a computing device. The described embodiments include a reverse map table (RMT) and a separate guest accessed pages table (GAPT) for each virtual machine. The RMT has a plurality of entries, each entry including information for identifying a virtual machine that is permitted to access an associated page of data in a memory. Each GAPT has a record of pages being accessed by a corresponding virtual machine. During operation, a table walker receives a request from a given virtual machine to translate a guest physical address to a system physical address. The table walker checks at least one of the RMT and a corresponding GAPT to determine whether the given virtual machine has access to a corresponding page. If not, the table walker terminates the translating. Otherwise, the table walker completes the translating.