Tracking Implicit Dependencies

Tracking Implicit Dependencies

[Andrew Zhu Aday]

Hi Smatch team,

My name is Andrew Aday and I'm an CS undergrad at Columbia University.

I'm currently doing research on kernel fuzzing via the system call interface,
and I'm at the point now where I need to track "implicit dependencies" between
system calls. I'm writing this email to ask: how appropriate is Smatch
for this task?

To explain:

Syscall A is an "explicit dependency" of syscall B if A produces a
resource which B
uses. For example `open` and `read`

Syscall A is an "implicit dependency" of syscall B if A can affect the
control flow/coverage of B, but B doesn't use A's return value. For example,
`mlockall` and `msync`; calling `mlockall` before `msync` will cause
the latter to
fail with -EBUSY, and thus influences its control flow.

My naive approach:

Use static analysis to build out the CFG for each syscall, and create a mapping
from each system call to the global variables it accesses. Mark two syscalls
as implicitly dependent if the intersection of their global var
accesses is nonempty.
(After pruning the especially common ones e.g. GFP_KERNEL)

I've looked briefly at Smatch, but I wanted to get your assessment
before I go any
further. Is what I'm trying to do feasible? I see there's a `FUNCTION_CALL_HOOK`
I can plug into to recursively collect all the global variables under
a given syscall.
But I'm very unfamiliar with static analysis in general, so I'm not
sure about how
straightforward doing this is.

Please let me know your thoughts! And of course ask me any questions or if I
need to explain better.

p.s Why does the cross-function database become more accurate every
time it's rebuilt?

Thanks!

Re: Tracking Implicit Dependencies

[Andrew Zhu Aday]

Hi Smatch,

I ran across a bug: when running  `~/smatch/smatch_scripts/kchecker mm/msync.c`,
I noticed that FUNCTION_CALL_HOOK and CONDITION_HOOK are not actually
called within the body msync. Some other syscalls I looked at seem to
work correctly.

Do you know why this is the case? Is there a simple fix?

Thanks,
Andrew

On Fri, Sep 29, 2017 at 3:23 PM, Andrew Zhu Aday
<andrew.aday@columbia.edu> wrote:
> Hi Smatch,
>
> I ran across a bug: when running  `~/smatch/smatch_scripts/kchecker
> mm/msync.c`,
> I noticed that FUNCTION_CALL_HOOK and CONDITION_HOOK are not actually
> called within the body msync. Some other syscalls I looked at seem to work
> correctly.
>
> Do you know why this is the case? Is there a simple fix?
>
> Thanks,
> Andrew
>
> On Sat, Sep 23, 2017 at 1:37 AM, Andrew Zhu Aday <andrew.aday@columbia.edu>
> wrote:
>>
>> Hi Smatch team,
>>
>> My name is Andrew Aday and I'm an CS undergrad at Columbia University.
>>
>> I'm currently doing research on kernel fuzzing via the system call
>> interface,
>> and I'm at the point now where I need to track "implicit dependencies"
>> between
>> system calls. I'm writing this email to ask: how appropriate is Smatch
>> for this task?
>>
>> To explain:
>>
>> Syscall A is an "explicit dependency" of syscall B if A produces a
>> resource which B
>> uses. For example `open` and `read`
>>
>> Syscall A is an "implicit dependency" of syscall B if A can affect the
>> control flow/coverage of B, but B doesn't use A's return value. For
>> example,
>> `mlockall` and `msync`; calling `mlockall` before `msync` will cause
>> the latter to
>> fail with -EBUSY, and thus influences its control flow.
>>
>> My naive approach:
>>
>> Use static analysis to build out the CFG for each syscall, and create a
>> mapping
>> from each system call to the global variables it accesses. Mark two
>> syscalls
>> as implicitly dependent if the intersection of their global var
>> accesses is nonempty.
>> (After pruning the especially common ones e.g. GFP_KERNEL)
>>
>> I've looked briefly at Smatch, but I wanted to get your assessment
>> before I go any
>> further. Is what I'm trying to do feasible? I see there's a
>> `FUNCTION_CALL_HOOK`
>> I can plug into to recursively collect all the global variables under
>> a given syscall.
>> But I'm very unfamiliar with static analysis in general, so I'm not
>> sure about how
>> straightforward doing this is.
>>
>> Please let me know your thoughts! And of course ask me any questions or if
>> I
>> need to explain better.
>>
>> p.s Why does the cross-function database become more accurate every
>> time it's rebuilt?
>>
>> Thanks!
>
>

