uno_fcts.c

C程序漏洞检查

/***** uno: uno_fcts.c *****/

/* Copyright (c) 2000-2003 by Lucent Technologies - Bell Laboratories     */
/* All Rights Reserved.  This software is for educational purposes only.  */
/* Permission is given to distribute this code provided that this intro-  */
/* ductory message is not removed and no monies are exchanged.            */
/* No guarantee is expressed or implied by the distribution of this code. */
/* Software written by Gerard J. Holzmann based on the public domain      */
/* ANSI-C parser Ctree Version 0.14 from Shaun Flisakowski                */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include "dtags.h"
#include "uno_fcts.h"

extern int	longtrace, verbose;
static int	debug = 0;

static BFct	*fcts = (BFct *) 0, *prop_fct = (BFct *) 0;
static BSym	*free_sym = (BSym *) 0;
static NList	*free_n = (NList *) 0;
static Node	*prop_start = (Node *) 0;
static Pool	*free_pool = (Pool *) 0;
static Pool	*pool[512];
static Report	*report = (Report *) 0;
static Rstack	*rstack = (Rstack *) 0, *free_rstack = (Rstack *) 0;
static Stack	*stack = (Stack *) 0, *free_stack = (Stack *) 0, init;
static VList	*free_v = (VList *) 0;
static Var	*free_var = (Var *) 0;
static char	*glob_prop = "uno_check";
static int	ErrCnt = 1;
static int	depth = 0, oid = 0, tabs = 0;

static void	check_prop(Arc *);
static void	end_of_path(void);

extern void	handle_fct(char *);
extern void	add_fct(char *);
extern char	*emalloc(int);

static char *BuiltinCheck[] = {
	": uno_check	0",
	">1>",
	">2>",
	"[select('',1,0) == _true_]",		/* if (select("", DEF, NONE)) */
	">3>",
	"[mark(1)]",				/*	mark(1);                 */
	">4>",
	"[select('',68,0) == _true_]",		/* if (select("", USE|DEREF, NONE)) */
	">5>",
	"[match(1,1,0) == _true_]",		/* if (match(1, DEF, NONE))    */
	">6>",
	"[no_error()]",				/*	no_error();              */
	"<5<",
	"<4<",
	">7>",
	"[match(1,1,0) == _false_]",		/* else */
	">8>",
	"[known_nonzero() == _true_]",		/*	if (known_nonzero()) */
	"{6}",
	"[no_error()]",				/*		no_error();  */
	"<8<",
	"<7<",
	">9>",
	"[known_nonzero() == _false_]",		/* 	else                 */
	"{6}",
	"[error('possible global use or deref before def')]", /*	error(); */
	"<9<",
	"<7<",
	"<4<",
	"<3<",
	"{6}",
	"[select('',68,0) == _false_]",
	"<3<",
	"<2<",
	"<1<",
	"{3}",
	"[select('',1,0) == _false_]",
	"<1<",
	"<0<",
	0
};

static void
builtin_check(void)
{	int i;

	add_fct(glob_prop);
	for (i = 0; BuiltinCheck[i]; i++)
		handle_fct(BuiltinCheck[i]);
}

static char *
new_str(char *s)
{	Pool *p;
	char *t;
	int n;

	n = strlen(s);
	if (n > 0 && n < 512 && pool[n])
	{	p = pool[n];
		pool[n] = p->nxt;
		p->nxt = free_pool;
		free_pool = p;
		t = p->s;
	} else
		t = (char *) emalloc(n+1);
	strcpy(t, s);
	return t;
}

static Var *
new_var(char *s)
{	Var *f;

	if (free_var)
	{	f = free_var;
		free_var = f->nxt;
		memset(f, 0, sizeof(Var));
	} else
		f = (Var *) emalloc(sizeof(Var));

	f->s = new_str(s);
	return f;
}

static BSym *
new_sym(char *s)
{	BSym *f;

	if (free_sym)
	{	f = free_sym;
		free_sym = f->nxt;
		memset(f, 0, sizeof(BSym));
	} else
		f = (BSym *) emalloc(sizeof(BSym));

	f->s = new_str(s);
	return f;
}

static BSym *
rev_symrel(BSym *s)
{	int n;

	if (!s) return (BSym *) 0;
	rev_symrel(s->nxt);

	n = strlen(s->s);
	if (n > 0 && n < 512)
	{	Pool *p;
		if (free_pool)
		{	p = free_pool;
			free_pool = p->nxt;
			memset(p, 0, sizeof(Pool));
		} else
			p = (Pool *) emalloc(sizeof(Pool));
		p->s = s->s;
		p->nxt = pool[n];
		pool[n] = p;
	}
	s->s = (char *) 0;

	s->nxt = free_sym;
	free_sym = s;

	return (BSym *) 0;
}

