One feature pertains to an efficient algorithm to protect the integrity of a plurality of data structures by computing an aggregate message authentication code (MAC) over the plurality of data structures. An aggregate MAC may be constructed from a plurality of MAC values associated with a plurality of data structures. The aggregate MAC binds the plurality of data structures and attests to their combined integrity simultaneously. Rather than checking the integrity of a data structure when it is accessed, the aggregate MAC is periodically checked or verified, to ascertain the integrity of all data structures. If the aggregate MAC computed is different from the previously stored aggregate MAC, then all data structures that are part of the aggregate MAC are discarded.