#include "osscan.h"

extern struct ops o;

FingerPrint *get_fingerprint(struct hoststruct *target, struct seq_info *si, 
			     unsigned short *portarray) {
	FingerPrint *FP = NULL, *FPtmp = NULL;
	FingerPrint *FPtests[9];
	struct AVal *seq_AVs;
	int last;
	struct ip *ip;
	struct tcphdr *tcp;
	struct icmp *icmp;
	struct timeval t1,t2;
	int i;
	struct hostent *myhostent = NULL;
	unsigned int localnet, netmask;
	pcap_t *pd;
	char myname[513];
	double temp1=0;
	int rawsd;
	int tries = 0;
	int newcatches;
	int current_port = 0;
	int testsleft;
	int testno;
	int  timeout;
	unsigned int sequence_base;
	unsigned int openport;
	int bytes;
	unsigned int closedport = 31337;
	struct port *tport = NULL;
	char *p;
	int decoy;
	struct bpf_program fcode;
	char err0r[PCAP_ERRBUF_SIZE];
	char filter[512];
	double seq_inc_sum = 0;
	unsigned int  seq_avg_inc = 0;
	struct udpprobeinfo *upi = NULL;
	unsigned int seq_gcd = 1;
//#ifdef WIN32
//	unsigned int seq_diffs[NUM_SEQ_SAMPLES-1];
//#else
		unsigned int seq_diffs[NUM_SEQ_SAMPLES];
//#endif

	int ossofttimeout, oshardtimeout;

	if (target->timedout) return NULL;

	/* Init our fingerprint tests to each be NULL */
	bzero(FPtests, sizeof(FPtests)); 
	get_random_bytes(&sequence_base, sizeof(unsigned int));
	/* Init our raw socket */
#ifdef WIN32
	rawsd=500;
#else
	if ((rawsd = socket(AF_INET, SOCK_RAW, IPPROTO_RAW)) < 0 ) pfatal("socket trobles in get_fingerprint");
	unblock_socket(rawsd);
	broadcast_socket(rawsd);
#endif
 /* Do we have a correct source address? */
	if (!target->source_ip.s_addr) 
	{
		if (gethostname(myname, MAXHOSTNAMELEN) != 0 && !((myhostent = gethostbyname(myname)))) fatal("Cannot get hostname!  Try using -S <my_IP_address> or -e <interface to scan through>\n");
		memcpy(&target->source_ip, myhostent->h_addr_list[0], sizeof(struct in_addr));
		if (o.debugging || o.verbose) log_write(LOG_STDOUT, "We skillfully deduced that your address is %s\n", inet_ntoa(target->source_ip));
	}
	/* Now for the pcap opening nonsense ... */
	/* Note that the snaplen is 152 = 64 byte max IPhdr + 24 byte max link_layer
	* header + 64 byte max TCP header.  Had to up it for UDP test
	*/

	ossofttimeout = MAX(200000, target->to.timeout);
	oshardtimeout = MAX(500000, 5 * target->to.timeout);

	pd = my_pcap_open_live(target->device.name, 650,  (o.spoofsource)? 1 : 0, (ossofttimeout + 500)/ 1000);

	if (o.debugging) log_write(LOG_STDOUT, "Wait time is %d\n", (ossofttimeout +500)/1000);

	if (pcap_lookupnet(target->device.name, &localnet, &netmask, err0r) < 0) fatal("Failed to lookup device subnet/netmask: %s", err0r);
	p = strdup(inet_ntoa(target->host));

	snprintf(filter, sizeof(filter), "(icmp and dst host %s) or (tcp and src host %s and dst host %s)", inet_ntoa(target->source_ip), p, inet_ntoa(target->source_ip));
	free(p);
 /* Due to apparent bug in libpcap */
	if (islocalhost(&(target->host))) filter[0] = '\0';
	if (o.debugging) log_write(LOG_STDOUT, "Packet capture filter: %s\n", filter);
	if (pcap_compile(pd, &fcode, filter, 0, netmask) < 0) fatal("Error compiling our pcap filter: %s\n", pcap_geterr(pd));
	if (pcap_setfilter(pd, &fcode) < 0 ) fatal("Failed to set the pcap filter: %s\n", pcap_geterr(pd));
	/* Lets find an open port to used */
	openport = -1;
	tport = NULL;
	if (target->ports.state_counts_tcp[PORT_OPEN] > 0) 
	{ 
		tport = nextport(&target->ports, NULL, IPPROTO_TCP, PORT_OPEN);
		assert(tport);
		openport = tport->portno;
	}
 
	/* Now we should find a closed port */
	if (target->ports.state_counts_tcp[PORT_CLOSED] > 0) 
	{
		tport = nextport(&target->ports, NULL, IPPROTO_TCP, PORT_CLOSED);
		assert(tport);
		closedport = tport->portno;
	} 
	else if (target->ports.state_counts_tcp[PORT_UNFIREWALLED] > 0) 
	{
		/* Well, we will settle for unfiltered */
		tport = nextport(&target->ports, NULL, IPPROTO_TCP, PORT_UNFIREWALLED);
		assert(tport);
		closedport = tport->portno;
	} 
	else 
	{
		closedport = (get_random_uint() % 14781) + 30000;
	}

	if (o.verbose && openport != -1) log_write(LOG_STDOUT, "For OSScan assuming that port %d is open and port %d is closed and neither are firewalled\n", openport, closedport);

	current_port = o.magic_port + NUM_SEQ_SAMPLES +1;
 
	/* Now lets do the NULL packet technique */
	testsleft = (openport == -1)? 4 : 7;
	FPtmp = NULL;
	/* bzero(FPtests, sizeof(FPtests));*/
	tries = 0;
	do 
	{ 
		newcatches = 0;
		if (openport != -1) 
		{
			/* Test 1 */
			if (!FPtests[1]) 
			{
				if (o.scan_delay) enforce_scan_delay(NULL);
				send_tcp_raw_decoys(rawsd, &target->host, current_port, openport, sequence_base, 0,TH_BOGUS|TH_SYN, 0,"\003\003\012\001\002\004\001\011\010\012\077\077\077\077\000\000\000\000\000\000" , 20, NULL, 0, &target->device);
			}
     
			/* Test 2 */
			if (!FPtests[2]) 
			{
				if (o.scan_delay) enforce_scan_delay(NULL);
				send_tcp_raw_decoys(rawsd, &target->host, current_port +1, openport, sequence_base, 0,0, 0,"\003\003\012\001\002\004\001\011\010\012\077\077\077\077\000\000\000\000\000\000" , 20, NULL, 0, &target->device);
			}
			/* Test 3 */
			if (!FPtests[3]) 
			{     
				if (o.scan_delay) enforce_scan_delay(NULL);
				send_tcp_raw_decoys(rawsd, &target->host, current_port +2, openport, sequence_base, 0,TH_SYN|TH_FIN|TH_URG|TH_PUSH, 0,"\003\003\012\001\002\004\001\011\010\012\077\077\077\077\000\000\000\000\000\000" , 20, NULL, 0, &target->device);
			}

			/* Test 4 */
			if (!FPtests[4]) 
			{     
				if (o.scan_delay) enforce_scan_delay(NULL);
				send_tcp_raw_decoys(rawsd, &target->host, current_port +3, openport, sequence_base, 0,TH_ACK, 0,"\003\003\012\001\002\004\001\011\010\012\077\077\077\077\000\000\000\000\000\000" , 20, NULL, 0, &target->device);
			}
		}
   
		/* Test 5 */
		if (!FPtests[5]) 
		{   
			if (o.scan_delay) enforce_scan_delay(NULL);
			send_tcp_raw_decoys(rawsd, &target->host, current_port +4, closedport, sequence_base, 0,TH_SYN, 0,"\003\003\012\001\002\004\001\011\010\012\077\077\077\077\000\000\000\000\000\000" , 20, NULL, 0, &target->device);
		}
		/* Test 6 */
		if (!FPtests[6]) 
		{   
			if (o.scan_delay) enforce_scan_delay(NULL);
			send_tcp_raw_decoys(rawsd, &target->host, current_port +5, closedport, sequence_base, 0,TH_ACK, 0,"\003\003\012\001\002\004\001\011\010\012\077\077\077\077\000\000\000\000\000\000" , 20, NULL, 0, &target->device);
		}
		/* Test 7 */
		if (!FPtests[7]) 
		{
			if (o.scan_delay) enforce_scan_delay(NULL);   
			send_tcp_raw_decoys(rawsd, &target->host, current_port +6, closedport, sequence_base, 0,TH_FIN|TH_PUSH|TH_URG, 0,"\003\003\012\001\002\004\001\011\010\012\077\077\077\077\000\000\000\000\000\000" , 20, NULL, 0, &target->device);
		}

		if (!FPtests[8]) 
		{
			if (o.scan_delay) enforce_scan_delay(NULL);
			upi = send_closedudp_probe(rawsd, &target->host, o.magic_port, closedport,&target->device);
		}
		gettimeofday(&t1, NULL);
		timeout = 0;
		/* Insure we haven't overrun our allotted time ... */
		if (o.host_timeout && (TIMEVAL_MSEC_SUBTRACT(t1, target->host_timeout) >= 0))
		{
			target->timedout = 1;
			goto osscan_timedout;
		}
		while(( ip = (struct ip*) readip_pcap(pd, &bytes, oshardtimeout)) && !timeout) 
		{
//		printf("INPACKET\n");
//		hdump(ip, bytes);

			gettimeofday(&t2, NULL);
			if (TIMEVAL_SUBTRACT(t2,t1) > oshardtimeout) 
			{
				timeout = 1;
			}
			if (o.host_timeout && (TIMEVAL_MSEC_SUBTRACT(t2, target->host_timeout) >= 0))
			{
				target->timedout = 1;
				goto osscan_timedout;
			}
			if (bytes < (4 * ip->ip_hl) + 4) continue;
			if (ip->ip_p == IPPROTO_TCP) 
			{
				tcp = ((struct tcphdr *) (((char *) ip) + 4 * ip->ip_hl));
				testno = ntohs(tcp->th_dport) - current_port + 1;
				if (testno <= 0 || testno > 7) continue;
				if (o.debugging > 1) log_write(LOG_STDOUT, "Got packet for test number %d\n", testno);
				if (FPtests[testno]) continue;
				testsleft--;
				newcatches++;
				FPtests[testno] = safe_malloc(sizeof(FingerPrint));
				bzero(FPtests[testno], sizeof(FingerPrint));
				FPtests[testno]->results = fingerprint_iptcppacket(ip, 265, sequence_base);
				FPtests[testno]->name = (testno == 1)? "T1" : (testno == 2)? "T2" : (testno == 3)? "T3" : (testno == 4)? "T4" : (testno == 5)? "T5" : (testno == 6)? "T6" : (testno == 7)? "T7" : "PU";
			} 
			else if (ip->ip_p == IPPROTO_ICMP) 
			{
				icmp = ((struct icmp *)  (((char *) ip) + 4 * ip->ip_hl));
				/* It must be a destination port unreachable */
				if (icmp->icmp_type != 3 || icmp->icmp_code != 3) 
				{
					/* This ain't no stinking port unreachable! */
					continue;
				}
				if (bytes < ntohs(ip->ip_len)) 
				{
					error("We only got %d bytes out of %d on our ICMP port unreachable packet, skipping", bytes, ntohs(ip->ip_len));
					continue;
				}
				if (FPtests[8]) continue;
				FPtests[8] = safe_malloc(sizeof(FingerPrint));
				bzero(FPtests[8], sizeof(FingerPrint));
				FPtests[8]->results = fingerprint_portunreach(ip, upi);
				if (FPtests[8]->results) 
				{       
					FPtests[8]->name = "PU";
					testsleft--;
					newcatches++;
				} 
				else 
				{
					free(FPtests[8]);
					FPtests[8] = NULL;
				}
			}
			if (testsleft == 0)break;
		}     
	} while ( testsleft > 0 && (tries++ < 5 && (newcatches || tries == 1)));

 

 /* First we send our initial NUM_SEQ_SAMPLES SYN packets  */
	if (openport != -1) 
	{
		for(i=1; i <= NUM_SEQ_SAMPLES; i++) 
		{
			if (o.scan_delay) enforce_scan_delay(NULL);
			for(decoy=0; decoy < o.numdecoys; decoy++) 
			{
				send_tcp_raw_decoys(rawsd, &target->host, o.magic_port+i, openport, sequence_base + i, 0, TH_SYN, 0 , NULL, 0, NULL, 0, &target->device);
				if (!o.scan_delay) usleep( 5000 + target->to.srtt);
			}
          usleep(10000);
		}
   /* Now we collect  the replies */
		si->responses = 0;
		timeout = 0; 
		gettimeofday(&t1,NULL);
		while(si->responses < NUM_SEQ_SAMPLES && !timeout) 
		{ 
			ip = (struct ip*) readip_pcap(pd, &bytes, oshardtimeout);
			gettimeofday(&t2, NULL);
			/* Insure we haven't overrun our allotted time ... */
			if (o.host_timeout && (TIMEVAL_MSEC_SUBTRACT(t2, target->host_timeout) >= 0))
			{
				target->timedout = 1;
				goto osscan_timedout;
			}
			if (!ip) 
			{ 
				if (TIMEVAL_SUBTRACT(t2,t1) > ossofttimeout) timeout = 1;
				continue; 
			} 
			else if (TIMEVAL_SUBTRACT(t2,t1) > oshardtimeout) 
			{
//				timeout = 1;
			}		  
			if (bytes < (4 * ip->ip_hl) + 4) continue;
			if (ip->ip_p == IPPROTO_TCP) 
			{
				tcp = ((struct tcphdr *) (((char *) ip) + 4 * ip->ip_hl));
				if (ntohs(tcp->th_dport) < o.magic_port || ntohs(tcp->th_dport) - o.magic_port > NUM_SEQ_SAMPLES || ntohs(tcp->th_sport) != openport) 
				{
					continue;
				}
				if ((tcp->th_flags & TH_RST)) 
				{
					/*readtcppacket((char *) ip, ntohs(ip->ip_len));*/	 
					if (si->responses == 0) 
					{	 
						fprintf(stderr, "WARNING:  RST from port %d -- is this port really open?\n", openport);
						/* We used to quit in this case, but left-overs from a SYN
						scan or lame-ass TCP wrappers can cause this! */
					} 
					continue;
				} 
				else if ((tcp->th_flags & (TH_SYN|TH_ACK)) == (TH_SYN|TH_ACK)) 
				{
					/*readtcppacket((char *)ip, ntohs(ip->ip_len));*/
					si->seqs[si->responses++] = ntohl(tcp->th_seq);
					if (si->responses > 1) 
					{
						seq_diffs[si->responses-2] = MOD_DIFF(ntohl(tcp->th_seq), si->seqs[si->responses-2]);
					}      
				}
			}
		}
		if (si->responses >= 4 && o.scan_delay <= 1000) 
		{
			seq_gcd = gcd_n_uint(si->responses -1, seq_diffs);
			/*     printf("The GCD is %u\n", seq_gcd);*/
			if (seq_gcd) 
			{     
				for(i=0; i < si->responses - 1; i++) seq_diffs[i] /= seq_gcd;
				for(i=0; i < si->responses - 1; i++) 
				{     
					if (MOD_DIFF(si->seqs[i+1],si->seqs[i]) > 50000000) 
					{
						si->class = SEQ_TR;
						si->index = 9999999;
						/*	 printf("Target is a TR box\n");*/
						break;
					}	
					seq_avg_inc += seq_diffs[i];
				}
			}
			if (seq_gcd == 0) 
			{
				si->class = SEQ_CONSTANT;
				si->index = 0;
			} 
			else if (seq_gcd % 64000 == 0) 
			{
				si->class = SEQ_64K;
				/*       printf("Target is a 64K box\n");*/
				si->index = 1;
			} 
			else if (seq_gcd % 800 == 0) 
			{
				si->class = SEQ_i800;
				/*       printf("Target is a i800 box\n");*/
				si->index = 10;
			} 
			else if (si->class == SEQ_UNKNOWN) 
			{
				
				seq_avg_inc = (0.5) + seq_avg_inc / (si->responses - 1);
				/*       printf("seq_avg_inc=%u\n", seq_avg_inc);*/
				for(i=0; i < si->responses -1; i++)       
				{
					/*	 printf("The difference is %u\n", seq_diffs[i]);
					printf("Adding %u^2=%e", MOD_DIFF(seq_diffs[i], seq_avg_inc), pow(MOD_DIFF(seq_diffs[i], seq_avg_inc), 2));*/
					/* pow() seems F#@!#$!ed up on some Linux systems so I will
					not use it for now 
  					seq_inc_sum += pow(MOD_DIFF(seq_diffs[i], seq_avg_inc), 2);
					*/	 

					seq_inc_sum += ((double)(MOD_DIFF(seq_diffs[i], seq_avg_inc)) * ((double)MOD_DIFF(seq_diffs[i], seq_avg_inc)));
					/*	 seq_inc_sum += pow(MOD_DIFF(seq_diffs[i], seq_avg_inc), 2);*/
				}
				/*       printf("The sequence sum is %e\n", seq_inc_sum);*/
				seq_inc_sum /= (si->responses - 1);
				/* Some versions of Linux libc seem to have broken pow ... so we
				avoid it */


//				temp1 = (sqrt(seq_inc_sum));

				si->index = (unsigned int) (0.5 + pow(seq_inc_sum, 0.5));

				/*       printf("The sequence index is %d\n", si->index);*/
				if (si->index < 75) 
				{
					si->class = SEQ_TD;
					/*	 printf("Target is a Micro$oft style time dependant box\n");*/
				}
				else 
				{
					si->class = SEQ_RI;
					/*	 printf("Target is a random incremental box\n");*/
				}
			}
			FPtests[0] = safe_malloc(sizeof(FingerPrint));
			bzero(FPtests[0], sizeof(FingerPrint));
			FPtests[0]->name = "TSeq";
			seq_AVs = safe_malloc(sizeof(struct AVal) * 3);
			bzero(seq_AVs, sizeof(struct AVal) * 3);
			FPtests[0]->results = seq_AVs;
			seq_AVs[0].attribute = "Class";
			switch(si->class) 
			{
				case SEQ_CONSTANT:
					strcpy(seq_AVs[0].value, "C");
					seq_AVs[0].next = &seq_AVs[1];
					seq_AVs[1].attribute= "Val";     
					sprintf(seq_AVs[1].value, "%X", si->seqs[0]);
					break;
				case SEQ_64K:
					strcpy(seq_AVs[0].value, "64K");      
					break;
				case SEQ_i800:
					strcpy(seq_AVs[0].value, "i800");
					break;
				case SEQ_TD:
					strcpy(seq_AVs[0].value, "TD");
					seq_AVs[0].next = &seq_AVs[1];
					seq_AVs[1].attribute= "gcd";     
					sprintf(seq_AVs[1].value, "%X", seq_gcd);
					seq_AVs[1].next = &seq_AVs[2];
					seq_AVs[2].attribute="SI";
					sprintf(seq_AVs[2].value, "%X", si->index);
					break;
				case SEQ_RI:
					strcpy(seq_AVs[0].value, "RI");
					seq_AVs[0].next = &seq_AVs[1];
					seq_AVs[1].attribute= "gcd";     
					sprintf(seq_AVs[1].value, "%X", seq_gcd);
					seq_AVs[1].next = &seq_AVs[2];
					seq_AVs[2].attribute="SI";
					sprintf(seq_AVs[2].value, "%X", si->index);
					break;
				case SEQ_TR:
					strcpy(seq_AVs[0].value, "TR");
					break;
			}
		}
		else 
		{
			log_write(LOG_STDOUT|LOG_NORMAL|LOG_SKID,"Insufficient responses for TCP sequencing (%d), OS detection will be MUCH less reliable\n", si->responses);
		}
	} 
	else 
	{
	}
	for(i=0; i < 9; i++) 
	{
		if (i > 0 && !FPtests[i] && ((openport != -1) || i > 4)) 
		{
			/* We create a Resp (response) attribute with value of N (no) because
			it is important here to note whether responses were or were not 
			received */
			FPtests[i] = safe_malloc(sizeof(FingerPrint));
			bzero(FPtests[i], sizeof(FingerPrint));
			seq_AVs = safe_malloc(sizeof(struct AVal));
			seq_AVs->attribute = "Resp";
			strcpy(seq_AVs->value, "N");
			seq_AVs->next = NULL;
			FPtests[i]->results = seq_AVs;
			FPtests[i]->name =  (i == 1)? "T1" : (i == 2)? "T2" : (i == 3)? "T3" : (i == 4)? "T4" : (i == 5)? "T5" : (i == 6)? "T6" : (i == 7)? "T7" : "PU";
		}
	}
	last = -1;
	FP = NULL;
	for(i=0; i < 9 ; i++) 
	{
		if (!FPtests[i]) continue; 
		if (!FP) FP = FPtests[i];
		if (last > -1) 
		{
			FPtests[last]->next = FPtests[i];    
		}
		last = i;
	}
	if (last) FPtests[last]->next = NULL;
	osscan_timedout:
	if (target->timedout) FP = NULL;
	close(rawsd);
	pcap_close(pd);
	return FP;
}


