[2b/3][ASan][libcxx] std::basic_string annotations

[AdvenamTacet]

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 adds annotations for std::basic_string. Long string is very similar to std::vector, and therefore works well with __sanitizer_annotate_contiguous_container from LLVM 15 and therefore annotations works if that implementation is compiled with previous LLVM.
However, only the standard allocator is supported.

As D132522 extended possibilities of __sanitizer_annotate_contiguous_container, now annotations may be supported with all allocators, but that support will be added in next patch. Only strings with default allocator are annotated with that patch.

There is also support for annotating objects using short string optimization.
This is limited functionality. If ASan is extended and (for example) objects on stack should not be annotated (note that not every short string is on stack), __annotate_short_string_check should be modified to return false in those situations.

If you have any questions, please email:

• [e-mail]
• [e-mail]

[philnik]

libcxx/include/string

1857

Isn't this redundant? __annotate_short_string_check() already checks this.

3098–3099

The indentation is wrong.

3159

I think the annotations in __grow_by are wrong. Since __grow_by doesn't change the size of the string, it should annotate the memory to be __old_sz large, not that all the memory is available. That should fix the inconsistency here. Then you can just call __null_terminate_at before traits_type::assign and everything should be working properly. This would then also catch problems in a user-defined traits_type::assign.

libcxx/test/std/strings/basic.string/string.nonmembers/string_op+/string_string.pass.cpp

42

All these checks are libc++-specific, so we should mark them that way.

libcxx/test/support/asan_testing.h

38

51

54

[AdvenamTacet]

This update:

• adds requested comments,
• sets asserts to libc++ specific (LIBCPP_ASSERT),
• applies small code fixes:
  • _LIBCPP_CLANG_VER -> TEST_CLANG_VER,
  • std::__libcpp_is_constant_evaluated() -> TEST_IS_CONSTANT_EVALUATED,
  • __is_string_short -> is_string_short,
  • removes incorrect comments,
  • fixes indentation.

[AdvenamTacet]

libcxx/include/string

1857

But for long strings it also has to be checked, as every string is long during constant evaluation.

