Using lsof, netstat, ls, ps, looking through proc with ls, cat, etc. is likely to not work if there's a rootkit on the box. The whole point of a rootkit is to hide processes and files from these tools.
Get some statically linked versions of these bins on to the server, and hope they haven't patched your kernel. Are you sure that it's someone who has root? How do you know? Is it not possible that it's someone running this from a PHP script or something, that they've gotten on to the server with the help of a vulnerability in some customer's website code? Maybe it's even a customer doing this intentionally? I've seen this sort of thing where they don't even write the code to disk - some vuln in a PHP script lets them download code from some remote server and execute it from memory - PHP's require() accepts a URL. The usual thing to do here is to take the server offline and make a copy of the disk with a writeblocker in place to prevent further changes, etc. and then inspect the image of the disk on a machine that is not using any binaries from that disk. If there really is a rootkit in place then you'll likely find it. If you're unable to do this, perhaps boot up the server from a CD, there are plenty of forensic analysis/security targeted Linux boot CDs around. If you're unable to capture full packets, perhaps netflow would be useful? - look for incoming data to ports you don't expect. It's much more lightweight on your data storage, and probably doesn't involve you putting in a new server - but a bit heavier on your network kit. -- Nathan Ward