struct AVal *fingerprint_iptcppacket(struct ip *ip, int mss, unsigned int syn) {
  struct AVal *AVs;
  int length;
  int opcode;
  unsigned short tmpshort;
  char *p,*q;
  struct tcphdr *tcp = ((struct tcphdr *) (((char *) ip) + 4 * ip->ip_hl));

  AVs = malloc(6 * sizeof(struct AVal));

  /* Link them together */
  AVs[0].next = &AVs[1];
  AVs[1].next = &AVs[2];
  AVs[2].next = &AVs[3];
  AVs[3].next = &AVs[4];
  AVs[4].next = &AVs[5];
  AVs[5].next = NULL;

  /* First we give the "response" flag to say we did actually receive
     a packet -- this way we won't match a template with Resp=N */
  AVs[0].attribute = "Resp";
  strcpy(AVs[0].value, "Y");


  /* Next we check whether the Don't Fragment bit is set */
  AVs[1].attribute = "DF";
  if(ntohs(ip->ip_off) & 0x4000) {
    strcpy(AVs[1].value,"Y");
  } else strcpy(AVs[1].value, "N");

  /* Now we do the TCP Window size */
  AVs[2].attribute = "W";
  sprintf(AVs[2].value, "%hX", ntohs(tcp->th_win));

