go/client/client_test.go

// Copyright 2016 The Roughtime Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License. */

package main

import (
	"crypto/rand"
	"encoding/json"
	"math/big"
	"net"
	"strconv"
	"sync"
	"testing"
	"time"

	"golang.org/x/crypto/ed25519"
	"roughtime.googlesource.com/go/config"
	"roughtime.googlesource.com/go/protocol"
)

const (
	nonsenseReply = ^time.Duration(0)
	maxRadius     = 10 * time.Second
)

type timeSpan struct {
	midpoint uint64
	radius   time.Duration
}

var timeEstablishmentTests = []struct {
	quorum                   int
	times                    []timeSpan
	shouldEstablish          bool
	shouldSignalMisbehaviour bool
	shouldHaveErrors         []int
}{
	{
		quorum: 1,
		times: []timeSpan{
			timeSpan{10, 5},
		},
		shouldEstablish: true,
	},
	{
		quorum: 1,
		times: []timeSpan{
			timeSpan{10, 5},
			timeSpan{20, 5},
		},
		shouldEstablish: true,
	},
	{
		quorum: 2,
		times: []timeSpan{
			timeSpan{100e6, maxRadius},
			timeSpan{200e6, maxRadius},
		},
		shouldEstablish: false,
	},
	{
		quorum: 2,
		times: []timeSpan{
			timeSpan{175e6, maxRadius},
			timeSpan{200e6, maxRadius},
			timeSpan{201e6, maxRadius},
		},
		shouldEstablish: true,
	},
	{
		quorum: 3,
		times: []timeSpan{
			timeSpan{100e6, maxRadius},
			timeSpan{101e6, maxRadius},
			timeSpan{102e6, maxRadius},
		},
		shouldEstablish: true,
	},
	{
		quorum: 3,
		times: []timeSpan{
			timeSpan{175e6, maxRadius},
			timeSpan{175e6, maxRadius},
			timeSpan{200e6, maxRadius},
			timeSpan{200e6, maxRadius},
			timeSpan{200e6, maxRadius},
			timeSpan{200e6, maxRadius},
			timeSpan{200e6, maxRadius},
			timeSpan{200e6, maxRadius},
			timeSpan{200e6, maxRadius},
			timeSpan{175e6, maxRadius},
		},
		shouldEstablish: true,
	},
	{
		// An excessive radius should be rejected as invalid.
		quorum: 3,
		times: []timeSpan{
			timeSpan{200e6, 1 * time.Hour},
			timeSpan{200e6, maxRadius},
			timeSpan{200e6, maxRadius},
		},
		shouldHaveErrors: []int{0},
		shouldEstablish:  false,
	},
	{
		// A zero radius is acceptable if the midpoint is reasonable.
		quorum: 3,
		times: []timeSpan{
			timeSpan{200e6, 0},
			timeSpan{200e6, maxRadius},
			timeSpan{200e6, maxRadius},
		},
		shouldEstablish: true,
	},
	{
		quorum: 3,
		times: []timeSpan{
			timeSpan{201e6, 1 * time.Second},
			timeSpan{201e6, 2 * time.Second},
			timeSpan{201e6, 3 * time.Second},
		},
		shouldEstablish: true,
	},
	{
		quorum: 2,
		times: []timeSpan{
			timeSpan{100e6, maxRadius},
			timeSpan{200e6, maxRadius},
			timeSpan{200e6, maxRadius},
		},
		shouldEstablish:          true,
		shouldSignalMisbehaviour: true,
	},
	{
		quorum: 2,
		times: []timeSpan{
			timeSpan{0, nonsenseReply},
			timeSpan{0, nonsenseReply},
			timeSpan{200e6, maxRadius},
			timeSpan{200e6, maxRadius},
		},
		shouldEstablish:  true,
		shouldHaveErrors: []int{0, 1},
	},
}

