OK, this seems to have "undone" some of the changes. The addresses at the end of the dynamic section of objdump are gone on the affected binaries. I also noticed that the other systems I was checking the binaries against don't have prelink installed, so that would explain why those addresses weren't showing up on those systems.

I ran tripwire and started comparing that report against the previous alarm reports. I've found that some files (/usr/sbin/callback, /usr/sbin/diskdumpctl_proc,/usr/bin/a2p, /usr/bin/c++... ) are back to where they were, e.g. MD5s are now what they were previously, suggesting that prelink updated many of these files.

HOWEVER, not all of them are back to where they were. /usr/bin/aspell, /usr/lib/autofs/autofs-ldap-auto-master, /usr/sbin/iptstate still do not checkout against any previous tripwire reports.

Still looks like I'm going to have to reformat and reinstall...

Perhaps... perhaps not. prelink may well be a "plausible explanation" for what TripWire is saying. TripWire presumably would not know about prelinking. (And for what it's worth, I don't bother to use it here.) If you changed a library, then the consequence of prelink would indeed be a "changed binary," and TripWire would howl.

A quick search of Google for the two terms, tripwire prelink, seemed to hit pay dirt, including the note that in Fedora Core 4, prelinking occurs "every 14 days."

To me, it seems like a strange utility (not suspicious, just strange as in "of dubious value"), and the 14-day schedule makes it more-so. I junked the thing probably six months ago, along with other RH stuff that I couldn't readily explain/justify, and I certainly don't see "slugging performance" in its absence. As others have commented, it seems to me that this would be the kind of thing that one might run "after an RPM update," or "on request," but not "regularly." Yet obviously, RH does so. Again, I'm not saying that this is suspicious.

I noticed that FC3 does the same thing while I was exploring the prelink idea. It seems that it will also update every 7 days even if no RPM has been updated. This might be useful information, except that I never experienced such massive changes before the last two weeks. If I could explain all of the changes with this, I would be satisfied that nothing has been compromised.

Is there any chance the settings in /etc/sysconfig/prelink got changed?

Sure its possible, but nothing in it looks out of the ordinary.