  /* Time for the ACK, the codes are:
     S   = same as syn
     S++ = syn + 1
     O   = other
  */
  AVs[3].attribute = "ACK";
  if (ntohl(tcp->th_ack) == syn + 1)
    strcpy(AVs[3].value, "S++");
  else if (ntohl(tcp->th_ack) == syn) 
    strcpy(AVs[3].value, "S");
  else strcpy(AVs[3].value, "O");
    
  /* Now time for the flags ... they must be in this order:
     B = Bogus (64, not a real TCP flag)
     U = Urgent
     A = Acknowledgement
     P = Push
     R = Reset
     S = Synchronize
     F = Final
  */
  AVs[4].attribute = "Flags";
  p = AVs[4].value;
  if (tcp->th_flags & TH_BOG) *p++ = 'B';
  if (tcp->th_flags & TH_URG) *p++ = 'U';
  if (tcp->th_flags & TH_ACK) *p++ = 'A';
  if (tcp->th_flags & TH_PUSH) *p++ = 'P';
  if (tcp->th_flags & TH_RST) *p++ = 'R';
  if (tcp->th_flags & TH_SYN) *p++ = 'S';
  if (tcp->th_flags & TH_FIN) *p++ = 'F';
  *p++ = '\0';

  /* Now for the TCP options ... */
  AVs[5].attribute = "Ops";
  p = AVs[5].value;
  /* Partly swiped from /usr/src/linux/net/ipv4/tcp_input.c in Linux kernel */
  length = (tcp->th_off * 4) - sizeof(struct tcphdr);
  q = ((char *)tcp) + sizeof(struct tcphdr);