bool __is_long() const _NOEXCEPT {
    if (__libcpp_is_constant_evaluated())
        return true;

It has to be checked here and we cannot wait until the check in __annotate_contiguous_container, because during constant evaluation, next line would rise cannot perform pointer arithmetic on null pointer.

I don't want to remove it from __annotate_short_string_check(), because then returned values won't be correct.
And I don't want to remove it from __annotate_contiguous_container to make sure it can be simply called.
It also has no impact on performance.

Possibly it may be changed to __annotate_short_string_check() || (!__libcpp_is_constant_evaluated() && __is_long()), but I have a strong preference for current version, as that would suggest possibility of poisoning short string during constant evaluation.

[AdvenamTacet]

This update fixes problem with __grow_by:

• it adds __set_long_size(__old_sz); to __grow_by and thanks to that, size value is always correct,
• it changes how __grow_by annotates memory,
• it adds new annotations, required after above change.

[AdvenamTacet]

libcxx/include/string

3159

Ugh... my original comment was correct, please ignore my previous response. Sorry for confusion.

Since __grow_by doesn't change the size of the string, it should annotate the memory to be __old_sz large, not that all the memory is available.

I agree, it makes more sense. I changed it. Now it works like that.

Btw. previous implementation didn't just unpoison whole memory. as __grow_by knows how many elements will be added, it unpoisoned exact number of bytes, so the buffer were ready.

---

The problem is with size value. In original implementation, __grow_by does not call __set_long_size, therefore if it's called in a short string, size value is no longer correct.

• I added a call to __set_long_size inside __grow_by.
• Fixed how it annotates buffers (1).
• I made minimal changes to functions using __grow_by (now diff with master is much smaller).

The real problem was later in __annotate_increace(n) called by __null_terminate_at, which requires a correct size value.

---

I see that my last patch failed, but it should be easy to fix, I had to make a mistake with updating some value.
Somewhere inside ::assign(size_type __n, value_type __c).

$ "/usr/bin/python3.10" "/home/libcxx-builder/.buildkite-agent/builds/356fcbab9cbd-1/llvm-project/libcxx-ci/libcxx/test/../utils/run.py" "--execdir" "/home/libcxx-builder/.buildkite-agent/builds/356fcbab9cbd-1/llvm-project/libcxx-ci/build/generic-asan/test/std/strings/basic.string/string.modifiers/string_assign/Output/size_char.pass.cpp.dir" "--" "/home/libcxx-builder/.buildkite-agent/builds/356fcbab9cbd-1/llvm-project/libcxx-ci/build/generic-asan/test/std/strings/basic.string/string.modifiers/string_assign/Output/size_char.pass.cpp.dir/t.tmp.exe"
# command stderr:
AddressSanitizer: CHECK failed: asan_poisoning.cpp:454 "((*(u8 *)MemToShadow(a))) == ((0))" (0x2, 0x0) (tid=354701)
    #0 0x5651a5546f51 in __asan::CheckUnwind() asan_rtl.cpp.o
    #1 0x5651a555ea32 in __sanitizer::CheckFailed(char const*, int, char const*, unsigned long long, unsigned long long) (/home/libcxx-builder/.buildkite-agent/builds/356fcbab9cbd-1/llvm-project/libcxx-ci/build/generic-asan/test/std/strings/basic.string/string.modifiers/string_assign/Output/size_char.pass.cpp.dir/t.tmp.exe+0xdaa32) (BuildId: 05ded1d03f29cb11827d1b47b24d2ce97422315a)
    #2 0x5651a55402ca in __sanitizer_annotate_contiguous_container (/home/libcxx-builder/.buildkite-agent/builds/356fcbab9cbd-1/llvm-project/libcxx-ci/build/generic-asan/test/std/strings/basic.string/string.modifiers/string_assign/Output/size_char.pass.cpp.dir/t.tmp.exe+0xbc2ca) (BuildId: 05ded1d03f29cb11827d1b47b24d2ce97422315a)
    #3 0x5651a557cfbb in std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char>>::__annotate_contiguous_container[abi:v170000](void const*, void const*, void const*, void const*) const /home/libcxx-builder/.buildkite-agent/builds/356fcbab9cbd-1/llvm-project/libcxx-ci/build/generic-asan/include/c++/v1/string:1841:11
    #4 0x5651a557f60a in std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char>>::__annotate_shrink[abi:v170000](unsigned long) const /home/libcxx-builder/.buildkite-agent/builds/356fcbab9cbd-1/llvm-project/libcxx-ci/build/generic-asan/include/c++/v1/string:1874:9
    #5 0x5651a557c32d in std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char>>::__null_terminate_at[abi:v170000](char*, unsigned long) /home/libcxx-builder/.buildkite-agent/builds/356fcbab9cbd-1/llvm-project/libcxx-ci/build/generic-asan/include/c++/v1/string:2050:9
    #6 0x5651a557b48f in std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char>>::assign(unsigned long, char) /home/libcxx-builder/.buildkite-agent/builds/356fcbab9cbd-1/llvm-project/libcxx-ci/build/generic-asan/include/c++/v1/string:2608:12

[AdvenamTacet]

This update fixes issues mention above, the problem was missing if.
(__annotate_increase should be called only when size was increased).

I also refactored helpers, as every time __beg and __end are same, there
is no point to pass them every time.
Now those variables are set in __annotate_contiguous_container.

In next update I will remove support for different allocators and move them to
a new patch, similar to D136765. Here I want to confirm that everything works on CI.

[AdvenamTacet]

This update applies the patch to newest commit from master branch.

[AdvenamTacet]

Using std::addressof instead of &.
Patch applied to a newer commit from master.

[AdvenamTacet]

This update removes support for all allocators, now annotations work with only default allocator.
It updates the test, maing sure that with other allocators memory is not poisoned.

It also adds a way to turn off annotations with _LIBCPP_ASAN_ANNOTATE_ONLY_LONG, in case someone has a specific case where short strings shouldn't be annotated.

Support for annotating all allocators will be added in a separate patch.

I believe, this patch is ready for upstreaming.

[ldionne]

Could you give a really simple example of issues this allows catching? Like the "Hello world" for this new functionality. I think that would be useful for folks (at least for me) to understand concretely what we're gaining (I have no doubt we're gaining something, I just don't see it clearly in my mind).

I see a lot of added complexity in this patch. It's only a couple of ifs here and there, but it's in some of the trickiest code and most used code in the library. And that code is already very much in need of refactoring. Honestly, that makes me worried and from the maintainability and ease-to-validate-correctness perspective, this is only making things worse. It may still be worth doing if we're gaining something massive in return, but there's a clear tradeoff here. Also, this area is:

1. Super tricky cause it touches critical and already crufty code that few people understand well
2. In active development: constexpr-ification recently, hardening work, the debug mode that we gotta probably rip out, and now this

All in all, I guess I wish there had been a design document/RFC explaining this stack of changes before starting to try to get code changes into the library. If there's one, please point it out to me and apologies for my ignorance.

libcxx/include/__string/extern_template_lists.h

30

Using ASAN is an ABI affecting change, kind of like our debug mode. Doing this will only seem to make things work, but in reality it'll cause other problems. For example, if you take a string created inside the dylib (without ASAN) and you try to use it from your ASAN-compiled user program, I assume you'll run into issues, right?

The solution is (quite unfortunately) to have a different built library for that configuration, unless I missed something.

libcxx/include/string

1848

_LIBCPP_ASAN_ANNOTATE_ONLY_LONG adds yet another configuration option. We try not to add configuration options unless we absolutely need to, so I would remove it. If users need to specify whether to annotate short strings or not, IMO the feature is mis-designed. Users shouldn't even be aware of the fact that we have short strings and long strings and they are implemented differently.

[AdvenamTacet]

This update reverts part of a previous update and removes _LIBCPP_ASAN_ANNOTATE_ONLY_LONG.

[AdvenamTacet]

libcxx/include/__string/extern_template_lists.h

30

In general, ASan does accept false positives in situation when part of the program is compiled without ASan. That may happen with std::vector annotations already. But minimizing the risk of it is a good course of action.
I agree that a separate built is the goal solution. I think, it may work as a temporary solution and then be changed into a separate library built. What do you think?

But I understand if you disagree, just I'm also not sure what has to be changed here to add an ASan library build to llvm. What has to be done? Where should I look to learn it?
Please, let me know.

libcxx/include/string

1848

It's not necessary, I added it after discussion about problems ChromeOS had as another way to turn off annotations more granularly. However, I believe that D145628 already answers that problem. Removed it.

[AdvenamTacet]

@ldionne When a program is compiled with ASan, these annotations allow it to detect all accesses to memory that has been allocated but is not currently in use by an object of std::basic_string type. The only exception are functions where instrumentation has been explicitly disabled.

String annotations already exist in Microsoft C++ Standard Library.
Link: https://devblogs.microsoft.com/cppblog/stdstring-now-supports-address-sanitizer/

It’s not the same as libc++ hardening. While all accesses with operator[] or iterators are also detected, particularly important are cases with raw pointers, such as when passing data to C functions (strcpy() etc.).

The simplest example may be:

std::string s = “abcdefg”;
char *ptr = &s[4];
s = “”;
char c = *ptr; // ASan error

A write to *ptr would be detected as well.

Examples of what is detected are:

• incorrect use of C functions,
• random access to that memory (*(char *)randint() = 'x'; will be detected, if by chance unused strings memory is accessed),
• use after resize (as in the example above),
• other BO etc.

A real world bug, which motivated that research was as follow (simplified):

bool custom_cmp(const char l, const char r) {
        std::cout << "DEBUG print: " << l << " " << r << std::endl;

        return l < 'a' || l == r;
}

void foo() {
  std::string str1 = "A VERY LONG STRING IS HERE";
  std::string str2 = "short string";
  const char* iter1_begin = str1.c_str();
  const char* iter1_end   = str1.c_str() + str1.size();
  const char* iter2_begin = str2.c_str();

  std::cout << (std::equal(iter1_begin, iter1_end, buf, custom_cmp)) << std::endl;
}

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 str1 was longer than str2, read out-of-bounds on iter2 could happen. Container sanitization would detect it.
I hope it shows when those annotations are applicable. Let me know if you want me to add a bunch of samples to the patch. I can add a bunch of failing unit tests with examples. Is it a good idea?

This implementation uses the same API as std::vector (function: __sanitizer_annotate_contiguous_container) and from high level is the same here and there.
Long std::basic_string is almost the same as std::vecotr, so logic is absolutely the same. The difference is support for short strings, but that logic is very similar as well.
Long string (with standard allocators) annotations work with old ASan API (does not require rG1c5ad6d2c01294a0decde43a88e9c27d7437d157, so long-only patch wouldn't create a problem for ChromeOS). Only short string annotations require new API rG1c5ad6d2c01294a0decde43a88e9c27d7437d157.
If you think it's a good idea, I can split this patch into two. One for long only, second enabling SSO annotations.

It is worth mentioning that the change, proposed by me here, has negligible impact on performance, because when binary is already compiled with ASan, every access to strings memory is instrumented either way. Code from that change is executed only when strings size is modified and it's proportional to the change. All functions are no-ops when compiled without ASan.

---

Examples are above, here I let myself to digress a little. One may argue that some out of bounds errors may be detected by ASan without those changes, and that's true. If out of bound reaches memory outside of allocated area, ASan detects the bug without those changes. In situations like that, those changes increase speed of detecting errors. Potentially significantly, but I will come back to it. It's also worth to remember that there are no poisoned areas between elements in arrays.

std::string s[1024];
// ^ There are NO redzones between elements.

And memory is not poisoned inside classes between variables (and at the beginning and the end):

class X {
std::string x;
// NO redzone
int a[3];
};

Therefore, not every access outside of objects memory is detected. (Eg. above, s[0] is short, without detecting an error, BO can write over rest of 1023 strings memory. Error will be detected when memory after s[1023] is reached.) With those changes OOB will be detected, unless size() == capacity() before OOB happenes (case when there is no allocated and not-in-use memory).

---

Because short strings are on stack, bugs affect not only heap. Bellow I show modified example from above, with standard comparator, which leaks stack memory (including canary). Assumptions:

• user fully controls s[0],
• user has access to result of std::equals,
• it's super simplified.

bool result = false;
char x = 0;
size_t n = 0;

void user_input(std::string &s) {
  // Simulation of user providing input
  n += 1;

  if(result) {
    x = 0;
    std::cout << "Leaked " << s.size() << " bytes, with " << n << " requests." << std::endl;
    std::cout << "Leak: " << s << std::endl << std::endl;
    s.push_back('\0');
  } else {
    if(!s.empty()) s.pop_back();
    x += 1;
    s.push_back(x);
  }
}

void leak_cannary() {
  std::string s[3];
  s[2] = "secret data";
  for(int i = 0; i < 'z' * 100; ++i) {
    result = std::equal(s[0].begin(), s[0].end(), s[1].data());
    // User has access to the result.
    user_input(s[0]);
  }
}

Example result is: Leaked 169 bytes, with 12062 requests.

Chance of finding that bug with simple (random) harness and today ASan is close to zero, but it can be easily exploited.

Here I won't fully offtop how off-by-one on a buffer just before string may leak stack as well (same off-by-two on string with Alternate String Layout). If someone is interested, I'm happy to talk about ways to exploit SSO (connected with some bugs) outside of that revision, I was looking at it to create a CTF challenge.

[AdvenamTacet]

This update should resolve the conflict, it applies changes on the newest commit.

[AdvenamTacet]

This update is strictly related to refactor, which happened on the main branch.
No real changes included, newest commit from main as base.

[AdvenamTacet]

This update turns off annotations for short strings.
It is a small change and I will create another revision simply turning on annotations for short strings.

I was thinkin a lot about it and I believe it's better to have one patch turning on annotations for long strings only (with the default allocator only) and a separate one, very simple, turning on annotations for short strings as well.
My reasoning:

• Long strings with default allocator works with old ASan API. (Main reason.)
• There is much smaller chance to see a similar carse to area allocators (something we should address) with only long strings.
• If someone reports a problem, it's very helpful to see which change exactly caused the problem.

[AdvenamTacet]

This update:

• fixes problem with tests after setting _LIBCPP_SHORT_STRING_ANNOTATIONS_ALLOWED,
• removes #if ... [code] #endif from the test.

This is a fix after the previous update.

Also, I created a revision to turn on short string annotations.
Check D147680 for details.

Now short strings are not poisoned at all with this revision.

[AdvenamTacet]

This update tries to fix the merge conflict.

[ldionne]

libcxx/include/__string/extern_template_lists.h

30

I believe this means that -fsanitize=address would have to cause a different libc++.dylib to be linked. So for example, the driver would add e.g. -l c++asan instead of -l c++, and we would have to produce libc++asan.dylib in addition to libc++.dylib. That's not a small change though, since it seems like this might be the first time a sanitizer has an effect on the version of libc++ we have to link against. But it might be the right way to go (probably the only way to go, really). In practice, disabling extern templates like this is only going to give users the impression that things work and then they will run into issues.

CC @vitalybuka

libcxx/include/string

1847

Would __annotate_short_string_check be better called something like __short_string_is_annotated()?

2406

Isn't that a pre-existing problem that should be fixed in its own patch?

2524

I feel like this function would be a lot simpler if we instead called __annotate_contiguous_container directly, no?

2615

This whole set of changes feels kind of clunky. Why don't we annotate delete and then annotate new instead? Wouldn't that get rid of the special this check?

[ldionne]

Thanks a lot for the write up, I think this makes sense. I still find this more intrusive than I'd like, but let's see how we can improve this in a few places.

[AdvenamTacet]

libcxx/include/string

2406

I created a separate revision with that change: D148693
I will remove it from this patch in the next update.

[AdvenamTacet]

This update:

• changes name of __annotate_short_string_check function to __asan_short_string_is_annotated,
• removes the fix moved to D148693 revision,
• simplifies a function entioned in a code review,
• fixes use of & instead of std::addressof in libcxx/test/support/asan_testing.h.

Thank you for looking at it!

[AdvenamTacet]

libcxx/include/string

1847

I changed it to __asan_short_string_is_annotated, but I don't fully like those names. I added asan so it is clear what kind of annotations are [not] there.

2524

I do not think so, and I don't like the idea of calling __annotate_contiguous_container directly, but I did improve the function a lot. Hope it's ok now.

2615

No, it wouldn't. Here we are working on __str and not *this. We cannot __annotate_delete __str, if it's long because we would have to annotate whole string every time (big performance hit and stil check).

We also shouldn't call __annotate_delete on *this and __str if those are the same objects.

So, the check would be just earlier. Or maybe I don't see something here?

[AdvenamTacet]

libcxx/include/__string/extern_template_lists.h

30

@vitalybuka do you have any suggestion how to implement it?

Btw. a separate dylib may help with issue described here: https://github.com/llvm/llvm-project/issues/62431 (not sure, tho).

[AdvenamTacet]

This update:

• fixes annotations after changes in D148693,
• does rebase.

Now the revision is working, the only missing element is a separate dylib for ASan.

[AdvenamTacet]

libcxx/include/__string/extern_template_lists.h

30

Hey @ldionne,
could you tell me where I should look to modify it? I don't really know how to start working on that change and I believe, it's the only missing part after landing D148693. I would appreciate letting me know at what files I should look first.

Btw. it won't affect the issue mentioned above.

[ldionne]

libcxx/include/__string/extern_template_lists.h

30

I think we would want to start with a RFC on Discourse. This would be the first time that we introduce another shared library for libc++ and there are a few things to coordinate:

1. We need to build this new version of the library (do we do that with multiple CMake invocations or do we do like compiler-rt and allow building multiple libraries from a single invocation?)
2. We need to ship this library as part of the LLVM release and vendors need to also start shipping it with their own releases if they want -fsanitize=address to work
3. Do we need to also provide a -fsanitize=address version of other components in the LLVM stack? For example, if we ship another library that uses libc++ and we want it to work with -fsanitize=address, we would likely need to provide a sanitized version of it or else if e.g. a std::string is created inside that component and passed to another component that was compiled with -fsanitize=address, then you'd get a mismatch.

So this is unfortunately kind of involved, but I think knowing how to do this would benefit us since we have similar needs for other efforts. For example, it would be conceivable to ship an unstable-ABI version of the library, and a hardened version as well, and doing that would follow the exact same steps.

[vitalybuka]

libcxx/include/__string/extern_template_lists.h

30

I believe this means that -fsanitize=address would have to cause a different libc++.dylib to be linked. So for example, the driver would add e.g. -l c++asan instead of -l c++, and we would have to produce libc++asan.dylib in addition to libc++.dylib. That's not a small change though, since it seems like this might be the first time a sanitizer has an effect on the version of libc++ we have to link against. But it might be the right way to go (probably the only way to go, really). In practice, disabling extern templates like this is only going to give users the impression that things work and then they will run into issues.

For msan, tsan, instrumented libc++ was requirement all the time.
For asan, hwasan it's highly recommended.

For all use-case I work, we do that on build system level.
Our sanitizer*bootstrap build bots do that as well.

It would be nice if libc++ is shipped with each version. Sometimes additional flags may affect behavior of sanitizer, but even version instrumented with default flags will be useful.

CC @vitalybuka

@vitalybuka do you have any suggestion how to implement it?

I don't have specific thoughts on how to implemented.
I guess libc++ could install all sanitized versions with some prefixes: asan/msan/tsan/hwasan
Then the driver will pick one to link.

Btw. a separate dylib may help with issue described here: https://github.com/llvm/llvm-project/issues/62431 (not sure, tho).

30

I believe this means that -fsanitize=address would have to cause a different libc++.dylib to be linked. So for example, the driver would add e.g. -l c++asan instead of -l c++, and we would have to produce libc++asan.dylib in addition to libc++.dylib. That's not a small change though, since it seems like this might be the first time a sanitizer has an effect on the version of libc++ we have to link against. But it might be the right way to go (probably the only way to go, really). In practice, disabling extern templates like this is only going to give users the impression that things work and then they will run into issues.

CC @vitalybuka

30

I think we would want to start with a RFC on Discourse. This would be the first time that we introduce another shared library for libc++ and there are a few things to coordinate:

1. We need to build this new version of the library (do we do that with multiple CMake invocations or do we do like compiler-rt and allow building multiple libraries from a single invocation?)

Single invocation would be nice, as it's better scale on other sanitizers.

2. We need to ship this library as part of the LLVM release and vendors need to also start shipping it with their own releases if they want -fsanitize=address to work

please include msan/hwasan/tsan versions into the plan

lsan/ubsan do not needed special libc++.
dfsan is close to msan, but it's very specific tool, so we can skip for now.

[AdvenamTacet]

libcxx/include/__string/extern_template_lists.h

30

Created a RFC: https://discourse.llvm.org/t/rfc-instrumented-versions-of-libc-for-different-sanitizers/71653

Who can I/should I ping there? Who can I ping from vendors?

[AdvenamTacet]

libcxx/include/string

3159

The issue described above is addressed in D148693 and solved by rG6a9c41fdd4ca834a46fd866278c90a35f2375333. This revision has to be updated. Now the size is correct after __grow_by_without_replace.