static Var *
rev_release(Var *v)
{	int n;

	if (!v) return (Var *) 0;
	rev_release(v->nxt);

	n = strlen(v->s);
	if (n > 0 && n < 512)
	{	Pool *p;
		if (free_pool)
		{	p = free_pool;
			free_pool = p->nxt;
			memset(p, 0, sizeof(Pool));
		} else
			p = (Pool *) emalloc(sizeof(Pool));
		p->s = v->s;
		p->nxt = pool[n];
		pool[n] = p;
	}
	v->s = (char *) 0;

	v->nxt = free_var;
	free_var = v;

	return (Var *) 0;
}

static BFct *
find_function(char *s)
{	BFct *f;

	for (f = fcts; f; f = f->nxt)
		if (strcmp(f->fnm, s) == 0)
			return f;
	return (BFct *) 0;
}

void
add_fct(char *s)
{	BFct *f;

	if (0 && debug) printf("adding fct %s\n", s);

	for (f = fcts; f; f = f->nxt)
		if (strcmp(f->fnm, s) == 0)
			return;	/* reported in uno_global.c */

	f = (BFct *) emalloc(sizeof(BFct));
	f->fnm = new_str(s);
	f->nxt = fcts;
	fcts = f;

	f->root = (Node *) emalloc(sizeof(Node));
	f->root->nid = 0;
	return;
}

void
add_call(char *fnm, char *c)
{	BFct *f;
	BSym *s;

	f = find_function(fnm);
	if (!f)
	{	fprintf(stderr, "error: bad input sequence (%s)\n",
			fnm);
		exit(1);
	}

	for (s = f->calls; s; s = s->nxt)
		if (strcmp(s->s, c) == 0)
			return;

	s = (BSym *) emalloc(sizeof(BSym));
	s->s = new_str(c);
	s->nxt = f->calls;
	f->calls = s;
}

static Node *
find_node(BFct *f, int id)
{	Node *n;

	for (n = f->root; n; n = n->nxt)
		if (n->nid == id)
			break;

	if (!n)
	{	n = (Node *) emalloc(sizeof(Node));
		n->nid  = id;
		n->nxt  = f->root;
		f->root = n;
	}
	return n;
}

static Arc *
add_arc(BFct *f, int from, int to)
{	Arc *a;
	Node *n;

	a = (Arc *) emalloc(sizeof(Arc));
	n = find_node(f, from);
	a->to   = find_node(f, to);
	a->nxt  = n->succ;
	n->succ = a;

	return a;
}

static void
add_label(BFct *f, Arc *a, char *s)
{	Label *n;
	char  *p;

	while (p = strchr(s, '\t'))
		*p = ' ';

	n = (Label *) emalloc(sizeof(Label));
	n->label = new_str(s);

	if (strcmp(f->fnm, glob_prop) == 0)
	{	n->nxt = a->lab;	/* prop: labels on arcs */
		a->lab = n;
		return;
	} else
	{	n->nxt = a->to->lab;	/* sys: labels on nodes */
		a->to->lab = n;
	}

	if (strlen(s) <= 2)
		return;

	switch (s[1]) {
	case ' ':	p = strchr(&s[2], ' '); break;
	case '\t':	p = strchr(&s[2], '\t'); break;
	default:
bad:		fprintf(stderr, "uno:global: unexpected type of label: '%s'\n", s);
		return;
	}

	if (!p) goto bad;
	*p = '\0';
	switch (s[0]) {
	case 'C': 
	case 'c': 
	case 'b': 
	case 'h': 
	case 'i': 
	case 'j':
		/* add_call(f->fnm, &s[2]); */
		break;
	case 'N':
	case 'G':
	case 'D':
	case 'U':
	case 'R': break;
	default : goto bad;
	}
	*p = ' ';	/* restore */
}

static void
ini_prop(void)
{	Node *n;

	prop_fct = find_function(glob_prop);
	if (!prop_fct)
	{	if (verbose)
			printf("uno:global: using builtin property check\n");
		builtin_check();
		prop_fct = find_function(glob_prop);
		if (!prop_fct)
		{	fprintf(stderr, "uno:global: error, could not load builtin property\n");
			exit(1);
		}
	}
	n = find_node(prop_fct, 0);
	prop_start = n->succ->to;
}