  while(length > 0) {
    opcode=*q++;
    length--;
    if (!opcode) {
      *p++ = 'L'; /* End of List */
      break;
    } else if (opcode == 1) {
      *p++ = 'N'; /* No Op */
    } else if (opcode == 2) {
      *p++ = 'M'; /* MSS */
      q++;
      memcpy(&tmpshort, q, sizeof(unsigned short));
      if(ntohs(tmpshort) == mss)
	*p++ = 'E'; /* Echoed */
      q += 2;
      length -= 3;
    } else if (opcode == 3) { /* Window Scale */
      *p++ = 'W';
      q += 2;
      length -= 2;
    } else if (opcode == 8) { /* Timestamp */
      *p++ = 'T';
      q += 9;
      length -= 9;
    }
  }
  *p++ = '\0';
  return AVs;
}

FingerPrint **match_fingerprint(FingerPrint *FP, int *matches_found) {
  static FingerPrint *matches[15];
  int max_matches = 14;
  FingerPrint *current_os;
  FingerPrint *current_test;
  struct AVal *tst;
  int match = 1;
  int i,j;

  *matches_found = 0;

  if (!FP) {
    matches[0] = NULL;
    return matches;
  }

  for(i = 0; o.reference_FPs[i]; i++) {
    current_os = o.reference_FPs[i];
    match = 1;
    for(current_test = current_os; current_test; current_test = current_test->next) 
      {
	tst = gettestbyname(FP, current_test->name);
	if (tst) {
	  match = AVal_match(current_test->results, tst);
	  if (!match) break;
	}
      }
    if (match) {
      /* Yeah, we found a match! */
      if ((*matches_found) >= max_matches -1) {
	matches[0] = NULL;
	*matches_found = ETOOMANYMATCHES;
	return matches;
      }
      /* Lets make sure we haven't found a match with this exact
	 name before */
      for(j=0; j < *matches_found; j++) {
	if (strcmp(current_os->OS_name, matches[j]->OS_name) == 0)
	  break;
      }
      if (j == *matches_found)
	matches[(*matches_found)++] = current_os;
    }
  }
  matches[(*matches_found)] = NULL;
  return matches;
}

