Packet Loss Tracker - Stream Separation

webrtc/test/fuzzers/transport_feedback_packet_loss_tracker_fuzzer.cc

 /*
  *  Copyright (c) 2017 The WebRTC project authors. All Rights Reserved.
  *
  *  Use of this source code is governed by a BSD-style license
  *  that can be found in the LICENSE file in the root of the source
  *  tree. An additional intellectual property rights grant can be found
  *  in the file PATENTS.  All contributing project authors may
  *  be found in the AUTHORS file in the root of the source tree.
  */
 
@@ skipping 26 matching lines @@
   RTC_CHECK_LT(upper - lower, 1 << (8 * sizeof(uint16_t)));
   const size_t range = upper - lower;
   const uint16_t fuzzed = FuzzInput<uint16_t>(data, size);
   const size_t offset = (static_cast<float>(fuzzed) / 0x10000) * (range + 1);
   RTC_CHECK_LE(offset, range);  // (fuzzed <= 0xffff) -> (offset < range + 1)
   return lower + offset;
 }
 
 class TransportFeedbackGenerator {
  public:
-  explicit TransportFeedbackGenerator(rtc::ArrayView<const uint8_t> data)
-      : data_(data), ended_(false), data_idx_(0) {}
-
-  void GetNextTransportFeedback(rtcp::TransportFeedback* feedback) {
+  explicit TransportFeedbackGenerator(const uint8_t** data, size_t* size)
+      : data_(data), size_(size) {}
+
+  bool GetNextTransportFeedback(rtcp::TransportFeedback* feedback) {
+    constexpr int64_t kBaseTimeUs = 1234;  // Irrelevant to this test.

[minyue-webrtc, 2017/02/14 16:46:59]

the old place is better. Generally, make it as close to actual use as possible.

[elad.alon_webrtc.org, 2017/02/15 16:47:36]

Done.

+
     uint16_t base_seq_num = 0;
     if (!ReadData<uint16_t>(&base_seq_num)) {
-      return;
-    }
-
-    const int64_t kBaseTimeUs = 1234;  // Irrelevant to this test.
+      return false;
+    }
     feedback->SetBase(base_seq_num, kBaseTimeUs);
 
-    uint16_t num_statuses = 0;
-    if (!ReadData<uint16_t>(&num_statuses))
-      return;
-    num_statuses = std::max<uint16_t>(num_statuses, 1);
+    uint16_t remaining_packets = 0;
+    if (!ReadData<uint16_t>(&remaining_packets))
+      return false;
+    // Range is [0x00001 : 0x10000], but we keep it 0x0000 to 0xffff for now,
+    // and add the last status as RECEIVED. That is because of a limitation
+    // that says that the last status cannot be LOST.
 
     uint16_t seq_num = base_seq_num;
-    while (true) {
+    while (remaining_packets > 0) {

[minyue-webrtc, 2017/02/14 16:46:58]

if there any functional changes made in this loop?

The old style isn't bad. once we have multiple way to to exit the loop, it is
good to add exit(s) (in this case return) inside. 

[elad.alon_webrtc.org, 2017/02/15 16:47:36]

The previous code was no bad, of course! It's just that circumstances have
changed.
* Previously, you could only terminate when you were done - regardless of why
you were done - and then you'd immediately leave the function altogether.
* Now it's possible to either have "early termination" (fuzzed source ran dry)
or "proper" termination (fuzzed the right amount of packets). The former is
exits the function, the latter only the loop (followed by more code). So to make
it easier to read, I state the break condition in the loop condition, where one
would expect to find it, and only leave the early termination explicit.

       uint8_t status_byte = 0;
-      if (!ReadData<uint8_t>(&status_byte))
-        return;
+      if (!ReadData<uint8_t>(&status_byte)) {

[minyue-webrtc, 2017/02/14 16:46:59]

nit: remove {}

+        return false;
+      }
       // Each status byte contains 8 statuses.
-      for (size_t j = 0; j < 8; ++j) {
-        if (status_byte & 0x01) {
+      for (size_t i = 0; i < 8 && remaining_packets > 0; ++i) {
+        const bool received = (status_byte & (0x01 << i));
+        if (received) {

[minyue-webrtc, 2017/02/14 16:46:59]

nit: remove {}

           feedback->AddReceivedPacket(seq_num, kBaseTimeUs);
         }
-        seq_num++;
-        if (seq_num >= base_seq_num + num_statuses) {
-          feedback->AddReceivedPacket(seq_num, kBaseTimeUs);
-          return;
-        }
-        status_byte >>= 1;
+        ++seq_num;
+        --remaining_packets;
       }
     }
-  }
-
-  bool ended() const { return ended_; }
+
+    // As mentioned above, all feedbacks must report with a received packet.
+    feedback->AddReceivedPacket(seq_num, kBaseTimeUs);
+
+    return true;
+  }
 
  private:
   template <typename T>
   bool ReadData(T* value) {
-    RTC_CHECK(!ended_);
-    if (data_idx_ + sizeof(T) > data_.size()) {
-      ended_ = true;
-      return false;
-    }
-    *value = ByteReader<T>::ReadBigEndian(&data_[data_idx_]);
-    data_idx_ += sizeof(T);
-    return true;
-  }
-
-  const rtc::ArrayView<const uint8_t> data_;
-  bool ended_;
-  size_t data_idx_;
+    if (*size_ < sizeof(T)) {
+      return false;
+    } else  {
+      *value = FuzzInput<T>(data_, size_);
+      return true;
+    }
+  }
+
+  const uint8_t** data_;
+  size_t* size_;

[minyue-webrtc, 2017/02/14 16:46:59]

size_ -> remaining_bytes_

[elad.alon_webrtc.org, 2017/02/15 16:47:35]

FuzzOneInput() takes on a parameter called "size", then this value is propagated
throughout the fuzzer. IMHO, we either change everywhere or nowhere. Given that
other fuzzers use the name "size", I vote for keeping it.

[minyue-webrtc, 2017/02/16 09:51:44]

Acknowledged.

 };
 
-}  // namespace
-
-void FuzzOneInput(const uint8_t* data, size_t size) {
-  if (size < 3 * sizeof(uint16_t)) {
-    return;
-  }
+bool Setup(const uint8_t** data,
+           size_t* size,
+           std::unique_ptr<TransportFeedbackPacketLossTracker>* tracker) {
+  if (*size < 3 * sizeof(uint16_t)) {
+    return false;
+  }
+
   constexpr size_t kSeqNumHalf = 0x8000u;
 
   // 0x8000 >= max_window_size >= plr_min_num_packets > rplr_min_num_pairs >= 1
   // (The distribution isn't uniform, but it's enough; more would be overkill.)
-  const size_t max_window_size = FuzzInRange(&data, &size, 2, kSeqNumHalf);
+  const size_t max_window_size = FuzzInRange(data, size, 2, kSeqNumHalf);
   const size_t plr_min_num_packets =
-      FuzzInRange(&data, &size, 2, max_window_size);
+      FuzzInRange(data, size, 2, max_window_size);
   const size_t rplr_min_num_pairs =
-      FuzzInRange(&data, &size, 1, plr_min_num_packets - 1);
-
-  TransportFeedbackPacketLossTracker tracker(
-      max_window_size, plr_min_num_packets, rplr_min_num_pairs);
-
-  TransportFeedbackGenerator feedback_generator(
-      rtc::ArrayView<const uint8_t>(data, size));
-
-  while (!feedback_generator.ended()) {
+      FuzzInRange(data, size, 1, plr_min_num_packets - 1);
+
+  tracker->reset(new TransportFeedbackPacketLossTracker(
+        max_window_size, plr_min_num_packets, rplr_min_num_pairs));
+
+  return true;
+}
+
+bool FuzzSequenceNumberDelta(const uint8_t** data,
+                             size_t* size,
+                             uint16_t* delta) {
+  // Deltas fuzzed so that smaller deltas would be more likely, but even a
+  // complete wrap-around would be possible.
+  // Note: A delta of (x + 0x10000) is indistinguishable from a delta of (x),
+  // so deltas are distributed in the range [0 : 0xffff].
+  // The exact distribution is:
+  // * First seed in range [0 : 24] (~10% chance) -> delta is 1.
+  // * First seed in range [25 : 240] (~85% chance) -> delta in range [2 : 217]
+  // * First seed in range [241 : 255] (~5% chance) -> delta in [1 : 2^16]
+
+  if (*size < sizeof(uint8_t)) {
+    return false;
+  }
+
+  uint8_t first_seed = FuzzInput<uint8_t>(data, size);
+  if (first_seed < 25) {
+    *delta = 1;
+  } else if (first_seed < 241) {
+    *delta = first_seed - 24 + 1;
+  } else if (*size < sizeof(uint16_t)) {
+    return false;
+  } else {
+    *delta = FuzzInput<uint16_t>(data, size);  // Note: 2^16 == 0
+  }
+
+  return true;
+}
+
+bool FuzzPacketTransmissionBurst(

[minyue-webrtc, 2017/02/14 16:46:58]

And I think this is not "transmission", which may involve network, it is "send"

So I suggest "FuzzSendingPackets"

[minyue-webrtc, 2017/02/14 16:46:59]

I see the "burst" here means burst send instead of burst loss. It may be
misleading because people may not think of burst send when seeing "burst."

You may drop "burst" as a word.

[elad.alon_webrtc.org, 2017/02/15 16:47:36]

Changed to FuzzPacketBlock, to keep it consistent with
FuzzTransportFeedbackBlock, where I don't want the word "receiving" to appear.

+    std::unique_ptr<TransportFeedbackPacketLossTracker>& tracker,
+    const uint8_t** data,
+    size_t* size) {
+  // We want to test with bursts lengths between 0 and 2^16, inclusive(!).
+  // Easiest is to just disregard one potential burst size in the middle, and
+  // assign it to be representative of 2^16.
+  if (*size < sizeof(uint16_t)) {
+    return false;
+  }
+  size_t packet_transmission_burst_len = FuzzInput<uint16_t>(data, size);
+  constexpr size_t sentinel_for_wrap_around = 0x4321;
+  if (packet_transmission_burst_len == sentinel_for_wrap_around) {
+    packet_transmission_burst_len = 0xffff + 1;

[minyue-webrtc, 2017/02/14 16:46:59]

a little bit too ad hoc.

can we packet_transmission_burst_len + 1? since we don't need zero (reading
zeros is very inefficient, imagine a file of all zeros.)

[elad.alon_webrtc.org, 2017/02/15 16:47:35]

The problem is that 0 is a valid case which should be checked. Otherwise, we'd
never be running the fuzzer on a window that has no unacked messages.
(If you've got an idea how to do it more nicely, I'll be happy to implement it.)

[minyue-webrtc, 2017/02/16 09:51:44]

I think 0 case should be included in the unittest, or DCHECK, it is not the main
purpose of the fuzzer. Or do you see an additional value?

If the fuzzer data contains a lot of zeros, allowing zero block length will be
inefficient.

[elad.alon_webrtc.org, 2017/02/16 15:51:40]

Okay, I'll modify.

+  }
+
+  if (packet_transmission_burst_len == 0) {
+    return true;
+  }
+
+  // First sent sequence number uniformly selected.
+  if (*size < sizeof(uint16_t)) {
+    return false;
+  }
+  uint16_t seq_num = FuzzInput<uint16_t>(data, size);
+  tracker->OnPacketAdded(seq_num);

[minyue-webrtc, 2017/02/14 16:46:58]

try moving 182,183 in to loop.

[elad.alon_webrtc.org, 2017/02/15 16:47:36]

I think it's clearer like this - first packet gets special treatment (could
start anywhere, with uniform distribution), then subsequent ones are a delta of
the first. I'll modify the loop slightly (make it a for loop that begins at 1)
to make it more apparent that it excludes the first element, though.

[minyue-webrtc, 2017/02/16 09:51:44]

Acknowledged.

+  tracker->Validate();
+
+  // Fuzz subsequent sequence numbers according to a non-uniformly
+  // distributed delta (to make sure the fuzzer-test does not end up
+  // spending 99.9% of its time working on a mostly empty window).
+  while (--packet_transmission_burst_len > 0) {
+    uint16_t delta;
+    bool may_continue = FuzzSequenceNumberDelta(data, size, &delta);
+    if (!may_continue)
+      return false;
+    seq_num += delta;
+    tracker->OnPacketAdded(seq_num);
+    tracker->Validate();
+  }
+
+  return true;
+}
+
+bool FuzzTransportFeedbackBurst(

[minyue-webrtc, 2017/02/14 16:46:58]

try not calling this Bursts either.

FuzzTransportFeedbacks

[elad.alon_webrtc.org, 2017/02/15 16:47:36]

Done (FuzzTransportFeedbackBlock).

+    std::unique_ptr<TransportFeedbackPacketLossTracker>& tracker,
+    const uint8_t** data,
+    size_t* size) {
+  // Fuzz the number of back-to-back feedbacks. At least one, or this would
+  // be meaningless - we'd go straight back to fuzzing another packet
+  // transmission burst.
+  if (*size < sizeof(uint8_t)) {
+    return false;
+  }
+
+  size_t feedbacks_num = 1 + (FuzzInput<uint8_t>(data, size) & 0x3f);
+  TransportFeedbackGenerator feedback_generator(data, size);
+
+  for (size_t i = 0; i < feedbacks_num; i++) {
     rtcp::TransportFeedback feedback;
-    feedback_generator.GetNextTransportFeedback(&feedback);
-    tracker.OnReceivedTransportFeedback(feedback);
-    tracker.Validate();
-  }
-}
-
+    bool may_continue = feedback_generator.GetNextTransportFeedback(&feedback);
+    if (!may_continue) {
+      return false;
+    }
+    tracker->OnReceivedTransportFeedback(feedback);
+    tracker->Validate();
+  }
+
+  return true;
+}
+
+}  // namespace
+
+void FuzzOneInput(const uint8_t* data, size_t size) {
+  std::unique_ptr<TransportFeedbackPacketLossTracker> tracker;
+  bool may_continue;
+
+  may_continue = Setup(&data, &size, &tracker);
+
+  while (may_continue) {
+    may_continue = FuzzPacketTransmissionBurst(tracker, &data, &size);
+    if (!may_continue) {
+      return;
+    }
+    may_continue = FuzzTransportFeedbackBurst(tracker, &data, &size);

[minyue-webrtc, 2017/02/14 16:46:59]

it looks like send and feedback are independent. What chance would they overlap?

[elad.alon_webrtc.org, 2017/02/15 16:47:35]

When running the fuzzer, we do get them to overlap; I've checked. I can check
how often, if you'd like, but for now I'll assume that's enough.

[minyue-webrtc, 2017/02/16 09:51:44]

IMO, making the sending and feedback totally independent like this makes the
test spending most of time on "feedback does not hit any previously sent
packet", can we do something like

maintaining a set of "10 last sent sequence numbers" and pick one of them + a
chance of none-of-them when sending feedback.

[minyue-webrtc, 2017/02/16 13:19:22]

I realized that I was wrong in saying that "feedback, in most time, does not hit
any previously sent packet". Hitting can happen because there are a number (up
to max_window_size) of sent packets sparsely distributed in the buffer, and the
feedback is a continuum of packets, where the number of packets can be large. In
that sense, it is fine to let the two be independent.

+  }
+}
+
 }  // namespace webrtc