[cocci] Depends on with negative matches

[cocci] Depends on with negative matches

[Mats Kindahl]

[-- Attachment #1: Type: text/plain, Size: 5359 bytes --]

Hi all,

I want have a case where I want to find missing resource releases. The 
real case is a different one, so I am creating a similar case using 
malloc() and want to find any malloc() that is either not freeing the 
memory or returning it to the caller. Here are a few cases:

    #include <stdio.h>
    #include <stdlib.h>

    struct something {
       const char *here;
       int ok;
    };

    /* This should match */
    void func_1() {
       struct something *foo;
       foo = malloc(sizeof(struct something));
       if (!foo) {
         printf("Error %s", foo->here);
         return;
       }
       foo->ok = 1;
    }

    /* This should NOT match */
    struct something *func_2() {
       struct something *foo;
       foo = malloc(sizeof(struct something));
       if (foo) {
         foo->ok = 1;
         return foo;
       }
       printf("Error %s", foo->here);
       return NULL;
    }

    /* This should NOT match */
    struct something *func_3() {
       struct something *foo;
       foo = malloc(sizeof(struct something));
       if (!foo) {
         printf("Error %s", foo->here);
         return NULL;
       }
       foo->ok = 1;
       return foo;
    }

    /* This should match */
    void func_4(struct something *foo) {
       if (!foo)
         foo = malloc(sizeof(struct something));
       foo->ok = 1;
       printf("Error %s", foo->here);
    }

    /* This should NOT match */
    void func_5(struct something *foo) {
       if (!foo)
         foo = malloc(sizeof(struct something));
       foo->ok = 1;
       printf("Error %s", foo->here);
       free(foo);
    }

    /* This should NOT match */
    struct something *func_6(struct something *foo) {
       if (!foo)
         foo = malloc(sizeof(struct something));
       foo->ok = 1;
       printf("Error %s", foo->here);
       return foo;
    }

I tried this semantic patch, but unfortunately it does not seem to 
capture the dependencies correctly.

    // Capture any malloc() to a local variable
    @r@
    local idexpression var;
    position p;
    @@
       var@p = malloc(...);

    // Detect cases that either free the variable or return it. Expect an
    // intermediate NULL check with error handling code that can do
    // anything it likes.
    @r1@
    local idexpression r.var;
    position r.p;
    statement S;
    @@
       var@p = malloc(...);
       ...
       if (var == NULL) S
       ...
    (
       free(var);
    |
       return var;
    )

    // Detect cases that either free the variable or return it. Expect an
    // non-NULL check that then either returns or free the variable. We
    // ignore any code that follows this if statement and assume that is
    // error handling code.
    @r2@
    local idexpression r.var;
    position r.p;
    @@
       var@p = malloc(...);
       ...
       if (var != NULL) {
         ...
    (
         free(var);
         ...
    |
         return var;
    )
       }

    // If neither of the above cases match, then we have a bad malloc, so
    // mark it.
    @depends on !r1 && !r2@
    local idexpression r.var;
    position r.p;
    @@
    * var@p = malloc(...);

Unfortunately, it matches correctly in most cases, but some of the cases 
are not detected correctly.

    mats@abzu:~/lang/cocci/tests$ spatch --sp-file missing_free.cocci
    code/malloc-example.c
    init_defs_builtins: /usr/lib/coccinelle/standard.h
    HANDLING: code/malloc-example.c
    diff =
    --- code/malloc-example.c
    +++ /tmp/cocci-output-172050-d31474-malloc-example.c
    @@ -9,7 +9,6 @@ struct something {
    /* This should match */
    void func_1() {
       struct something *foo;
    -  foo = malloc(sizeof(struct something));
       if (!foo) {
         printf("Error %s", foo->here);
         return;
    @@ -44,7 +43,6 @@ struct something *func_3() {
    /* This should match */
    void func_4(struct something *foo) {
       if (!foo)
    -    foo = malloc(sizeof(struct something));
       foo->ok = 1;
       printf("Error %s", foo->here);
    }
    @@ -52,7 +50,6 @@ void func_4(struct something *foo) {
    /* This should NOT match */
    void func_5(struct something *foo) {
       if (!foo)
    -    foo = malloc(sizeof(struct something));
       foo->ok = 1;
       printf("Error %s", foo->here);
       free(foo);
    @@ -61,7 +58,6 @@ void func_5(struct something *foo) {
    /* This should NOT match */
    struct something *func_6(struct something *foo) {
       if (!foo)
    -    foo = malloc(sizeof(struct something));
       foo->ok = 1;
       printf("Error %s", foo->here);
       return foo;

I tried to look at the kmalloc() examples in the coccinellery and also 
some other examples in the source code that seems to do similar things, 
but none have this case with "either free or return" and multiple cases 
with negative dependencies. It seems like you can get it mostly correct 
if you just keep the first rule only (with the NULL check), but I want 
to capture the "positive branch" case as well, where you check for 
non-NULL and then execute some code that should end with either a free 
or a return.

Anybody have some insight into what I've done wrong or if there is a 
better way to solve this problem?

Best wishes,
Mats Kindahl


[-- Attachment #2: Type: text/html, Size: 8384 bytes --]

Re: [cocci] Depends on with negative matches

[Julia Lawall]

Thanks for the many test cases.

You can try this:

@r@
local idexpression var;
position p;
@@
var@p = malloc(...)

@@
local idexpression r.var;
position r.p;
@@

*var@p = malloc(...)
... when != true var == NULL
    when != false var != NULL
    when != free(var)
    when != return (var);

You may want to add some more when clauses like when != e->f = var

julia

Re: [cocci] Detecting missing resource releases (with SmPL)?

[Markus Elfring]

> Anybody have some insight

Probably, yes.

Which information sources should get more development attention?


> into what I've done wrong

Some circumstances can make your source code analysis attempts more challenging.


> or if there is a better way to solve this problem?

Further software design possibilities can be taken better into account.
How will technical aspects be clarified accordingly?

Regards,
Markus

Re: [cocci] Scope for source code analyses (with SmPL)?

[Markus Elfring]

> I want have a case where I want to find missing resource releases.
…

Does it matter for you if desired resource releases should usually be performed
within the same function implementation (or not)?

Would you like to care for inter-procedural source code analyses?
https://en.wikipedia.org/wiki/Control-flow_graph#Inter-procedural_control-flow_graph

See also:
https://gitlab.inria.fr/coccinelle/coccinelle/-/blob/f0ebfea0e00e844e16c4403d790e9a8df87036a9/docs/manual/cocci_syntax.tex#L1771-1774

Regards,
Markus

Re: [cocci] Depends on with negative matches

[Mats Kindahl]

[-- Attachment #1: Type: text/plain, Size: 4554 bytes --]

Thank you Julia,

It worked for the example I gave, but the "real" code has validation 
functions rather than comparisons with NULL, and when I tested with 
that, it did not work. Here is a modified version of the code closer to 
what have:

    #include <stdbool.h>
    #include <stdio.h>
    #include <stdlib.h>

    extern bool PointerIsValid(const void *pointer);

    struct something {
       const char *here;
       int ok;
    };

    /* This should match */
    void func_1() {
       struct something *foo;
       foo = malloc(sizeof(struct something));
       if (!PointerIsValid(foo)) {
         printf("Error %s", foo->here);
         return;
       }
       foo->ok = 1;
    }

    /* This should NOT match */
    struct something *func_2() {
       struct something *foo;
       foo = malloc(sizeof(struct something));
       if (PointerIsValid(foo)) {
         foo->ok = 1;
         return foo;
       }
       printf("Error %s", foo->here);
       return NULL;
    }

    /* This should NOT match */
    struct something *func_3() {
       struct something *foo;
       foo = malloc(sizeof(struct something));
       if (!PointerIsValid(foo)) {
         printf("Error %s", foo->here);
         return NULL;
       }
       foo->ok = 1;
       return foo;
    }

    /* This should match */
    void func_4(struct something *foo) {
       if (!PointerIsValid(foo))
         foo = malloc(sizeof(struct something));
       foo->ok = 1;
       printf("Error %s", foo->here);
    }

    /* This should NOT match */
    void func_5(struct something *foo) {
       if (!PointerIsValid(foo))
         foo = malloc(sizeof(struct something));
       foo->ok = 1;
       printf("Error %s", foo->here);
       free(foo);
    }

    /* This should NOT match */
    struct something *func_6(struct something *foo) {
       if (!PointerIsValid(foo))
         foo = malloc(sizeof(struct something));
       foo->ok = 1;
       printf("Error %s", foo->here);
       return foo;
    }

Here is the new version of the semantic patch:

    // Capture any malloc() to a local variable
    @r@
    local idexpression var;
    position p;
    @@
       var@p = malloc(...)

    @@
    local idexpression r.var;
    position r.p;
    @@
    * var@p = malloc(...);
       ... when != false !PointerIsValid(var)
           when != true PointerIsValid(var)
           when != free(var)
           when != return (var);

And here is the result.

    mats@abzu:~/lang/cocci/tests$ spatch --sp-file missing_free.cocci
    code/malloc-example.c
    init_defs_builtins: /usr/lib/coccinelle/standard.h
    HANDLING: code/malloc-example.c
    diff =
    --- code/malloc-example.c
    +++ /tmp/cocci-output-177912-b5da93-malloc-example.c
    @@ -12,7 +12,6 @@ struct something {
    /* This should match */
    void func_1() {
       struct something *foo;
    -  foo = malloc(sizeof(struct something));
       if (!PointerIsValid(foo)) {
         printf("Error %s", foo->here);
         return;
    @@ -23,7 +22,6 @@ void func_1() {
    /* This should NOT match */
    struct something *func_2() {
       struct something *foo;
    -  foo = malloc(sizeof(struct something));
       if (PointerIsValid(foo)) {
         foo->ok = 1;
         return foo;
    @@ -35,7 +33,6 @@ struct something *func_2() {
    /* This should NOT match */
    struct something *func_3() {
       struct something *foo;
    -  foo = malloc(sizeof(struct something));
       if (!PointerIsValid(foo)) {
         printf("Error %s", foo->here);
         return NULL;
    @@ -47,7 +44,6 @@ struct something *func_3() {
    /* This should match */
    void func_4(struct something *foo) {
       if (!PointerIsValid(foo))
    -    foo = malloc(sizeof(struct something));
       foo->ok = 1;
       printf("Error %s", foo->here);
    }

I was assuming that you could pass in any expression in the "when != 
true expr", since that is what the grammar says. Was that wrong or did I 
make a mistake?

Best wishes,
Mats Kindahl

On 2024-12-19 08:53, Julia Lawall wrote:
> Thanks for the many test cases.
>
> You can try this:
>
> @r@
> local idexpression var;
> position p;
> @@
> var@p = malloc(...)
>
> @@
> local idexpression r.var;
> position r.p;
> @@
>
> *var@p = malloc(...)
> ... when != true var == NULL
>      when != false var != NULL
>      when != free(var)
>      when != return (var);
>
> You may want to add some more when clauses like when != e->f = var
>
> julia

[-- Attachment #2: Type: text/html, Size: 7263 bytes --]

Re: [cocci] Depends on with negative matches

[Markus Elfring]

> It worked for the example I gave,

Nice …


> but the "real" code

Is this viewable by any public interfaces?


> has validation functions rather than comparisons with NULL,

How much will such an implementation detail matter?


> and when I tested with that, it did not work.

Will corresponding case distinctions be reconsidered?


…
> Here is the new version of the semantic patch:
>
>     // Capture any malloc() to a local variable
>     @r@
>     local idexpression var;
>     position p;
>     @@
>       var@p = malloc(...)
>
>     @@
>     local idexpression r.var;
>     position r.p;
>     @@
>     * var@p = malloc(...);
>       ... when != false !PointerIsValid(var)
>           when != true PointerIsValid(var)
>           when != free(var)
>           when != return (var);
…

I would appreciate further clarifications of previously mentioned development concerns.

Regards,
Markus

Re: [cocci] Depends on with negative matches

[Julia Lawall]

I think you just had true and false backwards:

// Capture any malloc() to a local variable
@r@
local idexpression var;
position p;
@@
  var@p = malloc(...)

@@
local idexpression r.var;
position r.p;
@@
* var@p = malloc(...);
  ... when != true !PointerIsValid(var)
      when != false PointerIsValid(var)
      when != free(var)
      when != return (var);

For example, you don't want to complain if there is a path with no free,
but that path goes through a failing pointer is valid test.

julia

Re: [cocci] Depends on with negative matches

[Markus Elfring]

…
> For example, you don't want to complain if there is a path with no free,
> but that path goes through a failing pointer is valid test.

Would you get into the mood to discuss algorithmic properties any more?

Regards,
Markus

Re: [cocci] Depends on with negative matches

[Mats Kindahl]

Hi Julia,

Thanks you! I feel really stupid, but now it works. My only excuse is 
that the documentation for "when != true <expr>" is not very elaborate. :)

Thanks again Julia,
Mats Kindahl

On 2024-12-20 22:54, Julia Lawall wrote:
> I think you just had true and false backwards:
>
> // Capture any malloc() to a local variable
> @r@
> local idexpression var;
> position p;
> @@
>    var@p = malloc(...)
>
> @@
> local idexpression r.var;
> position r.p;
> @@
> * var@p = malloc(...);
>    ... when != true !PointerIsValid(var)
>        when != false PointerIsValid(var)
>        when != free(var)
>        when != return (var);
>
> For example, you don't want to complain if there is a path with no free,
> but that path goes through a failing pointer is valid test.
>
> julia

Re: [cocci] Depends on with negative matches

[Julia Lawall]

On Sat, 21 Dec 2024, Mats Kindahl wrote:

> Hi Julia,
>
> Thanks you! I feel really stupid, but now it works. My only excuse is that the
> documentation for "when != true <expr>" is not very elaborate. :)

Great that it works :)

julia

>
> Thanks again Julia,
> Mats Kindahl
>
> On 2024-12-20 22:54, Julia Lawall wrote:
> > I think you just had true and false backwards:
> >
> > // Capture any malloc() to a local variable
> > @r@
> > local idexpression var;
> > position p;
> > @@
> >    var@p = malloc(...)
> >
> > @@
> > local idexpression r.var;
> > position r.p;
> > @@
> > * var@p = malloc(...);
> >    ... when != true !PointerIsValid(var)
> >        when != false PointerIsValid(var)
> >        when != free(var)
> >        when != return (var);
> >
> > For example, you don't want to complain if there is a path with no free,
> > but that path goes through a failing pointer is valid test.
> >
> > julia
>

Re: [cocci] Depends on with negative matches

[Markus Elfring]

> I feel really stupid, but now it works.

Will any solution approaches become more interesting for known software limitations?

Regards,
Markus