struct AVal *gettestbyname(FingerPrint *FP, char *name) {

  if (!FP) return NULL;
  do {
    if (!strcmp(FP->name, name))
      return FP->results;
    FP = FP->next;
  } while(FP);
  return NULL;
}

struct AVal *getattrbyname(struct AVal *AV, char *name) {

  if (!AV) return NULL;
  do {
    if (!strcmp(AV->attribute, name))
      return AV;
    AV = AV->next;
  } while(AV);
  return NULL;
}

int AVal_match(struct AVal *reference, struct AVal *fprint) {
  struct AVal *current_ref;
  struct AVal *current_fp;
  unsigned int number;
  unsigned int val;
  char *p, *q;  /* OHHHH YEEEAAAAAHHHH!#!@#$!% */
  char valcpy[512];
  char *endptr;
  int andexp, orexp, expchar, numtrue;

  for(current_ref = reference; current_ref; current_ref = current_ref->next) {
    current_fp = getattrbyname(fprint, current_ref->attribute);    
    if (!current_fp) continue;
    /* OK, we compare an attribute value in  cinrrent_fp->value to a 
     potentially large expression in current_ref->value.  The syntax uses
    < (less than), > (greather than), + (non-zero), | (or), and & (and) 
    No parenthesis are allowed and an expression cannot have | AND & */
    numtrue = andexp = orexp = 0;
    Strncpy(valcpy, current_ref->value, sizeof(valcpy));
    p = valcpy;
    if (strchr(current_ref->value, '|')) {
      orexp = 1; expchar = '|';
    } else {
      andexp = 1; expchar = '&';
    }
    do {
      q = strchr(p, expchar);
      if (q) *q = '\0';
      if (!strcmp(p, "+")) {
	if (!*current_fp->value) { if (andexp) return 0; }
	else {
	  val = strtol(current_fp->value, &endptr, 16);
	  if (val == 0 || *endptr) { if (andexp) return 0; }
	  else { numtrue++; if (orexp) break; }
	}
      } else if (*p == '<' && isxdigit((int) p[1])) {
	if (!*current_fp->value) { if (andexp) return 0; }
	number = strtol(p + 1, &endptr, 16);
	val = strtol(current_fp->value, &endptr, 16);
	if (val >= number || *endptr) { if (andexp) return 0; }
	else { numtrue++; if (orexp) break; }
      } else if (*p == '>' && isxdigit((int) p[1])) {
	if (!*current_fp->value) { if (andexp) return 0; }
	number = strtol(p + 1, &endptr, 16);
	val = strtol(current_fp->value, &endptr, 16);
	if (val <= number || *endptr) { if (andexp) return 0; }
	else { numtrue++; if (orexp) break; }
      }
      else {
	if (strcmp(p, current_fp->value))
	  { if (andexp) return 0; }
	else { numtrue++; if (orexp) break; }
      }
      if (q) p = q + 1;
    } while(q);
      if (numtrue == 0) return 0;
    /* Whew, we made it past one Attribute alive , on to the next! */
  }
  return 1;  
}

void freeFingerPrint(FingerPrint *FP) {
FingerPrint *currentFP;
FingerPrint *nextFP;

if (!FP) return;

 for(currentFP = FP; currentFP; currentFP = nextFP) {
   nextFP = currentFP->next;
   if (currentFP->results)
     free(currentFP->results);
   free(currentFP);
 }
return;
}


