I've been using Red Hat and Fedora for ages and I feel that I have never had anything but trouble from selinux. I have got false alarms, selinux broke ppp and updating the packages selinux-policy and selinux-policy-targeted slows updating my system to the latest packages. So this is what I did:
1. Change SELINUX=disabled
2. Execute yum erase selinux-policy selinux-policy-doc selinux-policy-devel selinux-policy-targeted
This frees 38 MB in Fedora 17 and makes "yum update" faster and saves you from false alarms. You can't remove libselinux because of the dependencies, but it is not necessary to get rid of the worst problems of selinux.
I strongly suggest that selinux should be disabled by default in Fedora.
---------- Post added at 11:54 AM ---------- Previous post was at 10:07 AM ----------
In fact file /etc/sysconfig/selinux belongs to package selinux-policy. So if you remove selinux-policy it will be gone, and there is no use in changing it. Just ignore step 1 and execute step 2 in my post above.
Boot after step 2 and check that selinux is disabled. You should see this:
$ dmesg | grep -i selinux
[ 0.001224] SELinux: Initializing.
[ 0.001278] SELinux: Starting in permissive mode
[ 0.493303] SELinux: Registering netfilter hooks
[ 3.143814] SELinux: Disabled at runtime.
[ 3.143916] SELinux: Unregistering netfilter hooks
[ 3.190100] type=1404 audit(1336290660.693:2): selinux=0 auid=4294967295 ses=4294967295
The key line is "Disabled at runtime".
Another check is this:
$ if selinuxenabled; then echo enabled; else echo disabled; fi
It uses command selinuxenabled, which is in package libselinux-utils. This package is harmless and does not have to be erased.
Yet another update on file /etc/sysconfig/selinux: File /etc/sysconfig/selinux belongs to package selinux-policy, so it disappears when your remove that package. But /etc/sysconfig/selinux is just a symlink to file /etc/selinux/config - so make sure that it contains line "SELINUX=disabled". By the way, file /etc/selinux/config does not belong to any package after you remove selinux-policy! So you should edit /etc/selinux/config first and then remove the packages.