Q:

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?

A:

There's no general recipe. If your system has been infected by an unknown trojan, all you can do is reinstall.
If you know that the trojan operates in a certain way — for example you know that the trojan doesn't infect the kernel — there may be a less harsh way of recovering. But that's entirely dependent on knowing how the trojan behaves. If all you have is the symptoms (such as your computer sending spam without your consent), there's no general technique: the trojan detector has to be smarter than the trojan designer (and lucky). As far as trojans are concerned, detection and hiding are like gun and armor: there is a technological escalation, and neither party has an intrinsic advantage (though hiders do have a head start).
Many systems have a secure distribution channel in place. For example, when you install a package from the Ubuntu repositories with the apt-based tools (apt-get, aptitude, synaptic, software center, …), the tool checks that the package is signed (vetted) by someone Ubuntu trusts. (Most distributions have a similar mechanism.) When you install a package from a PPA, all you can know is that the PPA owner vetted the package, which is no help if you have no reason to trust the PPA owner in the first place.
About trojans and backdoors, I strongly recommend reading Ken Thompson's Turing award lecture, Reflections on Trusting Trust. To summarize, he changed the compiler so that when compiling the login program, it would add code that allowed him to log in with a secret password; then he changed the compiler so that when it compiled itself, it would insert the code to add the backdoor; then he recompiled the whole system (in particular the login program and the compiler); finally he restored the compiler source to the original, unquestionable source. Again, read Ken Thompson's article; then you may also read David Wheeler's counterpoint, perhaps best apprehended through Bruce Schneier's blog article.

A:

If I understand correctly "trojan" described in this article couldn't be discovered in "normal" way as "normal" malware. This IRCd was behaving normally until he was used, so administrator could find this security hole only when: 1) it was used and action made by this hole caused entry in logs or was visible in some other way, 2) reading source code.
"Real" Linux malware should be also detected by AV software for Linux or AV LiveCD Rescue Disks, so you could scan computer using this software. As you can see in SecureList in list there is 1941 entries with Linux in name and that software should be detected by Kaspersky software. Quick look to this list shows that many entries are about some DDoS tools and exploits or tools that cannot spread automatically and could be used only as tools for attack (so aren't harmful).
For checking for backdoors/rootkits installed by cracker you could use tool that checks file checksums (you should generate list of files and checksums on clean system and update it after server software update). Every new file or file with wrong checksum is suspicious. List of checksum and tool that generate it should be on read only medium (cracker could also change for example md5sum for it's own version that shows wrong checksums). This way of finding malware could be used on 'stable' systems where software isn't upgraded every day.
Some malware could be detected by running netstat locally to check for network traffic, but if system is infected data showed by netstat could also be changed. In this case some solution is to monitor network traffic from another computer (for example from router, to check what traffic is sent to the internet).

A:

SELinux and AppArmor exist for prevention of trojan / rootkit and other infections. I tell the case for SELinux, which I know better.
With SELinux enabled, you give a context to all the process (daemon included) you install on the machine. You also label the file system to work with the context, matching them.
When a process tries to do something not within its context, you receive a message, and, if SELinux is in enforcing mode, the action cannot complete.
This way, if your ircd trojan was willing to overwrite the ps command or something else (common strategy for trojans / rootkits / worms to avoid detection), i would not be allowed to do that. And you would be informed.
I knkow it's difficult to configure, but my machines are working with SELinux enforced right now, and my (two) Fedora laptops can do anything a desktop needs without too much hassle.
Even my home server is now in enforcing mode.
Another strategy is a regular run of rootkit detectors which calculate a checksum for the cirtical commands, and inform you regarding changes in the basic commands.
I work with both the SELinux and the rkhunter enabled (plus a clamav antivirus).
Regards

