Author: yonik
Date: Wed May 4 18:54:26 2011
New Revision: 1099557
URL: http://svn.apache.org/viewvc?rev=1099557&view=rev
Log:
noggit: fix hang on bad input, fix long overflow detection, add random testing
Modified:
labs/noggit/src/main/java/org/apache/noggit/JSONParser.java
labs/noggit/src/test/java/org/apache/noggit/TestJSONParser.java
Modified: labs/noggit/src/main/java/org/apache/noggit/JSONParser.java
URL:
http://svn.apache.org/viewvc/labs/noggit/src/main/java/org/apache/noggit/JSONParser.java?rev=1099557&r1=1099556&r2=1099557&view=diff
==============================================================================
--- labs/noggit/src/main/java/org/apache/noggit/JSONParser.java (original)
+++ labs/noggit/src/main/java/org/apache/noggit/JSONParser.java Wed May 4
18:54:26 2011
@@ -57,6 +57,12 @@ public class JSONParser {
/** Event indicating the end of input has been reached */
public static final int EOF=11;
+ public static class ParseException extends RuntimeException {
+ public ParseException(String msg) {
+ super(msg);
+ }
+ }
+
public static String getEventString( int e )
{
switch( e )
@@ -202,7 +208,7 @@ public class JSONParser {
}
}
- private RuntimeException err(String msg) {
+ private ParseException err(String msg) {
// We can't tell if EOF was hit by comparing start<=end
// because the illegal char could have been the last in the buffer
// or in the stream. To deal with this, the "eof" var was introduced
@@ -214,13 +220,13 @@ public class JSONParser {
if (start>=end) msg = "Unexpected EOF";
else msg="JSON Parse Error";
}
- return new RuntimeException(msg + ": " + tot);
+ return new ParseException(msg + ": " + tot);
}
private String getContext() {
String context = "";
if (start>=0) {
- context += " BEFORE='" + errEscape(Math.max(start-40,0), start+1) + "'";
+ context += " BEFORE='" + errEscape(Math.max(start-60,0), start+1) + "'";
}
if (start<end) {
context += " AFTER='" + errEscape(start+1, start+40) + "'";
@@ -249,7 +255,10 @@ public class JSONParser {
// We build up the number in the negative plane since it's larger (by one)
than
// the positive plane.
long v = '0' - firstChar;
- for (int i=0; i<22; i++) {
+ // can't overflow a long in 18 decimal digits (i.e. 17 additional after
the first).
+ // we also need 22 additional to handle double so we'll handle in 2
separate loops.
+ int i;
+ for (i=0; i<17; i++) {
int ch = getChar();
// TODO: is this switch faster as an if-then-else?
switch(ch) {
@@ -263,7 +272,7 @@ public class JSONParser {
case '7':
case '8':
case '9':
- v = v *10 - (ch-'0');
+ v = v*10 - (ch-'0');
out.unsafeWrite(ch);
continue;
case '.':
@@ -281,19 +290,56 @@ public class JSONParser {
// for invalid chars following the number.
if (ch!=-1) --start; // push back last char if not EOF
- // the max number of digits we are reading only allows for
- // a long to wrap once, so we can just check if the sign is
- // what is expected to detect an overflow.
- if (isNeg) {
- // -0 is allowed by the spec
- valstate = v<=0 ? LONG : BIGNUMBER;
- } else {
- v=-v;
- valstate = v>=0 ? LONG : BIGNUMBER;
- }
- return v;
+ valstate = LONG;
+ return isNeg ? v : -v;
}
}
+
+ // after this, we could overflow a long and need to do extra checking
+ boolean overflow = false;
+ long maxval = isNeg ? Long.MIN_VALUE : -Long.MAX_VALUE;
+
+ for (; i<22; i++) {
+ int ch = getChar();
+ switch(ch) {
+ case '0':
+ case '1':
+ case '2':
+ case '3':
+ case '4':
+ case '5':
+ case '6':
+ case '7':
+ case '8':
+ case '9':
+ if (v < (0x8000000000000000L/10)) overflow=true; // can't multiply
by 10 w/o overflowing
+ v *= 10;
+ int digit = ch - '0';
+ if (v < maxval + digit) overflow=true; // can't add digit w/o
overflowing
+ v -= digit;
+ out.unsafeWrite(ch);
+ continue;
+ case '.':
+ out.unsafeWrite('.');
+ valstate = readFrac(out,22-i);
+ return 0;
+ case 'e':
+ case 'E':
+ out.unsafeWrite(ch);
+ nstate=0;
+ valstate = readExp(out,22-i);
+ return 0;
+ default:
+ // return the number, relying on nextEvent() to return an error
+ // for invalid chars following the number.
+ if (ch!=-1) --start; // push back last char if not EOF
+
+ valstate = overflow ? BIGNUMBER : LONG;
+ return isNeg ? v : -v;
+ }
+ }
+
+
nstate=0;
valstate = BIGNUMBER;
return 0;
@@ -445,6 +491,7 @@ public class JSONParser {
for (;;) {
if (middle>=end) {
arr.write(buf,start,middle-start);
+ start=middle;
getMore();
middle=start;
}
@@ -527,7 +574,7 @@ public class JSONParser {
return valstate;
} else if (ch>'9' || ch<'0') {
out.unsafeWrite('0');
- start--;
+ if (ch!=-1) start--;
lval = 0;
valstate=LONG;
return LONG;
Modified: labs/noggit/src/test/java/org/apache/noggit/TestJSONParser.java
URL:
http://svn.apache.org/viewvc/labs/noggit/src/test/java/org/apache/noggit/TestJSONParser.java?rev=1099557&r1=1099556&r2=1099557&view=diff
==============================================================================
--- labs/noggit/src/test/java/org/apache/noggit/TestJSONParser.java (original)
+++ labs/noggit/src/test/java/org/apache/noggit/TestJSONParser.java Wed May 4
18:54:26 2011
@@ -29,13 +29,28 @@ import java.io.IOException;
*/
public class TestJSONParser extends TestCase {
- public static Random r = new Random(0);
+ public static Random r = new Random();
+
+ // these are to aid in debugging if an unexpected error occurs
+ static int parserType;
+ static int bufferSize;
+ static String parserInput;
+ static JSONParser lastParser;
+
+ public static String lastParser() {
+ return "parserType=" + parserType
+ + (parserType==1 ? " bufferSize=" + bufferSize : "")
+ + " parserInput='" + parserInput + "'";
+ }
public static JSONParser getParser(String s) {
- return getParser(s, r.nextInt(2));
+ return getParser(s, r.nextInt(2), -1);
}
- public static JSONParser getParser(String s, int type) {
+ public static JSONParser getParser(String s, int type, int bufSize) {
+ parserInput = s;
+ parserType = type;
+
JSONParser parser=null;
switch (type) {
case 0:
@@ -45,11 +60,28 @@ public class TestJSONParser extends Test
case 1:
// test using Reader...
// small input buffers can help find bugs on boundary conditions
- parser = new JSONParser(new StringReader(s), new
char[r.nextInt(25)+1]);
+
+ if (bufSize < 1) bufSize = r.nextInt(25) + 1;
+ bufferSize = bufSize;// record in case there is an error
+ parser = new JSONParser(new StringReader(s), new char[bufSize]);
+ break;
+ }
+ return lastParser = parser;
+ }
+
+ /** for debugging purposes
+ public void testSpecific() throws Exception {
+ JSONParser parser = getParser("[0",1,1);
+ for (;;) {
+ int ev = parser.nextEvent();
+ if (ev == JSONParser.EOF) {
break;
+ } else {
+ System.out.println("got " + JSONParser.getEventString(ev));
+ }
}
- return parser;
}
+ **/
public static byte[] events = new byte[256];
static {
@@ -84,10 +116,87 @@ public class TestJSONParser extends Test
public static void parse(String input, String expected) throws IOException {
input = input.replace('\'','"');
for (int i=0; i<Integer.MAX_VALUE; i++) {
- JSONParser p = getParser(input,i);
+ JSONParser p = getParser(input,i,-1);
if (p==null) break;
parse(p,input,expected);
- }
+ }
+
+ testCorruption(input, 100000);
+
+ }
+
+ public static void testCorruption(String input, int iter) {
+ char[] arr = new char[input.length()];
+
+ for (int i=0; i<iter; i++) {
+ input.getChars(0, arr.length, arr, 0);
+ int changes = r.nextInt(arr.length>>1) + 1;
+ for (int j=0; j<changes; j++) {
+ char ch;
+ switch (r.nextInt(30)) {
+ case 0: ch = 0; break;
+ case 1: ch = '['; break;
+ case 2: ch = ']'; break;
+ case 3: ch = '{'; break;
+ case 4: ch = '}'; break;
+ case 5: ch = '"'; break;
+ case 6: ch = '\''; break;
+ case 7: ch = ' '; break;
+ case 8: ch = '\r'; break;
+ case 9: ch = '\n'; break;
+ case 10:ch = '\t'; break;
+ case 11:ch = ','; break;
+ case 12:ch = ':'; break;
+ case 13:ch = '.'; break;
+ case 14:ch = 'a'; break;
+ case 15:ch = 'e'; break;
+ case 16:ch = '0'; break;
+ case 17:ch = '1'; break;
+ case 18:ch = '+'; break;
+ case 19:ch = '-'; break;
+ case 20:ch = 't'; break;
+ case 21:ch = 'f'; break;
+ case 22:ch = 'n'; break;
+ case 23:ch = '/'; break;
+ case 24:ch = '\\'; break;
+ case 25:ch = 'u'; break;
+ default:ch = (char)r.nextInt(256);
+ }
+
+ arr[r.nextInt(arr.length)] = ch;
+ }
+
+
+ JSONParser parser = getParser(new String(arr));
+ int ret = 0;
+ try {
+ for (;;) {
+ int ev = parser.nextEvent();
+ if (r.nextBoolean()) {
+ // see if we can read the event
+ switch (ev) {
+ case JSONParser.STRING: ret += parser.getString().length();
break;
+ case JSONParser.BOOLEAN: ret += parser.getBoolean() ? 1 : 2;
break;
+ case JSONParser.BIGNUMBER: ret +=
parser.getNumberChars().length(); break;
+ case JSONParser.NUMBER: ret += parser.getDouble(); break;
+ case JSONParser.LONG: ret += parser.getLong(); break;
+ default: ret += ev;
+ }
+ }
+
+ if (ev == JSONParser.EOF) break;
+ }
+ } catch (IOException ex) {
+ // shouldn't happen
+ System.out.println(ret); // use ret
+ } catch (JSONParser.ParseException ex) {
+ // OK
+ } catch (Throwable ex) {
+ ex.printStackTrace();
+ System.out.println(lastParser());
+ throw new RuntimeException(ex);
+ }
+ }
}
@@ -165,7 +274,7 @@ public class TestJSONParser extends Test
public static void parse(String input, Object[] expected) throws IOException
{
input = input.replace('\'','"');
for (int i=0; i<Integer.MAX_VALUE; i++) {
- JSONParser p = getParser(input,i);
+ JSONParser p = getParser(input,i,-1);
if (p==null) break;
parse(p,input,expected);
}
@@ -332,6 +441,26 @@ public class TestJSONParser extends Test
// check it works with a leading zero too
t = "0.2250738585072014E-308" + "0";
parse("["+t+","+"-"+t+"]", new Object[]{a,bn(t),bn("-"+t),A,e});
+
+ // check that overflow detection is working properly w/ numbers that don't
cause a wrap to negatives
+ // when multiplied by 10
+ t = "1910151821265210155" + "0";
+ parse("["+t+","+"-"+t+"]", new Object[]{a,bn(t),bn("-"+t),A,e});
+
+ for (int i=0; i<1000000; i++) {
+ long val = r.nextLong();
+ String sval = Long.toString(val);
+ JSONParser parser = getParser("["+val+"]");
+ parser.nextEvent();
+ assertTrue(parser.nextEvent() == JSONParser.LONG);
+ if (r.nextBoolean()) {
+ assertEquals(val, parser.getLong());
+ } else {
+ CharArr chars = parser.getNumberChars();
+ assertEquals(sval, chars.toString());
+ }
+ }
+
}
public void testArray() throws IOException {
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
