uno_bounds.c

C程序漏洞检查！

	if (!z) return;

	n = z->n;

	if (!n || !n->hdr.defuse)
		return;

	l = leftmost(n);
	if (l && l->hdr.tok == EXTRN)
		return;	

	for (s = n->hdr.defuse->other; s; s = s->nxt)
	{
		if ((s->sm->decl_level >= FUNCTION_SCOPE)	/* local */
		&&  (s->mark & DECL)				/* declaration */
		&&  (s->mark & DEF)				/* with initializer */
		&& !(s->mark & ARRAY_DECL)			/* not array decl */
		&& !uno_ignore(s->sm)				/* not from /usr/include */
		&& !(s->mark & REF2))				/* not compound x->ref2 or x.ref2 */
		{	b = uno_dig(s->sm, n);			/* try to derive initial bounds on var */
			if (debug>1)
			explain_bound("newbound", b, n);
	}	}
}

static ArSize *
uno_freears(ArSize *a)
{
	if (a)
	{	uno_freears(a->nxt);
		a->nxt = freears;
		freears = a;
	}
	return (ArSize *) 0;
}

static ArBound *
uno_dumpbounds(ArBound *b)
{
	if (b)
	{	uno_dumpbounds(b->nxt);
		b->nxt = freebounds;
		freebounds = b;
	}
	return (ArBound *) 0;
}

static ArBound *
bound_from_expr(treenode *nn)
{	ArBound *b = (ArBound *) 0;
	symentry_t *s;
	int n;

	if (!nn
	||  !nn->lnode
	||   nn->lnode->hdr.type != TN_IDENT)
		return (ArBound *) 0;

	nogood = 0;
	n = eval_const_expr(nn->rnode, ZT);
	if (nogood)
		return (ArBound *) 0;

	s = nn->lnode->syment;

	switch (nn->hdr.tok) {
	case EQUAL:
		b = add_bound(s, n, n+1, LB|UB|FROMEXPR);
		break;
	case NOT_EQ:
		b = add_bound(s, n, n+1, LB|UB|NEG|FROMEXPR);
		break;
	case LESS:
		b = add_bound(s, 0, n, UB|FROMEXPR);
		break;
	case LESS_EQ:
		b = add_bound(s, 0, n+1, UB|FROMEXPR);
		break;
	case GRTR:
		b = add_bound(s, n+1, 0, LB|FROMEXPR);
		break;
	case GRTR_EQ:
		b = add_bound(s, n, 0, LB|FROMEXPR);
		break;
	}

	return b;
}

void
explain_bound(char *m, ArBound *b, treenode *n)
{
	if (!b) return;

	if (0)
	{	printf("{");
		if (b->bounds & UNK) printf("U");
		if (b->bounds & DUP) printf("(%s:%s)",
			b->s->nme->str,
			b->sameas->nme->str);
		if (b->bounds & NEG) printf("!");
		if ((b->bounds & LB)
		&&  (b->bounds & UB)
		&&  (b->lb == b->ub-1))
			printf("(%s==%d)", b->s->nme->str, b->lb);
		else
		{	if (b->bounds & LB)  printf("(%s>=%d)", b->s->nme->str, b->lb);
			if (b->bounds & UB)  printf("(%s<%d)",  b->s->nme->str, b->ub);
		}
		if (b->bounds & FROMASGN) printf("a");
		if (b->bounds & FROMEXPR) printf("e");
		printf("}");
		return;
	}

	printf("\tuno: %s:%d (%s) %s bound on %s:",
		n?n->hdr.fnm:"",
		n?n->hdr.line:0,
		m,
		n?x_stmnt(n):"",
		b->s->nme->str);

	if (b->bounds & UNK)
		printf(" <unknown>");
	if (b->bounds & NEG)
		printf("<negated>");
	if (b->bounds & DUP)
		printf(" <duplicate of %s>", b->sameas?b->sameas->nme->str:"?");
	else
	{	switch (b->bounds & (LB|UB)) {
		case UB:
			printf("UB < %d", b->ub);
			break;
		case LB:
			printf("LB >= %d", b->lb);
			break;
		case (LB|UB):
			printf(">= %d and < %d", b->lb, b->ub);
			break;
		}
	}
	if (b->bounds & FROMASGN)
		printf(" (from asgn)");
	if (b->bounds & FROMEXPR)
		printf(" (from expr)");

	printf(" set at level %d", b->level_set);
	printf("\n");
}

