uno_lts.c

C程序漏洞检查

static void
dfs_uno(State *s)
{	Trans *t;
	treenode *exp = ZT;

	if (!s) return;

	depth++;
	if (debug)
	{	if (s->n && s->n->hdr.which == LEAF_T)
			printf("%3d: Down <%s> %u <%d: %s>\n",
			depth,
			name_of_node(s->n->hdr.type),
			(s->n->hdr.defuse),
			s->n->hdr.line,
			x_stmnt(s->n));
		else
			printf("%3d: Down <%s:%s:%s> %u <%d: %s>\n",
			depth,
			s->n?name_of_node(s->n->hdr.type):"",
			(s->n && s->n->lnode)?name_of_node(s->n->lnode->hdr.type):"",
			(s->n && s->n->rnode)?name_of_node(s->n->rnode->hdr.type):"",
			(s->n?(int)(s->n->hdr.defuse):-1),
			s->n?s->n->hdr.line:-1,
			s->n?x_stmnt(s->n):"--");
		if (s->n->hdr.defuse) dump_defuse(s->n->hdr.defuse, stdout);
		fflush(stdout);
	}

	if (!dfs_push(s)	/* nothing new to track */
	&&   s->visited)	/* been here before     */
	{	if (debug)
			printf("	old\n");
		goto done;
	}
	if (debug)
	{	if (s->visited)
			printf("	revisit\n");
		else
			printf("	new\n");
	}
	s->visited = 1;

	ana_defuse(s->n);	/* uninitialized var analysis */

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

	for (t = s->succ; t && t->branch; t = t->nxt)
	{	if (exp)
		{
 if (debug) {
	printf("Feasible?: %s", x_stmnt(exp));
	printf(" <==> %s\n", x_stmnt(t->cond));
 }
			if (infeasible(exp, t->cond))
			{
				if (debug) printf("infeasible path\n");
				continue;	/* e.g. 0 == _true_ */
			}
			newpathcond(exp, t->cond);
#if 0
XXX
			if (inconsistent(s->n, pathcond))
			{	/*
				 * s->n has symbols that are known nonzero from previous pathconds
				 * and known zero from the current pathcond -- or vice versa
				 */
				prevpathcond();
				continue;
			}
#endif
			if (!t->knz) setknownzeros(s->n, t, pathcond);

			if (debug) dumknow(s->n, t);

			dfstack->state = pathcond;
		} else
		{	dfstack->state = getpathframe();
			dfstack->state->exp = s->n;
			dfstack->state->val = ZT;
		}

		dfs_uno(t->branch);

		if (exp)
			prevpathcond();
		else
		{	dfstack->state->nxt = pathfree;
			pathfree = dfstack->state;
			dfstack->state = (PathCond *) 0;
		}
	}
done:
	if (debug) printf("%3d: Up\n", depth);
	depth--;
	dfs_pop();
}

static void
uno_statistics(void)
{	Graphs *g;
	SymRef *r;
	int cnt;

	if (1 || Verbose || lintlike || debug)
		bound_stats();

	if (!Verbose) return;

	if (uno_prop) gen_stats();

	g = find_graph("main");

	if (!g)
		return;

	for (cnt=0, g = graph; g; g = g->nxt)
		if (g != glob_decls)
			cnt++;

	if (localonly)
	{	printf("uno: %3d function declarations\n", cnt);

		for (cnt = 0, r = globs; r; r = r->nxt)
			cnt++;
		printf("uno: %3d uninitialized global pointers\n", cnt);
	}
}

static void
uno_indirect_calls(FILE *fd)
{	Gst *k, *m;
	/* for each fct in grst, add all entries of frst */
	/* assumes that any fct that can call another fct through a ptr,
	   can in principle call any of the fcts that are passed around
	   with fct ptrs */

	for (k = grst; k; k = k->nxt)
	for (m = frst; m; m = m->nxt)
		fprintf(fd, "p\t%s\t%s\t%d\n",
			k->gnm->fctnm, m->gnm->fctnm, m->gnm->status);
	
}