Re: Tracking Implicit Dependencies

[Andrew Zhu Aday]

Also, when parsing a function definition, why does smatch only follow
some internal function calls? For example, in the syscall
`get_mempolicy` in ``mm/mempolicy.c`,
it will follow the call to `copy_nodes_to_user`, but will not follow
`do_get_mempolicy`.

Is there a way I can make it follow all internal function calls?

On Fri, Sep 29, 2017 at 3:23 PM, Andrew Zhu Aday
<andrew.aday@columbia.edu> wrote:
> Hi Smatch,
>
> I ran across a bug: when running  `~/smatch/smatch_scripts/kchecker mm/msync.c`,
> I noticed that FUNCTION_CALL_HOOK and CONDITION_HOOK are not actually
> called within the body msync. Some other syscalls I looked at seem to
> work correctly.
>
> Do you know why this is the case? Is there a simple fix?
>
> Thanks,
> Andrew
>
> On Fri, Sep 29, 2017 at 3:23 PM, Andrew Zhu Aday
> <andrew.aday@columbia.edu> wrote:
>> Hi Smatch,
>>
>> I ran across a bug: when running  `~/smatch/smatch_scripts/kchecker
>> mm/msync.c`,
>> I noticed that FUNCTION_CALL_HOOK and CONDITION_HOOK are not actually
>> called within the body msync. Some other syscalls I looked at seem to work
>> correctly.
>>
>> Do you know why this is the case? Is there a simple fix?
>>
>> Thanks,
>> Andrew
>>
>> On Sat, Sep 23, 2017 at 1:37 AM, Andrew Zhu Aday <andrew.aday@columbia.edu>
>> wrote:
>>>
>>> Hi Smatch team,
>>>
>>> My name is Andrew Aday and I'm an CS undergrad at Columbia University.
>>>
>>> I'm currently doing research on kernel fuzzing via the system call
>>> interface,
>>> and I'm at the point now where I need to track "implicit dependencies"
>>> between
>>> system calls. I'm writing this email to ask: how appropriate is Smatch
>>> for this task?
>>>
>>> To explain:
>>>
>>> Syscall A is an "explicit dependency" of syscall B if A produces a
>>> resource which B
>>> uses. For example `open` and `read`
>>>
>>> Syscall A is an "implicit dependency" of syscall B if A can affect the
>>> control flow/coverage of B, but B doesn't use A's return value. For
>>> example,
>>> `mlockall` and `msync`; calling `mlockall` before `msync` will cause
>>> the latter to
>>> fail with -EBUSY, and thus influences its control flow.
>>>
>>> My naive approach:
>>>
>>> Use static analysis to build out the CFG for each syscall, and create a
>>> mapping
>>> from each system call to the global variables it accesses. Mark two
>>> syscalls
>>> as implicitly dependent if the intersection of their global var
>>> accesses is nonempty.
>>> (After pruning the especially common ones e.g. GFP_KERNEL)
>>>
>>> I've looked briefly at Smatch, but I wanted to get your assessment
>>> before I go any
>>> further. Is what I'm trying to do feasible? I see there's a
>>> `FUNCTION_CALL_HOOK`
>>> I can plug into to recursively collect all the global variables under
>>> a given syscall.
>>> But I'm very unfamiliar with static analysis in general, so I'm not
>>> sure about how
>>> straightforward doing this is.
>>>
>>> Please let me know your thoughts! And of course ask me any questions or if
>>> I
>>> need to explain better.
>>>
>>> p.s Why does the cross-function database become more accurate every
>>> time it's rebuilt?
>>>
>>> Thanks!
>>
>>

Re: Tracking Implicit Dependencies

[Andrew Zhu Aday]

cc

On Fri, Sep 29, 2017 at 3:36 PM, Andrew Zhu Aday
<andrew.aday@columbia.edu> wrote:
> Also, when parsing a function definition, why does smatch only follow
> some internal function calls? For example, in the syscall
> `get_mempolicy` in ``mm/mempolicy.c`,
> it will follow the call to `copy_nodes_to_user`, but will not follow
> `do_get_mempolicy`.
>
> Is there a way I can make it follow all internal function calls?
>
> On Fri, Sep 29, 2017 at 3:23 PM, Andrew Zhu Aday
> <andrew.aday@columbia.edu> wrote:
>> Hi Smatch,
>>
>> I ran across a bug: when running  `~/smatch/smatch_scripts/kchecker mm/msync.c`,
>> I noticed that FUNCTION_CALL_HOOK and CONDITION_HOOK are not actually
>> called within the body msync. Some other syscalls I looked at seem to
>> work correctly.
>>
>> Do you know why this is the case? Is there a simple fix?
>>
>> Thanks,
>> Andrew
>>
>> On Fri, Sep 29, 2017 at 3:23 PM, Andrew Zhu Aday
>> <andrew.aday@columbia.edu> wrote:
>>> Hi Smatch,
>>>
>>> I ran across a bug: when running  `~/smatch/smatch_scripts/kchecker
>>> mm/msync.c`,
>>> I noticed that FUNCTION_CALL_HOOK and CONDITION_HOOK are not actually
>>> called within the body msync. Some other syscalls I looked at seem to work
>>> correctly.
>>>
>>> Do you know why this is the case? Is there a simple fix?
>>>
>>> Thanks,
>>> Andrew
>>>
>>> On Sat, Sep 23, 2017 at 1:37 AM, Andrew Zhu Aday <andrew.aday@columbia.edu>
>>> wrote:
>>>>
>>>> Hi Smatch team,
>>>>
>>>> My name is Andrew Aday and I'm an CS undergrad at Columbia University.
>>>>
>>>> I'm currently doing research on kernel fuzzing via the system call
>>>> interface,
>>>> and I'm at the point now where I need to track "implicit dependencies"
>>>> between
>>>> system calls. I'm writing this email to ask: how appropriate is Smatch
>>>> for this task?
>>>>
>>>> To explain:
>>>>
>>>> Syscall A is an "explicit dependency" of syscall B if A produces a
>>>> resource which B
>>>> uses. For example `open` and `read`
>>>>
>>>> Syscall A is an "implicit dependency" of syscall B if A can affect the
>>>> control flow/coverage of B, but B doesn't use A's return value. For
>>>> example,
>>>> `mlockall` and `msync`; calling `mlockall` before `msync` will cause
>>>> the latter to
>>>> fail with -EBUSY, and thus influences its control flow.
>>>>
>>>> My naive approach:
>>>>
>>>> Use static analysis to build out the CFG for each syscall, and create a
>>>> mapping
>>>> from each system call to the global variables it accesses. Mark two
>>>> syscalls
>>>> as implicitly dependent if the intersection of their global var
>>>> accesses is nonempty.
>>>> (After pruning the especially common ones e.g. GFP_KERNEL)
>>>>
>>>> I've looked briefly at Smatch, but I wanted to get your assessment
>>>> before I go any
>>>> further. Is what I'm trying to do feasible? I see there's a
>>>> `FUNCTION_CALL_HOOK`
>>>> I can plug into to recursively collect all the global variables under
>>>> a given syscall.
>>>> But I'm very unfamiliar with static analysis in general, so I'm not
>>>> sure about how
>>>> straightforward doing this is.
>>>>
>>>> Please let me know your thoughts! And of course ask me any questions or if
>>>> I
>>>> need to explain better.
>>>>
>>>> p.s Why does the cross-function database become more accurate every
>>>> time it's rebuilt?
>>>>
>>>> Thanks!
>>>
>>>

