government / src / policy / strict_test.go

@ 6025dda55b1abdf77b71aa1d3aa49f2f5b7180b5 | history


package policy

import (
	"crypto/x509"
	"errors"
	"os"
	"reflect"
	"strings"
	"testing"

	"nmyk.io/government/ast"
	"nmyk.io/government/internal/lisptest"
	"nmyk.io/government/lisp2gov"
	"nmyk.io/government/ratify"
	"nmyk.io/government/sexpr"
)

// loadCerts compiles src and returns its certs in order. Policy processing
// never looks at signatures, so tests may edit these certs freely.
func loadCerts(t *testing.T, src string) []*x509.Certificate {
	t.Helper()
	out, err := lisp2gov.Compile(src, lisp2gov.Options{})
	if err != nil {
		t.Fatal(err)
	}
	certs, err := ratify.Ratify(out, ratify.Options{At: ratifyTime})
	if err != nil {
		t.Fatal(err)
	}
	return certs
}

// edited returns a copy of certs whose cert i is a copy that f may change.
func edited(certs []*x509.Certificate, i int, f func(c *x509.Certificate)) []*x509.Certificate {
	out := append([]*x509.Certificate(nil), certs...)
	c := *certs[i]
	c.Policies = append([]x509.OID(nil), c.Policies...)
	c.PolicyMappings = append([]x509.PolicyMapping(nil), c.PolicyMappings...)
	f(&c)
	out[i] = &c
	return out
}

// decode runs the rest of the way to a program: graph, layers, tree,
// values.
func decode(certs []*x509.Certificate) ([]sexpr.Value, error) {
	g, err := Program(certs, Options{})
	if err != nil {
		return nil, err
	}
	layers, err := g.Layers()
	if err != nil {
		return nil, err
	}
	tree, err := ast.Unlayer(layers)
	if err != nil {
		return nil, err
	}
	forms, _, err := ast.FromTree(tree)
	return forms, err
}

func TestTestdataDecodesToItsSource(t *testing.T) {
	files, _ := lisptest.Files()
	examples, _ := lisptest.Examples()
	files = append(files, examples...)
	for _, file := range files {
		src, err := os.ReadFile(file)
		if err != nil {
			t.Fatal(err)
		}
		want, err := sexpr.ReadAll(string(src))
		if err != nil {
			t.Fatal(err)
		}
		got, err := decode(loadCerts(t, string(src)))
		if err != nil {
			t.Errorf("%s: %v", file, err)
			continue
		}
		if !reflect.DeepEqual(got, want) {
			t.Errorf("%s: decoded program differs from its source", file)
		}
	}
}

func checkErr(t *testing.T, name string, err error, code, msg string) {
	t.Helper()
	var e *Error
	if !errors.As(err, &e) || e.Code != code || !strings.Contains(e.Msg, msg) {
		t.Errorf("%s: error = %v, want %s containing %q", name, err, code, msg)
	}
}

func TestStrictShape(t *testing.T) {
	certs := loadCerts(t, "(+ 1 (* 2 3))")
	plusOID := certs[1].PolicyMappings[0].SubjectDomainPolicy  // +#2, at depth 2
	timesOID := certs[2].PolicyMappings[0].SubjectDomainPolicy // *#5, at depth 3
	tests := []struct {
		name  string
		certs []*x509.Certificate
		msg   string
	}{
		{"anyPolicy in cert 1", edited(certs, 1, func(c *x509.Certificate) { c.Policies = append(c.Policies, AnyPolicy) }), "cert 1 asserts anyPolicy"},
		{"no anyPolicy in cert 2", edited(certs, 2, func(c *x509.Certificate) { c.Policies = []x509.OID{plusOID} }), "cert 2 does not assert anyPolicy"},
		{"mappings in the last cert", edited(certs, 3, func(c *x509.Certificate) { c.PolicyMappings = certs[2].PolicyMappings }), "cert 3 is the last and has mappings"},
		// *#5 belongs at depth 3; named in cert 2, no depth-1 node expects
		// it, so RFC processing would quietly drop it.
		{"policy that attaches to nothing", edited(certs, 2, func(c *x509.Certificate) { c.Policies = append(c.Policies, timesOID) }), "orphaned policy GOV.0.5.23 at depth 2"},
		{"mapping from a policy with no node", edited(certs, 2, func(c *x509.Certificate) {
			c.PolicyMappings = append(c.PolicyMappings, x509.PolicyMapping{IssuerDomainPolicy: timesOID, SubjectDomainPolicy: certs[1].Policies[0]})
		}), "orphaned mapping GOV.0.5.23 -> GOV.0.1.1 in cert 2: GOV.0.5.23 is not a node at depth 2"},
		{"a policy outside GOV", edited(certs, 1, func(c *x509.Certificate) { c.Policies = append(c.Policies, mustOID("1.2.3")) }), "not under"},
	}
	for _, tt := range tests {
		_, err := Program(tt.certs, Options{})
		checkErr(t, tt.name, err, ErrPolicy, tt.msg)
	}
}

