JDK-7063674 : Wrong results from basic comparisons after calls to Long.bitCount(long)
  • Type: Bug
  • Component: hotspot
  • Sub-Component: compiler
  • Affected Version: 6u26
  • Priority: P3
  • Status: Closed
  • Resolution: Fixed
  • OS: linux
  • CPU: x86
  • Submitted: 2011-07-07
  • Updated: 2014-03-03
  • Resolved: 2012-06-16
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availabitlity Release.

To download the current JDK release, click here.
JDK 6 JDK 7 JDK 8 Other
6u38Fixed 7u6Fixed 8Fixed hs20.13Fixed
Related Reports
Relates :  
Relates :  
Description
FULL PRODUCT VERSION :
java version "1.6.0_26"
Java(TM) SE Runtime Environment (build 1.6.0_26-b03)
Java HotSpot(TM) 64-Bit Server VM (build 20.1-b02, mixed mode)

Also occurs on a JDK 7 install we have:
java version "1.7.0"
Java(TM) SE Runtime Environment (build 1.7.0-b147)
Java HotSpot(TM) 64-Bit Server VM (build 21.0-b17, mixed mode)



FULL OS VERSION :
Linux 2.6.18-238.12.1.el5 #1 SMP Tue May 31 13:22:04 EDT 2011 x86_64 x86_64 x86_64 GNU/Linux

EXTRA RELEVANT SYSTEM CONFIGURATION :
Doesn't occur on all CPUs. But we have verified it on:
Quad-Core AMD Opteron(tm) Processor 8347 and Intel(R) Xeon(R) CPU           E5520

A DESCRIPTION OF THE PROBLEM :
After a certain number of calls to a particular method, Math.min() returns the incorrect result. We have made a small test case, where Math.min(1,2) returns 2!!!

Investigating some JVM options we discovered that the problem does not occur when using -XX:-UsePopCountInstruction. Which leads us to believe the problem is related to the use of the Long.bitCount method. If so, this could be a serious security bug, given the amount of bit shifting that goes on in encryption code.

I had tried to simplify the example somewhat, but on smaller examples I didn't observe the problem on JDK7.


THE PROBLEM WAS REPRODUCIBLE WITH -Xint FLAG: No

THE PROBLEM WAS REPRODUCIBLE WITH -server FLAG: Did not try

REGRESSION.  Last worked in version 6

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
The attached example has a loop which calls our method with random numbers which it then discards the result of, it then calls the method with known inputs and an expected result. If the result is not the expected one we print out the number of iterations that were correct before this call and the incorrect return value. In addition we hard code a check inside the method the arguments we are testing detect the incorrect behavior, printing out the exact variables involved in the incorrect Math.min call.

Run the example class (PopCountBug) on CPUs which have the pop count instruction, if the bug presents itself then a few lines of output will be written. If the bug does not occur then there will be no output.

$ #here we are using 1.6 update 26, the bug occurs after 6748 iterations
$ #we also print out the values of the problematic variables, and the result of the Math.min call
$ usr/local/java/jdk1.6.0_26/bin/java PopCountBug
scoreDel: 1 scoreIns: 2 min(scoreDel, scoreIns): 2
6748
3

$ #same thing with an early access JDK 7
$ /usr/local/java/jdk1.7.0/bin/java PopCountBug
scoreDel: 1 scoreIns: 2 min(scoreDel, scoreIns): 2
6493
3

$ #here we try Java 1.6 update 13, on which the bug does not occur
$ /usr/local/java/jdk1.6.0_13/bin/java PopCountBug

EXPECTED VERSUS ACTUAL BEHAVIOR :
Expected no output
$ usr/local/java/jdk1.6.0_26/bin/java PopCountBug

Actual:
$ usr/local/java/jdk1.6.0_26/bin/java PopCountBug
scoreDel: 1 scoreIns: 2 min(scoreDel, scoreIns): 2
6748
3
REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import java.util.*;
import java.io.*;
import java.util.zip.*;

public class PopCountBug {

  public static void main(String args[]) throws IOException {
    Random r = new Random(42);
    for (int i = 0; i < 10000000; i++) {
      score(r.nextLong(), r.nextLong(), r.nextLong(), r.nextLong());
      int res = score(19331613728L, 6237928679L, 272696352L, 8385412327L);
      if (res != 2) {
        System.out.println(i);
        System.out.println(res);
        return;
      }
    }
  }

