government / stress_test.go

@ 141e6346099989c841d4af3293458485a50c86e7 | history


package government_test

import (
	"bytes"
	"errors"
	"fmt"
	"reflect"
	"strings"
	"testing"
	"time"

	"government/lisp2gov"
	"government/policy"
	"government/program"
	"government/ratify"
	"government/sexpr"
)

// deep nests (+ 1 ...) until the program is depth certs deep: each list
// puts its elements one cert lower, and the innermost 0 sits at the bottom.
func deep(depth int) string {
	return strings.Repeat("(+ 1 ", depth-1) + "0" + strings.Repeat(")", depth-1)
}

func numbers(n int) string {
	var b strings.Builder
	for i := 1; i <= n; i++ {
		fmt.Fprintf(&b, " %d", i)
	}
	return b.String()
}

// stress runs src through everything: compile, ratify, policy processing,
// decode, evaluate. It checks the decoded forms are the source's and
// returns the program and what it printed.
func stress(t *testing.T, src string, opts program.Options) (*program.Program, string, []byte) {
	t.Helper()
	data, err := lisp2gov.Compile(src, lisp2gov.Options{})
	if err != nil {
		t.Fatal(err)
	}
	opts.At = time.Now()
	p, err := program.Load(data, opts)
	if err != nil {
		t.Fatal(err)
	}
	want, err := sexpr.ReadAll(src)
	if err != nil {
		t.Fatal(err)
	}
	if !reflect.DeepEqual(p.Forms, want) {
		t.Error("the program decodes to different forms")
	}
	var out bytes.Buffer
	if err := p.Run(&out); err != nil {
		t.Fatal(p.Describe(err))
	}
	return p, out.String(), data
}

func TestStressDeep(t *testing.T) {
	start := time.Now()
	p, out, data := stress(t, deep(200), program.Options{})
	if p.Depth() != 200 || len(p.Certs) != 201 {
		t.Errorf("depth %d in %d certs, want 200 in 201", p.Depth(), len(p.Certs))
	}
	if out != "199\n" {
		t.Errorf("printed %q", out)
	}
	t.Logf("200 deep: %d bytes, %d nodes, %v", len(data), p.Nodes, time.Since(start))
}

func TestStressWide(t *testing.T) {
	tests := []struct {
		name, src, want string
	}{
		{"1,000 arguments", "(+" + numbers(1000) + ")", "500500\n"},
		{"1,000-element quoted list", "(car (cdr '(" + numbers(1000) + ")))", "2\n"},
		{"1,000 top-level forms", numbers(1000), strings.ReplaceAll(strings.TrimSpace(numbers(1000)), " ", "\n") + "\n"},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			start := time.Now()
			p, out, data := stress(t, tt.src, program.Options{})
			if out != tt.want {
				t.Errorf("printed %.40q...", out)
			}
			t.Logf("%d bytes, %d nodes, depth %d, %v", len(data), p.Nodes, p.Depth(), time.Since(start))
		})
	}
}

// graphSize is how many nodes policy processing makes for a program,
// counting the validator's copies: the number --max-nodes limits.
func graphSize(t *testing.T, data []byte) int {
	t.Helper()
	certs, err := ratify.Ratify(data, ratify.Options{At: time.Now()})
	if err != nil {
		t.Fatal(err)
	}
	g, err := policy.Program(certs, policy.Options{})
	if err != nil {
		t.Fatal(err)
	}
	n := 0
	for _, level := range g.Levels {
		n += len(level)
	}
	return n - 1 // the anyPolicy root is not made under the budget
}

// TestMaxNodesIsExact: a budget of exactly the graph's size is enough, and
// one less is refused.
func TestMaxNodesIsExact(t *testing.T) {
	// Not "42": its graph is one node, and a budget of 0 means the default.
	for _, src := range []string{"(+ 1 (* 2 3))", deep(50), "(+" + numbers(100) + ")"} {
		data, err := lisp2gov.Compile(src, lisp2gov.Options{})
		if err != nil {
			t.Fatal(err)
		}
		n := graphSize(t, data)
		if _, err := program.Load(data, program.Options{At: time.Now(), MaxNodes: n}); err != nil {
			t.Errorf("%.20s: budget %d refused: %v", src, n, err)
		}
		_, err = program.Load(data, program.Options{At: time.Now(), MaxNodes: n - 1})
		var pe *policy.Error
		if !errors.As(err, &pe) || pe.Code != policy.ErrTooLarge {
			t.Errorf("%.20s: budget %d of %d: %v, want E-TOO-LARGE", src, n-1, n, err)
		}
	}
}

// TestSmallFileLargeGraph is the attack the budget is for: every atom
// above the bottom is copied down once per cert, so a few thousand
// top-level atoms beside one deep form ask for millions of graph nodes
// from a file of a few hundred kilobytes. The default budget must refuse
// it, and quickly, without building the graph first.
func TestSmallFileLargeGraph(t *testing.T) {
	src := numbers(6000) + "\n" + deep(200)
	data, err := lisp2gov.Compile(src, lisp2gov.Options{})
	if err != nil {
		t.Fatal(err)
	}
	start := time.Now()
	_, err = program.Load(data, program.Options{At: time.Now()})
	var pe *policy.Error
	if !errors.As(err, &pe) || pe.Code != policy.ErrTooLarge {
		t.Fatalf("%v, want E-TOO-LARGE", err)
	}
	t.Logf("%d-byte file asking for about %d nodes refused in %v: %v", len(data), 6000*200, time.Since(start), err)
}