/* eval.cpp - Evaluation program for 1999 DARPA IDS evaluaton weeks 4-5.

Copyright (C) 2003, Matt Mahoney.  This program is distributed
without warranty under terms of the GNU general public license
See http://www.gnu.org/licenses/gpl.txt

  Version 1/6/03 - Added detections for 1999 week 2.
  Version 1/24/03 - Allows dates 3/1 through 4/10 (weeks 1-5) in alarms.
  Version 12/15/03 - Added poorly detected attack count (as defined in
    table 4 of The 1999 DARPA Off-Line Intrusion Detection
    Evaluation by Lippmann et al., Computer, 2000).

Usage: eval - v fa < file.sim
       eval file.sim v fa

where file.sim is the output of an IDS in 1999 DARPA format, which has
lines of the following form:

  id mm/dd/yyyy hh:mm:ss target score #comments

The id is ignored.  The alarm gives the date, time, host name or IP
address of the target, and a numeric score indicating a confidence level.
The output depends on the v option:

  0 = Warnings about bad input (alarms ignored).
  1 = Table of attacks detected at fa (100) false alarms by category.
  2 = Also list of detected attack types with alarm comments (default).
  3 = Also list detected instances and how many FA before each.
  4 = Also a detailed list of every detection and false alarm.

  fa = Stop evaluation after fa false alarms (default 100).

Like EVAL3 and EVAL4, an attack is detected if 1 or more alarms identifies
the target IP address and the time of any part of the attack with 60
seconds leeway.  A false alarm is any alarm that does not match at least
one attack.  Detections are counted at fa false alarms (default 100).
Attacks detected between fa and fa+1 false alarms count, although in
practice it would depend on the threshold.  Thus EVAL (like EVAL4) will
report fa+1 false alarms if it does not process all alarms.

EVAL differs somewhat from EVAL3 and EVAL4.

- EVAL computes in-spec and out-of-spec detections for common cases.
  Out-of-spec detections are not counted.
- Detections during week 2 are not counted.
- Badly formatted alarms (e.g. target=0.0.0.0, score=0, date out of range,
  syntax error) are discarded.  EVAL3 and EVAL4 count these as false alarms.
- One alarm may be credited to two overlapping attacks and count as two
  detections.  EVAL3 and EVAL4 would arbitrarily pick just one.
- Target addresses must be 172.16.x.x or 192.168.x.x.  EVAL3 and
  EVAL4 would count matches to external destination addresses in the
  truth file.  These were removed.  3 attacks (2 httptunnel and 1
  portsweep) had no internal destination addresses, so the internal
  source addresses from the master identification file were used.
- Duplicate alarms are not removed as in EVAL3.
- The mislabeled apache2_err attack which EVAL3 and EVAL4 detect
  remains mislabeled (not detected by EVAL).
- Some attack names spellings were corrected or changed to be consistent
  with the master identification list.
- The input does not need to be sorted by score as with EVAL4.
- There is no limit on the number of alarms as in EVAL3 (which stops
  at 8000).
- Alarms with equal scores are taken in the order they are input.
- The target may be a host name (lower case) as well as an IP address.
- The input format need not be fixed width as in EVAL3 and EVAL4.
- The comment charcater # is optional.
- EVAL is a lot faster than EVAL3.

*/

#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

// 8-32 bit types
typedef unsigned char U8;
typedef unsigned short U16;
typedef unsigned long U32;

// List of attacks to be detected, generated by truth2eval.pl from
// http://www.ll.mit.edu/IST/ideval/docs/1999/master-listfile-condensed.txt
// Some attack names were corrected.

