It would be helpful to know what version of ping you have, from which package. Based on the strace, it doesn't look like the ping from iputils-ping 3:20020927-3 or the one from netkit-ping 0.10-10.3. For one thing, it reads from /dev/urandom, which neither of those seem to do.
It also seems that you cut off the part of the strace where it reads from /etc/nsswitch.conf and actually uses nss-mdns, which is an unfortunate omission. The actual failure seems to be a problem talking to the dns server that for some reason fails with EPERM. (You were running the strace as root, I hope?) sendmsg(4, {msg_name(16)={sa_family=AF_INET, sin_port=htons(5353), sin_addr=inet_addr("224.0.0.251")}, msg_iov(1)=[{"\31\377\0\0\0\1\0\0\0\0\0\0\3www\6google\3com\5loca"..., 38}], msg_controllen=24, {cmsg_len=24, cmsg_level=SOL_IP, cmsg_type=, ...}, msg_flags=0}, MSG_DONTROUTE) = -1 EPERM (Operation not permitted) Here's the corresponding query from my machine. Note that both iputils-ping and netkit-ping look like this, and note that it's using different syscalls than the ping in your strace: send(4, "\263H\1\0\0\1\0\0\0\0\0\0\3www\6google\3com\0\0\1\0\1", 32, 0) = 32 poll([{fd=4, events=POLLIN, revents=POLLIN}], 1, 5000) = 1 ioctl(4, FIONREAD, [94]) = 0 recvfrom(4, "\263H\201\200\0\1\0\3\0\0\0\0\3www\6google\3com\0\0\1\0"..., 1024, 0, {sa_family=AF_INET, sin_port=htons(53), sin_addr=inet_addr("192.168.1.1")}, [ 16]) = 94 -- see shy jo
signature.asc
Description: Digital signature