Repository: tahoe-lafs/zfec (language: python)

Issue:
zfec.Decoder.decode segfaults for k == m == 256
Reproducer:

```
import zfec
k = m = 256
blocks = [b''] * k
nums = list(range(k))
decer = zfec.Decoder(k, m)
print("Decoding")
decer.decode(blocks, nums)
print("Decoded")
```

Results:

```
❯ python repro.py 
Decoding
Segmentation fault (core dumped)
```

stack trace:

```
Program received signal SIGSEGV, Segmentation fault.
0x00007ffff775a1cd in __memmove_avx_unaligned_erms () from /nix/store/7fz6dhhriwv6n4kdg05qi8cwf7mfqza9-glibc-2.35-163/lib/libc.so.6
(gdb) bt
#0  0x00007ffff775a1cd in __memmove_avx_unaligned_erms () from /nix/store/7fz6dhhriwv6n4kdg05qi8cwf7mfqza9-glibc-2.35-163/lib/libc.so.6
#1  0x00007ffff7e1a392 in memcpy (__len=256, __src=<optimized out>, __dest=<optimized out>)
    at /nix/store/4pqv2mwdn88h7xvsm7a5zplrd8sxzvw0-glibc-2.35-163-dev/include/bits/string_fortified.h:29
#2  build_decode_matrix_into_space (code=0x4f0910, index=0x7fffffff52e0, k=256, matrix=0x7ffffffe4240 "\001") at zfec/fec.c:521
#3  0x00007ffff7e1abce in fec_decode (code=0x4f0910, inpkts=0x0, outpkts=0x0, index=0x7fffffff52e0, sz=0) at zfec/fec.c:533
#4  0x0000000000000000 in ?? ()
```

Apparent source line in `fec.c`:

```
memcpy(p, &(code->enc_matrix[index[i] * code->k]), k);
```

* `k == 256`
* `*code == {magic = 4271885820, k = 256, n = 256, enc_matrix = 0x53c010 "\001"}`
* `i ==92`
* `index[i] == 65536`



Discussion / hints:
`enc_matrix` should have `k * n == 65536` elements (as allocated by `NEW_GF_MATRIX` in `fec_new`).  `index[i] * code->k` is `16777216` which is impossibly far beyond the end the allocated space for `enc_matrix`, which it is used to index.

Since `code->k` is effectively constant I suppose that `index[i]` has been mis-computed at some point.

valgrind confirms this invalid read:

```
==1535306== Invalid read of size 8                                                       
==1535306==    at 0x484FDED: memmove (in /nix/store/zxw3x6cmhpw4x09lhb2aim3zkynr9mld-valgrind-3.19.0/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)                          
==1535306==    by 0x13062391: memcpy (string_fortified.h:29)                                                                                                                      
==1535306==    by 0x13062391: build_decode_matrix_into_space (fec.c:521)                 
==1535306==    by 0x13062BCD: fec_decode (fec.c:533)         
==1535306==  Address 0x12f81370 is 0 bytes after a block of size 65,536 alloc'd                                                                                                   
==1535306==    at 0x484679B: malloc (in /nix/store/zxw3x6cmhpw4x09lhb2aim3zkynr9mld-valgrind-3.19.0/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==1535306==    by 0x13061E99: fec_new (fec.c:449)                                                                                                                                 
==1535306==    by 0x130603E1: Decoder_init (_fecmodule.c:363)                                                                                                                     
==1535306==    by 0x4977AD6: type_call (in /nix/store/rc9cz7z4qlgmsbwvpw2acig5g2rdws46-python3-3.10.5/lib/libpython3.10.so.1.0)                                                   
==1535306==    by 0x4914363: _PyObject_MakeTpCall (in /nix/store/rc9cz7z4qlgmsbwvpw2acig5g2rdws46-python3-3.10.5/lib/libpython3.10.so.1.0)                                        
==1535306==    by 0x48C7509: _PyEval_EvalFrameDefault (in /nix/store/rc9cz7z4qlgmsbwvpw2acig5g2rdws46-python3-3.10.5/lib/libpython3.10.so.1.0)                                    
==1535306==    by 0x4A4205E: _PyEval_Vector (in /nix/store/rc9cz7z4qlgmsbwvpw2acig5g2rdws46-python3-3.10.5/lib/libpython3.10.so.1.0)                                              
==1535306==    by 0x4A426C7: PyEval_EvalCode (in /nix/store/rc9cz7z4qlgmsbwvpw2acig5g2rdws46-python3-3.10.5/lib/libpython3.10.so.1.0)                                             
==1535306==    by 0x4AC6D8C: run_mod (in /nix/store/rc9cz7z4qlgmsbwvpw2acig5g2rdws46-python3-3.10.5/lib/libpython3.10.so.1.0)                                                     
==1535306==    by 0x4AD3741: _PyRun_SimpleFileObject (in /nix/store/rc9cz7z4qlgmsbwvpw2acig5g2rdws46-python3-3.10.5/lib/libpython3.10.so.1.0)                                     
==1535306==    by 0x4AD3D1A: _PyRun_AnyFileObject (in /nix/store/rc9cz7z4qlgmsbwvpw2acig5g2rdws46-python3-3.10.5/lib/libpython3.10.so.1.0)                                        
==1535306==    by 0x4AD7EDE: Py_RunMain (in /nix/store/rc9cz7z4qlgmsbwvpw2acig5g2rdws46-python3-3.10.5/lib/libpython3.10.so.1.0)                                                  
```

and the idea that `enc_matrix` is 65536 bytes long.

