netdev - [PATCH] ping mdev rounding issue

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Message-ID: <20141111091605.GA20540@cirno.bucko.me.uk>
Date:	Tue, 11 Nov 2014 09:16:05 +0000
From:	David Buckley <isreal-netdev-at-vger.kernel.org@...ko.me.uk>
To:	netdev@...r.kernel.org
Subject: [PATCH] ping mdev rounding issue

ping has a rounding issue in standard deviation computation.

It stores all values as integer micros, and computes standard deviation
as:

sqrt(SUM(time*time)/count - (SUM(time)/count)*(SUM(time)/count))

Because the second 'count' divide is performed before the multiply, a
rounding error results of the order O(sqrt(SUM(time)/count)).

Example: I ping my server twice. One takes 1000us, the second takes
1001us.

Standard deviation computed by ping is:

  sqrt((1000000+1002001)/2 - ((1000+1001)/2)*((1000+1001)/2))
= sqrt(1001000 - 1000*1000) = sqrt(1000) = 31

So we got a 1us difference and report a 31 us standard deviation.

If the samples are 999 and 1001
  sqrt((998001+1002001)/2 - ((999+1001)/2)*((999+1001)/2))
= sqrt(1000001 - 1000*1000) = sqrt(1) = 0

So more deviation makes for less /reported/ deviation.

This is reduced slightly in this case by more samples (100*1000+1001
reports deviation of 4us, for instance), but really it's caused by the
rounding error ((float)SUM(time)/count) - (SUM(time)/count) being
/multiplied/ by the average time. The expected error is of the order
sqrt(mean).

Example real-world bad computation:

PING 74.125.230.238 (74.125.230.238) 56(84) bytes of data.
64 bytes from 74.125.230.238: icmp_seq=1 ttl=51 time=16.1 ms
64 bytes from 74.125.230.238: icmp_seq=2 ttl=51 time=16.1 ms
64 bytes from 74.125.230.238: icmp_seq=3 ttl=51 time=16.2 ms
64 bytes from 74.125.230.238: icmp_seq=4 ttl=51 time=16.1 ms
^C
--- google.com ping statistics ---
4 packets transmitted, 4 received, 0% packet loss, time 3003ms
rtt min/avg/max/mdev = 16.132/16.170/16.246/0.161 ms

With patch (attached):

PING 74.125.230.238 (74.125.230.238) 56(84) bytes of data.
64 bytes from 74.125.230.238: icmp_seq=1 ttl=51 time=16.0 ms
64 bytes from 74.125.230.238: icmp_seq=2 ttl=51 time=16.1 ms
64 bytes from 74.125.230.238: icmp_seq=3 ttl=51 time=16.1 ms
64 bytes from 74.125.230.238: icmp_seq=4 ttl=51 time=16.1 ms
^C
--- 74.125.230.238 ping statistics ---
4 packets transmitted, 4 received, 0% packet loss, time 3003ms
rtt min/avg/max/mdev = 16.045/16.128/16.197/0.054 ms

-- 
David Buckley

View attachment "fix_rounding.patch" of type "text/x-diff" (794 bytes)