Re: Re: [Zcip] embeddable zeroconf/ip code

--nextPart2589894.98j4XQUuHt
Content-Type: multipart/mixed;
  boundary="Boundary-01=_oU2dBEKWwuls58L"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

--Boundary-01=_oU2dBEKWwuls58L
Content-Type: text/plain;
  charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

On Tue, 19 Oct 2004 06:21 am, H. Peter Anvin wrote:
> > Or am I missing something? =A0The only real issue I can see here
> > with PRNG is ensuring the sequences repeat no sooner than every
> > 2^16 - 512 samples.
>
> Again, it's a quality of implementation issue.
I don't think that matters much (if you get much beyond 10 you're dead anyw=
ay,=20
because of the exponential backoff requirement), just that there is a=20
reasonable spread.

I do have a unit test for the PRNG spread from zcip though - see attached. =
It=20
relies on a framework called check, but the changes shouldn't be too bad to=
=20
delete that dependency if you cared.

Brad




--Boundary-01=_oU2dBEKWwuls58L
Content-Type: text/x-csrc;
  charset="iso-8859-1";
  name="check_random.c"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: attachment;
	filename="check_random.c"

#include <check.h>

#include <stdlib.h>
#include <stdio.h>

#include "zcip.h"

int in_range(struct in_addr *addr_to_test)
{
    return ( (((unsigned long int)(169<<24)+(254<<16)+(1<<8)+0) <=3D ntohl(=
addr_to_test->s_addr)) &&
	     (((unsigned long int)(169<<24)+(254<<16)+(254<<8)+255) >=3D ntohl(add=
r_to_test->s_addr)));
}

START_TEST(test_uniform_distribution)=20
{
    struct ether_addr hw_addr1;
    struct in_addr ip_addr1;
    int i, failed;
    int bins[65204];

    failed =3D 0;

    hw_addr1.ether_addr_octet[0] =3D 0x00;
    hw_addr1.ether_addr_octet[1] =3D 0x40;
    hw_addr1.ether_addr_octet[2] =3D 0x05;
    hw_addr1.ether_addr_octet[3] =3D 0xDE;
    hw_addr1.ether_addr_octet[4] =3D 0x83;
    hw_addr1.ether_addr_octet[5] =3D 0x36;

    seed_rng(&(hw_addr1));

    for (i =3D 0; i<65024; i++)=20
	    bins[i] =3D 0;
    for (i =3D 0; i< 100000000; i++)
	{
	    pick_random_address(&(ip_addr1));
	    if (!(in_range(&(ip_addr1))))=20
		failed++;
	    else
		bins[(ntohl(ip_addr1.s_addr)-((169<<24)+(254<<16)+(1<<8)+0))]++;
	}
    fail_unless(0 =3D=3D failed, "IPs out of range");
  =20
    failed =3D 0;
    for (i=3D0; i< 65024; i++)=20
	{=20
	    if (0 =3D=3D bins[i])=20
		    failed++;
	}
    fail_unless(0 =3D=3D failed, "some bins empty");

    failed =3D 0;
    /* central limit theorem says normal distribution should hold */
    /* so mean is 1537.9, standard deviation is 39 */
    /* 95% of bins (=3D=3D 1300) should be within about 2 standard deviatio=
ns */
    /* we actually test for 99% (=3D=3D 650) within 3 standard deviations */
    for (i=3D0; i< 65024; i++)=20
	{=20
	    if ( ((1538-(3*39)) > bins[i]) || ((1538+(3*39)) < bins[i]))
		failed++;
	}
    fail_unless(650 >  failed, "Too many bins outside 3sd");
}
END_TEST


