I am a Linux admin at a web hosting company. I’ve seen lots of different hacks. If I wanted to go poking around on our customer’s boxes, I am certain I would find a hack of some sort before I went through 100 of them.*
Since I’m not certain about how your system is set up, this is a general guide given what you’ve told us so far.
This doesn’t look like a root compromise from the information that you have supplied. Terrible permissions on web-writeable directories and swiss-cheese code will get php shells and mailers installed on your system fairly quickly. They don’t usually lead to a root compromise of the server. The main problem in these situations is finding the code that’s being exploited to install the php apps. Removing the offending directories is not going to stop the problem, they’ll just install them somewhere else using the same security holes. Any web applications you have installed that are developed by others (e.g. wordpress, joomla, control panels such as ispCP or webmin) need to be updated to a current version. If you have any of these kinds of apps installed that are seriously out of date, after you update them, the problem is likely to be fixed, partly because this sort of thing is much easier to do against known apps. If after you’ve updated them all, you get hacked again, then it’s time to start examining any custom code you have installed on the website.
Also, if you have an ftp server running, check the logs for logins from strange places. Consider upgrading to something like sftp if you aren’t already running an encrypted file transfer.
Now, that’s most of the time. Sometimes the hacker’s goal isn’t to spam or DoS, which is usually easily accomplished with web apps like I describe above. Sometimes the hacker is ambitious, and they use the php shell to run a local exploit and get some sort of privileged user access. You need to check the server for a root compromise. Chkrootkit and rkhunter are seriously imperfect tools for doing this, but they are a good starting point. Look for odd users and for users that aren’t supposed to have passwords having them (e.g. bin having a password). Look for odd logins from strange places. If it is root compromised, there is no choice. You must reinstall and copy your data over from the old disk or backup.
If you only do one of the above, it is very likely you will get hacked again. Reinstalling the operating system will not secure the websites, and securing the websites will do you no good if the underlying system has been compromised.
Since Ubuntu 10.04 is going to be EOL soon, you will want to transfer the website to a server with a newer version of Ubuntu (e.g. 12.04 LTS) on it in the near future anyway. But don’t do it without securing the website first, since you’ll just end up back in the same boat if you don’t.
Fail2ban is very nice on systems where users can’t/won’t learn how to use ssh keys to authenticate. You can also configure it to protect other services like pop3/imap if you are running those. Even with it, I’d suggest restricting almost everyone in /etc/sudoers to an ssh key, with a backup user using a password for local access that is prohibited from ssh’ing in.
I’m ambivalent about selinux. I think it’s a great concept that wasn’t implemented with the average person in mind. Most of our CentOS customers end up either configuring it where it might as well not be there, or turning it off entirely. Of course, if you have legacy code that you don’t want to re-write in order to secure it, selinux can be used to make it a non-threat, and might be the only solution to that problem.
Anyway, that’s the view of someone who sees this sort of thing weekly. I’m not even the security admin, I just take care of the hacks that I happen upon. There’s a fresh hell in the security admin’s queue every day.
*Don’t come bitching to me about the horrible security on their boxes. The customers have root, are big kids, and don’t always follow our suggestions for security, even after being hacked repeatedly.