Huh, `index` is a _parameter_ to `fec_decode` - not a value computed in `fec.c`.  So these values seem to come from the Python bindings.

The Python code computes `index` correctly as far as I can tell, though.

The loop variable `i` in `build_decode_matrix_into_space` is `unsigned char`.  `k` is `unsigned [int]`.  The loop condition is `i < k` which will never be false for `k == 256`.  The loop runs and runs until it incorrectly overwrites some memory that leads to the corruption of `index`.

Fix patch:
diff --git a/changelog b/changelog
index 9801c562..a357d89a 100644
--- a/changelog
+++ b/changelog
@@ -1,3 +1,6 @@
+Wed Sep 20 10:35:00 EST 2023 exarkun@twistedmatrix.com
+  * zfec: fix incorrect results, memory corruption, and a sometimes-crash when decoding with k = n = 256.
+
 Tue Jan 25 13:45:00 EST 2022 exarkun@twistedmatrix.com
   * zfec: setup: remove support for python < 3.7
 
diff --git a/setup.py b/setup.py
index 35233659..27695b66 100644
--- a/setup.py
+++ b/setup.py
@@ -58,7 +58,7 @@
     url="https://github.com/tahoe-lafs/zfec",
     extras_require={
         "bench": ["pyutil >= 3.0.0"],
-        "test": ["twisted", "pyutil >= 3.0.0"],
+        "test": ["twisted", "pyutil >= 3.0.0", "hypothesis"],
     },
     ext_modules=extensions,
     cmdclass=versioneer.get_cmdclass(),
diff --git a/zfec/fec.c b/zfec/fec.c
index 310a038b..993f22a1 100644
--- a/zfec/fec.c
+++ b/zfec/fec.c
@@ -511,7 +511,7 @@ fec_encode(const fec_t* code, const gf*restrict const*restrict const src, gf*res
  */
 void
 build_decode_matrix_into_space(const fec_t*restrict const code, const unsigned*const restrict index, const unsigned k, gf*restrict const matrix) {
-    unsigned char i;
+    unsigned short i;
     gf* p;
     for (i=0, p=matrix; i < k; i++, p += k) {
         if (index[i] < k) {
@@ -527,9 +527,22 @@ build_decode_matrix_into_space(const fec_t*restrict const code, const unsigned*c
 void
 fec_decode(const fec_t* code, const gf*restrict const*restrict const inpkts, gf*restrict const*restrict const outpkts, const unsigned*restrict const index, size_t sz) {
     gf* m_dec = (gf*)alloca(code->k * code->k);
+
+    /* char is large enough for outix - it counts the number of primary blocks
+       we are decoding for return.  the most primary blocks we might have to
+       decode is for k == 128, m == 256.  in this case we might be given 128
+       secondary blocks and have to decode 128 primary blocks.  if k decreases
+       then the number of total blocks we might have to return decreases.  if
+       k increases then the number of secondary blocks that exist decreases so
+       we will be passed some primary blocks and the number of primary blocks
+       we have to decode decreases. */
     unsigned char outix=0;
-    unsigned char row=0;
-    unsigned char col=0;
+
+    /* row and col are compared directly to k, which could be 256, so make
+       them large enough to represent 256.
+     */
+    unsigned short row=0;
+    unsigned short col=0;
     build_decode_matrix_into_space(code, index, code->k, m_dec);
 
     for (row=0; row<code->k; row++) {


Test patch:
diff --git a/zfec/test/test_zfec.py b/zfec/test/test_zfec.py
index 6653c64b..f8b3e922 100755
--- a/zfec/test/test_zfec.py
+++ b/zfec/test/test_zfec.py
@@ -10,6 +10,8 @@
     from io import BytesIO
 
 import unittest
+from hypothesis import given
+from hypothesis.strategies import integers, binary, lists, just
 
 global VERBOSE
 VERBOSE=False
@@ -52,12 +54,6 @@ def _help_test_random():
     ss = [ randstr(l//k) for x in range(k) ]
     _h(k, m, ss)
 
-def _help_test_random_with_l(l):
-    m = random.randrange(1, 257)
-    k = random.randrange(1, m+1)
-    ss = [ randstr(l//k) for x in range(k) ]
-    _h(k, m, ss)
-
 def _h_easy(k, m, s):
     encer = zfec.easyfec.Encoder(k, m)
     nums_and_blocks = list(enumerate(encer.encode(s)))
@@ -127,11 +123,35 @@ def test_from_agl_py(self):
         # print "after decoding:"
         # print "b0: %s, b1: %s" % tuple(base64.b16encode(x) for x in [b0, b1])
 
-    def test_small(self):
-        for i in range(16):
-            _help_test_random_with_l(i)
-        if VERBOSE:
-            print("%d randomized tests pass." % (i+1))
+    @given(
+        integers(min_value=0, max_value=15).flatmap(
+            lambda l:
+            integers(min_value=1, max_value=256).flatmap(
+                lambda m:
+                integers(min_value=1, max_value=m).flatmap(
+                    lambda k:
+                    lists(
+                        binary(min_size=l//k, max_size=l//k),
+                        min_size=k,
+                        max_size=k,
+                    ).flatmap(
+                        lambda ss: just((k, m, ss)),
+                    ),
+                ),
+            ),
+        ),
+    )
+    def test_small(self, kmss):
+        """
+        Short primary blocks (length between 0 and 15) round-trip through
+        Encoder / Decoder for all values of k, m, such that:
+
+          * 1 <= m <= 256
+          * 1 <= k <= m
+
+        """
+        (k, m, ss) = kmss
+        _h(k, m, ss)
 
     def test_random(self):
         for i in range(3):