From: Dan Carpenter Date: Fri, 12 Oct 2012 07:55:55 +0000 (+0300) Subject: absolute: track the absolute limits that variables can be X-Git-Tag: 1.57~211 X-Git-Url: https://repo.or.cz/w/smatch.git/commitdiff_plain/4c8dacd2d919092fcbeab4fde6b72218a0ac5f98 absolute: track the absolute limits that variables can be If you have an assignment like this "int x = (unsigned char)y;" then you know that x is a number between 0-255. This is to track those kinds of things. smatch_extra.c tracks some of these things right now, but it's not really the right thing. Smatch extra should be tracking stronger implications. Tracking this stuff in Smatch extra leads to buffer overflow false positives. Signed-off-by: Dan Carpenter --- diff --git a/Makefile b/Makefile index cea7ac3f..c6599548 100644 --- a/Makefile +++ b/Makefile @@ -48,7 +48,8 @@ SMATCH_FILES=smatch_flow.o smatch_conditions.o smatch_slist.o smatch_states.o \ smatch_ranges.o smatch_implied.o smatch_ignore.o smatch_project.o \ smatch_tracker.o smatch_files.o smatch_expression_stacks.o \ smatch_constraints.o smatch_buf_size.o smatch_capped.o smatch_db.o \ - smatch_expressions.o smatch_returns.o smatch_parse_call_math.o + smatch_expressions.o smatch_returns.o smatch_parse_call_math.o \ + smatch_absolute.o SMATCH_CHECKS=$(shell ls check_*.c | sed -e 's/\.c/.o/') SMATCH_DATA=smatch_data/kernel.allocation_funcs smatch_data/kernel.balanced_funcs \ diff --git a/check_debug.c b/check_debug.c index 685e8014..9de1596e 100644 --- a/check_debug.c +++ b/check_debug.c @@ -91,6 +91,36 @@ static void match_print_implied_max(const char *fn, struct expression *expr, voi free_string(name); } +static void match_print_absolute_min(const char *fn, struct expression *expr, void *info) +{ + struct expression *arg; + long long val; + char *name; + + arg = get_argument_from_call_expr(expr->args, 0); + if (!get_absolute_min(arg, &val)) + val = whole_range.min; + + name = get_variable_from_expr_complex(arg, NULL); + sm_msg("implied min: %s = %lld", name, val); + free_string(name); +} + +static void match_print_absolute_max(const char *fn, struct expression *expr, void *info) +{ + struct expression *arg; + long long val; + char *name; + + arg = get_argument_from_call_expr(expr->args, 0); + if (!get_absolute_max(arg, &val)) + val = whole_range.max; + + name = get_variable_from_expr_complex(arg, NULL); + sm_msg("implied max: %s = %lld", name, val); + free_string(name); +} + static void print_possible(struct sm_state *sm) { struct sm_state *tmp; @@ -193,6 +223,8 @@ void check_debug(int id) add_function_hook("__smatch_implied", &match_print_implied, NULL); add_function_hook("__smatch_implied_min", &match_print_implied_min, NULL); add_function_hook("__smatch_implied_max", &match_print_implied_max, NULL); + add_function_hook("__smatch_absolute_min", &match_print_absolute_min, NULL); + add_function_hook("__smatch_absolute_max", &match_print_absolute_max, NULL); add_function_hook("__smatch_possible", &match_possible, NULL); add_function_hook("__smatch_cur_slist", &match_cur_slist, NULL); add_function_hook("__smatch_buf_size", &match_buf_size, NULL); diff --git a/check_debug.h b/check_debug.h index 0220a552..c9fced43 100644 --- a/check_debug.h +++ b/check_debug.h @@ -7,6 +7,10 @@ static inline void __smatch_value(const char *unused){} static inline void __smatch_implied(long long val){} static inline void __smatch_implied_min(long long val){} static inline void __smatch_implied_max(long long val){} + +static inline void __smatch_absolute_min(long long val){} +static inline void __smatch_absolute_max(long long val){} + static inline void __smatch_possible(const char *unused){} static inline void __smatch_print_value(const char *unused){} diff --git a/check_list.h b/check_list.h index a4c891a0..b3afb52d 100644 --- a/check_list.h +++ b/check_list.h @@ -4,6 +4,7 @@ #endif CK(register_smatch_extra) /* smatch_extra always has to be first */ +CK(register_absolute) CK(register_modification_hooks) CK(register_definition_db_callbacks) CK(register_project) diff --git a/smatch.h b/smatch.h index 29ebf3d5..b4909a8e 100644 --- a/smatch.h +++ b/smatch.h @@ -327,6 +327,9 @@ extern struct data_range whole_range; static const long long valid_ptr_max = LONG_MAX; static const long long valid_ptr_min = 4096; +/* smatch_absolute.c */ +extern int absolute_id; + /* smatch_states.c */ void __push_fake_cur_slist(); struct state_list *__pop_fake_cur_slist(); @@ -425,6 +428,7 @@ enum info_type { RANGE_CAP, LOCK_HELD, LOCK_RELEASED, + ABSOLUTE_LIMITS, }; int get_return_id(void); diff --git a/smatch_absolute.c b/smatch_absolute.c new file mode 100644 index 00000000..9c31fce7 --- /dev/null +++ b/smatch_absolute.c @@ -0,0 +1,201 @@ +/* + * smatch/smatch_absolute.c + * + * Copyright (C) 2012 Oracle. + * + * Licensed under the Open Software License version 1.1 + * + * This is to track the absolute max that variables can be. It's a bit like + * smatch_extra.c but it only tracks the absolute max and min. So for example, + * if you have "int x = (unsigned char)y;" then the absolute max of x is 255. + * + * I imagine this will be useful for find integer overflows. + * + */ + +#include "smatch.h" +#include "smatch_slist.h" +#include "smatch_extra.h" + +int absolute_id; + +static char *show_num(long long num) +{ + static char buf[64]; + + if (num < 0) + sprintf(buf, "(%lld)", num); + else + sprintf(buf, "%lld", num); + return buf; +} + +static char *show_range(long long min, long long max) +{ + static char buf[256]; + char *p = buf; + + if (min == whole_range.min) + p += sprintf(p, "min"); + else if (min == whole_range.max) + p += sprintf(p, "max"); + else + p += sprintf(p, "%s", show_num(min)); + if (min != max) { + if (max == whole_range.max) + sprintf(p, "-max"); + else + sprintf(p, "-%s", show_num(max)); + } + return buf; + +} + +static struct smatch_state *alloc_absolute(long long min, long long max) +{ + struct smatch_state *state; + + if (min == whole_range.min && max == whole_range.max) + return &undefined; + + state = __alloc_smatch_state(0); + state->name = alloc_string(show_range(min, max)); + state->data = alloc_range(min, max); + return state; +} + +static struct smatch_state *merge_func(struct smatch_state *s1, struct smatch_state *s2) +{ + struct data_range *r1, *r2; + long long min, max; + + if (!s1->data || !s2->data) + return &undefined; + + r1 = s1->data; + r2 = s2->data; + + if (r1->min == r2->min && r1->max == r2->max) + return s1; + + min = r1->min; + if (r2->min < min) + min = r2->min; + max = r1->max; + if (r2->max > max) + max = r2->max; + + return alloc_absolute(min, max); +} + +static void reset_state(struct sm_state *sm) +{ + set_state(absolute_id, sm->name, sm->sym, &undefined); +} + +static void match_assign(struct expression *expr) +{ + struct symbol *type; + long long min, max; + + if (expr->op != '=') { + set_state_expr(absolute_id, expr->left, &undefined); + return; + } + + type = get_type(expr->left); + if (!type) + return; + + if (!get_absolute_min(expr->right, &min)) + min = whole_range.min; + if (!get_absolute_max(expr->right, &max)) + max = whole_range.max; + + /* handle wrapping. sort of sloppy */ + if (type_max(type) < max) + min = type_min(type); + if (type_min(type) > min) + max = type_max(type); + + if (min <= type_min(type) && max >= type_max(type)) + set_state_expr(absolute_id, expr->left, &undefined); + else + set_state_expr(absolute_id, expr->left, alloc_absolute(min, max)); +} + +static void struct_member_callback(char *fn, char *global_static, int param, char *printed_name, struct smatch_state *state) +{ + struct data_range *range; + + if (!state->data) + return; + range = state->data; + if (range->min == whole_range.min && range->max == whole_range.max) + return; + sm_msg("info: passes absolute_limits '%s' %d '%s' %s %s", fn, param, printed_name, state->name, global_static); +} + +static void match_call_info(struct expression *expr) +{ + struct expression *arg; + char *name; + int i = 0; + + name = get_fnptr_name(expr->fn); + if (!name) + return; + + FOR_EACH_PTR(expr->args, arg) { + long long min, max; + + if (!get_absolute_min(arg, &min)) + continue; + if (!get_absolute_max(arg, &max)) + continue; + if (min == whole_range.min && max == whole_range.max) + continue; + + /* fixme: determine the type of the paramter */ + sm_msg("info: passes absolute_limits '%s' %d '$$' %s %s", + name, i, show_range(min, max), + is_static(expr->fn) ? "static" : "global"); + i++; + } END_FOR_EACH_PTR(arg); + + free_string(name); +} + +static void set_param_limits(const char *name, struct symbol *sym, char *key, char *value) +{ + struct range_list *rl = NULL; + long long min, max; + char fullname[256]; + + if (strncmp(key, "$$", 2)) + return; + + snprintf(fullname, 256, "%s%s", name, key + 2); + get_value_ranges(value, &rl); + min = rl_min(rl); + max = rl_max(rl); + set_state(absolute_id, fullname, sym, alloc_absolute(min, max)); +} + +void register_absolute(int id) +{ + absolute_id = id; + + add_merge_hook(absolute_id, &merge_func); + add_hook(&match_assign, ASSIGNMENT_HOOK); + if (option_info) { + add_hook(&match_call_info, FUNCTION_CALL_HOOK); + add_member_info_callback(absolute_id, struct_member_callback); + } + add_definition_db_callback(set_param_limits, ABSOLUTE_LIMITS); +} + +void register_absolute_late(int id) +{ + add_indirect_modification_hook(absolute_id, reset_state); +} diff --git a/smatch_math.c b/smatch_math.c index 7c8567b6..c30d2bbb 100644 --- a/smatch_math.c +++ b/smatch_math.c @@ -461,11 +461,29 @@ static long long _get_implied_value(struct expression *expr, int *undefined, int case IMPLIED: case IMPLIED_MAX: case IMPLIED_MIN: - case ABSOLUTE_MIN: - case ABSOLUTE_MAX: if (!get_implied_value_helper(expr, &ret, implied)) *undefined = 1; break; + case ABSOLUTE_MIN: + case ABSOLUTE_MAX: { + struct smatch_state *state; + struct data_range *range; + + if (get_implied_value_helper(expr, &ret, implied)) + break; + + state = get_state_expr(absolute_id, expr); + if (!state || !state->data) { + *undefined = 1; + break; + } + range = state->data; + if (implied == ABSOLUTE_MAX) + ret = range->max; + else + ret = range->min; + break; + } case FUZZYMAX: if (!get_fuzzy_max_helper(expr, &ret)) *undefined = 1; @@ -609,12 +627,15 @@ int get_absolute_min(struct expression *expr, long long *val) int undefined = 0; struct symbol *type; + type = get_type(expr); *val = _get_value(expr, &undefined, ABSOLUTE_MIN); - if (!undefined) + if (undefined) { + *val = type_min(type); return 1; + } - type = get_type(expr); - *val = type_min(type); + if (type_min(type) > *val) + *val = type_min(type); return 1; } @@ -623,12 +644,15 @@ int get_absolute_max(struct expression *expr, long long *val) int undefined = 0; struct symbol *type; + type = get_type(expr); *val = _get_value(expr, &undefined, ABSOLUTE_MAX); - if (!undefined) + if (undefined) { + *val = type_max(type); return 1; + } - type = get_type(expr); - *val = type_max(type); + if (type_max(type) < *val) + *val = type_max(type); return 1; } diff --git a/smatch_scripts/db/fill_db_caller_info.pl b/smatch_scripts/db/fill_db_caller_info.pl index 7b846e33..e569905b 100755 --- a/smatch_scripts/db/fill_db_caller_info.pl +++ b/smatch_scripts/db/fill_db_caller_info.pl @@ -92,6 +92,18 @@ while () { $func = "$dummy $func"; } + } elsif ($_ =~ /info: passes absolute_limits /) { + # init/main.c +165 obsolete_checksetup(7) info: passes param_value strlen 0 min-max static + $type = 10; # ABSOLUTE_LIMITS + ($file_and_line, $caller, $dummy, $dummy, $dummy, $func, $param, $key, $value, $gs) = split(/ /, $_); + ($file, $line) = split(/:/, $file_and_line); + + if ($func eq "'(struct") { + ($file_and_line, $dummy, $dummy, $dummy, $dummy, $dummy, $func, $param, $key, $value, $gs) = split(/ /, $_); + ($file, $line) = split(/:/, $file_and_line); + $func = "$dummy $func"; + } + } elsif ($_ =~ /info: passes_buffer /) { # init/main.c +175 obsolete_checksetup(17) info: passes_buffer 'printk' 0 '$$' 38 global $type = 2; # BUF_SIZE