From 57a73b207be38774053e8cddf64b6fe3d01313c3 Mon Sep 17 00:00:00 2001 From: Dan Carpenter Date: Tue, 17 Nov 2015 11:23:18 +0300 Subject: [PATCH] *new* real_absolute: give a more accurate absolute value The problem is this: x = unknown / 2; With the original code, we didn't save anything when we saw that because unknown divided by 2 is still unknown. We only save things in smatch_extra.c when there is a level of confidence or a some intent or meaning. That way we can use get_absolute_rl() and if it is the whole range we can say "Oh, we don't know anything about this variable, let's ignore it." But other times, especially if we are looking at integer overflows then it's important to know that "x can only possibly go up to u32max / 4 so it can't overflow." Smatch extra is used to generate warnings but the real absolute is pretty much used to eliminate false positives. In that way it's not as critical to be 100% accurate, any extra information is an improvement. So I think I will not replicate all the smatch_extra.c code for tracking the real absolute. Signed-off-by: Dan Carpenter --- Makefile | 2 +- smatch_extra.h | 4 ++ smatch_math.c | 46 ++++++++++++++++++---- smatch_real_absolute.c | 105 +++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 148 insertions(+), 9 deletions(-) create mode 100644 smatch_real_absolute.c diff --git a/Makefile b/Makefile index 053b842a..66d9794c 100644 --- a/Makefile +++ b/Makefile @@ -73,7 +73,7 @@ SMATCH_FILES=smatch_flow.o smatch_conditions.o smatch_slist.o smatch_states.o \ smatch_function_info.o smatch_links.o smatch_auto_copy.o \ smatch_type_links.o smatch_untracked_param.o smatch_impossible.o \ smatch_strings.o smatch_param_used.o smatch_address.o \ - smatch_buf_comparison.o + smatch_buf_comparison.o smatch_real_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/smatch_extra.h b/smatch_extra.h index 6228c8f4..0cb81848 100644 --- a/smatch_extra.h +++ b/smatch_extra.h @@ -94,6 +94,7 @@ struct range_list *rl_truncate_cast(struct symbol *type, struct range_list *rl); struct range_list *cast_rl(struct symbol *type, struct range_list *rl); int get_implied_rl(struct expression *expr, struct range_list **rl); int get_absolute_rl(struct expression *expr, struct range_list **rl); +int get_real_absolute_rl(struct expression *expr, struct range_list **rl); struct range_list *var_to_absolute_rl(struct expression *expr); int custom_get_absolute_rl(struct expression *expr, struct range_list *(*fn)(struct expression *expr), @@ -193,3 +194,6 @@ int is_fake_call(struct expression *expr); /* smatch_param_limit.c */ struct smatch_state *get_orig_estate(const char *name, struct symbol *sym); + +/* smatch_real_absolute.c */ +struct smatch_state *get_real_absolute_state(struct expression *expr); diff --git a/smatch_math.c b/smatch_math.c index 82c2f57b..0007831b 100644 --- a/smatch_math.c +++ b/smatch_math.c @@ -45,7 +45,8 @@ enum { RL_HARD, RL_FUZZY, RL_IMPLIED, - RL_ABSOLUTE + RL_ABSOLUTE, + RL_REAL_ABSOLUTE, }; static struct range_list *last_stmt_rl(struct statement *stmt, int implied, int *recurse_cnt) @@ -151,8 +152,11 @@ static struct range_list *handle_divide_rl(struct expression *expr, int implied, if (!left_rl || !right_rl) return NULL; - if (is_whole_rl(left_rl) || is_whole_rl(right_rl)) - return NULL; + + if (implied != RL_REAL_ABSOLUTE) { + if (is_whole_rl(left_rl) || is_whole_rl(right_rl)) + return NULL; + } return rl_binop(left_rl, '/', right_rl); } @@ -269,7 +273,7 @@ static struct range_list *handle_bitwise_AND(struct expression *expr, int implie struct range_list *left_rl, *right_rl; sval_t known; - if (implied != RL_IMPLIED && implied != RL_ABSOLUTE) + if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE) return NULL; type = get_type(expr); @@ -331,7 +335,7 @@ static struct range_list *use_rl_binop(struct expression *expr, int implied, int struct symbol *type; struct range_list *left_rl, *right_rl; - if (implied != RL_IMPLIED && implied != RL_ABSOLUTE) + if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE) return NULL; type = get_type(expr); @@ -738,11 +742,14 @@ struct range_list *var_to_absolute_rl(struct expression *expr) struct range_list *rl; state = get_extra_state(expr); - if (!state) { + if (!state || is_whole_rl(estate_rl(state))) { if (get_local_rl(expr, &rl)) return rl; if (get_db_type_rl(expr, &rl)) return rl; + state = get_real_absolute_state(expr); + if (state && state->data) + return clone_rl(estate_rl(state)); return alloc_whole_rl(get_type(expr)); } /* err on the side of saying things are possible */ @@ -786,6 +793,19 @@ static struct range_list *handle_variable(struct expression *expr, int implied, if (implied == RL_HARD && !estate_has_hard_max(state)) return NULL; return clone_rl(estate_rl(state)); + case RL_REAL_ABSOLUTE: + state = get_extra_state(expr); + if (!state || !state->data || is_whole_rl(estate_rl(state))) { + if (get_local_rl(expr, &rl)) + return rl; + if (get_db_type_rl(expr, &rl)) + return rl; + state = get_real_absolute_state(expr); + if (state && state->data) + return clone_rl(estate_rl(state)); + return NULL; + } + return clone_rl(estate_rl(state)); case RL_FUZZY: if (!get_fuzzy_min_helper(expr, &min)) min = sval_type_min(get_type(expr)); @@ -893,7 +913,7 @@ static struct range_list *handle_cast(struct expression *expr, int implied, int rl = _get_rl(expr->cast_expression, implied, recurse_cnt); if (rl) return cast_rl(type, rl); - if (implied == RL_ABSOLUTE) + if (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE) return alloc_whole_rl(type); if (implied == RL_IMPLIED && type && type_bits(type) > 0 && type_bits(type) < 32) @@ -966,7 +986,7 @@ static struct range_list *_get_rl(struct expression *expr, int implied, int *rec out_cast: if (rl) return rl; - if (type && implied == RL_ABSOLUTE) + if (type && (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE)) return alloc_whole_rl(type); return NULL; } @@ -1056,6 +1076,16 @@ int get_absolute_rl(struct expression *expr, struct range_list **rl) return 1; } +int get_real_absolute_rl(struct expression *expr, struct range_list **rl) +{ + int recurse_cnt = 0; + + *rl = _get_rl(expr, RL_REAL_ABSOLUTE, &recurse_cnt); + if (!*rl) + *rl = alloc_whole_rl(get_type(expr)); + return 1; +} + int custom_get_absolute_rl(struct expression *expr, struct range_list *(*fn)(struct expression *expr), struct range_list **rl) diff --git a/smatch_real_absolute.c b/smatch_real_absolute.c new file mode 100644 index 00000000..892850d5 --- /dev/null +++ b/smatch_real_absolute.c @@ -0,0 +1,105 @@ +/* + * Copyright (C) 2015 Oracle. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt + */ + +/* + * Say we have a line like: + * foo = bar / 8; + * Assume we don't know anything about bar. Well, now we know that foo is less + * than UINT_MAX / 8. Which might be useful, but it probably is misleading + * useless knowledge. Up to now we have ignored those but now we have said to + * store them. + * + * It also works if you have something like "foo = (int)(char)unknown_var;". + * + * I feel like this data doesn't have to be perfect, it just has to be better + * than nothing and that will help eliminate some false positives. + * + */ + +#include "smatch.h" +#include "smatch_slist.h" +#include "smatch_extra.h" + +static int my_id; + +static void pre_merge_hook(struct sm_state *sm) +{ + struct smatch_state *abs; + struct smatch_state *extra; + struct range_list *rl; + + extra = get_state(SMATCH_EXTRA, sm->name, sm->sym); + if (!extra || !estate_rl(extra)) + return; + abs = get_state(my_id, sm->name, sm->sym); + if (!abs || !estate_rl(abs)) { + set_state(my_id, sm->name, sm->sym, clone_estate(extra)); + return; + } + rl = rl_intersection(estate_rl(abs), estate_rl(extra)); + set_state(my_id, sm->name, sm->sym, alloc_estate_rl(clone_rl(rl))); +} + +static struct smatch_state *empty_state(struct sm_state *sm) +{ + return alloc_estate_empty(); +} + +static void reset(struct sm_state *sm, struct expression *mod_expr) +{ + set_state(my_id, sm->name, sm->sym, alloc_estate_whole(estate_type(sm->state))); +} + +static void match_assign(struct expression *expr) +{ + struct range_list *rl; + struct symbol *type; + + if (is_fake_call(expr->right)) + return; + + get_real_absolute_rl(expr->right, &rl); + + type = get_type(expr->left); + if (!type) + return; + + rl = cast_rl(type, rl); + if (sval_cmp(rl_max(rl), sval_type_max(type)) == 0 && + sval_cmp(rl_min(rl), sval_type_min(type))) + return; + + set_state_expr(my_id, expr->left, alloc_estate_rl(clone_rl(rl))); +} + +struct smatch_state *get_real_absolute_state(struct expression *expr) +{ + return get_state_expr(my_id, expr); +} + +void register_real_absolute(int id) +{ + my_id = id; + + add_pre_merge_hook(my_id, &pre_merge_hook); + add_unmatched_state_hook(my_id, &empty_state); + add_merge_hook(my_id, &merge_estates); + add_modification_hook(my_id, &reset); + + add_hook(&match_assign, ASSIGNMENT_HOOK); +} + -- 2.11.4.GIT