int os_scan(struct hoststruct *target, unsigned short *portarray) {
FingerPrint **FP_matches[3];
int FP_nummatches[3];
struct seq_info si[3];
int try;
int i;
struct timeval now;

 if (target->timedout)
   return 1;
 
 bzero(si, sizeof(si));
 if (target->ports.state_counts_tcp[PORT_OPEN] == 0)
   log_write(LOG_STDOUT|LOG_NORMAL|LOG_SKID,"Warning:  No TCP ports found open on this machine, OS detection will be MUCH less reliable\n", si->responses);

 for(try=0; try < 3; try++) {
   if (o.host_timeout) {   
     gettimeofday(&now, NULL);
     if (target->timedout || TIMEVAL_MSEC_SUBTRACT(now, target->host_timeout) >= 0)
       {
	 target->timedout = 1;
	 return 1;
       }
   }
   target->FPs[try] = get_fingerprint(target, &si[try], portarray); 
   if (target->timedout)
     return 1;
   FP_matches[try] = match_fingerprint(target->FPs[try], &(FP_nummatches[try]));
   if (FP_matches[try][0]) 
     break;
   if (try < 2)
     sleep(2);
 }
 target->numFPs = (try == 3)? 3 : try + 1;
 memcpy(&(target->seq), &si[target->numFPs - 1], sizeof(struct seq_info));
 if (try != 3) {
   if (try > 0) {
     error("WARNING: OS didn't match until the %d try", try + 1);
     for(i=0; i < try; i++) {
       if (target->FPs[i]) {
	 if (o.debugging)
	   error("Failed match #%d (0-based):\n%s", i, fp2ascii(target->FPs[i]));
	 freeFingerPrint(target->FPs[i]);
	 target->FPs[i] = NULL;
       }
     }
     target->FPs[0] = target->FPs[try];
     target->FPs[try] = NULL;
     try = 0;
     target->numFPs = 1;
   }
   target->goodFP = 0;
 } else  {
   /* Uh-oh, we were NEVER able to match, lets take
      the first fingerprint */
   for(try=0; try < 3; try++) {   
     if (FP_nummatches[try] == 0) {   
       target->goodFP = ENOMATCHESATALL;
       break;
     }
   }
   if (try == 3) target->goodFP = ETOOMANYMATCHES;
 }

 if (target->goodFP > 0)
   target->FP_matches = FP_matches[target->goodFP];
 else target->FP_matches = FP_matches[0];
 return 1;
}

char *mergeFPs(FingerPrint *FPs[], int numFPs) {
static char str[10240];
struct AVal *AV;
FingerPrint *currentFPs[32];
char *p = str;
int i;
int changed;

if (numFPs <=0) return "(None)";
if (numFPs > 32) return "(Too many)";
  
bzero(str, sizeof(str));
for(i=0; i < numFPs; i++) {
  if (FPs[i] == NULL) {
    fatal("mergeFPs was handed a pointer to null fingerprint");
  }
  currentFPs[i] = FPs[i];
}

do {
  changed = 0;
  for(i = 0; i < numFPs; i++) {
    if (currentFPs[i]) {
      /* This junk means do not print this one if the next
	 one is the same */
      if (i == numFPs - 1 || !currentFPs[i+1] ||
	  strcmp(currentFPs[i]->name, currentFPs[i+1]->name) != 0 ||
	  AVal_match(currentFPs[i]->results,currentFPs[i+1]->results) ==0)
	{
	  changed = 1;
	  strcpy(p, currentFPs[i]->name);
	  p += strlen(currentFPs[i]->name);
	  *p++='(';
	  for(AV = currentFPs[i]->results; AV; AV = AV->next) {
	    strcpy(p, AV->attribute);
	    p += strlen(AV->attribute);
	    *p++='=';
	    strcpy(p, AV->value);
	    p += strlen(AV->value);
	    *p++ = '%';
	  }
	  if(*(p-1) != '(')
	    p--; /* Kill the final & */
	  *p++ = ')';
	  *p++ = '\n';
	}
      /* Now prepare for the next one */
      currentFPs[i] = currentFPs[i]->next;
    }
  }
} while(changed);

*p = '\0';
return str;
}


char *fp2ascii(FingerPrint *FP) {
static char str[2048];
FingerPrint *current;
struct AVal *AV;
char *p = str;
int len;
bzero(str, sizeof(str));

if (!FP) return "(None)";

if(*(FP->OS_name)) {
  len = snprintf(str, 128, "FingerPrint  %s\n", FP->OS_name);
  if (len < 0) fatal("OS name too long");
  p += len;
}

for(current = FP; current ; current = current->next) {
  strcpy(p, current->name);
  p += strlen(current->name);
  *p++='(';
  for(AV = current->results; AV; AV = AV->next) {
    strcpy(p, AV->attribute);
    p += strlen(AV->attribute);
    *p++='=';
    strcpy(p, AV->value);
    p += strlen(AV->value);
    *p++ = '%';
  }
  if(*(p-1) != '(')
    p--; /* Kill the final & */
  *p++ = ')';
  *p++ = '\n';
}
*p = '\0';
return str;
}

FingerPrint **parse_fingerprint_reference_file() {
FingerPrint **FPs;
FingerPrint *current;
FILE *fp;
char filename[256];
char line[1024];
int numrecords = 0;
int lineno = 0;
char *p, *q; /* OH YEAH!!!! */

/* If you need more than 2048 fingerprints, tough */
 FPs = safe_malloc(sizeof(FingerPrint *) * 2048); 
 bzero(FPs, sizeof(FingerPrint *) * 2048);

if (nmap_fetchfile(filename, sizeof(filename), "nmap-os-fingerprints") == -1){
  fatal("OS scan requested but I cannot find nmap-os-fingerprints file.  It should be in %s, ~/.nmap/ or .", NMAPDATADIR);
}

fp = fopen(filename, "r");

 top:
while(fgets(line, sizeof(line), fp)) {  
  lineno++;
  /* Read in a record */
  if (*line == '\n' || *line == '#')
    continue;

 fparse:

  if (strncasecmp(line, "FingerPrint", 11)) {
    fprintf(stderr, "Parse error on line %d of nmap-os-fingerprints file: %s\n", lineno, line);
    continue;
  }
  p = line + 12;
  while(*p && isspace((int) *p)) p++;
  if (!*p) {
    fprintf(stderr, "Parse error on line %d of nmap-os-fingerprints file: %s\n", lineno, line);    
    continue;
  }
  FPs[numrecords] = safe_malloc(sizeof(FingerPrint));
  bzero(FPs[numrecords], sizeof(FingerPrint));
  q = FPs[numrecords]->OS_name;
  while(*p && *p != '\n' && *p != '#') {
    *q++ = *p++;
  }

  q--;

  /* Now let us back up through any ending spaces */
  while(isspace((int)*q)) 
    q--;

  /* Terminate the sucker */
  q++; 
  *q = '\0';

  current = FPs[numrecords];
  /* Now we read the fingerprint itself */
  while(fgets(line, sizeof(line), fp)) {
    lineno++;
    if (*line == '#')
      continue;
    if (*line == '\n')
      break;
    if (!strncmp(line, "FingerPrint",11)) {
      goto fparse;
    }
    p = line;
    q = strchr(line, '(');
    if (!q) {
      fprintf(stderr, "Parse error on line %d of nmap-os-fingerprints file: %s\n", lineno, line);
      goto top;
    }
    *q = '\0';
    if(current->name) {
      current->next = safe_malloc(sizeof(FingerPrint));
      current = current->next;
      bzero(current, sizeof(FingerPrint));
    }
    current->name = strdup(p);
    p = q+1;
    *q = '(';
    q = strchr(p, ')');
    if (!q) {
      fprintf(stderr, "Parse error on line %d of nmap-os-fingerprints file: %s\n", lineno, line);
      goto top;
    }
    *q = '\0';
    current->results = str2AVal(p);
  }
  /* printf("Read in fingerprint:\n%s\n", fp2ascii(FPs[numrecords])); */
  numrecords++;
}
fclose(fp);
FPs[numrecords] = NULL; 
return FPs;
}

