@ 4f9fbfd716661e42b7cf2b9f9c44cd9aa9ff450d | 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)
}