Okay, so, I had more time to dig a bit into this and, after some analysis, I got:

Errors being reproduced:

[1668392.078137] audit: type=1400 audit(1459311786.129:1375455): apparmor="DENIED" operation="sendmsg" info="Failed name lookup - disconnected path" error=-13 profile="/usr/sbin/dnsmasq" name="dev/log" pid=15735 comm="dnsmasq" requested_mask="w" denied_mask="w" fsuid=0 ouid=0

And apparmor dnsmasq profile:

#/usr/sbin/dnsmasq flags=(attach_disconnected) {
#/usr/sbin/dnsmasq flags=(complain) {
/usr/sbin/dnsmasq {

Without any flags.

And the command causing the apparmor errors:

root     16877  0.0  0.2  66416  3648 ?        S    13:23   0:00 sudo /usr/bin/neutron-rootwrap /etc/neutron/rootwrap.conf ip netns exec qdhcp-37d013b6-f6fa-4652-8073-5e7d2c418a9d env NEUTRON_NETWORK_ID=37d013b6-f6fa-4652-8073-5e7d2c418a9d dnsmasq --no-hosts --no-resolv --strict-order --bind-interfaces --interface=ns-aa95fe20-ff --except-interface=lo --pid-file=/var/lib/neutron/dhcp/37d013b6-f6fa-4652-8073-5e7d2c418a9d/pid --dhcp-hostsfile=/var/lib/neutron/dhcp/37d013b6-f6fa-4652-8073-5e7d2c418a9d/host --addn-hosts=/var/lib/neutron/dhcp/37d013b6-f6fa-4652-8073-5e7d2c418a9d/addn_hosts --dhcp-optsfile=/var/lib/neutron/dhcp/37d013b6-f6fa-4652-8073-5e7d2c418a9d/opts --dhcp-leasefile=/var/lib/neutron/dhcp/37d013b6-f6fa-4652-8073-5e7d2c418a9d/leases --dhcp-range=set:tag0,192.168.21.0,static,86400s --dhcp-lease-max=256 --conf-file=/etc/neutron/dnsmasq.conf --domain=openstacklocal

It is a "sudo-like" approach from openstack (rootwrap) to execute dnsmasq in a new network namespace with different privileges.

Ubuntu kernel 3.13.X has apparmor 3 alpha 6 code: https://pastebin.canonical.com/152812/
Ubuntu kernel 3.16 and 3.19 has apparmor 3 rc 1 code: https://pastebin.canonical.com/152813/

From apparmor I could see that the error comes from "aa_path_name" called by either:

- path_name *
- aa_remount
- aa_bind_mount
- aa_mount_change_type
- aa_move_mount
- aa_new_mount
- aa_unmount
- aa_pivotroot

So, since the job is being restarted by neutron (or at least it is trying to re-start it, causing the apparmor to block the access), I created a systemtap script to monitor path_name and check for dnsmasq trying to open "log" (allegedly /dev/log) file.

probe kernel.function("path_name").call {
	funcname = execname();
	if (funcname == "dnsmasq") {
		filename = reverse_path_walk($path->dentry);
		if (filename == "log") {
			printf("(%s) %s\n", execname(), filename);
			print_backtrace();
		}
	}
}

And got the backtrace from the denials:

(dnsmasq) log

 0xffffffff8132deb0 : path_name+0x0/0x140 [kernel]
 0xffffffff8132e413 : aa_path_perm+0xa3/0x130 [kernel]
 0xffffffff81337e26 : aa_unix_peer_perm+0x536/0x990 [kernel]
 0xffffffff8132c653 : apparmor_unix_may_send+0x73/0x150 [kernel]
 0xffffffff812eb8a6 : security_unix_may_send+0x16/0x20 [kernel]
 0xffffffff817019db : unix_dgram_connect+0x23b/0x250 [kernel]
 0xffffffff8164a987 : SYSC_connect+0xe7/0x120 [kernel]
 0xffffffff8164b68e : sys_connect+0xe/0x10 [kernel]
 0xffffffff817700cd : system_call_fastpath+0x1a/0x1f [kernel]

 When trying to check if "log" could be converted to "fullpath" by using systemtap function:

 	return task_dentry_path(task_current(),
		@cast(path,"path","kernel:nfs:kernel<linux/path.h>")->dentry,
		@cast(path,"path","kernel:nfs:kernel<linux/path.h>")->mnt)

I saw that I could resolve path for all other files but "/dev/log":

(dnsmasq) /usr/lib/x86_64-linux-gnu/libnfnetlink.so.0.2.0
(dnsmasq) /usr/lib/x86_64-linux-gnu/libmnl.so.0.1.0
(dnsmasq) /usr/lib/x86_64-linux-gnu/gconv/gconv-modules.cache
(dnsmasq) /etc/neutron/dnsmasq.conf
(dnsmasq) /etc/neutron/dnsmasq.conf
(dnsmasq) /etc/localtime
(dnsmasq) /etc/localtime
(dnsmasq) /etc/localtime
(dnsmasq) <unknown>

Because 

    function task_dentry_path:string(task:long,dentry:long,vfsmnt:long)

Couldn't handle the udev (vfsmnt) path. With that, I thought apparmor couldn't be handling udev path for different root vfsmnt (like a different FS namespace).

Checking iproute2 ipnetns.c I saw that executing a command in a new network namespace causes:

unshare(CLONE_NEWNS) AND
mount("", "/", "none", MS_SLAVE | MS_REC, NULL)

This second being possibly the "problem" - its intent is not to allow mounts to propagate back to parent task - since it basically removes a root vfsmnt from the execution taken in place, breaking apparmor (or even dentry cache) path resolution logic. Here, the needed flag "attach_disconnected" (present in apparmor path resolution logic) comes in place, to allow "/" to be added in path names missing leading / due to missing root vfsmnt from dentry cache.

To observe: 3.13 (apparmor 3 alpha 6) doesn't complain on disconnected paths but 3.16 and beyond (rc1) does (needing the flag "attach_disconnected").