Principles of basic file system integrity auditing

You may know about file system integrity auditing tools, but how should you use them? It's not as difficult as it might look.

Sometimes, file system integrity auditing is the only way to be sure your system has not been compromised. When firewalls, malware scanners, intrusion detection systems, and your own careful computer use behavior all fail, you may never know about it, if the intrusion is subtle enough--unless you perform regular integrity audits.
Couple that with regular backups, and you have a ready-made way to detect, and recover from, the most insidious of system compromises.
There are at least dozens of tools you can use to create snapshots of a file system and compare them to audit the integrity of a file system. In theory, all you really need to do is:

1. Take a snapshot of the file system that is not altered by any malicious software such as a rootkit.
2. Maintain the snapshot somewhere that it cannot be altered even if the system is compromised.
3. Compare it with another snapshot later so you can determine what changes have taken place, if any.

Many tools exist that can perform these tasks, with varying levels of ease and effectiveness. The numerous tools exist in part because different tools are better suited to different circumstances. Differences in operating systems, network resources that can be used for remote snapshot generation and storage, specificity of file system selection for snapshots, automated scheduling and notification, and other factors may all need to be taken into account when selecting a file system integrity auditing tool set.
The tools
Tripwire is a well known integrity auditor, briefly described in "Implement integrity auditing with basic utilities":

Tripwire is probably the most widely recognized, and most widely used, professional-grade integrity auditing system. The original commercial software is called Tripwire Change Auditing, but there's an open source version of it as well that's available for any major open source Unix-like operating system.

One reason it is so widely used is the fact that it is very flexible, and can be configured to perform well under a staggering range of circumstances.
On the other hand, if you can get all the functionality you need from software that is already installed on the system, perhaps you should just use tools you have. Options such as bending rsync to your will can prove simpler than installing and maintaining a separate file-system-integrity auditing system.
In fact, if you use a backup tool such as rsync as a file system integrity auditor, you by definition also have backups of the relevant parts of the file system, thus killing two birds with one stone.
Some operating systems have tools that others do not, and these might be worth investigating. For instance, if you are running a FreeBSD system, and you keep backups (you do keep backups, right?) using software that is not well suited to double-duty as a file system integrity auditing system, a utility called mtree that is part of every standard FreeBSD install, might suit your integrity auditing needs.
The tool itself is used by the FreeBSD install to automate creation of the directory hierarchy for the OS, and the Ports system uses it to generate directory hierarchies for installed ports. Since it is already there for you to use as needed, you can use mtree for file system integrity auditing fairly easily. It might even give you capabilities you would not get with other tools; for instance, unlike Tripwire, mtree is aware of file flags.
Rules of thumb
While the specific actions taken to perform snapshot capture and integrity audit comparison varies from one tool to the next, the general rules of thumb for how to get the most from file system integrity auditing are pretty much universal:

1. The less often part of your file system changes for legitimate reasons, the more appropriate it is to use integrity auditing for that part of the file system. For instance, on a Unix system, the /var file system typically changes on a constant basis because many log files live there; maintaining usable snapshots for part of a file system that contains constantly updated logs is nigh impossible. On the other hand, /bin should change very rarely, as this contains only the core system tools--among the most stable executable tools on most systems.
2. The more important a given part of the file system is to the basic operation of the system, particularly if it contains executable system utilities, the more important for security purposes it is to ensure that part of the file system is covered by your integrity auditing policy. Core system utilities in particular are targeted by rootkits, because replacing a good utility with one that automatically covers a malicious security cracker's tracks is the most common methodology for allowing a savvy security cracker to remain undiscovered. The /bin file system contains such utilities on Unix systems, while /var is often absent of any executables used in basic system operation.
3. Snapshots should be taken by a tool that is not subject to compromise if the system itself is compromised. This usually means either storing the executable program file itself on read-only media such as a non-rewritable CD, to execute it from a CDROM drive, or running it from a remote computer that is relatively safe from compromise by someone who has compromised the target system. If someone compromises a system and, while there, compromises the tool that is used to capture and compare snapshots, the integrity auditing system will not do you much good.
4. Snapshots should be stored where they, too, cannot be compromised. Regardless of how good a tool you have, and how well you protect it from compromise, if a malicious security cracker can change the snapshots themselves, they aren't going to provide accurate information about the comparison of previous and current file system states.
5. Run regular audits against a known good snapshot. The only time you should need to keep a new known good snapshot in storage is when you need to make a change to the system, thus altering the current known good state of the system. Some file system integrity auditing implementations--particularly those integrated with your backup tool, such as some of the ways rsync can be used to run integrity auditing--may require you to effectively take snapshots more often because of the fact your backups are your snapshots. When possible, though, even your backups should only be taken when things change from a previous state, and for parts of the file system that are stable enough to benefit from integrity auditing the times that the state of the file system changes should be well-known in advance.
6. If you have to change something on a file system for which you maintain snapshots for integrity auditing, make sure you audit it by comparing the filesystems current state with that of the last known good snapshot just before changing anything. This ensures that you will know with as much certainty as possible that nothing had been compromised before any changes were made. If you find a problem, track it down and deal with it right away, before making the changes you need to make, or you will have completely invalidated the purpose of an integrity auditing system.
7. If you make a change to a file system for which you maintain snapshots for integrity auditing, and you have made a change (presumably after doing an integrity audit), you should take a new snapshot immediately--before any malicious security crackers might have a chance to change something. Once you have made legitimate, authorized changes, the old snapshots you have are no longer valid, and need to be replaced so you will have known good snapshots against which to run comparisons for future audits.
8. Keep backups--or even completely redundant backup servers--that correspond with known good snapshots, if you have any need to be able to restore quickly in case of a compromise. If you are running a server for which uptime is important, and you discover that the system has been compromised by unauthorized changes, you do not want to have to take the system offline while installing from scratch if you can avoid it. A good backup that corresponds to your last known good snapshot can greatly reduce your recovery time, even if there is nothing on the system you cannot technically reconstruct from scratch.
9. Do not allow any sensitive information to be handled by a system that an integrity audit indicates has been affected by an unauthorized change, at least until you clear up the problem (most likely by restoring from a known good backup or reinstalling). This is the whole point of an integrity auditing system: knowing when a system has been compromised, so you can prevent any further damage from occurring and recover from the security breach.
10. Never assume that, just because you only found an unauthorized change in only one part of the system, the unauthorized changes you found are the only unauthorized changes that have been made.

The more likely your systems are to be specifically targeted, the more seriously you should consider implementing a file system integrity auditing system to protect them--but even the most casual users with no specific high value target painted on their backs can benefit from an at least partial implementation of an integrity auditing system. The sooner you know you have been compromised, the less time the malicious security cracker has to do damage to your bottom line, or to use you as a tool against others.