FA-90166 / Bytecode virtual machines / Open access
LEB128 immediates: signed values never sign-extend · case 01
Negative signed immediates decode as large positive numbers.
ROOT CAUSE
Sign extension tests the continuation bit of the last byte, which is always clear.
VERIFIED REPAIR
Extend using bit 0x40 of the final byte.
Unsuccessful approach: Testing the type's top bit only works for maximum-length encodings.
Case contract
Decode consecutive LEB128 immediates of kinds u32, s32, u64, s64 from a byte list: 7 payload bits per byte, least significant group first, bit 0x80 means another byte follows; at most ceil(bits/7) bytes (5 for 32-bit, 10 for 64-bit). Signed kinds sign-extend from bit 0x40 of the final byte; u32/s32 values outside their range are errors. Return decoded values followed by the first error, if any: ["unexpected-end", pos], ["too-long", pos] or ["out-of-range", pos].
Why this case matters
Compact bytecode formats encode immediates with LEB128; decoding errors silently change operands.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(data, kinds):
pos = 0
out = []
for kind in kinds:
bits = 32 if kind in ('u32', 's32') else 64
maxlen = (bits + 6) // 7
result = 0
shift = 0
n = 0
while True:
if pos >= len(data):
return out + [['unexpected-end', pos]]
byte = data[pos]
pos += 1
n += 1
result |= (byte & 0x7F) << shift
shift += 7
if (byte & 0x80) == 0:
break
if n == maxlen:
return out + [['too-long', pos]]
if kind[0] == 's' and byte & 0x80:
result -= 1 << shift
if kind == 's32' and not -(1 << 31) <= result < (1 << 31):
return out + [['out-of-range', pos]]
if kind == 'u32' and result >= (1 << 32):
return out + [['out-of-range', pos]]
out.append(result)
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: mixed immediates', ([237, 7, 179, 127, 127], ['u32', 's32', 's64']), [1005, -77, -1]),
('single byte 0x7F', ([127, 127], ['u32', 's32']), [127, -1]),
('five-byte u32 is the maximum length', ([128, 128, 128, 128, 1], ['u32']), [268435456]),
('six-byte u32 is too long', ([128, 128, 128, 128, 128, 0, 1], ['u32', 'u32']), [['too-long', 5]]),
('s32 2^31 out of range, -2^31 in range',
([128, 128, 128, 128, 120, 128, 128, 128, 128, 8], ['s32', 's32']),
[-2147483648, ['out-of-range', 10]]),
('u32 with bit 6 set in last byte stays positive', ([65, 128, 64], ['u32', 'u32']), [65, 8192]),
('negative s64 spanning several bytes', ([255, 255, 255, 255, 255, 95], ['s64']), [-1099511627777]),
('truncated immediate', ([128, 129], ['u64']), [['unexpected-end', 2]])],
[('regression: mixed immediates', ([213, 15, 230, 126, 127], ['u32', 's32', 's64']), [2005, -154, -1]),
('single byte 0x7F', ([127, 127], ['u32', 's32']), [127, -1]),
('five-byte u32 is the maximum length', ([128, 128, 128, 128, 2], ['u32']), [536870912]),
('six-byte u32 is too long', ([128, 128, 128, 128, 128, 0, 2], ['u32', 'u32']), [['too-long', 5]]),
('s32 2^31 out of range, -2^31 in range',
([128, 128, 128, 128, 120, 128, 128, 128, 128, 8], ['s32', 's32']),
[-2147483648, ['out-of-range', 10]]),
('u32 with bit 6 set in last byte stays positive', ([66, 128, 64], ['u32', 'u32']), [66, 8192]),
('negative s64 spanning several bytes', ([254, 255, 255, 255, 255, 95], ['s64']), [-1099511627778]),
('truncated immediate', ([128, 130], ['u64']), [['unexpected-end', 2]])],
[('regression: mixed immediates', ([189, 23, 153, 126, 127], ['u32', 's32', 's64']), [3005, -231, -1]),
('single byte 0x7F', ([127, 127], ['u32', 's32']), [127, -1]),
('five-byte u32 is the maximum length', ([128, 128, 128, 128, 3], ['u32']), [805306368]),
('six-byte u32 is too long', ([128, 128, 128, 128, 128, 0, 3], ['u32', 'u32']), [['too-long', 5]]),
('s32 2^31 out of range, -2^31 in range',
([128, 128, 128, 128, 120, 128, 128, 128, 128, 8], ['s32', 's32']),
[-2147483648, ['out-of-range', 10]]),
('u32 with bit 6 set in last byte stays positive', ([67, 128, 64], ['u32', 'u32']), [67, 8192]),
('negative s64 spanning several bytes', ([253, 255, 255, 255, 255, 95], ['s64']), [-1099511627779]),
('truncated immediate', ([128, 131], ['u64']), [['unexpected-end', 2]])],
[('regression: mixed immediates', ([165, 31, 204, 125, 127], ['u32', 's32', 's64']), [4005, -308, -1]),
('single byte 0x7F', ([127, 127], ['u32', 's32']), [127, -1]),
('five-byte u32 is the maximum length', ([128, 128, 128, 128, 4], ['u32']), [1073741824]),
('six-byte u32 is too long', ([128, 128, 128, 128, 128, 0, 4], ['u32', 'u32']), [['too-long', 5]]),
('s32 2^31 out of range, -2^31 in range',
([128, 128, 128, 128, 120, 128, 128, 128, 128, 8], ['s32', 's32']),
[-2147483648, ['out-of-range', 10]]),
('u32 with bit 6 set in last byte stays positive', ([68, 128, 64], ['u32', 'u32']), [68, 8192]),
('negative s64 spanning several bytes', ([252, 255, 255, 255, 255, 95], ['s64']), [-1099511627780]),
('truncated immediate', ([128, 132], ['u64']), [['unexpected-end', 2]])],
[('regression: mixed immediates', ([141, 39, 255, 124, 127], ['u32', 's32', 's64']), [5005, -385, -1]),
('single byte 0x7F', ([127, 127], ['u32', 's32']), [127, -1]),
('five-byte u32 is the maximum length', ([128, 128, 128, 128, 5], ['u32']), [1342177280]),
('six-byte u32 is too long', ([128, 128, 128, 128, 128, 0, 5], ['u32', 'u32']), [['too-long', 5]]),
('s32 2^31 out of range, -2^31 in range',
([128, 128, 128, 128, 120, 128, 128, 128, 128, 8], ['s32', 's32']),
[-2147483648, ['out-of-range', 10]]),
('u32 with bit 6 set in last byte stays positive', ([69, 128, 64], ['u32', 'u32']), [69, 8192]),
('negative s64 spanning several bytes', ([251, 255, 255, 255, 255, 95], ['s64']), [-1099511627781]),
('truncated immediate', ([128, 133], ['u64']), [['unexpected-end', 2]])]]
for label, args, expected in cases[N - 1]:
check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression: mixed immediates | [1005, 16307, 127] | [1005, -77, -1] | Failed |
| single byte 0x7F | [127, 127] | [127, -1] | Failed |
| five-byte u32 is the maximum length | [268435456] | [268435456] | Passed |
| six-byte u32 is too long | [['too-long', 5]] | [['too-long', 5]] | Passed |
| s32 2^31 out of range, -2^31 in range | [['out-of-range', 5]] | [-2147483648, ['out-of-range', 10]] | Failed |
| u32 with bit 6 set in last byte stays positive | [65, 8192] | [65, 8192] | Passed |
| negative s64 spanning several bytes | [3298534883327] | [-1099511627777] | Failed |
| truncated immediate | [['unexpected-end', 2]] | [['unexpected-end', 2]] | Passed |
SHA-256 / b20494653338248f1b6ee1bc0e18350a19f02056aa99a95e937691beff2adf54
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(data, kinds):
pos = 0
out = []
for kind in kinds:
bits = 32 if kind in ('u32', 's32') else 64
maxlen = (bits + 6) // 7
result = 0
shift = 0
n = 0
while True:
if pos >= len(data):
return out + [['unexpected-end', pos]]
byte = data[pos]
pos += 1
n += 1
result |= (byte & 0x7F) << shift
shift += 7
if (byte & 0x80) == 0:
break
if n == maxlen:
return out + [['too-long', pos]]
if kind[0] == 's' and result & (1 << (bits - 1)):
result -= 1 << shift
if kind == 's32' and not -(1 << 31) <= result < (1 << 31):
return out + [['out-of-range', pos]]
if kind == 'u32' and result >= (1 << 32):
return out + [['out-of-range', pos]]
out.append(result)
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: mixed immediates', ([237, 7, 179, 127, 127], ['u32', 's32', 's64']), [1005, -77, -1]),
('single byte 0x7F', ([127, 127], ['u32', 's32']), [127, -1]),
('five-byte u32 is the maximum length', ([128, 128, 128, 128, 1], ['u32']), [268435456]),
('six-byte u32 is too long', ([128, 128, 128, 128, 128, 0, 1], ['u32', 'u32']), [['too-long', 5]]),
('s32 2^31 out of range, -2^31 in range',
([128, 128, 128, 128, 120, 128, 128, 128, 128, 8], ['s32', 's32']),
[-2147483648, ['out-of-range', 10]]),
('u32 with bit 6 set in last byte stays positive', ([65, 128, 64], ['u32', 'u32']), [65, 8192]),
('negative s64 spanning several bytes', ([255, 255, 255, 255, 255, 95], ['s64']), [-1099511627777]),
('truncated immediate', ([128, 129], ['u64']), [['unexpected-end', 2]])],
[('regression: mixed immediates', ([213, 15, 230, 126, 127], ['u32', 's32', 's64']), [2005, -154, -1]),
('single byte 0x7F', ([127, 127], ['u32', 's32']), [127, -1]),
('five-byte u32 is the maximum length', ([128, 128, 128, 128, 2], ['u32']), [536870912]),
('six-byte u32 is too long', ([128, 128, 128, 128, 128, 0, 2], ['u32', 'u32']), [['too-long', 5]]),
('s32 2^31 out of range, -2^31 in range',
([128, 128, 128, 128, 120, 128, 128, 128, 128, 8], ['s32', 's32']),
[-2147483648, ['out-of-range', 10]]),
('u32 with bit 6 set in last byte stays positive', ([66, 128, 64], ['u32', 'u32']), [66, 8192]),
('negative s64 spanning several bytes', ([254, 255, 255, 255, 255, 95], ['s64']), [-1099511627778]),
('truncated immediate', ([128, 130], ['u64']), [['unexpected-end', 2]])],
[('regression: mixed immediates', ([189, 23, 153, 126, 127], ['u32', 's32', 's64']), [3005, -231, -1]),
('single byte 0x7F', ([127, 127], ['u32', 's32']), [127, -1]),
('five-byte u32 is the maximum length', ([128, 128, 128, 128, 3], ['u32']), [805306368]),
('six-byte u32 is too long', ([128, 128, 128, 128, 128, 0, 3], ['u32', 'u32']), [['too-long', 5]]),
('s32 2^31 out of range, -2^31 in range',
([128, 128, 128, 128, 120, 128, 128, 128, 128, 8], ['s32', 's32']),
[-2147483648, ['out-of-range', 10]]),
('u32 with bit 6 set in last byte stays positive', ([67, 128, 64], ['u32', 'u32']), [67, 8192]),
('negative s64 spanning several bytes', ([253, 255, 255, 255, 255, 95], ['s64']), [-1099511627779]),
('truncated immediate', ([128, 131], ['u64']), [['unexpected-end', 2]])],
[('regression: mixed immediates', ([165, 31, 204, 125, 127], ['u32', 's32', 's64']), [4005, -308, -1]),
('single byte 0x7F', ([127, 127], ['u32', 's32']), [127, -1]),
('five-byte u32 is the maximum length', ([128, 128, 128, 128, 4], ['u32']), [1073741824]),
('six-byte u32 is too long', ([128, 128, 128, 128, 128, 0, 4], ['u32', 'u32']), [['too-long', 5]]),
('s32 2^31 out of range, -2^31 in range',
([128, 128, 128, 128, 120, 128, 128, 128, 128, 8], ['s32', 's32']),
[-2147483648, ['out-of-range', 10]]),
('u32 with bit 6 set in last byte stays positive', ([68, 128, 64], ['u32', 'u32']), [68, 8192]),
('negative s64 spanning several bytes', ([252, 255, 255, 255, 255, 95], ['s64']), [-1099511627780]),
('truncated immediate', ([128, 132], ['u64']), [['unexpected-end', 2]])],
[('regression: mixed immediates', ([141, 39, 255, 124, 127], ['u32', 's32', 's64']), [5005, -385, -1]),
('single byte 0x7F', ([127, 127], ['u32', 's32']), [127, -1]),
('five-byte u32 is the maximum length', ([128, 128, 128, 128, 5], ['u32']), [1342177280]),
('six-byte u32 is too long', ([128, 128, 128, 128, 128, 0, 5], ['u32', 'u32']), [['too-long', 5]]),
('s32 2^31 out of range, -2^31 in range',
([128, 128, 128, 128, 120, 128, 128, 128, 128, 8], ['s32', 's32']),
[-2147483648, ['out-of-range', 10]]),
('u32 with bit 6 set in last byte stays positive', ([69, 128, 64], ['u32', 'u32']), [69, 8192]),
('negative s64 spanning several bytes', ([251, 255, 255, 255, 255, 95], ['s64']), [-1099511627781]),
('truncated immediate', ([128, 133], ['u64']), [['unexpected-end', 2]])]]
for label, args, expected in cases[N - 1]:
check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression: mixed immediates | [1005, 16307, 127] | [1005, -77, -1] | Failed |
| single byte 0x7F | [127, 127] | [127, -1] | Failed |
| five-byte u32 is the maximum length | [268435456] | [268435456] | Passed |
| six-byte u32 is too long | [['too-long', 5]] | [['too-long', 5]] | Passed |
| s32 2^31 out of range, -2^31 in range | [-2147483648, ['out-of-range', 10]] | [-2147483648, ['out-of-range', 10]] | Passed |
| u32 with bit 6 set in last byte stays positive | [65, 8192] | [65, 8192] | Passed |
| negative s64 spanning several bytes | [3298534883327] | [-1099511627777] | Failed |
| truncated immediate | [['unexpected-end', 2]] | [['unexpected-end', 2]] | Passed |
SHA-256 / ebf02b0285932050a144d64af3cfe1b197a135f52741e1d28c1a03bee2194925
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(data, kinds):
pos = 0
out = []
for kind in kinds:
bits = 32 if kind in ('u32', 's32') else 64
maxlen = (bits + 6) // 7
result = 0
shift = 0
n = 0
while True:
if pos >= len(data):
return out + [['unexpected-end', pos]]
byte = data[pos]
pos += 1
n += 1
result |= (byte & 0x7F) << shift
shift += 7
if (byte & 0x80) == 0:
break
if n == maxlen:
return out + [['too-long', pos]]
if kind[0] == 's' and byte & 0x40:
result -= 1 << shift
if kind == 's32' and not -(1 << 31) <= result < (1 << 31):
return out + [['out-of-range', pos]]
if kind == 'u32' and result >= (1 << 32):
return out + [['out-of-range', pos]]
out.append(result)
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: mixed immediates', ([237, 7, 179, 127, 127], ['u32', 's32', 's64']), [1005, -77, -1]),
('single byte 0x7F', ([127, 127], ['u32', 's32']), [127, -1]),
('five-byte u32 is the maximum length', ([128, 128, 128, 128, 1], ['u32']), [268435456]),
('six-byte u32 is too long', ([128, 128, 128, 128, 128, 0, 1], ['u32', 'u32']), [['too-long', 5]]),
('s32 2^31 out of range, -2^31 in range',
([128, 128, 128, 128, 120, 128, 128, 128, 128, 8], ['s32', 's32']),
[-2147483648, ['out-of-range', 10]]),
('u32 with bit 6 set in last byte stays positive', ([65, 128, 64], ['u32', 'u32']), [65, 8192]),
('negative s64 spanning several bytes', ([255, 255, 255, 255, 255, 95], ['s64']), [-1099511627777]),
('truncated immediate', ([128, 129], ['u64']), [['unexpected-end', 2]])],
[('regression: mixed immediates', ([213, 15, 230, 126, 127], ['u32', 's32', 's64']), [2005, -154, -1]),
('single byte 0x7F', ([127, 127], ['u32', 's32']), [127, -1]),
('five-byte u32 is the maximum length', ([128, 128, 128, 128, 2], ['u32']), [536870912]),
('six-byte u32 is too long', ([128, 128, 128, 128, 128, 0, 2], ['u32', 'u32']), [['too-long', 5]]),
('s32 2^31 out of range, -2^31 in range',
([128, 128, 128, 128, 120, 128, 128, 128, 128, 8], ['s32', 's32']),
[-2147483648, ['out-of-range', 10]]),
('u32 with bit 6 set in last byte stays positive', ([66, 128, 64], ['u32', 'u32']), [66, 8192]),
('negative s64 spanning several bytes', ([254, 255, 255, 255, 255, 95], ['s64']), [-1099511627778]),
('truncated immediate', ([128, 130], ['u64']), [['unexpected-end', 2]])],
[('regression: mixed immediates', ([189, 23, 153, 126, 127], ['u32', 's32', 's64']), [3005, -231, -1]),
('single byte 0x7F', ([127, 127], ['u32', 's32']), [127, -1]),
('five-byte u32 is the maximum length', ([128, 128, 128, 128, 3], ['u32']), [805306368]),
('six-byte u32 is too long', ([128, 128, 128, 128, 128, 0, 3], ['u32', 'u32']), [['too-long', 5]]),
('s32 2^31 out of range, -2^31 in range',
([128, 128, 128, 128, 120, 128, 128, 128, 128, 8], ['s32', 's32']),
[-2147483648, ['out-of-range', 10]]),
('u32 with bit 6 set in last byte stays positive', ([67, 128, 64], ['u32', 'u32']), [67, 8192]),
('negative s64 spanning several bytes', ([253, 255, 255, 255, 255, 95], ['s64']), [-1099511627779]),
('truncated immediate', ([128, 131], ['u64']), [['unexpected-end', 2]])],
[('regression: mixed immediates', ([165, 31, 204, 125, 127], ['u32', 's32', 's64']), [4005, -308, -1]),
('single byte 0x7F', ([127, 127], ['u32', 's32']), [127, -1]),
('five-byte u32 is the maximum length', ([128, 128, 128, 128, 4], ['u32']), [1073741824]),
('six-byte u32 is too long', ([128, 128, 128, 128, 128, 0, 4], ['u32', 'u32']), [['too-long', 5]]),
('s32 2^31 out of range, -2^31 in range',
([128, 128, 128, 128, 120, 128, 128, 128, 128, 8], ['s32', 's32']),
[-2147483648, ['out-of-range', 10]]),
('u32 with bit 6 set in last byte stays positive', ([68, 128, 64], ['u32', 'u32']), [68, 8192]),
('negative s64 spanning several bytes', ([252, 255, 255, 255, 255, 95], ['s64']), [-1099511627780]),
('truncated immediate', ([128, 132], ['u64']), [['unexpected-end', 2]])],
[('regression: mixed immediates', ([141, 39, 255, 124, 127], ['u32', 's32', 's64']), [5005, -385, -1]),
('single byte 0x7F', ([127, 127], ['u32', 's32']), [127, -1]),
('five-byte u32 is the maximum length', ([128, 128, 128, 128, 5], ['u32']), [1342177280]),
('six-byte u32 is too long', ([128, 128, 128, 128, 128, 0, 5], ['u32', 'u32']), [['too-long', 5]]),
('s32 2^31 out of range, -2^31 in range',
([128, 128, 128, 128, 120, 128, 128, 128, 128, 8], ['s32', 's32']),
[-2147483648, ['out-of-range', 10]]),
('u32 with bit 6 set in last byte stays positive', ([69, 128, 64], ['u32', 'u32']), [69, 8192]),
('negative s64 spanning several bytes', ([251, 255, 255, 255, 255, 95], ['s64']), [-1099511627781]),
('truncated immediate', ([128, 133], ['u64']), [['unexpected-end', 2]])]]
for label, args, expected in cases[N - 1]:
check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression: mixed immediates | [1005, -77, -1] | [1005, -77, -1] | Passed |
| single byte 0x7F | [127, -1] | [127, -1] | Passed |
| five-byte u32 is the maximum length | [268435456] | [268435456] | Passed |
| six-byte u32 is too long | [['too-long', 5]] | [['too-long', 5]] | Passed |
| s32 2^31 out of range, -2^31 in range | [-2147483648, ['out-of-range', 10]] | [-2147483648, ['out-of-range', 10]] | Passed |
| u32 with bit 6 set in last byte stays positive | [65, 8192] | [65, 8192] | Passed |
| negative s64 spanning several bytes | [-1099511627777] | [-1099511627777] | Passed |
| truncated immediate | [['unexpected-end', 2]] | [['unexpected-end', 2]] | Passed |
SHA-256 / 068badf6ebdfe8f3cd74d98bab2206f2d313c01a8f560956b3b3bdb0ae6bdb6c
Verification & scope
A deterministic, bounded teaching model of one bytecode virtual machine mechanism with a stipulated instruction encoding; it is not a production VM and claims no conformance to any real specification. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.
Observations recorded using Python 3.12.14 at 2026-09-29T14:51:24.081653+00:00.
Case digest / 260dbe3f5f6834c7bc210d73b69056244566b1aeb8818921748bcbc4426e2905