struct AVal *str2AVal(char *str) {
int i = 1;
int count = 1;
char *q = str, *p=str;
struct AVal *AVs;
if (!*str) return NULL;

/* count the AVals */
while((q = strchr(q, '%'))) {
  count++;
  q++;
}

AVs = safe_malloc(count * sizeof(struct AVal));
bzero(AVs, sizeof(struct AVal) * count);
for(i=0; i < count; i++) {
  q = strchr(p, '=');
  if (!q) {
    fatal("Parse error with AVal string (%s) in nmap-os-fingerprints file", str);
  }
  *q = '\0';
  AVs[i].attribute = strdup(p);
  p = q+1;
  if (i != count - 1) {
    q = strchr(p, '%');
    if (!q) {
      fatal("Parse error with AVal string (%s) in nmap-os-fingerprints file", str);
    }
    *q = '\0';
    AVs[i].next = &AVs[i+1];
  }
  strcpy(AVs[i].value, p); 
  p = q + 1;
}
return AVs;
}


struct udpprobeinfo *send_closedudp_probe(int sd, struct in_addr *victim,
unsigned short sport, unsigned short dport,struct interface_info *ainfo) {

static struct udpprobeinfo upi;
static int myttl = 0;
static unsigned char patternbyte = 0;
static unsigned short id = 0; 
char packet[328]; /* 20 IP hdr + 8 UDP hdr + 300 data */
struct ip *ip = (struct ip *) packet;
udphdr_bsd *udp = (udphdr_bsd *) (packet + sizeof(struct ip));
struct in_addr *source;
int datalen = 300;
char *data = packet + 28;
unsigned short realcheck; /* the REAL checksum */
int res;
struct sockaddr_in sock;
int decoy;
struct pseudo_udp_hdr {
  struct in_addr source;
  struct in_addr dest;        
  char zero;
  char proto;        
  unsigned short length;
} *pseudo = (struct pseudo_udp_hdr *) ((char *)udp - 12) ;

if (!patternbyte) patternbyte = (get_random_uint() % 60) + 65;
memset(data, patternbyte, datalen);

while(!id) id = get_random_uint();

/* check that required fields are there and not too silly */
if ( !victim || !sport || !dport || sd < 0) {
  fprintf(stderr, "send_udp_raw: One or more of your parameters suck!\n");
  return NULL;
}

if (!myttl)  myttl = (time(NULL) % 14) + 51;
/* It was a tough decision whether to do this here for every packet
   or let the calling function deal with it.  In the end I grudgingly decided
   to do it here and potentially waste a couple microseconds... */
sethdrinclude(sd); 

 for(decoy=0; decoy < o.numdecoys; decoy++) {
   source = &o.decoys[decoy];

   /*do we even have to fill out this damn thing?  This is a raw packet, 
     after all */
   sock.sin_family = AF_INET;
   sock.sin_port = htons(dport);
   sock.sin_addr.s_addr = victim->s_addr;


   bzero((char *) packet, sizeof(struct ip) + sizeof(udphdr_bsd));

   udp->uh_sport = htons(sport);
   udp->uh_dport = htons(dport);
   udp->uh_ulen = htons(8 + datalen);

   /* Now the psuedo header for checksuming */
   pseudo->source.s_addr = source->s_addr;
   pseudo->dest.s_addr = victim->s_addr;
   pseudo->proto = IPPROTO_UDP;
   pseudo->length = htons(sizeof(udphdr_bsd) + datalen);

   /* OK, now we should be able to compute a valid checksum */
realcheck = in_cksum((unsigned short *)pseudo, 20 /* pseudo + UDP headers */ +
 datalen);
#if STUPID_SOLARIS_CHECKSUM_BUG
 udp->uh_sum = sizeof(struct udphdr) + datalen;
#else
udp->uh_sum = realcheck;
#endif

   /* Goodbye, pseudo header! */
   bzero(pseudo, 12);

   /* Now for the ip header */
   ip->ip_v = 4;
   ip->ip_hl = 5;
   ip->ip_len = BSDFIX(sizeof(struct ip) + sizeof(udphdr_bsd) + datalen);
   ip->ip_id = id;
   ip->ip_ttl = myttl;
   ip->ip_p = IPPROTO_UDP;
   ip->ip_src.s_addr = source->s_addr;
   ip->ip_dst.s_addr= victim->s_addr;

   upi.ipck = in_cksum((unsigned short *)ip, sizeof(struct ip));

   ip->ip_sum = upi.ipck;


   /* OK, now if this is the real she-bang (ie not a decoy) then
      we stick all the inph0 in our upi */
   if (decoy == o.decoyturn) {   
     upi.iptl = 28 + datalen;
     upi.ipid = id;
     upi.sport = sport;
     upi.dport = dport;
     upi.udpck = realcheck;
     upi.udplen = 8 + datalen;
     upi.patternbyte = patternbyte;
     upi.target.s_addr = ip->ip_dst.s_addr;
   }
   if (TCPIP_DEBUGGING > 1) {
     log_write(LOG_STDOUT, "Raw UDP packet creation completed!  Here it is:\n");
     readudppacket(packet,1);
   }
   if (TCPIP_DEBUGGING > 1)     
     log_write(LOG_STDOUT, "\nTrying sendto(%d , packet, %d, 0 , %s , %d)\n",
	    sd, BSDUFIX(ip->ip_len), inet_ntoa(*victim),
	    (int) sizeof(struct sockaddr_in));
/*	      if ((res = sendto(sd, packet, BSDUFIX(ip->ip_len), 0,*/
   if ((res = Sendto("send_closedudp_probe",sd, packet, BSDUFIX(ip->ip_len), 0,
		     (struct sockaddr *)&sock, (int) sizeof(struct sockaddr_in),ainfo)) == -1)
     {
       perror("sendto in send_udp_raw_decoys");
       return NULL;
     }

   if (TCPIP_DEBUGGING > 1) log_write(LOG_STDOUT, "successfully sent %d bytes of raw_tcp!\n", res);
 }

return &upi;

}

