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) {
     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;
+    }
+    constexpr int64_t kBaseTimeUs = 1234;  // Irrelevant to this test.
     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) {
       uint8_t status_byte = 0;
-      if (!ReadData<uint8_t>(&status_byte))
-        return;
+      if (!ReadData<uint8_t>(&status_byte)) {
+        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) {
           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_;
 };
 
-}  // 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]

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

as discussed offline, the outcome of a large delta can be achieved anyway since
we loop Send - Feedback several times. 

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

Done.

+
+  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 FuzzPacketBlock(

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

I do not quite like the name. Unlike TransportFeedback, we do not fuzz any
"Packet", we fuzz packet sending event.

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

FuzzPacketSendBlock, then?

[minyue-webrtc, 2017/02/17 11:09:14]

that sounds good, and it is coupled to FuzzTransportFeedbackBlock

+    std::unique_ptr<TransportFeedbackPacketLossTracker>& tracker,
+    const uint8_t** data,
+    size_t* size) {
+  // We want to test with block lengths between 0 and 2^16, inclusive(!).
+  // Easiest is to just disregard one potential block size in the middle, and
+  // assign it to be representative of 2^16.
+  if (*size < sizeof(uint16_t)) {
+    return false;
+  }
+  size_t packet_block_len = FuzzInput<uint16_t>(data, size);
+  constexpr size_t sentinel_for_wrap_around = 0x4321;
+  if (packet_block_len == sentinel_for_wrap_around) {
+    packet_block_len = 0xffff + 1;
+  }
+
+  if (packet_block_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);
+  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).
+  for (size_t i = 1; i < packet_block_len; i++) {
+    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 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 block.
+  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 = FuzzPacketBlock(tracker, &data, &size);
+    if (!may_continue) {
+      return;
+    }
+    may_continue = FuzzTransportFeedbackBlock(tracker, &data, &size);
+  }
+}
+
 }  // namespace webrtc