X-Git-Url: https://git.tcpdump.org/libpcap/blobdiff_plain/d71913d38475f5b4f0dc753074337ba29d5c0789..7a23bb335748d78c1865b2b57da18d30ee83c53f:/optimize.c diff --git a/optimize.c b/optimize.c index bea8cdcb..778bcb1b 100644 --- a/optimize.c +++ b/optimize.c @@ -427,20 +427,18 @@ find_dom(opt_state_t *opt_state, struct block *root) */ x = opt_state->all_dom_sets; /* - * These are both guaranteed to be > 0, so the product is - * guaranteed to be > 0. - * - * XXX - but what if it overflows? + * In opt_init(), we've made sure the product doesn't overflow. */ i = opt_state->n_blocks * opt_state->nodewords; - do + while (i != 0) { + --i; *x++ = 0xFFFFFFFFU; - while (--i != 0); + } /* Root starts off empty. */ - i = opt_state->nodewords; - do + for (i = opt_state->nodewords; i != 0;) { + --i; root->dom[i] = 0; - while (--i != 0); + } /* root->level is the highest level no found. */ for (level = root->level; level >= 0; --level) { @@ -478,15 +476,12 @@ find_edom(opt_state_t *opt_state, struct block *root) x = opt_state->all_edge_sets; /* - * These are both guaranteed to be > 0, so the product is - * guaranteed to be > 0. - * - * XXX - but what if it overflows? + * In opt_init(), we've made sure the product doesn't overflow. */ - i = opt_state->n_edges * opt_state->edgewords; - do + for (i = opt_state->n_edges * opt_state->edgewords; i != 0; ) { + --i; x[i] = 0xFFFFFFFFU; - while (--i != 0); + } /* root->level is the highest level no found. */ memset(root->et.edom, 0, opt_state->edgewords * sizeof(*(uset)0)); @@ -2138,17 +2133,19 @@ link_inedge(struct edge *parent, struct block *child) static void find_inedges(opt_state_t *opt_state, struct block *root) { + u_int i; + int level; struct block *b; - for (u_int i = 0; i < opt_state->n_blocks; ++i) + for (i = 0; i < opt_state->n_blocks; ++i) opt_state->blocks[i]->in_edges = 0; /* * Traverse the graph, adding each edge to the predecessor * list of its successors. Skip the leaves (i.e. level 0). */ - for (int i = root->level; i > 0; --i) { - for (b = opt_state->levels[i]; b != 0; b = b->link) { + for (level = root->level; level > 0; --level) { + for (b = opt_state->levels[level]; b != 0; b = b->link) { link_inedge(&b->et, JT(b)); link_inedge(&b->ef, JF(b)); } @@ -2460,13 +2457,19 @@ count_blocks(struct icode *ic, struct block *p) static void number_blks_r(opt_state_t *opt_state, struct icode *ic, struct block *p) { - int n; + u_int n; if (p == 0 || isMarked(ic, p)) return; Mark(ic, p); n = opt_state->n_blocks++; + if (opt_state->n_blocks == 0) { + /* + * Overflow. + */ + opt_error(opt_state, "filter is too complex to optimize"); + } p->id = n; opt_state->blocks[n] = p; @@ -2514,6 +2517,8 @@ opt_init(opt_state_t *opt_state, struct icode *ic) { bpf_u_int32 *p; int i, n, max_stmts; + u_int product; + size_t block_memsize, edge_memsize; /* * First, count the blocks, so we can malloc an array to map @@ -2529,6 +2534,12 @@ opt_init(opt_state_t *opt_state, struct icode *ic) number_blks_r(opt_state, ic, ic->root); opt_state->n_edges = 2 * opt_state->n_blocks; + if ((opt_state->n_edges / 2) != opt_state->n_blocks) { + /* + * Overflow. + */ + opt_error(opt_state, "filter is too complex to optimize"); + } opt_state->edges = (struct edge **)calloc(opt_state->n_edges, sizeof(*opt_state->edges)); if (opt_state->edges == NULL) { opt_error(opt_state, "malloc"); @@ -2545,9 +2556,59 @@ opt_init(opt_state_t *opt_state, struct icode *ic) opt_state->edgewords = opt_state->n_edges / BITS_PER_WORD + 1; opt_state->nodewords = opt_state->n_blocks / BITS_PER_WORD + 1; + /* + * Make sure opt_state->n_blocks * opt_state->nodewords fits + * in a u_int; we use it as a u_int number-of-iterations + * value. + */ + product = opt_state->n_blocks * opt_state->nodewords; + if ((product / opt_state->n_blocks) != opt_state->nodewords) { + /* + * XXX - just punt and don't try to optimize? + * In practice, this is unlikely to happen with + * a normal filter. + */ + opt_error(opt_state, "filter is too complex to optimize"); + } + + /* + * Make sure the total memory required for that doesn't + * overflow. + */ + block_memsize = (size_t)2 * product * sizeof(*opt_state->space); + if ((block_memsize / product) != 2 * sizeof(*opt_state->space)) { + opt_error(opt_state, "filter is too complex to optimize"); + } + + /* + * Make sure opt_state->n_edges * opt_state->edgewords fits + * in a u_int; we use it as a u_int number-of-iterations + * value. + */ + product = opt_state->n_edges * opt_state->edgewords; + if ((product / opt_state->n_edges) != opt_state->edgewords) { + opt_error(opt_state, "filter is too complex to optimize"); + } + + /* + * Make sure the total memory required for that doesn't + * overflow. + */ + edge_memsize = (size_t)product * sizeof(*opt_state->space); + if (edge_memsize / product != sizeof(*opt_state->space)) { + opt_error(opt_state, "filter is too complex to optimize"); + } + + /* + * Make sure the total memory required for both of them dosn't + * overflow. + */ + if (block_memsize > SIZE_MAX - edge_memsize) { + opt_error(opt_state, "filter is too complex to optimize"); + } + /* XXX */ - opt_state->space = (bpf_u_int32 *)malloc(2 * opt_state->n_blocks * opt_state->nodewords * sizeof(*opt_state->space) - + opt_state->n_edges * opt_state->edgewords * sizeof(*opt_state->space)); + opt_state->space = (bpf_u_int32 *)malloc(block_memsize + edge_memsize); if (opt_state->space == NULL) { opt_error(opt_state, "malloc"); } @@ -2923,7 +2984,7 @@ dot_dump_node(struct icode *ic, struct block *block, struct bpf_program *prog, icount = slength(block->stmts) + 1 + block->longjt + block->longjf; noffset = min(block->offset + icount, (int)prog->bf_len); - fprintf(out, "\tblock%d [shape=ellipse, id=\"block-%d\" label=\"BLOCK%d\\n", block->id, block->id, block->id); + fprintf(out, "\tblock%u [shape=ellipse, id=\"block-%u\" label=\"BLOCK%u\\n", block->id, block->id, block->id); for (i = block->offset; i < noffset; i++) { fprintf(out, "\\n%s", bpf_image(prog->bf_insns + i, i)); } @@ -2950,9 +3011,9 @@ dot_dump_edge(struct icode *ic, struct block *block, FILE *out) Mark(ic, block); if (JT(block)) { - fprintf(out, "\t\"block%d\":se -> \"block%d\":n [label=\"T\"]; \n", + fprintf(out, "\t\"block%u\":se -> \"block%u\":n [label=\"T\"]; \n", block->id, JT(block)->id); - fprintf(out, "\t\"block%d\":sw -> \"block%d\":n [label=\"F\"]; \n", + fprintf(out, "\t\"block%u\":sw -> \"block%u\":n [label=\"F\"]; \n", block->id, JF(block)->id); } dot_dump_edge(ic, JT(block), out);