static struct Attack {
  U32 id;  // ID number, matches the segment in aseg
  U32 flags;  // Bits 0-16: insider, manual, console, succesful,
              // evidence in files, outside.tcpdump, inside.tcpdump, BSM,
              // logs, directory lists, stealthy, new,
              // probe, DOS, R2L, U2R, data
              // Bits 17-20 (pascal, hume, zeno, marx) are set later
              // 21-23 = week 4-5, week 2, poorly detected
  const char* name;  // ID (wd.hhmmss) and attack name
  void print() const;  // Print name, flags
} attack[]={
{  0,0,""},
{  1,0x087F8,"41.084031 ps"},
{  2,0x04078,"41.084818 sendmail"},
{  3,0x818B0E,"41.090000 ntfsdos"},
{  4,0x801459,"41.091531 portsweep"},
{  5,0x804B78,"41.093708 sshtrojan"},
{  6,0x801459,"41.111531 portsweep"},
{  7,0x04078,"41.112127 xsnoop"},
{  8,0x804078,"41.114554 snmpget"},
{  9,0x04178,"41.114703 guesstelnet"},
{ 10,0x801478,"41.122222 portsweep"},
{ 11,0x041D9,"41.133333 guessftp"},
{ 12,0x043F8,"41.135830 ftpwrite"},
{ 13,0x08959,"41.155048 yaga"},
{ 14,0x02059,"41.161308 crashiis"},
{ 15,0x801478,"41.162715 portsweep"},
{ 16,0x10AF8,"41.182453 secret"},
{ 17,0x02078,"41.213446 smurf"},
{ 18,0x043B8,"42.090909 httptunnel"},
{ 19,0x04038,"42.094131 phf"},
{ 20,0x818638,"42.104107 loadmodule"},
{ 21,0x182B8,"42.112913 ps"},
{ 22,0x818B0E,"42.120000 ntfsdos"},
{ 23,0x10838,"42.122248 secret"},
{ 24,0x818038,"42.135452 sqlattack"},
{ 25,0x808938,"42.143228 sechole"},
{ 26,0x02138,"42.145441 land"},
{ 27,0x02038,"42.155148 mailbomb"},
{ 28,0x02038,"42.174944 processtable"},
{ 29,0x02138,"42.210410 crashiis"},
{ 30,0x01078,"43.080401 satan"},
{ 31,0x04B7A,"43.084000 netcat_setup"},
{ 32,0x04278,"43.093814 imap"},
{ 33,0x14B7A,"43.100000 ppmacro"},
{ 34,0x02159,"43.101313 processtable"},
{ 35,0x0848E,"43.103931 fdformat"},
{ 36,0x0497A,"43.110000 netcat_breakin"},
{ 37,0x023F8,"43.111111 warezmaster"},
{ 38,0x802A59,"43.113032 arppoison"},
{ 39,0x804F78,"43.114500 ncftp"},
{ 40,0x10AF8,"43.122854 secret"},
{ 41,0x0417A,"43.125900 named"},
{ 42,0x04178,"43.134223 guessftp"},
{ 43,0x02059,"43.144547 smurf"},
{ 44,0x041F8,"43.155357 guest"},
{ 45,0x801478,"43.164334 portsweep"},
{ 46,0x02078,"43.165422 mailbomb"},
{ 47,0x041F8,"43.175811 guesstelnet"},
{ 48,0x804078,"43.191217 snmpget"},
{ 49,0x01178,"44.080000 ntinfoscan"},
{ 50,0x01078,"44.080757 ipsweep"},
{ 51,0x02159,"44.082615 teardrop"},
{ 52,0x804B7A,"44.083000 netbus"},
{ 53,0x814D78,"44.091807 sshtrojan"},
{ 54,0x802959,"44.110000 dosnuke"},
{ 55,0x804E59,"44.114500 ncftp"},
{ 56,0x14A7A,"44.120500 ppmacro"},
{ 57,0x041F8,"44.124700 guest"},
{ 58,0x0407A,"44.130700 xlock"},
{ 59,0x04178,"44.131529 guesspop"},
{ 60,0x04078,"44.161242 phf"},
{ 61,0x029D9,"44.164944 sshprocesstable"},
{ 62,0x02078,"44.183234 mailbomb"},
{ 63,0x818278,"44.201454 sqlattack"},
{ 64,0x02059,"45.084547 smurf"},
{ 65,0x802878,"45.090000 arppoison"},
{ 66,0x804B78,"45.095541 sshtrojan"},
{ 67,0x801478,"45.100334 ipsweep"},
{ 68,0x0407A,"45.103937 xlock"},
{ 69,0x0417A,"45.105138 named"},
{ 70,0x801478,"45.111010 portsweep"},
{ 71,0x804E59,"45.114500 ncftp"},
{ 72,0x804B7A,"45.114900 netbus"},
{ 73,0x02078,"45.123234 mailbomb"},
{ 74,0x0407A,"45.130542 named"},
{ 75,0x801478,"45.140000 ipsweep"},
{ 76,0x808278,"45.162148 loadmodule"},
{ 77,0x808978,"45.165009 sechole"},
{ 78,0x01078,"45.181011 portsweep"},
{ 79,0x01078,"45.192523 ipsweep"},
{ 80,0x10A88,"45.203400 secret"},
{ 81,0x0207A,"51.083800 pod"},
{ 82,0x801439,"51.084334 portsweep"},
{ 83,0x0207A,"51.085000 pod"},
{ 84,0x8021F8,"51.085947 warezclient"},
{ 85,0x0205A,"51.093123 smurf"},
{ 86,0x010F8,"51.094334 portsweep"},
{ 87,0x0207A,"51.102700 apache2"},
{ 88,0x04178,"51.105811 guesstelnet"},
{ 89,0x80295B,"51.114500 dosnuke"},
{ 90,0x808659,"51.120309 loadmodule"},
{ 91,0x082F8,"51.121101 ffbconfig"},
{ 92,0x02078,"51.131803 smurf"},
{ 93,0x802878,"51.133019 arppoison"},
{ 94,0x0207A,"51.140100 apache2"},
{ 95,0x0207A,"51.142100 pod"},
{ 96,0x04159,"51.144601 imap"},
{ 97,0x801478,"51.150000 ipsweep"},
{ 98,0x04159,"51.163200 dict"},
{ 99,0x021D8,"51.171917 syslogd"},
{100,0x02078,"51.180445 neptune"},
{101,0x02178,"51.183623 crashiis"},
{102,0x801878,"51.185613 ls_domain"},
{103,0x802978,"51.194715 dosnuke"},
{104,0x02068,"51.200037 udpstorm"},
{105,0x8028F8,"51.201715 selfping"},
{106,0x804F59,"51.204631 ncftp"},
{107,0x802878,"52.081109 tcpreset"},
{108,0x02178,"52.083236 teardrop"},
{109,0x08B59,"52.085357 casesen"},
{110,0x0407A,"52.092200 xsnoop"},
{111,0x8028F8,"52.094514 selfping"},
{112,0x808278,"52.100738 xterm"},
{113,0x043D9,"52.101901 ftpwrite"},
{114,0x02079,"52.103409 back"},
{115,0x087FA,"52.112045 ps"},
{116,0x02078,"52.113855 neptune"},
{117,0x040F8,"52.120600 httptunnel"},
{118,0x087F8,"52.125501 eject"},
{119,0x02178,"52.130655 pod"},
{120,0x08B78,"52.132827 yaga"},
{121,0x02078,"52.135003 crashiis"},
{122,0x04B7A,"52.140207 ppmacro"},
{123,0x021DB,"52.141200 syslogd"},
{124,0x808378,"52.142452 perl"},
{125,0x183F8,"52.162435 fdformat"},
{126,0x801878,"52.165435 queso"},
{127,0x02038,"52.181637 neptune"},
{128,0x802959,"52.205605 dosnuke"},
{129,0x01078,"52.211313 portsweep"},
{130,0x804E59,"52.214522 ncftp"},
{131,0x0205A,"52.050813 udpstorm"},
{132,0x802BFA,"53.045454 selfping"},
{133,0x0407A,"53.084346 xlock"},
{134,0x04078,"53.085717 phf"},
{135,0x80284A,"53.092039 tcpreset"},
{136,0x804B7A,"53.094800 netbus"},
{137,0x02078,"53.102617 back"},
{138,0x04B7A,"53.110500 netcat"},
{139,0x801C78,"53.110516 queso"},
{140,0x801478,"53.123735 portsweep"},
{141,0x808678,"53.133203 perl"},
{142,0x801C59,"53.134015 queso"},
{143,0x80407A,"53.144800 snmpget"},
{144,0x02159,"53.150110 processtable"},
{145,0x02058,"53.152648 back"},
{146,0x086F8,"53.155432 ffbconfig"},
{147,0x02159,"53.171350 apache2"},
{148,0x01078,"53.195130 portsweep"},
{149,0x0868E,"54.082003 ps"},
{150,0x04079,"54.090101 phf"},
{151,0x0895B,"54.091200 casesen"},
{152,0x810B0E,"54.102102 ntfsdos"},
{153,0x801478,"54.103459 portsweep"},
{154,0x01378,"54.110416 ntinfoscan"},
{155,0x0897A,"54.115000 yaga"},
{156,0x0207A,"54.115701 crashiis"},
{157,0x043F8,"54.120600 httptunnel"},
{158,0x082F8,"54.125758 fdformat"},
{159,0x01078,"54.145832 satan"},
{160,0x02078,"54.155338 teardrop"},
{161,0x808978,"54.160341 sechole"},
{162,0x801C59,"54.170132 resetscan"},
{163,0x01078,"54.171643 ipsweep"},
{164,0x804078,"54.175007 snmpget"},
{165,0x01378,"54.183002 ntinfoscan"},
{166,0x801978,"54.190707 ls_domain"},
{167,0x8021F8,"54.194108 warezclient"},
{168,0x01178,"54.195951 mscan"},
{169,0x802878,"54.225131 arppoison"},
{170,0x01079,"55.080105 portsweep"},
{171,0x0407A,"55.080500 xsnoop"},
{172,0x02159,"55.081418 crashiis"},
{173,0x01C1B,"55.082500 insidesniffer"},
{174,0x02078,"55.084452 back"},
{175,0x01879,"55.085500 insidesniffer"},
{176,0x04B5B,"55.085514 netcat"},
{177,0x808078,"55.091529 xterm"},
{178,0x801478,"55.093137 portsweep"},
{179,0x08A0E,"55.100600 anypw"},
{180,0x041D9,"55.100830 guest"},
{181,0x802B4A,"55.102000 tcpreset"},
{182,0x80830E,"55.103001 perl"},
{183,0x0487A,"55.110800 framespoofer"},
{184,0x801478,"55.115202 portsweep"},
{185,0x808678,"55.123412 sqlattack"},
{186,0x08978,"55.124400 yaga"},
{187,0x02078,"55.125112 crashiis"},
{188,0x04178,"55.125811 guesstelnet"},
{189,0x02078,"55.125830 crashiis"},
{190,0x021F8,"55.140643 syslogd"},
{191,0x083F9,"55.141732 eject"},
{192,0x02059,"55.163447 land"},
{193,0x021FA,"55.171917 syslogd"},
{194,0x04278,"55.172757 sendmail"},
{195,0x808078,"55.174733 xterm"},
{196,0x02078,"55.183012 neptune"},
{197,0x808659,"55.184715 perl"},
{198,0x8021F8,"55.185233 warezclient"},
{199,0x801C38,"55.202002 queso"},
{200,0x08B78,"55.204925 casesen"},
{201,0x10A88,"55.200530 secret"},
{202,0x01000,"21.080101 ntinfoscan"},
{203,0x02000,"21.085015 pod"},
{204,0x02000,"21.093916 back"},
{205,0x04000,"21.120918 httptunnel"},
{206,0x02000,"21.155715 land"},
{207,0x10000,"21.172713 secret"},
{208,0x08000,"21.190917 ps"},
{209,0x01000,"22.084417 portsweep"},
{210,0x08000,"22.094351 eject"},
{211,0x02000,"22.100643 back"},
{212,0x08000,"22.105419 loadmodule"},
{213,0x10000,"22.114913 secret"},
{214,0x02000,"22.142516 mailbomb"},
{215,0x01000,"22.130510 ipsweep"},
{216,0x04000,"22.161115 phf"},
{217,0x04000,"22.180617 httptunnel"},
{218,0x01000,"23.120213 satan"},
{219,0x02000,"23.134418 mailbomb"},
{220,0x08000,"23.152518 perl"},
{221,0x01000,"23.201710 ipsweep"},
{222,0x08000,"23.232300 eject"},
{223,0x02000,"23.235614 crashiis"},
{224,0x02000,"24.080417 crashiis"},
{225,0x01000,"24.093317 satan"},
{226,0x01000,"24.105011 portsweep"},
{227,0x02000,"24.110416 neptune"},
{228,0x10000,"24.125713 secret"},
{229,0x08000,"24.142517 perl"},
{230,0x02000,"24.154715 land"},
{231,0x01000,"24.163610 ipsweep"},
{232,0x04000,"24.191618 ftpwrite"},
{233,0x04000,"25.080717 phf"},
{234,0x08000,"25.081040 perl"},
{235,0x08000,"25.081646 ps"},
{236,0x02000,"25.091815 pod"},
{237,0x02000,"25.112015 neptune"},
{238,0x02000,"25.124012 crashiis"},
{239,0x08000,"25.131217 loadmodule"},
{240,0x08000,"25.140617 perl"},
{241,0x08000,"25.142418 ps"},
{242,0x08000,"25.152416 eject"},
{243,0x01000,"25.171310 portsweep"},
{244,0x04000,"25.174318 ftpwrite"}
};

