A counter integrity tree for memory security includes at least one split-counter node specifying at least two counters each defined as a combination of a major count value shared between the at least two counters and a respective minor count value specified separately for each of the at least two counters. This increases the number of child nodes which can be provided per parent node of the tree, and hence reduces the number of tree levels that have to be traversed in a tree covering a given size of memory region. The minor counter size can be varied dynamically by allocating nodes in a mirror counter integrity tree for accommodating larger minor counters which do not fit in the corresponding node of the main counter integrity tree.