static BFct *
fct_in_lab(char *s)
{	BFct *f = (BFct *) 0;
	char *t;

	for (t = s+2; *t != '\0' && *t != ' '; t++)
		;

	if (*t == ' ')
	{	*t = '\0';
		f = find_function(s+2); /* 2 char prefix */
		*t = ' ';
	}
	return f;
}

static int
n_reported(Stack *s)
{	Report *r;
	int n;

	if (s && s->move && s->move->to)
		n = s->move->to->nid;
	else
		return 0;

	for (r = report; r; r = r->nxt)
		if (r->n > n-3
		&&  r->n < n+3)	/* within a range of subsequent states */
			return 1;
	r = (Report *) emalloc(sizeof(Report));
	r->n = n;
	r->nxt = report;
	report = r;

	if (debug) printf("NID=%d\n", n);

	return 0;
}

static int
print_fnm(Rstack *s, char *p)
{
	if (!s) return 0;

	if (s->n && s->n->lab)
		printf("	%s %s\n", p, &s->n->lab->label[2]);
	else if (strcmp(s->f->fnm, "_global_") != 0)
		printf("	%s %s()\n", p, s->f->fnm);
	return 1;
}

static void
print_rstack(Rstack *s, char *p)
{
	if (print_fnm(s, p))
		print_rstack(s->nxt, p);
}

static void
print_stack(Stack *s, int d)
{	Arc *a;
	int i;

	if (!s) return;
	print_stack(s->nxt, d-1);

	a = s->move;

	if (a
	&&  a->to->lab
	&&  strlen(a->to->lab->label) > 0)
	{	for (i = 0; i < tabs; i++)
			printf("   ");
		printf("%3d:\t[%d]\t%s\n", d,
			a->to->nid, a->to->lab->label);
	}

	if (s->fc)
	{	tabs++;
		for (i = 0; i < tabs; i++)
			printf("   ");
		printf("%3d: BFct call to %s\n", d, s->fc->fnm);
	}
	if (s->fr)
	{	for (i = 0; i < tabs; i++)
			printf("   ");
		tabs--;
		printf("%3d: Return to %s\n", d, s->fr->fnm);
	}
}

static void
do_fct_call(BFct *f, Node *sys)
{	Rstack *r, *or;
	BFct *g;
	BSym *s;
	Node *n;

	f->visited = 1;	/* prevent fct call cycles */

	if (free_rstack)
	{	r = free_rstack;
		free_rstack = free_rstack->nxt;
		memset(r, 0, sizeof(Rstack));
	} else
		r = (Rstack *) emalloc(sizeof(Rstack));

	r->f = f;
	r->n = sys;	/* continuation point for return from fct in end_of_path */
	r->nxt = rstack;
	rstack = r;

	stack->fc = f;	/* remember for error trace */

	n = find_node(f, 0);
	if (n && n->succ)
	{	if (debug) printf("%3d: dive in\n", depth);
		check_prop(n->succ);
		if (debug) printf("%3d: undive\n", depth);
	} else
	{	if (debug) printf("%3d: no visible operations (calls: %u)\n", depth, f->calls);

		/* if we're here, then probably f->calls is also nil, or else
		 * there would be an abstract call graph for this fct with the
		 * call points recorded...
		 */

		if (!f->calls)	/* expected */
		{	end_of_path();	/* continuation with sys */
		} else
		{	fprintf(stderr, "%3d: unexpected...\n", depth);
			for (s = f->calls; s; s = s->nxt)
			{	g = find_function(s->s);
				if (g && !g->visited)
				{	if (debug) printf("	ByPass Call on %s\n", s->s);
					do_fct_call(g, (Node *) 0); /* no continuation within this fct */
					if (debug) printf("	Return from ByPass Call on %s\n", s->s);
	}	}	}	}

	stack->fc = (BFct *) 0;

	or = rstack;
	rstack = rstack->nxt;
	or->nxt = free_rstack;
	free_rstack = or;

	f->visited = 0;
}

static int
same_markings(Vis *v)
{	Var   *p;
	VList *q;
	int cnt = 0;

	if (!v->v && !stack->sels)
	{	if (v->zeromarks)
			return 1;
		v->zeromarks = 1;
		return 0;
	}

	for (p = stack->sels; p; p = p->nxt)
	{	for (q = v->v; q; q = q->nxt)
		{	if (strcmp(q->v->s, p->s) == 0
			&&  q->v->mark == p->mark)
				break;
		}
		if (!q)	/* add p */
		{	if (free_v)
			{	q = free_v;
				free_v = q->nxt;
				memset(q, 0, sizeof(VList));
			} else
				q = (VList *) emalloc(sizeof(VList));
			
			q->v = new_var(p->s);
			q->v->mark = p->mark;
			q->nxt = v->v;
			v->v = q;
			cnt++;
	}	}

	return (cnt == 0);
}