// List of attack segments, generated by truth2eval.pl from
// http://www.ll.mit.edu/IST/ideval/docs/1999/master-listfile-condensed.txt
// Some remote target addresses were corrected by using the local source
// address as the target.

static const struct AttackSegment {
  U32 id;  // Attack index for which this segment is a part
  U32 ip;  // Target IP address.  If last byte is 00, then allow any 0-255
  U32 start, finish;  // Time interval, seconds since 00:00 Jan. 25, 1999
} aseg [] = {
{  1,0xAC107032,5213915,5214162},
{  1,0xAC107032,5214567,5214610},
{  1,0xAC107032,5215214,5216680},
{  2,0xAC107232,5215692,5215694},
{  3,0xAC107064,5216880,5217360},
{  4,0xAC107132,5217305,5217306},
{  4,0xAC107132,5217921,5217922},
{  4,0xAC107132,5218536,5218537},
{  5,0xAC107232,5218583,5218584},
{  5,0xAC107232,5218715,5218906},
{  6,0xC0A80101,5224515,5224756},
{  7,0xAC1072A8,5224963,5225040},
{  8,0xAC100001,5226312,5228323},
{  9,0xAC107132,5226436,5226446},
{ 10,0xAC107064,5228535,5228836},
{ 11,0xAC107032,5232796,5232817},
{ 11,0xAC107646,5232800,5232818},
{ 12,0xAC107032,5234296,5234308},
{ 12,0xAC107032,5234609,5234641},
{ 13,0xAC107064,5241015,5242421},
{ 13,0xAC107064,5255416,5256201},
{ 14,0xAC107064,5242388,5243293},
{ 15,0xAC1072A9,5243230,5243526},
{ 16,0xAC107032,5250259,5250780},
{ 17,0xAC107032,5261656,5261667},
{ 18,0xAC107032,5303357,5303516},
{ 19,0xAC107232,5305272,5305273},
{ 20,0xAC107132,5308872,5310442},
{ 21,0xAC107032,5311757,5311862},
{ 21,0xAC107032,5312830,5313909},
{ 22,0xAC107064,5313600,5314200},
{ 23,0xAC107232,5314933,5318082},
{ 24,0xAC1070C2,5320457,5320526},
{ 25,0xAC107064,5322735,5323136},
{ 25,0xAC107064,5340735,5341027},
{ 26,0xAC107132,5324050,5324951},
{ 27,0xAC107232,5327476,5327743},
{ 27,0xAC107014,5327476,5327477},
{ 27,0xAC1070C2,5327478,5327480},
{ 27,0xAC107014,5327486,5327740},
{ 27,0xAC1072CF,5327739,5327740},
{ 27,0xAC107014,5327751,5327752},
{ 27,0xAC107154,5328147,5328148},
{ 27,0xAC107014,5328147,5328160},
{ 28,0xAC107232,5334555,5334736},
{ 29,0xAC107064,5346250,5347157},
{ 30,0xAC107232,5385854,5385867},
{ 31,0xAC107064,5390772,5390776},
{ 32,0xAC107232,5391493,5391546},
{ 33,0xAC107064,5393676,5393680},
{ 33,0xAC107064,5394217,5394457},
{ 34,0xAC107132,5393598,5395280},
{ 35,0xAC107032,5395080,5395260},
{ 36,0xAC107064,5397068,5397100},
{ 37,0xAC107032,5397939,5397986},
{ 38,0xAC107132,5398213,5398894},
{ 39,0xAC107232,5400758,5400847},
{ 40,0xAC107032,5401695,5402187},
{ 41,0xAC107014,5403632,5403633},
{ 42,0xAC107132,5406136,5406252},
{ 43,0xAC107064,5423365,5423366},
{ 44,0xAC107032,5413995,5414158},
{ 45,0xAC107064,5416995,5417229},
{ 46,0xAC107032,5417657,5417838},
{ 47,0xAC107032,5421497,5421725},
{ 48,0xAC100001,5425936,5426953},
{ 49,0xAC107064,5472061,5472964},
{ 50,0xAC107001,5472431,5472432},
{ 50,0xAC107002,5472441,5472442},
{ 50,0xAC107003,5472451,5472452},
{ 50,0xAC107004,5472461,5472462},
{ 50,0xAC107005,5472471,5472472},
{ 50,0xAC107006,5472482,5472483},
{ 50,0xAC107007,5472492,5472493},
{ 50,0xAC107008,5472502,5472503},
{ 50,0xAC107009,5472512,5472513},
{ 50,0xAC10700A,5472522,5472523},
{ 51,0xAC107232,5473580,5474481},
{ 52,0xAC107064,5474111,5474116},
{ 52,0xAC107064,5474379,5474475},
{ 52,0xC0A8010A,5474506,5474507},
{ 53,0xAC107232,5477895,5478525},
{ 54,0xAC107064,5482807,5483800},
{ 55,0xAC107232,5485514,5485602},
{ 55,0xAC107628,5485535,5485582},
{ 56,0xAC107064,5487158,5487163},
{ 56,0xAC107064,5487885,5487983},
{ 57,0xAC107032,5489807,5489969},
{ 58,0xAC1072A8,5490499,5490524},
{ 59,0xAC1070C2,5490916,5491047},
{ 60,0xAC107232,5501535,5501536},
{ 61,0xAC107032,5503755,5504256},
{ 62,0xAC107232,5509937,5510544},
{ 63,0xAC1070C2,5516057,5516125},
{ 64,0xAC107032,5561118,5561120},
{ 65,0xAC107232,5562010,5562781},
{ 66,0xAC107232,5565315,5565944},
{ 67,0xAC107001,5565790,5565791},
{ 67,0xAC107002,5565890,5565891},
{ 67,0xAC107003,5565990,5565991},
{ 67,0xAC107004,5566090,5566091},
{ 67,0xAC107005,5566190,5566191},
{ 67,0xAC107006,5566290,5566291},
{ 67,0xAC107007,5566390,5566391},
{ 67,0xAC107008,5566490,5566491},
{ 67,0xAC107009,5566590,5566591},
{ 67,0xAC10700A,5566690,5566691},
{ 68,0xAC107232,5568124,5568203},
{ 69,0xAC107014,5568804,5569019},
{ 69,0xAC107169,5568804,5569019},
{ 70,0xAC107132,5569815,5570086},
{ 71,0xAC107232,5571913,5572002},
{ 71,0xAC107646,5571935,5571982},
{ 72,0xAC107064,5572260,5572265},
{ 72,0xAC107064,5572442,5572513},
{ 73,0xAC107132,5574737,5575516},
{ 74,0xAC107014,5579370,5579428},
{ 75,0xAC107201,5580015,5580016},
{ 75,0xAC107203,5580145,5580146},
{ 75,0xAC107205,5580274,5580275},
{ 75,0xAC107204,5580404,5580405},
{ 75,0xAC107232,5580533,5580534},
{ 76,0xAC107132,5588476,5588817},
{ 77,0xAC107064,5590215,5590628},
{ 77,0xAC107064,5592610,5592926},
{ 78,0xAC107132,5595015,5595020},
{ 79,0xAC107001,5599514,5599515},
{ 79,0xAC107002,5599524,5599525},
{ 79,0xAC107003,5599534,5599535},
{ 79,0xAC107004,5599544,5599545},
{ 79,0xAC107005,5599554,5599555},
{ 79,0xAC107006,5599564,5599565},
{ 79,0xAC107007,5599574,5599575},
{ 79,0xAC107008,5599584,5599585},
{ 79,0xAC107009,5599594,5599595},
{ 79,0xAC10700A,5599604,5599605},
{ 79,0xAC10700B,5599615,5599616},
{ 79,0xAC10700C,5599625,5599626},
{ 79,0xAC10700D,5599635,5599636},
{ 79,0xAC10700E,5599645,5599646},
{ 79,0xAC10700F,5599655,5599656},
{ 79,0xAC107010,5599665,5599666},
{ 79,0xAC107011,5599675,5599676},
{ 79,0xAC107012,5599685,5599686},
{ 79,0xAC107013,5599695,5599696},
{ 79,0xAC107014,5599705,5599706},
{ 79,0xAC107015,5599715,5599716},
{ 79,0xAC107016,5599725,5599726},
{ 79,0xAC107017,5599735,5599736},
{ 79,0xAC107018,5599745,5599746},
{ 79,0xAC107019,5599755,5599756},
{ 79,0xAC10701A,5599765,5599766},
{ 79,0xAC10701B,5599775,5599776},
{ 79,0xAC10701C,5599785,5599786},
{ 79,0xAC10701D,5599795,5599796},
{ 79,0xAC10701E,5599805,5599806},
{ 79,0xAC10701F,5599815,5599816},
{ 79,0xAC107020,5599825,5599826},
{ 79,0xAC107021,5599835,5599836},
{ 79,0xAC107022,5599845,5599846},
{ 79,0xAC107023,5599855,5599856},
{ 79,0xAC107024,5599865,5599866},
{ 79,0xAC107025,5599875,5599876},
{ 79,0xAC107026,5599885,5599886},
{ 79,0xAC107027,5599895,5599896},
{ 79,0xAC107028,5599905,5599906},
{ 79,0xAC107029,5599915,5599916},
{ 79,0xAC10702A,5599925,5599926},
{ 79,0xAC10702B,5599935,5599936},
{ 79,0xAC10702C,5599945,5599946},
{ 79,0xAC10702D,5599955,5599956},
{ 79,0xAC10702E,5599965,5599966},
{ 79,0xAC10702F,5599975,5599976},
{ 79,0xAC107030,5599985,5599986},
{ 79,0xAC107031,5599995,5599996},
{ 79,0xAC107032,5600005,5600006},
{ 79,0xAC107033,5600015,5600016},
{ 79,0xAC107034,5600025,5600026},
{ 79,0xAC107035,5600035,5600036},
{ 79,0xAC107036,5600045,5600046},
{ 79,0xAC107037,5600055,5600056},
{ 79,0xAC107038,5600065,5600066},
{ 79,0xAC107039,5600075,5600076},
{ 79,0xAC10703A,5600085,5600086},
{ 79,0xAC10703B,5600095,5600096},
{ 79,0xAC10703C,5600105,5600106},
{ 79,0xAC10703D,5600116,5600117},
{ 79,0xAC10703E,5600126,5600127},
{ 79,0xAC10703F,5600136,5600137},
{ 79,0xAC107040,5600146,5600147},
{ 79,0xAC107041,5600156,5600157},
{ 79,0xAC107042,5600166,5600167},
{ 79,0xAC107043,5600176,5600177},
{ 79,0xAC107044,5600186,5600187},
{ 79,0xAC107045,5600196,5600197},
{ 79,0xAC107046,5600206,5600207},
{ 79,0xAC107047,5600216,5600217},
{ 79,0xAC107048,5600226,5600227},
{ 79,0xAC107049,5600236,5600237},
{ 79,0xAC10704A,5600246,5600247},
{ 79,0xAC10704B,5600256,5600257},
{ 79,0xAC10704C,5600266,5600267},
{ 79,0xAC10704D,5600276,5600277},
{ 79,0xAC10704E,5600286,5600287},
{ 79,0xAC10704F,5600296,5600297},
{ 79,0xAC107050,5600306,5600307},
{ 79,0xAC107051,5600316,5600317},
{ 79,0xAC107052,5600326,5600327},
{ 79,0xAC107053,5600336,5600337},
{ 79,0xAC107054,5600346,5600347},
{ 79,0xAC107055,5600356,5600357},
{ 79,0xAC107056,5600366,5600367},
{ 79,0xAC107057,5600376,5600377},
{ 79,0xAC107058,5600386,5600387},
{ 79,0xAC107059,5600396,5600397},
{ 79,0xAC10705A,5600406,5600407},
{ 79,0xAC10705B,5600416,5600417},
{ 79,0xAC10705C,5600426,5600427},
{ 79,0xAC10705D,5600437,5600438},
{ 79,0xAC10705E,5600447,5600448},
{ 79,0xAC10705F,5600457,5600458},
{ 79,0xAC107060,5600467,5600468},
{ 79,0xAC107061,5600477,5600478},
{ 79,0xAC107062,5600487,5600488},
{ 79,0xAC107063,5600497,5600498},
{ 79,0xAC107064,5600507,5600508},
{ 79,0xAC107065,5600517,5600518},
{ 79,0xAC107066,5600527,5600528},
{ 79,0xAC107067,5600537,5600538},
{ 79,0xAC107068,5600547,5600548},
{ 79,0xAC107069,5600557,5600558},
{ 79,0xAC10706A,5600567,5600568},
{ 79,0xAC10706B,5600577,5600578},
{ 79,0xAC10706C,5600587,5600588},
{ 79,0xAC10706D,5600597,5600598},
{ 79,0xAC10706E,5600607,5600608},
{ 79,0xAC10706F,5600617,5600618},
{ 79,0xAC107070,5600627,5600628},
{ 79,0xAC107071,5600637,5600638},
{ 79,0xAC107072,5600647,5600648},
{ 79,0xAC107073,5600657,5600658},
{ 79,0xAC107074,5600667,5600668},
{ 79,0xAC107075,5600677,5600678},
{ 79,0xAC107076,5600687,5600688},
{ 79,0xAC107077,5600697,5600698},
{ 79,0xAC107078,5600707,5600708},
{ 79,0xAC107079,5600717,5600718},
{ 79,0xAC10707A,5600727,5600728},
{ 79,0xAC10707B,5600737,5600738},
{ 79,0xAC10707C,5600747,5600748},
{ 79,0xAC10707D,5600757,5600758},
{ 79,0xAC10707E,5600767,5600768},
{ 79,0xAC10707F,5600777,5600778},
{ 79,0xAC107080,5600788,5600789},
{ 79,0xAC107081,5600798,5600799},
{ 79,0xAC107082,5600808,5600809},
{ 79,0xAC107083,5600818,5600819},
{ 79,0xAC107084,5600828,5600829},
{ 79,0xAC107085,5600838,5600839},
{ 79,0xAC107086,5600848,5600849},
{ 79,0xAC107087,5600858,5600859},
{ 79,0xAC107088,5600868,5600869},
{ 79,0xAC107089,5600878,5600879},
{ 79,0xAC10708A,5600888,5600889},
{ 79,0xAC10708B,5600898,5600899},
{ 79,0xAC10708C,5600908,5600909},
{ 79,0xAC10708D,5600918,5600919},
{ 79,0xAC10708E,5600928,5600929},
{ 79,0xAC10708F,5600938,5600939},
{ 79,0xAC107090,5600948,5600949},
{ 79,0xAC107091,5600958,5600959},
{ 79,0xAC107092,5600968,5600969},
{ 79,0xAC107093,5600978,5600979},
{ 79,0xAC107094,5600988,5600989},
{ 79,0xAC107095,5600998,5600999},
{ 79,0xAC107096,5601008,5601009},
{ 79,0xAC107097,5601018,5601019},
{ 79,0xAC107098,5601028,5601029},
{ 79,0xAC107099,5601038,5601039},
{ 79,0xAC10709A,5601048,5601049},
{ 79,0xAC10709B,5601058,5601059},
{ 79,0xAC10709C,5601068,5601069},
{ 79,0xAC10709D,5601078,5601079},
{ 79,0xAC10709E,5601088,5601089},
{ 79,0xAC10709F,5601098,5601099},
{ 79,0xAC1070A0,5601108,5601109},
{ 79,0xAC1070A1,5601119,5601120},
{ 79,0xAC1070A2,5601129,5601130},
{ 79,0xAC1070A3,5601139,5601140},
{ 79,0xAC1070A4,5601149,5601150},
{ 79,0xAC1070A5,5601159,5601160},
{ 79,0xAC1070A6,5601169,5601170},
{ 79,0xAC1070A7,5601179,5601180},
{ 79,0xAC1070A8,5601189,5601190},
{ 79,0xAC1070A9,5601199,5601200},
{ 79,0xAC1070AA,5601209,5601210},
{ 79,0xAC1070AB,5601219,5601220},
{ 79,0xAC1070AC,5601229,5601230},
{ 79,0xAC1070AD,5601239,5601240},
{ 79,0xAC1070AE,5601249,5601250},
{ 79,0xAC1070AF,5601259,5601260},
{ 79,0xAC1070B0,5601269,5601270},
{ 79,0xAC1070B1,5601279,5601280},
{ 79,0xAC1070B2,5601289,5601290},
{ 79,0xAC1070B3,5601299,5601300},
{ 79,0xAC1070B4,5601309,5601310},
{ 79,0xAC1070B5,5601319,5601320},
{ 79,0xAC1070B6,5601329,5601330},
{ 79,0xAC1070B7,5601339,5601340},
{ 79,0xAC1070B8,5601349,5601350},
{ 79,0xAC1070B9,5601359,5601360},
{ 79,0xAC1070BA,5601369,5601370},
{ 79,0xAC1070BB,5601379,5601380},
{ 79,0xAC1070BC,5601389,5601390},
{ 79,0xAC1070BD,5601399,5601400},
{ 79,0xAC1070BE,5601409,5601410},
{ 79,0xAC1070BF,5601419,5601420},
{ 79,0xAC1070C0,5601429,5601430},
{ 79,0xAC1070C1,5601439,5601440},
{ 79,0xAC1070C2,5601449,5601450},
{ 79,0xAC1070C3,5601459,5601460},
{ 79,0xAC1070C4,5601470,5601471},
{ 79,0xAC1070C5,5601480,5601481},
{ 79,0xAC1070C6,5601490,5601491},
{ 79,0xAC1070C7,5601500,5601501},
{ 79,0xAC1070C8,5601510,5601511},
{ 79,0xAC1070C9,5601520,5601521},
{ 79,0xAC1070CA,5601530,5601531},
{ 79,0xAC1070CB,5601540,5601541},
{ 79,0xAC1070CC,5601550,5601551},
{ 79,0xAC1070CD,5601560,5601561},
{ 79,0xAC1070CE,5601570,5601571},
{ 79,0xAC1070CF,5601580,5601581},
{ 79,0xAC1070D0,5601590,5601591},
{ 79,0xAC1070D1,5601600,5601601},
{ 79,0xAC1070D2,5601610,5601611},
{ 79,0xAC1070D3,5601620,5601621},
{ 79,0xAC1070D4,5601630,5601631},
{ 79,0xAC1070D5,5601640,5601641},
{ 79,0xAC1070D6,5601650,5601651},
{ 79,0xAC1070D7,5601660,5601661},
{ 79,0xAC1070D8,5601670,5601671},
{ 79,0xAC1070D9,5601680,5601681},
{ 79,0xAC1070DA,5601690,5601691},
{ 79,0xAC1070DB,5601700,5601701},
{ 79,0xAC1070DC,5601710,5601711},
{ 79,0xAC1070DD,5601720,5601721},
{ 79,0xAC1070DE,5601730,5601731},
{ 79,0xAC1070DF,5601740,5601741},
{ 79,0xAC1070E0,5601750,5601751},
{ 79,0xAC1070E1,5601760,5601761},
{ 79,0xAC1070E2,5601770,5601771},
{ 79,0xAC1070E3,5601780,5601781},
{ 79,0xAC1070E4,5601790,5601791},
{ 79,0xAC1070E5,5601800,5601801},
{ 79,0xAC1070E6,5601810,5601811},
{ 79,0xAC1070E7,5601821,5601822},
{ 79,0xAC1070E8,5601831,5601832},
{ 79,0xAC1070E9,5601841,5601842},
{ 79,0xAC1070EA,5601851,5601852},
{ 79,0xAC1070EB,5601861,5601862},
{ 79,0xAC1070EC,5601871,5601872},
{ 79,0xAC1070ED,5601881,5601882},
{ 79,0xAC1070EE,5601891,5601892},
{ 79,0xAC1070EF,5601901,5601902},
{ 79,0xAC1070F0,5601911,5601912},
{ 79,0xAC1070F1,5601921,5601922},
{ 79,0xAC1070F2,5601931,5601932},
{ 79,0xAC1070F3,5601941,5601942},
{ 79,0xAC1070F4,5601951,5601952},
{ 79,0xAC1070F5,5601961,5601962},
{ 79,0xAC1070F6,5601971,5601972},
{ 79,0xAC1070F7,5601981,5601982},
{ 79,0xAC1070F8,5601991,5601992},
{ 79,0xAC1070F9,5602001,5602002},
{ 79,0xAC1070FA,5602011,5602012},
{ 79,0xAC1070FB,5602021,5602022},
{ 79,0xAC1070FC,5602031,5602032},
{ 79,0xAC1070FD,5602041,5602042},
{ 79,0xAC1070FE,5602051,5602052},
{ 80,0xAC107032,5603640,5603760},
{ 81,0xAC107032,5819992,5820002},
{ 82,0xC0A80101,5820197,5820430},
{ 83,0xAC107232,5820513,5820518},
{ 84,0xAC107032,5821156,5821197},
{ 85,0xAC107032,5823180,5823300},
{ 86,0xAC107032,5823791,5824014},
{ 87,0xAC107232,5826562,5827619},
{ 88,0xAC107650,5828294,5828494},
{ 89,0xAC107064,5831127,5832120},
{ 90,0xAC107132,5832194,5832869},
{ 91,0xAC107032,5832678,5833426},
{ 92,0xAC107232,5836692,5836693},
{ 93,0xAC107064,5837414,5837431},
{ 93,0xAC107064,5837632,5838291},
{ 94,0xAC107232,5839543,5840147},
{ 95,0xAC107132,5840550,5840551},
{ 96,0xAC107232,5841979,5841989},
{ 97,0xAC107101,5842816,5842817},
{ 97,0xAC107103,5843046,5843047},
{ 97,0xAC107105,5843276,5843277},
{ 97,0xAC107104,5843506,5843507},
{ 97,0xAC107132,5843736,5843737},
{ 98,0xAC107232,5848337,5849332},
{ 99,0xAC107032,5851150,5852051},
{100,0xAC107032,5853844,5854255},
{101,0xAC107064,5855771,5856678},
{102,0xAC107014,5857041,5857042},
{103,0xAC1073EA,5860081,5861082},
{104,0xAC107100,5860827,5861727},
{104,0xAC107000,5860827,5861727},
{105,0xAC107032,5861832,5862015},
{106,0xAC107232,5863573,5863662},
{106,0xAC107646,5863595,5863642},
{107,0xAC107032,5904675,5905325},
{108,0xAC107232,5905934,5906835},
{109,0xAC107064,5907197,5907204},
{109,0xAC1071CC,5907201,5907204},
{109,0xAC107064,5907206,5908242},
{109,0xAC107064,5909595,5910175},
{110,0xAC107032,5908741,5908813},
{111,0xAC107032,5910313,5910496},
{112,0xAC1070C2,5911638,5911674},
{112,0xAC1070C2,5913376,5914081},
{113,0xAC107032,5912356,5912367},
{113,0xAC1072CF,5912359,5912360},
{113,0xAC107032,5913168,5913200},
{114,0xAC107232,5916681,5917919},
{115,0xAC107032,5916009,5917425},
{115,0xAC107032,5921940,5922060},
{116,0xAC107232,5917084,5917905},
{116,0xC0A8010A,5917722,5917723},
{117,0xAC107032,5918792,5919002},
{118,0xAC107032,5921714,5922706},
{119,0xAC107132,5922360,5922390},
{120,0xAC107064,5923691,5925038},
{120,0xAC107064,5925490,5926230},
{121,0xAC107064,5925003,5925908},
{122,0xAC107064,5927186,5927197},
{122,0xAC107064,5927651,5927958},
{123,0xAC107032,5926436,5926437},
{124,0xAC1072CF,5927057,5927944},
{125,0xAC107032,5934255,5934288},
{125,0xAC107032,5935215,5937855},
{126,0xAC107132,5936060,5936111},
{127,0xC0A80101,5940965,5941171},
{128,0xAC107064,5950623,5951616},
{129,0xAC107294,5951754,5951781},
{129,0xAC107064,5951784,5951811},
{129,0xAC10760A,5951814,5951841},
{129,0xAC107614,5951844,5951871},
{129,0xAC10761E,5951874,5951901},
{129,0xAC107628,5951904,5951931},
{129,0xAC107632,5951934,5951961},
{129,0xAC10763C,5951964,5951991},
{129,0xAC107646,5951995,5952022},
{129,0xAC107650,5952025,5952052},
{129,0xAC10765A,5952055,5952082},
{129,0xAC107014,5952085,5952112},
{129,0xAC1072A9,5952115,5952142},
{129,0xAC1070CF,5952145,5952172},
{129,0xAC107154,5952175,5952202},
{129,0xAC100001,5952205,5952232},
{129,0xAC1070C2,5952235,5952262},
{129,0xAC1073EA,5952265,5952292},
{129,0xAC107305,5952295,5952322},
{129,0xAC107357,5952325,5952352},
{129,0xAC1074C2,5952355,5952383},
{129,0xAC1074C9,5952386,5952413},
{129,0xAC10742C,5952416,5952443},
{129,0xAC10700A,5952446,5952473},
{129,0xAC107584,5952476,5952503},
{129,0xAC107534,5952506,5952533},
{129,0xAC1072A8,5952536,5952563},
{129,0xAC10756F,5952566,5952593},
{129,0xAC107567,5952596,5952623},
{129,0xAC1070C8,5952626,5952653},
{129,0xAC107169,5952656,5952683},
{129,0xAC1071CC,5952686,5952713},
{129,0xAC107095,5952716,5952743},
{129,0xAC1072CF,5952747,5952774},
{129,0xAC107664,5952777,5952804},
{129,0xAC107132,5952807,5952834},
{129,0xAC107232,5952837,5952864},
{129,0xAC107032,5952867,5952894},
{129,0xAC107232,5952897,5952924},
{130,0xAC107232,5953502,5953590},
{130,0xAC107614,5953524,5953570},
{131,0xAC107100,5981438,5981439},
{132,0xAC107032,6066259,6066501},
{133,0xAC107032,5993162,5993187},
{134,0xAC107232,5993896,5993897},
{135,0xAC107032,5996640,5997540},
{136,0xAC107064,5997033,5997038},
{136,0xAC107064,6005025,6005101},
{137,0xAC107232,5999172,5999176},
{138,0xAC107064,6003338,6003427},
{139,0xAC107232,6003136,6003379},
{139,0xAC107232,6003519,6003641},
{139,0xAC107232,6003780,6003781},
{139,0xAC107232,6003920,6003921},
{140,0xAC107232,6007030,6007602},
{141,0xAC1070CF,6010397,6011043},
{142,0xAC107032,6010824,6010825},
{142,0xAC107032,6011005,6011006},
{142,0xAC107032,6011205,6011206},
{142,0xAC107032,6011405,6011406},
{142,0xAC107032,6011605,6011606},
{142,0xAC107032,6011789,6011790},
{142,0xAC107032,6011973,6011974},
{143,0xAC100001,6014975,6015080},
{144,0xAC107132,6015676,6017541},
{145,0xAC107232,6017175,6017284},
{146,0xAC107032,6019159,6043859},
{146,0xAC107032,6018859,6018860},
{147,0xAC107232,6023597,6024116},
{148,0xAC107032,6033079,6033187},
{149,0xAC107032,6078780,6078960},
{150,0xAC107232,6080468,6080473},
{150,0xAC107232,6082293,6082374},
{151,0xAC107064,6081380,6081458},
{151,0xAC107095,6081438,6081454},
{151,0xAC107064,6081472,6082055},
{151,0xAC107064,6088469,6088807},
{152,0xAC107064,6085260,6086160},
{153,0xAC107032,6086051,6086052},
{153,0xAC107032,6086222,6086223},
{153,0xAC107032,6086394,6086395},
{154,0xAC107064,6089197,6090166},
{155,0xAC107064,6090725,6091056},
{155,0xAC107064,6091460,6091664},
{156,0xAC107064,6091021,6091924},
{157,0xAC107032,6091590,6091801},
{158,0xAC107032,6094637,6094774},
{158,0xAC107032,6095514,6097047},
{159,0xAC107232,6101909,6102041},
{160,0xAC107232,6105198,6106099},
{161,0xAC107064,6105795,6106206},
{161,0xAC107064,6106808,6107111},
{162,0xAC107000,6109279,6109341},
{163,0xAC107001,6110170,6110171},
{163,0xAC107002,6110180,6110181},
{163,0xAC107003,6110190,6110191},
{163,0xAC107004,6110200,6110201},
{163,0xAC107005,6110210,6110211},
{163,0xAC107006,6110220,6110221},
{163,0xAC107007,6110230,6110231},
{163,0xAC107008,6110240,6110241},
{163,0xAC107009,6110250,6110251},
{163,0xAC10700A,6110260,6110261},
{164,0xAC100001,6112212,6112518},
{165,0xAC107064,6114660,6115631},
{166,0xAC107014,6116911,6116912},
{167,0xAC107032,6118874,6118915},
{168,0xAC107000,6119910,6142681},
{168,0xAC107100,6119910,6142681},
{168,0xAC107200,6119910,6142681},
{168,0xAC107300,6119910,6142681},
{168,0xAC107400,6119910,6142681},
{168,0xAC107500,6119910,6142681},
{168,0xAC107600,6119910,6142681},
{169,0xAC107064,6130274,6130595},
{169,0xAC107064,6130796,6131955},
{170,0xAC107032,6163288,6163317},
{171,0xAC107132,6163717,6163796},
{172,0xAC107064,6164057,6165002},
{173,0xAC107000,6164781,6165854},
{173,0xAC107100,6164781,6165854},
{173,0xAC107200,6164781,6165854},
{173,0xAC107300,6164781,6165854},
{173,0xAC107400,6164781,6165854},
{173,0xAC107500,6164781,6165854},
{173,0xAC107600,6164781,6165854},
{174,0xAC107232,6165856,6165965},
{175,0xAC107000,6166426,6167984},
{175,0xAC107100,6166426,6167984},
{175,0xAC107200,6166426,6167984},
{175,0xAC107300,6166426,6167984},
{175,0xAC107400,6166426,6167984},
{175,0xAC107500,6166426,6167984},
{175,0xAC107600,6166426,6167984},
{176,0xAC107064,6166651,6166652},
{176,0xAC107064,6177788,6177892},
{177,0xAC1070CF,6167777,6168109},
{178,0xAC107032,6168671,6168672},
{178,0xAC107032,6168871,6168872},
{178,0xAC107032,6169071,6169072},
{179,0xAC107064,6173100,6173333},
{180,0xAC107032,6170893,6170945},
{181,0xAC107064,6171600,6171900},
{182,0xAC107232,6172500,6172800},
{183,0xAC107064,6174626,6174631},
{184,0xAC107132,6177130,6177474},
{185,0xAC1070C2,6179655,6179717},
{186,0xAC107064,6180278,6181340},
{187,0xAC107064,6180672,6181604},
{188,0xAC107064,6181091,6181694},
{189,0xAC107064,6181110,6182013},
{190,0xAC107032,6185175,6186076},
{191,0xAC107032,6185848,6185873},
{191,0xAC107032,6186077,6186106},
{192,0xAC107132,6186747,6187648},
{193,0xAC107032,6188190,6189091},
{194,0xAC107232,6197235,6197246},
{195,0xAC107169,6198435,6198465},
{195,0xAC107169,6199005,6200695},
{196,0xAC107132,6201004,6201013},
{197,0xAC107232,6202034,6204183},
{198,0xAC107032,6202329,6202370},
{199,0xAC100001,6207620,6207621},
{199,0xAC100001,6207801,6207802},
{199,0xAC100001,6207982,6207983},
{199,0xAC100001,6208163,6208164},
{199,0xAC100001,6208344,6208345},
{199,0xAC100001,6208525,6208526},
{199,0xAC100001,6208706,6208707},
{200,0xAC107064,6209357,6210475},
{200,0xAC107064,6211378,6211984},
{201,0xAC107032,6206730,6207330},
{202,0xAC107064,3398461,3398462},
{203,0xAC107132,3401415,3401416},
{204,0xAC107232,3404356,3404357},
{205,0xAC107032,3413358,3413359},
{206,0xAC107032,3427035,3427036},
{207,0xAC107232,3432433,3432434},
{208,0xAC107032,3438557,3438558},
{209,0xAC107232,3487457,3487458},
{210,0xAC107032,3491031,3491032},
{211,0xAC107232,3492403,3492404},
{212,0xAC107132,3495259,3495260},
{213,0xAC107032,3498553,3498554},
{214,0xAC107032,3507916,3507917},
{215,0xAC107000,3503110,3503111},
{216,0xAC107232,3514275,3514276},
{217,0xAC107032,3521177,3521178},
{218,0xAC107232,3585733,3585734},
{219,0xAC107032,3591858,3591859},
{220,0xAC107232,3597918,3597919},
{221,0xAC107000,3615430,3615431},
{222,0xAC107032,3626580,3626581},
{223,0xAC107064,3628574,3628575},
{224,0xAC107064,3657857,3657858},
{225,0xAC107232,3663197,3663198},
{226,0xAC107232,3667811,3667812},
{227,0xAC1072CF,3668656,3668657},
{228,0xAC107232,3675433,3675434},
{229,0xAC107232,3680717,3680718},
{230,0xAC107032,3685635,3685636},
{231,0xAC107000,3688570,3688571},
{232,0xAC107032,3698178,3698179},
{233,0xAC107232,3744437,3744438},
{234,0xAC107232,3744640,3744641},
{235,0xAC107032,3745006,3745007},
{236,0xAC107154,3748695,3748696},
{237,0xAC107232,3756015,3756016},
{238,0xAC107064,3760812,3760813},
{239,0xAC107132,3762737,3762738},
{240,0xAC107232,3765977,3765978},
{241,0xAC107032,3767058,3767059},
{242,0xAC107032,3770656,3770657},
{243,0xAC107032,3777190,3777191},
{244,0xAC107032,3778998,3778999}
};

