election-methods@mailman.electorama.com

Technical discussion of election methods

View all threads

Schulze STV bugs

KM
Kristofer Munsterhjelm
Fri, Jun 19, 2026 12:29 PM

Here are the bugs I found in prog01.c, Schulze's 2007 implementation of
Schulze STV:

  1. Undefined behavior due to sequence ordering:

This is the big one. In line 818 of prog01.c, we have

Value2[i2]=Value2[i2]++;

This is undefined, because (as far as I understand it) Value[i2] is
being altered twice: once by the assignment and once by the
postdecrement, but the C standard doesn't specify in what order this
should happen. Presumably the MSVC compiler Schulze used interpreted
this as incrementing Value2[i2]. Modern compilers do something else, and
this breaks the implementation, producing erroneous election outcomes.
To fix, replace the line with

Value2[i2]++;

This bug can be exercised by the A68.dat election: the intended Schulze
STV outcome is ACD, but if the code behaves incorrectly, it'll return
ABC instead.

  1. The Test3 array is in some cases too small, leading to out-of-bounds
    writes.

The following example election exercises the bug:

M 10
C 13
N 1
F 2

BEGIN
1 A B C D E F G
END

The allocation statement at fault is

Test3    =(int                *)calloc(N2+1          ,sizeof(int                ));

Apparently N2+1 is too small. I don't know what the proper allocation
size is, though.

  1. The n-choose-k function over(n, k) doesn't recognize overflow, and
    internally overflows in some cases even when n choose k is well within
    integer bounds.

Thus with enough candidates, over() overflows and returns a negative
value, which leads to a crash in malloc. This is kinda theoretical
because even with the bug fixed, such instances will usually be too
large to practically count anyway. However, one may note that over() can
also overflow on say, over(30, 29), even if 30 choose 29 is not itself
very large.

The following election exercises this bug:

M 29
C 30
N 1
F 2

BEGIN
1 A
END

Even with the bug fixed, prog01 gets stuck on this example: something
inside the proportional completion function is taking a very long time.
But I don't know if it's a bug or an unavoidable consequence of the
algorithm itself.

-km

Here are the bugs I found in prog01.c, Schulze's 2007 implementation of Schulze STV: 1. Undefined behavior due to sequence ordering: This is the big one. In line 818 of prog01.c, we have > Value2[i2]=Value2[i2]++; This is undefined, because (as far as I understand it) Value[i2] is being altered twice: once by the assignment and once by the postdecrement, but the C standard doesn't specify in what order this should happen. Presumably the MSVC compiler Schulze used interpreted this as incrementing Value2[i2]. Modern compilers do something else, and this breaks the implementation, producing erroneous election outcomes. To fix, replace the line with > Value2[i2]++; This bug can be exercised by the A68.dat election: the intended Schulze STV outcome is ACD, but if the code behaves incorrectly, it'll return ABC instead. 2. The Test3 array is in some cases too small, leading to out-of-bounds writes. The following example election exercises the bug: > M 10 > C 13 > N 1 > F 2 > > BEGIN > 1 A B C D E F G > END The allocation statement at fault is > Test3 =(int *)calloc(N2+1 ,sizeof(int )); Apparently N2+1 is too small. I don't know what the proper allocation size is, though. 3. The n-choose-k function over(n, k) doesn't recognize overflow, and internally overflows in some cases even when n choose k is well within integer bounds. Thus with enough candidates, over() overflows and returns a negative value, which leads to a crash in malloc. This is kinda theoretical because even with the bug fixed, such instances will usually be too large to practically count anyway. However, one may note that over() can also overflow on say, over(30, 29), even if 30 choose 29 is not itself very large. The following election exercises this bug: > M 29 > C 30 > N 1 > F 2 > > BEGIN > 1 A > END Even with the bug fixed, prog01 gets stuck on this example: something inside the proportional completion function is taking a very long time. But I don't know if it's a bug or an unavoidable consequence of the algorithm itself. -km