Erlang Central

IP Checksum

Revision as of 19:29, 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 hours 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