static void
uno_snapshot(Graphs *g)
{
	if (localonly) return;

	fprintf(fd_uno, "%c\t%s\t%s\t%d\n",	/* function */
		(strcmp(g->scope, "global") == 0)? 'F' : 'f',
		g->fctnm,
		g->cfg->n->hdr.fnm,
		g->cfg->n->hdr.line);

	fprintf(fd_uno, "X\treturns_a\tvalue\t");
	if (g->status & (1|2|4))	/* 1:return value, 2:no return value, 4: cannot tell */
		fprintf(fd_uno, "%d\n", g->status);
	else
	{	fprintf(fd_uno, "2\n");
		if (debug)
		fprintf(stderr, "uno: using default return value status for %s\n",
			g->fctnm);
	}

	if (0) { SymRef *r; for (r = g->def_use; r; r = r->nxt)
	fprintf(fd_uno, "X\t%s\t%d\n", r->sm->nme->str, r->status); }

	/* record information in use of *globals* within this function */

	uno_report0(fd_uno, "D", DEF,           g->def_use);	/* def */
	uno_report0(fd_uno, "D", DEF|USE,       g->def_use);
	uno_report0(fd_uno, "D", DEF|USE|DEREF, g->def_use);

	uno_report0(fd_uno, "D", UNO_CONST,           g->def_use);
	uno_report0(fd_uno, "D", UNO_CONST|USE,       g->def_use);
	uno_report0(fd_uno, "D", UNO_CONST|USE|DEREF, g->def_use);

	uno_report1(fd_uno, "R", USE|DEREF,     g->suspect);	/* possible deref_useb4def */
	uno_report1(fd_uno, "U", USE,           g->suspect);	/* possible useb4def */

	uno_report1(fd_uno, "C", DEF,           g->fcalls);	/* fcts called, - return vals used */
	uno_report1(fd_uno, "c", USE,           g->fcalls);	/* fcts called, + return vals used */
	uno_report1(fd_uno, "b", DEF|USE,       g->fcalls);
#if 1
	/* fcts called through ptrs */
	uno_report1(fd_uno, "h", DEF|HIDE,      g->fcalls);	/* fcts called - can't tell retval */
	uno_report1(fd_uno, "i", USE|HIDE,      g->fcalls);
	uno_report1(fd_uno, "j", DEF|USE|HIDE,  g->fcalls);
#endif
	fprintf(fd_uno, "\n");
}

static void
gen_graph(Graphs *g)
{
	if (!g || g->visited) return;
	g->visited = 1;

	curgraph = g;

	dfs_uno(g->cfg);		/* collect info */

	if (!uno_prop) ana_locs(g);	/* check for unreferenced locals */

	uno_assert((int) !dfstack, "internal error, dfstack non-zero");

	if (uno == 4)	/* -U3 or -local */
	{	if (!localonly)
			uno_snapshot(g);	/* write the .uno file */
		if (!uno_prop)
		{	cfg_unvisit(g->all);
			if (debug) printf("\n============\n");
			dfs_bound(g->cfg, ZT, ZT, ZS);	/* check for array indexing errors */
	}	}

	if (uno_prop && g->cfg != uno_prop)
	{	cfg_unvisit(g->all);
		dfs_generic(g->cfg);
	}
}

static void
dfs_reset(void)
{	Graphs *g;

	for (g = graph; g; g = g->nxt)
		g->visited = 0;
}

#if 0
static symentry_t *
mksym(char *s, treenode *n)
{
	return mk_vardecl(nmelook(s, strlen(s)+1), n);
}
#endif

static void
dup_graph(Graphs *g, treenode *n)
{	int d, r;

	d = (strcmp(g->scope, "global") != 0);
	r = is_static_fct;

	fprintf(stderr, "uno: fct %s redefined\n", g->fctnm);
	fprintf(stderr, "\tdefined%sat %s:%d, redefined%sat %s:%d\n",
		d?" file-static ":" ",
		g->cfg->n->hdr.fnm, g->cfg->n->hdr.line,
		r?" file-static ":" ",
		n->hdr.fnm, n->hdr.line);
}

static Graphs *
new_graph(treenode *n, char *str)
{	Graphs *g;

	for (g = graph; g; g = g->nxt)
		if (g != glob_decls
		&&  g->cfg != uno_prop
		&&  strcmp(g->fctnm, str) == 0
		&&  strcmp(g->cfg->n->hdr.fnm, "-1") == 0)
		{	if (debug)
			printf("uno: replacing template for %s\n", g->fctnm);
			break;
		}

	if (!g)
	for (g = graph; g; g = g->nxt)
	{	if (g == glob_decls
		||  g->cfg == uno_prop)
			continue;

		if (usecheck)
		if (g->cfg->n == n			/* unlikely conflict - or */
		||  (strcmp(g->fctnm, str) == 0		/* same name - and */
		&&   (!is_static_fct			/* new decl has global scope - or */
		||    strcmp(g->scope, "global") == 0	/* previous decl had global scope - or */
		||    strcmp(g->scope, cur_in) == 0)))	/* prev decl has same file scope - or */
			dup_graph(g, n);		/* no break - look for other trouble */
	}

	if (!g)
	{	if (freegraph)
		{	g = freegraph;
			freegraph = g->nxt;
			memset(g, 0, sizeof(Graphs));
		} else
			g = (Graphs *) emalloc(sizeof(Graphs));
		if (!graph)
			graph = g;
		else
		{	g->nxt = graph;
			graph = g;
	}	}

	if (is_static_fct)
	{	g->scope = (char *) emalloc(strlen(cur_in)+1);
		strcpy(g->scope, cur_in);
	} else
		g->scope = "global";

	g->fctnm = (char *) emalloc(strlen(str)+1);
	strcpy(g->fctnm, str);
	g->cfg = create_state(g);
	g->cfg->n = n;

	curgraph = g;

	if (debug)
	printf("uno: new graph for fct %s, status %d (%s)\n", str, g->status, g->cfg->n->hdr.fnm);

	return g;
}

