Description of problem:

$ rpm -q selinux-policy
selinux-policy-3.7.19-93.el6.noarch

rsyslog can be configured to use a spool directory to store logs when upstream syslog servers are not reachable.  The policy already has permissions for /var/spool/rsyslogd, but not /var/spool.  This prevents rsyslog from starting.

Also, it appears that rsyslog may need access to the random character device (likely to support the TLS configuration we have)

Here are the relevant audit.log entries:

type=AVC msg=audit(1307988290.489:19097): avc:  denied  { search } for  pid=12357 comm="rsyslogd" name="spool" dev=dm-0 ino=393585 scontext=unconfined_u:system_r:syslogd_t:s0 tcontext=system_u:object_r:var_spool_t:s0 tclass=dir
type=SYSCALL msg=audit(1307988290.489:19097): arch=c000003e syscall=4 success=no exit=-13 a0=7fff20b35ea0 a1=7fff20b35e00 a2=7fff20b35e00 a3=fffffff8 items=0 ppid=12356 pid=12357 auid=0 uid=0 gid=0 euid=0 suid=0 fsuid=0 egid=0 sgid=0 fsgid=0 tty=(none) ses=3132 comm="rsyslogd" exe="/sbin/rsyslogd" subj=unconfined_u:system_r:syslogd_t:s0 key=(null)
type=AVC msg=audit(1307988290.493:19098): avc:  denied  { read } for  pid=12358 comm=72733A616374696F6E203620717565 name="random" dev=devtmpfs ino=3783 scontext=unconfined_u:system_r:syslogd_t:s0 tcontext=system_u:object_r:random_device_t:s0 tclass=chr_file
type=SYSCALL msg=audit(1307988290.493:19098): arch=c000003e syscall=21 success=no exit=-13 a0=7f883d1f34e8 a1=4 a2=0 a3=0 items=0 ppid=1 pid=12358 auid=0 uid=0 gid=0 euid=0 suid=0 fsuid=0 egid=0 sgid=0 fsgid=0 tty=(none) ses=3132 comm=72733A616374696F6E203620717565 exe="/sbin/rsyslogd" subj=unconfined_u:system_r:syslogd_t:s0 key=(null)
type=ANOM_ABEND msg=audit(1307988290.493:19099): auid=0 uid=0 gid=0 ses=3132 subj=unconfined_u:system_r:syslogd_t:s0 pid=12358 comm=72733A616374696F6E203620717565 sig=6

I applied this custom policy and it starts and seems to run properly:

module rsyslogdlocal 1.0;

require {
	type syslogd_t;
	type random_device_t;
	type var_spool_t;
	class dir search;
	class chr_file read;
}

#============= syslogd_t ==============
allow syslogd_t random_device_t:chr_file read;
allow syslogd_t var_spool_t:dir search;

The version of rsyslog is: rsyslog-4.6.2-3.el6.x86_64

Thanks!