[C-safe-secure-studygroup] more on dynamic+static analysis

[Clive Pygott]

Your example:

// again, not statically checkable, but we can insert a precise dynamic
check
void foo(int n, int m) {
   int *p = (int*)malloc(n * sizeof(int));
  ...
  p[m] = 0;
 }

goes to what I was saying yesterday about whole program analysis. It may be
statically checkable, if at each point foo is called you can show   (n > 0)
&& (m >= 0) && (m < n)      If n and m are derived from expressions, then
can you push back into those expression to check this property. How deep a
tool can go become a quality of implementation issue

What do you mean by  "we can insert a precise dynamic check", I'm guessing
void foo(int n, int m) {
   int *p = (int*)malloc(n * sizeof(int));
   if ((m >= 0) && (m < n))
     p[m] = 0;
 }

Whilst this is a dynamic check in the sense that you are adding code that
will perform the check at runtime, the fact that there won't be an index
out of bounds error here is statically checkable

    Clive








On Wed, Jan 25, 2017 at 11:25 PM, Kostya Serebryany <kcc at google.com> wrote:

> There are lots of problems in C that *can not* be solved by static nor
> by dynamic analyses alone, but *can* be solved with a combination of
> those.
>
> Let's take buffer overflows as an example (probably, the most well
> understood problem in C).
> I think that every memory access can be classified to be one of:
> * statically checkable
> * not statically checkable, but precisely checkable at run-time
> * not statically checkable, and only imprecisely checkable at run-time
> * not statically checkable, and existing dynamic analysis tools are likely
> useless
>
> // This is fully analyzable statically
> int a[10];
> void foo() {  for (int i = 0; i < 20; i++) a[i] = 0; }
>
> // This can't be analyzed statically, but we can insert  checks that
> // will perform precise checks dynamically
> int a[10];
> extern int get_idx();  // No source available during analysis
> void foo() { a[get_idx()] = 0; }
>
> // again, not statically checkable, but we can insert a precise dynamic
> check
> void foo(int n, int m) {
>    int *p = (int*)malloc(n * sizeof(int));
>   ...
>   p[m] = 0;
>  }
>
> // W/o the context of the calls we can't do anything statically,
> // so the only thing that remains is imprecise dynamic check
> // (using e.g. shadow memory, like valgrind or AddressSanitizer do)
> void foo(int m, int *p) {
>    p[m] = 0;
> }
>
> // In this case, static analysis is most likely infeasible
> // and adding a precise dynamic check is too expensive,
> // but an imprecise check would work "ok" because all objects are in heap
> // and so we can rely on the redzones (like in valgrind, asan)
> int *p1 = (int*)malloc(N1);
> int *p2 = (int*)malloc(N1);
> ...
> int *pK = (int*)malloc(NK);
>
> int *p = .. ? p1 : .. p2 ? : ... pK;  // one of the above pointers
> ...
> p[m] = 0;
>
>
> // Now, this is much worse: if S::buffer overflows by one, redzones will
> not find it,
> // and there is no usable dynamic tool on the market today that will find
> this reliably.
> // (Well, there is Intel MPX, but I can't call it usable today)
> // For this case we should be able to warn users that due to expression
> (**)
> // * static analysis gave up
> // * dynamic analysis is potentially inefficient
> struct S {
>   int buffer[10];
>   int more_fields;
> };
>
> struct S s;
> int *p1 = ...
> ...
> int *pK = &s.buffer[0];  // (**)
> ...
> int *p = .. ? ... :  pK;
> p[m] = 0;
>
>
> I think it would be a great outcome of this study group if we can prepare
> a comprehensive
> set of tests like the above.
> Not just for buffer overflows, but for everything else as well (at least,
> for use-after-free of all kinds)
>
> Thoughts?
>
> --kcc
>
>
> _______________________________________________
> C-safe-secure-studygroup mailing list
> C-safe-secure-studygroup at lists.trustable.io
> https://lists.trustable.io/cgi-bin/mailman/listinfo/c-
> safe-secure-studygroup
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.trustable.io/pipermail/c-safe-secure-studygroup/attachments/20170126/646e60a1/attachment-0001.html>