First-order-FEC recoverability calculation

webrtc/test/fuzzers/transport_feedback_packet_loss_tracker_fuzzer.cc

Index: webrtc/test/fuzzers/transport_feedback_packet_loss_tracker_fuzzer.cc
diff --git a/webrtc/test/fuzzers/transport_feedback_packet_loss_tracker_fuzzer.cc b/webrtc/test/fuzzers/transport_feedback_packet_loss_tracker_fuzzer.cc
index 837ae883f6c83f213c9951d0f21832d363359cc7..c68d9e68a2e8e4e00dc2021d9f38b3b46ae55fa6 100644
--- a/webrtc/test/fuzzers/transport_feedback_packet_loss_tracker_fuzzer.cc
+++ b/webrtc/test/fuzzers/transport_feedback_packet_loss_tracker_fuzzer.cc
@@ -9,6 +9,7 @@
  */
 
 #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"
@@ -19,6 +20,15 @@ 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)
@@ -81,25 +91,44 @@ class TransportFeedbackGenerator {
 }  // 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>(
-      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>(
+
+  // 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);
-  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);