Erlang Central

IP Checksum

Revision as of 19:42, 17 February 2009 by TribbleFaith467 (Talk | contribs)


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).