Erlang Central

Difference between revisions of "IP Checksum"

From ErlangCentral Wiki

(One intermediate revision by one user not shown)
Line 69:Line 69:
 
    prop_ones_complement(Base)).
 
    prop_ones_complement(Base)).
  
%% If you implemented for base 16 only, use this property with Base==16
+
%% If you implemented for base 16 only, use this property with Base == 16.
 
prop_ones_complement(Base) ->
 
prop_ones_complement(Base) ->
 
     ?FORALL(I,choose(0,(1 bsl Base)-1),
 
     ?FORALL(I,choose(0,(1 bsl Base)-1),
Line 109:Line 109:
 
    <<0:Zeros>> == Padded
 
    <<0:Zeros>> == Padded
 
    end).
 
    end).
 +
</code>
 +
 +
=== Ones complement sum ===
 +
 +
The ones complement sum is computed by adding a number of words in ones complement. We assume this function to be implemented as '''ip_checksum:ones_sum/2''' which takes a bit string as first argument and a base as second argument. We assume that padding is done outside the ones_sum function and only test that the function works for bit strings of which the length is divisible by the given base.
 +
 +
Because of our test driven development method, we have already tested the ones_complement function and therefore trust this function in our property.
 +
We do not assume that the '''ones_sum/2''' function returns the ones complement of the sum, it just returns the sum.
 +
We can compute the sum, add its ones complement to the exiting list and expect to get zero (or actually -0) out of the result.
 +
 +
Again the property below needs Erlang release 12B or newer, but can easily be adapted to work for binaries instead of arbitrary bit strings.
 +
 +
<code>
 +
prop_ones_sum() ->
 +
    prop_ones_sum(16).
 +
 +
prop_ones_sum(Base) ->
 +
    ?FORALL(I,choose(0,1024),
 +
    ?FORALL(Bin,bitstring(I*Base),
 +
    begin
 +
Sum = ip_checksum:sum(Bin,Base),
 +
CSum = ip_checksum:ones_complement(Sum),
 +
sum(<<CSum/bits, Bin/bits>>,Base) ==
 +
    <<((1 bsl Base)-1):Base>>
 +
    end)).
 +
</code>
 +
 +
=== Checksum ===
 +
 +
After computing ones complement sum, one has to take the ones complement of the result to compute the checksum. Of course, we have all ingredients in house to do so, but in case you implement both functions as one you would like to test the final result
 +
'''ip_checksum:checksum/2''' with a bit string and base as arguments. We assume here that the '''checksum''' function also takes care of padding, but if you assume a padded binary as input, you know how to specify that.
 +
 +
<code>
 +
prop_checksum() ->
 +
    prop_checksum(16).
 +
 +
prop_checksum(Base) ->
 +
    ?FORALL(Bin,bitstring(),
 +
    begin
 +
      Sum = ip_checksum:checksum(Bin,Base),
 +
              sum(<<Sum/bits, Bin/bits>>,Base) ==
 +
                <<((1 bsl Base)-1):Base>>
 +
    end).
 +
</code>

Revision as of 20:44, 17 February 2009


Contents

Authors

Thomas Arts

http://www.quviq.com/

Testing IP checksum implementations

In RFC 1071 efficient algorithms are discussed for computing the internet checksum, also known as IP checksum. Whenever you implement efficient algorithms, an error may sneak through.

This article is meant to be used as test driven development specification for anyone that wants to implement one of the algorithms of RFC 1071 or even a new one to compute the IP checksum. The article can also be read as an example of specifying something without revealing its implementation details; a good example of using QuickCheck specifications.

Whether you write your code in Erlang, C or Java, we assume that you can build an interface to a module called ip_checksum.erl in which Erlang functions either are the functions under test or call the functions under test. You need access to QuickCheck, download a trial version from Quviq if you do not have a valid licence.

IP Checksum

The IP checksum is the 16 bit one's complement of the one's complement sum of all 16 bit words in the header.

Ones complement is a way of representing negative numbers (see WikiPedia for more details).

The IP checksum uses base 16, that is 1 word or 2 bytes. In 16 bits you can represent the numbers 0 to 65535. The idea with ones complement is to use half the numbers in this interval for representing negative numbers. Thus, 0 up to 32767 are the positive numbers and 65535 is -0, or an alternative representation of zero. The number 65534 is -1 etc. Until 32768 which is -32767. Hence the interval -32767 up to 32767 can be represented.

In the remainder of this article we will present properties for functions that you probably would like to test. The properties are always parametrized by the base and have a special version for base 16. One could implement the functions for other bases as well.

Generators

Depending on the version of QuickCheck you run with, you might need to add the following generators for binaries and bit strings that are used in the properties.

A generator for binaries of arbitrary and fixed length. Note that these binaries have a shrinking behaviour that shrinks a number of individual bytes to zero.

binary() ->
    ?SIZED(Size,
      	   ?LET(NrBytes,choose(0,Size),binary(NrBytes))).