  static final long sMask = (1L << 35) - 1;
  private static int score(final long r0, final long r1, final long template0, final long template1) {
    final long diff = simpleDiff(r0, r1, template0, template1) & sMask;
    final int exactScore = Long.bitCount(diff);
    if (exactScore <= 2) {
      return exactScore;
    }
    final long diffDel = diff & simpleDiff(r0 >>> 1, r1 >>> 1, template0, template1);
    final int scoreDel = Long.bitCount(diffDel);
    final long diffIns = diff & simpleDiff(r0, r1, template0 >>> 1, template1 >>> 1);
    final int scoreIns = Long.bitCount(diffIns);
    final int minA =  Math.min(scoreDel, scoreIns);
    final int bestScore = Math.min(exactScore, minA + 1);
    if (r0 == 19331613728L && bestScore != 2) {
      System.out.println("scoreDel: " + scoreDel + " scoreIns: "+ scoreIns + " min(scoreDel, scoreIns): " + minA);
    }

    return (int) bestScore;
  }

  static long simpleDiff(final long a0, final long a1, final long b0, final long b1) {
    final long diff = (a0 ^ b0) | (a1 ^ b1);
    return diff;
  }
}
---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
Invoking java with -XX:-UsePopCountInstruction prevents the bug from occurring.

Comments
Closed as already verified during 7u40 bug verification process.
2013-07-31

EVALUATION http://hg.openjdk.java.net/lambda/lambda/hotspot/rev/ccaa67adfe5b
2012-06-29

EVALUATION http://hg.openjdk.java.net/hsx/hsx23.2/hotspot/rev/dc333950f54f
2012-06-19

EVALUATION http://hg.openjdk.java.net/hsx/hotspot-comp/hotspot/rev/ccaa67adfe5b
2012-06-12

WORK AROUND -XX:-UsePopCountInstruction
2012-06-11

EVALUATION We are scheduling popcnt instructions between compare and branch/conditional move instructions because AD instructs are not defined to kill flags: 0x00007fd5708e10aa: cmp %r8d,%r9d 0x00007fd5708e10ad: popcnt %rcx,%rbp ;*invokestatic bitCount ; - PopCountBug::score@76 (line 30) 0x00007fd5708e10b2: popcnt %r11,%r9 ;*invokestatic bitCount ; - PopCountBug::score@51 (line 28) 0x00007fd5708e10b7: cmovl %r9d,%ebp ;*invokestatic min But the Intel Instruction Set Reference says for POPCNT: Flags Affected OF, SF, ZF, AF, CF, PF are all cleared. ZF is set if SRC = 0, otherwise ZF is cleared
2012-06-11

EVALUATION I can reproduce this bug with our latest JDK 8 build: cthaling@sc14ia03:~$ /java/re/jdk/8/promoted/all/b42/binaries/linux-x64/bin/java -showversion -d64 PopCountBug java version "1.8.0-ea" Java(TM) SE Runtime Environment (build 1.8.0-ea-b42) Java HotSpot(TM) 64-Bit Server VM (build 24.0-b13, mixed mode) scoreDel: 1 scoreIns: 2 min(scoreDel, scoreIns): 2 12306 3
2012-06-11

EVALUATION Introduced with JDK 7b53: cthaling@sc14ia03:~$ /java/re/jdk/7/promoted/all/b52/binaries/linux-x64/bin/java -showversion -d64 PopCountBug java version "1.7.0-ea" Java(TM) SE Runtime Environment (build 1.7.0-ea-b52) Java HotSpot(TM) 64-Bit Server VM (build 15.0-b03, mixed mode) cthaling@sc14ia03:~$ /java/re/jdk/7/promoted/all/b53/binaries/linux-x64/bin/java -showversion -d64 PopCountBug java version "1.7.0-ea" Java(TM) SE Runtime Environment (build 1.7.0-ea-b53) Java HotSpot(TM) 64-Bit Server VM (build 15.0-b04, mixed mode) scoreDel: 1 scoreIns: 2 min(scoreDel, scoreIns): 2 5864 3 The bug is also in JDK 6 (introduced in 6u18): cthaling@sc14ia03:~/hsx/hotspot-comp/7063674/make$ /java/re/jdk/6u17/promoted/latest/binaries/linux-amd64/bin/java -showversion -d64 -XX:-TieredCompilation -cp .. PopCountBug java version "1.6.0_17" Java(TM) SE Runtime Environment (build 1.6.0_17-b04) Java HotSpot(TM) 64-Bit Server VM (build 14.3-b01, mixed mode) cthaling@sc14ia03:~/hsx/hotspot-comp/7063674/make$ /java/re/jdk/6u18/promoted/latest/binaries/linux-amd64/bin/java -showversion -d64 -XX:-TieredCompilation -cp .. PopCountBug java version "1.6.0_18" Java(TM) SE Runtime Environment (build 1.6.0_18-b07) Java HotSpot(TM) 64-Bit Server VM (build 16.0-b13, mixed mode) scoreDel: 1 scoreIns: 2 min(scoreDel, scoreIns): 2 5839 3
2012-06-11