static void
expr_bound(treenode *n, treenode *v)		/* try to derive bounds on scalars from cond */
{	ArBound *b = (ArBound *) 0;
	char *s;

	if (!n || !v) return;	/* branch conditions only */

	if (n && n->hdr.type == TN_EXPR)
		b = bound_from_expr(n);
	if (!b) return;

	if (v->hdr.tok == IDENT)
	{	s = ((leafnode *)v)->data.sval->str;

		if (strcmp(s, "_false_") == 0)
		{	if (debug>1)
			printf("	negating bound\n");

			negate_bound(b);
		} else if (strcmp(s,  "_true_") != 0)
			goto not_yet;
	} else
	{	/* remove bound b from bounded */
not_yet:
		if (debug>1)
		{	printf("uno: complex condition, removing last derived bound\n");
			explain_bound("expr_bound", b, n);
		}
		uno_assert((int) (b == bounded), "exprbound error");
		bounded = bounded->nxt;

		b->nxt = freebounds;
		freebounds = b;
		return;
	}

	if (debug>1)
	explain_bound("expr_bound", b, n);
}

static void
asgn_bound(State *s)		/* try to derive bounds on scalars from asgn */
{	ArBound *b = (ArBound *) 0;
	treenode *n;

	if (!s) return;
	n = s->n;

	if (n
	&&  n->hdr.type == TN_ASSIGN
	&&  n->hdr.tok == EQ)
		b = bound_from_asgn((symentry_t *)0, n);

	if (debug>1)
	explain_bound("asgn_bound", b, n);
}

static void
gather_bounds(State *z)
{	ArBound *a, *b;
	SymList *s;
	treenode *e;
	int hit;

	if (!z) return;

	if (debug>1)
	{	if (z->n && z->n->hdr.defuse)
		{	printf("	defuse on last step: ");
			dump_defuse(z->n->hdr.defuse, stdout);
			printf("\n");
		}
		for (b = bounded; b; b = b->nxt)
			explain_bound("gather", b, z->n);
	}

	if (z->n && z->n->hdr.type == TN_IF)
		e = ((if_node *)z->n)->cond;
	else
		e = z->n;

	if (e && e->hdr.defuse)
	for (s = e->hdr.defuse->other; s; s = s->nxt)
	{	if (!(s->mark & DEF))	/* set, so must have added bound FROMASGN or INCR... */
			continue;
if (debug)
printf("UU: saw def on %s\n", s->sm->nme->str);

		for (b = bounded; b; b = b->nxt)
		{
if (debug)
printf("UU:	check with bound on %s %d,%d [%d] (set at level %d)\n",
	b->s->nme->str,
	b->lb, b->ub, b->bounds,
	b->level_set);
			if (strcmp(b->s->nme->str, s->sm->nme->str) == 0
#if 1
			&&  b->level_set < depth
#else
			&& (b->bounds & FROMEXPR)
#endif
			)
				b->bounds |= UNK;	/* no longer valid */
		}
		for (b = boundstack->curbounds; b; b = b->nxt)
		{
if (debug)
printf("UU:	previous bound on %s %d,%d [%d] (set at level %d)\n",
	b->s->nme->str,
	b->lb, b->ub, b->bounds,
	b->level_set);
			if (strcmp(b->s->nme->str, s->sm->nme->str) == 0)
			{
if (debug)
printf("UU:	now expired\n");
				b->bounds |= UNK;	/* all previous bounds expire */
			}
		}
	}

	for (b = bounded; b; b = b->nxt)	/* save bounds on stack */
	{	hit = 0;
		if ((b->bounds & FROMASGN)
		||  (b->bounds & UNK))
		{	for (a = boundstack->curbounds; a; a = a->nxt)
				if (a->s == b->s)
					a->bounds |= UNK;	/* remove */
		} else	/* FROMEXPR */
		{	for (a = boundstack->curbounds; a; a = a->nxt)
				if (a->s == b->s)
				{	merge_bounds(a, b);	/* rewrites a as (a/\b) */
					hit = 1;
		}		}

		if (!hit)
		{	a = loose_bound(b->s, b->lb, b->ub, b->bounds);	/* add new bound */
			a->sameas = b->sameas;				/* even if UNK */
			a->dup = b->dup;
			a->nxt = boundstack->curbounds;
			a->level_set = b->level_set;
			boundstack->curbounds = a;

			if (debug>1)
			explain_bound("attach", b, e);
		}
	}

	uno_dumpbounds(bounded);	/* forget all bounds for next step */
	bounded = (ArBound *) 0;
}

