RE: I-D ACTION:draft-cavanna-iscsi-crc-vs-cksum-00.txt

[julian_satran@il.ibm.com]

Pat,

Thanks a lot for you patience and hard work.  I assumed that was the case
based on the experimental results on the effects of ATM splicing on CRC and
checksums published in 1998 that show how data bias affects checksums.

On another subject - can you comment on weighted checksums?

Thanks,
Julo


pat_thaler@agilent.com on 13/03/2001 04:43:51

Please respond to pat_thaler@agilent.com

To:   Julian Satran/Haifa/IBM@IBMIL, ips@ece.cmu.edu
cc:   pat_thaler@agilent.com, Dafna_Sheinwald@il.ibm.com
Subject:  RE: I-D ACTION:draft-cavanna-iscsi-crc-vs-cksum-00.txt





Julian asked:

"Do you have a formula to evaluate Pud for low noise channels with BER = e?
Any formula to evaluate the conditional probability of an undetected error
on bursts of 17, 18, 19 bits?

Is there any reason to believe that we can approximate them to ones used
for
CRC?"

Abstract:

The following will show that the formula used in the case of CRC for Pud
does not apply to checksums. Many data sets with small differences produce
the same checksum while few such data sets produce the same CRC. Therefore,
Pud for checksum is significantly worse than that for CRC. For independent
bit errors, Pud is approximately 12,000 times worse for Fletcher32 than for
CRC and 22,000 times worse for Adler32 than for CRC.

Note:
While Fletcher32 is better than Adler32 for the error case analyzed here,
Fletcher32 has more susceptibility to two byte errors that Adler32 does not
have. Overall, Fletcher32 is not necessarily a better choice.

The grungy details:

The formula for Pud for CRC in a low noise channel is:

 Pud = Pcrc * Cn,x * Pxerrors

Where:
 Pcrc is the probability that the received CRC matches the errored message
 Cn,x is the number of combinations of 3 errors in an n bit message
 Pxerrors is the probability of getting a particular combination of 3
errors
 Pbe is the probability of a bit error.

Inserting the values for 3 bit errors in a 1000 byte message where Pbe <<
1:

 Pud = 2^-32 * C8000,3 * Pbe^3
     = 2^-32 * 85e9 * Pbe^3
     = 20 * Pbe^3