binary(NrBytes) ->
    ?LET(Bytes, 
	 vector(NrBytes,choose(0,255)),
	 list_to_binary(Bytes)).

Similarly, we define a generator for bit strings, since we like to take the ones complement in base 19, don't we :0). Note that you need Erlang release 12B or newer to be able to use these generators.

bitstring() ->
    ?SIZED(Size,
	   ?LET(NrBits,choose(0,Size*5),bitstring(NrBits))).

bitstring(NrBits) ->
    case {NrBits div 8,NrBits rem 8} of
	{Bytes,0} -> 
	    binary(Bytes);
	{Bytes,Bits} ->
	    ?LET({Bin1,Byte},{binary(Bytes),
			     choose(0,(1 bsl Bits)-1)},
		 <<Bin1/binary,(Byte bsl 8-Bits):Bits>>)
    end.

Ones complement

The first function you might want to check is the ones complement of a word. We assume you have a function ip_checksum:ones_complement/1 implemented that takes a binary with one 16 bit word as input.

We do not want to compare your ones complement implementation with ours by telling you how we implemented it and writing == in between. Instead we go by the definition and say that a number and its ones complement sum to -0.

prop_ones_complement() ->
    ?FORALL(Base,choose(1,64),
	    prop_ones_complement(Base)).

%% If you implemented for base 16 only, use this property with Base == 16.
prop_ones_complement(Base) ->
    ?FORALL(I,choose(0,(1 bsl Base)-1),
	    begin
		<<CI:Base>> = ip_checksum:ones_complement(<<I:Base>>),
		(1 bsl Base)-1 == I+CI
	    end).

Padding

It is not clear from the specification presented above, but if you need to compute the checksum of a list of bytes in base 16, then there should be an even number of bytes. Likewise, if we would like to do ones complement in 32 bits base, we would need to extend a sequence of bytes such that it is divisible by 4.

Extending a bit string such that it is divisible by the base is called padding. We assume that you implemented a padding function that added the necessary bits, given either a binary of a bit string. We assume this function to be implemented as ip_checksum:padd/1 taking a bit string as argument and returning a new bit string which is an extended version with as many zero bits as needed.

Note that the properties below can only be used with Erlang R12B or newer, because of the use of bit strings. It's left as an exercise to make it work for binaries only.

prop_padding_binary() ->
    ?FORALL(Bytes,choose(1,10),
	    prop_padding(binary(),Bytes*8)).

prop_padding_bitstring() ->
    ?FORALL(Base,choose(1,64),
	    prop_padding(bitstring(),Base)).

%% if you implemented padding for binaries with size 16 bits, use this one
prop_padding_words() ->
    prop_padding(binary(),16).

prop_padding(G,PadSize) ->
    ?FORALL(BitString,G,
	    begin
		Bits = bit_size(BitString),
		<<B:Bits/bits, Padded/bits>> = 
		    ip_checksum:padd(BitString,PadSize),
                Zeros = bit_size(Padded),
		((Bits+Zeros) rem PadSize) == 0 andalso
	            B == BitString andalso
		    <<0:Zeros>> == Padded
	    end).

Ones complement sum

The ones complement sum is computed by adding a number of words in ones complement. We assume this function to be implemented as ip_checksum:ones_sum/2 which takes a bit string as first argument and a base as second argument. We assume that padding is done outside the ones_sum function and only test that the function works for bit strings of which the length is divisible by the given base.

Because of our test driven development method, we have already tested the ones_complement function and therefore trust this function in our property. We do not assume that the ones_sum/2 function returns the ones complement of the sum, it just returns the sum. We can compute the sum, add its ones complement to the exiting list and expect to get zero (or actually -0) out of the result.

Again the property below needs Erlang release 12B or newer, but can easily be adapted to work for binaries instead of arbitrary bit strings.

prop_ones_sum() ->
    prop_ones_sum(16).

prop_ones_sum(Base) ->
    ?FORALL(I,choose(0,1024),
	    ?FORALL(Bin,bitstring(I*Base),
		    begin
			Sum = ip_checksum:sum(Bin,Base),
			CSum = ip_checksum:ones_complement(Sum),
			sum(<<CSum/bits, Bin/bits>>,Base) ==
			    <<((1 bsl Base)-1):Base>>
		    end)).

Checksum

After computing ones complement sum, one has to take the ones complement of the result to compute the checksum. Of course, we have all ingredients in house to do so, but in case you implement both functions as one you would like to test the final result ip_checksum:checksum/2 with a bit string and base as arguments. We assume here that the checksum function also takes care of padding, but if you assume a padded binary as input, you know how to specify that.

prop_checksum() ->
    prop_checksum(16).

prop_checksum(Base) ->
    ?FORALL(Bin,bitstring(),
	    begin
	      Sum = ip_checksum:checksum(Bin,Base),
              sum(<<Sum/bits, Bin/bits>>,Base) ==
                <<((1 bsl Base)-1):Base>>
	    end).