uno_lts.c

C程序漏洞检查

			s->iscond = (cnt > 1);
	}	}
}

static void
nut_prepare(State *from, State *to)	/* insert forward arcs to nodes with a nut attached */
{	Trans *t;

	if (!to || !to->n || to->visited)
		return;
	to->visited = 1;

	if (to->n->hdr.nuts
	|| !(to->succ && to->succ->branch))
	{	for (t = from->direct; t; t = t->nxt)
			if (t->branch == to)
				break;
		if (!t)
		{	t = get_trans();
			t->branch = to;
			t->nxt = from->direct;
			from->direct = t;
		}
		return;
	}

	for (t = to->succ; t; t = t->nxt)
		nut_prepare(from, t->branch);
}

static void
nuts_forward(Graphs *g, State *s)
{	Trans *t;

	if (!s->direct)
	for (t = s->succ; t; t = t->nxt)
	{	cfg_unvisit(g->all);
		s->visited = 1;
		nut_prepare(s, t->branch);
	}
}

static void
dumknow(treenode *n, Trans *t)
{	SymRef *r;

	printf("KnownNonZero @ %s:%d: ",
		n?n->hdr.fnm:"--",
		n?n->hdr.line:0);
	for (r = t->knz; r; r = r->nxt)
		printf("%s, ", r->sm->nme->str);
	printf("\n");
}

static treenode *
clone_node(treenode *r)
{	treenode *n;
	n = (treenode *) emalloc(sizeof(treenode));
	memcpy(n, r, sizeof(treenode));
	n->hdr.nuts = (Nuts *) 0;
	n->hdr.defuse = (DefUse *) 0;
	return n;
}

static void
nut_insertion(Graphs *g, State *s, Trans *t)
{	State  *ns;
	Trans  *nt;
	SymRef *r = t->knz;

	if (debug) dumknow(s->n, t);
	 /*
	  * insert dummy state between s and t->branch,
	  * to attach nut knz info
	  */
	nt = get_trans();
	nt->branch = t->branch;

	ns = create_state(g);	/* inserted new state */
	ns->n = clone_node(s->n);	/* points to the same node */
	ns->succ = nt;		/* goes to the original successor */
	t->branch = ns;		/* the old transition now points to inserted state */

	for (r = t->knz; r; r = r->nxt)
		attach_nut("N", r->sm, ns->n);	/* non-zero vars */
}

static void
nut_setup(Graphs *g)	/* build abstracted graph */
{	State *s;
	Trans *t;

	for (s = g->all; s; s = s->all)
	for (t = s->succ; t; t = t->nxt)
		if (t->knz)
			nut_insertion(g, s, t);

	for (s = g->all; s; s = s->all)
		nuts_forward(g, s);
}

static unsigned long Cnt = 1;

static void
nut_hunt(FILE *fd, State *s)
{	Trans *t;
	Nuts *q;

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

	if (s->visited)
	{	fprintf(fd, "{%u}\n", (int) s->uno_state);
		return;
	}
	s->visited = 1;
	s->uno_state = Cnt++;

	fprintf(fd, ">%u>\n", (int) s->uno_state);

	if (!s->n->hdr.nuts)
		fprintf(fd, "[]\n");
	for (q = s->n->hdr.nuts; q; q = q->nxt)
		fprintf(fd, "[%s]\n", q->nut);

	for (t = s->direct; t; t = t->nxt)
	{	nut_hunt(fd, t->branch);
		fprintf(fd, "<%u<\n", (int) s->uno_state);
	}
}

static void
fct_details(FILE *fd, State *s)
{	Trans *t;
	State *ns;
	treenode *exp = (treenode *) 0;

	if (!s || !s->n || s->visited)
		return;

	s->visited = 1;

	if (s->n->hdr.type == TN_IF)
		exp = ((if_node *)s->n)->cond;
	else if (s->n->hdr.type != TN_LABEL)
		exp = s->n;

	for (t = s->succ; t; t = t->nxt)
	{	ns = t->branch;
		if (!ns || !ns->n)
		{	if (exp)
				fprintf(fd, ">0>\n[%s]\n<%d<\n",
				x_stmnt(exp), (int) s->uno_state);
			continue;
		}
		if (ns->visited)
			fprintf(fd, "{%u}\n", (int) ns->uno_state);
		else
		{	ns->uno_state = Cnt++;
			fprintf(fd, ">%u>\n", (int) ns->uno_state);
		}
		fprintf(fd, "[%s", x_stmnt(exp));
		if (t->cond) fprintf(fd, " == %s", x_stmnt(t->cond));
		fprintf(fd, "]\n");
		fct_details(fd, ns);
		fprintf(fd, "<%u<\n", (int) s->uno_state);
	}
}

