Thanks to Pierre Chifflier, Debian now has setroubleshoot packaged. The good thing about setroubleshoot is that it gives you a very user friendly message about the SELinux violations that occur on your box while you were doing something.
Now that something is very difficult to define (at least for Debian). My day job requires me to work on the RHELdistribution which has very good SELinux policy defined (Same is the case with Fedora). Here's a list of things which Debian's SELinux policy lacks and that RHEL/Fedora's doesn't
`acpi -V` raises a violataion
`dmesg` raises a violation
`apt-get update` raises a violation
You can't suspend, that raises a violation
nvidia module load raises a violation (Oh!! Well. That's binary-only. But the same doesn't raise a violation in Fedora)
So even though I'd love to use SELinux on Debian, I can't. Basic tasks are seen as violation by the Debian SELinux Policy. Try out enabling SELinux in Permissive mode and install setroubleshoot. You'll see setroubleshoot pop-up a SELinux violation every 5 seconds. Turns out that Debian's SELinux policy is becoming just too too much secure and thus interfering with the user using the OS.
Although I’m not a Debian user at the moment, but I see such things as that the policy needs some more Debian specific rules or one needs to be accustomed to using the box in SELinux way :). I experienced similar things in Gentoo "Hardened" GNU/Linux, which I used for around 6 months trying to fix policy, where it lacks. Hope to see SELinux "well" integrated in other distributions soon :).