Re: Tracking Implicit Dependencies

[Dan Carpenter]

Huh...  Sorry for not responding earlier.  I missed your email in my
other inbox.  I know that students are always on a deadline.  Please CC
me and I'll try to respond more quickly.

On Sat, Sep 23, 2017 at 01:37:45AM -0400, Andrew Zhu Aday wrote:
> Hi Smatch team,
> 
> My name is Andrew Aday and I'm an CS undergrad at Columbia University.
> 
> I'm currently doing research on kernel fuzzing via the system call interface,
> and I'm at the point now where I need to track "implicit dependencies" between
> system calls. I'm writing this email to ask: how appropriate is Smatch
> for this task?

It's very appropriate.  It's still probably a big project though...

> 
> To explain:
> 
> Syscall A is an "explicit dependency" of syscall B if A produces a
> resource which B
> uses. For example `open` and `read`
> 
> Syscall A is an "implicit dependency" of syscall B if A can affect the
> control flow/coverage of B, but B doesn't use A's return value. For example,
> `mlockall` and `msync`; calling `mlockall` before `msync` will cause
> the latter to
> fail with -EBUSY, and thus influences its control flow.

Hm...  That's tricky.

> 
> My naive approach:
> 
> Use static analysis to build out the CFG for each syscall, and create a mapping
> from each system call to the global variables it accesses. Mark two syscalls
> as implicitly dependent if the intersection of their global var
> accesses is nonempty.
> (After pruning the especially common ones e.g. GFP_KERNEL)
> 

