diff --git a/src/Makefile.test.include b/src/Makefile.test.include
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -20,6 +20,7 @@
   test/fuzz/inv_deserialize \
   test/fuzz/messageheader_deserialize \
   test/fuzz/netaddr_deserialize \
+  test/fuzz/script_flags \
   test/fuzz/service_deserialize \
   test/fuzz/transaction_deserialize \
   test/fuzz/txoutcompressor_deserialize \
@@ -401,6 +402,23 @@
  $(LIBSECP256K1)
 test_fuzz_netaddr_deserialize_LDADD += $(BOOST_LIBS) $(CRYPTO_LIBS)
 
+test_fuzz_script_flags_SOURCES = $(FUZZ_SUITE) test/fuzz/script_flags.cpp
+test_fuzz_script_flags_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES)
+test_fuzz_script_flags_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
+test_fuzz_script_flags_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS)
+test_fuzz_script_flags_LDADD = \
+ $(LIBUNIVALUE) \
+ $(LIBBITCOIN_SERVER) \
+ $(LIBBITCOIN_COMMON) \
+ $(LIBBITCOIN_UTIL) \
+ $(LIBBITCOIN_CONSENSUS) \
+ $(LIBBITCOIN_CRYPTO) \
+ $(LIBBITCOIN_CRYPTO_SSE41) \
+ $(LIBBITCOIN_CRYPTO_AVX2) \
+ $(LIBBITCOIN_CRYPTO_SHANI) \
+ $(LIBSECP256K1)
+test_fuzz_script_flags_LDADD += $(BOOST_LIBS) $(CRYPTO_LIBS)
+
 test_fuzz_service_deserialize_SOURCES = $(FUZZ_SUITE) test/fuzz/deserialize.cpp
 test_fuzz_service_deserialize_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) -DSERVICE_DESERIALIZE=1
 test_fuzz_service_deserialize_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
diff --git a/src/test/fuzz/CMakeLists.txt b/src/test/fuzz/CMakeLists.txt
--- a/src/test/fuzz/CMakeLists.txt
+++ b/src/test/fuzz/CMakeLists.txt
@@ -1,23 +1,33 @@
 # Fuzzer test harness
 add_custom_target(bitcoin-fuzzers)
 
+macro(add_fuzz_target TARGET EXE_NAME)
+	add_executable(${TARGET} EXCLUDE_FROM_ALL
+		fuzz.cpp
+		${ARGN}
+	)
+	set_target_properties(${TARGET} PROPERTIES OUTPUT_NAME ${EXE_NAME})
+
+	target_link_libraries(${TARGET} server)
+
+	add_dependencies(bitcoin-fuzzers ${TARGET})
+endmacro()
+
 include(SanitizeHelper)
 function(add_deserialize_fuzz_targets)
 	foreach(_fuzz_test_name ${ARGN})
 		sanitize_target_name("fuzz-" ${_fuzz_test_name} _fuzz_target_name)
-		add_executable(${_fuzz_target_name} EXCLUDE_FROM_ALL
+		add_fuzz_target(
+			${_fuzz_target_name}
+			${_fuzz_test_name}
+
+			# Sources
 			deserialize.cpp
-			fuzz.cpp
 		)
-		set_target_properties(${_fuzz_target_name} PROPERTIES OUTPUT_NAME ${_fuzz_test_name})
 
 		sanitize_c_cxx_definition("" ${_fuzz_test_name} _target_definition)
 		string(TOUPPER ${_target_definition} _target_definition)
 		target_compile_definitions(${_fuzz_target_name} PRIVATE ${_target_definition})
-
-		target_link_libraries(${_fuzz_target_name} server)
-
-		add_dependencies(bitcoin-fuzzers ${_fuzz_target_name})
 	endforeach()
 endfunction()
 
@@ -43,3 +53,12 @@
 	txoutcompressor_deserialize
 	txundo_deserialize
 )
+
+add_fuzz_target(
+	fuzz-script_flags
+	script_flags
+
+	# Sources
+	fuzz.cpp
+	script_flags.cpp
+)
diff --git a/src/test/fuzz/script_flags.cpp b/src/test/fuzz/script_flags.cpp
new file mode 100644
--- /dev/null
+++ b/src/test/fuzz/script_flags.cpp
@@ -0,0 +1,79 @@
+// Copyright (c) 2009-2019 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <script/interpreter.h>
+#include <script/script.h>
+#include <streams.h>
+#include <version.h>
+
+#include <test/fuzz/fuzz.h>
+
+/** Flags that are not forbidden by an assert */
+static bool IsValidFlagCombination(uint32_t flags);
+
+void test_one_input(std::vector<uint8_t> buffer) {
+    CDataStream ds(buffer, SER_NETWORK, INIT_PROTO_VERSION);
+    try {
+        int nVersion;
+        ds >> nVersion;
+        ds.SetVersion(nVersion);
+    } catch (const std::ios_base::failure &) {
+        return;
+    }
+
+    try {
+        const CTransaction tx(deserialize, ds);
+        const PrecomputedTransactionData txdata(tx);
+
+        uint32_t verify_flags;
+        ds >> verify_flags;
+
+        if (!IsValidFlagCombination(verify_flags)) {
+            return;
+        }
+
+        uint32_t fuzzed_flags;
+        ds >> fuzzed_flags;
+
+        for (unsigned int i = 0; i < tx.vin.size(); ++i) {
+            CTxOut prevout;
+            ds >> prevout;
+
+            const TransactionSignatureChecker checker{&tx, i, prevout.nValue,
+                                                      txdata};
+
+            ScriptError serror;
+            const bool ret =
+                VerifyScript(tx.vin.at(i).scriptSig, prevout.scriptPubKey,
+                             verify_flags, checker, &serror);
+            assert(ret == (serror == ScriptError::OK));
+
+            // Verify that removing flags from a passing test or adding flags to
+            // a failing test does not change the result
+            if (ret) {
+                verify_flags &= ~fuzzed_flags;
+            } else {
+                verify_flags |= fuzzed_flags;
+            }
+            if (!IsValidFlagCombination(verify_flags)) {
+                return;
+            }
+
+            ScriptError serror_fuzzed;
+            const bool ret_fuzzed =
+                VerifyScript(tx.vin.at(i).scriptSig, prevout.scriptPubKey,
+                             verify_flags, checker, &serror_fuzzed);
+            assert(ret_fuzzed == (serror_fuzzed == ScriptError::OK));
+
+            assert(ret_fuzzed == ret);
+        }
+    } catch (const std::ios_base::failure &) {
+        return;
+    }
+}
+
+static bool IsValidFlagCombination(uint32_t flags) {
+    // If the CLEANSTACK flag is set, then P2SH should also be set
+    return (~flags & SCRIPT_VERIFY_CLEANSTACK) || (flags & SCRIPT_VERIFY_P2SH);
+}