Mechanisms to protect the integrity of a data structure that is traversed to locate protected memory pages are provided. Leaf nodes of the data structure store mappings that indicate which memory pages are protected. Both the pages indicated by the mappings and the pages that store the data structure are monitored by a tracing service that sends a notification to the hypervisor when a write to a traced page occurs. When system software receives such a notification, the system software traverses the data structure to determine whether any of the memory pages of the data structure is the traced page that was written to. If so, the alert action for that page is performed. If not, the system software determines whether any of the mappings in the leaf nodes include such a page and, if so, the alert action for that page is performed.