JSONObject/Array should be protected from stack overflow exceptions caused by recursion

[stleary]

See #720 for an example of this might be done.

[cleydyr]

Hey, @stleary . What if we use a programmatic stack data structure (ArrayDeque, for example) with iteration to do the parsing instead of recursion?

[TamasPergerDWP]

JSONObject and JSONArray both use JSONTokener class, where the nextValue function catches and handles the StackOverflowError.

This leaves JSONML to be fixed - PR in progress.

[stleary]

@cleydyr I think the risk of missing something in a complete rewrite of the parser would outweigh the benefit of fixing the stack overflow.

[norrisjeremy]

JSONObject and JSONArray both use JSONTokener class, where the nextValue function catches and handles the StackOverflowError.

This leaves JSONML to be fixed - PR in progress.

I don’t think catching StackOverflowError’s can be reliably counted on as being safe?
Since it’s basically a form of memory exhaustion, doesn’t it mean that the JVM can be left in an unrecoverable state?

[norrisjeremy]

JSONObject and JSONArray both use JSONTokener class, where the nextValue function catches and handles the StackOverflowError.
This leaves JSONML to be fixed - PR in progress.

I don’t think catching StackOverflowError’s can be reliably counted on as being safe? Since it’s basically a form of memory exhaustion, doesn’t it mean that the JVM can be left in an unrecoverable state?

See JDK-8067946.
That seems to indicate on some platforms, the JVM is unable to generate a StackOverflowError and will simply crash.
Therefore it seems unsafe to rely upon catching a StackOverflowError as a means of mitigating an issue.

[TamasPergerDWP]

I don’t think catching StackOverflowError’s can be reliably counted on as being safe? Since it’s basically a form of memory exhaustion, doesn’t it mean that the JVM can be left in an unrecoverable state?

See JDK-8067946. That seems to indicate on some platforms, the JVM is unable to generate a StackOverflowError and will simply crash. Therefore it seems unsafe to rely upon catching a StackOverflowError as a means of mitigating an issue.

Fair enough - although it works OK in my environment, throwing StackOverflowError as expected, other platforms may behave in a different way. Now that I have the unit tests, only the implementation is left to do.

[norrisjeremy]

I don’t think catching StackOverflowError’s can be reliably counted on as being safe? Since it’s basically a form of memory exhaustion, doesn’t it mean that the JVM can be left in an unrecoverable state?

See JDK-8067946. That seems to indicate on some platforms, the JVM is unable to generate a StackOverflowError and will simply crash. Therefore it seems unsafe to rely upon catching a StackOverflowError as a means of mitigating an issue.

Fair enough - although it works OK in my environment, throwing StackOverflowError as expected, other platforms may behave in a different way. Now that I have the unit tests, only the implementation is left to do.

Dunno if it would be worth noting that this means the original fix for CVE-2022-45690 could be considered incomplete, since the JVM could still crash in some circumstances?

[norrisjeremy]

FYI, another StackOverflowError, based upon dromara/hutool#2749:

$ cat poc.java
public class poc {
  public static void main(String[] args) {
    java.util.Map<String, Object> map = new java.util.HashMap<>(1, 1f);
    java.util.Map<String, Object> node = map;
    for (int i = 0; i < 10000; i++) {
      node = (java.util.Map<String, Object>) node.computeIfAbsent("a", k -> new java.util.HashMap<String, Object>(1, 1f));
    }
    node.put("a", 1);
    org.json.JSONObject jsonObject = new org.json.JSONObject(map);
    System.out.println(jsonObject.toString());
  }
}

$ java -XX:MaxJavaStackTraceDepth=12 -cp json-20220924.jar poc.java
Note: poc.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
Exception in thread "main" java.lang.StackOverflowError
	at org.json.JSONObject.<init>(JSONObject.java:284)
	at org.json.JSONObject.wrap(JSONObject.java:2480)
	at org.json.JSONObject.wrap(JSONObject.java:2452)
	at org.json.JSONObject.<init>(JSONObject.java:291)
	at org.json.JSONObject.wrap(JSONObject.java:2480)

[norrisjeremy]

I also think toString() could lead to StackOverflowError, because it too can have nested recursion?

 public String toString()
  public String toString(int indentFactor)
    public Writer write(Writer writer, int indentFactor, int indent)
      static final Writer writeValue(Writer writer, Object value, int indentFactor, int indent)
        public Writer write(Writer writer, int indentFactor, int indent)
          static final Writer writeValue(Writer writer, Object value, int indentFactor, int indent)
            public Writer write(Writer writer, int indentFactor, int indent)
              ...

[norrisjeremy]

I also think toString() could lead to StackOverflowError, because it too can have nested recursion?

 public String toString()
  public String toString(int indentFactor)
    public Writer write(Writer writer, int indentFactor, int indent)
      static final Writer writeValue(Writer writer, Object value, int indentFactor, int indent)
        public Writer write(Writer writer, int indentFactor, int indent)
          static final Writer writeValue(Writer writer, Object value, int indentFactor, int indent)
            public Writer write(Writer writer, int indentFactor, int indent)
              ...

$ cat poc.java
public class poc {
  public static void main(String[] args) {
    org.json.JSONObject jsonObject = new org.json.JSONObject();
    jsonObject.put("a", 1);
    for (int i = 0; i < 10000; i++) {
      jsonObject = jsonObject.put("a", jsonObject);
    }
    System.out.println(jsonObject.toString());
  }
}

$ java -XX:MaxJavaStackTraceDepth=12 -cp json-20220924.jar poc.java
Exception in thread "main" java.lang.StackOverflowError
	at org.json.JSONObject.quote(JSONObject.java:2031)
	at org.json.JSONObject.quote(JSONObject.java:2011)
	at org.json.JSONObject.write(JSONObject.java:2605)
	at org.json.JSONObject.writeValue(JSONObject.java:2544)
	at org.json.JSONObject.write(JSONObject.java:2611)

[cleydyr]

@cleydyr I think the risk of missing something in a complete rewrite of the parser would outweigh the benefit of fixing the stack overflow.

I didn't do a complete rewrite of the parser. I made some refactorings in the beginning and rearranged the parsing code to emulate recursive calls with ArrayDeque of ParsingContext (which is a class for holding local variables and the point in the parsing process where the parser is).

(The schema in https://www.json.org/json-en.html helped a lot.)

I covered both JSONML and JSONArray/JSONObject with my fix. It's passing all tests (though, of course, I removed the tests that counted on the code StackOverflow being thrown). I'll send you a PR so that you have a look at it.