Subject: Re: [nfsv4] Extensions to NFSv4 for Checksums

From: Eric Werme USG <[email-masked]>
Date: Fri, 10 Feb 2006 15:39:18 -0500 (EST)

>On Feb 9, 2006, at 7:57 PM, Eric Werme USG wrote:
>
>>
>>    The standard TCP checksum is arguably weak in that it's not  
>> resilient
>>    to certain single bit errors as well as data re-arrangement.
>>
>> What single bit errors does it miss?  In its simplest form, it's a
>> sum of 16 bit values with the carry folded back in.  A single
>> bit error will have values that are powers of two between 0x0001  
>> and 0x8000,
>> but the checksum requires that 0xffff be added or subtracted to fail.
>
>See http://citeseer.ist.psu.edu/stone00when.html

I've long felt that more messages evade the ethernet CRC than I'd
expect and long wished for someone to study things like in this paper.
I've also done things like defer UDP checksum processing until the NFS
or application thread is ready to process the message.  It both gets
the data in the right cache and maximizes the time something could
corrupt the data post-reception.

>To quote the abstract:
>"Traces of Internet packets from the past two years show that between
>1 packet in 1,100 and 1 packet in 32,000 fails the TCP checksum"

To quote the paper:
"This sum [internet checksum] will catch any burst error of 15 bits or
less, ..."
The draft should be corrected.

>In a Sun lab, we spent a few weeks tracking down a bad 10Mbps hub that
>was triggering exactly the case that this paper describes. Only
>caught by SCCS's stronger CRC.

The paper describes several cases.  "... just about any factor that could
cause a bad checksum periodically does."

>While protection at different layers is useful, it is not sufficient.
>Pushing checksums as close to the ends as possible is the only way
>to insure correctness.

>From the paper:
"In the past, one of the authors has periodically recommended
improving transmission performance by doing the checksum as part of
the DMA process or in the transmission path in the network
interface.  Based on this study, we can now say that advice is wrong
because it leaves data too exposed to hardware errors."

I was impressed with some of the corruption they uncovered, it certainly
says that parity/ecc on data paths is not enough.  Back in my PDP-11
days, I found a serial device that sometimes started the message with
an extra 00 byte.  The link protocol, DDCMP, saved a checksum such that
dividing the message by the CRC polynomial left a zero remainder.  The
extra 00 didn't change the math and left a valid message.

> Early testers of Sun's new ZFS filesystem
>that includes integrity checksums are getting surprised just how
>often the disks return bad data, even though there are various
>checks in drives and transports.

Ah, that must be related to something I didn't comment on.  See next message.

>> That flaky router I ran into didn't affect the data, but something
>> in the RPC/NFS header before the data.
>
>Math says that NFS is on shaky grounds, and real world experience
>has confirmed that for me.
>> Overall, I'm not convinced there a problem that needs fixing.
>
>Well we disagree.

Well, it may be more a matter of not agreeing on how to address the
issue.  It seems to me the first thing to do is to get excited when
a bad checksum is received.  Are there any systems out there that do
more than silently increment a counter when a bad checksum is found?
If we had console messages, flashing lights, and sirens instead....
The paper cited privacy concerns as a challenge to chasing down the
source of the problem.  Some of that (e.g. not application software)
can be dealt with by various diagnostic tests, though I'll grant you
it may be easier to add the application level checksum.

>> Eric (Ric) Werme         |  [email-masked]

>And still using a DEC address! :-)

My workstation is now zko.hp.com (at least they upgraded us to 100BaseT),
but zk3.dec.com lives on in the lab and we're still running Tru64 Unix's
Email system there.  Gotta test the software somewhere!

	-Ric

_______________________________________________
nfsv4 mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/nfsv4

---

From: Alok Aggarwal <[email-masked]>
Date: Fri, 10 Feb 2006 15:40:31 -0700 (MST)

> The draft should be corrected.

What the draft intended to say was two single bit errors in a TCP
datagram might cancel out in a way that they render the TCP checksum
vulnerable. I will correct it.

>> caught by SCCS's stronger CRC.

In the specific example David was talking about, single bit flips
were causing the original file data that looked like -

      0x2d, 0x43, 0x7a, 0x47, 0x01, 0xcb, 0x2e, 0x35,
      0x12, 0x7e, 0x30, 0x09, 0xb1, 0x00, 0x04, 0x54,

to turn into -

      0x2d, 0x43, 0x7a, 0x47, 0x01, 0xcb, 0x"e, 0x35,
      					   ^^
      0x12, 0x7e, 0x30, 0x09, 0xr1, 0x00, 0x04, 0x54,
 			       ^^
In the first bit flip we lost a bit and in the second bit flip
we gained a bit resulting in the bit errors cancelling out. Ones
complement of the original and corrupted data is the same.

Alok

---

From: Eric Werme USG <[email-masked]>
Date: Sat, 11 Feb 2006 08:48:59 -0500

Yes, two single bit errors at the same position in _any_ 16-bit "hexect"
will leave a valid checksum.

You said this was occurring in a hub, I would expect the ethernet
receiver would have high CRC error counts and the TCP receiver have
a high checksum error count.  I've long since forgotten the math to
know what it takes for those errors to evade the CRC.

Like I mentioned before, incrementing an error counter doesn't do justice
to the severity of the event.

BTW, my "wetware ECC" repaired my memory of the bad transmitter problem
I mentioned before.  I said it inserted a 0x00 byte, IIRC, it dropped the
first bit which was a 0.  It added a 0 bit at the end.  The net effect
was that all the bits in the message constituted a large number that
was left shifted by 1, i.e. multiplied by two.  The CRC calculation
essentially "divides" that number by the CRC polynomial and the remainder
is the checksum. By mulitplying the message by 2, the division resulted
in a checksum that was 2X, and the CRC check still passed.  If the
transmitted message plus checksum had been specced to result in a non-
zero remainder, then that would have been doubled and failed the check.

While that problem didn't have a significant impact (the higher level protocol
rejected it as malformed), it did leave me with an increased sense that
the hardware had it in for me.  That was confirmed by the DQ11 that got
me on a plane to Santa Barbara one Jan 2nd. hours after I discovered it
looked like a problem I saw at work but hadn't been able to solve.

Come to think of it, there was an elevated error counter in that case too.
That wound up being a great trip, I need to write that up somewhere.

	-Ric Werme