This is an archive of the discontinued LLVM Phabricator instance.

[2a/3][ASan][libcxx] std::deque annotations
ClosedPublic

Authored by AdvenamTacet on Aug 17 2022, 6:19 PM.

Details

Summary

This revision is a part of a series of patches extending AddressSanitizer C++ container overflow detection capabilities by adding annotations, similar to those existing in std::vector, to std::string and std::deque collections. These changes allow ASan to detect cases when the instrumented program accesses memory which is internally allocated by the collection but is still not in-use (accesses before or after the stored elements for std::deque, or between the size and capacity bounds for std::string).

The motivation for the research and those changes was a bug, found by Trail of Bits, in a real code where an out-of-bounds read could happen as two strings were compared via a std::equals function that took iter1_begin, iter1_end, iter2_begin iterators (with a custom comparison function). When object iter1 was longer than iter2, read out-of-bounds on iter2 could happen. Container sanitization would detect it.

This revision introduces annotations for std::deque. Each chunk of the container can now be annotated using the __sanitizer_annotate_double_ended_contiguous_container function, which was added in the rG1c5ad6d2c01294a0decde43a88e9c27d7437d157. Any attempt to access poisoned memory will trigger an ASan error. Although false negatives are rare, they are possible due to limitations in the ASan API, where a few (usually up to 7) bytes before the container may remain unpoisoned. There are no false positives in the same way as with std::vector annotations.

This patch only supports objects (deques) that use the standard allocator. However, it can be easily extended to support all allocators, as suggested in the D146815 revision.

Furthermore, the patch includes the addition of the is_double_ended_contiguous_container_asan_correct function to libcxx/test/support/asan_testing.h. This function can be used to verify whether a std::deque object has been correctly annotated.

Finally, the patch extends the unit tests to verify ASan annotations (added LIBCPP_ASSERTs).
If a program is compiled without ASan, all helper functions will be no-ops. In binaries with ASan, there is a negligible performance impact since the code from the change is only executed when the deque container changes in size and it’s proportional to the change. It is important to note that regardless of whether or not these changes are in use, every access to the container's memory is instrumented.

If you have any questions, please email:

  • advenam.tacet@trailofbits.com
  • disconnect3d@trailofbits.com

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
philnik added inline comments.Aug 17 2022, 6:37 PM
libcxx/include/deque
1597

The same through out.

1790

Every implementation-detail symbol should either be _Uglified or __uglified, but never __Uglified.

1849

Please add an end comment to longer preprocessor blocks.

This revision now requires changes to proceed.Aug 17 2022, 6:37 PM
AdvenamTacet marked 7 inline comments as done.

The udpate is fixing issues mentioned in the code review.
Content:

  • fixed formating,
  • use of _LIBCPP_HIDE_FROM_ABI,
  • names and style improvements.

This update should fix failing unit tests and improve code quality.
Content:

  • Fixed includes (thx philnik for pointing that)
  • Improved variable names (more consistent)
  • Values passed to compiler-rt functions are correct now. (There

was an optimization depending on compiler-rt implementation, now
it should be correct even when implementation is extended.)

Overall, it's a very small update.

Herald added a project: Restricted Project. · View Herald TranscriptAug 22 2022, 6:23 AM
Herald added subscribers: Restricted Project, Enna1. · View Herald Transcript

Duplicated file removed.

This update should fix failure of C++03 tests and a format check test.

This update adds clang version check (_LIBCPP_CLANG_VER >= 16000),
because the change requires compiler-rt functions from a parent revision.

As a result, it changes implementation of libcxx/test/support/asan_testing.h.

It also removes a comment fix in compiler-rt function. I will add it to
the parent revision (D132090).

Changin _de_ in names into _double_ended_, based on a review for compiler-rt part.
There will be one more change based on the review.

clang-format (sorry for double update)

Update of API. (A change was requested in review for D132090 and this
patch is reflecting that change - only one function is in API.)

Moving libc++ code from D132090.

I'm sending this update to test annotations with CI.
Updated changes to newer commit.
When I see green CI, I will send an update unifying those changes with D136765 and D132769, as well as minimizing code.

Tests update, code refactor in next update.

This update is a big refactor of code responsible for annotations.
This update reduced size of the patch significantly.
There are only two helper function (one wrapper), both are minimal.

