Strengthening Verification

A problem with verifying int_stack is that there is not enough state to check whether it really has not been modified. For instance, a buggy pointer could cause any of the values that had been pushed onto the stack to be changed, and the verify_int_stack() routine would not catch it.

Occasionally, we need more integrity checking. This usually arises when:

• The data structure is a shared global data structure that is being accessed and updated from multiple places, and it has a high potential for corruption.
• Some instance of the data structure is being corrupted in some large, long-running program, and we need to quickly isolate the source of the corruption.

One approach to ensuring complete integrity checking is to compute some kind of checksum or signature. A checksum is a small value, usually 8 to 32 bit, that is added to the ADT, and is computed using the contents of the rest of the data structure. Another way of looking at the checksum is that it is a hash of the data structure.

The checksum usually has two requirements:

• It must be relatively cheap to compute and update
• It must be difficult to change a field, or a few elements, of the data structure and still obtain the same checksum.

For the int_stack ADT, a decent checksum is to xor (^) all the elements of the data structure. This will result in the following header:

	struct int_stack {
	  /* other stuff ... */
	  unsigned	is_chksum;
	};
	/* other accessor macros ... */
	#define x_chksum_int_stack(_s)	(deref_int_stack(_s)->is_chksum)

Verification involves recomputing the checksum and ensuring that it matches.

	void
	verify_int_stack(
		FILE *		file,
		int		line,
		const int_stack	stack
		)
	{
	  unsigned	chksum;
	  int		i;

	  /* other verifys ...*/
	  chksum = (unsigned)len_int_stack(stack);
	  chksum ^= (unsigned)max_int_stack(stack);
	  chksum ^= (unsigned)vals_int_stack(stack);
	  for( i = 0; i < len_int_stack(stack); i++ ) {
	    chksum ^= (unsigned)vals_int_stack(stack)[i];
	  }
	  verify(file, line, chksum == x_chksum_int_stack(stack));
	}

We will also have to modify the various functions to setup the checksum appropriately. Here, we show the ones most affected.

	int_stack
	make_int_stack(void)
	{
	  int_stack	stack = xalloc(struct int_stack);
	  unsigned	chksum;

	  x_max_int_stack(stack) = 16;
	  x_len_int_stack(stack) = 0;
	  x_vals_int_stack(stack) = xnalloc(int, 16);

	  chksum = (unsigned)len_int_stack(stack);
	  chksum ^= (unsigned)max_int_stack(stack);
	  chksum ^= (unsigned)vals_int_stack(stack);
	  x_chksum_int_stack(stack) = chksum;

	  VERIFY_INT_STACK(stack);
	  return stack;
	}

	void
	push_int_stack(
		int_stack	stack,
		int		val
		)
	{
	  int	len = len_int_stack(stack);
	  int	max = max_int_stack(stack);
	  int	nmax;
	  int *	vals;
	  int *	nvals;
	  int	i;

	  VERIFY_INT_STACK(stack);

	  if( len == max ) {
	    nmax = max + 16;
	    nvals = xnalloc(int, nmax);
	    vals = vals_int_stack(stack);
	    for( i = 0; i < len; i++ ) {
	      nvals[i] = vals[i];
	    }
	    x_max_int_stack(stack) = nmax;
	    x_vals_int_stack(stack) = nvals;
	    xnfree(int, max, vals);

	    /* undo the old values */
	    x_chksum_int_stack(stack) ^= (unsigned)vals;
	    x_chksum_int_stack(stack) ^= (unsigned)max;

	    /* update the new values */
	    x_chksum_int_stack(stack) ^= (unsigned)nvals;
	    x_chksum_int_stack(stack) ^= (unsigned)nmax;
	  }

	  vals_int_stack(stack)[len] = val;
	  x_len_int_stack(stack) = len+1;

	  /* undo the old values */
	  x_chksum_int_stack(stack) ^= (unsigned)len;

	  /* update the new values */
	  x_chksum_int_stack(stack) ^= (unsigned)(len+1);
	  x_chksum_int_stack(stack) ^= val;

	  VERIFY_INT_STACK(stack);
	}

	void
	pop_int_stack(
		int_stack	stack
		)
	{
	  int	len = len_int_stack(stack);
	  VERIFY_INT_STACK(stack);

	  x_len_int_stack(stack)--;

	  /* undo the old values in the checksum */
	  x_chksum_int_stack(stack) ^= (unsigned) len;
	  x_chksum_int_stack(stack) ^= (unsigned) vals_int_stack(len)[len-1];
	  /* update the checksum with new value */
	  x_chksum_int_stack(stack) ^= (unsigned) (len-1);

	  VERIFY_INT_STACK(stack);
	}

Note that a fair bit of code has been added to the routines for checksum computation. This is because of run-time efficiency. Alternatively, we could define a function that recomputed the checksum, and call that prior to exiting the functions that modify the data structure.

	static void
	update_checksum_int_stack(
		int_stack	stack
		)
	{
	  unsigned	chksum;
	  int		i;

	  chksum = (unsigned)len_int_stack(stack);
	  chksum ^= (unsigned)max_int_stack(stack);
	  chksum ^= (unsigned)vals_int_stack(stack);
	  for( i = 0; i < len_int_stack(stack); i++ ) {
	    chksum ^= (unsigned)vals_int_stack(stack)[i];
	  }
	  x_chksum_int_stack(stack) = chksum;
	}

	void
	pop_int_stack(
		int_stack	stack
		)
	{
	  VERIFY_INT_STACK(stack);

	  x_len_int_stack(stack)--;

	  update_checksum_int_stack(stack);
	  VERIFY_INT_STACK(stack);
	}