How to find out if my server is compromised?

I have a linux VPS and I received a complaint that my server was scanning on port 22 some other network. How do I find out if it was compromised or not?


I answered a question earlier today that has recommendations in this area:

Linux backdoors I should be wary of

If you suspect that it may have been one of your users and your default shell is bash, you can grep through the .bash_history. For example:

grep nmap /home/*/.bash_history

It's notable that your users can modify the history unless you've introduced methods to make it more difficult.