An apparatus has processing circuitry (4); memory access circuitry (15) to perform a guard tag check for a tag checking target address having an associated address tag, the guard tag check comprising comparing the address tag with a guard tag stored in a memory system in association with a block of one or more memory locations comprising an addressed location identified by the target address; and an instruction decoder (6) responsive to a random tag setting instruction specifying a tag setting target address, to control the processing circuitry (4) to set the address tag associated with the tag setting target address to a random tag value randomly selected from a set of candidate tag values.