static void
nut_start(void)
{	Graphs *g;
	State *x;

	for (g = graph; g; g = g->nxt)
	{	if (g == glob_decls)
			continue;

		cfg_unvisit(g->all);
		fprintf(fd_uno, ": %s	%d\n", g->fctnm, g->status);	/* reminder of fct name */

		if (g->cfg == uno_prop)
		{	extern int err_path;
			err_path++;
			fct_details(fd_uno, uno_prop);
			err_path--;
		} else if (g->hasnuts)
		{	nut_setup(g);
			cfg_unvisit(g->all);
			x = g->cfg;
#if 1
			while (!x->n->hdr.nuts && x->direct && !x->direct->nxt)
				x = x->direct->branch;
#endif
			nut_hunt(fd_uno, x);
		}
		fprintf(fd_uno, "\n");
	}
}

static void
gen_lts(State *s)
{	State *n;
	Trans *t;
	ArBound *b;
	char *z, *zz;
	int cnt;

	if (!s || !s->n || s->visited) return;

	s->visited = 1;

	for (z = zz = x_stmnt(s->n), cnt=0; *zz; zz++) {
		if (*zz == '"') *zz = '\'';
		if (*zz == '\n') *zz = ' ';
		if (*zz == '\r') *zz = ' ';
		if (++cnt > 16) { *zz = '\0'; break; }
	}

	printf("N%u [label=\"%d : %s : %s : ",
		(unsigned int) s->n,
		s->n->hdr.line,
		name_of_node(s->n->hdr.type),
		z );
#if 0
	printf("N%u [label=\"%s : %d : %s <%d> : %s : ",
		(unsigned int) s->n,
		s->n->hdr.fnm,
		s->n->hdr.line,
		name_of_node(s->n->hdr.type),
		s->iscond,
		x_stmnt(s->n) );
#endif

	if (s->n->hdr.type == TN_IF)
		dump_defuse(((if_node *)s->n)->cond->hdr.defuse, stdout);
	else
		dump_defuse(s->n->hdr.defuse, stdout);

	for (b = s->pvb; b; b = b->nxt)
	{	explain_bound("", b, (treenode *)0);
		printf(",");
	}

	printf("\"];\n");

	for (t = s->succ; t && t->branch; t = t->nxt)
	{	n = t->branch;
		printf("N%u -> N%u;\n",
			(unsigned int) s->n,
			(unsigned int) n->n);
		gen_lts(n);
	}
}

SymRef *
uno_getref(symentry_t *t)
{	SymRef *r;

	if (dfs_free)
	{	r = dfs_free;
		dfs_free = dfs_free->nxt;
		r->sm = (symentry_t *) 0;
		r->n  = ZT;
		r->nxt = (SymRef *) 0;
		r->status = 0;
		r->s_val = 0;
	} else
		r = (SymRef *) emalloc(sizeof(SymRef));

	r->sm = t;

	return r;
}

SymRef *
uno_copy_ref(SymRef *r)
{	SymRef *q;
	q = uno_getref(r->sm);
	q->n = r->n;
	q->status = r->status;
	q->s_val = r->s_val;
	return q;
}

SymExt *
uno_getext(symentry_t *t)
{	SymExt *r;

	if (freesymext)
	{	r = freesymext;
		freesymext = r->nxt;
		memset(r, 0, sizeof(SymExt));
	} else
		r = (SymExt *) emalloc(sizeof(SymExt));
	r->sm = t;

	return r;
}