I added a lot of comment to the (new) code, if you want a smaller patch those comments may be removed, but I think it's good to have them.

I belive, the code is ready for a review. I tested it locally (but only with one C++ standard, so there may be some failure, I will fix it asap).

This update:

  • removes incorrect extern,
  • fixes a typo,
  • adds sanity ASan test (not tested).

This update:

  • removed unnecessary macro and related limitations,
  • updates formatting in __annotate_from_to,
  • simplifies calls to helpers in __add_front_capacity.
AdvenamTacet edited the summary of this revision. (Show Details)Mar 29 2023, 7:43 AM
AdvenamTacet edited the summary of this revision. (Show Details)
philnik requested changes to this revision.Mar 31 2023, 2:39 PM

Looks pretty good. I haven't looked closely at the annotation placements and tests yet.

libcxx/include/deque
1204–1205

Same below.

1859

As in other patches, let's give the parameters proper names.

1865
1873

Please don't add a 10th version of formatting. We are trying to reduce the formatting differences, not increase them.

1875

You have specialized functions for there IIUC. Why don't you use them here? There are a few more cases below.

1892

throughout the patch

1971

Missing _LIBCPP_HIDE_FROM_ABI

1976

Please add braces.

2799

Please avoid NFC changes in such a large patch.

2900–2908

Maybe add a function __annotate_whole_block?

