Patent ID: 7770029

Claim:
A method of securing memory access patterns associated with data in a computer memory, comprising: storing each piece of the data in a separate memory block; associating each memory block with a respective node of a search tree, wherein the data structure of the search tree is implemented by pointers stored in each memory block; and periodically rearranging at least some of the nodes with respect to the data structure to obscure the memory access patterns, the periodically rearranging comprising: selecting a random node from a root node of the search tree based on a probability p; descending the search tree with a probability of 1−p by selecting a left and a right child node with equal probability such that the random node becomes the left or right child respectively; issuing a read request for a node of the search tree using the randomly selected label as retrieval criterion; and splaying the requested node to a root position of the search tree to rearrange the search tree.