static void
uno_local(void)
{	Graphs *g;
	char *z, unof[512];

	if (uno == 4 && !localonly)
	{	z = strstr(cur_in, ".c");
		uno_assert((int) z, "bad filename");
		*z = '\0';
		sprintf(unof, "%s.uno", cur_in);
		*z = '.';	/* restore */
		fd_uno = fopen(unof, "w");
		uno_assert((int) fd_uno, "cannot create .uno file");
	}

	dfstack = (DfStack *) 0;
	curgraph = glob_decls;

	if (debug) printf("== GLOBALS\n");

	dfs_uno(glob_decls->cfg); /* collect global declarations - build lists */

	if (debug) printf("== done with GLOBALS\n");

	dfstack = (DfStack *) 0;
	dfs_reset();

	for (g = graph; g; g = g->nxt)
		if (strcmp(g->fctnm, property) == 0)
		{	uno_prop = g->cfg;
			break;
		}

	for (g = graph; g; g = g->nxt)
		if (g != glob_decls)
		{	if (debug) printf("== GEN_GRAPH %s\n", g->fctnm); fflush(stdout);
			gen_graph(g);	/* the local check */
		}

	if (uno == 4 && !localonly)	/* add info on globals to snapshot file */
	{	/* globuse flags: 1 - use, 2 - static, 4 - extern, 8 - def, 16 - useb4def, 32 - alias taken */

		uno_report0(fd_uno, "G", DEF,     glob_decls->def_use);	/* global def */
		uno_report0(fd_uno, "G", DEF|USE, glob_decls->def_use);

		uno_report0(fd_uno, "a",      32, globuse);	/* address taken & at least once */

		uno_report0(fd_uno, "v",       0, globuse);	/* normal -def -use */
		uno_report0(fd_uno, "v",       4, globuse);	/* extern -def -use */

		uno_report0(fd_uno, "s",       8, globuse);	/* normal +def -use */
		uno_report0(fd_uno, "s",    8|16, globuse);	/* normal +def -use +useb4def */
		uno_report0(fd_uno, "s",     4|8, globuse);	/* extern +def -use */
		uno_report0(fd_uno, "s",  4|8|16, globuse);	/* extern +def -use +useb4def */

		uno_report0(fd_uno, "u",       1, globuse);	/* normal -def +use */
		uno_report0(fd_uno, "u",    1|16, globuse);	/* normal -def +use +useb4def */
		uno_report0(fd_uno, "u",     1|4, globuse);	/* extern -def +use */
		uno_report0(fd_uno, "u",  1|4|16, globuse);	/* extern -def +use +useb4def */

		uno_report0(fd_uno, "t",     1|8, globuse);	/* normal +def +use */
		uno_report0(fd_uno, "t",  1|8|16, globuse);	/* normal +def +use +useb4def */
		uno_report0(fd_uno, "t",   1|4|8, globuse);	/* extern +def +use */
		uno_report0(fd_uno, "t",1|4|8|16, globuse);	/* extern +def +use +useb4def */
#if 1
		struct_fields(fd_uno);
		/* codes "y" and "z" identify used and unused fields in structs in this file */
#endif

		if (1) uno_indirect_calls(fd_uno);
	}
}

static void
gen_dot(void)
{	Graphs *g;

	printf("digraph dodot {\n");
	printf("	ratio=auto;\n");

	for (g = graph; g; g = g->nxt)
	{	/* printf("want %s, got %s\n", want, g->fctnm); */
		if (strcmp(want, g->fctnm) == 0)
		{	printf("N00 [label=\"%s\"];\n", want);
			printf("N00 -> N%u;\n", g->cfg->n);
			cfg_unvisit(g->all);
			gen_lts(g->cfg);
			printf("\n");
			break;
	}	}
	printf("}\n");
}

static State *
add_seq(State *cur, treenode *n)
{	State *s;

	if (!cur) return cur;

	uno_assert((int) n, "bad call of add_seq");

	s = create_state(curgraph);
	s->n = n;
#if 0
	if (x_testcase) *testcase = 0;
	/* uno should report this, if enabled */
	/* or report an unused global if disabled */
#endif

	cur->nxt = s;
	return s;
}

