1
0

tree.c 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570
  1. /* $Id: tree.c 767 2004-10-06 12:48:49Z aturner $ */
  2. /*
  3. * Copyright (c) 2001-2004 Aaron Turner.
  4. * All rights reserved.
  5. *
  6. * Redistribution and use in source and binary forms, with or without
  7. * modification, are permitted provided that the following conditions
  8. * are met:
  9. *
  10. * 1. Redistributions of source code must retain the above copyright
  11. * notice, this list of conditions and the following disclaimer.
  12. * 2. Redistributions in binary form must reproduce the above copyright
  13. * notice, this list of conditions and the following disclaimer in the
  14. * documentation and/or other materials provided with the distribution.
  15. * 3. Neither the names of the copyright owners nor the names of its
  16. * contributors may be used to endorse or promote products derived from
  17. * this software without specific prior written permission.
  18. *
  19. * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
  20. * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  21. * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  22. * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  23. * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24. * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
  25. * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  26. * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
  27. * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  28. * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  29. * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30. */
  31. #include "config.h"
  32. #include <libnet.h>
  33. #include <stdio.h>
  34. #include <stdlib.h>
  35. #include "tcpreplay.h"
  36. #include "cidr.h"
  37. #include "tree.h"
  38. #include "err.h"
  39. extern struct data_tree treeroot;
  40. extern double ratio;
  41. #ifdef DEBUG
  42. extern int debug;
  43. #endif
  44. extern int min_mask, max_mask;
  45. extern CIDR *cidrdata;
  46. int checkincidr;
  47. static struct tree_type *new_tree();
  48. static struct tree_type *packet2tree(const u_char *);
  49. static void tree_print(struct data_tree *);
  50. static void tree_printnode(const char *, const struct tree_type *);
  51. static void tree_buildcidr(struct data_tree *, BUILDCIDR *);
  52. static void tree_checkincidr(struct data_tree *, BUILDCIDR *);
  53. RB_PROTOTYPE(data_tree, tree_type, node, tree_comp)
  54. RB_GENERATE(data_tree, tree_type, node, tree_comp)
  55. /*
  56. * used with rbwalk to walk a tree and generate CIDR * cidrdata.
  57. * is smart enough to prevent dupes. void * arg is cast to bulidcidr_type
  58. */
  59. void
  60. tree_buildcidr(struct data_tree *treeroot, BUILDCIDR * bcdata)
  61. {
  62. struct tree_type *node = NULL;
  63. CIDR *newcidr = NULL;
  64. unsigned long network = 0;
  65. unsigned long mask = ~0; /* turn on all bits */
  66. RB_FOREACH(node, data_tree, treeroot) {
  67. /* we only check types that are vaild */
  68. if (bcdata->type != ANY) /* don't check if we're adding ANY */
  69. if (bcdata->type != node->type) /* no match, exit early */
  70. return;
  71. /*
  72. * in cases of leaves and last visit add to cidrdata if
  73. * necessary
  74. */
  75. if (!check_ip_CIDR(cidrdata, node->ip)) { /* if we exist, abort */
  76. newcidr = new_cidr();
  77. newcidr->masklen = bcdata->masklen;
  78. network = node->ip & (mask >> (32 - bcdata->masklen));
  79. newcidr->network = network;
  80. add_cidr(cidrdata, &newcidr);
  81. }
  82. }
  83. }
  84. /*
  85. * uses rbwalk to check to see if a given ip address of a given type in the
  86. * tree is inside any of the cidrdata
  87. *
  88. * since this is void, we return via the global int checkincidr
  89. */
  90. void
  91. tree_checkincidr(struct data_tree *treeroot, BUILDCIDR * bcdata)
  92. {
  93. struct tree_type *node = NULL;
  94. RB_FOREACH(node, data_tree, treeroot) {
  95. /* we only check types that are vaild */
  96. if (bcdata->type != ANY) /* don't check if we're adding ANY */
  97. if (bcdata->type != node->type) /* no match, exit early */
  98. return;
  99. /*
  100. * in cases of leaves and last visit add to cidrdata if
  101. * necessary
  102. */
  103. if (check_ip_CIDR(cidrdata, node->ip)) { /* if we exist, abort */
  104. checkincidr = 1;
  105. }
  106. }
  107. }
  108. /*
  109. * processes the tree using rbwalk / tree2cidr to generate a CIDR
  110. * used for 2nd pass, router mode
  111. *
  112. * returns > 0 for success (the mask len), 0 for fail
  113. */
  114. int
  115. process_tree()
  116. {
  117. int mymask = 0;
  118. BUILDCIDR *bcdata;
  119. if ((bcdata = (BUILDCIDR *) malloc(sizeof(BUILDCIDR))) == NULL)
  120. err(1, "malloc");
  121. for (mymask = max_mask; mymask <= min_mask; mymask++) {
  122. dbg(1, "Current mask: %u", mymask);
  123. /* set starting vals */
  124. bcdata->type = SERVER;
  125. bcdata->masklen = mymask;
  126. /* build cidrdata with servers */
  127. tree_buildcidr(&treeroot, bcdata);
  128. /* calculate types of all IP's */
  129. tree_calculate(&treeroot);
  130. /* try to find clients in cidrdata */
  131. checkincidr = 0;
  132. bcdata->type = CLIENT;
  133. tree_checkincidr(&treeroot, bcdata);
  134. if (checkincidr == 0) { /* didn't find any clients in cidrdata */
  135. return (mymask); /* success! */
  136. }
  137. else {
  138. destroy_cidr(cidrdata); /* clean up after our mess */
  139. cidrdata = NULL;
  140. }
  141. }
  142. /* we failed to find a vaild cidr list */
  143. return (0);
  144. }
  145. /*
  146. * processes rbdata to bulid cidrdata based upon the
  147. * given type (SERVER, CLIENT, UNKNOWN) using the given masklen
  148. *
  149. * is smart enough to prevent dupes
  150. */
  151. void
  152. tree_to_cidr(const int masklen, const int type)
  153. {
  154. }
  155. /*
  156. * Checks to see if an IP is client or server by finding it in the tree
  157. * returns SERVER or CLIENT.
  158. * if mode = UNKNOWN, then abort on unknowns
  159. * if mode = CLIENT, then unknowns become clients
  160. * if mode = SERVER, then unknowns become servers
  161. */
  162. int
  163. check_ip_tree(const int mode, const unsigned long ip)
  164. {
  165. struct tree_type *node = NULL, *finder = NULL;
  166. finder = new_tree();
  167. finder->ip = ip;
  168. node = RB_FIND(data_tree, &treeroot, finder);
  169. if (node == NULL && mode == UNKNOWN)
  170. errx(1, "%s (%lu) is an unknown system... aborting.!\n"
  171. "Try a different auto mode (-n router|client|server)",
  172. libnet_addr2name4(ip, RESOLVE), ip);
  173. #ifdef DEBUG
  174. if (node->type == SERVER) {
  175. dbg(1, "Server: %s", libnet_addr2name4(ip, RESOLVE));
  176. }
  177. else if (node->type == CLIENT) {
  178. dbg(1, "Client: %s", libnet_addr2name4(ip, RESOLVE));
  179. }
  180. else {
  181. dbg(1, "Unknown: %s", libnet_addr2name4(ip, RESOLVE));
  182. }
  183. #endif
  184. /* return node type if we found the node, else return the default (mode) */
  185. if (node != NULL) {
  186. return (node->type);
  187. }
  188. else {
  189. return mode;
  190. }
  191. }
  192. /*
  193. * adds an entry to the tree (phase 1 of auto mode)
  194. */
  195. void
  196. add_tree(const unsigned long ip, const u_char * data)
  197. {
  198. struct tree_type *node = NULL, *newnode = NULL;
  199. newnode = packet2tree(data);
  200. if (newnode->type == UNKNOWN) {
  201. /* couldn't figure out if packet was client or server */
  202. dbg(2, "%s (%lu) unknown client/server",
  203. libnet_addr2name4(newnode->ip, RESOLVE), newnode->ip);
  204. }
  205. /* try to find a simular entry in the tree */
  206. node = RB_FIND(data_tree, &treeroot, newnode);
  207. #ifdef DEBUG
  208. if (debug > 2)
  209. tree_printnode("add_tree", node);
  210. #endif
  211. /* new entry required */
  212. if (node == NULL) {
  213. /* increment counters */
  214. if (newnode->type == SERVER) {
  215. newnode->server_cnt++;
  216. }
  217. else if (newnode->type == CLIENT) {
  218. newnode->client_cnt++;
  219. }
  220. /* insert it in */
  221. RB_INSERT(data_tree, &treeroot, newnode);
  222. }
  223. else {
  224. /* we found something, so update it */
  225. dbg(2, " node: %p\nnewnode: %p", node, newnode);
  226. #ifdef DEBUG
  227. if (debug > 2)
  228. tree_printnode("update node", node);
  229. #endif
  230. /* increment counter */
  231. if (newnode->type == SERVER) {
  232. node->server_cnt++;
  233. }
  234. else if (newnode->type == CLIENT) {
  235. /* temp debug code */
  236. node->client_cnt++;
  237. }
  238. /* didn't insert it, so free it */
  239. free(newnode);
  240. }
  241. dbg(2, "------- START NEXT -------");
  242. #ifdef DEBUG
  243. if (debug > 2)
  244. tree_print(&treeroot);
  245. #endif
  246. }
  247. /*
  248. * calculates wether an IP is a client, server, or unknown for each node in the tree
  249. */
  250. void
  251. tree_calculate(struct data_tree *treeroot)
  252. {
  253. struct tree_type *node;
  254. RB_FOREACH(node, data_tree, treeroot) {
  255. if ((node->server_cnt > 0) || (node->client_cnt > 0)) {
  256. /* type based on: server >= (client*ratio) */
  257. if ((double)node->server_cnt >= (double)node->client_cnt * ratio) {
  258. node->type = SERVER;
  259. }
  260. else {
  261. node->type = CLIENT;
  262. }
  263. }
  264. else { /* IP had no client or server connections */
  265. node->type = UNKNOWN;
  266. }
  267. }
  268. }
  269. /*
  270. * tree_comp(), called by rbsearch compares two treees and returns:
  271. * 1 = first > second
  272. * -1 = first < second
  273. * 0 = first = second
  274. * based upon the ip address stored
  275. *
  276. */
  277. int
  278. tree_comp(struct tree_type *t1, struct tree_type *t2)
  279. {
  280. if (t1->ip > t2->ip) {
  281. dbg(2, "%s > %s", libnet_addr2name4(t1->ip, RESOLVE),
  282. libnet_addr2name4(t2->ip, RESOLVE));
  283. return 1;
  284. }
  285. if (t1->ip < t2->ip) {
  286. dbg(2, "%s < %s", libnet_addr2name4(t1->ip, RESOLVE),
  287. libnet_addr2name4(t2->ip, RESOLVE));
  288. return -1;
  289. }
  290. dbg(2, "%s = %s", libnet_addr2name4(t1->ip, RESOLVE),
  291. libnet_addr2name4(t2->ip, RESOLVE));
  292. return 0;
  293. }
  294. /*
  295. * creates a new TREE * with reasonable defaults
  296. */
  297. static struct tree_type *
  298. new_tree()
  299. {
  300. struct tree_type *node;
  301. node = (struct tree_type *)malloc(sizeof(struct tree_type));
  302. if (node == NULL)
  303. err(1, "malloc");
  304. memset(node, '\0', sizeof(struct tree_type));
  305. node->server_cnt = 0;
  306. node->client_cnt = 0;
  307. node->type = UNKNOWN;
  308. node->masklen = -1;
  309. node->ip = 0;
  310. return (node);
  311. }
  312. /*
  313. * returns a struct of TREE * from a packet header
  314. * and sets the type to be SERVER or CLIENT or UNKNOWN
  315. * if it's an undefined packet, we return -1 for the type
  316. * the u_char * data should be the data that is passed by pcap_dispatch()
  317. */
  318. struct tree_type *
  319. packet2tree(const u_char * data)
  320. {
  321. struct tree_type *node = NULL;
  322. eth_hdr_t *eth_hdr = NULL;
  323. ip_hdr_t ip_hdr;
  324. tcp_hdr_t tcp_hdr;
  325. udp_hdr_t udp_hdr;
  326. icmp_hdr_t icmp_hdr;
  327. dns_hdr_t dns_hdr;
  328. node = new_tree();
  329. eth_hdr = (eth_hdr_t *) (data);
  330. /* prevent issues with byte alignment, must memcpy */
  331. memcpy(&ip_hdr, (data + LIBNET_ETH_H), LIBNET_IP_H);
  332. /* copy over the source mac */
  333. strncpy((char *)node->mac, (char *)eth_hdr->ether_shost, 6);
  334. /* copy over the source ip */
  335. node->ip = ip_hdr.ip_src.s_addr;
  336. /*
  337. * TCP
  338. */
  339. if (ip_hdr.ip_p == IPPROTO_TCP) {
  340. dbg(1, "%s uses TCP... ",
  341. libnet_addr2name4(ip_hdr.ip_src.s_addr, RESOLVE));
  342. /* memcpy it over to prevent alignment issues */
  343. memcpy(&tcp_hdr, (data + LIBNET_ETH_H + (ip_hdr.ip_hl * 4)),
  344. LIBNET_TCP_H);
  345. /* ftp-data is going to skew our results so we ignore it */
  346. if (tcp_hdr.th_sport == 20) {
  347. return (node);
  348. }
  349. /* set TREE->type based on TCP flags */
  350. if (tcp_hdr.th_flags == TH_SYN) {
  351. node->type = CLIENT;
  352. dbg(1, "is a client");
  353. }
  354. else if (tcp_hdr.th_flags == (TH_SYN | TH_ACK)) {
  355. node->type = SERVER;
  356. dbg(1, "is a server");
  357. }
  358. else {
  359. dbg(1, "is an unknown");
  360. }
  361. /*
  362. * UDP
  363. */
  364. }
  365. else if (ip_hdr.ip_p == IPPROTO_UDP) {
  366. /* memcpy over to prevent alignment issues */
  367. memcpy(&udp_hdr, (data + LIBNET_ETH_H + (ip_hdr.ip_hl * 4)),
  368. LIBNET_UDP_H);
  369. dbg(1, "%s uses UDP... ",
  370. libnet_addr2name4(ip_hdr.ip_src.s_addr, RESOLVE));
  371. switch (ntohs(udp_hdr.uh_dport)) {
  372. case 0x0035: /* dns */
  373. /* prevent memory alignment issues */
  374. memcpy(&dns_hdr,
  375. (data + LIBNET_ETH_H + (ip_hdr.ip_hl * 4) + LIBNET_UDP_H),
  376. LIBNET_DNS_H);
  377. if (dns_hdr.flags & DNS_QUERY_FLAG) {
  378. /* bit set, response */
  379. node->type = SERVER;
  380. dbg(1, "is a dns server");
  381. }
  382. else {
  383. /* bit not set, query */
  384. node->type = CLIENT;
  385. dbg(1, "is a dns client");
  386. }
  387. return (node);
  388. break;
  389. default:
  390. break;
  391. }
  392. switch (ntohs(udp_hdr.uh_sport)) {
  393. case 0x0035: /* dns */
  394. /* prevent memory alignment issues */
  395. memcpy(&dns_hdr,
  396. (data + LIBNET_ETH_H + (ip_hdr.ip_hl * 4) + LIBNET_UDP_H),
  397. LIBNET_DNS_H);
  398. if (dns_hdr.flags & DNS_QUERY_FLAG) {
  399. /* bit set, response */
  400. node->type = SERVER;
  401. dbg(1, "is a dns server");
  402. }
  403. else {
  404. /* bit not set, query */
  405. node->type = CLIENT;
  406. dbg(1, "is a dns client");
  407. }
  408. return (node);
  409. break;
  410. default:
  411. dbg(1, "unknown UDP protocol: %hu->%hu", udp_hdr.uh_sport,
  412. udp_hdr.uh_dport);
  413. break;
  414. }
  415. /*
  416. * ICMP
  417. */
  418. }
  419. else if (ip_hdr.ip_p == IPPROTO_ICMP) {
  420. /* prevent alignment issues */
  421. memcpy(&icmp_hdr, (data + LIBNET_ETH_H + (ip_hdr.ip_hl * 4)),
  422. LIBNET_ICMP_H);
  423. dbg(1, "%s uses ICMP... ",
  424. libnet_addr2name4(ip_hdr.ip_src.s_addr, RESOLVE));
  425. /*
  426. * if port unreachable, then source == server, dst == client
  427. */
  428. if ((icmp_hdr.icmp_type == ICMP_UNREACH) &&
  429. (icmp_hdr.icmp_code == ICMP_UNREACH_PORT)) {
  430. node->type = SERVER;
  431. dbg(1, "is a server with a closed port");
  432. }
  433. }
  434. return (node);
  435. }
  436. /*
  437. * prints out a node of the tree to stderr
  438. */
  439. static void
  440. tree_printnode(const char *name, const struct tree_type *node)
  441. {
  442. if (node == NULL) {
  443. fprintf(stderr, "%s node is null\n", name);
  444. }
  445. else {
  446. fprintf(stderr, "-- %s: %p\nIP: %s\nMask: %d\nSrvr: %d\nClnt: %d\n",
  447. name, (void *)node, libnet_addr2name4(node->ip, RESOLVE),
  448. node->masklen, node->server_cnt, node->client_cnt);
  449. if (node->type == SERVER) {
  450. fprintf(stderr, "Type: Server\n--\n");
  451. }
  452. else {
  453. fprintf(stderr, "Type: Client\n--\n");
  454. }
  455. }
  456. }
  457. /*
  458. * prints out the entire tree
  459. */
  460. static void
  461. tree_print(struct data_tree *treeroot)
  462. {
  463. struct tree_type *node = NULL;
  464. RB_FOREACH(node, data_tree, treeroot) {
  465. tree_printnode("my node", node);
  466. }
  467. return;
  468. }