[F-D18] Incorrect Right Shift in Signed High Multiply Instructions

[yiyi-wang-rv]

Summary

The SBPF interpreter's signed high multiply instructions (OpShmul64Imm and OpShmul64Reg) use an incorrect right shift operation that produces wrong results for negative products. The Int128.RShiftN function uses sign-magnitude semantics instead of treating the value as two's complement, causing the high 64 bits of signed multiplications to be computed incorrectly.

Root Cause

In pkg/sbpf/interpreter.go, the signed high multiply instructions use Int128.RShiftN(64) to extract the high 64 bits of a 128-bit signed multiply result:

case OpShmul64Imm:
    if !ip.sbpfVersion.EnablePqr() {
        err = ExcInvalidInstr
        break
    }
    dst128 := wide.Int128FromInt64(int64(r[ins.Dst()]))
    imm128 := wide.Int128FromInt64(int64(ins.Imm()))
    r[ins.Dst()] = dst128.Mul(imm128).RShiftN(64).Uint64()  // Bug: RShiftN uses sign-magnitude!
    pc++

The Int128.RShiftN function in the wide library implements signed right shift using sign-magnitude semantics:

func (x Int128) RShiftN(n uint) (z Int128) {
    neg := false
    if x.Hi < 0 {
        x = x.Neg()   // Convert negative to positive (sign-magnitude)
        neg = true
    }
    // ... shift the magnitude ...
    if neg {
        return z.Neg()  // Negate result back
    }
    return z
}

This is incorrect for extracting the high bits of a two's complement multiplication. When the product is negative (e.g., -683639278233902435), the RShiftN function:

1. Negates to get the positive magnitude
2. Shifts the magnitude right by 64 (resulting in 0 for small magnitudes)
3. Negates back (0 negated is still 0)

This produces 0 instead of the correct value of -1 (0xFFFFFFFFFFFFFFFF).

Example

For inputs:

• dst = 321305695 (0x1326BC5F)
• imm = -2127691133 (0x8132BE83)

The 128-bit product is -683639278233902435, represented in two's complement as:

• Hi = -1 (0xFFFFFFFFFFFFFFFF)
• Lo = 0xF68339B2D25D229D

The correct high 64 bits should be -1 (0xFFFFFFFFFFFFFFFF), but the buggy RShiftN returns 0.

Agave Reference Implementation

Agave (Rust) correctly uses wrapping operations that preserve two's complement semantics:

// From solana-labs/rbpf/src/interpreter.rs
self.reg[dst] = (self.reg[dst] as i64 as i128)
    .wrapping_mul(insn.imm as i128)
    .wrapping_shr(64) as u64;

The key difference is that Rust's wrapping_shr performs a logical (unsigned) right shift on the 128-bit result, preserving all bits correctly.

Impact

• Incorrect Computation: Signed high multiply instructions produce wrong results for negative products
• Register Corruption: Registers that should contain -1 (0xFFFFFFFFFFFFFFFF) instead contain 0
• Differential Fuzzing Failure: Mithril and Agave produce different register values after executing the same program
• Program Behavior Divergence: Programs using SHMUL instructions may behave differently on Mithril vs Agave

Files Modified

• pkg/sbpf/interpreter.go (modified)

Fix

Convert the Int128 product to Uint128 before shifting to perform a logical (unsigned) right shift that preserves the bit pattern:

case OpShmul64Imm:
    if !ip.sbpfVersion.EnablePqr() {
        err = ExcInvalidInstr
        break
    }
    // === START RV FIX ===
    // Fix: Int128.RShiftN uses sign-magnitude semantics which is incorrect.
    // We need to do a logical (unsigned) right shift on the 128-bit product.
    // Convert to Uint128 first to preserve the bit pattern, then shift.
    dst128 := wide.Int128FromInt64(int64(r[ins.Dst()]))
    imm128 := wide.Int128FromInt64(int64(ins.Imm()))
    r[ins.Dst()] = dst128.Mul(imm128).Uint128().RShiftN(64).Uint64()
    // === END RV FIX ===
    pc++
case OpShmul64Reg:
    if !ip.sbpfVersion.EnablePqr() {
        err = ExcInvalidInstr
        break
    }
    // === START RV FIX ===
    // Fix: Int128.RShiftN uses sign-magnitude semantics which is incorrect.
    // We need to do a logical (unsigned) right shift on the 128-bit product.
    // Convert to Uint128 first to preserve the bit pattern, then shift.
    dst128 := wide.Int128FromInt64(int64(r[ins.Dst()]))
    src128 := wide.Int128FromInt64(int64(r[ins.Src()]))
    r[ins.Dst()] = dst128.Mul(src128).Uint128().RShiftN(64).Uint64()
    // === END RV FIX ===
    pc++

The fix:

1. Computes the signed 128-bit product using Int128.Mul (correct)
2. Converts to Uint128 using .Uint128() which preserves the bit pattern
3. Uses Uint128.RShiftN(64) for a logical (unsigned) right shift
4. Extracts the low 64 bits with .Uint64()