RAP is very similar to a stack canary, except designed to prevent against ROP.
EDIT: After speaking to spender from grsecurity, it turns out that what I'm describing here is a subset of the RAP functionality, specifically the return pointer protection. RAP is actually callled "Reuse Attack Protector", which is designed to protect against all forms of indirect calls. The paper you linked describes some of the functionality within RAP, of which both the return pointer protection and ICFG features are a part of.
We can see the following assembly from the paper:
The first block there sets up the RAP cookie:
; store the old value of rbx
; read the top value on the stack (the return pointer) and put it in rbx
; xor rbx with a random value stored in r12
; rbx now contains the RAP canary
Then, at the end of the function, before the ret:
; xor the RAP canary in rbx with the random value in r12
; this "decrypts" the stack pointer from the RAP canary
; compare the top value on the stack (the return pointer)
; with the value decrypted from the RAP canary
; if the comparison fails, jump to error
; restore the original value of rbx
; an error occured, quit the process
The idea behind ROP is that you would find instructions you want (gadgets) followed by a return instruction. This protection feature re-writes the functions so that the final instruction before each return is always a
pop %rbx, and previous instructions are used to validate the RAP canary. This makes it really difficult to find ROP gadgets outside of non-aligned instructions (i.e. gadgets that just happen to exist due to the binary interpretation of instructions outside normal alignment).
The protection can be applied to both usermode and kernel. The cookie value (the value in %r12) is regenerated per task, per syscall, and per iteration in some infinite loops (e.g. event handlers and dispatch loops).
The reason for the last one is that infinite loops often use a (this isn't quite correct).
ret to break out of the loop.
EDIT: After discussing this more with spender, I'm going to suggest waiting for the explanation to come out. There's a lot of subtlety to how the feature works and I'm not sure I can accurately cover it from the paper and my brief discusson on IRC. Once it's out I'll re-update this answer to give you a better idea of what it does.