libcxx/test/std/containers/sequences/deque/deque.capacity/resize_size.pass.cpp
92–99 ↗(On Diff #508651)

Maybe just call both in the same loop?

This revision now requires changes to proceed.Mar 31 2023, 2:39 PM
AdvenamTacet marked 10 inline comments as done.
AdvenamTacet edited the summary of this revision. (Show Details)

Based on the code review, this update:

  • adds __annotate_whole_block and __annotate_poison_block helpers,
  • updates arguements and variables names in __annotate_from_to and __verify_asan_annotations,
  • changes _VSTD to std,
  • adds missing _LIBCPP_HIDE_FROM_ABI,
  • removes NFC,
  • fixes formatting and comments.
AdvenamTacet added inline comments.Apr 3 2023, 8:11 PM
libcxx/include/deque
1859

I changed __b and __e to __beg and __end. I believe same length makes the code easier to read. Updated also local variable names.

1875

There was no helper for a single block and use of __annotate_shrink_* is impossible as it requires annotated memory area to be just before or just after the container in-use area, but new block may be added not directly before/after. I added __annotate_whole_block.

2900–2908

I added __annotate_poison_block for this. It's not very similar to other helpers, because here we are annotating a memory block in __buf and not in __map_.

libcxx/test/std/containers/sequences/deque/deque.capacity/resize_size.pass.cpp
92–99 ↗(On Diff #508651)

I started doing it, but stopped. I don't think it's a good idea to introduce that change in this patch. There is already a lot of copy-paste of tests, so it would require to refactor all of them or have two different styles in one file.

philnik added inline comments.May 1 2023, 4:02 PM
libcxx/include/deque
1538

Let's add a LLVM 18 TODO to clean this up.

1556

Maybe having two enums like

enum {
  __asan_poinson,
  __asan_unposion
};

enum {
  __asan_front_moved,
  __asan_back_moved,
};

would make this more readable? (and remove the need for the comments below)

1563

I think it's pretty clear what a return; does.

1568

Maybe use __map_const_pointer?

1569

What does the mp stand for?

1659–1663

I would reverse the condition here to match __annotate_new.

2900–2908

Ah. Makes sense.

3058
AdvenamTacet marked 5 inline comments as done.

This update:

  • adds enums (poisoning, unpoisoning; back, front)
  • adds LLVM 18 TODO comment; improves other comments
  • reverses the condition in __annotate_delete.
AdvenamTacet added inline comments.May 1 2023, 7:34 PM
libcxx/include/deque
1568

I did try it at the beginning and there are type related issues. It's much cleaner that way than working around it.

1569

I believe map_pointer, but I used this name based on the rest of the code where it's used.

This update updates a base commit.

philnik accepted this revision.May 3 2023, 10:12 AM

LGTM % nits.

libcxx/include/deque
1568

Let's adda new alias __map_const_iterator then. The typename __map::const_iterator is really irritating.

1569

Let's drop it if nobody knows what it actually stands for.

1710–1712

I think this comment is wrong now?

This revision is now accepted and ready to land.May 3 2023, 10:12 AM
AdvenamTacet marked 5 inline comments as done.

This update addresses all nits.

  • Adds __map_const_iterator.
  • Removes incorrect comments.
  • Addresses _mp sufix.
libcxx/include/deque
1569

I changed it to map, I feel that it makes code much easier to read when it is clear if it points on the map (buffer of buffers) or the actual buffer. Hope it's clear now.

This update fixes an issue with name shadowing and hopefully resolves all CI problems.

This revision was landed with ongoing or failed builds.May 5 2023, 9:11 AM
This revision was automatically updated to reflect the committed changes.
vitalybuka reopened this revision.May 6 2023, 12:23 AM
vitalybuka added a subscriber: vitalybuka.

Asan bots are broken, reverted.

This revision is now accepted and ready to land.May 6 2023, 12:23 AM

Asan bots are broken, reverted.

Could you maybe provide some more information? Which bots were broken by this and what was the error? Without any information we can't address the problem.

It looks like the problem was created when I added __annotate_whole_block. Example buildbot output relevant for this revision: https://lab.llvm.org/buildbot/#/builders/5/builds/33480/steps/13/logs/stdio

==296484==ERROR: AddressSanitizer: bad parameters to __sanitizer_annotate_double_ended_contiguous_container:
      storage_beg        : 0x6210000d0d00
      storage_end        : 0x6210000d1d00
      old_container_beg  : 0x6210000d1b40
      old_container_end  : 0x6210000d1d00
      new_container_beg  : 0x6210000d1b40
      new_container_end  : 0x6210000d0d00
    #0 0x56178e14cac5 in __sanitizer_annotate_double_ended_contiguous_container /b/sanitizer-x86_64-linux-fast/build/llvm-project/compiler-rt/lib/asan/asan_poisoning.cpp:499:5
    #1 0x56178efd3474 in __annotate_double_ended_contiguous_container /b/sanitizer-x86_64-linux-fast/build/libcxx_build_asan/include/c++/v1/deque:893:13
    #2 0x56178efd3474 in __annotate_from_to /b/sanitizer-x86_64-linux-fast/build/libcxx_build_asan/include/c++/v1/deque:991:13
    #3 0x56178efd3474 in __annotate_whole_block /b/sanitizer-x86_64-linux-fast/build/libcxx_build_asan/include/c++/v1/deque:1037:9
    #4 0x56178efd3474 in std::__1::deque<std::__1::pair<std::__1::function<void ()>, llvm::ThreadPoolTaskGroup*>, std::__1::allocator<std::__1::pair<std::__1::function<void ()>, llvm::ThreadPoolTaskGroup*>>>::__add_back_capacity() /b/sanitizer-x86_64-linux-fast/build/libcxx_build_asan/include/c++/v1/deque:2233:13
    #5 0x56178efd1aaf in std::__1::pair<std::__1::function<void ()>, llvm::ThreadPoolTaskGroup*>& std::__1::deque<std::__1::pair<std::__1::function<void ()>, llvm::ThreadPoolTaskGroup*>, std::__1::allocator<std::__1::pair<std::__1::function<void ()>, llvm::ThreadPoolTaskGroup*>>>::emplace_back<std::__1::pair<std::__1::function<void ()>, llvm::ThreadPoolTaskGroup*>>(std::__1::pair<std::__1::function<void ()>, llvm::ThreadPoolTaskGroup*>&&) /b/sanitizer-x86_64-linux-fast/build/libcxx_build_asan/include/c++/v1/deque:1596:9
    [...]

All errors I could find seem to have an origin in __add_back_capacity and I'm almost sure that I see a problem in the function.

I am trying to create unit test catching it and then I will send the next update with fix and tests.

I have a hard time trying to create a stand alone test.
To go to the problematic if branch, push_back should be called when:

  • __back_spare() == 0
  • __front_spare() < __block_size
  • __map_.size() < __map_.capacity()
  • __map_.__back_spare() == 0

The problem is incorrect value argument to a helper function __annotate_whole_block, but actually there is no need to call this function yet (it can be called later after whole if-else block). It's easy to see what is wrong and how to fix it. I have a hard time creating a unit test covering it.

This update fixes the issue with incorrect arguments during deque annotations. Now the patch should work without a problem after landing.

This update resolves merge conflicts with the new head commin on the main branch.

I believe, this revision is ready to land.

This revision was automatically updated to reflect the committed changes.
alexfh added a subscriber: alexfh.May 30 2023, 7:22 PM

Hi @AdvenamTacet, is it expected that the std::deque<const T> can't be compiled after the patch? I couldn't find a clause in the standard that requires deque to have non-const value_type.

Example: https://gcc.godbolt.org/z/sbcvzzbKd

#include <deque>

std::deque<const int> q;
std::deque<const int> qq = q;

@ldionne @EricWF do you know if std::deque<const T> is allowed by the standard? If it's not, can we have a proper static assert (similar to the one in libstdc++: https://gcc.godbolt.org/z/jjzbP3bd4) instead of a vague compiler error?

@alexfh it's not by design. A const_cast is missing (or should I use (void *)?). We may add it in the very place where error happens or later before calling API, but type has to be changed here.

Working on the fix right now.

  • I am going to add a const deque test.
  • Add the const_cast, I believe it's the correct choice.

Ok, I just learned that deque objects have to be assignable/movable, so std::deque<const int> is not correct (from what I understand). Therefore tests for it cannot exist. But it's not my intention to change behavior of std::deque<const T> and therefore I created D151777. The new patch adds a few const. All examples working previously seem to work with D151777, but I found some not working even before this patch.

As - if I'm correct - deque object cannot be of const type, I think I did as much as I could.

It looks like std::deque elements do not need to be copy assignable since C++11 (https://en.cppreference.com/w/cpp/container/deque).

Though it says member functions can impose stricter requirements - I'm not sure if there is a member that still requires copy assignable

vitalybuka reopened this revision.May 31 2023, 1:36 PM

I believe it's reasonable to revert for investigation.

This revision is now accepted and ready to land.May 31 2023, 1:36 PM
vitalybuka added a comment.EditedMay 31 2023, 1:52 PM

Sorry that I had to revert this second time. This one discovered a lot of real bugs in our code.
Please include D151836 or similar test into the patch?

This update (hopefully) brings back old behavior of deque with const elements.

To understand the problem better, I tried to create tests for deque with const elements, but those are failing even in functions that might work. It seems like resize is failing, but it should be possible to make it work changing iterator to const_iterator (didn't test it, tho).
https://godbolt.org/z/qfxTW7aK7

Hey @alexfh, I hope this will solve your problem!
But deque<const T> seems to be poorly supported in general.

PS
MinGW prints:

std::deque must have a non-const, non-volatile value_type

https://godbolt.org/z/zerMG7GTf

This update:

  • adds a test suggested by @vitalybuka (extended to do that kind of caterpillar from every side),
  • removes the issue,
  • reimplementes __annotate_whole_block (last arguments removed; no longer calling __annotate_from_to).

The problem was a very similar to the previous one. Incorrect last argument (argument informing if end or begin of the container moved). It wasn't easy to spot, even that now it's obvious.
I was checking for issues like that previously but I had to miss that one. However, the argument doesn't have much sense, whole block has to be annotated anyway and it's not always obvious what value should be passed in some situations. I reimplemented problematic function, so it does not require the argument. Hope it will help to avoid similar issues in future.

I believe it's ready to land again, as both probles are solved (const element type bahaviour and incorrect annotations), a new test is added and tests passed (locally).

This update changes how __annotate_delete() for an empty container is executed and makrs two functions as const.
It solves issues with non-standard allocators.

Now it's tested with D146815 and both revisions can land.

This update renames the new test and updates it slightly.

AdvenamTacet edited the summary of this revision. (Show Details)Jun 1 2023, 9:43 PM

Hey @vitalybuka, thanks for the standalone failing test (D151836)! It was really helpful! I fixed the problem and hope there are no more issues with that revision (and for no more reverts).

This one discovered a lot of real bugs in our code.

I'm really happy that my code could help!

Hey @philnik, I hope I fixed the patch already and it can go back to upstream, for good this time. Also, D136765 wasn't reverted for a while already, so maybe we can land D146815 as well?

This update fixes a naming issue.

rebase, I hope it fixes the CI fail (doesn't look like issue made by this revision).

Rebase, I hope it will fix the issue with the fail on MacOS.

ld: warning: object file (/Users/libcxx-buildkite-agent/libcxx.buildkite-agent/builds/y10-8-macminivault-com/llvm-project/libcxx-ci/build/apple-system-backdeployment-10.15/lib/libc++experimental.a(memory_resource.cpp.o)) was built for newer macOS version (12.0) than being linked (10.15)
ld: warning: dylib (/Users/libcxx-buildkite-agent/libcxx.buildkite-agent/builds/y10-8-macminivault-com/llvm-project/libcxx-ci/build/apple-system-backdeployment-10.15/lib/libc++.dylib) was built for newer macOS version (12.0) than being linked (10.15)
ld: warning: dylib (/Users/libcxx-buildkite-agent/libcxx.buildkite-agent/builds/y10-8-macminivault-com/llvm-project/libcxx-ci/build/apple-system-backdeployment-10.15/lib/libunwind.dylib) was built for newer macOS version (12.0) than being linked (10.15)
ld: warning: dylib (/Users/libcxx-buildkite-agent/libcxx.buildkite-agent/builds/y10-8-macminivault-com/llvm-project/libcxx-ci/build/apple-system-backdeployment-10.15/lib/libunwind.dylib) was built for newer macOS version (12.0) than being linked (10.15)

This update:

  • removes XFAIL as the test should always pass,
  • removes _LIBCPP_ENABLE_ASSERTIONS=1 because ASan assertions are catched anyway.

I copt-pasted those, but there is no need for them, I believe.

Updating libcxx/include/__config in response to _LIBCPP_FUNC_VIS removal.

Used: _LIBCPP_EXPORTED_FROM_ABI

This revision was automatically updated to reflect the committed changes.

I hope I fixed everything requested, cannot find anything else to fix. I hope this time it landed for the last time...
I see buildbot failures, but I don't see how my patch may be the cause (one, two).

This one discovered a lot of real bugs in our code.

Hey @vitalybuka, could you share a little bit more? Like statistics, in what projects, how those bugs look like, was there any more interesting? I will appreciate any and every data which we can use!

I hope I fixed everything requested, cannot find anything else to fix. I hope this time it landed for the last time...
I see buildbot failures, but I don't see how my patch may be the cause (one, two).

This one discovered a lot of real bugs in our code.

Hey @vitalybuka, could you share a little bit more? Like statistics, in what projects, how those bugs look like, was there any more interesting? I will appreciate any and every data which we can use!

I have number of bugs we had to fix after the first attempt to integrate, but, I guess, it's meaningless on it's own, without any baseline.
From my experience of enabling https://libcxx.llvm.org/UsingLibcxx.html#enabling-the-safe-libc-mode on the same code-base, my very rough estimate is that your patch fetched at least 10% of additional bugs to the "safe libc++ mode".

Unfortunately all discoveries so far are in internal code, nothing to share from open sourced components yet. Maybe chromium.org or https://github.com/google/oss-fuzz will find bugs in open source libraries. But they didn't integrated the patch yet.

At least 90% of these bugs look like https://godbolt.org/z/eGddPd3qs or std::stack equivalent. Note that for large 'n' you can already expect SEGV or 'heap-use-after-free' with existing Asan. But smaller 'n' was not covered before your patches.

Also very good news that fixing those bugs very easy, either remove the reference or swap use and pop(). This mean fix rate for discovered bugs should be very high.

BTW. This pattern is quote similar to typical implementations work-lists, BFS and DFS algorithms. We have them in LLVM. We run LLVM under Asan here https://lab.llvm.org/buildbot/#/builders/168, but I didn't see any related reports.

ldionne added inline comments.Jul 5 2023, 7:24 AM
libcxx/include/__config
910 ↗(On Diff #534836)

This breaks on AppleClang when using asan, because then _LIBCPP_CLANG_VER isn't defined and we check for _LIBCPP_CLANG_VER >= 1600. That triggers -Wundef, which is turned into an error in our test suite.

ldionne added inline comments.Jul 5 2023, 7:25 AM
libcxx/include/deque
1548

Same here for -Wundef.

AdvenamTacet added inline comments.Jul 5 2023, 7:52 AM
libcxx/include/__config
910 ↗(On Diff #534836)

Hey! What is the correct way of checking the version then?

Also, can I fix it in another commit, or should we revert the whole commit, fix it and land it again?

libcxx/test/support/asan_testing.h