Note that this equation is assuming that the CRC in question does not
detect
all 3 bit errors. If the CRC detects all 3 bit errors as many do, the Pud
would be 0. Also, actually equals Pxerrors = (Pbe ^ errored_bits) * ((1 -
Pbe) ^ unerrored_bits, but the latter is very close to 1 for low noise
channels.

Approximately 20 positions of 3 bit errors cause undetectable errors in a
1000 byte message with the CRC.

How many 3 bit errors cause undetectable errors for checksums? In the
attached analysis of checksum Hamming distance and burst error detection, I
showed that an undetectable error for both checksums is formed by sequence
of three errored values with errors: x, -2x, and x. The same error pattern
in three values with equal spacing between them will cause an undetectable
error (see Undetectable 3 bit errors in non-consecutive values below).

For Adler32:
A value is one byte long.
For x = 1, 2, 4, 8, 16, 32 or 64: The three errors can be caused by a 1 bit
change each.

There are 998 sets of 3 consecutive bytes in a 1000 byte frame.
There are 996 sets of 3 bytes spaced with 1 bytes between them.
There are 994 sets of 3 bytes spaced with 2 bytes between them.
....
There are 2 sets of 3 bytes spaced with 498 bytes between them.

Therefore, the undetectable errors analyzed below yield (998 + 2) * 49 / 2
sets of bytes that can have one of 7 sets of 3 bits change for an
undetectable error in a 1000 byte frame. Of the 8 ways those three bits can
be changed, 2 of them produce an undetectable error.

If the pattern discussed here is the only one that produces 3 bit errors,
then Pud for 3 bit errors in a 1000 byte message with Adler32 would be:

  Pud = Pcsum * Cerror * P3errors

where
 Pcsum equals the probability that the 3 bit error results in a correct
checksum which is 0.25 for the 3 bit errors.
 Cerror is the number of combinations of undetectable 3 bit errors.
 P3errors is the probability of getting a particular combination of 3
errors.

   Pud  = 0.25 * (998 + 2) * 499/2 * 7 * Pbe^3
        = 437 * 10^3 * Pbe^3

For Fletcher32:
A value is two bytes long.
For x = 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192 or
16384: The three errors can be caused by a 1 bit change each.

In a 1000 byte message, there are 500 values.
There are 498 sets of 3 consecutive values in a 1000 byte frame.
There are 496 sets of 3 values spaced with 1 values between them.
There are 494 sets of 3 values spaced with 2 values between them.
....
There are 2 sets of 3 values spaced with 248 values between them.

Therefore, the undetectable errors analyzed below yield (498 + 2) * 249/ 2
sets of bytes that can have one of 15 sets of 3 bits change for an
undetectable error in a 1000 byte frame. Of the 8 ways those three bits can
be changed, 2 of them produce an undetectable error.

If the pattern discussed here is the only one that produces 3 bit errors,
then Pud for 3 bit errors in a 1000 byte message with Fletcher32 would be:

  Pud = 0.25 (498 + 2) * 249/2 * 15 * Pbe^3
      = 233 * 10^3 * Pbe^3

To recap:
CRC           Pud = 20 * Pbe^3
Adler32:      Pud = 437 * 10^3 * Pbe^3
Fletcher32:   Pud = 233 * 10^3 * Pbe^3

Regards,
Pat Thaler


------- Analysis of checksum Hamming distance and burst error detection
-----------

It is relatively easy to investigate the Hamming distance and burst
detection of Adler32 and Fletcher32 using mathematics. In the argument
below, I will use "value" to identify the quantities that get summed since
Adler sums bytes and Fletcher32 sums 16-bits.

Both Adler and Fletcher calculate for each value:

 S1 = (S1 + value) mod m
 S2 = (S2 + S1) mod m

where m is 65521 for Adler and 65535 for Fletcher.

Which means that for an n value string of values V1 to Vn:
 S1 = (V1 + V2 + ... + Vn (+ 1 for Adler)) mod m
 S2 = (n * V1 + (n-1) * V2 + ... + Vn (+ n for Adler)) mod m

A two bit error can only change two values. For a two bit error to be
undetectable the two changed values must produce no change to S1 and S2.

Let
 x be the change to the first errored value
 y be the change to the second errored value
 k be the separation between the first and second errored values.

Then for an undetectable error:

 delta S1 = (x + y) mod m = 0
 delta S2 = ((k + 1) * x + y) mod m = 0
          = (k * x + x + y) mod m =0
          = (k * x) mod m = 0          because (x + y) mod m = 0

Therefore, for an undetectable 2 bit error, k * x must be a multiple of m.

For Adler, m is prime and the maximum value of x is 255 so the only way to
satisfy the condition is for k to equal 65521. Then x can be any value so
it
could be a one bit error such as changing the lsb of the first value from 0
to 1. y would then need to be the inverse changing the lsb of the second
value from 1 to 0.

For Fletcher, m is factorable to 3, 5, 17, 257. For x to provide one or
more
of those factors, it would have to have more than a 1 bit change and y
would
have to have the inverse of that change which would mean an error of at
least 4 bits. The only way to get a two bit undetectable error is for k to
equal 65535.

So, Fletcher and Adler do have 2-bit undetectable errors if the messages
are
longer than the modulus.

What about burst protection? For Fletcher, we know that a change of a value
from all 0's to all 1's produces an undetectable error so we know that
burst protection is less than 16. k = 1 for a burst spread across two
consecutive values. Therefore, the only way for a burst spread across two
consecutive values to produce an undetectable error is for x to equal
65535.
A burst shorter than 16 can't do it.

For Adler, corrupting two consecutive bytes can't produce an undetectable
error because that would be the case above where k equals 1. There is no
way
for a burst across two consecutive values to be undetectable in Adler
since
x is less than the modulus.

For a burst across three values:

let x equal the error in the first value
    y equal the error in the second value
    z equal the error in the third value.

For the burst to be undetectable

 Delta S1 = (x + y + z) mod m = 0
 Delta S2 = (3x + 2y + z) mod m = 0

Since the maximum values of x, y, and z are 255 and m is more than 6 times
that, the sums above will always be less than m and we can drop the mod m.

 Delta S2 = (3x + 2y + z) = 2x + y + (x + y + z) = 0
          = 2x + y = 0                    because x + y + z = 0

        y = - 2x

 Delta S1 = x + y + z = 0
          = x - 2x + z = 0
          = -x + z
        z = x

So an undetectable error is created when in three consecutive values the
errors are
    x
  -2x
    x

This could for instance be errors of 1, -2, and 1. Since the error to the
first and third values are the same, the error must span at least 2 * the
length of the value + 1. So for Adler, it must be a 17 bit burst at least.

Also, note that this can be created by a 3 bit error and is equally
applicable to Adler and Fletcher.

Therefore, for messages shorter than the modulus + 1, the Hamming distance
of Adler32 and Fletcher 32 is 3 and, for messages longer than that, the
Hamming distance is 2.

Regards,
Pat Thaler

---------- Undetectable 3 bit errors in non-consecutive values
---------------

For undetectable errors in 3 values spaced with k1 from the first error to
second error and k2 values from the second error to the third:
 Delta S1 = (x + y + z) mod m = 0
 Delta S2 = ((k1 + k2 + 1)x + (k2 + 1)y + z) mod m = 0
          = ((k1 + k2)x + (k2)y +(x + y + z)) mod m = 0
          = ((k1 + k2)x + (k2)y) mod m = 0         because (x + y + z) mod
m
= 0

  y = - x(k1 + k2)/k2

  z = -x - y = - x + x(k1 + k2)/k2
    = x (-k2 + k1 + k2)/k2 = x(k2/k1)

For k1 = k2, the result is the same as for 3 consecutive values. That is:
  y = -2x
  z = x

Therefore, if x is 1, 2, ... 64 (for Adler32) or 1, 2, ... 16384 (for
Fletcher32),
then x, y, and z will be single bit errors.