[3/3][ASan] integration test for std::deque and std::basic_string annotations

[AdvenamTacet]

Summary

This commit is a part 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).

Trail of Bits developed this as part of a research project where
we tried to find bugs using the oss-fuzz (using llvm-14 with our
modifications) harnesses. Now, we want to upstream the llvm-16
port of this work.

One integration test for std::deque and std::basic_string,
which checks whether a std::basic_string can be stored
in a std::deque collection with annotation.

That test requires both std::basic_string and
std::deque annotations.

Structure of our patches:
[1a/3][ASan][compiler-rt] API for double ended containers
[1b/3][ASan][compiler-rt] API for annotating objects memory
[2a/3][ASan][libcxx] std::deque annotations
[2b/3][ASan][libcxx] std::basic_string annotations
[3/3][ASan] integration test for std::deque and std::basic_string annotations

1a -> 2a -

\
 --> 3
/

1b -> 2b -

If you have any questions, please email:

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

libcxx/test/std/containers/sequences/deque/deque.asan/string-integration.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <deque>
+
+#include <cassert>
+#include <array>
+#include "test_macros.h"
+#include "asan_testing.h" // includes deque and string - don't do it before
+
+// This tests exists to check if strings work well with deque, as those
+// may be partialy annotated, we cannot simply call
+// is_contiguous_container_asan_correct with deque, as it assumes that
+// object memory inside is not annotated, so we check everything in a more careful way.
+
+template <typename D>
+bool verify_inside(D const& d) {
+  for (size_t i = 0; i < d.size(); ++i) {
+    if (!is_string_asan_correct(d[i]))
+      return false;
+  }
+
+  return true;
+}
+
+template <typename T, size_t N>
+T get_s(char c) {
+  T s;
+  for (size_t i = 0; i < N; ++i)
+    s.push_back(c);
+
+  return s;
+}
+
+template <typename T>
+void test() {
+  typedef std::deque<T> D;
+  size_t const N = sizeof(T) < 256 ? (4096 / sizeof(T)) : 16;
+
+  {
+    D d1a(1), d1b(N), d1c(N + 1), d1d(32 * N);
+    assert(verify_inside(d1a));
+    assert(verify_inside(d1b));
+    assert(verify_inside(d1c));
+    assert(verify_inside(d1d));
+  }
+  {
+    D d2;
+    for (size_t i = 0; i < 16 * N; ++i) {
+      d2.push_back(get_s<T, 1>(i % 10 + 'a'));
+      assert(verify_inside(d2));
+      d2.push_back(get_s<T, 222>(i % 10 + 'b'));
+      assert(verify_inside(d2));
+
+      d2.pop_front();
+      assert(verify_inside(d2));
+    }
+  }
+  {
+    D d3;
+    for (size_t i = 0; i < 16 * N; ++i) {
+      d3.push_front(get_s<T, 1>(i % 10 + 'a'));
+      assert(verify_inside(d3));
+      d3.push_front(get_s<T, 222>(i % 10 + 'b'));
+      assert(verify_inside(d3));
+
+      d3.pop_back();
+      assert(verify_inside(d3));
+    }
+  }
+  {
+    D d4;
+    for (size_t i = 0; i < 16 * N; ++i) {
+      // When there is no SSO, all elements inside should not be poisoned,
+      // so we can verify deque poisoning.
+      d4.push_front(get_s<T, 333>(i % 10 + 'a'));
+      assert(verify_inside(d4));
+      assert(is_contiguous_container_asan_correct(d4));
+      d4.push_back(get_s<T, 222>(i % 10 + 'b'));
+      assert(verify_inside(d4));
+      assert(is_contiguous_container_asan_correct(d4));
+    }
+  }
+  {
+    D d5;
+    for (size_t i = 0; i < 5 * N; ++i) {
+      // In d4 we never had poisoned memory inside deque.
+      // Here we start with SSO, so part of the inside of the container,
+      // will be poisoned.
+      d5.push_front(T());
+      assert(verify_inside(d5));
+    }
+    for (size_t i = 0; i < d5.size(); ++i) {
+      // We change the size to have long string.
+      // Memory owne by deque should not be poisoned by string.
+      d5[i].resize(1000);
+      assert(verify_inside(d5));
+    }
+
+    assert(is_contiguous_container_asan_correct(d5));
+
+    d5.erase(d5.begin() + 2);
+    assert(verify_inside(d5));
+
+    d5.erase(d5.end() - 2);
+    assert(verify_inside(d5));
+
+    assert(is_contiguous_container_asan_correct(d5));
+  }
+  {
+    D d6a;
+    assert(is_contiguous_container_asan_correct(d6a));
+
+    D d6b(N + 2, get_s<T, 1000>('a'));
+    d6b.push_front(get_s<T, 1001>('b'));
+    while (!d6b.empty()) {
+      d6b.pop_back();
+      assert(is_contiguous_container_asan_correct(d6b));
+    }
+
+    D d6c(N + 2, get_s<T, 1002>('c'));
+    while (!d6c.empty()) {
+      d6c.pop_back();
+      assert(is_contiguous_container_asan_correct(d6c));
+    }
+  }
+  {
+    D d7(9 * N + 2);
+
+    d7.insert(d7.begin() + 1, T());
+    assert(verify_inside(d7));
+
+    d7.insert(d7.end() - 3, T());
+    assert(verify_inside(d7));
+
+    d7.insert(d7.begin() + 2 * N, get_s<T, 1>('a'));
+    assert(verify_inside(d7));
+
+    d7.insert(d7.end() - 2 * N, get_s<T, 1>('b'));
+    assert(verify_inside(d7));
+
+    d7.insert(d7.begin() + 2 * N, 3 * N, get_s<T, 1>('c'));
+    assert(verify_inside(d7));
+
+    // It may not be short for big element types, but it will be checked correctly:
+    d7.insert(d7.end() - 2 * N, 3 * N, get_s<T, 2>('d'));
+    assert(verify_inside(d7));
+
+    d7.erase(d7.begin() + 2);
+    assert(verify_inside(d7));
+
+    d7.erase(d7.end() - 2);
+    assert(verify_inside(d7));
+  }
+}
+
+int main(int, char**) {
+  // Those tests supports only types based on std::basic_string.
+
+  {
+    typedef std::string T;
+    test<T>();
+  }
+  {
+    typedef std::wstring T;
+    test<T>();
+  }
+#if TEST_STD_VER >= 11
+  {
+    typedef std::u16string T;
+    test<T>();
+  }
+  {
+    typedef std::u32string T;
+    test<T>();
+  }
+#endif
+#if TEST_STD_VER >= 20
+  {
+    typedef std::u8string T;
+    test<T>();
+  }
+#endif
+  return 0;
+}