static int
same_callpts(Vis *v)
{	Rstack *p;
	NList *q;
	int cnt = 0;

	if (!v->r && !rstack)
	{	if (v->zerostack)
			return 1;
		v->zerostack = 1;
		return 0;
	}

	for (p = rstack; p; p = p->nxt)
	{	for (q = v->r; q; q = q->nxt)
		{	if (p->n == q->n)
				break;
		}
		if (!q)	/* add p->n */
		{	if (free_v)
			{	q = free_n;
				free_n = q->nxt;
				memset(q, 0, sizeof(NList));
			} else
				q = (NList *) emalloc(sizeof(NList));
			q->n = p->n;
			q->nxt = v->r;
			v->r = q;
			cnt++;
	}	}

	return (cnt == 0);
}

static int
same_unostate(Vis *v)
{
	if (v->uno_state & (1<<stack->uno_state))
		return 1;
	v->uno_state |= (1<<stack->uno_state);
	return 0;
}

static int
same_state(Arc *in)
{	Stack	*s;
	Var	*e, *f;
	BSym	*x, *y;
	Node	*sys = in->to;

	if (!sys->vis)
		sys->vis = (Vis *) emalloc(sizeof(Vis));

	if (same_unostate(sys->vis)
	&&  same_callpts(sys->vis)
	&&  same_markings(sys->vis))
		return 1;			/* been here before with that state */

	if (free_stack)
	{	s = free_stack;
		free_stack = s->nxt;
		memset(s, 0, sizeof(Stack));
	} else
		s = (Stack *) emalloc(sizeof(Stack));
	s->move = in;
	s->uno_state = stack->uno_state;

	for (e = stack->sels; e; e = e->nxt)		/* copy marked vars forward */
	{	f = new_var(e->s);
		f->loc = e->loc;
		f->sel = 0;
		f->stat = e->stat;
		f->mark = e->mark;
		f->nxt = s->sels;
		s->sels = f;
	}
	for (x = stack->knz; x; x = x->nxt)
	{	y = new_sym(x->s);
		y->nxt = s->knz;
		s->knz = y;
	}

	s->nxt = stack;
	stack = s;					/* stack trace for error reports */

	return 0;
}

static void
end_of_path(void)
{	Arc	*a;
	Rstack	*r;

	if (!rstack) return;

	r = rstack;
	rstack = rstack->nxt;

	stack->fr = rstack?rstack->f:(BFct *) 0;	/* remember for error traces */

	if (debug)
	printf("%3d:\tFCT EXITS -- %s -- return to %s\n", depth,
		r->f->fnm, rstack?rstack->f->fnm:"--");

	if (!r->n || !r->n->succ)		/* no continuation point */
	{	if (debug) printf("%3d: no continuation point\n", depth);
		end_of_path();			/* ? */
	} else
		for (a = r->n->succ; a; a = a->nxt)	/* continuation in caller */
		{	if (debug) printf("%3d:\tCONTinuation in %s [%d->%d]\n", depth,
				rstack?rstack->f->fnm:"--", r->n->nid, a->to->nid);
			check_prop(a);
			if (debug) printf("%3d:\tUN_CONT %s [%d->%d]\n", depth,
				rstack?rstack->f->fnm:"--", a->to->nid, r->n->nid);
		}
	r->nxt = rstack;
	rstack = r;

	stack->fr = (BFct *) 0;

	if (debug)
	printf("%3d:\tFCT UN_EXITS -- %s\n", depth, r->f->fnm);
}

static void
f2d_assert(int p, char *s)
{
	if (!p)
	{	printf("uno:global: %s\n", s);
		exit(1);
	}
}

static int
has_fct_match(Label *n, Label *m)
{	char *p, *q = (char *) 0, *r, *s = (char *) 0;
	char took = '(';
	char c = '\"';
	int t;

	if (strncmp(n->label, "C ", strlen("C ")) == 0
	||  strncmp(n->label, "c ", strlen("c ")) == 0)
	{	/* either: fct_call("qlock()") or fct_call("qlock") */
		p = strchr(m->label, c);	/* start of fct name */