Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

encoding/json: detect circular data structures when encoding #10769

Closed
bep opened this issue May 10, 2015 · 14 comments
Closed

encoding/json: detect circular data structures when encoding #10769

bep opened this issue May 10, 2015 · 14 comments
Labels
FrozenDueToAge help wanted NeedsFix The path to resolution is known, but the work has not been done.
Milestone

Comments

@bep
Copy link
Contributor

bep commented May 10, 2015

The following program panics.

OS: Linux
Go version: tip and 1.4.2

I searched, but didn't find this in here.

/cc @dvyukov go-fuzz

package main

import (
    "html/template"
    "io/ioutil"
)

func main() {
    t, err := template.New("foo").Parse(data)
    if err != nil {
        return
    }

    a := &A{}
    a.B1 = &B{a}
    ping := &Ping{a}

    t.Execute(ioutil.Discard, ping)
}

var data = "<script>{{ .Pong }}</script>"

type Ping struct {
    Pong *A
}

type A struct {
    B1 *B
}

type B struct {
    A1 *A
}
runtime: goroutine stack exceeds 1000000000-byte limit
fatal error: stack overflow

runtime stack:
runtime.throw(0x5e7490, 0xe)
    /home/bep/dev/golang/go/src/runtime/panic.go:543 +0x96
runtime.newstack()
    /home/bep/dev/golang/go/src/runtime/stack1.go:744 +0xb3f
runtime.morestack()
    /home/bep/dev/golang/go/src/runtime/asm_amd64.s:330 +0x82

goroutine 1 [stack growth]:
encoding/json.(*structEncoder).encode(0xc208012e40, 0xc208095810, 0x585560, 0xc208028038, 0xd9, 0x0)
    /home/bep/dev/golang/go/src/encoding/json/encode.go:569 fp=0xc2280fa280 sp=0xc2280fa278
encoding/json.(*structEncoder).(encoding/json.encode)-fm(0xc208095810, 0x585560, 0xc208028038, 0xd9, 0x5bf900)
    /home/bep/dev/golang/go/src/encoding/json/encode.go:598 +0x58 fp=0xc2280fa2b8 sp=0xc2280fa280
encoding/json.typeEncoder.func1(0xc208095810, 0x585560, 0xc208028038, 0xd9, 0xc208028000)
    /home/bep/dev/golang/go/src/encoding/json/encode.go:336 +0x6d fp=0xc2280fa2f0 sp=0xc2280fa2b8
encoding/json.(*ptrEncoder).encode(0xc208028088, 0xc208095810, 0x531e60, 0xc208028040, 0xd6, 0x4c5200)
    /home/bep/dev/golang/go/src/encoding/json/encode.go:706 +0xed fp=0xc2280fa340 sp=0xc2280fa2f0
encoding/json.(*ptrEncoder).(encoding/json.encode)-fm(0xc208095810, 0x531e60, 0xc208028040, 0xd6, 0x0)
    /home/bep/dev/golang/go/src/encoding/json/encode.go:711 +0x58 fp=0xc2280fa378 sp=0xc2280fa340
encoding/json.(*structEncoder).encode(0xc208012f30, 0xc208095810, 0x585620, 0xc208028040, 0xd9, 0x4aad00)
    /home/bep/dev/golang/go/src/encoding/json/encode.go:584 +0x2c3 fp=0xc2280fa520 sp=0xc2280fa378
encoding/json.(*structEncoder).(encoding/json.encode)-fm(0xc208095810, 0x585620, 0xc208028040, 0xd9, 0xc208028000)
    /home/bep/dev/golang/go/src/encoding/json/encode.go:598 +0x58 fp=0xc2280fa558 sp=0xc2280fa520
encoding/json.(*ptrEncoder).encode(0xc208028090, 0xc208095810, 0x531ec0, 0xc208028038, 0xd6, 0x4c5200)
    /home/bep/dev/g
@dvyukov
Copy link
Member

dvyukov commented May 10, 2015

Isn't it a documented encoding/json limitation? What would be the expected behavior of such program?

@bep
Copy link
Contributor Author

bep commented May 10, 2015

