Even more interesting is how the FBI knew they'd been infiltrated before they themselves did?
(There's the obvious conspiracy style accusation in that they were already in there poking around... but that doesn't seem to ring true in this regard)
In the Marriot hack post-mortem, they shared that one of the tools they used (which successfully identified the attack) was IBM Guardium.
> Accenture told Marriott's IT staff that one of their security products, a database monitoring system called IBM Guardium, had detected an anomaly on the Starwood guest reservation database
Seeing large amounts of encrypted traffic leaving via a DNS tunnel during non-standard business hours for instance would be an example of such an anomaly. It's not always that easy to detect however.
Simply storing netflow data and graphing it would show it at a glance. Use a machine setup as a transparent bridge with only physical login if you are paranoid about the netflow data being modified.
Hiding on a box is easy. Hiding on the wire is hard.