START_TEST(test_deterministic_seed)=20
{
    struct ether_addr hw_addr1;
    struct in_addr ip_addr1, ip_addr2;

    hw_addr1.ether_addr_octet[0] =3D 0x00;
    hw_addr1.ether_addr_octet[1] =3D 0x40;
    hw_addr1.ether_addr_octet[2] =3D 0x05;
    hw_addr1.ether_addr_octet[3] =3D 0xDE;
    hw_addr1.ether_addr_octet[4] =3D 0x83;
    hw_addr1.ether_addr_octet[5] =3D 0x36;

    seed_rng(&(hw_addr1));
    pick_random_address(&(ip_addr1));
    fail_unless(in_range(&(ip_addr1)), "address out of range");

    seed_rng(&(hw_addr1));
    pick_random_address(&(ip_addr2));
    fail_unless(in_range(&(ip_addr2)), "address out of range");

    fail_unless((ip_addr1.s_addr =3D=3D ip_addr2.s_addr),
		"Using same seed produces different IPs");
}
END_TEST

START_TEST(test_variant_seed)=20
{
    struct ether_addr hw_addr1, hw_addr2;
    struct in_addr ip_addr1, ip_addr2;

    hw_addr1.ether_addr_octet[0] =3D 0x00;
    hw_addr1.ether_addr_octet[1] =3D 0x40;
    hw_addr1.ether_addr_octet[2] =3D 0x05;
    hw_addr1.ether_addr_octet[3] =3D 0xDE;
    hw_addr1.ether_addr_octet[4] =3D 0x83;
    hw_addr1.ether_addr_octet[5] =3D 0x36;

    seed_rng(&(hw_addr1));
    pick_random_address(&(ip_addr1));
    fail_unless(in_range(&(ip_addr1)), "address out of range");

    hw_addr2.ether_addr_octet[0] =3D 0x00;
    hw_addr2.ether_addr_octet[1] =3D 0x20;
    hw_addr2.ether_addr_octet[2] =3D 0x18;
    hw_addr2.ether_addr_octet[3] =3D 0xA1;
    hw_addr2.ether_addr_octet[4] =3D 0x28;
    hw_addr2.ether_addr_octet[5] =3D 0x8F;

    seed_rng(&(hw_addr2));
    pick_random_address(&(ip_addr2));
    fail_unless(in_range(&(ip_addr2)), "address out of range");

    fail_unless((ip_addr1.s_addr !=3D ip_addr2.s_addr),
		"Using different seed produces same IP");
}
END_TEST

Suite *random_suite (void)=20
{=20
  Suite *s =3D suite_create ("Random");=20
  TCase *tc_core =3D tcase_create ("Core");
=20
  suite_add_tcase (s, tc_core);
=20
  tcase_add_test (tc_core, test_deterministic_seed);=20
  tcase_add_test (tc_core, test_variant_seed);=20
  tcase_add_test (tc_core, test_uniform_distribution);=20
  return s;=20
}
=20
int main (void)=20
{=20
  int nf;=20
  Suite *s =3D random_suite ();=20
  SRunner *sr =3D srunner_create (s);
  srunner_set_log (sr, "check_random.log");=20
  srunner_run_all (sr, CK_NORMAL);=20
  nf =3D srunner_ntests_failed (sr);=20
  srunner_free (sr);=20
  suite_free (s);=20
  return (nf =3D=3D 0) ? EXIT_SUCCESS : EXIT_FAILURE;=20
}

--Boundary-01=_oU2dBEKWwuls58L--

--nextPart2589894.98j4XQUuHt
Content-Type: application/pgp-signature

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQBBd2UrGwwszQ/PZzgRArRkAKCPtr4KXMbsx1SHHuGWgtjzpuRbKQCghxnP
oHrjxY2omblN1vvFNTVSKws=
=OvCB
-----END PGP SIGNATURE-----

--nextPart2589894.98j4XQUuHt--


-------------------------------------------------------
This SF.net email is sponsored by: IT Product Guide on ITManagersJournal
Use IT products in your business? Tell us what you think of them. Give us
Your Opinions, Get Free ThinkGeek Gift Certificates! Click to find out more
http://productguide.itmanagersjournal.com/guidepromo.tmpl