I am able to reproduce this just by having apparmor.d profile usr.sbin.rsyslogd removed from disable/ directory.
[ 674.165128] audit: type=1400 audit(1456491880.616:134): apparmor="DENIED" operation="sendmsg" profile="/usr/sbin/rsyslogd" name="/dev/log" pid=3639 comm="dhclient" requested_mask="r" denied_mask="r" fsuid=0 ouid=0 [ 674.165178] audit: type=1400 audit(1456491880.616:135): apparmor="DENIED" operation="sendmsg" profile="/usr/sbin/rsyslogd" name="/dev/log" pid=3639 comm="dhclient" requested_mask="r" denied_mask="r" fsuid=0 ouid=0
OR
[ 522.429097] audit: type=1400 audit(1456491728.880:113): apparmor="DENIED" operation="sendmsg" profile="/usr/sbin/rsyslogd" name="/dev/log" pid=3184 comm="sshd" requested_mask="r" denied_mask="r" fsuid=0 ouid=0 [ 527.268883] audit: type=1400 audit(1456491733.720:114): apparmor="DENIED" operation="sendmsg" profile="/usr/sbin/rsyslogd" name="/dev/log" pid=3239 comm="sshd" requested_mask="r" denied_mask="r" fsuid=0 ouid=0
I am able to reproduce this just by having apparmor.d profile usr.sbin.rsyslogd removed from disable/ directory.
[ 674.165128] audit: type=1400 audit(145649188 0.616:134) : apparmor="DENIED" operation="sendmsg" profile= "/usr/sbin/ rsyslogd" name="/dev/log" pid=3639 comm="dhclient" requested_mask="r" denied_mask="r" fsuid=0 ouid=0 0.616:135) : apparmor="DENIED" operation="sendmsg" profile= "/usr/sbin/ rsyslogd" name="/dev/log" pid=3639 comm="dhclient" requested_mask="r" denied_mask="r" fsuid=0 ouid=0
[ 674.165178] audit: type=1400 audit(145649188
OR
[ 522.429097] audit: type=1400 audit(145649172 8.880:113) : apparmor="DENIED" operation="sendmsg" profile= "/usr/sbin/ rsyslogd" name="/dev/log" pid=3184 comm="sshd" requested_mask="r" denied_mask="r" fsuid=0 ouid=0 3.720:114) : apparmor="DENIED" operation="sendmsg" profile= "/usr/sbin/ rsyslogd" name="/dev/log" pid=3239 comm="sshd" requested_mask="r" denied_mask="r" fsuid=0 ouid=0
[ 527.268883] audit: type=1400 audit(145649173