GFP_KERNEL is a define so it's just a number.

> I've looked briefly at Smatch, but I wanted to get your assessment
> before I go any
> further. Is what I'm trying to do feasible? I see there's a `FUNCTION_CALL_HOOK`
> I can plug into to recursively collect all the global variables under
> a given syscall.
> But I'm very unfamiliar with static analysis in general, so I'm not
> sure about how
> straightforward doing this is.
> 
> Please let me know your thoughts! And of course ask me any questions or if I
> need to explain better.
> 
> p.s Why does the cross-function database become more accurate every
> time it's rebuilt?
> 

The cross function database just looks at frob() the value of "x" to
frob_two().  But since this is the first time the DB was built then
we don't know the value of "x".  The next time we build the DB we can
see how frob() is called so the information about "x" becomes more
filled out.

regards,
dan carpenter

Re: Tracking Implicit Dependencies

[Dan Carpenter]

On Fri, Sep 29, 2017 at 03:23:56PM -0400, Andrew Zhu Aday wrote:
> Hi Smatch,
> 
> I ran across a bug: when running  `~/smatch/smatch_scripts/kchecker mm/msync.c`,
> I noticed that FUNCTION_CALL_HOOK and CONDITION_HOOK are not actually
> called within the body msync. Some other syscalls I looked at seem to
> work correctly.
> 
> Do you know why this is the case? Is there a simple fix?

They're definitely called.  I don't know how you're testing...

A lot of the function calls are not recorded in the DB because those
functions are too common.  So if we were trying to parse down_read()
and we looked up all the callers it would take a minute do just merge
all the data.  I don't mind changing it to record the function call and
adding a different flag somewhere that actually don't look up the
caller_info when we're parsing the function itself.

$ echo "select * from caller_info where caller = 'SYSC_msync';" | sqlite3 smatch_db.sqlite
mm/msync.c|SYSC_msync|get_file|110807|1|0|-1||struct file*(*)(struct file*)
mm/msync.c|SYSC_msync|get_file|110807|1|1001|0|$|s64min-(-1),1-s64max
mm/msync.c|SYSC_msync|vfs_fsync_range|110808|0|0|-1||int(*)(struct file*, llong, llong, int)
mm/msync.c|SYSC_msync|vfs_fsync_range|110808|0|1001|0|$|s64min-(-1),1-s64max
mm/msync.c|SYSC_msync|vfs_fsync_range|110808|0|1001|3|$|1

regards,
dan carpenter

Re: Tracking Implicit Dependencies

[Dan Carpenter]