struct AVal *fingerprint_portunreach(struct ip *ip, struct udpprobeinfo *upi) {
struct icmp *icmp;
struct ip *ip2;
int numtests = 10;
unsigned short checksum;
unsigned short *checksumptr;
udphdr_bsd *udp;
struct AVal *AVs;
int i;
int current_testno = 0;
unsigned char *datastart, *dataend;

/* The very first thing we do is make sure this is the correct
   response */
if (ip->ip_p != IPPROTO_ICMP) {
  error("fingerprint_portunreach handed a non-ICMP packet!");
  return NULL;
}

if (ip->ip_src.s_addr != upi->target.s_addr)
  return NULL;  /* Not the person we sent to */

icmp = ((struct icmp *)  (((char *) ip) + 4 * ip->ip_hl));
if (icmp->icmp_type != 3 || icmp->icmp_code != 3)
  return NULL; /* Not a port unreachable */

ip2 = (struct ip*) ((char *)icmp + 8);
udp = (udphdr_bsd *) ((char *)ip2 + 20);

/* The ports better match as well ... */
if (ntohs(udp->uh_sport) != upi->sport || ntohs(udp->uh_dport) != upi->dport) {
  return NULL;
}

/* Create the Avals */
AVs = safe_malloc(numtests * sizeof(struct AVal));
bzero(AVs, numtests * sizeof(struct AVal));

/* Link them together */
for(i=0; i < numtests - 1; i++)
  AVs[i].next = &AVs[i+1];

/* First of all, if we got this far the response was yes */
AVs[current_testno].attribute = "Resp";
strcpy(AVs[current_testno].value, "Y");

current_testno++;

/* Now let us do an easy one, Don't fragment */
AVs[current_testno].attribute = "DF";
  if(ntohs(ip->ip_off) & 0x4000) {
    strcpy(AVs[current_testno].value,"Y");
  } else strcpy(AVs[current_testno].value, "N");

current_testno++;

/* Now lets do TOS of the response (note, I've never seen this be
   useful */
AVs[current_testno].attribute = "TOS";
sprintf(AVs[current_testno].value, "%hX", ip->ip_tos);

current_testno++;

/* Now we look at the IP datagram length that was returned, some
   machines send more of the original packet back than others */
AVs[current_testno].attribute = "IPLEN";
sprintf(AVs[current_testno].value, "%hX", ntohs(ip->ip_len));

current_testno++;

/* OK, lets check the returned IP length, some systems @$@ this
   up */
AVs[current_testno].attribute = "RIPTL";
sprintf(AVs[current_testno].value, "%hX", ntohs(ip2->ip_len));

current_testno++;

/* This next test doesn't work on Solaris because the lamers
   overwrite our ip_id */
#if !defined(SOLARIS) && !defined(SUNOS) && !defined(IRIX)
/* Now lets see how they treated the ID we sent ... */
AVs[current_testno].attribute = "RID";
if (ntohs(ip2->ip_id) == 0)
  strcpy(AVs[current_testno].value, "0");
else if (ip2->ip_id == upi->ipid)
  strcpy(AVs[current_testno].value, "E"); /* The "expected" value */
else strcpy(AVs[current_testno].value, "F"); /* They fucked it up */

current_testno++;
#endif

/* Let us see if the IP checksum we got back computes */

AVs[current_testno].attribute = "RIPCK";
/* Thanks to some machines not having struct ip member ip_sum we
   have to go with this BS */
checksumptr = (unsigned short *)   ((char *) ip2 + 10);
checksum =   *checksumptr;

if (checksum == 0)
  strcpy(AVs[current_testno].value, "0");
else {
  *checksumptr = 0;
  if (in_cksum((unsigned short *)ip2, 20) == checksum) {
    strcpy(AVs[current_testno].value, "E"); /* The "expected" value */
  } else {
    strcpy(AVs[current_testno].value, "F"); /* They fucked it up */
  }
  *checksumptr = checksum;
}

current_testno++;

/* UDP checksum */
AVs[current_testno].attribute = "UCK";
if (udp->uh_sum == 0)
  strcpy(AVs[current_testno].value, "0");
else if (udp->uh_sum == upi->udpck)
  strcpy(AVs[current_testno].value, "E"); /* The "expected" value */
else strcpy(AVs[current_testno].value, "F"); /* They fucked it up */

current_testno++;

/* UDP length ... */
AVs[current_testno].attribute = "ULEN";
sprintf(AVs[current_testno].value, "%hX", ntohs(udp->uh_ulen));

current_testno++;

/* Finally we ensure the data is OK */
datastart = ((unsigned char *)udp) + 8;
dataend = (unsigned char *)  ip + ntohs(ip->ip_len);

while(datastart < dataend) {
  if (*datastart != upi->patternbyte) break;
  datastart++;
}
AVs[current_testno].attribute = "DAT";
if (datastart < dataend)
  strcpy(AVs[current_testno].value, "F"); /* They fucked it up */
else  
  strcpy(AVs[current_testno].value, "E");

AVs[current_testno].next = NULL;

return AVs;
}