func TestEstablishment(t *testing.T) {
	client := &Client{
		nowFunc: func() time.Duration {
			// The monotonic clock always returns zero to avoid
			// query latency affecting the results.
			return 0
		},

		Permutation: func(n int) []int {
			// The permutation is fixed so that "servers" will be
			// queried in the order given.
			ret := make([]int, n)
			for i := range ret {
				ret[i] = i
			}

			return ret
		},

		MaxRadius:     maxRadius,
		MaxDifference: 60 * time.Second,
		QueryTimeout:  30 * time.Second,
		NumQueries:    1,
	}

	var waitGroup sync.WaitGroup
	defer waitGroup.Wait()

	for i, test := range timeEstablishmentTests {
		var handles []*serverHandle
		var servers []config.Server

		for j, span := range test.times {
			handle, err := startServer(&waitGroup, span)
			if err != nil {
				t.Fatal(err)
			}

			handles = append(handles, handle)
			servers = append(servers, config.Server{
				Name:      strconv.Itoa(j),
				PublicKey: handle.publicKey,
				Addresses: []config.ServerAddress{
					config.ServerAddress{
						Protocol: "udp",
						Address:  handle.addr.String(),
					},
				},
			})
			defer handle.Close()
		}

		var chain config.Chain
		result, err := client.EstablishTime(&chain, test.quorum, servers)
		if err != nil {
			t.Fatal(err)
		}

		if test.shouldEstablish != (result.MonoUTCDelta != nil) {
			t.Errorf("#%d: time establishment mismatch, wanted: %t", i, test.shouldEstablish)
		}

		if test.shouldEstablish && len(chain.Links) < test.quorum {
			t.Errorf("#%d: chain too short (%d) to be valid", i, len(chain.Links))
		}

		// Serialize and reparse chain to ensure that it's valid.
		chainBytes, err := json.MarshalIndent(chain, "", "  ")
		if err != nil {
			t.Fatal(err)
		}

		if _, err := LoadChain(chainBytes); err != nil {
			t.Errorf("#%d: resulting chain does not parse: %s", i, err)
		}

		if test.shouldSignalMisbehaviour != result.OutOfRangeAnswer {
			t.Errorf("#%d: misbehaviour mismatch, wanted: %t", i, test.shouldSignalMisbehaviour)
		}

		if len(result.ServerErrors) != len(test.shouldHaveErrors) {
			t.Errorf("#%d: server errors mismatch, got %#v but wanted errors from #%v", i, result.ServerErrors, test.shouldHaveErrors)
		}

		for _, serverNumber := range test.shouldHaveErrors {
			if _, ok := result.ServerErrors[strconv.Itoa(serverNumber)]; !ok {
				t.Errorf("#%d: missing error for server %d", i, serverNumber)
			}
		}
	}
}

type serverHandle struct {
	publicKey []byte
	addr      *net.UDPAddr
}

func (handle *serverHandle) Close() {
	conn, err := net.DialUDP("udp", nil, handle.addr)
	if err != nil {
		panic(err)
	}

	conn.Write([]byte{0})
}

func startServer(wg *sync.WaitGroup, span timeSpan) (*serverHandle, error) {
	rootPublic, rootPrivate, err := ed25519.GenerateKey(rand.Reader)
	if err != nil {
		return nil, err
	}

	onlinePublicKey, onlinePrivateKey, err := ed25519.GenerateKey(rand.Reader)
	if err != nil {
		return nil, err
	}

	cert, err := protocol.CreateCertificate(0, ^uint64(0), onlinePublicKey, rootPrivate)
	if err != nil {
		return nil, err
	}

	conn, err := net.ListenUDP("udp", &net.UDPAddr{IP: net.IPv4(127, 0, 0, 1), Port: 0})
	if err != nil {
		return nil, err
	}

	localAddr, ok := conn.LocalAddr().(*net.UDPAddr)
	if !ok {
		panic("not a UDP address")
	}

	wg.Add(1)

	go func() {
		var packetBuf [protocol.MinRequestSize]byte
		defer wg.Done()

		for {
			n, sourceAddr, err := conn.ReadFromUDP(packetBuf[:])
			if err != nil {
				panic(err)
			}

			if n == 1 && packetBuf[0] == 0 {
				return
			}

			if span.radius == nonsenseReply {
				conn.WriteToUDP([]byte{1, 2, 3, 4, 5}, sourceAddr)
				continue
			}

			packet, err := protocol.Decode(packetBuf[:n])
			if err != nil {
				println(n)
				panic(err)
			}

			nonce, ok := packet[protocol.TagNonce]
			if !ok || len(nonce) != protocol.NonceSize {
				panic("missing nonce")
			}

			replies, err := protocol.CreateReplies([][]byte{nonce}, span.midpoint, uint32(span.radius/time.Microsecond), cert, onlinePrivateKey)
			if err != nil {
				panic(err)
			}

			conn.WriteToUDP(replies[0], sourceAddr)
		}
	}()

	return &serverHandle{
		publicKey: rootPublic,
		addr:      localAddr,
	}, nil
}

func TestFindNOverlapping(t *testing.T) {
	type sample struct {
		min int64
		max int64
	}
	testcases := []struct {
		samples []sample
		maxN    int
	}{
		{
			samples: []sample{
				{0, 2},
				{1, 3},
			},
			maxN: 2,
		},
		{
			samples: []sample{
				{0, 2},
				{1, 3},
				{4, 5},
			},
			maxN: 2,
		},
		{
			samples: []sample{
				{0, 10},
				{1, 2},
				{5, 10},
				{6, 10},
			},
			maxN: 3,
		},
	}
	for i, tc := range testcases {
		samples := make([]*timeSample, len(tc.samples))
		for j, s := range tc.samples {
			samples[j] = &timeSample{
				base: big.NewInt(0),
				min:  big.NewInt(s.min),
				max:  big.NewInt(s.max),
			}
		}
		for n := 1; n <= len(samples); n++ {
			expectedOk := n <= tc.maxN
			_, ok := findNOverlapping(samples, n)
			if ok != expectedOk {
				t.Errorf("#%d: findNOverlapping(n=%d) returned %v, wanted %v", i, n, ok, expectedOk)
			}
		}
	}
}