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

[Kostya Serebryany]

On Thu, Jan 26, 2017 at 2:11 AM, Clive Pygott <clivepygott at gmail.com> wrote:

> 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.
>

Yes.


> 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.
>


Correct. But
a) 'n' or 'm' do not necessary come from expressions  -- they could be
derived from un-trusted inputs,
b) not every expression is possible to analyze in theory, let alone in
practice,
c) whole program analysis may not be available



> 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))
>

More like  if ((m < 0) || (m >= n)) abort();


>      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
>

Precisely.
But this check does not fix the problem, it only changes it from
easy-to-exploit hard-to-reproduce buffer overflow into a harder-to-exploit
and easy-to-reproduce crash (DoS attack is still possible).
This is why we actually need the next layer of tools to find these cases
(fuzzing, symbolic execution, etc)

--kcc



>
>     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
>>
>>
>
> _______________________________________________
> 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/4fadbe07/attachment.html>