static DfStack *
uno_getframe(void)
{	DfStack *r;

	if (dfs_frame)
	{	r = dfs_frame;
		dfs_frame = dfs_frame->nxt;
		r->symrefs = (SymRef *) 0;
		r->globrefs = (SymRef *) 0;
		r->nxt = (DfStack *) 0;
	} else
		r = (DfStack *) emalloc(sizeof(DfStack));

	return r;
}

static void
uno_report0(FILE *fd, char *s, int t, SymRef *d)
{	SymRef *r;

	for (r = d; r; r = r->nxt)
		if (t == -1 || r->status == t)
		fprintf(fd, "%s\t%s\t%s\t%d\n",
			s,
			r->sm->nme->str,
			r->n->hdr.fnm,
			r->n->hdr.line);
}

static void
uno_report1(FILE *fd, char *s, int t, SymExt *d)
{	SymExt *r;

	for (r = d; r; r = r->nxt)
	{	if (t != -1
		&&  t != r->status)
			continue;

		fprintf(fd, "%s\t%s\t%s\t%d\n",
			s,
			r->sm->nme->str,
			r->n->hdr.fnm,
			r->n->hdr.line);
	}
}

static void
add_glob(symentry_t *t, treenode *n, int st)
{	SymRef *r;

	if (debug) printf("Adding Global %s to globs\n", t->nme->str);

	for (r = globs; r; r = r->nxt)
		if (r->sm == t)
		{	r->status |= st;
			return;
		}

	r = uno_getref(t);
	r->n = n;
	r->status = st;
	r->nxt = globs;
	globs = r;
}

static int
on_glob(symentry_t *t)
{	SymRef *r;

	for (r = globs; r; r = r->nxt)
		if (r->sm == t)
			return ((r->status & ~2) == 0);
	return 0;
}

static void
mark_guse(symentry_t *t, treenode *n, int st)
{	SymRef *r;

	if (0)
	printf("mark_guse: %s:%d: - %s - %d\n", n->hdr.fnm, n->hdr.line, t->nme->str, st);

	if (is_enum_const(t)) return;

	for (r = globuse; r; r = r->nxt)
		if (r->sm == t)
		{	if (st == 32)	/* ALIAS flag dominates all */
				r->status = st;
			else if (r->status != 32)
				r->status |= st;
			return;
		}

	r = uno_getref(t);
	r->status = st;
	r->n = n;
	r->nxt = globuse;
	globuse = r;
}

static void
uno_complain(SymRef *r, char *qualify, char *issue)
{
	if (strcmp(qualify, "extern ") == 0)	/* unused extern */
	{	char *p = strstr(r->n->hdr.fnm, ".h");
		if (p && strcmp(p, ".h") == 0)	/* in header file */
			return;			/* too fussy */
	}

	fprintf(stdout, "uno: ");
	if (r->n) fprintf(stdout, "%s:%d:", r->n->hdr.fnm, r->n->hdr.line);
	fprintf(stdout, "\t%sglobal variable '%s' %s\n",
		qualify, r->sm->nme->str, issue);
}

