absolute: track the absolute limits that variables can be
authorDan Carpenter <dan.carpenter@oracle.com>
Fri, 12 Oct 2012 07:55:55 +0000 (12 10:55 +0300)
committerDan Carpenter <dan.carpenter@oracle.com>
Fri, 12 Oct 2012 07:55:55 +0000 (12 10:55 +0300)
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 <dan.carpenter@oracle.com>
Makefile
check_debug.c
check_debug.h
check_list.h
smatch.h
smatch_absolute.c [new file with mode: 0644]
smatch_math.c
smatch_scripts/db/fill_db_caller_info.pl

index cea7ac3..c659954 100644 (file)
--- 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 \
index 685e801..9de1596 100644 (file)
@@ -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);
index 0220a55..c9fced4 100644 (file)
@@ -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){}
 
index a4c891a..b3afb52 100644 (file)
@@ -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)
index 29ebf3d..b4909a8 100644 (file)
--- 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 (file)
index 0000000..9c31fce
--- /dev/null
@@ -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);
+}
index 7c8567b..c30d2bb 100644 (file)
@@ -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;
 }
 
index 7b846e3..e569905 100755 (executable)
@@ -92,6 +92,18 @@ while (<WARNS>) {
             $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