Heap Buffer Overflow when installing many table entries

[matthewtlam]

After running the ASAN (Address Sanitizer) tool on our tests with a simple grpc service that installs many table entries, I noticed that it resulted in a heap_buffer_overflow error.

The ASAN tool detects out-of-bound accesses to heap, stack and globals; use after free and use after return errors. Usually ASAN errors indicate some type of double free or accessing an uninitialized variable (garbage).

This is where ASAN is complaining about it.

unsigned key = (unsigned) (unsigned char) *prefix >> (8 - prefix_length);

insert_prefix(current_node, (uint8_t) prefix_length, key, value); // <------------- ASAN complains about this line.

Here is a mostly complete ASAN report but omits redundant info with the "...".

=================================================================
==4595==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x504000276f74 at pc 0x55d2364c6514 bp 0x7f6a89c79dd0 sp 0x7f6a89c79dc8
READ of size 1 at 0x504000276f74 thread T34 (grpcpp_sync_ser)
    #0 0x55d2364c6513 in bf_lpm_trie_insert [third_party/p4lang_behavioral_model/src/bf_lpm_trie/bf_lpm_trie.c:293]:45
    #1 0x55d236406901 in insert_prefix [third_party/p4lang_behavioral_model/src/bm_sim/lpm_trie.h:64]:5
    #2 0x55d236406901 in bm::(anonymous namespace)::LPMTrieStructure::add_entry(bm::LPMMatchKey const&, unsigned long) [third_party/p4lang_behavioral_model/src/bm_sim/lookup_structures.cpp:83]:10
    #3 0x55d236414e13 in bm::MatchUnitGeneric<bm::LPMMatchKey, bm::ActionEntry>::add_entry_(std::__u::vector<bm::MatchKeyParam, std::__u::allocator<bm::MatchKeyParam>> const&, bm::ActionEntry, unsigned int*, int) [third_party/p4lang_behavioral_model/src/bm_sim/match_units.cpp:978]:21
    #4 0x55d23640c929 in bm::MatchUnitAbstract<bm::ActionEntry>::add_entry(std::__u::vector<bm::MatchKeyParam, std::__u::allocator<bm::MatchKeyParam>> const&, bm::ActionEntry, unsigned int*, int) [third_party/p4lang_behavioral_model/src/bm_sim/match_units.cpp:809]:23
    #5 0x55d2363ebdbf in bm::MatchTable::add_entry(std::__u::vector<bm::MatchKeyParam, std::__u::allocator<bm::MatchKeyParam>> const&, bm::ActionFn const*, bm::ActionData, unsigned int*, int) [third_party/p4lang_behavioral_model/src/bm_sim/match_tables.cpp:399]:22
    #6 0x55d23637b99d in bm::Context::mt_add_entry(std::__u::basic_string<char, std::__u::char_traits<char>, std::__u::allocator<char>> const&, std::__u::vector<bm::MatchKeyParam, std::__u::allocator<bm::MatchKeyParam>> const&, std::__u::basic_string<char, std::__u::char_traits<char>, std::__u::allocator<char>> const&, bm::ActionData, unsigned int*, int) [third_party/p4lang_behavioral_model/src/bm_sim/context.cpp:73]:17
    #7 0x55d2361b3f95 in bm::SwitchWContexts::mt_add_entry(unsigned int, std::__u::basic_string<char, std::__u::char_traits<char>, std::__u::allocator<char>> const&, std::__u::vector<bm::MatchKeyParam, std::__u::allocator<bm::MatchKeyParam>> const&, std::__u::basic_string<char, std::__u::char_traits<char>, std::__u::allocator<char>> const&, bm::ActionData, unsigned int*, int) [third_party/p4lang_behavioral_model/include/bm/bm_sim/switch.h:346](:32
    #8 0x55d2362c02d8 in add_entry [third_party/p4lang_behavioral_model/PI/src/pi_tables_imp.cpp:189]:38
    #9 0x55d2362c02d8 in _pi_table_entry_add [third_party/p4lang_behavioral_model/PI/src/pi_tables_imp.cpp:793]:25
    #10 0x55d2362ac11e in pi_table_entry_add [third_party/p4lang_PI/src/pi_tables.c:110]:10
    #11 0x55d2362a8c0d in pi::MatchTable::entry_add(pi::MatchKey const&, pi::ActionEntry const&, bool, unsigned long*) [third_party/p4lang_PI/frontends_extra/cpp/src/tables.cpp:700]:10
    #12 0x55d2362414eb in pi::fe::proto::DeviceMgrImp::table_insert(p4::v1::TableEntry const&, pi::fe::proto::common::SessionTemp*) [third_party/p4lang_PI/proto/frontend/src/device_mgr.cpp:2700]:25
    #13 0x55d23623e56e in pi::fe::proto::DeviceMgrImp::table_write(p4::v1::Update_Type, p4::v1::TableEntry const&, pi::fe::proto::common::SessionTemp*) [third_party/p4lang_PI/proto/frontend/src/device_mgr.cpp:691]:16
    #14 0x55d236203e47 in pi::fe::proto::DeviceMgrImp::write_(p4::v1::WriteRequest const&) [third_party/p4lang_PI/proto/frontend/src/device_mgr.cpp:2104]:20
    #15 0x55d2361ff9e3 in pi::fe::proto::DeviceMgrImp::write(p4::v1::WriteRequest const&) [third_party/p4lang_PI/proto/frontend/src/device_mgr.cpp:660]:12
    #16 0x55d2361ff881 in pi::fe::proto::DeviceMgr::write(p4::v1::WriteRequest const&) [third_party/p4lang_PI/proto/frontend/src/device_mgr.cpp:3132]:16
    #17 0x55d2361f4250 in pi::server::(anonymous namespace)::P4RuntimeServiceImpl::Write(grpc::ServerContext*, p4::v1::WriteRequest const*, p4::v1::WriteResponse*) [third_party/p4lang_PI/proto/server/pi_server.cpp:425]:31
    #18 0x55d236575299 in grpc::Status std::__u::__function::__policy_invoker<grpc::Status (p4::v1::grpc::P4Runtime::Service*, grpc::ServerContext*, p4::v1::WriteRequest const*,):16
