1.7.7.2's new Array sort() can throw ArrayIndexOutOfBoundsException #357
Comments
|
Thank you for reproducing this. Sorry it crept in. I'll look at it soon.
…On Wed, Nov 1, 2017 at 5:40 AM, Ben Summers ***@***.***> wrote:
Here's a test case where the rewritten Array sort() function can throw
ArrayIndexOutOfBoundsException.
It's slightly convoluted, but hit us immediately after an update to
1.7.7.2. Using chunks of underscore.js was necessary to reproduce.
Test case
var i = ["UHl3DzELNleHuQ", "Na6de_6oK1SkkNPRHLib8Y2Lwg",
"GnPrJj5R7savc5YGqRQ8Vf5z", "AmV1H9UWHU1GxQ",
"i7w_JpplQauf2jAD8ko", "z-qs4duUdshTy686Pg4",
"EI8kRBMNjZfRC9YH-Q", "w-A", "ukUm_NcvcToZyKn4Vw",
"05C4qwB52eGjZcf83_YO3PSbYA", "_73TGwD1CRtoWdwdCTZdw8E",
"NnXYyCqBJ-q036o", "eg", "uUIuxNDHfoHgntjZnqrvrjjTVJc",
"bhY", "qSzGSQ", "LpLx6ZJDp0LNHZsoRee3wYim", "uDXkQA", "hhWgHw"];
// -----------------------------
// Copied from Underscore.js 1.5.1 (MIT license)
var _ = {};
var ArrayProto = Array.prototype, ObjProto = Object.prototype, FuncProto = Function.prototype;var nativeMap = ArrayProto.map;
_.map = _.collect = function(obj, iterator, context) {
var results = [];
if (obj == null) return results;
if (nativeMap && obj.map === nativeMap) return obj.map(iterator, context);
each(obj, function(value, index, list) {
results.push(iterator.call(context, value, index, list));
});
return results;
};
_.pluck = function(obj, key) {
return _.map(obj, function(value){ return value[key]; });
};
var lookupIterator = function(value) {// return _.isFunction(value) ? value : function(obj){ return obj[value]; };
return function(obj){ return obj[value]; };
};
_.sortBy = function(obj, value, context) {
var iterator = lookupIterator(value);
return _.pluck(_.map(obj, function(value, index, list) {
return {
value : value,
index : index,
criteria : iterator.call(context, value, index, list)
};
}).sort(function(left, right) {
var a = left.criteria;
var b = right.criteria;
if (a !== b) {
if (a > b || a === void 0) return 1;
if (a < b || b === void 0) return -1;
}
return left.index < right.index ? -1 : 1;
}), 'value');
};
// -----------------------------
var a = [];i.forEach(function(v) {
a.push({value:v});
});
_.sortBy(a, 'value');
Backtrace when run
Running it in the Rhino shell:
$ java -cp lib/js.jar org.mozilla.javascript.tools.shell.Main minimal.js
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
at org.mozilla.javascript.Sorting.partition(Sorting.java:68)
at org.mozilla.javascript.Sorting.hybridSort(Sorting.java:46)
at org.mozilla.javascript.Sorting.hybridSort(Sorting.java:37)
at org.mozilla.javascript.NativeArray.js_sort(NativeArray.java:1030)
at org.mozilla.javascript.NativeArray.execIdCall(NativeArray.java:300)
at org.mozilla.javascript.IdFunctionObject.call(IdFunctionObject.java:101)
at org.mozilla.javascript.optimizer.OptRuntime.call1(OptRuntime.java:32)
at org.mozilla.javascript.gen.minimal_js_1._c_anonymous_7(Unknown Source)
at org.mozilla.javascript.gen.minimal_js_1.call(Unknown Source)
at org.mozilla.javascript.optimizer.OptRuntime.call2(OptRuntime.java:42)
at org.mozilla.javascript.gen.minimal_js_1._c_script_0(Unknown Source)
at org.mozilla.javascript.gen.minimal_js_1.call(Unknown Source)
at org.mozilla.javascript.ContextFactory.doTopCall(ContextFactory.java:399)
at org.mozilla.javascript.ScriptRuntime.doTopCall(ScriptRuntime.java:3452)
at org.mozilla.javascript.gen.minimal_js_1.call(Unknown Source)
at org.mozilla.javascript.gen.minimal_js_1.exec(Unknown Source)
at org.mozilla.javascript.tools.shell.Main.processFileSecure(Main.java:601)
at org.mozilla.javascript.tools.shell.Main.processFile(Main.java:560)
at org.mozilla.javascript.tools.shell.Main.processSource(Main.java:531)
at org.mozilla.javascript.tools.shell.Main.processFiles(Main.java:179)
at org.mozilla.javascript.tools.shell.Main$IProxy.run(Main.java:100)
at org.mozilla.javascript.Context.call(Context.java:526)
at org.mozilla.javascript.ContextFactory.call(ContextFactory.java:509)
at org.mozilla.javascript.tools.shell.Main.exec(Main.java:161)
at org.mozilla.javascript.tools.shell.Main.main(Main.java:136)
Background
We run a fairly large app with a moderate amount of traffic. Within 10
hours of pushing the 1.7.7.2 interpreter to production, we'd had three
reports of this issue through our monitoring.
My first reproducible test case contained personal information, so I wrote
a small fuzzer to pick strings from /dev/random, which found this test case
in well under a second. So it looks like it's pretty easy to trigger.
It's really great that Rhino is still being actively maintained, we really
appreciate the steady upgrades. Thank you!
—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
<#357>, or mute the thread
<https://github.com/notifications/unsubscribe-auth/AAf0a8otd76fryfc0M6uUzJIH-HSrehcks5syGasgaJpZM4QOJX_>
.
|
|
Here's a slightly reduced reproducer: // array's length has to be more than 17 to get into |hybridSort()|
// |0| is in the middle to be chosen as pivot on the first |partition()| call
[1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
.map(function(value, index) { return {index: index, criteria: value}; })
.sort(function(left, right) {
var a = left.criteria;
var b = right.criteria;
if (a !== b) {
if (a > b || a === void 0) return 1;
if (a < b || b === void 0) return -1;
}
return left.index < right.index ? -1 : 1;
});The root cause of the issue, as far as I understand: this particular comparator function tries to always produce stable sort, as a result it will return I don't know how to properly fix this (and Hoare partition scheme isn't supposed to produce stable sorts anyway?), beyond just adding boundary checks to the respective loops in |
|
Thanks for the tests. That code made too many assumptions about how the comparator might behave. Can you look at the following PR, and ideally test it yourself? I'd love some review. Thanks! |
|
Fixed in #360 and merged to master. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Here's a test case where the rewritten Array sort() function can throw ArrayIndexOutOfBoundsException.
It's slightly convoluted, but hit us immediately after an update to 1.7.7.2. Using chunks of underscore.js was necessary to reproduce.
Test case
Backtrace when run
Running it in the Rhino shell:
Background
We run a fairly large app with a moderate amount of traffic. Within 10 hours of pushing the 1.7.7.2 interpreter to production, we'd had three reports of this issue through our monitoring.
My first reproducible test case contained personal information, so I wrote a small fuzzer to pick strings from /dev/random, which found this test case in well under a second. So it looks like it's pretty easy to trigger.
It's really great that Rhino is still being actively maintained, we really appreciate the steady upgrades. Thank you!
The text was updated successfully, but these errors were encountered: