tree.c 26 KB

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