... 
    #40 0x55d236144530 in asan_thread_start(void*) [third_party/llvm/llvm-project/compiler-rt/lib/asan/asan_interceptors.cpp:239]:28
    #41 0x7f6aaa27d7d8 in start_thread (/usr/grte/v5/lib64/libpthread.so.0+0xb7d8) (BuildId: 3ccc1600b9140e48da03ed16e0210354)

0x504000276f74 is located 0 bytes after 36-byte region [0x504000276f50,0x504000276f74)
allocated by thread T34 (grpcpp_sync_ser) here:
    #0 0x55d23617dafd in operator new(unsigned long) [third_party/llvm/llvm-project/compiler-rt/lib/asan/asan_new_delete.cpp:86]:3
    #1 0x55d23631ac16 in allocate<1UL> [third_party/p4lang_behavioral_model/include/bm/bm_sim/short_alloc.h:87]:31
    #2 0x55d23631ac16 in allocate [third_party/p4lang_behavioral_model/include/bm/bm_sim/short_alloc.h:134]:49
    #3 0x55d23631ac16 in __allocate_at_least<detail::short_alloc<char, 16UL, 1UL> > [third_party/crosstool/v18/stable/toolchain/bin/../include/c++/v1/__memory/allocate_at_least.h:41]:19
    #4 0x55d23631ac16 in std::__u::vector<char, detail::short_alloc<char, 16ul, 1ul>>::__vallocate(unsigned long) [third_party/crosstool/v18/stable/toolchain/bin/../include/c++/v1/vector:743]:25
    #5 0x55d2363b97a9 in void std::__u::vector<char, detail::short_alloc<char, 16ul, 1ul>>::__assign_with_size<std::__u::__wrap_iter<char const*>, std::__u::__wrap_iter<char const*>>(std::__u::__wrap_iter<char const*>, std::__u::__wrap_iter<char const*>, long) [third_party/crosstool/v18/stable/toolchain/bin/../include/c++/v1/vector:1356]:5
    #6 0x55d236414cae in assign<std::__u::__wrap_iter<const char *>, 0> [third_party/crosstool/v18/stable/toolchain/bin/../include/c++/v1/vector:1337]:3
    #7 0x55d236414cae in operator= [third_party/p4lang_behavioral_model/include/bm/bm_sim/bytecontainer.h:112]:11
    #8 0x55d236414cae in operator= [third_party/p4lang_behavioral_model/include/bm/bm_sim/match_key_types.h:40]:8
    #9 0x55d236414cae in operator= [third_party/p4lang_behavioral_model/include/bm/bm_sim/match_key_types.h:57]:8
    #10 0x55d236414cae in operator= [third_party/p4lang_behavioral_model/include/bm/bm_sim/match_units.h:453]:10
    #11 0x55d236414cae in bm::MatchUnitGeneric<bm::LPMMatchKey, bm::ActionEntry>::add_entry_(std::__u::vector<bm::MatchKeyParam, std::__u::allocator<bm::MatchKeyParam>> const&, bm::ActionEntry, unsigned int*, int) [third_party/p4lang_behavioral_model/src/bm_sim/match_units.cpp:972]:20
    #12 0x55d23640c929 in bm::MatchUnitAbstract<bm::ActionEntry>::add_entry(std::__u::vector<bm::MatchKeyParam, std::__u::allocator<bm::MatchKeyParam>> const&, bm::ActionEntry, unsigned int*, int) [third_party/p4lang_behavioral_model/src/bm_sim/match_units.cpp:809]:23
    #13 0x55d2363ebdbf in bm::MatchTable::add_entry(std::__u::vector<bm::MatchKeyParam, std::__u::allocator<bm::MatchKeyParam>> const&, bm::ActionFn const*, bm::ActionData, unsigned int*, int) [third_party/p4lang_behavioral_model/src/bm_sim/match_tables.cpp:399]:22
    #14 0x55d23637b99d in bm::Context::mt_add_entry(std::__u::basic_string<char, std::__u::char_traits<char>, std::__u::allocator<char>> const&, std::__u::vector<bm::MatchKeyParam, std::__u::allocator<bm::MatchKeyParam>> const&, std::__u::basic_string<char, std::__u::char_traits<char>, std::__u::allocator<char>> const&, bm::ActionData, unsigned int*, int) [third_party/p4lang_behavioral_model/src/bm_sim/context.cpp:73]:17
    #15 0x55d2361b3f95 in bm::SwitchWContexts::mt_add_entry(unsigned int, std::__u::basic_string<char, std::__u::char_traits<char>, std::__u::allocator<char>> const&, std::__u::vector<bm::MatchKeyParam, std::__u::allocator<bm::MatchKeyParam>> const&, std::__u::basic_string<char, std::__u::char_traits<char>, std::__u::allocator<char>> const&, bm::ActionData, unsigned int*, int) [third_party/p4lang_behavioral_model/include/bm/bm_sim/switch.h:346]:32
    #16 0x55d2362c02d8 in add_entry [third_party/p4lang_behavioral_model/PI/src/pi_tables_imp.cpp:189]:38
    #17 0x55d2362c02d8 in _pi_table_entry_add [third_party/p4lang_behavioral_model/PI/src/pi_tables_imp.cpp:793]:25
    #18 0x55d2362ac11e in pi_table_entry_add [third_party/p4lang_PI/src/pi_tables.c:110]:10
    #19 0x55d2362a8c0d in pi::MatchTable::entry_add(pi::MatchKey const&, pi::ActionEntry const&, bool, unsigned long*) [third_party/p4lang_PI/frontends_extra/cpp/src/tables.cpp:700]:10
    #20 0x55d2362414eb in pi::fe::proto::DeviceMgrImp::table_insert(p4::v1::TableEntry const&, pi::fe::proto::common::SessionTemp*) [third_party/p4lang_PI/proto/frontend/src/device_mgr.cpp:2700]:25
    #21 0x55d23623e56e in pi::fe::proto::DeviceMgrImp::table_write(p4::v1::Update_Type, p4::v1::TableEntry const&, pi::fe::proto::common::SessionTemp*) [third_party/p4lang_PI/proto/frontend/src/device_mgr.cpp:691]:16
    #22 0x55d236203e47 in pi::fe::proto::DeviceMgrImp::write_(p4::v1::WriteRequest const&) [third_party/p4lang_PI/proto/frontend/src/device_mgr.cpp:2104]:20
    #23 0x55d2361ff9e3 in pi::fe::proto::DeviceMgrImp::write(p4::v1::WriteRequest const&) [third_party/p4lang_PI/proto/frontend/src/device_mgr.cpp:660]:12
    #24 0x55d2361ff881 in pi::fe::proto::DeviceMgr::write(p4::v1::WriteRequest const&) [third_party/p4lang_PI/proto/frontend/src/device_mgr.cpp:3132]:16
    #25 0x55d2361f4250 in pi::server::(anonymous namespace)::P4RuntimeServiceImpl::Write(grpc::ServerContext*, p4::v1::WriteRequest const*, p4::v1::WriteResponse*) [third_party/p4lang_PI/proto/server/pi_server.cpp:425]:31
    #26 0x55d236575299 in grpc::Status std::__u::__function::__policy_invoker<grpc::Status (p4::v1::grpc::P4Runtime::Service*, grpc::ServerContext*, p4::v1::WriteRequest const*, 
