diff --git a/libs/binder/tests/parcel_fuzzer/include_random_parcel/fuzzbinder/random_parcel.h b/libs/binder/tests/parcel_fuzzer/include_random_parcel/fuzzbinder/random_parcel.h
index db35e39..633626c 100644
--- a/libs/binder/tests/parcel_fuzzer/include_random_parcel/fuzzbinder/random_parcel.h
+++ b/libs/binder/tests/parcel_fuzzer/include_random_parcel/fuzzbinder/random_parcel.h
@@ -19,9 +19,18 @@
 #include <binder/Parcel.h>
 #include <fuzzer/FuzzedDataProvider.h>
 
+#include <functional>
+
 namespace android {
 /**
  * Fill parcel data, including some random binder objects and FDs
+ *
+ * p - the Parcel to fill
+ * provider - takes ownership and completely consumes provider
+ * writeHeader - optional function to write a specific header once the format of the parcel is
+ *     picked (for instance, to write an interface header)
  */
-void fillRandomParcel(Parcel* p, FuzzedDataProvider&& provider);
+void fillRandomParcel(
+        Parcel* p, FuzzedDataProvider&& provider,
+        std::function<void(Parcel* p, FuzzedDataProvider& provider)> writeHeader = nullptr);
 } // namespace android
diff --git a/libs/binder/tests/parcel_fuzzer/libbinder_driver.cpp b/libs/binder/tests/parcel_fuzzer/libbinder_driver.cpp
index e849c9b..be39bb9 100644
--- a/libs/binder/tests/parcel_fuzzer/libbinder_driver.cpp
+++ b/libs/binder/tests/parcel_fuzzer/libbinder_driver.cpp
@@ -27,7 +27,14 @@
 
         std::vector<uint8_t> subData = provider.ConsumeBytes<uint8_t>(
                 provider.ConsumeIntegralInRange<size_t>(0, provider.remaining_bytes()));
-        fillRandomParcel(&data, FuzzedDataProvider(subData.data(), subData.size()));
+        fillRandomParcel(&data, FuzzedDataProvider(subData.data(), subData.size()),
+                         [&binder](Parcel* p, FuzzedDataProvider& provider) {
+                             // most code will be behind checks that the head of the Parcel
+                             // is exactly this, so make it easier for fuzzers to reach this
+                             if (provider.ConsumeBool()) {
+                                 p->writeInterfaceToken(binder->getInterfaceDescriptor());
+                             }
+                         });
 
         Parcel reply;
         (void)binder->transact(code, data, &reply, flags);
diff --git a/libs/binder/tests/parcel_fuzzer/random_parcel.cpp b/libs/binder/tests/parcel_fuzzer/random_parcel.cpp
index 89eadae..cfabc1e 100644
--- a/libs/binder/tests/parcel_fuzzer/random_parcel.cpp
+++ b/libs/binder/tests/parcel_fuzzer/random_parcel.cpp
@@ -39,15 +39,21 @@
     CHECK(OK == p->write(data.data(), data.size()));
 }
 
-void fillRandomParcel(Parcel* p, FuzzedDataProvider&& provider) {
+void fillRandomParcel(Parcel* p, FuzzedDataProvider&& provider,
+                      std::function<void(Parcel* p, FuzzedDataProvider& provider)> writeHeader) {
     if (provider.ConsumeBool()) {
         auto session = RpcSession::make(RpcTransportCtxFactoryRaw::make());
         CHECK_EQ(OK, session->addNullDebuggingClient());
         p->markForRpc(session);
+
+        writeHeader(p, provider);
+
         fillRandomParcelData(p, std::move(provider));
         return;
     }
 
+    writeHeader(p, provider);
+
     while (provider.remaining_bytes() > 0) {
         auto fillFunc = provider.PickValueInArray<const std::function<void()>>({
                 // write data