#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];
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;
unsigned int seq_diffs[NUM_SEQ_SAMPLES];
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 */
 if ((rawsd = socket(AF_INET, SOCK_RAW, IPPROTO_RAW)) < 0 )
   pfatal("socket trobles in get_fingerprint");
 unblock_socket(rawsd);
 broadcast_socket(rawsd);

 /* 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, 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, &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);
     }
     
     /* 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);
     }

     /* 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);
     }

     /* 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);
     }
   }
   
   /* 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);
   }

     /* 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);
   }

     /* 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);
   }

   if (!FPtests[8]) {
     if (o.scan_delay) enforce_scan_delay(NULL);
     upi = send_closedudp_probe(rawsd, &target->host, o.magic_port, closedport);
   }
   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) {
     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);
       if (!o.scan_delay)
	 usleep( 5000 + target->to.srtt);
    }
     /*     usleep(25000);*/
   }
   /* 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 */
#ifdef LINUX       
       si->index = (unsigned int) (0.5 + sqrt(seq_inc_sum));
#else
       si->index = (unsigned int) (0.5 + pow(seq_inc_sum, 0.5));
#endif

       /*       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) {

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));
#if HAVE_IP_IP_SUM
   ip->ip_sum = upi.ipck;
#endif

   /* 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,
		     (struct sockaddr *)&sock, (int) sizeof(struct sockaddr_in))) == -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;
}