// Host table, generated by hosts2eval.pl from the hosts file
static const struct Hosts {
  U32 ip;  // Address
  const char* hostname;
} hosts[]={
{0xAC100C0A,"plato.eyrie.af.mil"},
{0xAC10700A,"locke.eyrie.af.mil"},
{0xAC107014,"hobbes.eyrie.af.mil"},
{0xAC107032,"pascal.eyrie.af.mil"},
{0xAC107032,"pascal"},
{0xAC107064,"hume.eyrie.af.mil"},
{0xAC107064,"hume"},
{0xAC107095,"eagle.eyrie.af.mil"},
{0xAC1070C2,"falcon.eyrie.af.mil"},
{0xAC1070CF,"robin.eyrie.af.mil"},
{0xAC107132,"zeno.eyrie.af.mil"},
{0xAC107132,"zeno"},
{0xAC107154,"duck.eyrie.af.mil"},
{0xAC107169,"swallow.eyrie.af.mil"},
{0xAC1071CC,"goose.eyrie.af.mil"},
{0xAC107232,"marx.eyrie.af.mil"},
{0xAC107232,"marx"},
{0xAC107294,"crow.eyrie.af.mil"},
{0xAC1072A8,"finch.eyrie.af.mil"},
{0xAC1072A8,"finch.eyrie.af.edu"},
{0xAC1072A9,"swan.eyrie.af.mil"},
{0xAC1072CF,"pigeon.eyrie.af.mil"},
{0xAC107305,"pc1.eyrie.af.mil"},
{0xAC107357,"pc2.eyrie.af.mil"},
{0xAC1073EA,"pc0.eyrie.af.mil"},
{0xAC10742C,"pc5.eyrie.af.mil"},
{0xAC1074C2,"pc3.eyrie.af.mil"},
{0xAC1074C9,"pc4.eyrie.af.mil"},
{0xAC107534,"pc7.eyrie.af.mil"},
{0xAC107567,"pc9.eyrie.af.mil"},
{0xAC10756F,"pc8.eyrie.af.mil"},
{0xAC107584,"pc6.eyrie.af.mil"},
{0xAC10760A,"linux1.eyrie.af.mil"},
{0xAC107614,"linux2.eyrie.af.mil"},
{0xAC10761E,"linux3.eyrie.af.mil"},
{0xAC107628,"linux4.eyrie.af.mil"},
{0xAC107632,"linux5.eyrie.af.mil"},
{0xAC10763C,"linux6.eyrie.af.mil"},
{0xAC107646,"linux7.eyrie.af.mil"},
{0xAC107650,"linux8.eyrie.af.mil"},
{0xAC10765A,"linux9.eyrie.af.mil"},
{0xAC107664,"linux10.eyrie.af.mil"},
{0x870DD8BF,"alpha.apple.edu"},
{0x87083CB6,"beta.banana.edu"},
{0xC21BFB15,"gamma.grape.mil"},
{0xC207F899,"delta.peach.mil"},
{0xC373DA6C,"epsilon.pear.com"},
{0xC3499732,"lambda.orange.com"},
{0xC4254B9E,"jupiter.cherry.org"},
{0xC4E321BD,"saturn.kiwi.org"},
{0xC5B65BE9,"mars.avocado.net"},
{0xC5DAB145,"pluto.plum.net"},
{0xC0A8011E,"monitor.af.mil"},
{0xC0A8010A,"calvin.world.net"},
{0xC0A80114,"aesop.world.net"},
{0xC0A8015A,"solomon.world.net"},
{0xC0A80101,"loud.world.net"},
{0xC0A80102,"None."}
};

