This filter adds random data corruption when reading from the
underlying plugin.
---
filters/error/nbdkit-error-filter.pod | 4 +
filters/evil/nbdkit-evil-filter.pod | 159 ++++++++++++
configure.ac | 2 +
filters/evil/Makefile.am | 77 ++++++
tests/Makefile.am | 14 +
filters/evil/evil.c | 353 ++++++++++++++++++++++++++
tests/test-evil-cosmic.sh | 76 ++++++
tests/test-evil-stuck-high-bits.sh | 86 +++++++
tests/test-evil-stuck-low-bits.sh | 79 ++++++
tests/test-evil-stuck-wires.sh | 85 +++++++
10 files changed, 935 insertions(+)
diff --git a/filters/error/nbdkit-error-filter.pod
b/filters/error/nbdkit-error-filter.pod
index 49f21d10a..91af7f713 100644
--- a/filters/error/nbdkit-error-filter.pod
+++ b/filters/error/nbdkit-error-filter.pod
@@ -25,6 +25,9 @@ All parameters are optional, but you should usually specify
one of the
C<error-rate> or C<error-*-rate> parameters,
B<otherwise this filter will do nothing>.
+L<nbdkit-evil-filter(1)> is a related filter that injects data
+corruption instead of errors.
+
=head1 EXAMPLES
Inject a low rate of errors randomly into the connection:
@@ -162,6 +165,7 @@ C<nbdkit-error-filter> first appeared in nbdkit 1.6.
=head1 SEE ALSO
L<nbdkit(1)>,
+L<nbdkit-evil-filter(1)>,
L<nbdkit-file-plugin(1)>,
L<nbdkit-full-plugin(1)>,
L<nbdkit-retry-filter(1)>,
diff --git a/filters/evil/nbdkit-evil-filter.pod
b/filters/evil/nbdkit-evil-filter.pod
new file mode 100644
index 000000000..5100117ab
--- /dev/null
+++ b/filters/evil/nbdkit-evil-filter.pod
@@ -0,0 +1,159 @@
+=head1 NAME
+
+nbdkit-evil-filter - add random data corruption to reads
+
+=head1 SYNOPSIS
+
+ nbdkit --filter=evil PLUGIN [PLUGIN-ARGS...]
+ evil=[cosmic-rays|stuck-bits|stuck-wires]
+ [evil-probability=PROB] [evil-stuck-probability=PROB]
+ [evil-seed=SEED]
+
+=head1 DESCRIPTION
+
+nbdkit-evil-filter is a Byzantine filter for L<nbdkit(1)> that
+randomly corrupts data when reading from the underlying plugin. This
+can be used for testing filesystem checksums. Note that it does not
+change write operations, so the underlying plugin contains the correct
+data.
+
+L<nbdkit-error-filter(1)> is a related filter that injects hard errors
+into the NBD protocol.
+
+This filter has several modes, controlled using the C<evil=...>
+parameter. These are:
+
+=over 4
+
+=item C<evil=cosmic-rays>
+
+Bits are flipped at random when reading data. The probability that a
+bit is flipped is controlled using the C<evil-probability> parameter,
+defaulting to 1e-8 (on average 1 in every 100 million bits read is
+flipped).
+
+=item C<evil=stuck-bits>
+
+This is the default mode.
+
+Fixed bits in the backing file are stuck randomly high or low. The
+C<evil-probability> parameter controls the expected probability that a
+particular bit is stuck, defaulting in this mode to 1e-8 (1 in 100
+million). C<evil-stuck-probability> controls the probability that a
+stuck bit is read as its stuck value or its correct value, defaulting
+to 100% (always read as a stuck bit).
+
+=item C<evil=stuck-wires>
+
+This is similar to C<stuck-bits> but instead of simulating bad backing
+data, it simulates stuck wires along the data path (eg. in a
+register). The difference is that when reading, the stuck bit always
+happens at the same position in the packet of data being read,
+regardless of where on the underlying disk it is being read from.
+C<evil-probability> and controls the probability of a stuck wire,
+defaulting in this mode to 1e-6 (1 in 1 million).
+C<evil-stuck-probability> controls the probability that a stuck bit is
+read as its stuck value or its correct value, defaulting to 100%
+(always read as a stuck bit).
+
+=back
+
+=head1 EXAMPLES
+
+Add some stuck bits to the backing file at random:
+
+ nbdkit --filter=evil file disk.img
+
+Cosmic rays will flip (on average) one in every 100 million bits
+copied from the backing file over NBD:
+
+ nbdkit --filter=evil file disk.img evil=cosmic-rays \
+ --run 'nbdcopy $uri output.img'
+
+=head2 Extents
+
+Plugins can be sparse. This filter only corrupts bits in non-sparse
+parts of the backing disk and it leaves sparse regions unchanged
+(which is realistic behaviour). If you wish to use this filter to
+corrupt sparse regions, then combine this filter with
+L<nbdkit-noextents-filter(1)>. For example:
+
+ nbdkit --filter=evil --filter=noextents memory 1G
+
+=head1 PARAMETERS
+
+=over 4
+
+=item B<evil=cosmic-rays>
+
+=item B<evil=stuck-bits>
+
+=item B<evil=stuck-wires>
+
+Select the mode of evil. See the L</DESCRIPTION> above. The default
+is C<stuck-bits>.
+
+=item B<evil-probability=>N
+
+=item B<evil-probability=>NB<:>M
+
+=item B<evil-probability=>NB<%>
+
+Set the probability for the mode. You can either use a floating point
+number between 0 and 1, eg. C<evil-probability=0.001> or
+C<evil-probability=1e-6>. Or you can write it as N in M, eg.
+C<evil-probability=1:1000000> or C<evil-probability=3.33:100000>.
Or
+you can write this as a percentage, eg. C<evil-probability=1%>.
+
+The default probability depends on the mode.
+
+=item B<evil-seed=>SEED
+
+To make runs repeatable, use this to set a seed for the random number
+generator. The default is to choose a seed at random.
+
+=item B<evil-stuck-probability=>N
+
+=item B<evil-stuck-probability=>NB<:>M
+
+=item B<evil-stuck-probability=>NB<%>
+
+For the "stuck-*" modes, the probability that when reading a stuck
bit
+you will read the stuck bit or the correct value. This defaults to 1
+(ie. 100%) which means the bit is always stuck. Setting it to 0.5 for
+example will mean that half the time the bit appears stuck and half
+the time you see the correct value.
+
+=back
+
+=head1 FILES
+
+=over 4
+
+=item F<$filterdir/nbdkit-evil-filter.so>
+
+The filter.
+
+Use C<nbdkit --dump-config> to find the location of C<$filterdir>.
+
+=back
+
+=head1 VERSION
+
+C<nbdkit-pause-filter> first appeared in nbdkit 1.36.
+
+=head1 SEE ALSO
+
+L<nbdkit(1)>,
+L<nbdkit-filter(3)>,
+L<nbdkit-delay-filter(1)>,
+L<nbdkit-noextents-filter(1)>,
+L<nbdkit-error-filter(1)>.
+
+=head1 AUTHORS
+
+Richard W.M. Jones
+
+=head1 COPYRIGHT
+
+Copyright Red Hat
diff --git a/configure.ac b/configure.ac
index 310de7ac1..18431958a 100644
--- a/configure.ac
+++ b/configure.ac
@@ -124,6 +124,7 @@ filters="\
exportname \
ext2 \
extentlist \
+ evil \
fua \
gzip \
ip \
@@ -1534,6 +1535,7 @@ AC_CONFIG_FILES([Makefile
filters/exportname/Makefile
filters/ext2/Makefile
filters/extentlist/Makefile
+ filters/evil/Makefile
filters/fua/Makefile
filters/gzip/Makefile
filters/ip/Makefile
diff --git a/filters/evil/Makefile.am b/filters/evil/Makefile.am
new file mode 100644
index 000000000..ac6337428
--- /dev/null
+++ b/filters/evil/Makefile.am
@@ -0,0 +1,77 @@
+# nbdkit
+# Copyright Red Hat
+#
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions are
+# met:
+#
+# * Redistributions of source code must retain the above copyright
+# notice, this list of conditions and the following disclaimer.
+#
+# * Redistributions in binary form must reproduce the above copyright
+# notice, this list of conditions and the following disclaimer in the
+# documentation and/or other materials provided with the distribution.
+#
+# * Neither the name of Red Hat nor the names of its contributors may be
+# used to endorse or promote products derived from this software without
+# specific prior written permission.
+#
+# THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS
IS'' AND
+# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+# THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+# PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR
+# CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+# USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+# SUCH DAMAGE.
+
+include $(top_srcdir)/common-rules.mk
+
+EXTRA_DIST = nbdkit-evil-filter.pod
+
+# Relies on a Unix domain socket.
+if !IS_WINDOWS
+
+filter_LTLIBRARIES = nbdkit-evil-filter.la
+
+nbdkit_evil_filter_la_SOURCES = \
+ evil.c \
+ $(top_srcdir)/include/nbdkit-filter.h \
+ $(NULL)
+
+nbdkit_evil_filter_la_CPPFLAGS = \
+ -I$(top_srcdir)/include \
+ -I$(top_builddir)/include \
+ -I$(top_srcdir)/common/include \
+ -I$(top_srcdir)/common/utils \
+ $(NULL)
+nbdkit_evil_filter_la_CFLAGS = $(WARNINGS_CFLAGS)
+nbdkit_evil_filter_la_LIBADD = \
+ $(top_builddir)/common/utils/libutils.la \
+ $(IMPORT_LIBRARY_ON_WINDOWS) \
+ $(NULL)
+nbdkit_evil_filter_la_LDFLAGS = \
+ -module -avoid-version -shared $(NO_UNDEFINED_ON_WINDOWS) \
+ $(NULL)
+if USE_LINKER_SCRIPT
+nbdkit_evil_filter_la_LDFLAGS += \
+ -Wl,--version-script=$(top_srcdir)/filters/filters.syms
+endif
+
+if HAVE_POD
+
+man_MANS = nbdkit-evil-filter.1
+CLEANFILES += $(man_MANS)
+
+nbdkit-evil-filter.1: nbdkit-evil-filter.pod \
+ $(top_builddir)/podwrapper.pl
+ $(PODWRAPPER) --section=1 --man $@ \
+ --html $(top_builddir)/html/$@.html \
+ $<
+
+endif HAVE_POD
+endif !IS_WINDOWS
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 3ae13d660..ca4fc6b4e 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -1598,6 +1598,20 @@ EXTRA_DIST += \
test-error-triggered.sh \
$(NULL)
+# evil filter test.
+TESTS += \
+ test-evil-cosmic.sh \
+ test-evil-stuck-high-bits.sh \
+ test-evil-stuck-low-bits.sh \
+ test-evil-stuck-wires.sh \
+ $(NULL)
+EXTRA_DIST += \
+ test-evil-cosmic.sh \
+ test-evil-stuck-high-bits.sh \
+ test-evil-stuck-low-bits.sh \
+ test-evil-stuck-wires.sh \
+ $(NULL)
+
# exitlast filter test.
TESTS += test-exitlast.sh
EXTRA_DIST += test-exitlast.sh
diff --git a/filters/evil/evil.c b/filters/evil/evil.c
new file mode 100644
index 000000000..e961f6861
--- /dev/null
+++ b/filters/evil/evil.c
@@ -0,0 +1,353 @@
+/* nbdkit
+ * Copyright Red Hat
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * * Neither the name of Red Hat nor the names of its contributors may be
+ * used to endorse or promote products derived from this software without
+ * specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS
IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+ * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+ * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <config.h>
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <inttypes.h>
+#include <string.h>
+#include <time.h>
+#include <assert.h>
+
+#include <nbdkit-filter.h>
+
+#include "minmax.h"
+#include "ispowerof2.h"
+#include "random.h"
+
+enum mode {
+ COSMIC_RAYS,
+ STUCK_BITS,
+ STUCK_WIRES,
+};
+
+static enum mode evil_mode = STUCK_BITS;
+static double evil_probability = -1; /* default depends on mode */
+static double evil_stuck_probability = 1.0;
+static uint32_t evil_seed;
+
+static void
+evil_load (void)
+{
+ evil_seed = time (NULL);
+}
+
+static int
+evil_config (nbdkit_next_config *next, nbdkit_backend *nxdata,
+ const char *key, const char *value)
+{
+ if (strcmp (key, "evil") == 0 || strcmp (key,
"evil-mode") == 0) {
+ if (strcmp (value, "cosmic-rays") == 0 ||
+ strcmp (value, "cosmic") == 0) {
+ evil_mode = COSMIC_RAYS;
+ return 0;
+ }
+ else if (strcmp (value, "stuck-bits") == 0 ||
+ strcmp (value, "stuck-bit") == 0 ||
+ strcmp (value, "stuck") == 0) {
+ evil_mode = STUCK_BITS;
+ return 0;
+ }
+ else if (strcmp (value, "stuck-wires") == 0 ||
+ strcmp (value, "stuck-wire") == 0) {
+ evil_mode = STUCK_WIRES;
+ return 0;
+ }
+ else {
+ nbdkit_error ("evil: unknown mode: %s", value);
+ return -1;
+ }
+ }
+ else if (strcmp (key, "evil-probability") == 0) {
+ if (nbdkit_parse_probability ("evil-probability", value,
+ &evil_probability) == -1)
+ return -1;
+ if (evil_probability < 0 || evil_probability > 1) {
+ nbdkit_error ("%s: probability out of range, should be [0..1]",
key);
+ return -1;
+ }
+ return 0;
+ }
+ else if (strcmp (key, "evil-stuck-probability") == 0) {
+ if (nbdkit_parse_probability ("evil-stuck-probability", value,
+ &evil_stuck_probability) == -1)
+ return -1;
+ if (evil_stuck_probability < 0 || evil_stuck_probability > 1) {
+ nbdkit_error ("%s: probability out of range, should be [0..1]",
key);
+ return -1;
+ }
+ return 0;
+ }
+ else if (strcmp (key, "evil-seed") == 0) {
+ if (nbdkit_parse_uint32_t ("evil-seed", value, &evil_seed) ==
-1)
+ return -1;
+ return 0;
+ }
+ else
+ return next (nxdata, key, value);
+}
+
+static int
+evil_config_complete (nbdkit_next_config_complete *next,
+ nbdkit_backend *nxdata)
+{
+ if (evil_probability < 0) {
+ /* Choose default probability based on the chosen mode. */
+ switch (evil_mode) {
+ case COSMIC_RAYS:
+ case STUCK_BITS:
+ evil_probability = 1e-8;
+ break;
+ case STUCK_WIRES:
+ evil_probability = 1e-6;
+ }
+ }
+
+ return next (nxdata);
+}
+
+#define evil_config_help \
+ "evil=cosmic-rays|stuck-bits|stuck-wires\n" \
+ " Set the mode (default:
cosmic-rays).\n" \
+ "evil-probability=PROB Probability of flipped or stuck
bit.\n" \
+ "evil-seed=SEED Random number seed.\n" \
+ "evil-stuck-probability=PROB Probability of stuck bit being
stuck."
+
+/* This is the heart of the algorithm, the function which corrupts
+ * the buffer after reading it from the plugin.
+ *
+ * The observation is that if we have a block of (eg) size 10^6 bits
+ * and our probability of finding a corrupt bit is (eg) 1/10^4, then
+ * we expect approximately 100 bits in the block to be corrupted.
+ *
+ * For stuck bits we want the corrupted bits to be the same on each
+ * access, either relative to the backing disk (STUCK_BITS) or to the
+ * request (STUCK_WIRES).
+ *
+ * Instead of creating an expensive bitmap ahead of time covering the
+ * whole disk, we can use the random number generator with a fixed
+ * seed derived from the offset of the start of the block. We can
+ * then choose a random number uniformly in the range [0..2*(1/P)] (in
+ * the example [0..2*10^4]) as the distance to the next corrupt bit.
+ * We jump forwards, corrupt that bit, and repeat until we reach
+ * the end of the block.
+ *
+ * "Corrupted" in this case can mean flipped by cosmic rays or stuck,
+ * depending on the filter mode.
+ *
+ * On average this will choose the right number of bits in the block.
+ * (Although their distribution will be suboptimal. In a uniform
+ * distribution it should be possible for two corrupted bits to be
+ * greater than 2*(1/P) apart, but the above algorithm would not do
+ * this. In practice this probably doesn't matter.)
+ *
+ * Note that "block" != "buffer", especially in the
STUCK_BITS mode.
+ * We iterate over blocks as above, but only corrupt a bit when it
+ * happens to coincide with the buffer we have just read.
+ *
+ * We choose the block size adaptively so that at least 100 bits in
+ * the block will be corrupted. The block size must be a power of 2.
+ * The block size thus depends on the probability.
+ */
+enum corruption_type { FLIP, STUCK };
+
+static uint64_t block_size; /* in bytes */
+static struct random_state state; /* only used for cosmic-rays */
+
+static int
+evil_thread_model (void)
+{
+ switch (evil_mode) {
+ case COSMIC_RAYS:
+ /* Because cosmic-rays uses the global random state we need to
+ * tighten the thread model.
+ */
+ return NBDKIT_THREAD_MODEL_SERIALIZE_REQUESTS;
+
+ case STUCK_BITS:
+ case STUCK_WIRES:
+ return NBDKIT_THREAD_MODEL_PARALLEL;
+ }
+ abort ();
+}
+
+static int
+evil_get_ready (int thread_model)
+{
+ switch (evil_mode) {
+ case COSMIC_RAYS:
+ xsrandom ((uint64_t) evil_seed, &state);
+ break;
+
+ case STUCK_BITS:
+ case STUCK_WIRES:
+ ;
+ }
+
+ /* Choose the block size based on the probability, so that at least
+ * 100 bits are expected to be corrupted in the block. Block size
+ * must be a power of 2.
+ */
+ block_size = next_power_of_2 ((uint64_t) (100. / evil_probability));
+
+ return 0;
+}
+
+static uint8_t
+corrupt_one_bit (uint8_t byte, unsigned bit,
+ uint64_t rand, enum corruption_type ct)
+{
+ const unsigned mask = 1 << bit;
+
+ switch (ct) {
+ case FLIP:
+ byte ^= mask;
+ break;
+ case STUCK:
+ rand &= 0xffffffff;
+ if (evil_stuck_probability * 0x100000000 > rand) {
+ if (rand & 1) /* stuck high or low? */
+ byte |= mask;
+ else
+ byte &= ~mask;
+ }
+ }
+ return byte;
+}
+
+static void
+corrupt_buffer (uint8_t *buf, uint32_t count, uint64_t offset_in_block,
+ struct random_state *rs, enum corruption_type ct)
+{
+ if (evil_probability == 0)
+ /* No corruption, and avoids a divide by zero below. */
+ return;
+
+ uint64_t offs, intvl, i, rand;
+ const uint64_t dinvp = (uint64_t) (2.0 * (1.0 / evil_probability));
+
+ assert ((offset_in_block & ~(block_size-1)) == 0);
+
+ /* Iterate over the whole block from the start. */
+ for (offs = 0; offs < offset_in_block + count; ) {
+ /* Choose the length of the interval to the next corrupted bit, by
+ * picking a random number in [0..2*(1/P)].
+ *
+ * Remember this is in bits!
+ */
+ intvl = xrandom (rs) % dinvp;
+
+ /* Consume one more random state. We may or may not use this.
+ * But we need to always consume two random states per iteration
+ * to make the output predictable.
+ */
+ rand = xrandom (rs);
+
+ /* Adjust offs to that byte. */
+ offs += intvl / 8;
+
+ /* If we have gone past the end of buffer, stop. */
+ if (offs >= offset_in_block + count) break;
+
+ /* If the current offs lies within the buffer, corrupt a bit. */
+ if (offs >= offset_in_block) {
+ i = offs - offset_in_block;
+ assert (i < count);
+ buf[i] = corrupt_one_bit (buf[i], intvl & 7, rand, ct);
+ }
+ }
+}
+
+/* Read data. */
+static int
+evil_pread (nbdkit_next *next,
+ void *handle, void *buf, uint32_t count, uint64_t offset,
+ uint32_t flags, int *err)
+{
+ uint64_t seed, bstart, len;
+ struct random_state local_state;
+
+ if (next->pread (next, buf, count, offset, flags, err) == -1)
+ return -1;
+
+ switch (evil_mode) {
+ case COSMIC_RAYS:
+ /* Use the global random state because we want to flip bits at random. */
+ corrupt_buffer (buf, count, 0, &state, FLIP);
+ break;
+
+ case STUCK_BITS:
+ /* Split the request to align with blocks. */
+ bstart = offset & ~(block_size-1);
+ while (count > 0) {
+ /* Set the seed so we corrupt the same bits relative to the offset. */
+ seed = (int64_t) evil_seed + bstart;
+ xsrandom (seed, &local_state);
+ /* If the buffer straddles two blocks, shorten to just the part
+ * inside the first block.
+ */
+ len = MIN (count, bstart + block_size - offset);
+ corrupt_buffer (buf, len, offset - bstart, &local_state, STUCK);
+ bstart += block_size;
+ offset += len;
+ buf += len;
+ count -= len;
+ }
+ break;
+
+ case STUCK_WIRES:
+ /* Set the seed so we corrupt the same bits in every request. */
+ seed = (int64_t) evil_seed;
+ xsrandom (seed, &local_state);
+ corrupt_buffer (buf, count, 0, &local_state, STUCK);
+ break;
+ }
+
+ return 0;
+}
+
+static struct nbdkit_filter filter = {
+ .name = "evil",
+ .longname = "nbdkit evil filter",
+ .load = evil_load,
+ .config = evil_config,
+ .config_complete = evil_config_complete,
+ .config_help = evil_config_help,
+ .thread_model = evil_thread_model,
+ .get_ready = evil_get_ready,
+ .pread = evil_pread,
+};
+
+NBDKIT_REGISTER_FILTER (filter)
diff --git a/tests/test-evil-cosmic.sh b/tests/test-evil-cosmic.sh
new file mode 100755
index 000000000..00f09ac7a
--- /dev/null
+++ b/tests/test-evil-cosmic.sh
@@ -0,0 +1,76 @@
+#!/usr/bin/env bash
+# nbdkit
+# Copyright Red Hat
+#
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions are
+# met:
+#
+# * Redistributions of source code must retain the above copyright
+# notice, this list of conditions and the following disclaimer.
+#
+# * Redistributions in binary form must reproduce the above copyright
+# notice, this list of conditions and the following disclaimer in the
+# documentation and/or other materials provided with the distribution.
+#
+# * Neither the name of Red Hat nor the names of its contributors may be
+# used to endorse or promote products derived from this software without
+# specific prior written permission.
+#
+# THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS
IS'' AND
+# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+# THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+# PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR
+# CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+# USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+# SUCH DAMAGE.
+
+# Test evil filter with cosmic rays.
+
+source ./functions.sh
+set -e
+set -x
+
+requires_plugin null
+requires_filter evil
+requires_filter noextents
+requires nbdcopy --version
+
+# Make sure these are the coreutils versions to avoid surprises.
+requires od --version
+requires sort --version
+requires uniq --version
+
+f="test-evil-cosmic.out"
+rm -f $f
+cleanup_fn rm -f $f
+
+# 80 million zero bits in the backing disk, and the filter will
+# randomly flip (ie. set high) 1 in 800,000 bits, or about 100.
+
+# XXX Actually the number of set bits clusters around 80. There could
+# be a mistake in my calculations or the interval algorithm we use
+# might be biased.
+
+export f
+nbdkit -U - null 10000000 \
+ --filter=evil --filter=noextents \
+ evil=cosmic-rays evil-probability=1/800000 \
+ --run 'nbdcopy "$uri" $f'
+
+# This will give an approximate count of the number of set bits.
+
+zbytes="$( od -A n -w1 -v -t x1 < $f | sort | uniq -c |
+ $SED -n -E -e 's/([0-9]+)[[:space:]]+00[[:space:]]*$/\1/p'
)"
+nzbits=$(( 10000000 - zbytes )); # looks wrong but actually correct ...
+
+if [ $nzbits -lt 20 ] || [ $nzbits -gt 180 ]; then
+ echo "ERROR: $0: unexpected number of non-zero bits: $nzbits"
+ echo " (expecting about 100)"
+ exit 1
+fi
diff --git a/tests/test-evil-stuck-high-bits.sh
b/tests/test-evil-stuck-high-bits.sh
new file mode 100755
index 000000000..8f6db2ea0
--- /dev/null
+++ b/tests/test-evil-stuck-high-bits.sh
@@ -0,0 +1,86 @@
+#!/usr/bin/env bash
+# nbdkit
+# Copyright Red Hat
+#
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions are
+# met:
+#
+# * Redistributions of source code must retain the above copyright
+# notice, this list of conditions and the following disclaimer.
+#
+# * Redistributions in binary form must reproduce the above copyright
+# notice, this list of conditions and the following disclaimer in the
+# documentation and/or other materials provided with the distribution.
+#
+# * Neither the name of Red Hat nor the names of its contributors may be
+# used to endorse or promote products derived from this software without
+# specific prior written permission.
+#
+# THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS
IS'' AND
+# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+# THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+# PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR
+# CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+# USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+# SUCH DAMAGE.
+
+# Test evil filter in the default mode ("stuck-bits").
+
+source ./functions.sh
+set -e
+set -x
+
+requires_plugin null
+requires_filter evil
+requires_filter noextents
+requires_nbdsh_uri
+
+sock=$(mktemp -u /tmp/nbdkit-test-sock.XXXXXX)
+pidfile=evil-stuck-high-bits.pid
+files="$sock $pidfile"
+rm -f $files
+cleanup_fn rm -f $files
+
+# Run nbdkit with the evil filter.
+start_nbdkit -P $pidfile -U $sock \
+ --filter=evil --filter=noextents \
+ null 1G evil-probability=1/800000
+
+# Since 1 in 800,000 bits are stuck (on average), for every 100,000
+# bytes that we read we expect about 1 stuck bit. Note however that
+# bits are stuck randomly low or high, and against the null filter you
+# cannot see a stuck low bit, so in fact we expect to see only 1 stuck
+# bit per 200,000 bytes.
+#
+# There is a separate test for stuck low bits (test-evil-stuck-low-bits.sh).
+#
+# Also stuck bits should be consistent across reads.
+
+nbdsh -u "nbd+unix://?socket=$sock" \
+ -c - <<EOF
+def count_bits(buf):
+ r = 0
+ for i in range(0, len(buf)-1):
+ if buf[i] != 0:
+ r += bin(buf[i]).count("1")
+ return r
+
+# Expect about 50 stuck-high bits.
+buf = h.pread(10000000, 0)
+bits = count_bits(buf)
+print("stuck high bits: %d (expected 50)" % bits)
+assert(bits > 20 and bits < 80)
+
+# If we read subsets they should match the contents of the buffer.
+buf1 = h.pread(1000, 1000)
+assert(buf1 == buf[1000:2000])
+
+buf1 = h.pread(10000, 999)
+assert(buf1 == buf[999:10999])
+EOF
diff --git a/tests/test-evil-stuck-low-bits.sh
b/tests/test-evil-stuck-low-bits.sh
new file mode 100755
index 000000000..3b0a48af7
--- /dev/null
+++ b/tests/test-evil-stuck-low-bits.sh
@@ -0,0 +1,79 @@
+#!/usr/bin/env bash
+# nbdkit
+# Copyright Red Hat
+#
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions are
+# met:
+#
+# * Redistributions of source code must retain the above copyright
+# notice, this list of conditions and the following disclaimer.
+#
+# * Redistributions in binary form must reproduce the above copyright
+# notice, this list of conditions and the following disclaimer in the
+# documentation and/or other materials provided with the distribution.
+#
+# * Neither the name of Red Hat nor the names of its contributors may be
+# used to endorse or promote products derived from this software without
+# specific prior written permission.
+#
+# THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS
IS'' AND
+# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+# THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+# PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR
+# CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+# USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+# SUCH DAMAGE.
+
+# Test evil filter in the default mode ("stuck-bits").
+
+source ./functions.sh
+set -e
+set -x
+
+requires_plugin ones
+requires_filter evil
+requires_nbdsh_uri
+
+sock=$(mktemp -u /tmp/nbdkit-test-sock.XXXXXX)
+pidfile=evil-stuck-low-bits.pid
+files="$sock $pidfile"
+rm -f $files
+cleanup_fn rm -f $files
+
+# Run nbdkit with the evil filter.
+start_nbdkit -P $pidfile -U $sock \
+ --filter=evil \
+ ones 1G evil-probability=1/800000
+
+# See description in test-evil-stuck-high-bits.sh. This test uses the
+# ones plugin to test for stuck low bits. The other parameters are
+# the same.
+
+nbdsh -u "nbd+unix://?socket=$sock" \
+ -c - <<EOF
+def count_bits(buf):
+ r = 0
+ for i in range(0, len(buf)-1):
+ if buf[i] != 0xff:
+ r += 8 - bin(buf[i]).count("1")
+ return r
+
+# Expect about 50 stuck-low bits.
+buf = h.pread(10000000, 32*1024*1024)
+bits = count_bits(buf)
+print("stuck low bits: %d (expected 50)" % bits)
+assert(bits > 20 and bits < 80)
+
+# If we read subsets they should match the contents of the buffer.
+buf1 = h.pread(1000, 32*1024*1024 + 1000)
+assert(buf1 == buf[1000:2000])
+
+buf1 = h.pread(10000, 32*1024*1024 + 999)
+assert(buf1 == buf[999:10999])
+EOF
diff --git a/tests/test-evil-stuck-wires.sh b/tests/test-evil-stuck-wires.sh
new file mode 100755
index 000000000..c79a009fc
--- /dev/null
+++ b/tests/test-evil-stuck-wires.sh
@@ -0,0 +1,85 @@
+#!/usr/bin/env bash
+# nbdkit
+# Copyright Red Hat
+#
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions are
+# met:
+#
+# * Redistributions of source code must retain the above copyright
+# notice, this list of conditions and the following disclaimer.
+#
+# * Redistributions in binary form must reproduce the above copyright
+# notice, this list of conditions and the following disclaimer in the
+# documentation and/or other materials provided with the distribution.
+#
+# * Neither the name of Red Hat nor the names of its contributors may be
+# used to endorse or promote products derived from this software without
+# specific prior written permission.
+#
+# THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS
IS'' AND
+# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+# THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+# PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR
+# CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+# USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+# SUCH DAMAGE.
+
+# Test evil filter in stuck-wires mode.
+
+source ./functions.sh
+set -e
+set -x
+
+requires_plugin null
+requires_filter evil
+requires_filter noextents
+requires_nbdsh_uri
+
+sock=$(mktemp -u /tmp/nbdkit-test-sock.XXXXXX)
+pidfile=evil-stuck-wires.pid
+files="$sock $pidfile"
+rm -f $files
+cleanup_fn rm -f $files
+
+# Run nbdkit with the evil filter.
+start_nbdkit -P $pidfile -U $sock \
+ --filter=evil --filter=noextents \
+ null 1G evil=stuck-wires evil-probability=1/10000
+
+# Reads from the filter should have 1:10,000 bits stuck high or low.
+# However we don't see stuck low bits are we are always reading
+# zeroes, so we only expect about 1:20,000 bits stuck high.
+#
+# If we read 10,000,000 bytes (80,000,000 bits) we would expect about
+# 4000 stuck bits.
+#
+# No matter where we read from the pattern of stuck bits should be the
+# same (stuck wires, not backing bits).
+
+nbdsh -u "nbd+unix://?socket=$sock" \
+ -c - <<EOF
+def count_bits(buf):
+ r = 0
+ for i in range(0, len(buf)-1):
+ if buf[i] != 0:
+ r += bin(buf[i]).count("1")
+ return r
+
+buf1 = h.pread(10000000, 0)
+bits = count_bits(buf1)
+print("stuck high bits: %d (expected 4000)" % bits)
+assert(bits > 3000 and bits < 5000)
+
+# These buffers should be identical.
+buf2 = h.pread(10000000, 1024)
+buf3 = h.pread(10000000, 32*1024*1024 - 9999)
+assert(buf1 == buf2)
+assert(buf1 == buf3)
+
+EOF
--
2.39.2
On Tue, May 16, 2023 at 01:12:19PM +0100, Richard W.M. Jones wrote:> > This filter adds random data corruption when reading from the > underlying plugin. > --- > filters/error/nbdkit-error-filter.pod | 4 + > filters/evil/nbdkit-evil-filter.pod | 159 ++++++++++++ > configure.ac | 2 + > filters/evil/Makefile.am | 77 ++++++ > tests/Makefile.am | 14 + > filters/evil/evil.c | 353 ++++++++++++++++++++++++++ > tests/test-evil-cosmic.sh | 76 ++++++ > tests/test-evil-stuck-high-bits.sh | 86 +++++++ > tests/test-evil-stuck-low-bits.sh | 79 ++++++ > tests/test-evil-stuck-wires.sh | 85 +++++++ > 10 files changed, 935 insertions(+)Interesting idea. Might also be interesting to see how this filter behaves with qemu's quorum device (that is, feed two or more copies of the same block source, one or both through nbdkit's evil filter, into qemu's quorum to see if those corruptions are flagged).> +++ b/filters/evil/nbdkit-evil-filter.pod > @@ -0,0 +1,159 @@ > +=head1 NAME > + > +nbdkit-evil-filter - add random data corruption to reads > + > +=head1 SYNOPSIS > + > + nbdkit --filter=evil PLUGIN [PLUGIN-ARGS...] > + evil=[cosmic-rays|stuck-bits|stuck-wires] > + [evil-probability=PROB] [evil-stuck-probability=PROB] > + [evil-seed=SEED] > + > +=head1 DESCRIPTION > + > +nbdkit-evil-filter is a Byzantine filter for L<nbdkit(1)> that > +randomly corrupts data when reading from the underlying plugin. This > +can be used for testing filesystem checksums. Note that it does not > +change write operations, so the underlying plugin contains the correct > +data.That's actually a cool description for something so evil!> + > +=head2 Extents > + > +Plugins can be sparse. This filter only corrupts bits in non-sparse > +parts of the backing disk and it leaves sparse regions unchanged > +(which is realistic behaviour). If you wish to use this filter to > +corrupt sparse regions, then combine this filter with > +L<nbdkit-noextents-filter(1)>. For example: > + > + nbdkit --filter=evil --filter=noextents memory 1GMakes sense in that the sparse portions of a file don't read from the underlying storage and therefore don't get the stuck read effects (assuming the metadata itself was not also corrupted by stuck bits when determining where the sparse portions of the file were). Of course, the more physically realistic we make the filter, the more complicated it gets.> +++ b/filters/evil/evil.c> + > +static int > +evil_config (nbdkit_next_config *next, nbdkit_backend *nxdata, > + const char *key, const char *value) > +{ > + if (strcmp (key, "evil") == 0 || strcmp (key, "evil-mode") == 0) { > + if (strcmp (value, "cosmic-rays") == 0 || > + strcmp (value, "cosmic") == 0) {Do we want strcasecmp on these? Do we want to allow _ as a synonym to -?> + evil_mode = COSMIC_RAYS; > + return 0; > + } > + else if (strcmp (value, "stuck-bits") == 0 || > + strcmp (value, "stuck-bit") == 0 || > + strcmp (value, "stuck") == 0) { > + evil_mode = STUCK_BITS; > + return 0; > + } > + else if (strcmp (value, "stuck-wires") == 0 || > + strcmp (value, "stuck-wire") == 0) { > + evil_mode = STUCK_WIRES; > + return 0; > + } > + else { > + nbdkit_error ("evil: unknown mode: %s", value); > + return -1; > + } > + } > + else if (strcmp (key, "evil-probability") == 0) { > + if (nbdkit_parse_probability ("evil-probability", value, > + &evil_probability) == -1) > + return -1; > + if (evil_probability < 0 || evil_probability > 1) { > + nbdkit_error ("%s: probability out of range, should be [0..1]", key);Do we want to explicitly support 0 for control purposes (no errors, but testing the effect of the filter as a passthrough)? Right now, you permit the probability...> + > +/* This is the heart of the algorithm, the function which corrupts > + * the buffer after reading it from the plugin. > + * > + * The observation is that if we have a block of (eg) size 10^6 bits > + * and our probability of finding a corrupt bit is (eg) 1/10^4, then > + * we expect approximately 100 bits in the block to be corrupted. > + * > + * For stuck bits we want the corrupted bits to be the same on each > + * access, either relative to the backing disk (STUCK_BITS) or to the > + * request (STUCK_WIRES). > + * > + * Instead of creating an expensive bitmap ahead of time covering the > + * whole disk, we can use the random number generator with a fixed > + * seed derived from the offset of the start of the block. We can > + * then choose a random number uniformly in the range [0..2*(1/P)] (in > + * the example [0..2*10^4]) as the distance to the next corrupt bit.Is '**' the intended operator in these two comments (exponentiation, rather than multiplication)? [1]> + * We jump forwards, corrupt that bit, and repeat until we reach > + * the end of the block....but 2**(1/0) is either going to result in infinity or NaN,...> + * > + * "Corrupted" in this case can mean flipped by cosmic rays or stuck, > + * depending on the filter mode. > + * > + * On average this will choose the right number of bits in the block. > + * (Although their distribution will be suboptimal. In a uniform > + * distribution it should be possible for two corrupted bits to be > + * greater than 2*(1/P) apart, but the above algorithm would not do > + * this. In practice this probably doesn't matter.) > + * > + * Note that "block" != "buffer", especially in the STUCK_BITS mode. > + * We iterate over blocks as above, but only corrupt a bit when it > + * happens to coincide with the buffer we have just read. > + * > + * We choose the block size adaptively so that at least 100 bits in > + * the block will be corrupted. The block size must be a power of 2. > + * The block size thus depends on the probability. > + */ > +enum corruption_type { FLIP, STUCK }; > + > +static uint64_t block_size; /* in bytes */ > +static struct random_state state; /* only used for cosmic-rays */ > + > +static int > +evil_thread_model (void) > +{ > + switch (evil_mode) { > + case COSMIC_RAYS: > + /* Because cosmic-rays uses the global random state we need to > + * tighten the thread model. > + */ > + return NBDKIT_THREAD_MODEL_SERIALIZE_REQUESTS; > + > + case STUCK_BITS: > + case STUCK_WIRES: > + return NBDKIT_THREAD_MODEL_PARALLEL; > + } > + abort (); > +} > + > +static int > +evil_get_ready (int thread_model) > +{ > + switch (evil_mode) { > + case COSMIC_RAYS: > + xsrandom ((uint64_t) evil_seed, &state); > + break; > + > + case STUCK_BITS: > + case STUCK_WIRES: > + ; > + } > + > + /* Choose the block size based on the probability, so that at least > + * 100 bits are expected to be corrupted in the block. Block size > + * must be a power of 2. > + */ > + block_size = next_power_of_2 ((uint64_t) (100. / evil_probability));...and I'm worried that your block_size computation reaches a point where it does not do what we want if the probably gets too close to zero. Even if it is not division by zero, division by a subnormal float can easily produce overflow to infinity, which converts to UINT64_MAX, and next_power_of_2(UINT64_MAX) was untested in patch 3's unit tests, but appears like it will be '1 << (64 - 64)' == 1, which isn't really desirable.> + > + return 0; > +} > + > +static uint8_t > +corrupt_one_bit (uint8_t byte, unsigned bit, > + uint64_t rand, enum corruption_type ct) > +{ > + const unsigned mask = 1 << bit; > + > + switch (ct) { > + case FLIP: > + byte ^= mask; > + break; > + case STUCK: > + rand &= 0xffffffff; > + if (evil_stuck_probability * 0x100000000 > rand) { > + if (rand & 1) /* stuck high or low? */ > + byte |= mask; > + else > + byte &= ~mask; > + } > + } > + return byte; > +} > + > +static void > +corrupt_buffer (uint8_t *buf, uint32_t count, uint64_t offset_in_block, > + struct random_state *rs, enum corruption_type ct) > +{ > + if (evil_probability == 0) > + /* No corruption, and avoids a divide by zero below. */ > + return;Okay, you are trying to avoid division by zero elsewhere, but this avoidance may occur too late after get_ready has already settled on a block size.> + > + uint64_t offs, intvl, i, rand; > + const uint64_t dinvp = (uint64_t) (2.0 * (1.0 / evil_probability));[1] Ah, I see - you did mean multiplication, not exponentiation. Like you commented elsewhere, it is not quite a true uniform distribution, but certainly seems sane enough for the intent.> + > + assert ((offset_in_block & ~(block_size-1)) == 0); > + > + /* Iterate over the whole block from the start. */ > + for (offs = 0; offs < offset_in_block + count; ) { > + /* Choose the length of the interval to the next corrupted bit, by > + * picking a random number in [0..2*(1/P)]. > + * > + * Remember this is in bits! > + */ > + intvl = xrandom (rs) % dinvp; > + > + /* Consume one more random state. We may or may not use this. > + * But we need to always consume two random states per iteration > + * to make the output predictable. > + */ > + rand = xrandom (rs); > + > + /* Adjust offs to that byte. */ > + offs += intvl / 8; > + > + /* If we have gone past the end of buffer, stop. */ > + if (offs >= offset_in_block + count) break; > + > + /* If the current offs lies within the buffer, corrupt a bit. */ > + if (offs >= offset_in_block) { > + i = offs - offset_in_block; > + assert (i < count); > + buf[i] = corrupt_one_bit (buf[i], intvl & 7, rand, ct); > + } > + } > +} > + > +/* Read data. */ > +static int > +evil_pread (nbdkit_next *next, > + void *handle, void *buf, uint32_t count, uint64_t offset, > + uint32_t flags, int *err) > +{ > + uint64_t seed, bstart, len; > + struct random_state local_state; > + > + if (next->pread (next, buf, count, offset, flags, err) == -1) > + return -1; > + > + switch (evil_mode) { > + case COSMIC_RAYS: > + /* Use the global random state because we want to flip bits at random. */ > + corrupt_buffer (buf, count, 0, &state, FLIP); > + break; > + > + case STUCK_BITS: > + /* Split the request to align with blocks. */ > + bstart = offset & ~(block_size-1); > + while (count > 0) { > + /* Set the seed so we corrupt the same bits relative to the offset. */ > + seed = (int64_t) evil_seed + bstart; > + xsrandom (seed, &local_state); > + /* If the buffer straddles two blocks, shorten to just the part > + * inside the first block. > + */ > + len = MIN (count, bstart + block_size - offset); > + corrupt_buffer (buf, len, offset - bstart, &local_state, STUCK); > + bstart += block_size; > + offset += len; > + buf += len; > + count -= len; > + } > + break; > + > + case STUCK_WIRES: > + /* Set the seed so we corrupt the same bits in every request. */ > + seed = (int64_t) evil_seed; > + xsrandom (seed, &local_state); > + corrupt_buffer (buf, count, 0, &local_state, STUCK); > + break; > + }Thanks to the ability to set a fixed seed, you can write unit tests that the different bit corruption behaviors are indeed repeatable regardless of client access size or offset.> +++ b/tests/test-evil-cosmic.sh> + > +f="test-evil-cosmic.out" > +rm -f $f > +cleanup_fn rm -f $f > + > +# 80 million zero bits in the backing disk, and the filter will > +# randomly flip (ie. set high) 1 in 800,000 bits, or about 100. > + > +# XXX Actually the number of set bits clusters around 80. There could > +# be a mistake in my calculations or the interval algorithm we use > +# might be biased.I have not closely inspected the math yet to see if there's an obvious bias (treat this as a first-pass quick review looking for obvious code/shell bugs, as opposed to more insidious deep analysis bugs). But that comment does mean we probably ought to double-check things prior to v2.> + > +export f > +nbdkit -U - null 10000000 \ > + --filter=evil --filter=noextents \ > + evil=cosmic-rays evil-probability=1/800000 \ > + --run 'nbdcopy "$uri" $f' > + > +# This will give an approximate count of the number of set bits. > + > +zbytes="$( od -A n -w1 -v -t x1 < $f | sort | uniq -c | > + $SED -n -E -e 's/([0-9]+)[[:space:]]+00[[:space:]]*$/\1/p' )" > +nzbits=$(( 10000000 - zbytes )); # looks wrong but actually correct ...Interesting computation!> + > +if [ $nzbits -lt 20 ] || [ $nzbits -gt 180 ]; then > + echo "ERROR: $0: unexpected number of non-zero bits: $nzbits" > + echo " (expecting about 100)" > + exit 1 > +fiAnd seems like a safe enough fudge factor that we are unlikely to get false negative CI runs.> diff --git a/tests/test-evil-stuck-high-bits.sh b/tests/test-evil-stuck-high-bits.sh > new file mode 100755 > index 000000000..8f6db2ea0 > --- /dev/null > +++ b/tests/test-evil-stuck-high-bits.sh > @@ -0,0 +1,86 @@> +# Run nbdkit with the evil filter. > +start_nbdkit -P $pidfile -U $sock \ > + --filter=evil --filter=noextents \ > + null 1G evil-probability=1/800000 > + > +# Since 1 in 800,000 bits are stuck (on average), for every 100,000 > +# bytes that we read we expect about 1 stuck bit. Note however that > +# bits are stuck randomly low or high, and against the null filter you > +# cannot see a stuck low bit, so in fact we expect to see only 1 stuck > +# bit per 200,000 bytes. > +# > +# There is a separate test for stuck low bits (test-evil-stuck-low-bits.sh). > +# > +# Also stuck bits should be consistent across reads. > + > +nbdsh -u "nbd+unix://?socket=$sock" \ > + -c - <<EOF > +def count_bits(buf): > + r = 0 > + for i in range(0, len(buf)-1): > + if buf[i] != 0: > + r += bin(buf[i]).count("1") > + return rInteresting change to count by embedded python instead of shell code.> + > +# Expect about 50 stuck-high bits. > +buf = h.pread(10000000, 0) > +bits = count_bits(buf) > +print("stuck high bits: %d (expected 50)" % bits) > +assert(bits > 20 and bits < 80) > + > +# If we read subsets they should match the contents of the buffer. > +buf1 = h.pread(1000, 1000) > +assert(buf1 == buf[1000:2000]) > + > +buf1 = h.pread(10000, 999) > +assert(buf1 == buf[999:10999])Should we also assert that there is at least one stuck bit in those two ranges, and/or pick a different or larger range to improve the chances of that being the case?> +++ b/tests/test-evil-stuck-wires.sh> + > +# Run nbdkit with the evil filter. > +start_nbdkit -P $pidfile -U $sock \ > + --filter=evil --filter=noextents \ > + null 1G evil=stuck-wires evil-probability=1/10000 > + > +# Reads from the filter should have 1:10,000 bits stuck high or low. > +# However we don't see stuck low bits are we are always readings/are we are/since we are/> +# zeroes, so we only expect about 1:20,000 bits stuck high. > +# > +# If we read 10,000,000 bytes (80,000,000 bits) we would expect about > +# 4000 stuck bits. > +# > +# No matter where we read from the pattern of stuck bits should be the > +# same (stuck wires, not backing bits). > + > +nbdsh -u "nbd+unix://?socket=$sock" \ > + -c - <<EOF > +def count_bits(buf): > + r = 0 > + for i in range(0, len(buf)-1): > + if buf[i] != 0: > + r += bin(buf[i]).count("1") > + return r > + > +buf1 = h.pread(10000000, 0) > +bits = count_bits(buf1) > +print("stuck high bits: %d (expected 4000)" % bits) > +assert(bits > 3000 and bits < 5000) > + > +# These buffers should be identical. > +buf2 = h.pread(10000000, 1024) > +buf3 = h.pread(10000000, 32*1024*1024 - 9999) > +assert(buf1 == buf2) > +assert(buf1 == buf3) > +Overall looks like an interesting idea for a filter. -- Eric Blake, Principal Software Engineer Red Hat, Inc. +1-919-301-3266 Virtualization: qemu.org | libvirt.org
On 5/16/23 14:12, Richard W.M. Jones wrote:> +/* This is the heart of the algorithm, the function which corrupts > + * the buffer after reading it from the plugin. > + * > + * The observation is that if we have a block of (eg) size 10^6 bits > + * and our probability of finding a corrupt bit is (eg) 1/10^4, then > + * we expect approximately 100 bits in the block to be corrupted.This is a binomial distribution (in the example, n=10^6, p=10^(-4)): https://en.wikipedia.org/wiki/Binomial_distribution The expected value is E = n*p = 10^2, so the comment looks correct in that regard. There is a different interpretation for "we expect" as well. Namely, the "mode" -- the most probable outcome, the number of corrupted bits we're most probably going to see. That's a different concept <https://en.wikipedia.org/wiki/Mode_(statistics)>. However, per the WP article, for the binomial distribution, it is essentially the same. Namely, the WP article says, for this distribution, the mode M (an integer) is given uniquely by (n + 1) * p - 1 <= M < (n + 1) * p [1] if ((n + 1) * p) is *not* an integer, and the M1 and M2 (equally probable, integer) modes M1 = (n + 1) * p [2] M2 = (n + 1) * p - 1 [3] if ((n + 1) * p) *is* an integer. Now,if we distribute the multiplications over the addends (break the parens open), we get: n * p + p - 1 <= M < n * p + p [1] M1 = n * p + p [2] M2 = n * p + p - 1 [3] But for the binomial distribution, E = n * p, so we can substitute (also rewriting +(p-1) as -(1-p) in [1]): E - (1 - p) <= M < E + p [1] M1 = E + p [2] M2 = E + p - 1 [3] Using the values from the code comment: n = 1,000,000 p = 0.000,1 E = n * p = 100 (n + 1) * p = 100.000,1 --> not an integer, so [1] applies: E - (1 - p) <= M < E + p [1] 99.000,1 <= M < 100.000,1 Therefore the mode M is 100 -- it equals the expected value E, for the particular "n" and "p" values! In general, they need not be equal. (For example, the mode(s) are always integers, but E need not be:if we change n to 1,000,001 then E is 100.0001, which is clearly impossible to interpret as a number of corrupted bits. It's effectively an average, but never directly produced by the distribution as a value.) Either way, my point is that M, M1 and M2 (from [1], [2], [3]) are very close to E in the general case too, so the "we expect" language applies even when we interpret it as "mode", not as "expected value".> + * > + * For stuck bits we want the corrupted bits to be the same on each > + * access, either relative to the backing disk (STUCK_BITS) or to the > + * request (STUCK_WIRES). > + * > + * Instead of creating an expensive bitmap ahead of time covering the > + * whole disk, we can use the random number generator with a fixed > + * seed derived from the offset of the start of the block. We can > + * then choose a random number uniformly in the range [0..2*(1/P)] (in > + * the example [0..2*10^4]) as the distance to the next corrupt bit. > + * We jump forwards, corrupt that bit, and repeat until we reach > + * the end of the block.Two points: (1) I figure the idea is that the "average distance" will be 1/p bits -- the expected value being (0 + 2*(1/p))/2 == 1/p -- so we expect this "average distance" to fit n/(1/p) = n*p times in the block size. This looks sane, but I'm unequipped to make any arguments about "expected value". According to wikipedia, this is the Irwin-Hall distribution <https://en.wikipedia.org/wiki/Irwin%E2%80%93Hall_distribution>: "the sum of a number of independent random variables, each having a uniform distribution". The individual random variables need to follow continuous (not discrete) uniform distributions though, so I don't know if Irwin-Hall "applies" here at all. Wikipedia says that, as "n" increases -- that is, as we sample our underlying uniform U(0, 1) distribution more and more times, and add up the results --, the distribution of the sum (= the Irwin-Hall distribution) approximates a Normal distribution, with both the epxected value and the mode being (s/2), where "s" is the number of samples (variables) summed. I don't know what happens if we scale the underlying U(0, 1) distribution's domain by 2/p, so that it becomes U(0, 2/p). I guess we'd *hope* that the expected value of the sum scales similarly, to: E = s/2 * 2/p = s/p Because in that case, we coul wish for the expected value (and mode) of the sum of the jumps to match our block size, that is: E = s/p = n or put differently, s = n*p Meaning that we'd expect having to sum as many "samples", i.e. having to take as many "jumps", in the average case, as n*p is (= 100 jumps with our numbers). But this is entirely hand-waving; I don't know if this holds up at all! (2) I think the interval as written is off-by-one. The left hand side (0) should indeed be inclusive, but the RHS 2*(1/p) should be *excluded*. We're supposed to have 20,000 integers in the set, from 0 to 19,999 inclusive.> + * > + * "Corrupted" in this case can mean flipped by cosmic rays or stuck, > + * depending on the filter mode. > + * > + * On average this will choose the right number of bits in the block. > + * (Although their distribution will be suboptimal. In a uniform > + * distribution it should be possible for two corrupted bits to be > + * greater than 2*(1/P) apart, but the above algorithm would not do > + * this. In practice this probably doesn't matter.) > + * > + * Note that "block" != "buffer", especially in the STUCK_BITS mode. > + * We iterate over blocks as above, but only corrupt a bit when it > + * happens to coincide with the buffer we have just read. > + * > + * We choose the block size adaptively so that at least 100 bits in > + * the block will be corrupted. The block size must be a power of 2. > + * The block size thus depends on the probability. > + */ > +enum corruption_type { FLIP, STUCK }; > + > +static uint64_t block_size; /* in bytes */ > +static struct random_state state; /* only used for cosmic-rays */ > + > +static int > +evil_thread_model (void) > +{ > + switch (evil_mode) { > + case COSMIC_RAYS: > + /* Because cosmic-rays uses the global random state we need to > + * tighten the thread model. > + */ > + return NBDKIT_THREAD_MODEL_SERIALIZE_REQUESTS; > + > + case STUCK_BITS: > + case STUCK_WIRES: > + return NBDKIT_THREAD_MODEL_PARALLEL; > + } > + abort (); > +} > + > +static int > +evil_get_ready (int thread_model) > +{ > + switch (evil_mode) { > + case COSMIC_RAYS: > + xsrandom ((uint64_t) evil_seed, &state); > + break; > + > + case STUCK_BITS: > + case STUCK_WIRES: > + ; > + } > + > + /* Choose the block size based on the probability, so that at least > + * 100 bits are expected to be corrupted in the block. Block size > + * must be a power of 2. > + */ > + block_size = next_power_of_2 ((uint64_t) (100. / evil_probability)); > + > + return 0; > +} > + > +static uint8_t > +corrupt_one_bit (uint8_t byte, unsigned bit, > + uint64_t rand, enum corruption_type ct) > +{ > + const unsigned mask = 1 << bit; > + > + switch (ct) { > + case FLIP: > + byte ^= mask; > + break; > + case STUCK: > + rand &= 0xffffffff; > + if (evil_stuck_probability * 0x100000000 > rand) { > + if (rand & 1) /* stuck high or low? */ > + byte |= mask; > + else > + byte &= ~mask; > + } > + } > + return byte; > +} > + > +static void > +corrupt_buffer (uint8_t *buf, uint32_t count, uint64_t offset_in_block, > + struct random_state *rs, enum corruption_type ct) > +{ > + if (evil_probability == 0) > + /* No corruption, and avoids a divide by zero below. */ > + return; > + > + uint64_t offs, intvl, i, rand; > + const uint64_t dinvp = (uint64_t) (2.0 * (1.0 / evil_probability)); > + > + assert ((offset_in_block & ~(block_size-1)) == 0); > + > + /* Iterate over the whole block from the start. */ > + for (offs = 0; offs < offset_in_block + count; ) { > + /* Choose the length of the interval to the next corrupted bit, by > + * picking a random number in [0..2*(1/P)]. > + * > + * Remember this is in bits! > + */ > + intvl = xrandom (rs) % dinvp; > + > + /* Consume one more random state. We may or may not use this. > + * But we need to always consume two random states per iteration > + * to make the output predictable. > + */ > + rand = xrandom (rs); > + > + /* Adjust offs to that byte. */ > + offs += intvl / 8; > + > + /* If we have gone past the end of buffer, stop. */ > + if (offs >= offset_in_block + count) break; > + > + /* If the current offs lies within the buffer, corrupt a bit. */ > + if (offs >= offset_in_block) { > + i = offs - offset_in_block; > + assert (i < count); > + buf[i] = corrupt_one_bit (buf[i], intvl & 7, rand, ct); > + } > + } > +} > + > +/* Read data. */ > +static int > +evil_pread (nbdkit_next *next, > + void *handle, void *buf, uint32_t count, uint64_t offset, > + uint32_t flags, int *err) > +{ > + uint64_t seed, bstart, len; > + struct random_state local_state; > + > + if (next->pread (next, buf, count, offset, flags, err) == -1) > + return -1; > + > + switch (evil_mode) { > + case COSMIC_RAYS: > + /* Use the global random state because we want to flip bits at random. */ > + corrupt_buffer (buf, count, 0, &state, FLIP); > + break; > + > + case STUCK_BITS: > + /* Split the request to align with blocks. */ > + bstart = offset & ~(block_size-1); > + while (count > 0) { > + /* Set the seed so we corrupt the same bits relative to the offset. */ > + seed = (int64_t) evil_seed + bstart; > + xsrandom (seed, &local_state); > + /* If the buffer straddles two blocks, shorten to just the part > + * inside the first block. > + */ > + len = MIN (count, bstart + block_size - offset); > + corrupt_buffer (buf, len, offset - bstart, &local_state, STUCK); > + bstart += block_size; > + offset += len; > + buf += len; > + count -= len; > + } > + break; > + > + case STUCK_WIRES: > + /* Set the seed so we corrupt the same bits in every request. */ > + seed = (int64_t) evil_seed; > + xsrandom (seed, &local_state); > + corrupt_buffer (buf, count, 0, &local_state, STUCK); > + break; > + } > + > + return 0; > +} > + > +static struct nbdkit_filter filter = { > + .name = "evil", > + .longname = "nbdkit evil filter", > + .load = evil_load, > + .config = evil_config, > + .config_complete = evil_config_complete, > + .config_help = evil_config_help, > + .thread_model = evil_thread_model, > + .get_ready = evil_get_ready, > + .pread = evil_pread, > +}; > + > +NBDKIT_REGISTER_FILTER (filter) > diff --git a/tests/test-evil-cosmic.sh b/tests/test-evil-cosmic.sh > new file mode 100755 > index 000000000..00f09ac7a > --- /dev/null > +++ b/tests/test-evil-cosmic.sh > @@ -0,0 +1,76 @@ > +#!/usr/bin/env bash > +# nbdkit > +# Copyright Red Hat > +# > +# Redistribution and use in source and binary forms, with or without > +# modification, are permitted provided that the following conditions are > +# met: > +# > +# * Redistributions of source code must retain the above copyright > +# notice, this list of conditions and the following disclaimer. > +# > +# * Redistributions in binary form must reproduce the above copyright > +# notice, this list of conditions and the following disclaimer in the > +# documentation and/or other materials provided with the distribution. > +# > +# * Neither the name of Red Hat nor the names of its contributors may be > +# used to endorse or promote products derived from this software without > +# specific prior written permission. > +# > +# THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS IS'' AND > +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, > +# THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A > +# PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR > +# CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, > +# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT > +# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF > +# USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND > +# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, > +# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT > +# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF > +# SUCH DAMAGE. > + > +# Test evil filter with cosmic rays. > + > +source ./functions.sh > +set -e > +set -x > + > +requires_plugin null > +requires_filter evil > +requires_filter noextents > +requires nbdcopy --version > + > +# Make sure these are the coreutils versions to avoid surprises. > +requires od --version > +requires sort --version > +requires uniq --version > + > +f="test-evil-cosmic.out" > +rm -f $f > +cleanup_fn rm -f $f > + > +# 80 million zero bits in the backing disk, and the filter will > +# randomly flip (ie. set high) 1 in 800,000 bits, or about 100. > + > +# XXX Actually the number of set bits clusters around 80. There could > +# be a mistake in my calculations or the interval algorithm we use > +# might be biased. > + > +export f > +nbdkit -U - null 10000000 \ > + --filter=evil --filter=noextents \ > + evil=cosmic-rays evil-probability=1/800000 \ > + --run 'nbdcopy "$uri" $f' > + > +# This will give an approximate count of the number of set bits. > + > +zbytes="$( od -A n -w1 -v -t x1 < $f | sort | uniq -c | > + $SED -n -E -e 's/([0-9]+)[[:space:]]+00[[:space:]]*$/\1/p' )" > +nzbits=$(( 10000000 - zbytes )); # looks wrong but actually correct ...Some explanation on this would be nice. Laszlo> + > +if [ $nzbits -lt 20 ] || [ $nzbits -gt 180 ]; then > + echo "ERROR: $0: unexpected number of non-zero bits: $nzbits" > + echo " (expecting about 100)" > + exit 1 > +fi > diff --git a/tests/test-evil-stuck-high-bits.sh b/tests/test-evil-stuck-high-bits.sh > new file mode 100755 > index 000000000..8f6db2ea0 > --- /dev/null > +++ b/tests/test-evil-stuck-high-bits.sh > @@ -0,0 +1,86 @@ > +#!/usr/bin/env bash > +# nbdkit > +# Copyright Red Hat > +# > +# Redistribution and use in source and binary forms, with or without > +# modification, are permitted provided that the following conditions are > +# met: > +# > +# * Redistributions of source code must retain the above copyright > +# notice, this list of conditions and the following disclaimer. > +# > +# * Redistributions in binary form must reproduce the above copyright > +# notice, this list of conditions and the following disclaimer in the > +# documentation and/or other materials provided with the distribution. > +# > +# * Neither the name of Red Hat nor the names of its contributors may be > +# used to endorse or promote products derived from this software without > +# specific prior written permission. > +# > +# THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS IS'' AND > +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, > +# THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A > +# PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR > +# CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, > +# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT > +# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF > +# USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND > +# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, > +# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT > +# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF > +# SUCH DAMAGE. > + > +# Test evil filter in the default mode ("stuck-bits"). > + > +source ./functions.sh > +set -e > +set -x > + > +requires_plugin null > +requires_filter evil > +requires_filter noextents > +requires_nbdsh_uri > + > +sock=$(mktemp -u /tmp/nbdkit-test-sock.XXXXXX) > +pidfile=evil-stuck-high-bits.pid > +files="$sock $pidfile" > +rm -f $files > +cleanup_fn rm -f $files > + > +# Run nbdkit with the evil filter. > +start_nbdkit -P $pidfile -U $sock \ > + --filter=evil --filter=noextents \ > + null 1G evil-probability=1/800000 > + > +# Since 1 in 800,000 bits are stuck (on average), for every 100,000 > +# bytes that we read we expect about 1 stuck bit. Note however that > +# bits are stuck randomly low or high, and against the null filter you > +# cannot see a stuck low bit, so in fact we expect to see only 1 stuck > +# bit per 200,000 bytes. > +# > +# There is a separate test for stuck low bits (test-evil-stuck-low-bits.sh). > +# > +# Also stuck bits should be consistent across reads. > + > +nbdsh -u "nbd+unix://?socket=$sock" \ > + -c - <<EOF > +def count_bits(buf): > + r = 0 > + for i in range(0, len(buf)-1): > + if buf[i] != 0: > + r += bin(buf[i]).count("1") > + return r > + > +# Expect about 50 stuck-high bits. > +buf = h.pread(10000000, 0) > +bits = count_bits(buf) > +print("stuck high bits: %d (expected 50)" % bits) > +assert(bits > 20 and bits < 80) > + > +# If we read subsets they should match the contents of the buffer. > +buf1 = h.pread(1000, 1000) > +assert(buf1 == buf[1000:2000]) > + > +buf1 = h.pread(10000, 999) > +assert(buf1 == buf[999:10999]) > +EOF > diff --git a/tests/test-evil-stuck-low-bits.sh b/tests/test-evil-stuck-low-bits.sh > new file mode 100755 > index 000000000..3b0a48af7 > --- /dev/null > +++ b/tests/test-evil-stuck-low-bits.sh > @@ -0,0 +1,79 @@ > +#!/usr/bin/env bash > +# nbdkit > +# Copyright Red Hat > +# > +# Redistribution and use in source and binary forms, with or without > +# modification, are permitted provided that the following conditions are > +# met: > +# > +# * Redistributions of source code must retain the above copyright > +# notice, this list of conditions and the following disclaimer. > +# > +# * Redistributions in binary form must reproduce the above copyright > +# notice, this list of conditions and the following disclaimer in the > +# documentation and/or other materials provided with the distribution. > +# > +# * Neither the name of Red Hat nor the names of its contributors may be > +# used to endorse or promote products derived from this software without > +# specific prior written permission. > +# > +# THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS IS'' AND > +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, > +# THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A > +# PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR > +# CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, > +# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT > +# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF > +# USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND > +# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, > +# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT > +# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF > +# SUCH DAMAGE. > + > +# Test evil filter in the default mode ("stuck-bits"). > + > +source ./functions.sh > +set -e > +set -x > + > +requires_plugin ones > +requires_filter evil > +requires_nbdsh_uri > + > +sock=$(mktemp -u /tmp/nbdkit-test-sock.XXXXXX) > +pidfile=evil-stuck-low-bits.pid > +files="$sock $pidfile" > +rm -f $files > +cleanup_fn rm -f $files > + > +# Run nbdkit with the evil filter. > +start_nbdkit -P $pidfile -U $sock \ > + --filter=evil \ > + ones 1G evil-probability=1/800000 > + > +# See description in test-evil-stuck-high-bits.sh. This test uses the > +# ones plugin to test for stuck low bits. The other parameters are > +# the same. > + > +nbdsh -u "nbd+unix://?socket=$sock" \ > + -c - <<EOF > +def count_bits(buf): > + r = 0 > + for i in range(0, len(buf)-1): > + if buf[i] != 0xff: > + r += 8 - bin(buf[i]).count("1") > + return r > + > +# Expect about 50 stuck-low bits. > +buf = h.pread(10000000, 32*1024*1024) > +bits = count_bits(buf) > +print("stuck low bits: %d (expected 50)" % bits) > +assert(bits > 20 and bits < 80) > + > +# If we read subsets they should match the contents of the buffer. > +buf1 = h.pread(1000, 32*1024*1024 + 1000) > +assert(buf1 == buf[1000:2000]) > + > +buf1 = h.pread(10000, 32*1024*1024 + 999) > +assert(buf1 == buf[999:10999]) > +EOF > diff --git a/tests/test-evil-stuck-wires.sh b/tests/test-evil-stuck-wires.sh > new file mode 100755 > index 000000000..c79a009fc > --- /dev/null > +++ b/tests/test-evil-stuck-wires.sh > @@ -0,0 +1,85 @@ > +#!/usr/bin/env bash > +# nbdkit > +# Copyright Red Hat > +# > +# Redistribution and use in source and binary forms, with or without > +# modification, are permitted provided that the following conditions are > +# met: > +# > +# * Redistributions of source code must retain the above copyright > +# notice, this list of conditions and the following disclaimer. > +# > +# * Redistributions in binary form must reproduce the above copyright > +# notice, this list of conditions and the following disclaimer in the > +# documentation and/or other materials provided with the distribution. > +# > +# * Neither the name of Red Hat nor the names of its contributors may be > +# used to endorse or promote products derived from this software without > +# specific prior written permission. > +# > +# THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS IS'' AND > +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, > +# THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A > +# PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR > +# CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, > +# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT > +# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF > +# USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND > +# ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, > +# OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT > +# OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF > +# SUCH DAMAGE. > + > +# Test evil filter in stuck-wires mode. > + > +source ./functions.sh > +set -e > +set -x > + > +requires_plugin null > +requires_filter evil > +requires_filter noextents > +requires_nbdsh_uri > + > +sock=$(mktemp -u /tmp/nbdkit-test-sock.XXXXXX) > +pidfile=evil-stuck-wires.pid > +files="$sock $pidfile" > +rm -f $files > +cleanup_fn rm -f $files > + > +# Run nbdkit with the evil filter. > +start_nbdkit -P $pidfile -U $sock \ > + --filter=evil --filter=noextents \ > + null 1G evil=stuck-wires evil-probability=1/10000 > + > +# Reads from the filter should have 1:10,000 bits stuck high or low. > +# However we don't see stuck low bits are we are always reading > +# zeroes, so we only expect about 1:20,000 bits stuck high. > +# > +# If we read 10,000,000 bytes (80,000,000 bits) we would expect about > +# 4000 stuck bits. > +# > +# No matter where we read from the pattern of stuck bits should be the > +# same (stuck wires, not backing bits). > + > +nbdsh -u "nbd+unix://?socket=$sock" \ > + -c - <<EOF > +def count_bits(buf): > + r = 0 > + for i in range(0, len(buf)-1): > + if buf[i] != 0: > + r += bin(buf[i]).count("1") > + return r > + > +buf1 = h.pread(10000000, 0) > +bits = count_bits(buf1) > +print("stuck high bits: %d (expected 4000)" % bits) > +assert(bits > 3000 and bits < 5000) > + > +# These buffers should be identical. > +buf2 = h.pread(10000000, 1024) > +buf3 = h.pread(10000000, 32*1024*1024 - 9999) > +assert(buf1 == buf2) > +assert(buf1 == buf3) > + > +EOF
On Wed, May 17, 2023 at 03:28:11PM +0200, Laszlo Ersek wrote:> On 5/16/23 14:12, Richard W.M. Jones wrote: > > > +/* This is the heart of the algorithm, the function which corrupts > > + * the buffer after reading it from the plugin. > > + * > > + * The observation is that if we have a block of (eg) size 10^6 bits > > + * and our probability of finding a corrupt bit is (eg) 1/10^4, then > > + * we expect approximately 100 bits in the block to be corrupted. > > This is a binomial distribution (in the example, n=10^6, p=10^(-4)): > > https://en.wikipedia.org/wiki/Binomial_distribution > > The expected value is E = n*p = 10^2, so the comment looks correct in > that regard. > > There is a different interpretation for "we expect" as well. Namely, the > "mode" -- the most probable outcome, the number of corrupted bits we're > most probably going to see. That's a different concept > <https://en.wikipedia.org/wiki/Mode_(statistics)>. However, per the WP > article, for the binomial distribution, it is essentially the same. > > Namely, the WP article says, for this distribution, the mode M (an > integer) is given uniquely by > > (n + 1) * p - 1 <= M < (n + 1) * p [1] > > if ((n + 1) * p) is *not* an integer, and the M1 and M2 (equally > probable, integer) modes > > M1 = (n + 1) * p [2] > M2 = (n + 1) * p - 1 [3] > > if ((n + 1) * p) *is* an integer. > > Now,if we distribute the multiplications over the addends (break the > parens open), we get: > > n * p + p - 1 <= M < n * p + p [1] > M1 = n * p + p [2] > M2 = n * p + p - 1 [3] > > But for the binomial distribution, E = n * p, so we can substitute (also > rewriting +(p-1) as -(1-p) in [1]): > > E - (1 - p) <= M < E + p [1] > M1 = E + p [2] > M2 = E + p - 1 [3] > > Using the values from the code comment: > > n = 1,000,000 > p = 0.000,1 > E = n * p = 100 > > (n + 1) * p = 100.000,1 --> not an integer, so [1] applies: > > E - (1 - p) <= M < E + p [1] > 99.000,1 <= M < 100.000,1 > > Therefore the mode M is 100 -- it equals the expected value E, for the > particular "n" and "p" values! > > In general, they need not be equal. (For example, the mode(s) are always > integers, but E need not be:if we change n to 1,000,001 then E is > 100.0001, which is clearly impossible to interpret as a number of > corrupted bits. It's effectively an average, but never directly produced > by the distribution as a value.) > > Either way, my point is that M, M1 and M2 (from [1], [2], [3]) are very > close to E in the general case too, so the "we expect" language applies > even when we interpret it as "mode", not as "expected value". > > > + * > > + * For stuck bits we want the corrupted bits to be the same on each > > + * access, either relative to the backing disk (STUCK_BITS) or to the > > + * request (STUCK_WIRES). > > + * > > + * Instead of creating an expensive bitmap ahead of time covering the > > + * whole disk, we can use the random number generator with a fixed > > + * seed derived from the offset of the start of the block. We can > > + * then choose a random number uniformly in the range [0..2*(1/P)] (in > > + * the example [0..2*10^4]) as the distance to the next corrupt bit. > > + * We jump forwards, corrupt that bit, and repeat until we reach > > + * the end of the block. > > Two points: > > (1) I figure the idea is that the "average distance" will be 1/p bits -- > the expected value being (0 + 2*(1/p))/2 == 1/p -- so we expect this > "average distance" to fit n/(1/p) = n*p times in the block size. > > This looks sane, but I'm unequipped to make any arguments about > "expected value". > > According to wikipedia, this is the Irwin-Hall distribution > <https://en.wikipedia.org/wiki/Irwin%E2%80%93Hall_distribution>: "the > sum of a number of independent random variables, each having a uniform > distribution". The individual random variables need to follow continuous > (not discrete) uniform distributions though, so I don't know if > Irwin-Hall "applies" here at all. > > Wikipedia says that, as "n" increases -- that is, as we sample our > underlying uniform U(0, 1) distribution more and more times, and add up > the results --, the distribution of the sum (= the Irwin-Hall > distribution) approximates a Normal distribution, with both the epxected > value and the mode being (s/2), where "s" is the number of samples > (variables) summed. > > I don't know what happens if we scale the underlying U(0, 1) > distribution's domain by 2/p, so that it becomes U(0, 2/p). I guess we'd > *hope* that the expected value of the sum scales similarly, to: > > E = s/2 * 2/p = s/p > > Because in that case, we coul wish for the expected value (and mode) of > the sum of the jumps to match our block size, that is: > > E = s/p = n > > or put differently, > > s = n*p > > Meaning that we'd expect having to sum as many "samples", i.e. having to > take as many "jumps", in the average case, as n*p is (= 100 jumps with > our numbers). > > But this is entirely hand-waving; I don't know if this holds up at all!Yes I don't think the bit picking method I chose gets the right distribution exactly. However it has the advantage of being (a) reproducible without needing to store any state except for the small random number generator state, and (b) easy enough to implement.> (2) I think the interval as written is off-by-one. The left hand side > (0) should indeed be inclusive, but the RHS 2*(1/p) should be > *excluded*. We're supposed to have 20,000 integers in the set, from 0 to > 19,999 inclusive.This is actually what we use - I'll update the comment.> > +# This will give an approximate count of the number of set bits. > > + > > +zbytes="$( od -A n -w1 -v -t x1 < $f | sort | uniq -c | > > + $SED -n -E -e 's/([0-9]+)[[:space:]]+00[[:space:]]*$/\1/p' )" > > +nzbits=$(( 10000000 - zbytes )); # looks wrong but actually correct ... > > Some explanation on this would be nice.In v2 I killed this completely and use some Python code instead. (That didn't fix the bias I was observing in this test, and nor did adding lots of debugging, so I still don't understand that.) Rich. -- Richard Jones, Virtualization Group, Red Hat http://people.redhat.com/~rjones Read my programming and virtualization blog: http://rwmj.wordpress.com virt-top is 'top' for virtual machines. Tiny program with many powerful monitoring features, net stats, disk stats, logging, etc. http://people.redhat.com/~rjones/virt-top