If it is a documented limitation I would strongly expect it to return an informative ERROR - and not go into a glowing hot CPU and then panic.

It should be possible to detect these cycles earlier.

In this case it's triggered from a Go template -- go template end users don't understand cyclic object graphs until it's spelled out for them.

@bep
Copy link
Contributor Author

bep commented May 10, 2015

The json package says:

JSON cannot represent cyclic data structures and Marshal does not
handle them.  Passing cyclic structures to Marshal will result in
an infinite recursion.

The template package says:

 See package json to understand how non-string content is marshalled for embedding in JavaScript contexts. 

So, I guess you are kind of correct when you say that this is a documented limitation ... But one could argue that this opens the html templates up for code injection (DDoS), which the documentation says it protects against.

@adg
Copy link
Contributor

adg commented May 10, 2015

I don't think it's reasonable to expect the template package to mitigate all possible forms of pathological input. I'm sure it's possible, but am having a hard time imagining a real program that would allow a user to construct the circular graph that triggers this behaviour.

To mitigate this issue we would necessarily complicate and slow down the JSON encoder, which is something we have decided not to do.

Thanks for the report.

@adg adg closed this as completed May 10, 2015
@bep
Copy link
Contributor Author

bep commented May 10, 2015

Up to you.

BTW, this issue was found by a user using a real program. He didn't have to "construct the circular graph", it was there in the context. Maybe it shouldn't have been, but circular refs are very common -- I wouldn't call them "pathological input".

@adg
Copy link
Contributor

adg commented May 10, 2015

How could it be anything other than pathological? What is a reasonable way to JSON encode a circular data structure?

@bradfitz
Copy link
Contributor

It wouldn't be too hard or slow down the JSON encoder much to catch circular references. (and if we catch one, we can just return an error)

I think we can leave this open.

@bradfitz bradfitz reopened this May 10, 2015
@adg adg changed the title encoding/json: stack overflow encoding/json: detect circular data structures when encoding May 10, 2015
@bep
Copy link
Contributor Author

bep commented May 10, 2015

That I agree about.

The Go program in question is Hugo, a static site generator. It uses Go templates. In the template context is the Site. Site has a list of Pages; each Page has a reference to the Site it belongs to.

So a person does this in a template (gohugoio/hugo#1123):

<script>
{{ .Site }}
</script>

And BAM!

I would agree that this usage is "pathological", but people do stupid (and some do evil) things.

And from Hugo's point of view, to fix this, we must remove the circular reference from Page (and maybe some other), but that would make the software useless.

@gopherbot
Copy link
Contributor

Change https://golang.org/cl/187920 mentions this issue: encoding/json: error when encoding a pointer cycle

@ORESoftware
Copy link

just return an error if there is a circular reference

@lujjjh
Copy link
Contributor

lujjjh commented Aug 13, 2020

The documentation says:

JSON cannot represent cyclic data structures and Marshal does not handle them. Passing cyclic structures to Marshal will result in an error.

However, there are still cases result in an infinite recursion in Go 1.15.

It seems that 64c9ee9 does not handle cyclic maps or slices:

package main

import "encoding/json"

func main() {
	x := map[string]interface{}{}
	x["x"] = x
	json.Marshal(x)
}

and

package main

import "encoding/json"

func main() {
	x := []interface{}{nil}
	x[0] = x
	json.Marshal(x)
}

@davecheney
Copy link
Contributor

@lujjjh this issue was closed approximately 10 months ago. Would you please raise a new issue if there is a problem in the current release of Go. Thank you.

@eaglexiang
Copy link

quote about circle references check is:

// JSON cannot represent cyclic data structures and Marshal does not
// handle them. Passing cyclic structures to Marshal will result in
// an error.

it said result in an error but not infinite recursion any more, owing to which "panic while map marshalling" may be seen as a bug?

@lujjjh
Copy link
Contributor

lujjjh commented Aug 13, 2020

@lujjjh this issue was closed approximately 10 months ago. Would you please raise a new issue if there is a problem in the current release of Go. Thank you.

Thanks for your reply.

I have raised a new issue #40745.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge help wanted NeedsFix The path to resolution is known, but the work has not been done.
Projects
None yet
Development

No branches or pull requests