map<string, U32> hostmap;  // Fast hostname lookup, returns ip

// Print ID, attack name, flags
void Attack::print() const {

  // Meaning of flag bits 0-23 in Attack
  static const char* flaglabels[]={
    "In", "Man", "Con", "", "FS", "OT", "IT",
    "BSM", "LOG", "DIR", "Stl", "New",
    "Probe", "DOS", "R2L", "U2R", "Data",
    "pascal", "hume", "zeno", "marx",
    "W45", "W2", "Poor"};

  // Print attack name and flag names
  printf("%-25s", name);
  for (int i=sizeof(flaglabels)/sizeof(const char*)-1; i>=0; --i)
    if ((flags>>i)&1)
      printf(" %s", flaglabels[i]);
  printf("\n");
}

// Exception for input errors
class ParseError {
  string msg;
public:
  ParseError(const string& s): msg(s) {}
  ParseError() {}
  string what() const {return msg;}
};

// Read a line of input from f into s, return false at EOF
bool readline(string& s, FILE* f=stdin) {
  s="";
  int c;
  while ((c=getc(f))!=EOF && c!='\n')
    if (c!='\r')
      s+=char(c);
  return c!=EOF || s!="";
}

// Remove first word of s (ending in delim or white space) and return it.
// Trim leading and trailing delim and white space.
string getword(string& s, char delim=' ') {
  if (s.empty()) throw ParseError("end of line");
  string w;
  string::iterator b, e;
  for (b=s.begin(); b!=s.end() && (*b<=' ' || *b==delim); ++b)
    ;  // Find begin of word
  for (e=b; e!=s.end() && *e!=delim && *e>' '; ++e)
    ; // Find end of word
  w=string(b, e);
  s=string(min(e+1, s.end()), s.end());
  return w;
}

