Hopefully you're taking regular VM snapshots so you've got some logs they can't delete. Otherwise good luck, someone Bitcoin mining is probably clever enough to cover their tracks.
Realistically an breach bad enough that they have server control is probably through the web. The most common way I've seen is through various CMS code execution exploits. If your web apps allow file upload that's a really common way to get code running on the server as well