...
    #48 0x55d236144530 in asan_thread_start(void*) [third_party/llvm/llvm-project/compiler-rt/lib/asan/asan_interceptors.cpp:239]:28

Thread T25 (grpcpp_sync_ser) created by T0 here:
    #0 0x55d23612c3e1 in pthread_create [third_party/llvm/llvm-project/compiler-rt/lib/asan/asan_interceptors.cpp:250]:3
    #1 0x55d239b0ca67 in Thread::CreatePthread(pthread_attr_t&) [thread/thread.cc:503]:13
    #2 0x55d239b0db77 in Thread::Start() [thread/thread.cc:679]:3
    #3 0x55d23981d303 in (anonymous namespace)::ThreadInternalsGoogleThread::Start() 
    #4 0x55d2375ce6cb in grpc_core::Thread::Start() [third_party/grpc/src/core/lib/gprpp/thd.h:153]:14
    #5 0x55d2375dd3ff in Start [third_party/grpc/src/cpp/thread_manager/thread_manager.h:124]:25
    #6 0x55d2375dd3ff in grpc::ThreadManager::Initialize() [third_party/grpc/src/cpp/thread_manager/thread_manager.cc:146]:13
    #7 0x55d2375bc70f in Start [third_party/grpc/src/cpp/server/server_cc.cc:876]:7
    #8 0x55d2375bc70f in grpc::Server::Start(grpc::ServerCompletionQueue**, unsigned long) [third_party/grpc/src/cpp/server/server_cc.cc:1232]:12
    #9 0x55d2375b3ae5 in grpc::ServerBuilder::BuildAndStart() [third_party/grpc/src/cpp/server/server_builder.cc:505]:11
    #10 0x55d2361f222b in PIGrpcServerRunV2 [third_party/p4lang_PI/proto/server/pi_server.cpp:699]:33
    #11 0x55d236186b49 in sswitch_grpc::SimpleSwitchGrpcRunner::init_and_start(bm::OptionsParser const&) [third_party/p4lang_behavioral_model/targets/simple_switch_grpc/switch_runner.cpp:644]:3
    #12 0x55d2361829f4 in main [third_party/p4lang_behavioral_model/targets/simple_switch_grpc/main.cpp:238]:23
    #13 0x7f6aaa100632 in __libc_start_main (/usr/grte/v5/lib64/libc.so.6+0x61632) (BuildId: 280088eab084c30a3992a9bce5c35b44)
    #14 0x55d2360a9729 in _start /[usr/grte/v5/debug-src/src/csu/../sysdeps/x86_64/start.S:120]

