False positive Use-after-free about partclone/srv/btrfs/volumes.c line 170

[Quuxplusone]

Bugzilla Link	PR31458
Status	NEW
Importance	P normal
Reported by	Leslie Zhai (zhaixiang@loongson.cn)
Reported on	2016-12-23 01:28:22 -0800
Last modified on	2017-01-17 21:34:24 -0800
Version	3.9
Hardware	PC Linux
CC	ganna@apple.com, llvm-bugs@lists.llvm.org
Fixed by commit(s)
Attachments	volumes.c (349007 bytes, text/x-csrc) graph.svg (4685696 bytes, image/svg+xml)
Blocks
Blocked by
See also

Hi clang developers,

After reviewed the code https://github.com/Thomas-
Tsai/partclone/blob/master/src/btrfs/volumes.c#L164

I argue that it is false positive Use-after-free for Clang Static Analyzer
https://pbs.twimg.com/media/C0WBcn6VEAAS1Rp.jpg

because device is reassgin!

    while (!list_empty(&fs_devices->devices)) {
--- reassign ----> device = list_entry(fs_devices->devices.next,
                    struct btrfs_device, dev_list);
        if (device->fd != -1) {
            fsync(device->fd);
            if (posix_fadvise(device->fd, 0, 0, POSIX_FADV_DONTNEED))
                fprintf(stderr, "Warning, could not drop caches\n");
            close(device->fd);
            device->fd = -1;
        }
        device->writeable = 0;
        list_del(&device->dev_list);
        /* free the memory */
        free(device->name);
        free(device->label);
        free(device);
    }

Regards,
Leslie Zhai

[Quuxplusone]

The same issue: https://pbs.twimg.com/media/C0WGNQtVQAAiBbh.jpg

if btrfs_open_devices failed to open such device, ret value is ALWAYS !0 so
goto out, it will *NOT* handle fs_devices or fs_devices->seed any more.

Regards,
Leslie Zhai

[Quuxplusone]

These could be different issues.

In the first example, I suspect the analyzer steps into 'list_entry'. What does that expand to? Maybe you could attach a preprocessed file?

In the second case, the analyzer does not capture the relation between the two variables.

[Quuxplusone]

> These could be different issues.

Sorry, I will report another bug, and thanks for your reply ;-)

>
> In the first example, I suspect the analyzer steps into 'list_entry'. What
> does that expand to? Maybe you could attach a preprocessed file?

list_entry is defined here https://github.com/isoft-
linux/partclone/blob/master/src/btrfs/list.h#L302

and container_of is defined here https://github.com/isoft-
linux/partclone/blob/master/src/btrfs/kerncompat.h#L294

[Quuxplusone]

Attached volumes.c (349007 bytes, text/x-csrc): Preprocessed file.

[Quuxplusone]

Attached graph.svg (4685696 bytes, image/svg+xml): Trimmed exploded graph.

[Quuxplusone]

Added a preprocessed file. Clang run line to reproduce the issue:

clang -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -disable-llvm-verifier -main-file-name volumes.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-eagerly-assume -analyzer-checker=core -analyzer-checker=unix -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-output plist -w -mrelocation-model static -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -momit-leaf-frame-pointer -dwarf-column-info -resource-dir /usr/bin/../lib/clang/3.7.1 -D HAVE_CONFIG_H -D LOCALEDIR="/usr/local/share/locale" -D _FILE_OFFSET_BITS=64 -D BTRFS -D BTRFS_FLAT_INCLUDES -I . -I .. -internal-isystem /usr/local/include -internal-isystem /usr/bin/../lib/clang/3.7.1/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -ferror-limit 19 -fmessage-length 0 -mstackrealign -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -x c volumes.c -analyze-function btrfs_close_devices

Now, something strange is going on. In the exploded graph i see that the while-loop is at first assumed to execute 0 times, then we unpack the ->seed and goto again:, and only then enter the loop. However, user bug reports aren't showing any of this, and always say that we enter the loop first.

Looking further into this.

[Quuxplusone]

Hi Artem,

Thanks for your research!

And I will learn how to generate CFG svg to fix the strange issue
https://llvm.org/bugs/show_bug.cgi?id=31603
Analyzer is OK for my reduced testcase, but I have no idea why False positive
for *REAL* partclone project...

Regards,
Leslie Zhai

[Quuxplusone]

We have the following structures on the heap inside the while-loop:

             +-----------------+ +-----------------+
             |*fs_devices      | |*device          |
... -------+ |+---------------+| |+---------------+| +------- ...
        (?)| ||.devices       || ||.dev_list      || |(?)
    +-----+| ||+-----+ +-----+|| ||+-----+ +-----+|| |+-----+
... |.next|===>|.prev| |.next|===>||.prev| |.next|===>|.prev| ...
    +-----+| ||+-----+ +-----+|| ||+-----+ +-----+|| |+-----+
... -------+ |+---------------+| |+---------------+| +------- ...
             +-----------------+ +-----------------+

The "list_entry()" macro recovers the pointer to the device structure from
"fs_devices->devices.next", which actually points to the ".dev_list" field; the
offset is 0 but it doesn't matter.

Now, the analyzer sees that "*device" is removed from the list upon
"list_del(&device->dev_list)". However, the analyzer fails to realize that
"device->dev_list.prev" is actually intended to point back to fs_devices-
>devices.

It is obvious that this is the case for a human reader (who spent a few days
debugging this positive and trying to understand this code), however the
analyzer considers the possibility that "device->dev_list.prev" points to a
completely different unknown place somewhere on the heap.

What happens next: assuming that "fs_devices->devices" is untouched by the
"list_del" operation, the analyzer enters the while-loop again and sees that
"*fs_devices" is completely untouched. This is why he figures out that device
is reassigned to the same value, which was already released on the previous
iteration.

So the analyzer says that by supplying an ill-formed doubly-linked list we
could hang this function into an infinite loop of use-after-free's. Such
positives are usually suppressed with assertions; ideally, we should have been
able to assert that all lists are well-formed somewhere in the list functions.

Now, we can't do even that, because our heap-shape/alpha-renaming/whatever
thingy is not powerful enough to handle such assertion (there are rough ideas
on how to improve it, but it'd take time). So at the moment i do not really see
how to suppress this positive apart from disabling the whole function with
#ifndef __clang_analyzer__.

[Quuxplusone]

Hi Artem,

> ... So the analyzer says that by supplying an ill-formed doubly-linked list
we could hang this function into an infinite loop of use-after-free ...

Great analysis!

And I am *NOT* available until Feb 11 2017, because I will goto small village,
without (limited) network access, for Chinese Spring Festival. so Happy Chicken
Year ;-)

Regards,
Leslie Zhai