// An alarm.  Information is as input
struct Alarm {
  U32 time;  // Seconds since 00:00, Feb 28 1999
  U32 ip;  // Target
  double score;  // Confidence level
  string comments;  // Remainder of the input line
  int fa;  // Number of higher scoring false alarms, -1 = error
  Alarm(): time(0), ip(0), score(0), fa(0) {}
  bool read(FILE* f=stdin);  // Read data, return false at EOF
  void print() const;
};

// Print alarm in readable format compatible with eval3, eval4.
// fa is printed in the unused ID field.
void Alarm::print() const {
  const int sec=time%60;
  const int min=(time/60)%60;
  const int hour=(time/3600)%24;
  const int day=(time/86400)%31;
  const int month=time/(31*24*60*60)+2;
  const int ip3=ip>>24;
  const int ip2=(ip>>16)&255;
  const int ip1=(ip>>8)&255;
  const int ip0=ip&255;
  printf(
    "%8d %02d/%02d/1999 %02d:%02d:%02d %03d.%03d.%03d.%03d %8.6f #%s\n",
    fa, month, day, hour, min, sec, ip3, ip2, ip1, ip0, score,
    comments.c_str());
}

// For sorting alarms by descending score
bool operator < (const Alarm& a, const Alarm& b) {
  return a.score > b.score;
}