static State *
lts_node(State *n, treenode *root)
{	Graphs *g;
	State *now = n;

	if (!root) return n;

	switch (root->hdr.type) {
	case TN_FUNC_DECL:
		if (not_a_prototype)
		{	g = new_graph(root, nmestr(((leafnode *)(root->lnode))->data.sval));
			now = g->cfg;
		}	/* parentheses were missing, bug found by uno 10/7/01 */
		break;

	case TN_DECL:
		if (curgraph == glob_decls)
			add_seq(curgraph->all, root);
		else
			now = add_seq(now, root);
		break;

	case TN_LABEL:
		if (root->lnode->hdr.tok == CASE
		||  root->lnode->hdr.tok == DEFLT)	/* case label */
		{	State *t, *st;
			Trans *tr;
			leafnode *si;
			treenode *sl, *sn;

			t = lts_top_switch(root);	/* innermost switch stmnt */
			si = mk_ident();	/* start of this case */
			sl = mk_label_node(si, root, "case");
			sn = mk_goto_node(si);

			/* make new label; insert here
			 * add goto to this label into t->succ
			 */
			now = add_seq(now, sl);
			record_label(sl->lnode, now);

			st = create_state(curgraph);
			st->n = sn;		/* jump to this case */

			tr = get_trans();
			tr->branch = st;
			tr->cond = root->lnode;	/* the expr to be matched */
			tr->nxt = t->succ;
			t->succ = tr;
			now = add_seq(now, root);

			if (root->lnode->hdr.tok == DEFLT)
				sawdefault = 1;

			want_break(root);
		} else
		{	now = add_seq(now, root);
			record_label(root->lnode, now);
		}
		now = lts_tree(now, root->rnode);	/* stmnt labeled */
		break;

	case TN_JUMP:
		switch (root->hdr.tok) {
		case CONT:
			root = lts_top_start();
			saw_break();
			break;
		case BREAK:
			root = lts_top_end();
			saw_break();
			break;
		case GOTO:
			saw_break();
			break;
		case RETURN:
			/* lnode has a return expr, if any */
			fct_retval(root);
			saw_break();
			break;
		}
		now = add_seq(now, root);
		break;


	case TN_SWITCH:
		now = lts_switch(now, root);
		break;
	case TN_WHILE:
		now = lts_while(now, root);
		break;
	case TN_DOWHILE:
		now = lts_dowhile(now, root);
		break;

	case TN_TYPE_NME:
	case TN_NAME_LIST:
	case TN_FIELD_LIST:
	case TN_IDENT_LIST:
	case TN_TYPE_LIST:
	case TN_TRANS_LIST:
	case TN_INIT_LIST:
	case TN_PARAM_LIST:
	case TN_ENUM_LIST:
	case TN_EXPR_LIST:
	case TN_BLOCK:
	case TN_STEMNT_LIST:
	case TN_DECL_LIST:
	case TN_DECLS:
		now = lts_tree(now, root->lnode);
		now = lts_tree(now, root->rnode);
		break;

	case TN_EXPR:
	case TN_SELECT:
	case TN_DEREF:
	case TN_ARRAY_DECL:
	case TN_COMP_DECL:
	case TN_BIT_FIELD:
	case TN_PNTR:
	case TN_OBJ_DEF:
	case TN_OBJ_REF:
	case TN_INIT_BLK:
	case TN_ASSIGN:
	case TN_FUNC_CALL:
	case TN_INDEX:
	case TN_EMPTY:
		break;

	case TN_STEMNT:
		if (root->rnode
		&&  root->rnode->hdr.type != TN_LABEL
		&&  (root->rnode->hdr.type != TN_JUMP
		||   root->rnode->hdr.tok == RETURN))
			now = add_seq(now, root->rnode);

		/* could be a piece of code in the sequel
		   that is reachable only via a goto
		 */
		now = lts_tree(now, root->rnode);
		break;

	case TN_CAST:
		now = lts_tree(now, root->rnode);	/* operand */
		break;

	default:
		fprintf(stderr, "uno: line %3d unexpected node %s\n",
			root->hdr.line, name_of_node(root->hdr.type));
		break;
	}

	return now;
}

static treenode *
mk_label_node(leafnode *ident, treenode *n, char *s)
{	treenode *t;

	t = (treenode *) emalloc(sizeof(treenode));
	t->hdr.which = NODE_T;
	t->hdr.type = TN_LABEL;	/* just a place holder */
	t->hdr.tok = COLON;

	t->hdr.fnm = (char *) emalloc(strlen(n->hdr.fnm)+strlen("after ''")+strlen(s)+1);
	sprintf(t->hdr.fnm, "%s after '%s'", n->hdr.fnm, s);

	t->hdr.line = n->hdr.line;
	t->lnode