void
bound_stats(void)
{
	if (!Verbose) return;

	if (size_zero_resolved)
	printf("%4d\tstatic initializers resolved\n", size_zero_resolved);

	if (size_zero)
	printf("%4d\tarrays declared without size\n", size_zero);

	if (size_seen)
	printf("%4d\tarray indices seen\n", size_seen);

	if (size_notfound)
	printf("%4d\tcould not determine array bound (%d distinct vars)\n",
		size_notfound, size_other);

	if (size_deref)
	printf("%4d\tptr derefs in index (not handled yet)\n", size_deref);

	if (size_outofscope)
	printf("%4d\tnon-checked indices (out of scope)\n", size_outofscope);

	if (size_dunno)
	printf("%4d\tarray indices could not be evaluated\n", size_dunno);

	if (simple_checked > simple_known)
	printf("%4d\tarray indices had no known bound\n", simple_checked-simple_known);

	if (size_ok + size_nok)
	printf("%4d\tarray indices checked (%d violations reported)\n",
			size_ok + size_nok, size_nok);

	if (size_is_simple + simple_checked)
	printf("%4d\tsimple indices - %d of which could be and %d were checked)\n",
		size_is_simple, simple_checked, simple_known);

	if (simple_checked > simple_known)
	printf("	(%d had no known bound)\n", simple_checked-simple_known);
}

void
uno_bounds(SymList *s, ArList *d, treenode *n)
{	ArList *a;

	for (a = d; a; a = a->nxt)
		ana_aio_decl(s, a->tn, n);
}

void
uno_index(State *s)
{	ArList *a;
	treenode *e;

	if (!s) return;

	if (s->n && s->n->hdr.type == TN_IF)
		e = ((if_node *)s->n)->cond;
	else
		e = s->n;

	if (e && e->hdr.defuse)
	for (a = e->hdr.defuse->aio; a; a = a->nxt)		/* index operations */
		ana_aio_ix(s, a->tn);
}

static void
fix_dups(State *s)
{	ArBound *a, *b;
	int cnt = 0;

	for (a = boundstack->curbounds; a; a = a->nxt)
		if (a->bounds & DUP)
		{	a->dup = (ArBound *) 0;
			if (a->s == a->sameas)
			{	if (Verbose)
				{	printf("uno: warning: reflexive dup\n");
					explain_bound("target:", a, s->n);
				}
				a->bounds &= ~DUP;
				a->sameas = (symentry_t *) 0;
			}
			cnt = 0;
again:
			for (b = boundstack->curbounds; b; b = b->nxt)
			{	if (b == a) continue;

				if (b->s == a->sameas)
				{	if (debug>1)
					{	printf("\tdup on '%s' picked up from stack\n",
						a->s->nme->str);
						explain_bound("from", b, ZT);
					}

					if (b->bounds & UNK)
					{	a->bounds |= UNK;
						a->bounds &= ~DUP;
						a->sameas = (symentry_t *) 0;
						break;
					}

					if (!(b->bounds & DUP))
						a->dup = b;
					else
					{	if (b->s == b->sameas)
						{	printf("uno: warning: reflextive dup target\n");
							explain_bound("target:", b, ZT);
							b->bounds &= ~DUP;
							b->sameas = (symentry_t *) 0;
							a->dup = b;
						} else
						{	a->sameas = b->sameas;
							if (cnt++ <= 10)
								goto again;
							printf("dup cycle\n");
							explain_bound("member:", a, s->n);
							a->bounds |= UNK;
							a->bounds &= ~DUP;
							a->sameas = (symentry_t *) 0;
							a->dup = (ArBound *) 0;
					}	}
					break;
				}
			}
			if (!b)
			{	if (debug>1)
				printf("\tcould not find dup for %s on stack\n",
					a->s->nme->str);
				a->bounds |= UNK;
				a->bounds &= ~DUP;
				a->sameas = (symentry_t *) 0;
				a->dup = (ArBound *) 0;
			}
		}
}

static BoundStack *
uno_bframe(void)
{	BoundStack *f;

	if (freestack)
	{	f = freestack;
		freestack = freestack->nxt;
		f->nxt = (BoundStack *) 0;
	} else
		f = (BoundStack *) emalloc(sizeof(BoundStack));
	return f;
}