// Read an alarm in the form " id m/d/y h:m:s a.a.a.a score commments "
// Return true unless EOF.  Set fa = -1 if input error, else 0.
bool Alarm::read(FILE* f) {
  fa=-1;
  string s;
  if (!readline(s, f))
    return false;
  string msg=s;
  try {
    getword(s);  // Discard ID
    time=31*24*60*60*(atoi(getword(s, '/').c_str())-2);  // Month
    time+=24*60*60*atoi(getword(s, '/').c_str());  // Day
    getword(s);  // Discard year
    time+=60*60*atoi(getword(s, ':').c_str());  // Hour
    time+=60*atoi(getword(s, ':').c_str());  // Minute
    time+=atoi(getword(s).c_str());  // Second
    if (time<86400*31 || time>86400*73) throw ParseError("time");// 3/1-4/10?
    string target=getword(s);  // Host name or IP address
    if (target.size()>0 && isdigit(target[0])) {
      ip=256*256*256*atoi(getword(target, '.').c_str());
      ip+=256*256*atoi(getword(target, '.').c_str());
      ip+=256*atoi(getword(target, '.').c_str());
      ip+=atoi(getword(target, '.').c_str());
    }
    else
      ip=hostmap[target];
    if (ip==0) throw ParseError("host");
    score=atof(getword(s).c_str());
    if (score<=0) throw ParseError("score");
    comments=s;
    fa=0;
  }
  catch (ParseError x) {
    printf("Ignored: %s: %s\n", x.what().c_str(), msg.c_str());
  }
  return true;
}

