First-order-FEC recoverability calculation

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.
  */
 
 #include <algorithm>
+#include <array>

[minyue-webrtc, 2017/01/30 09:30:23]

no need if you take my suggestion

 
 #include "webrtc/base/array_view.h"
 #include "webrtc/modules/rtp_rtcp/source/byte_io.h"
 #include "webrtc/modules/rtp_rtcp/source/rtcp_packet/transport_feedback.h"
 #include "webrtc/voice_engine/transport_feedback_packet_loss_tracker.h"
 
 namespace webrtc {
 
 namespace {
 
+template <typename T>
+T FuzzInput(const uint8_t** data, size_t* size) {
+  RTC_CHECK(*size >= sizeof(T));
+  T rc = ByteReader<T>::ReadBigEndian(*data);
+  *data += sizeof(T);
+  *size -= sizeof(T);
+  return rc;
+}
+
 class TransportFeedbackGenerator {
  public:
   explicit TransportFeedbackGenerator(rtc::ArrayView<const uint8_t> data)
       : data_(data), ended_(false), data_idx_(0) {}
 
   void GetNextTransportFeedback(rtcp::TransportFeedback* feedback) {
     uint16_t base_seq_num = 0;
     if (!ReadData<uint16_t>(&base_seq_num)) {
       return;
     }
@@ skipping 42 matching lines @@
   }
 
   const rtc::ArrayView<const uint8_t> data_;
   bool ended_;
   size_t data_idx_;
 };
 
 }  // namespace
 
 void FuzzOneInput(const uint8_t* data, size_t size) {
-  if (size < sizeof(uint32_t)) {
+  if (size < 3 * sizeof(uint16_t)) {
     return;
   }
   constexpr size_t kSeqNumHalf = 0x8000u;
-  const size_t window_size_1 = std::min<size_t>(
+
+  // Produce:
+  // 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.)

[minyue-webrtc, 2017/01/30 09:30:23]

looks a bit cumbersome. You sort the values, but sorting the values does not
give you a readily feasible set of parameters.

I would do

rplr_min_num_pairs = std::min<size_t>(0x7999, std::max<uint_16>(1,
FuzzInput<uint_16>(&data, &size)));

plr_min_num_packets = std::min<size_t>(0x8000, rplr_min_num_pairs +
std::max<uint_16>(1, FuzzInput<uint_16>(&data, &size)));

max_window_size = std::min<size_t>(0x8000,  plr_min_num_packets +
FuzzInput<uint_16>(&data, &size))

[elad.alon_webrtc.org, 2017/01/30 11:14:12]

nit: I think you meant 0x7fff, not 0x7999.

All of these (simple) methods skew the distribution away from completely
uniform, and picking something else would be overkill.
* Randomly picking three, then sorting, gives a higher likelihood to higher
maximums and lower minimums.
* Doing it one by one, but with capping, means the first value is uniformly
distributed, but subsequent values get ever worse biases.

Thinking it again, yes, I do prefer the second approach. I'll do away with the
sorting and fuzz them one by one. To reduce the skew, I'll disregard those bits
in subsequent fuzzed values which are known to be irrelevant before using
std::max, meaning I'll get a slightly less severe bias.

+
+  std::array<size_t, 3> sizes;
+  for (size_t i = 0; i < 3; i++) {
+    constexpr uint16_t mask = (kSeqNumHalf - 1);  // 0x7fff
+    uint16_t t = FuzzInput<uint16_t>(&data, &size);
+    sizes[i] = 1 + (mask & t);  // 1 : 0x8000
+  }
+  std::sort(sizes.begin(), sizes.end(), std::greater<size_t>());
+
+  // Range = [2 : 0x8000]
+  const size_t max_window_size = std::min<size_t>(
       kSeqNumHalf,
-      std::max<uint16_t>(1, ByteReader<uint16_t>::ReadBigEndian(data)));
-  data += sizeof(uint16_t);
-  const size_t window_size_2 = std::min<size_t>(
-      kSeqNumHalf,
-      std::max<uint16_t>(1, ByteReader<uint16_t>::ReadBigEndian(data)));
-  data += sizeof(uint16_t);
-  size -= 2 * sizeof(uint16_t);
+      std::max<size_t>(2, sizes[0]));
+
+  // Range = [2 : max_window_size]
+  const size_t plr_min_num_packets = std::min<size_t>(
+      max_window_size,
+      std::max<size_t>(2, sizes[1]));
+
+  // Range = [1 : plr_min_num_packets - 1]
+  const size_t rplr_min_num_pairs = std::min<size_t>(
+      plr_min_num_packets - 1,
+      sizes[2]);
 
   TransportFeedbackPacketLossTracker tracker(
-      std::min(window_size_1, window_size_2),
-      std::max(window_size_1, window_size_2));
+      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()) {
     rtcp::TransportFeedback feedback;
     feedback_generator.GetNextTransportFeedback(&feedback);
     tracker.OnReceivedTransportFeedback(feedback);
     tracker.Validate();
   }
 }
 
 }  // namespace webrtc