static void
uno_guse(void)
{	SymRef *r;
	Graphs *g;

	/* flags: 1 - used, 2 - static, 4 - extern, 8 - def-ed, 16 - useb4def */
	/* local check of unused globals in this file */

	if (usecheck)
	for (r = globuse; r; r = r->nxt)
	{
		if (0)	printf("%s - %d \t%s:%d: <-> %s\n",
			r->sm->nme->str,
			r->status,
			r->n->hdr.fnm,
			r->n->hdr.line,
			file_name);

		if (r->n
		&&  r->n->hdr.fnm
		&&  strcmp(r->n->hdr.fnm, file_name) != 0)
			continue;

		switch (r->status) {
		case  0: /* normal -def -use */
			uno_complain(r, "", "not assigned to or used in this file");
			break;
		case  8: /* normal +def -use */
			uno_complain(r, "", "assigned to but not used in this file");
			break;

		case  2: /* static -def -use */
			uno_complain(r, "static ", "never assigned to or used");
			break;

		case 10: /* static +def -use */
			uno_complain(r, "static ", "assigned to but not used");
			break;

		case  3: /* static -def +use */
		case 19: /* 1|2|16   static -def  +use +useb4def */
			if (on_glob(r->sm))
			uno_complain(r, "static ", "used but never assigned to");
			break;

		case 27: /* 1|2|8|16 static +def  +use +useb4def */
			if (lintlike && on_glob(r->sm))	/* picky mode */
			uno_complain(r, "static ", "may be used before set");
			/*
			 * also picks up cases of globals assumed to be 0-init
			 * only dereference operations are trouble in this case
			 * - these are reported elsewhere
			 */
			break;

		case  4: /* extern -def -use */
			uno_complain(r, "extern ", "not assigned to or used in this file");
			break;

		case  1: /* 1        normal -def +use */
		case  5: /* 1|4      extern -def +use */
		case  9: /* 1|8      normal +def +use */
		case 11: /* 1|2|8    static +def +use */
		case 13: /* 1|4|8    extern +def +use */
		case 17: /* 1|16     normal -def  +use +useb4def */
		case 21: /* 1|4|16   extern -def  +use +useb4def */
		case 12: /* 4|8      extern +def -use */
			break;	/* ok */

		case 25: /* 1|8|16   normal +def  +use +useb4def */
		case 29: /* 1|4|8|16 extern +def  +use +useb4def */
			/* should be improved */
			if (!on_glob(r->sm)) continue;

			for (g = graph; g; g = g->nxt)
			{	if (g == glob_decls
				||  g->cfg == uno_prop
				||  strcmp(g->fctnm, "main") == 0)
					continue;
				break;
			}
			if (!g)	/* main is the only procedure */
			uno_complain(r, "", "may be used before set in main()");
			break;

		case 32:	/* global address was taken */
			break;

		default: /* 4&2 or 4&2&1 -- var has both static and extern flags */
			fprintf(stderr, "uno: internal error, invalid status %d, uno_guse\n",
				r->status);
			break;
	}	}
}

static void
fct_retval(treenode *n)
{
	if (!n->lnode)
	{	curgraph->status |= 2;	/* no return value */
		if (debug) printf("fct_retval %s adds 2\n", curgraph->fctnm);
	} else
		curgraph->status |= 1;	/* return value used */
}

static void
make_suspect(symentry_t *t, treenode *n, int tags)
{	SymExt *v;

	if (localonly) return;

	for (v = curgraph->suspect; v; v = v->nxt)
		if (v->sm == t
		&&  v->n == n)
		{	v->status |= tags;
			break;
		}
	if (!v)
	{	v = uno_getext(t);
		v->n = n;
		v->status = tags;
		v->nxt = curgraph->suspect;
		curgraph->suspect = v;
	}
}

static void
add_fcall(symentry_t *t, treenode *n, int status)
{	SymExt *r;

	if (debug) printf("fct %s calls fct %s\n", curgraph->fctnm, t->nme->str);

	for (r = curgraph->fcalls; r; r = r->nxt)
		if (r->sm == t)
		{	if (status & DEF)
				r->n = n;	/* remember failures to use ret value */
			break;
		}
	if (!r)
	{	r = uno_getext(t);
		r->n = n;
		r->nxt = curgraph->fcalls;
		curgraph->fcalls = r;
	}

	r->status |= status;

	switch (r->status) {
	case DEF:		attach_nut("C", t, n); break;
	case USE:		attach_nut("c", t, n); break;
	case DEF|USE:		attach_nut("b", t, n); break;
	case DEF|HIDE:		attach_nut("h", t, n); break;
	case USE|HIDE:		attach_nut("i", t, n); break;
	case DEF|USE|HIDE:	attach_nut("j", t, n); break;
	}
}

static Graphs *
find_graph(char *s)
{	Graphs *g;

	for (g = graph; g; g = g->nxt)
	{	if (g == glob_decls)
			continue;
		if (strcmp(s, g->fctnm) == 0)
			return g;
	}

	if (0) printf("uno: no graph %s\n", s);
	return (Graphs *) 0;
}

static void
add_locs(symentry_t *t, treenode *n)
{	SymRef *r;

	for (r = curgraph->locs; r; r = r->nxt)
		if (r->sm == t)
			return;

	r = uno_getref(t);
	r->n = n;
	r->nxt = curgraph->locs;
	curgraph->locs = r;
}

static int
is_local(symentry_t *t)
{	SymRef *r;