// eval filename v_option fa_option
int main (int argc, char** argv) {

  // Check arguments, print help message if none
  if (argc==1) {
    printf(
    "eval 12/15/03 (C) Matt Mahoney, 2003.  mmahoney@cs.fit.edu\n"
    "Distributed under the GNU GPL, http://www.gnu.org/licenses/gpl.txt\n"
    "\n"
    "eval evaluates intrusion detection output files for the 1999 Lincoln\n"
    "Labs/DARPA IDS evaluation data set, http://www.ll.mit.edu/IST/ideval/\n"
    "Input files are one alarm per line with an id number (ignored), date,\n"
    "time, target IP address or hostname, score (a decimal number) and\n"
    "optional comments after a #, e.g.\n"
    "\n"
    "  123 4/08/1999 08:00:26 192.168.1.30 0.570244 # maybe a portscan\n"
    "\n"
    "Usage: eval file [v [fa]] (e.g. eval phad.sim 2 100)\n"
    "\n"
    "If file is -, read from standard input: phad 1123200 in[3-5]* |eval -\n"
    "v is verbosity, 0 to 4, higher numbers give more output, default is 2.\n"
    "fa is the number of false alarms to stop after, default is 100.\n"
    "\n"
    "Notes: IT, OT, BSM, NT, FS, LOG, DIR = evidence in inside sniffer\n"
    "traffic, outside traffic, BSM, NT audit logs (LOG + hume), file\n"
    "system dumps, audit logs, or directory listings.\n"
    "In = insider attack, Con = console, Man = manual (not scripted),\n"
    "New = not in week 2, Stl = stealty. Probe, DOS, R2L, U2R, Data = category.\n"
    "pascal (Solaris), hume (NT), zeno (SunOS), marx (Linux) = target(s).\n"
    "W2, W45 = week 2, weeks 4-5.  Detailed counts are for W45 only.\n");
    return 1;
  }

  // Open input file, use stdin if "-"
  FILE* f=stdin;
  if (argv[1][0]!='-' || argv[1][1]!=0) {
    f=fopen(argv[1], "r");
    if (!f) {
      perror(argv[1]);
      return 1;
    }
  }

  // Get options
  const int v_option=argc>2 ? atoi(argv[2]) : 2;    // Verbosity
  const int fa_option=argc>3 ? atoi(argv[3]) : 100; // Max false alarms

  // Initialize hostmap to look up IP address by hostname
  for (int i=0; i<int(sizeof(hosts)/sizeof(Hosts)); ++i)
    hostmap[hosts[i].hostname]=hosts[i].ip;

  // Initialize flags 17-20 in attack[] for pascal, hume, zeno, marx.
  // The bit is set if this is one of the targets
  // Set flags 21 for weeks 4-5, 22 for week 2
  for (int i=0; i<int(sizeof(aseg)/sizeof(AttackSegment)); ++i) {
    if (aseg[i].ip==0xAC107032) attack[aseg[i].id].flags|=0x20000;  // pascal
    if (aseg[i].ip==0xAC107064) attack[aseg[i].id].flags|=0x40000;  // hume
    if (aseg[i].ip==0xAC107132) attack[aseg[i].id].flags|=0x80000;  // zeno
    if (aseg[i].ip==0xAC107232) attack[aseg[i].id].flags|=0x100000; // marx
    if (aseg[i].start>4000000)  attack[aseg[i].id].flags|=0x200000; // wk 4-5
    else                        attack[aseg[i].id].flags|=0x400000; // week 2
  }

  // Read alarms and sort by score
  vector<Alarm> alarms;  // List of valid alarms sorted by descending score
  Alarm a;
  while (a.read(f))
    if (a.fa==0)  // No read error?
      alarms.push_back(a);
  stable_sort(alarms.begin(), alarms.end());

  // det[i] is a list of indices (1-201) of alarms that detect attack[i]
  vector<vector<int> > det(sizeof(attack)/sizeof(Attack));

  // sorted_det[i].first, second is the attack index (1-201) and number of
  // false alarms preceding the i'th highest scoring detection
  vector<pair<int, int> > sorted_det;

  // detmap[s] is a list of highest scoring alarms indices detecting s,
  // e.g. the 16 alarms detecting the 16 "portsweep" instances.
  map<string, vector<int> > detmap;

  // True, false alarm count
  int tp=0, fa=0;

  // Attach alarms to attacks, print false alarms up to fa_option+1
  if (v_option>=4)
    printf(
      "\nTop %d false alarms (number, date, time, target, score, #comments)\n"
      "------------------------------------------------------------------\n",
      fa_option);
  for (int i=0; i<int(alarms.size()); ++i) {
    Alarm& a=alarms[i];
    a.fa=fa;

    // Test all attack segments
    bool detected=false;  // true if a match is found
    for (int j=0; j<int(sizeof(aseg)/sizeof(AttackSegment)); ++j) {
      const AttackSegment& as=aseg[j];
      if ((a.ip==as.ip || ((as.ip&255)==0 && a.ip/256==as.ip/256))
          && a.time>=as.start-60 && a.time<=as.finish+60) {
        detected=true;
        if (as.id<det.size()) {
          det[as.id].push_back(i);
          if (det[as.id].size()==1) {
            sorted_det.push_back(make_pair(int(as.id), fa));
            detmap[attack[as.id].name+10].push_back(i);
          }
        }
        else {  // Should never be here
          fprintf(stderr, "Oops, as.id=%ld\n", as.id);
          exit(1);
        }
      }
    }

    // Count true/false alarms, break if done
    if (detected)
      ++tp;
    else {
      if (v_option>=4)
        a.print();
      if (++fa>fa_option)
        break;
    }
  }

  // List all detections for each attack
  if (v_option>=4) {
    printf("\n"
    "Detections listed by attack (preceding FAs, date, time, target, score)\n"
    "---------------------------------------------------------------------\n");
    for (int i=1; i<int(det.size()); ++i) {
      attack[i].print();
      for (int j=0; j<int(det[i].size()) && j<10; ++j) {
        alarms[det[i][j]].print();
      }
      if (int(det[i].size())>=10)
        printf("%8d detections\n", int(det[i].size()));
    }
  }

  // List attacks detected sorted by number of preceding false alarms
  if (v_option>=3) {
    printf("\n n    FA  Attacks detected after FA false alarms\n"
             "---  ---- --------------------------------------\n");
    for (int i=0; i<int(sorted_det.size()); ++i) {
      printf("%3d %5d ", i+1, sorted_det[i].second);
      attack[sorted_det[i].first].print();
    }
  }

  // List detection comments for each attack type
  if (v_option>=2) {
    printf("\n"
           "Attack            FA (false alarms before detected)\n"
           "------           ----\n");
    for (map<string, vector<int> >::iterator p=detmap.begin();
        p!=detmap.end(); ++p) {
      for (int i=0; i<int(p->second.size()); ++i)
        printf("%-15s %5d %s\n", p->first.c_str(), alarms[p->second[i]].fa,
            alarms[p->second[i]].comments.c_str());
    }
  }

  // List a table of detected/total attacks for common specs
  if (v_option>=1) {
    const int cols=8, rows=12;
    U32 colmask[cols]={0,0x1000,0x2000,0x4000,0x8000,0x10000,0x800,0x400};
    U32 rowmask[rows]=
      {0x200000,0x200040,0x200020,0x200080,0x240100,0x200010,
       0x220000,0x240000,0x280000,0x300000,0x800000,0x400000};
    const char* rownames[rows]=
      {"W45","IT","OT","BSM","NT","FS",
       "pascal","hume","zeno","marx","Poor","W2"};
    printf("\n"
    "Detections/Total at %d false alarms (weeks 4-5 only except row W2)\n"
    "\n"
    "         All    Probe    DOS     R2L     U2R    Data     New   Stealthy\n"
    "       ------- ------- ------- ------- ------- ------- ------- --------\n",
    fa_option);
    for (int i=0; i<rows; ++i) {
      printf("%-6s", rownames[i]);
      for (int j=0; j<cols; ++j) {
        int dets=0, all=0;  // Detects dets/all at 20-500 FA
        for (int k=1; k<int(det.size()); ++k) {
          U32 mask=rowmask[i]|colmask[j];
          if ((attack[k].flags&mask)==mask) {
            ++all;
            if (!det[k].empty() && alarms[det[k][0]].fa<=fa_option)
              ++dets;
          }
        }
        printf(" %3d/%-3d", dets, all);
      }
      printf("\n");
    }

    // Print alarm summary
    printf(
      "\n%d detections, %d alarms, %d true, %d false, %d not evaluated.\n",
      int(sorted_det.size()), int(alarms.size()), tp, fa,
      int(alarms.size()-tp-fa));
  }
  return 0;
}