The ancient world before computers had stacks or heaps

Re:The ancient world before computers had stacks or heaps by jcgrillo on Wednesday April 03, 2024 @06:45PM (#39924286)

For a fun time, make a nested json blob about 1000 layers deep[1] and in python:

  with open('lulz.json') as ayy_lmao:
      oops = json.load(ayy_lmao)

If you parse arbitrary json bytes from the Internet (for example, if you have some public Python API with no auth) then you have given the world a fun little stacktrace generator, and a way to lessen your server room's heating bill.

EDIT: btw you can do the same thing in rust's serde_json if the type you're deserializing into somehow supports the nesting, but you'd have to work for it.

EDIT2: the only (decent) way I can think to mitigate this in the python app's case is to enforce a sufficiently restrictive Content-Length at the edge, which obviously isn't possible of you expect blobs O(100Kb) uncompressed. Or you could pre-parse to detect nesting.

[1] EDIT3: on my machine in ipython right now it's 1485:

  import json

  def nest(d):
      return '{"k":' + str(d) + '}'

  def make_mess(n):
      v = 1
      for _ in range(n):
          v = nest(v)
      return v

  json.loads(make_mess(1485))  # boom

[ Parent | on HN ]

Re:The ancient world before computers had stacks or heaps by munificent on Wednesday April 03, 2024 @07:21PM (#39924637)

Parsing untrusted input on a machine where failure could affect someone other than the person who provided the input is definitely a known case to be mindful of.

You'll want to cap the maximum allowed nesting depth. Even if not using recursion, you probably don't want untrusted input to be able to make your stack data structure allocate arbitrary amounts of memory.

If you do put a nesting limit in, you can do that equally well using an actual stack or recursion. (For example, I believe v8 still uses recursive descent for parsing JSON and JavaScript. It detects and handles stack overflows to ensure that untrusted input can't blow the stack and crash. I'm not sure if it's using a hardcoded nesting limit or actually trapping the stack/heap collision somehow.)

[ Parent | on HN ]

Re:The ancient world before computers had stacks or heaps by jcgrillo on Wednesday April 03, 2024 @07:58PM (#39924898)

Yes, unfortunately in the python case the standard library's json parser has no way to configure a reasonable limit. It'll just consume stack frames until it hits the interpeter's recursion limit. And, as has been mentioned elsewhere, python stack frames are expensive for a variety of reasons.

I've run into similar issues with recursive code in java. The story gets better in C or rust, but there wre still sharp edges. I guess there are sharp edges everywhere though...

[ Parent | on HN ]

Re:The ancient world before computers had stacks or heaps by Joel_Mckay on Wednesday April 03, 2024 @07:54PM (#39924874)

You mean like the reply depth limit in forums like YC.

Shouldn't you stick to a depth-first branch reply limit until moving to the next fork.

I want to respect your beliefs. =)

[ Parent | on HN ]

Re:The ancient world before computers had stacks or heaps by Joel_Mckay on Wednesday April 03, 2024 @07:03PM (#39924444)

In general, most json/bson parsers like libbson have a rather shallow depth restriction (xerces also constrains this if I recall.)

And yeah, recursion is avoided in some shops for good reasons.

[ Parent | on HN ]