// TestDeletingAMapping is the point of the strict check: losing a mapping
// must be an error, not a shorter program. It drops each mapping of a
// program in turn. The one loss nothing can see is the subtree holding the
// highest ids, as long as its parent keeps another element; this test
// lists those cases rather than hiding them.
func TestDeletingAMapping(t *testing.T) {
	src := "(define f (lambda (x) (* x (+ x 1)))) (f 2)"
	certs := loadCerts(t, src)
	tree, err := ast.ToTree(mustRead(t, src))
	if err != nil {
		t.Fatal(err)
	}
	subtree := map[uint64][2]uint64{} // id -> [first id, last id] of its subtree
	var walk func(n *ast.Node) uint64
	walk = func(n *ast.Node) uint64 {
		last := n.ID
		for _, c := range n.Children {
			last = walk(c)
		}
		subtree[n.ID] = [2]uint64{n.ID, last}
		return last
	}
	for _, f := range tree.Forms {
		walk(f)
	}
	maxID := subtree[tree.Forms[len(tree.Forms)-1].ID][1]

	var silent []string
	for i := 1; i < len(certs)-1; i++ {
		for j, m := range certs[i].PolicyMappings {
			_, childID, _, _ := ast.DecodeOID(m.SubjectDomainPolicy)
			parentKeepsAnElement := false
			for k, other := range certs[i].PolicyMappings {
				if k != j && other.IssuerDomainPolicy.Equal(m.IssuerDomainPolicy) {
					parentKeepsAnElement = true
				}
			}
			invisible := subtree[childID][1] == maxID && parentKeepsAnElement

			dropped := edited(certs, i, func(c *x509.Certificate) {
				c.PolicyMappings = append(c.PolicyMappings[:j:j], c.PolicyMappings[j+1:]...)
			})
			_, err := decode(dropped)
			name := short(m.IssuerDomainPolicy) + " -> " + short(m.SubjectDomainPolicy)
			switch {
			case invisible && err != nil:
				t.Errorf("%s: expected an undetectable loss, got %v", name, err)
			case invisible:
				silent = append(silent, name)
			case err == nil:
				t.Errorf("%s: dropping it gave a shorter program, not an error", name)
			}
		}
	}
	// The undetectable cases are the last element of each list on the
	// program's rightmost edge whose list keeps another element: here only
	// the 2 in (f 2), node 17.
	if len(silent) != 1 || !strings.HasSuffix(silent[0], "GOV.2.17.50") {
		t.Errorf("undetectable losses: %v, want only the mapping to 2#17", silent)
	}
}

func TestNodeBudget(t *testing.T) {
	certs := loadCerts(t, "(+ 1 (* 2 3))")
	// The graph holds 9 nodes below the root: 1 + 3 + 5.
	if _, err := Program(certs, Options{MaxNodes: 9}); err != nil {
		t.Errorf("budget 9: %v", err)
	}
	_, err := Program(certs, Options{MaxNodes: 8})
	checkErr(t, "budget 8", err, ErrTooLarge, "depth 3")
}

func mustRead(t *testing.T, src string) []sexpr.Value {
	t.Helper()
	forms, err := sexpr.ReadAll(src)
	if err != nil {
		t.Fatal(err)
	}
	return forms
}