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

[xiangzhai]

Bugzilla Link	31458
Version	3.9
OS	Linux
CC	@AnnaZaks

Extended Description

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

[xiangzhai]

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

[haoNoQ]

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

[xiangzhai]

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

[haoNoQ]

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.

[haoNoQ]

Trimmed exploded graph.

[haoNoQ]

Preprocessed file.

[xiangzhai]

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

[0f73b9cf-134f-41af-a8b1-14d9f305ee95]

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.

[xiangzhai]

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

[xiangzhai]

assigned to @haoNoQ