SUMMARY: AddressSanitizer: heap-buffer-overflow [third_party/p4lang_behavioral_model/src/bf_lpm_trie/bf_lpm_trie.c:293]:45 in bf_lpm_trie_insert
Shadow bytes around the buggy address:
  0x504000276c80: fa fa 00 00 00 00 00 fa fa fa 00 00 00 00 00 fa
  0x504000276d00: fa fa 00 00 00 00 00 00 fa fa fd fd fd fd fd fd
  0x504000276d80: fa fa fd fd fd fd fd fa fa fa fd fd fd fd fd fa
  0x504000276e00: fa fa 00 00 00 00 00 fa fa fa 00 00 00 00 00 fa
  0x504000276e80: fa fa fd fd fd fd fd fa fa fa fd fd fd fd fd fa
=>0x504000276f00: fa fa 00 00 00 00 04 fa fa fa 00 00 00 00[04]fa
  0x504000276f80: fa fa 00 00 00 00 00 00 fa fa 00 00 00 00 00 00
  0x504000277000: fa fa fd fd fd fd fd fa fa fa fd fd fd fd fd fa
  0x504000277080: fa fa fd fd fd fd fd fd fa fa fd fd fd fd fd fa
  0x504000277100: fa fa fd fd fd fd fd fa fa fa fd fd fd fd fd fa
  0x504000277180: fa fa fd fd fd fd fd fa fa fa fd fd fd fd fd fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==4595==ABORTING
I0517 04:14:48.383181    4665 p4_runtime_session.cc:382] P4RT stream is now inactive.
W0517 04:14:48.392832    4578 p4_runtime_session.cc:217] P4RuntimeSession did not close cleanly: UNAVAILABLE: Socket closed
=== Source Location Trace: ===

@smolkaj , @jonathan-dilorenzo for visibility.

[antoninbas]

I assume that the issue is somewhere in insert_prefix, but the code was inlined and we cannot pin point which line is problematic based on this.

The issue is likely to be here: https://github.com/p4lang/behavioral-model/blob/9979ce251df26e39734e5a225be7febdea36073c/src/bf_lpm_trie/bf_lpm_trie.c#L207-L210

I believe it is possible for a to be equal to prefixes->size - 1 at that point, which means the new element needs to be inserted at the very end of the array, but the array does not need to be grown. In this case, we try to move the contents of prefixes->prefixes[a] to prefixes->prefixes[a+1], which is outside of the allocated array, and that could be the issue. It may be that this calculation is off-by-one: size_t size = (prefixes->size - a) * sizeof(*prefixes->prefixes);

If someone fixes it, it would be great to add a unit test to https://github.com/p4lang/behavioral-model/blob/main/tests/test_tables.cpp which triggers this behavior.