Also processes you thinkk you DO recognize: Just for testing how alert my co-workers were, i had a program called "kswapd", just calculating prime-numbers... They never noticed. ;-)
Without any preperation it's harder. No point in installing tripwire, activating apparmor/selinux afterwards. Those things should be done after a fresh installation.
Indeed. I once found a gdm binary that had been subverted. I'm certain that would fly below the radar of many organizations.
hence 'rpm -Va'. No such facility with dpkg so maybe not a common thing to do but this should be pretty much standard Redhat/Centos procedure for checking for corrupt/modified binaries/libraries.