How to detect and remove a Linux trojan?

I recently (re)stumbled upon this: Linux Trojan Goes Unnoticed For Almost A Year (Unreal IRCd)

Yes, I know that adding some random PPA/software from an untrusted source is asking for trouble (or worse). I never do that, but many do (many Linux blogs and tabloids promote adding PPAs for fancy apps, without warning that it may break your system or worse still, compromise your security.)

How can a trojan horse or a rogue application/script be detected and removed?

It's always a game of cat and mouse with detection software. New malware is created, scanners get updated to detect it. There's always a lag between the two. There are programs that use heuristics that watch what software is doing and attempt to catch unwanted activity but in my opinion it's not a perfect solution and uses resources.

My advice is simple, don't install software from sources you don't trust but if you are like me and can't avoid the temptation, put them in a virtual machine (ie virtualbox) and play with it until you're confident it won't either bork your system or do things you didn't want.

Again, not a perfect solution but for now, a virtual machine has the best chance of isolating your machine from unwanteds.

Most anti-malware software for Linux/Unix simply searches for Windows malware. The occurences of Linux malware has usually been very limited, even in cases where the security updates are slow or don't come.

Basically, you only use software you trust and update daily, that's how you stay safe.

Another response said: "It's always a game of cat and mouse with detection software."
I disagree.

This is true of approaches that rely on signatures or heuristics for detecting malware.
But there is another way to detect malware: verify known goods:

• Tripwire, AIDE, etc. can verify files on disk.
  

• Second Look can verify the running kernel and processes.
  Second Look uses memory forensics to directly inspect the operating system, active services, and applications.
  It compares the code in memory to what has been released by the Linux distribution vendor. In this way it can immediately pinpoint malicious modifications made by rootkits and backdoors, and unauthorized programs (trojans, etc.).

(Disclosure: I am the lead developer of Second Look.)