Bug #4979
closed
Integer overflow in pit::FaceRecord::update
100%
Description
This addition may overflow if the Interest lifetime is very large. This is undefined behavior because the two values are signed integers. The overflow may not cause a crash immediately but it will likely trigger an assertion later in Forwarder::setExpiryTimer() because duration is negative.
This bug was found by NFDFuzz, an experimental fuzzer for NFD and ndn-cxx.
Stack trace of the failed assertion:
#0 0x60b217 in __sanitizer_print_stack_trace /tmp/final/llvm.src/projects/compiler-rt/lib/asan/asan_stack.cc:38:3
#1 0x549066 in fuzzer::Fuzzer::CrashCallback() /tmp/final/llvm.src/projects/compiler-rt/lib/fuzzer/FuzzerLoop.cpp:233:5
#2 0x54902f in fuzzer::Fuzzer::StaticCrashSignalCallback() /tmp/final/llvm.src/projects/compiler-rt/lib/fuzzer/FuzzerLoop.cpp:206:6
#3 0x7f711056b38f (/lib/x86_64-linux-gnu/libpthread.so.0+0x1138f)
#4 0x7f710f860427 in gsignal (/lib/x86_64-linux-gnu/libc.so.6+0x35427)
#5 0x7f710f862029 in abort (/lib/x86_64-linux-gnu/libc.so.6+0x37029)
#6 0x7f710f858bd6 (/lib/x86_64-linux-gnu/libc.so.6+0x2dbd6)
#7 0x7f710f858c81 in __assert_fail (/lib/x86_64-linux-gnu/libc.so.6+0x2dc81)
#8 0xa83341 in nfd::Forwarder::setExpiryTimer(std::shared_ptr<nfd::pit::Entry> const&, boost::chrono::duration<long, boost::ratio<1l, 1000l> >) /users/gjt3/NFD/build/../daemon/fw/forwarder.cpp:514:3
#9 0xa82423 in nfd::Forwarder::onContentStoreMiss(nfd::FaceEndpoint const&, std::shared_ptr<nfd::pit::Entry> const&, ndn::Interest const&) /users/gjt3/NFD/build/../daemon/fw/forwarder.cpp:184:9
#10 0xab4fa7 in void std::_Bind<std::_Mem_fn<void (nfd::Forwarder::*)(nfd::FaceEndpoint const&, std::shared_ptr<nfd::pit::Entry> const&, ndn::Interest const&)> (nfd::Forwarder*, nfd::FaceEndpoint, std::shared_ptr<nfd::pit::Entry>, std::_Placeholder<1>)>::__call<void, ndn::Interest const&, 0ul, 1ul, 2ul, 3ul>(std::tuple<ndn::Interest const&>&&, std::_Index_tuple<0ul, 1ul, 2ul, 3ul>) /usr/lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/c++/5.4.0/functional:1073:11
#11 0xab4b1b in void std::_Bind<std::_Mem_fn<void (nfd::Forwarder::*)(nfd::FaceEndpoint const&, std::shared_ptr<nfd::pit::Entry> const&, ndn::Interest const&)> (nfd::Forwarder*, nfd::FaceEndpoint, std::shared_ptr<nfd::pit::Entry>, std::_Placeholder<1>)>::operator()<ndn::Interest const&, void>(ndn::Interest const&) /usr/lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/c++/5.4.0/functional:1131:17
#12 0xaa766c in void nfd::cs::Cs::find<std::_Bind<std::_Mem_fn<void (nfd::Forwarder::*)(nfd::FaceEndpoint const&, std::shared_ptr<nfd::pit::Entry> const&, ndn::Interest const&, ndn::Data const&)> (nfd::Forwarder*, nfd::FaceEndpoint, std::shared_ptr<nfd::pit::Entry>, std::_Placeholder<1>, std::_Placeholder<2>)>, std::_Bind<std::_Mem_fn<void (nfd::Forwarder::*)(nfd::FaceEndpoint const&, std::shared_ptr<nfd::pit::Entry> const&, ndn::Interest const&)> (nfd::Forwarder*, nfd::FaceEndpoint, std::shared_ptr<nfd::pit::Entry>, std::_Placeholder<1>)> >(ndn::Interest const&, std::_Bind<std::_Mem_fn<void (nfd::Forwarder::*)(nfd::FaceEndpoint const&, std::shared_ptr<nfd::pit::Entry> const&, ndn::Interest const&, ndn::Data const&)> (nfd::Forwarder*, nfd::FaceEndpoint, std::shared_ptr<nfd::pit::Entry>, std::_Placeholder<1>, std::_Placeholder<2>)>&&, std::_Bind<std::_Mem_fn<void (nfd::Forwarder::*)(nfd::FaceEndpoint const&, std::shared_ptr<nfd::pit::Entry> const&, ndn::Interest const&)> (nfd::Forwarder*, nfd::FaceEndpoint, std::shared_ptr<nfd::pit::Entry>, std::_Placeholder<1>)>&&) const /users/gjt3/NFD/build/../daemon/table/cs.hpp:85:7
#13 0xa80446 in nfd::Forwarder::onIncomingInterest(nfd::FaceEndpoint const&, ndn::Interest const&) /users/gjt3/NFD/build/../daemon/fw/forwarder.cpp:134:10
#14 0xa8e50b in nfd::Forwarder::Forwarder()::$_2::operator()(nfd::face::Face&) const::{lambda(ndn::Interest const&, unsigned long const&)#1}::operator()(ndn::Interest const&, unsigned long const&) const /users/gjt3/NFD/build/../daemon/fw/forwarder.cpp:57:15
#15 0x7af635 in ndn::util::signal::Signal<nfd::face::LinkService, ndn::Interest, unsigned long>::operator()(ndn::Interest const&, unsigned long const&) /usr/local/include/ndn-cxx/util/signal/signal.hpp:232:7
#16 0x7a62af in nfd::face::LinkService::receiveInterest(ndn::Interest const&, unsigned long const&) /users/gjt3/NFD/build/../daemon/face/link-service.cpp:94:3
#17 0x73a275 in nfd::face::GenericLinkService::decodeInterest(ndn::Block const&, ndn::lp::Packet const&, unsigned long const&) /users/gjt3/NFD/build/../daemon/face/generic-link-service.cpp:391:9
#18 0x73662c in nfd::face::GenericLinkService::decodeNetPacket(ndn::Block const&, ndn::lp::Packet const&, unsigned long const&) /users/gjt3/NFD/build/../daemon/face/generic-link-service.cpp:324:17
#19 0x734f6a in nfd::face::GenericLinkService::doReceivePacket(ndn::Block const&, unsigned long const&) /users/gjt3/NFD/build/../daemon/face/generic-link-service.cpp:304:13
#20 0x104330b in nfd::face::StreamTransport<boost::asio::local::stream_protocol>::handleReceive(boost::system::error_code const&, unsigned long) /users/gjt3/NFD/build/../daemon/face/stream-transport.hpp:258:11
#21 0x10428b8 in _ZN5boost4asio6detail23reactive_socket_recv_opINS0_17mutable_buffers_1EZN3nfd4face15StreamTransportINS0_5local15stream_protocolEE12startReceiveEvEUlDpOT_E_E11do_completeEPNS1_15task_io_serviceEPNS1_25task_io_service_operationERKNS_6system10error_codeEm /usr/include/boost/asio/detail/reactive_socket_recv_op.hpp:110:7
#22 0x67e0ed in boost::asio::detail::epoll_reactor::descriptor_state::do_complete(boost::asio::detail::task_io_service*, boost::asio::detail::task_io_service_operation*, boost::system::error_code const&, unsigned long) /usr/include/boost/asio/detail/impl/epoll_reactor.ipp:651:11
#23 0x6917ba in boost::asio::detail::task_io_service::do_run_one(boost::asio::detail::scoped_lock<boost::asio::detail::posix_mutex>&, boost::asio::detail::task_io_service_thread_info&, boost::system::error_code const&) /usr/include/boost/asio/detail/impl/task_io_service.ipp:372:12
#24 0x690acf in boost::asio::detail::task_io_service::run(boost::system::error_code&) /usr/include/boost/asio/detail/impl/task_io_service.ipp:149:10
#25 0x68cd2d in boost::asio::io_service::run() /usr/include/boost/asio/impl/io_service.ipp:59:25
#26 0x66987d in nfd::NfdRunner::run() /users/gjt3/NFD/build/../daemon/fuzzer.cpp:157:15
#27 0x64e8aa in LLVMFuzzerTestOneInput /users/gjt3/NFD/build/../daemon/fuzzer.cpp:309:17
#28 0x54a2bc in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, unsigned long) /tmp/final/llvm.src/projects/compiler-rt/lib/fuzzer/FuzzerLoop.cpp:515:13
#29 0x549b1b in fuzzer::Fuzzer::RunOne(unsigned char const*, unsigned long, bool, fuzzer::InputInfo*, bool*) /tmp/final/llvm.src/projects/compiler-rt/lib/fuzzer/FuzzerLoop.cpp:440:3
#30 0x54b54d in fuzzer::Fuzzer::MutateAndTestOne() /tmp/final/llvm.src/projects/compiler-rt/lib/fuzzer/FuzzerLoop.cpp:648:19
#31 0x54be05 in fuzzer::Fuzzer::Loop(std::vector<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, fuzzer::fuzzer_allocator<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > > const&) /tmp/final/llvm.src/projects/compiler-rt/lib/fuzzer/FuzzerLoop.cpp:775:5
#32 0x540b00 in fuzzer::FuzzerDriver(int*, char***, int (*)(unsigned char const*, unsigned long)) /tmp/final/llvm.src/projects/compiler-rt/lib/fuzzer/FuzzerDriver.cpp:754:6
#33 0x562722 in main /tmp/final/llvm.src/projects/compiler-rt/lib/fuzzer/FuzzerMain.cpp:20:10
#34 0x7f710f84b82f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
#35 0x539b88 in _start (/users/gjt3/NFD/build/daemon/fuzzer+0x539b88)
Files
Updated by Junxiao Shi almost 4 years ago
- Status changed from New to In Progress
- Assignee set to Junxiao Shi
- Target version set to 22.02
- Estimated time set to 2.00 h
Updated by Junxiao Shi almost 4 years ago
- % Done changed from 0 to 30
https://gerrit.named-data.net/c/NFD/+/6157
patchset 1 expands the Table/TestPitEntry/Lifetime test case to reproduce the bug.
In FaceRecord::update function, the obvious fix is to impose a maximum limit of InterestLifetime, so that signed integer overflow is unlikely to occur.
However, I believe this cannot adequately solve the problem.
An incoming Interest could carry a very small InterestLifetime.
If the time elapsed between inserting PIT in-record and invoking Forwarder::setExpiryTimer exceeds the InterestLifetime, the assertion would fail.
Given both occurs in the same function Forwarder::onContentStoreMiss, this would only occur if InterestLifetime is zero.
I think the solution is to ban InterestLifetime=0ms from the encoding layer, since it does not make sense in a distributed network.
Updated by Alex Afanasyev almost 4 years ago
Junxiao, I am not following the logic / which assertion would fail. InterestLifetime is relative time and we use setExpiryTimer(0_s,...) all over the place. So, where is the issue?
I would agree that having a too-small interest lifetime is wrong, but I don't quite know what kind of minimum limit we could set.
Updated by Junxiao Shi almost 4 years ago
setExpiryTimer(0_s,...) is fine, but InterestLifetime=0 is unsafe.
In Forwarder::onContentStoreMiss function:
At timestamp T+0ms, this line executes:
https://gerrit.named-data.net/plugins/gitiles/NFD/+/c78226c4612dceea39b3f1d101dea0cb47168630/daemon/fw/forwarder.cpp#189
It sets inRecord.expiry to T+0ns.
It's only a few lines of code, but it would take non-zero time. On a slow machine with other process running, this could take 1ms.
At timestamp T+1ms, this line executes:
https://gerrit.named-data.net/plugins/gitiles/NFD/+/c78226c4612dceea39b3f1d101dea0cb47168630/daemon/fw/forwarder.cpp#196
It computes the remaining lifetime to be T+0ms - T+1ms = -1ms.
Then it calls Forwarder::setExpiryTimer(pitEntry, -1_ms) that triggers a crash.
Whenever InterestLifetime is zero, lastExpiring->getExpiry() - time::steady_clock::now() would be negative.
The only reason we haven't seen a crash in the wild is that, the duration unit in Forwarder::setExpiryTimer is milliseconds, so that any negative value above -1ms is truncated to 0ms.
However, this is still a logical error.
Updated by Davide Pesavento almost 4 years ago
Junxiao, you're mixing two different bugs. One is the signed addition overflow (undefined behavior) found by the fuzzer. The other one is the "residual" duration becoming negative if the InterestLifetime was very small. The former has nothing to do with the assertion per se, the bug is in the addition itself.
What's the reason for the assertion in setExpiryTimer anyway? Why can't we use std::max(0_ms, duration) instead?
Updated by Junxiao Shi almost 4 years ago
One is the signed addition overflow (undefined behavior) found by the fuzzer. The other one is the "residual" duration becoming negative if the InterestLifetime was very small.
I know the distinction, but both causes will trigger the assertion failure.
What's the reason for the assertion in
setExpiryTimeranyway? Why can't we usestd::max(0_ms, duration)instead?
Agreed. I'll change accordingly.
Updated by Davide Pesavento almost 4 years ago
Junxiao Shi wrote in #note-7:
One is the signed addition overflow (undefined behavior) found by the fuzzer. The other one is the "residual" duration becoming negative if the InterestLifetime was very small.
I know the distinction, but both causes will trigger the assertion failure.
Yes, my point was that removing the assertion will not fix the first bug.
Updated by Junxiao Shi almost 4 years ago
- Status changed from In Progress to Closed
- % Done changed from 30 to 100