Adam,
Jakub apparently disputes the notion that prelink is
ever an untrusted binary. He explicitly builds it with
static linking which means prelink can't modify itself.
He says that one just needs to do a trivial md5sum
check on the prelink binary before using it.
Jack