blob: d08d955eaf91155135deeea265a3b3111d4b55da [file] [log] [blame]
// 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)
}
}
}
}