static int
bound_push(State *s, treenode *exp_in, treenode *t_cond, State *prev_s)
{	ArBound	*a, *b;
	BoundStack *f;
	int any_updates;

	f = uno_bframe();
	f->curbounds = (ArBound *) 0;

	if (boundstack)		/* carry known bounds forward onto new stackframe */
	for (b = boundstack->curbounds; b; b = b->nxt)
	{	if (b->bounds&UNK)
			continue;
		if (debug>1) explain_bound("imprt", b, ZT);

		a = loose_bound(b->s, b->lb, b->ub, b->bounds);
		a->sameas = b->sameas;
		a->dup = b->dup;
		a->nxt = f->curbounds;
		a->level_set = b->level_set;
		f->curbounds = a;
	}

	f->nxt = boundstack;
	boundstack = f;

	/* pick up new bounds from the immediately preceding step that brought us here */
	dual_work(prev_s);		/* possible initializers in decls */
	expr_bound(exp_in, t_cond);	/* possible bound from branch cond */
	asgn_bound(prev_s);		/* possible bound from asgn */
	gather_bounds(prev_s);		/* reconcile the bounds */

	any_updates = 0;
	fix_dups(s);

	for (b = boundstack->curbounds; b; b = b->nxt)
	{
#if 0
		/* bound could have been known before */
		if (b->bounds & UNK)
			continue;
#endif
		if (debug>1) explain_bound("stack", b, ZT);

		if (unsatisfiable(b))	/* something became unsatisfiable at this step */
		{	if (debug) explain_bound("unsatisfiable", b, s->n);
			return 3;	/* don't update state - no run can get here */
		}

		for (a = s->pvb; a; a = a->nxt)	/* previously seen bounds at this step */
			if (same_bounds(a, b))
				break;

		if (!a)
		{	any_updates = 1;
			a = loose_bound(b->s, b->lb, b->ub, b->bounds);
			a->sameas = b->sameas;
			a->dup = b->dup;
			a->nxt = s->pvb;
			a->level_set = b->level_set;
			s->pvb = a;
	}	}

	if (debug>1)
	{	for (b = s->pvb; b; b = b->nxt)
			explain_bound("pvb", b, s->n);
	}

	if (!any_updates)		/* bounds stored @ state are unchanged */
	{	if (s->visited)
			return 2;	/* old state */
		s->visited = 1;
		return 1;		/* new state */
	}
	s->visited = 1;
	return 0;			/* revisit state */
}

static void
bound_pop(void)
{	BoundStack *f;

	uno_assert((int) boundstack, "boundstack pop error");
	uno_dumpbounds(boundstack->curbounds);	/* recycle */

	f = boundstack;
	boundstack = boundstack->nxt;		/* pop */

	f->nxt = freestack;			/* recycle */
	freestack = f;
}

void
bound_reset(void)
{
	bounded = uno_dumpbounds(bounded);
	arsize = uno_freears(arsize);
	arnosize = uno_freears(arnosize);
	v_reps = (Stack *) 0;
}

int
dfs_bound(State *s, treenode *exp_in, treenode *t_cond, State *prev_s)
{	Trans *t;
	treenode *exp;
	int result = 1;

	if (!s) return result;

	depth++;
	if (debug)
	{	printf("%3d: dfs_bound %s:%d <%s>\n",
			depth,
			s->n->hdr.fnm,
			s->n->hdr.line,
			x_stmnt(exp_in));
	}

	switch (bound_push(s, exp_in, t_cond, prev_s)) {
	case 3:	/* unsatisfiable bound */
		result = 0;
		goto done;
	case 2:	
		if (debug) printf("\told state\n");
		goto done;
	case 1:
		if (debug) printf("\tnew state\n");
		break;
	case 0:
		if (debug) printf("\trevisit state\n");
		break;
	}

	uno_index(s);	/* attempt to find out of bound array indices */

	if (s->iscond && s->n)
	{	if (s->n->hdr.type == TN_IF)
			exp = ((if_node *)s->n)->cond;
		else
			exp = s->n;
	} else
		exp = ZT;

	for (t = s->succ; t && t->branch; t = t->nxt)
		if (!infeasible(exp, t->cond))	/* e.g. 0 == _true_ */
			dfs_bound(t->branch, exp, t->cond, s);

done:	bound_pop();

	if (debug)
		printf("%3d: dfs_bound up\n", depth);
	depth--;

	return result;
}