tree.c 27 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975
  1. /* $Id$ */
  2. /*
  3. * Copyright (c) 2001-2010 Aaron Turner <aturner at synfin dot net>
  4. * Copyright (c) 2013-2018 Fred Klassen <tcpreplay at appneta dot com> - AppNeta
  5. *
  6. * The Tcpreplay Suite of tools is free software: you can redistribute it
  7. * and/or modify it under the terms of the GNU General Public License as
  8. * published by the Free Software Foundation, either version 3 of the
  9. * License, or with the authors permission any later version.
  10. *
  11. * The Tcpreplay Suite is distributed in the hope that it will be useful,
  12. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  14. * GNU General Public License for more details.
  15. *
  16. * You should have received a copy of the GNU General Public License
  17. * along with the Tcpreplay Suite. If not, see <http://www.gnu.org/licenses/>.
  18. */
  19. #include "config.h"
  20. #include "defines.h"
  21. #include "common.h"
  22. #include <stdio.h>
  23. #include <stdlib.h>
  24. #include <string.h>
  25. #include "tree.h"
  26. #include "tcpprep.h"
  27. #include "tcpprep_opts.h"
  28. #include "tcpprep_api.h"
  29. extern tcpr_data_tree_t treeroot;
  30. extern tcpprep_t *tcpprep;
  31. #ifdef DEBUG
  32. extern int debug;
  33. #endif
  34. /* static buffer used by tree_print*() functions */
  35. char tree_print_buff[TREEPRINTBUFFLEN];
  36. static tcpr_tree_t *new_tree();
  37. static tcpr_tree_t *packet2tree(const u_char *, const int);
  38. #ifdef DEBUG /* prevent compile warnings */
  39. static char *tree_print(tcpr_data_tree_t *);
  40. static char *tree_printnode(const char *, const tcpr_tree_t *);
  41. #endif /* DEBUG */
  42. static void tree_buildcidr(tcpr_data_tree_t *, tcpr_buildcidr_t *);
  43. static int tree_checkincidr(tcpr_data_tree_t *, tcpr_buildcidr_t *);
  44. static int ipv6_cmp(const struct tcpr_in6_addr *a, const struct tcpr_in6_addr *b);
  45. RB_PROTOTYPE(tcpr_data_tree_s, tcpr_tree_s, node, tree_comp)
  46. RB_GENERATE(tcpr_data_tree_s, tcpr_tree_s, node, tree_comp)
  47. /**
  48. * used with rbwalk to walk a tree and generate cidr_t * cidrdata.
  49. * is smart enough to prevent dupes. void * arg is cast to bulidcidr_t
  50. */
  51. void
  52. tree_buildcidr(tcpr_data_tree_t *treeroot, tcpr_buildcidr_t * bcdata)
  53. {
  54. tcpr_tree_t *node = NULL;
  55. tcpr_cidr_t *newcidr = NULL;
  56. unsigned long network = 0;
  57. struct tcpr_in6_addr network6;
  58. unsigned long mask = ~0; /* turn on all bits */
  59. tcpprep_opt_t *options = tcpprep->options;
  60. uint32_t i, j, k;
  61. dbg(1, "Running: tree_buildcidr()");
  62. RB_FOREACH(node, tcpr_data_tree_s, treeroot) {
  63. /* we only check types that are valid */
  64. if (bcdata->type != DIR_ANY) /* don't check if we're adding ANY */
  65. if (bcdata->type != node->type) /* no match, exit early */
  66. return;
  67. /*
  68. * in cases of leaves and last visit add to cidrdata if
  69. * necessary. First check IPv4
  70. */
  71. dbgx(4, "Checking if %s exists in cidrdata...", get_addr2name4(node->u.ip, RESOLVE));
  72. if (node->family == AF_INET) {
  73. if (! check_ip_cidr(options->cidrdata, node->u.ip)) { /* if we exist, abort */
  74. dbgx(3, "Node %s doesn't exist... creating.",
  75. get_addr2name4(node->u.ip, RESOLVE));
  76. newcidr = new_cidr();
  77. newcidr->masklen = bcdata->masklen;
  78. network = node->u.ip & (mask << (32 - bcdata->masklen));
  79. dbgx(3, "Using network: %s", get_addr2name4(network, RESOLVE));
  80. newcidr->u.network = network;
  81. add_cidr(&options->cidrdata, &newcidr);
  82. }
  83. }
  84. /* Check IPv6 Address */
  85. else if (node->family == AF_INET6) {
  86. if (! check_ip6_cidr(options->cidrdata, &node->u.ip6)) { /* if we exist, abort */
  87. dbgx(3, "Node %s doesn't exist... creating.",
  88. get_addr2name6(&node->u.ip6, RESOLVE));
  89. newcidr = new_cidr();
  90. newcidr->masklen = bcdata->masklen;
  91. /* init each 4 quads to zero */
  92. for (i = 0; i < 4; i++)
  93. network6.tcpr_s6_addr32[i] = 0;
  94. /* Build our mask */
  95. j = bcdata->masklen / 8;
  96. for (i = 0; i < j; i++)
  97. network6.tcpr_s6_addr[i] = node->u.ip6.tcpr_s6_addr[i];
  98. if ((k = bcdata->masklen % 8) != 0) {
  99. k = (uint32_t)~0 << (8 - k);
  100. network6.tcpr_s6_addr[j] = node->u.ip6.tcpr_s6_addr[i] & k;
  101. }
  102. dbgx(3, "Using network: %s", get_addr2name6(&network6, RESOLVE));
  103. newcidr->u.network6 = network6;
  104. add_cidr(&options->cidrdata, &newcidr);
  105. }
  106. }
  107. }
  108. }
  109. /**
  110. * uses rbwalk to check to see if a given ip address of a given type in the
  111. * tree is inside any of the cidrdata
  112. */
  113. static int
  114. tree_checkincidr(tcpr_data_tree_t *treeroot, tcpr_buildcidr_t * bcdata)
  115. {
  116. tcpr_tree_t *node = NULL;
  117. tcpprep_opt_t *options = tcpprep->options;
  118. RB_FOREACH(node, tcpr_data_tree_s, treeroot) {
  119. /* we only check types that are valid */
  120. if (bcdata->type != DIR_ANY) /* don't check if we're adding ANY */
  121. if (bcdata->type != node->type) /* no match, exit early */
  122. return 0;
  123. /*
  124. * in cases of leaves and last visit add to cidrdata if
  125. * necessary
  126. */
  127. if (node->family == AF_INET && check_ip_cidr(options->cidrdata, node->u.ip)) /* if we exist, abort */
  128. return 1;
  129. if (node->family == AF_INET6 && check_ip6_cidr(options->cidrdata, &node->u.ip6))
  130. return 1;
  131. }
  132. return 0;
  133. }
  134. /**
  135. * processes the tree using rbwalk / tree2cidr to generate a CIDR
  136. * used for 2nd pass, router mode
  137. *
  138. * returns > 0 for success (the mask len), 0 for fail
  139. */
  140. int
  141. process_tree(void)
  142. {
  143. int mymask = 0;
  144. tcpr_buildcidr_t *bcdata;
  145. tcpprep_opt_t *options = tcpprep->options;
  146. dbg(1, "Running: process_tree()");
  147. bcdata = (tcpr_buildcidr_t *)safe_malloc(sizeof(tcpr_buildcidr_t));
  148. for (mymask = options->max_mask; mymask <= options->min_mask; mymask++) {
  149. dbgx(1, "Current mask: %u", mymask);
  150. /* set starting vals */
  151. bcdata->type = DIR_SERVER;
  152. bcdata->masklen = mymask;
  153. /* build cidrdata with servers */
  154. tree_buildcidr(&treeroot, bcdata);
  155. /* calculate types of all IP's */
  156. tree_calculate(&treeroot);
  157. /* try to find clients in cidrdata */
  158. bcdata->type = DIR_CLIENT;
  159. if (! tree_checkincidr(&treeroot, bcdata)) { /* didn't find any clients in cidrdata */
  160. safe_free(bcdata);
  161. return (mymask); /* success! */
  162. }
  163. else {
  164. destroy_cidr(options->cidrdata); /* clean up after our mess */
  165. options->cidrdata = NULL;
  166. }
  167. }
  168. safe_free(bcdata);
  169. /* we failed to find a valid cidr list */
  170. notice("Unable to determine any IP addresses as a clients.");
  171. notice("Perhaps you should change the --ratio, --minmask/maxmask settings, or try another mode?");
  172. return (0);
  173. }
  174. /*
  175. * processes rbdata to build cidrdata based upon the
  176. * given type (SERVER, CLIENT, UNKNOWN) using the given masklen
  177. *
  178. * is smart enough to prevent dupes
  179. void
  180. tcpr_tree_to_cidr(const int masklen, const int type)
  181. {
  182. }
  183. */
  184. /**
  185. * Checks to see if an IP is client or server by finding it in the tree
  186. * returns TCPR_DIR_C2S or TCPR_DIR_S2C or -1 on error
  187. * if mode = UNKNOWN, then abort on unknowns
  188. * if mode = CLIENT, then unknowns become clients
  189. * if mode = SERVER, then unknowns become servers
  190. */
  191. tcpr_dir_t
  192. check_ip_tree(const int mode, const unsigned long ip)
  193. {
  194. tcpr_tree_t *node, *finder;
  195. finder = new_tree();
  196. finder->family = AF_INET;
  197. finder->u.ip = ip;
  198. node = RB_FIND(tcpr_data_tree_s, &treeroot, finder);
  199. if (node == NULL && mode == DIR_UNKNOWN)
  200. errx(-1, "%s (%lu) is an unknown system... aborting.!\n"
  201. "Try a different auto mode (-n router|client|server)",
  202. get_addr2name4(ip, RESOLVE), ip);
  203. /* return node type if we found the node, else return the default (mode) */
  204. if (node != NULL) {
  205. #ifdef DEBUG
  206. switch (node->type) {
  207. case DIR_SERVER:
  208. dbgx(1, "DIR_SERVER: %s", get_addr2name4(ip, RESOLVE));
  209. break;
  210. case DIR_CLIENT:
  211. dbgx(1, "DIR_CLIENT: %s", get_addr2name4(ip, RESOLVE));
  212. break;
  213. case DIR_UNKNOWN:
  214. dbgx(1, "DIR_UNKNOWN: %s", get_addr2name4(ip, RESOLVE));
  215. break;
  216. case DIR_ANY:
  217. dbgx(1, "DIR_ANY: %s", get_addr2name4(ip, RESOLVE));
  218. break;
  219. }
  220. #endif
  221. switch (node->type) {
  222. case DIR_SERVER:
  223. safe_free(finder);
  224. return TCPR_DIR_S2C;
  225. break;
  226. case DIR_CLIENT:
  227. safe_free(finder);
  228. return TCPR_DIR_C2S;
  229. break;
  230. case DIR_UNKNOWN:
  231. case DIR_ANY:
  232. /* use our current mode to determine return code */
  233. goto return_unknown;
  234. default:
  235. errx(-1, "Node for %s has invalid type: %d", get_addr2name4(ip, RESOLVE), node->type);
  236. }
  237. }
  238. return_unknown:
  239. safe_free(finder);
  240. switch (mode) {
  241. case DIR_SERVER:
  242. return TCPR_DIR_S2C;
  243. break;
  244. case DIR_CLIENT:
  245. return TCPR_DIR_C2S;
  246. break;
  247. default:
  248. return -1;
  249. }
  250. }
  251. tcpr_dir_t
  252. check_ip6_tree(const int mode, const struct tcpr_in6_addr *addr)
  253. {
  254. tcpr_tree_t *node, *finder;
  255. finder = new_tree();
  256. finder->family = AF_INET6;
  257. finder->u.ip6 = *addr;
  258. node = RB_FIND(tcpr_data_tree_s, &treeroot, finder);
  259. if (node == NULL && mode == DIR_UNKNOWN)
  260. errx(-1, "%s is an unknown system... aborting.!\n"
  261. "Try a different auto mode (-n router|client|server)",
  262. get_addr2name6(addr, RESOLVE));
  263. /*
  264. * FIXME: Is this logic correct? I think this might be backwards :(
  265. */
  266. /* return node type if we found the node, else return the default (mode) */
  267. if (node != NULL) {
  268. #ifdef DEBUG
  269. switch (node->type) {
  270. case DIR_SERVER:
  271. dbgx(1, "DIR_SERVER: %s", get_addr2name6(addr, RESOLVE));
  272. break;
  273. case DIR_CLIENT:
  274. dbgx(1, "DIR_CLIENT: %s", get_addr2name6(addr, RESOLVE));
  275. break;
  276. case DIR_UNKNOWN:
  277. dbgx(1, "DIR_UNKNOWN: %s", get_addr2name6(addr, RESOLVE));
  278. break;
  279. case DIR_ANY:
  280. dbgx(1, "DIR_ANY: %s", get_addr2name6(addr, RESOLVE));
  281. break;
  282. }
  283. #endif
  284. switch (node->type) {
  285. case DIR_SERVER:
  286. return TCPR_DIR_C2S;
  287. break;
  288. case DIR_CLIENT:
  289. return TCPR_DIR_S2C;
  290. break;
  291. case DIR_UNKNOWN:
  292. case DIR_ANY:
  293. /* use our current mode to determine return code */
  294. goto return_unknown;
  295. default:
  296. errx(-1, "Node for %s has invalid type: %d", get_addr2name6(addr, RESOLVE), node->type);
  297. }
  298. }
  299. return_unknown:
  300. safe_free(finder);
  301. switch (mode) {
  302. case DIR_SERVER:
  303. return TCPR_DIR_C2S;
  304. break;
  305. case DIR_CLIENT:
  306. return TCPR_DIR_S2C;
  307. break;
  308. default:
  309. return -1;
  310. }
  311. }
  312. /**
  313. * Parses the IP header of the given packet (data) to get the SRC/DST IP
  314. * addresses. If the SRC IP doesn't exist in the TREE, we add it as a
  315. * client, if the DST IP doesn't exist in the TREE, we add it as a server
  316. */
  317. void
  318. add_tree_first_ipv4(const u_char *data, const int len)
  319. {
  320. tcpr_tree_t *newnode, *findnode;
  321. ipv4_hdr_t ip_hdr;
  322. assert(data);
  323. if (len < (TCPR_ETH_H + TCPR_IPV4_H)) {
  324. errx(-1, "Capture length %d too small for IPv4 parsing", len);
  325. return;
  326. }
  327. /*
  328. * first add/find the source IP/client
  329. */
  330. newnode = new_tree();
  331. /* prevent issues with byte alignment, must memcpy */
  332. memcpy(&ip_hdr, (data + TCPR_ETH_H), TCPR_IPV4_H);
  333. /* copy over the source ip, and values to guarantee this a client */
  334. newnode->family = AF_INET;
  335. newnode->u.ip = ip_hdr.ip_src.s_addr;
  336. newnode->type = DIR_CLIENT;
  337. newnode->client_cnt = 1000;
  338. findnode = RB_FIND(tcpr_data_tree_s, &treeroot, newnode);
  339. /* if we didn't find it, add it to the tree, else free it */
  340. if (findnode == NULL) {
  341. RB_INSERT(tcpr_data_tree_s, &treeroot, newnode);
  342. } else {
  343. safe_free(newnode);
  344. }
  345. /*
  346. * now add/find the destination IP/server
  347. */
  348. newnode = new_tree();
  349. memcpy(&ip_hdr, (data + TCPR_ETH_H), TCPR_IPV4_H);
  350. newnode->family = AF_INET;
  351. newnode->u.ip = ip_hdr.ip_dst.s_addr;
  352. newnode->type = DIR_SERVER;
  353. newnode->server_cnt = 1000;
  354. findnode = RB_FIND(tcpr_data_tree_s, &treeroot, newnode);
  355. if (findnode == NULL) {
  356. RB_INSERT(tcpr_data_tree_s, &treeroot, newnode);
  357. } else {
  358. safe_free(newnode);
  359. }
  360. }
  361. void
  362. add_tree_first_ipv6(const u_char *data, const int len)
  363. {
  364. tcpr_tree_t *newnode, *findnode;
  365. ipv6_hdr_t ip6_hdr;
  366. assert(data);
  367. if (len < (TCPR_ETH_H + TCPR_IPV6_H)) {
  368. errx(-1, "Capture length %d too small for IPv6 parsing", len);
  369. return;
  370. }
  371. /*
  372. * first add/find the source IP/client
  373. */
  374. newnode = new_tree();
  375. /* prevent issues with byte alignment, must memcpy */
  376. memcpy(&ip6_hdr, (data + TCPR_ETH_H), TCPR_IPV6_H);
  377. /* copy over the source ip, and values to guarantee this a client */
  378. newnode->family = AF_INET6;
  379. newnode->u.ip6 = ip6_hdr.ip_src;
  380. newnode->type = DIR_CLIENT;
  381. newnode->client_cnt = 1000;
  382. findnode = RB_FIND(tcpr_data_tree_s, &treeroot, newnode);
  383. /* if we didn't find it, add it to the tree, else free it */
  384. if (findnode == NULL) {
  385. RB_INSERT(tcpr_data_tree_s, &treeroot, newnode);
  386. } else {
  387. safe_free(newnode);
  388. }
  389. /*
  390. * now add/find the destination IP/server
  391. */
  392. newnode = new_tree();
  393. memcpy(&ip6_hdr, (data + TCPR_ETH_H), TCPR_IPV6_H);
  394. newnode->family = AF_INET6;
  395. newnode->u.ip6 = ip6_hdr.ip_dst;
  396. newnode->type = DIR_SERVER;
  397. newnode->server_cnt = 1000;
  398. findnode = RB_FIND(tcpr_data_tree_s, &treeroot, newnode);
  399. if (findnode == NULL) {
  400. RB_INSERT(tcpr_data_tree_s, &treeroot, newnode);
  401. } else {
  402. safe_free(newnode);
  403. }
  404. }
  405. static void
  406. add_tree_node(tcpr_tree_t *newnode)
  407. {
  408. tcpr_tree_t *node;
  409. /* try to find a simular entry in the tree */
  410. node = RB_FIND(tcpr_data_tree_s, &treeroot, newnode);
  411. dbgx(3, "%s", tree_printnode("add_tree", node));
  412. /* new entry required */
  413. if (node == NULL) {
  414. /* increment counters */
  415. if (newnode->type == DIR_SERVER) {
  416. newnode->server_cnt++;
  417. }
  418. else if (newnode->type == DIR_CLIENT) {
  419. newnode->client_cnt++;
  420. }
  421. /* insert it in */
  422. RB_INSERT(tcpr_data_tree_s, &treeroot, newnode);
  423. }
  424. else {
  425. /* we found something, so update it */
  426. dbgx(2, " node: %p\nnewnode: %p", node, newnode);
  427. dbgx(3, "%s", tree_printnode("update node", node));
  428. /* increment counter */
  429. if (newnode->type == DIR_SERVER) {
  430. node->server_cnt++;
  431. }
  432. else if (newnode->type == DIR_CLIENT) {
  433. /* temp debug code */
  434. node->client_cnt++;
  435. }
  436. /* didn't insert it, so free it */
  437. safe_free(newnode);
  438. }
  439. dbg(2, "------- START NEXT -------");
  440. dbgx(3, "%s", tree_print(&treeroot));
  441. }
  442. /**
  443. * adds an entry to the tree (phase 1 of auto mode). We add each host
  444. * to the tree if it doesn't yet exist. We go through and track:
  445. * - number of times each host acts as a client or server
  446. * - the way the host acted the first time we saw it (client or server)
  447. */
  448. void
  449. add_tree_ipv4(const unsigned long ip, const u_char * data, const int len)
  450. {
  451. tcpr_tree_t *newnode;
  452. assert(data);
  453. newnode = packet2tree(data, len);
  454. if (newnode) {
  455. assert(ip == newnode->u.ip);
  456. if (newnode->type == DIR_UNKNOWN) {
  457. /* couldn't figure out if packet was client or server */
  458. dbgx(2, "%s (%lu) unknown client/server",
  459. get_addr2name4(newnode->u.ip, RESOLVE), newnode->u.ip);
  460. }
  461. add_tree_node(newnode);
  462. }
  463. }
  464. void
  465. add_tree_ipv6(const struct tcpr_in6_addr * addr, const u_char * data,
  466. const int len)
  467. {
  468. tcpr_tree_t *newnode;
  469. assert(data);
  470. newnode = packet2tree(data, len);
  471. if (newnode) {
  472. assert(ipv6_cmp(addr, &newnode->u.ip6) == 0);
  473. if (newnode->type == DIR_UNKNOWN) {
  474. /* couldn't figure out if packet was client or server */
  475. dbgx(2, "%s unknown client/server",
  476. get_addr2name6(&newnode->u.ip6, RESOLVE));
  477. }
  478. add_tree_node(newnode);
  479. }
  480. }
  481. /**
  482. * calculates whether each node in the tree is a client, server, or unknown for each node in the tree
  483. */
  484. void
  485. tree_calculate(tcpr_data_tree_t *treeroot)
  486. {
  487. tcpr_tree_t *node;
  488. tcpprep_opt_t *options = tcpprep->options;
  489. dbg(1, "Running tree_calculate()");
  490. RB_FOREACH(node, tcpr_data_tree_s, treeroot) {
  491. dbgx(4, "Processing %s", get_addr2name4(node->u.ip, RESOLVE));
  492. if ((node->server_cnt > 0) || (node->client_cnt > 0)) {
  493. /* type based on: server >= (client*ratio) */
  494. if ((double)node->server_cnt >= (double)node->client_cnt * options->ratio) {
  495. node->type = DIR_SERVER;
  496. dbgx(3, "Setting %s to server",
  497. get_addr2name4(node->u.ip, RESOLVE));
  498. }
  499. else {
  500. node->type = DIR_CLIENT;
  501. dbgx(3, "Setting %s to client",
  502. get_addr2name4(node->u.ip, RESOLVE));
  503. }
  504. }
  505. else { /* IP had no client or server connections */
  506. node->type = DIR_UNKNOWN;
  507. dbgx(3, "Setting %s to unknown",
  508. get_addr2name4(node->u.ip, RESOLVE));
  509. }
  510. }
  511. }
  512. static int
  513. ipv6_cmp(const struct tcpr_in6_addr *a, const struct tcpr_in6_addr *b)
  514. {
  515. int i;
  516. for (i = 0; i < 4; i++) {
  517. int k;
  518. if ((k = (a->tcpr_s6_addr32[i] - b->tcpr_s6_addr32[i]))) {
  519. return (k > 0) ? 1 : -1;
  520. }
  521. }
  522. return 0;
  523. }
  524. /**
  525. * tree_comp(), called by rbsearch compares two treees and returns:
  526. * 1 = first > second
  527. * -1 = first < second
  528. * 0 = first = second
  529. * based upon the ip address stored
  530. *
  531. */
  532. int
  533. tree_comp(tcpr_tree_t *t1, tcpr_tree_t *t2)
  534. {
  535. if (t1->family > t2->family) {
  536. dbgx(2, "family %d > %d", t1->family, t2->family);
  537. return 1;
  538. }
  539. if (t1->family < t2->family) {
  540. dbgx(2, "family %d < %d", t1->family, t2->family);
  541. return -1;
  542. }
  543. if (t1->family == AF_INET) {
  544. if (t1->u.ip > t2->u.ip) {
  545. dbgx(2, "%s > %s", get_addr2name4(t1->u.ip, RESOLVE),
  546. get_addr2name4(t2->u.ip, RESOLVE));
  547. return 1;
  548. }
  549. if (t1->u.ip < t2->u.ip) {
  550. dbgx(2, "%s < %s", get_addr2name4(t1->u.ip, RESOLVE),
  551. get_addr2name4(t2->u.ip, RESOLVE));
  552. return -1;
  553. }
  554. dbgx(2, "%s = %s", get_addr2name4(t1->u.ip, RESOLVE),
  555. get_addr2name4(t2->u.ip, RESOLVE));
  556. return 0;
  557. }
  558. if (t1->family == AF_INET6) {
  559. int ret = ipv6_cmp(&t1->u.ip6, &t1->u.ip6);
  560. dbgx(2, "cmp(%s, %s) = %d", get_addr2name6(&t1->u.ip6, RESOLVE),
  561. get_addr2name6(&t2->u.ip6, RESOLVE), ret);
  562. return ret;
  563. }
  564. return 0;
  565. }
  566. /**
  567. * creates a new TREE * with reasonable defaults
  568. */
  569. static tcpr_tree_t *
  570. new_tree()
  571. {
  572. tcpr_tree_t *node;
  573. node = (tcpr_tree_t *)safe_malloc(sizeof(tcpr_tree_t));
  574. memset(node, '\0', sizeof(tcpr_tree_t));
  575. node->server_cnt = 0;
  576. node->client_cnt = 0;
  577. node->type = DIR_UNKNOWN;
  578. node->masklen = -1;
  579. node->u.ip = 0;
  580. return (node);
  581. }
  582. /**
  583. * returns a struct of TREE * from a packet header
  584. * and sets the type to be SERVER or CLIENT or UNKNOWN
  585. * if it's an undefined packet, we return -1 for the type
  586. * the u_char * data should be the data that is passed by pcap_dispatch()
  587. */
  588. static tcpr_tree_t *
  589. packet2tree(const u_char * data, const int len)
  590. {
  591. tcpr_tree_t *node = NULL;
  592. eth_hdr_t *eth_hdr = NULL;
  593. ipv4_hdr_t ip_hdr;
  594. ipv6_hdr_t ip6_hdr;
  595. tcp_hdr_t tcp_hdr;
  596. udp_hdr_t udp_hdr;
  597. icmpv4_hdr_t icmp_hdr;
  598. dnsv4_hdr_t dnsv4_hdr;
  599. u_int16_t ether_type;
  600. u_char proto = 0;
  601. int hl = 0;
  602. #ifdef DEBUG
  603. char srcip[INET6_ADDRSTRLEN];
  604. #endif
  605. if (len < (int)sizeof(*eth_hdr)) {
  606. goto len_error;
  607. }
  608. node = new_tree();
  609. eth_hdr = (eth_hdr_t *) (data);
  610. /* prevent issues with byte alignment, must memcpy */
  611. memcpy(&ether_type, (u_char*)eth_hdr + 12, 2);
  612. /* drop VLAN info if it exists before the IP info */
  613. if (ether_type == htons(ETHERTYPE_VLAN)) {
  614. dbg(4,"Processing as VLAN traffic...");
  615. hl += 4;
  616. if (len < TCPR_ETH_H + hl) {
  617. goto len_error;
  618. }
  619. /* prevent issues with byte alignment, must memcpy */
  620. memcpy(&ether_type, (u_char*)eth_hdr + 16, 2);
  621. }
  622. if (ether_type == htons(ETHERTYPE_IP)) {
  623. if (len < (TCPR_ETH_H + hl + TCPR_IPV4_H)) {
  624. safe_free(node);
  625. errx(-1, "packet capture length %d too small for IPv4 processing",
  626. len);
  627. return NULL;
  628. }
  629. if (len < TCPR_ETH_H + TCPR_IPV4_H + hl) {
  630. goto len_error;
  631. }
  632. memcpy(&ip_hdr, (data + TCPR_ETH_H + hl), TCPR_IPV4_H);
  633. node->family = AF_INET;
  634. node->u.ip = ip_hdr.ip_src.s_addr;
  635. proto = ip_hdr.ip_p;
  636. hl += ip_hdr.ip_hl * 4;
  637. #ifdef DEBUG
  638. strlcpy(srcip, get_addr2name4(ip_hdr.ip_src.s_addr,
  639. RESOLVE), 16);
  640. #endif
  641. } else if (ether_type == htons(ETHERTYPE_IP6)) {
  642. if (len < (TCPR_ETH_H + hl + TCPR_IPV6_H)) {
  643. safe_free(node);
  644. errx(-1, "packet capture length %d too small for IPv6 processing",
  645. len);
  646. return NULL;
  647. }
  648. if (len < TCPR_ETH_H + TCPR_IPV6_H + hl) {
  649. goto len_error;
  650. }
  651. memcpy(&ip6_hdr, (data + TCPR_ETH_H + hl), TCPR_IPV6_H);
  652. node->family = AF_INET6;
  653. node->u.ip6 = ip6_hdr.ip_src;
  654. proto = ip6_hdr.ip_nh;
  655. hl += TCPR_IPV6_H;
  656. #ifdef DEBUG
  657. strlcpy(srcip, get_addr2name6(&ip6_hdr.ip_src, RESOLVE), INET6_ADDRSTRLEN);
  658. #endif
  659. } else {
  660. dbgx(2,"Unrecognized ether_type (%x)", ether_type);
  661. }
  662. /* copy over the source mac */
  663. memset(&node->mac[0], 0, sizeof(node->mac));
  664. strncpy((char *)node->mac, (char *)eth_hdr->ether_shost,
  665. sizeof(node->mac) - 1);
  666. /*
  667. * TCP
  668. */
  669. if (proto == IPPROTO_TCP) {
  670. dbgx(3, "%s uses TCP... ", srcip);
  671. if (len < TCPR_ETH_H + TCPR_TCP_H + hl) {
  672. goto len_error;
  673. }
  674. /* memcpy it over to prevent alignment issues */
  675. memcpy(&tcp_hdr, (data + TCPR_ETH_H + hl), TCPR_TCP_H);
  676. /* ftp-data is going to skew our results so we ignore it */
  677. if (tcp_hdr.th_sport == 20)
  678. return (node);
  679. /* set TREE->type based on TCP flags */
  680. if (tcp_hdr.th_flags == TH_SYN) {
  681. node->type = DIR_CLIENT;
  682. dbg(3, "is a client");
  683. }
  684. else if (tcp_hdr.th_flags == (TH_SYN | TH_ACK)) {
  685. node->type = DIR_SERVER;
  686. dbg(3, "is a server");
  687. }
  688. else {
  689. dbg(3, "is an unknown");
  690. }
  691. }
  692. /*
  693. * UDP
  694. */
  695. else if (proto == IPPROTO_UDP) {
  696. if (len < TCPR_ETH_H + TCPR_UDP_H + hl) {
  697. goto len_error;
  698. }
  699. /* memcpy over to prevent alignment issues */
  700. memcpy(&udp_hdr, (data + TCPR_ETH_H + hl), TCPR_UDP_H);
  701. dbgx(3, "%s uses UDP... ", srcip);
  702. switch (ntohs(udp_hdr.uh_dport)) {
  703. case 0x0035: /* dns */
  704. if (len < TCPR_ETH_H + TCPR_UDP_H + TCPR_DNS_H + hl) {
  705. goto len_error;
  706. }
  707. /* prevent memory alignment issues */
  708. memcpy(&dnsv4_hdr,
  709. (data + TCPR_ETH_H + hl + TCPR_UDP_H), TCPR_DNS_H);
  710. if (dnsv4_hdr.flags & DNS_QUERY_FLAG) {
  711. /* bit set, response */
  712. node->type = DIR_SERVER;
  713. dbg(3, "is a dns server");
  714. }
  715. else {
  716. /* bit not set, query */
  717. node->type = DIR_CLIENT;
  718. dbg(3, "is a dns client");
  719. }
  720. return (node);
  721. break;
  722. default:
  723. break;
  724. }
  725. switch (ntohs(udp_hdr.uh_sport)) {
  726. case 0x0035: /* dns */
  727. if (len < TCPR_ETH_H + TCPR_UDP_H + TCPR_DNS_H + hl) {
  728. goto len_error;
  729. }
  730. /* prevent memory alignment issues */
  731. memcpy(&dnsv4_hdr,
  732. (data + TCPR_ETH_H + hl + TCPR_UDP_H),
  733. TCPR_DNS_H);
  734. if ((dnsv4_hdr.flags & 0x7FFFF) ^ DNS_QUERY_FLAG) {
  735. /* bit set, response */
  736. node->type = DIR_SERVER;
  737. dbg(3, "is a dns server");
  738. }
  739. else {
  740. /* bit not set, query */
  741. node->type = DIR_CLIENT;
  742. dbg(3, "is a dns client");
  743. }
  744. return (node);
  745. break;
  746. default:
  747. dbgx(3, "unknown UDP protocol: %hu->%hu", udp_hdr.uh_sport,
  748. udp_hdr.uh_dport);
  749. break;
  750. }
  751. }
  752. /*
  753. * ICMP
  754. */
  755. else if (proto == IPPROTO_ICMP) {
  756. if (len < TCPR_ETH_H + TCPR_ICMPV4_H + hl) {
  757. goto len_error;
  758. }
  759. /* prevent alignment issues */
  760. memcpy(&icmp_hdr, (data + TCPR_ETH_H + hl), TCPR_ICMPV4_H);
  761. dbgx(3, "%s uses ICMP... ", srcip);
  762. /*
  763. * if port unreachable, then source == server, dst == client
  764. */
  765. if ((icmp_hdr.icmp_type == ICMP_UNREACH) &&
  766. (icmp_hdr.icmp_code == ICMP_UNREACH_PORT)) {
  767. node->type = DIR_SERVER;
  768. dbg(3, "is a server with a closed port");
  769. }
  770. }
  771. return (node);
  772. len_error:
  773. errx(-1, "packet capture length %d too small to process", len);
  774. return NULL;
  775. }
  776. #ifdef DEBUG
  777. /**
  778. * prints out a node of the tree to stderr
  779. */
  780. static char *
  781. tree_printnode(const char *name, const tcpr_tree_t *node)
  782. {
  783. memset(&tree_print_buff, '\0', TREEPRINTBUFFLEN);
  784. if (node == NULL) {
  785. snprintf(tree_print_buff, TREEPRINTBUFFLEN, "%s node is null", name);
  786. }
  787. else {
  788. snprintf(tree_print_buff, TREEPRINTBUFFLEN,
  789. "-- %s: %p\nIP: %s\nMask: %d\nSrvr: %d\nClnt: %d\n",
  790. name, (void *)node, node->family == AF_INET ?
  791. get_addr2name4(node->u.ip, RESOLVE) :
  792. get_addr2name6(&node->u.ip6, RESOLVE),
  793. node->masklen, node->server_cnt, node->client_cnt);
  794. if (node->type == DIR_SERVER) {
  795. strlcat(tree_print_buff, "Type: Server\n--\n", TREEPRINTBUFFLEN);
  796. }
  797. else {
  798. strlcat(tree_print_buff, "Type: Client\n--", TREEPRINTBUFFLEN);
  799. }
  800. }
  801. return (tree_print_buff);
  802. }
  803. /**
  804. * prints out the entire tree
  805. */
  806. static char *
  807. tree_print(tcpr_data_tree_t *treeroot)
  808. {
  809. tcpr_tree_t *node = NULL;
  810. memset(&tree_print_buff, '\0', TREEPRINTBUFFLEN);
  811. RB_FOREACH(node, tcpr_data_tree_s, treeroot) {
  812. tree_printnode("my node", node);
  813. }
  814. return (tree_print_buff);
  815. }
  816. #endif /* DEBUG */