On Fri, Sep 29, 2017 at 03:36:16PM -0400, Andrew Zhu Aday wrote:
> Also, when parsing a function definition, why does smatch only follow
> some internal function calls? For example, in the syscall
> `get_mempolicy` in ``mm/mempolicy.c`,
> it will follow the call to `copy_nodes_to_user`, but will not follow
> `do_get_mempolicy`.
> 
> Is there a way I can make it follow all internal function calls?
> 

I'm not totally sure I understand the question.  It follows everything.

I suspect that what you're looking is that copy_nodes_to_user() is
parsed inline and get_mempolicy() isn't.  In smatch_flow.c look at the
places which reference __inline_fn and you'll see the rules for this.
Basically inlines don't nest, it has to be shorter than 20 lines long
and have a max of 10 statements.

There is the smatch_db.sqlite file normal cross function analysis and
another sqlite DB in ram for handling inline functions.

regards,
dan carpenter

Re: Tracking Implicit Dependencies

[Dan Carpenter]

On Fri, Sep 29, 2017 at 11:50:28PM +0300, Dan Carpenter wrote:
> The cross function database just looks at frob() the value of "x" to

I meant "frob() *passes* the value"...

> frob_two().  But since this is the first time the DB was built then
> we don't know the value of "x".  The next time we build the DB we can
> see how frob() is called so the information about "x" becomes more
> filled out.

regards,
dan carpenter

Re: Tracking Implicit Dependencies

[Dan Carpenter]

On Sat, Sep 23, 2017 at 01:37:45AM -0400, Andrew Zhu Aday wrote:
> Syscall A is an "implicit dependency" of syscall B if A can affect the
> control flow/coverage of B, but B doesn't use A's return value. For example,
> `mlockall` and `msync`; calling `mlockall` before `msync` will cause
> the latter to
> fail with -EBUSY, and thus influences its control flow.

I'm trying to follow along but SYSC_mlockall never returns -EBUSY (16).

$ smdb return_states SYSC_mlockall
file | function | return_id | return_value | type | param | key | value |
mm/mlock.c | SYSC_mlockall | 583 |         (-22) |      INTERNAL |  -1 |                      |         long(*)(int) |
mm/mlock.c | SYSC_mlockall | 584 |          (-1) |      INTERNAL |  -1 |                      |         long(*)(int) |
mm/mlock.c | SYSC_mlockall | 584 |          (-1) |     CULL_PATH |  -1 |                      |                      |
mm/mlock.c | SYSC_mlockall | 584 |          (-1) |   PARAM_LIMIT |   0 |                    $ |                  1-6 |
mm/mlock.c | SYSC_mlockall | 587 |          (-4) |      INTERNAL |  -1 |                      |         long(*)(int) |
mm/mlock.c | SYSC_mlockall | 587 |          (-4) |   PARAM_LIMIT |   0 |                    $ |                  1-6 |
mm/mlock.c | SYSC_mlockall | 615 |             0 |      INTERNAL |  -1 |                      |         long(*)(int) |
mm/mlock.c | SYSC_mlockall | 615 |             0 |   PARAM_LIMIT |   0 |                    $ |                  1-6 |
mm/mlock.c | SYSC_mlockall | 616 |         (-12) |      INTERNAL |  -1 |                      |         long(*)(int) |
mm/mlock.c | SYSC_mlockall | 616 |         (-12) |   PARAM_LIMIT |   0 |                    $ |                  1-6 |
mm/mlock.c | SYSC_mlockall | 616 |         (-12) |       CAPABLE |   0 |                   14 |                      |
================================================
file | function | type | param | key | value |
     mm/mlock.c |   SYSC_mlockall |      PARAM_USED |   0 |               $ |               1 |
$

regards,
dan carpenter

Re: Tracking Implicit Dependencies

[Dan Carpenter]

Here are my thoughts.  This project is actually very difficult...

The resources we're allocating are probably tied to a file or a process
and Smatch doesn't really track that.  It just tracks parameters.  My
idea is that the resources are probably stored in a struct so we could
track that "(struct foo)->bar" gets set by SYSC_one() and checked by
SYSC_two().

Some of the information about when structs are set is stored in
function_type_value().  But the problem is that it ignores too common
functions like you already found out.  And then nothing is saving when
it's queried.

I've never tried this before so it might not work.  And everything is
always more complicated than you'd imagine.

regards,
dan carpenter