From dbaaafa705ca548059aac958082776f219b2daef Mon Sep 17 00:00:00 2001 From: "Angelos D. Keromytis" Date: Sun, 23 May 1999 22:11:10 +0000 Subject: KeyNote version 2 trust-management system (security policy handling). Utilities to follow. --- lib/libkeynote/keynote.y | 899 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 899 insertions(+) create mode 100644 lib/libkeynote/keynote.y (limited to 'lib/libkeynote/keynote.y') diff --git a/lib/libkeynote/keynote.y b/lib/libkeynote/keynote.y new file mode 100644 index 00000000000..ca6c3fbf066 --- /dev/null +++ b/lib/libkeynote/keynote.y @@ -0,0 +1,899 @@ +/* $OpenBSD: keynote.y,v 1.1 1999/05/23 22:11:05 angelos Exp $ */ + +/* + * The author of this code is Angelos D. Keromytis (angelos@dsl.cis.upenn.edu) + * + * This code was written by Angelos D. Keromytis in Philadelphia, PA, USA, + * in April-May 1998 + * + * Copyright (C) 1998, 1999 by Angelos D. Keromytis. + * + * Permission to use, copy, and modify this software without fee + * is hereby granted, provided that this entire notice is included in + * all copies of any software which is or includes a copy or + * modification of this software. + * + * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR + * IMPLIED WARRANTY. IN PARTICULAR, THE AUTHORS MAKES NO + * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE + * MERCHANTABILITY OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR + * PURPOSE. + */ +%union { + char *string; + double doubval; + int intval; + int bool; +}; +%type stringexp numexp expr floatexp +%type NUM KOF numex afterhint notemptyprog +%type notemptykeypredicate prog key keyexp keylist +%type FLOAT floatex +%type STRING VARIABLE str strnotconcat +%token TRUE FALSE NUM FLOAT STRING VARIABLE +%token OPENPAREN CLOSEPAREN EQQ COMMA ACTSTR LOCINI KOF KEYPRE KNVERSION +%token DOTT SIGNERKEY HINT OPENBLOCK CLOSEBLOCK SIGNATUREENTRY PRIVATEKEY +%token SEMICOLON TRUE FALSE +%nonassoc EQ NE LT GT LE GE REGEXP +%left OR +%left AND +%right NOT +%left PLUS MINUS DOTT +%left MULT DIV MOD +%left EXP +%nonassoc UNARYMINUS DEREF OPENNUM OPENFLT +%start grammarswitch +%{ +#include +#include +#include +#include +#include +#include +#include +#include "environment.h" +#include "signature.h" + +static int *keynote_kth_array = (int *) NULL; +static int keylistcount = 0; + +static int resolve_assertion(char *); +static int keynote_init_kth(void); +static int isfloatstring(char *); +static int checkexception(int); +static char *my_lookup(char *); +static int intpow(int, int); +static int get_kth(int); + +extern int keynote_in_action_authorizers(void *, int); +extern int knlex(); + +extern int keynote_exceptionflag, keynote_donteval; +extern char **keynote_values, *keynote_privkey; +extern struct keylist *keynote_keypred_keylist; +extern struct environment *keynote_temp_list; +extern struct environment *keynote_init_list; +extern int knlineno, keynote_used_variable; + +void knerror(char *); +%} +%% + +grammarswitch: LOCINI { keynote_exceptionflag = keynote_donteval = 0; } + localinit + | ACTSTR { keynote_exceptionflag = keynote_donteval = 0; } program + | KEYPRE { keynote_exceptionflag = keynote_donteval = 0; } + keypredicate + | SIGNERKEY { keynote_exceptionflag = keynote_donteval = 0; } key + | SIGNATUREENTRY { keynote_exceptionflag = keynote_donteval = 0; } + key + | KNVERSION { keynote_exceptionflag = keynote_donteval = 0; } + STRING { keynote_lex_remove($3); + if (strcmp($3, KEYNOTE_VERSION_STRING)) + keynote_errno = ERROR_SYNTAX; + free($3); + } + | PRIVATEKEY { keynote_exceptionflag = keynote_donteval = 0; } + STRING { keynote_lex_remove($3); + keynote_privkey = $3; + } + +keypredicate: /* Nothing */ { keynote_returnvalue = 0; + return 0; + } + | notemptykeypredicate { keynote_returnvalue = $1; + return 0; + } + +notemptykeypredicate: key { $$ = $1; } + | keyexp { $$ = $1; } + +keyexp: notemptykeypredicate AND { if (($1 == 0) && !keynote_justrecord) + keynote_donteval = 1; + } notemptykeypredicate + { if ($1 > $4) + $$ = $4; + else + $$ = $1; + keynote_donteval = 0; + } /* Min */ + | notemptykeypredicate OR { if (($1 == (keynote_current_session->ks_values_num - 1)) && !keynote_justrecord) + keynote_donteval = 1; + } notemptykeypredicate + { if ($1 >= $4) + $$ = $1; + else + $$ = $4; + keynote_donteval = 0; + } /* Max */ + | OPENPAREN keyexp CLOSEPAREN { $$ = $2; } + | KOF { keylistcount = 0; } OPENPAREN { + if (!keynote_justrecord && !keynote_donteval) + if (keynote_init_kth() == -1) + return -1; + } keylist CLOSEPAREN + { + if (keylistcount < $1) + { + keynote_errno = ERROR_SYNTAX; + return -1; + } + + if (!keynote_justrecord && !keynote_donteval) + $$ = get_kth($1); + else + $$ = 0; + } /* K-th */ + +keylist: key + { /* Don't do anything if we're just recording */ + if (!keynote_justrecord && !keynote_donteval) + if (($1 < keynote_current_session->ks_values_num) && ($1 >= 0)) + keynote_kth_array[$1]++; + + keylistcount++; + } + | key COMMA keylist + { /* Don't do anything if we're just recording */ + if (!keynote_justrecord && !keynote_donteval) + if (($1 < keynote_current_session->ks_values_num) && ($1 >= 0)) + keynote_kth_array[$1]++; + + keylistcount++; + } + +key: str { + if (keynote_donteval) + $$ = 0; + else + { + keynote_lex_remove($1); + if (keynote_justrecord) + { + if (keynote_keylist_add(&keynote_keypred_keylist, + $1) == -1) + { + free($1); + return -1; + } + + $$ = 0; + } + else + switch (keynote_in_action_authorizers($1, KEYNOTE_ALGORITHM_UNSPEC)) + { + case -1: + free($1); + return -1; + + case RESULT_TRUE: + free($1); + $$ = keynote_current_session->ks_values_num - + 1; + break; + + default: + $$ = resolve_assertion($1); + free($1); + break; + } + } + } + +localinit: /* Nothing */ + | localconstants + +localconstants: VARIABLE EQQ STRING + { + int i; + + keynote_lex_remove($1); + keynote_lex_remove($3); + + /* + * Variable names starting with underscores are illegal here. + */ + if ($1[0] == '_') + { + free($1); + free($3); + keynote_errno = ERROR_SYNTAX; + return -1; + } + + /* If the identifier already exists, report error. */ + if (keynote_env_lookup($1, &keynote_init_list, 1) != (char *) NULL) + { + free($1); + free($3); + keynote_errno = ERROR_SYNTAX; + return -1; + } + + i = keynote_env_add($1, $3, &keynote_init_list, 1, 0); + free($1); + free($3); + + if (i != RESULT_TRUE) + return -1; + } + | VARIABLE EQQ STRING + { + int i; + + keynote_lex_remove($1); + keynote_lex_remove($3); + + /* + * Variable names starting with underscores are illegal here. + */ + if ($1[0] == '_') + { + free($1); + free($3); + keynote_errno = ERROR_SYNTAX; + return -1; + } + + /* If the identifier already exists, report error. */ + if (keynote_env_lookup($1, &keynote_init_list, 1) != (char *) NULL) + { + free($1); + free($3); + keynote_errno = ERROR_SYNTAX; + return -1; + } + + i = keynote_env_add($1, $3, &keynote_init_list, 1, 0); + free($1); + free($3); + + if (i != RESULT_TRUE) + return -1; + } localconstants + +program: prog { + keynote_returnvalue = $1; + return 0; + } + +prog: /* Nada */ { $$ = 0; } + | notemptyprog { + /* + * Cleanup envlist of additions such as + * regexp results + */ + keynote_env_cleanup(&keynote_temp_list, 1); + } SEMICOLON prog + { + if ($1 > $4) + $$ = $1; + else + $$ = $4; + } + +notemptyprog: expr HINT afterhint + { + if (checkexception($1)) + $$ = $3; + else + $$ = 0; + } + | expr + { + if (checkexception($1)) + $$ = keynote_current_session->ks_values_num - 1; + else + $$ = 0; + } + +afterhint: str { if (keynote_exceptionflag || keynote_donteval) + $$ = 0; + else + { + keynote_lex_remove($1); + + $$ = keynote_retindex($1); + if ($$ == -1) /* Invalid return value */ + $$ = 0; + + free($1); + } + } + | OPENBLOCK prog CLOSEBLOCK { $$ = $2; } + + +expr: OPENPAREN expr CLOSEPAREN { $$ = $2; } + | expr AND { if ($1 == 0) + keynote_donteval = 1; + } expr { $$ = ($1 && $4); + keynote_donteval = 0; + } + | expr OR { if ($1) + keynote_donteval = 1; + } expr { $$ = ($1 || $4); + keynote_donteval = 0; + } + | NOT expr { $$ = !($2); } + | numexp { $$ = $1; } + | floatexp { $$ = $1; } + | stringexp { $$ = $1; } + | TRUE { $$ = 1; } + | FALSE { $$ = 0; } + +numexp: numex LT numex { $$ = $1 < $3; } + | numex GT numex { $$ = $1 > $3; } + | numex EQ numex { $$ = $1 == $3; } + | numex LE numex { $$ = $1 <= $3; } + | numex GE numex { $$ = $1 >= $3; } + | numex NE numex { $$ = $1 != $3; } + +floatexp: floatex LT floatex { $$ = $1 < $3; } + | floatex GT floatex { $$ = $1 > $3; } + | floatex LE floatex { $$ = $1 <= $3; } + | floatex GE floatex { $$ = $1 >= $3; } + +numex: numex PLUS numex { $$ = $1 + $3; } + | numex MINUS numex { $$ = $1 - $3; } + | numex MULT numex { $$ = $1 * $3; } + | numex DIV numex { if ($3 == 0) + { + if (!keynote_donteval) + keynote_exceptionflag = 1; + } + else + $$ = ($1 / $3); + } + | numex MOD numex { if ($3 == 0) + { + if (!keynote_donteval) + keynote_exceptionflag = 1; + } + else + $$ = $1 % $3; + } + | numex EXP numex { $$ = intpow($1, $3); } + | MINUS numex %prec UNARYMINUS { $$ = -($2); } + | OPENPAREN numex CLOSEPAREN { $$ = $2; } + | NUM { $$ = $1; } + | OPENNUM strnotconcat { if (keynote_exceptionflag || + keynote_donteval) + $$ = 0; + else + { + keynote_lex_remove($2); + + if (!isfloatstring($2)) + $$ = 0; + else + $$ = (int) floor(atof($2)); + free($2); + } + } + +floatex: floatex PLUS floatex { $$ = ($1 + $3); } + | floatex MINUS floatex { $$ = ($1 - $3); } + | floatex MULT floatex { $$ = ($1 * $3); } + | floatex DIV floatex { if ($3 == 0) + { + if (!keynote_donteval) + keynote_exceptionflag = 1; + } + else + $$ = ($1 / $3); + } + | floatex EXP floatex { if (!keynote_exceptionflag && + !keynote_donteval) + $$ = pow($1, $3); + } + | MINUS floatex %prec UNARYMINUS { $$ = -($2); } + | OPENPAREN floatex CLOSEPAREN { $$ = $2; } + | FLOAT { $$ = $1; } + | OPENFLT strnotconcat { + if (keynote_exceptionflag || + keynote_donteval) + $$ = 0.0; + else + { + keynote_lex_remove($2); + + if (!isfloatstring($2)) + $$ = 0.0; + else + $$ = atof($2); + free($2); + } + } + +stringexp: str EQ str { + if (keynote_exceptionflag || keynote_donteval) + $$ = 0; + else + { + $$ = strcmp($1, $3) == 0 ? 1 : 0; + keynote_lex_remove($1); + keynote_lex_remove($3); + free($1); + free($3); + } + } + | str NE str { + if (keynote_exceptionflag || keynote_donteval) + $$ = 0; + else + { + $$ = strcmp($1, $3) != 0 ? 1 : 0; + keynote_lex_remove($1); + keynote_lex_remove($3); + free($1); + free($3); + } + } + | str LT str { + if (keynote_exceptionflag || keynote_donteval) + $$ = 0; + else + { + $$ = strcmp($1, $3) < 0 ? 1 : 0; + keynote_lex_remove($1); + keynote_lex_remove($3); + free($1); + free($3); + } + } + | str GT str { + if (keynote_exceptionflag || keynote_donteval) + $$ = 0; + else + { + $$ = strcmp($1, $3) > 0 ? 1 : 0; + keynote_lex_remove($1); + keynote_lex_remove($3); + free($1); + free($3); + } + } + | str LE str { + if (keynote_exceptionflag || keynote_donteval) + $$ = 0; + else + { + $$ = strcmp($1, $3) <= 0 ? 1 : 0; + keynote_lex_remove($1); + keynote_lex_remove($3); + free($1); + free($3); + } + } + | str GE str { + if (keynote_exceptionflag || keynote_donteval) + $$ = 0; + else + { + $$ = strcmp($1, $3) >= 0 ? 1 : 0; + keynote_lex_remove($1); + keynote_lex_remove($3); + free($1); + free($3); + } + } + | str REGEXP str + { + regmatch_t pmatch[32]; + char grp[4], *gr; + regex_t preg; + int i; + + if (keynote_exceptionflag || keynote_donteval) + $$ = 0; + else + { + keynote_lex_remove($1); + keynote_lex_remove($3); + + memset(pmatch, 0, sizeof(pmatch)); + memset(grp, 0, sizeof(grp)); + + if (regcomp(&preg, $3, REG_EXTENDED)) + { + free($1); + free($3); + keynote_exceptionflag = 1; + } + else + { + /* Clean-up residuals from previous regexps */ + keynote_env_cleanup(&keynote_temp_list, 1); + + free($3); + i = regexec(&preg, $1, 32, pmatch, 0); + $$ = (i == 0 ? 1 : 0); + if (i == 0) + { +#ifdef NO_SNPRINTF + sprintf(grp, "%d", preg.re_nsub); +#else /* NO_SNPRINTF */ + snprintf(grp, 3, "%d", preg.re_nsub); +#endif /* NO_SNPRINTF */ + if (keynote_env_add("_0", grp, &keynote_temp_list, + 1, 0) != RESULT_TRUE) + { + free($1); + regfree(&preg); + return -1; + } + + for (i = 1; i < 32 && pmatch[i].rm_so != -1; i++) + { + gr = calloc(pmatch[i].rm_eo - pmatch[i].rm_so + + 1, sizeof(char)); + if (gr == (char *) NULL) + { + free($1); + regfree(&preg); + keynote_errno = ERROR_MEMORY; + return -1; + } + + strncpy(gr, $1 + pmatch[i].rm_so, + pmatch[i].rm_eo - pmatch[i].rm_so); + gr[pmatch[i].rm_eo - pmatch[i].rm_so] = '\0'; +#ifdef NO_SNPRINTF + sprintf(grp, "_%d", i); +#else /* NO_SNPRINTF */ + snprintf(grp, 3, "_%d", i); +#endif /* NO_SNPRINTF */ + if (keynote_env_add(grp, gr, &keynote_temp_list, + 1, 0) == -1) + { + free($1); + regfree(&preg); + free(gr); + return -1; + } + else + free(gr); + } + } + + regfree(&preg); + free($1); + } + } + } + +str: str DOTT str { if (keynote_exceptionflag || keynote_donteval) + $$ = (char *) NULL; + else + { + $$ = calloc(strlen($1) + strlen($3) + 1, + sizeof(char)); + keynote_lex_remove($1); + keynote_lex_remove($3); + if ($$ == (char *) NULL) + { + free($1); + free($3); + keynote_errno = ERROR_MEMORY; + return -1; + } + + strcpy($$, $1); + strcpy($$ + strlen($1), $3); + free($1); + free($3); + if (keynote_lex_add($$, LEXTYPE_CHAR) == -1) + return -1; + } + } + | strnotconcat { $$ = $1; } + +strnotconcat: STRING { $$ = $1; } + | OPENPAREN str CLOSEPAREN { $$ = $2; } + | VARIABLE { if (keynote_exceptionflag || keynote_donteval) + $$ = (char *) NULL; + else + { + $$ = my_lookup($1); + keynote_lex_remove($1); + free($1); + if ($$ == (char *) NULL) + { + if (keynote_errno) + return -1; + $$ = strdup(""); + } + else + $$ = strdup($$); + + if ($$ == (char *) NULL) + { + keynote_errno = ERROR_MEMORY; + return -1; + } + + if (keynote_lex_add($$, LEXTYPE_CHAR) == -1) + return -1; + } + } + | DEREF str { if (keynote_exceptionflag || keynote_donteval) + $$ = (char *) NULL; + else + { + $$ = my_lookup($2); + keynote_lex_remove($2); + free($2); + if ($$ == (char *) NULL) + { + if (keynote_errno) + return -1; + $$ = strdup(""); + } + else + $$ = strdup($$); + + if ($$ == (char *) NULL) + { + keynote_errno = ERROR_MEMORY; + return -1; + } + + if (keynote_lex_add($$, LEXTYPE_CHAR) == -1) + return -1; + } + } +%% + +/* + * Find all assertions signed by s and give us the one with the highest + * return value. + */ +static int +resolve_assertion(char *s) +{ + int i, alg = KEYNOTE_ALGORITHM_NONE, p = 0; + void *key = (void *) s; + struct assertion *as; + struct keylist *kl; + + kl = keynote_keylist_find(keynote_current_assertion->as_keylist, s); + if (kl != (struct keylist *) NULL) + { + alg = kl->key_alg; + key = kl->key_key; + } + + for (i = 0;; i++) + { + as = keynote_find_assertion(key, i, alg); + if (as == (struct assertion *) NULL) /* Gone through all of them */ + return p; + + if (as->as_kresult == KRESULT_DONE) + if (p < as->as_result) + p = as->as_result; + + /* Short circuit if we find an assertion with maximum return value */ + if (p == (keynote_current_session->ks_values_num - 1)) + return p; + } + + return 0; +} + +/* + * Environment variable lookup. + */ +static char * +my_lookup(char *s) +{ + struct keynote_session *ks = keynote_current_session; + char *ret; + + if (!strcmp(s, "_MIN_TRUST")) + { + keynote_used_variable = 1; + return ks->ks_values[0]; + } + else + { + if (!strcmp(s, "_MAX_TRUST")) + { + keynote_used_variable = 1; + return ks->ks_values[ks->ks_values_num - 1]; + } + else + { + if (!strcmp(s, "_VALUES")) + { + keynote_used_variable = 1; + return keynote_env_lookup("_VALUES", ks->ks_env_table, + HASHTABLESIZE); + } + else + { + if (!strcmp(s, "_ACTION_AUTHORIZERS")) + { + keynote_used_variable = 1; + return keynote_env_lookup("_ACTION_AUTHORIZERS", + ks->ks_env_table, HASHTABLESIZE); + } + } + } + } + + /* Temporary list (regexp results) */ + ret = keynote_env_lookup(s, &keynote_temp_list, 1); + if (ret != (char *) NULL) + return ret; + else + if (keynote_errno != 0) + return (char *) NULL; + + /* Local-Constants */ + ret = keynote_env_lookup(s, &keynote_init_list, 1); + if (ret != (char *) NULL) + return ret; + else + if (keynote_errno != 0) + return (char *) NULL; + + keynote_used_variable = 1; + + /* Action environment */ + ret = keynote_env_lookup(s, ks->ks_env_table, HASHTABLESIZE); + if (ret != (char *) NULL) + return ret; + else + if (keynote_errno != 0) + return (char *) NULL; + + /* Regex table */ + return keynote_env_lookup(s, &(ks->ks_env_regex), 1); +} + +/* + * If we had an exception, the boolean expression should return false. + * Otherwise, return the result of the expression (the argument). + */ +static int +checkexception(int i) +{ + if (keynote_exceptionflag) + { + keynote_exceptionflag = 0; + return 0; + } + else + return i; +} + + +/* + * Integer exponentation -- copied from Schneier's AC2, page 244. + */ +static int +intpow(int x, int y) +{ + int s = 1; + + /* + * x^y with y < 0 is equivalent to 1/(x^y), which for + * integer arithmetic is 0. + */ + if (y < 0) + return 0; + + while (y) + { + if (y & 1) + s *= x; + + y >>= 1; + x *= x; + } + + return s; +} + +/* + * Check whether the string is a floating point number. + */ +static int +isfloatstring(char *s) +{ + int i, point = 0; + + for (i = strlen(s) - 1; i >= 0; i--) + if (!isdigit(s[i])) + { + if (s[i] == '.') + { + if (point == 1) + return 0; + else + point = 1; + } + else + return 0; + } + + return 1; +} + +/* + * Initialize array for threshold search. + */ +static int +keynote_init_kth(void) +{ + int i = keynote_current_session->ks_values_num; + + if (i == -1) + return -1; + + keynote_kth_array = (int *) calloc(i, sizeof(int)); + if (keynote_kth_array == (int *) NULL) + { + keynote_errno = ERROR_MEMORY; + return -1; + } + + return RESULT_TRUE; +} + +/* + * Get the k-th best return value. + */ +static int +get_kth(int k) +{ + int i; + + for (i = keynote_current_session->ks_values_num - 1; i >= 0; i--) + { + k -= keynote_kth_array[i]; + + if (k <= 0) + return i; + } + + return 0; +} + +/* + * Cleanup array. + */ +void +keynote_cleanup_kth(void) +{ + if (keynote_kth_array != (int *) NULL) + { + free(keynote_kth_array); + keynote_kth_array = (int *) NULL; + } +} + +void +knerror(char *s) +{} -- cgit v1.2.3