protocol/vm/vm_test.go

   1 package vm
   2
   3 import (
   4         "bytes"
   5         "fmt"
   6         "os"
   7         "strings"
   8         "testing"
   9         "testing/quick"
  10
  11         "github.com/bytom/errors"
  12         "github.com/bytom/testutil"
  13 )
  14
  15 type tracebuf struct {
  16         bytes.Buffer
  17 }
  18
  19 func (t tracebuf) dump() {
  20         os.Stdout.Write(t.Bytes())
  21 }
  22
  23 // Programs that run without error.
  24 func TestProgramOK(t *testing.T) {
  25         doOKNotOK(t, true)
  26 }
  27
  28 // Programs that return an ErrFalseVMResult.
  29 func TestProgramNotOK(t *testing.T) {
  30         doOKNotOK(t, false)
  31 }
  32
  33 func doOKNotOK(t *testing.T, expectOK bool) {
  34         cases := []struct {
  35                 prog string
  36                 args [][]byte
  37         }{
  38                 {"TRUE", nil},
  39
  40                 // bitwise ops
  41                 {"INVERT 0xfef0 EQUAL", [][]byte{{0x01, 0x0f}}},
  42
  43                 {"AND 0x02 EQUAL", [][]byte{{0x03}, {0x06}}},
  44                 {"AND 0x02 EQUAL", [][]byte{{0x03, 0xff}, {0x06}}},
  45
  46                 {"OR 0x07 EQUAL", [][]byte{{0x03}, {0x06}}},
  47                 {"OR 0x07ff EQUAL", [][]byte{{0x03, 0xff}, {0x06}}},
  48
  49                 {"XOR 0x05 EQUAL", [][]byte{{0x03}, {0x06}}},
  50                 {"XOR 0x05ff EQUAL", [][]byte{{0x03, 0xff}, {0x06}}},
  51
  52                 // numeric and logical ops
  53                 {"1ADD 2 NUMEQUAL", [][]byte{Int64Bytes(1)}},
  54                 {"1ADD 0 NUMEQUAL", [][]byte{Int64Bytes(-1)}},
  55
  56                 {"1SUB 1 NUMEQUAL", [][]byte{Int64Bytes(2)}},
  57                 {"1SUB -1 NUMEQUAL", [][]byte{Int64Bytes(0)}},
  58
  59                 {"2MUL 2 NUMEQUAL", [][]byte{Int64Bytes(1)}},
  60                 {"2MUL 0 NUMEQUAL", [][]byte{Int64Bytes(0)}},
  61                 {"2MUL -2 NUMEQUAL", [][]byte{Int64Bytes(-1)}},
  62
  63                 {"2DIV 1 NUMEQUAL", [][]byte{Int64Bytes(2)}},
  64                 {"2DIV 0 NUMEQUAL", [][]byte{Int64Bytes(1)}},
  65                 {"2DIV 0 NUMEQUAL", [][]byte{Int64Bytes(0)}},
  66                 {"2DIV -1 NUMEQUAL", [][]byte{Int64Bytes(-1)}},
  67                 {"2DIV -1 NUMEQUAL", [][]byte{Int64Bytes(-2)}},
  68
  69                 {"NEGATE -1 NUMEQUAL", [][]byte{Int64Bytes(1)}},
  70                 {"NEGATE 1 NUMEQUAL", [][]byte{Int64Bytes(-1)}},
  71                 {"NEGATE 0 NUMEQUAL", [][]byte{Int64Bytes(0)}},
  72
  73                 {"ABS 1 NUMEQUAL", [][]byte{Int64Bytes(1)}},
  74                 {"ABS 1 NUMEQUAL", [][]byte{Int64Bytes(-1)}},
  75                 {"ABS 0 NUMEQUAL", [][]byte{Int64Bytes(0)}},
  76
  77                 {"0NOTEQUAL", [][]byte{Int64Bytes(1)}},
  78                 {"0NOTEQUAL NOT", [][]byte{Int64Bytes(0)}},
  79
  80                 {"ADD 5 NUMEQUAL", [][]byte{Int64Bytes(2), Int64Bytes(3)}},
  81
  82                 {"SUB 2 NUMEQUAL", [][]byte{Int64Bytes(5), Int64Bytes(3)}},
  83
  84                 {"MUL 6 NUMEQUAL", [][]byte{Int64Bytes(2), Int64Bytes(3)}},
  85
  86                 {"DIV 2 NUMEQUAL", [][]byte{Int64Bytes(6), Int64Bytes(3)}},
  87
  88                 {"MOD 0 NUMEQUAL", [][]byte{Int64Bytes(6), Int64Bytes(2)}},
  89                 {"MOD 0 NUMEQUAL", [][]byte{Int64Bytes(-6), Int64Bytes(2)}},
  90                 {"MOD 0 NUMEQUAL", [][]byte{Int64Bytes(6), Int64Bytes(-2)}},
  91                 {"MOD 0 NUMEQUAL", [][]byte{Int64Bytes(-6), Int64Bytes(-2)}},
  92                 {"MOD 2 NUMEQUAL", [][]byte{Int64Bytes(12), Int64Bytes(10)}},
  93                 {"MOD 8 NUMEQUAL", [][]byte{Int64Bytes(-12), Int64Bytes(10)}},
  94                 {"MOD -8 NUMEQUAL", [][]byte{Int64Bytes(12), Int64Bytes(-10)}},
  95                 {"MOD -2 NUMEQUAL", [][]byte{Int64Bytes(-12), Int64Bytes(-10)}},
  96
  97                 {"LSHIFT 2 NUMEQUAL", [][]byte{Int64Bytes(1), Int64Bytes(1)}},
  98                 {"LSHIFT 4 NUMEQUAL", [][]byte{Int64Bytes(1), Int64Bytes(2)}},
  99                 {"LSHIFT -2 NUMEQUAL", [][]byte{Int64Bytes(-1), Int64Bytes(1)}},
 100                 {"LSHIFT -4 NUMEQUAL", [][]byte{Int64Bytes(-1), Int64Bytes(2)}},
 101
 102                 {"1 1 BOOLAND", nil},
 103                 {"1 0 BOOLAND NOT", nil},
 104                 {"0 1 BOOLAND NOT", nil},
 105                 {"0 0 BOOLAND NOT", nil},
 106
 107                 {"1 1 BOOLOR", nil},
 108                 {"1 0 BOOLOR", nil},
 109                 {"0 1 BOOLOR", nil},
 110                 {"0 0 BOOLOR NOT", nil},
 111
 112                 {"1 2 OR 3 EQUAL", nil},
 113
 114                 // splice ops
 115                 {"0 CATPUSHDATA 0x0000 EQUAL", [][]byte{{0x00}}},
 116                 {"0 0xff CATPUSHDATA 0x01ff EQUAL", nil},
 117                 {"CATPUSHDATA 0x050105 EQUAL", [][]byte{{0x05}, {0x05}}},
 118                 {"CATPUSHDATA 0xff01ff EQUAL", [][]byte{{0xff}, {0xff}}},
 119                 {"0 0xcccccc CATPUSHDATA 0x03cccccc EQUAL", nil},
 120                 {"0x05 0x05 SWAP 0xdeadbeef CATPUSHDATA DROP 0x05 EQUAL", nil},
 121                 {"0x05 0x05 SWAP 0xdeadbeef CATPUSHDATA DROP 0x05 EQUAL", nil},
 122
 123                 // // control flow ops
 124                 {"1 JUMP:7 0 1 EQUAL", nil},                                                       // jumps over 0
 125                 {"1 JUMP:$target 0 $target 1 EQUAL", nil},                                         // jumps over 0
 126                 {"1 1 JUMPIF:8 0 1 EQUAL", nil},                                                   // jumps over 0
 127                 {"1 1 JUMPIF:$target 0 $target 1 EQUAL", nil},                                     // jumps over 0
 128                 {"1 0 JUMPIF:8 0 1 EQUAL NOT", nil},                                               // doesn't jump over 0
 129                 {"1 0 JUMPIF:$target 0 $target 1 EQUAL NOT", nil},                                 // doesn't jump over 0
 130                 {"1 0 JUMPIF:1", nil},                                                             // doesn't jump, so no infinite loop
 131                 {"1 $target 0 JUMPIF:$target", nil},                                               // doesn't jump, so no infinite loop
 132                 {"4 1 JUMPIF:14 5 EQUAL JUMP:16 4 EQUAL", nil},                                    // if (true) { return x == 4; } else { return x == 5; }
 133                 {"4 1 JUMPIF:$true 5 EQUAL JUMP:$end $true 4 EQUAL $end", nil},                    // if (true) { return x == 4; } else { return x == 5; }
 134                 {"5 0 JUMPIF:14 5 EQUAL JUMP:16 4 EQUAL", nil},                                    // if (false) { return x == 4; } else { return x == 5; }
 135                 {"5 0 JUMPIF:$true 5 EQUAL JUMP:$end $true 4 $test EQUAL $end", nil},              // if (false) { return x == 4; } else { return x == 5; }
 136                 {"0 1 2 3 4 5 6 JUMP:13 DROP DUP 0 NUMNOTEQUAL JUMPIF:12 1", nil},                 // same as "0 1 2 3 4 5 6 WHILE DROP ENDWHILE 1"
 137                 {"0 1 2 3 4 5 6 JUMP:$dup $drop DROP $dup DUP 0 NUMNOTEQUAL JUMPIF:$drop 1", nil}, // same as "0 1 2 3 4 5 6 WHILE DROP ENDWHILE 1"
 138                 {"0 JUMP:7 1ADD DUP 10 LESSTHAN JUMPIF:6 10 NUMEQUAL", nil},                       // fixed version of "0 1 WHILE DROP 1ADD DUP 10 LESSTHAN ENDWHILE 10 NUMEQUAL"
 139                 {"0 JUMP:$dup $add 1ADD $dup DUP 10 LESSTHAN JUMPIF:$add 10 NUMEQUAL", nil},       // fixed version of "0 1 WHILE DROP 1ADD DUP 10 LESSTHAN ENDWHILE 10 NUMEQUAL"
 140
 141         }
 142         for i, c := range cases {
 143                 progSrc := c.prog
 144                 if !expectOK {
 145                         progSrc += " NOT"
 146                 }
 147                 prog, err := Assemble(progSrc)
 148                 if err != nil {
 149                         t.Fatal(err)
 150                 }
 151                 fmt.Printf("* case %d, prog [%s] [%x]\n", i, progSrc, prog)
 152                 trace := new(tracebuf)
 153                 TraceOut = trace
 154                 vm := &virtualMachine{
 155                         program:   prog,
 156                         runLimit:  int64(initialRunLimit),
 157                         dataStack: append([][]byte{}, c.args...),
 158                 }
 159                 err = vm.run()
 160                 if err == nil && vm.falseResult() {
 161                         err = ErrFalseVMResult
 162                 }
 163                 if expectOK && err != nil {
 164                         trace.dump()
 165                         t.Errorf("case %d [%s]: expected success, got error %s", i, progSrc, err)
 166                 } else if !expectOK && err != ErrFalseVMResult {
 167                         trace.dump()
 168                         t.Errorf("case %d [%s]: expected ErrFalseVMResult, got %s", i, progSrc, err)
 169                 }
 170         }
 171 }
 172
 173 func TestVerifyTxInput(t *testing.T) {
 174         cases := []struct {
 175                 vctx    *Context
 176                 wantErr error
 177         }{
 178                 {
 179                         vctx: &Context{
 180                                 VMVersion: 1,
 181                                 Code:      []byte{byte(OP_ADD), byte(OP_5), byte(OP_NUMEQUAL)},
 182                                 Arguments: [][]byte{{2}, {3}},
 183                         },
 184                 },
 185                 {
 186                         vctx:    &Context{VMVersion: 2},
 187                         wantErr: ErrUnsupportedVM,
 188                 },
 189                 {
 190                         vctx: &Context{
 191                                 VMVersion: 1,
 192                                 Code:      []byte{byte(OP_ADD), byte(OP_5), byte(OP_NUMEQUAL)},
 193                                 Arguments: [][]byte{make([]byte, 50001)},
 194                         },
 195                         wantErr: ErrRunLimitExceeded,
 196                 },
 197         }
 198
 199         for _, c := range cases {
 200                 gotErr := Verify(c.vctx)
 201                 if errors.Root(gotErr) != c.wantErr {
 202                         t.Errorf("VerifyTxInput(%+v) err = %v want %v", c.vctx, gotErr, c.wantErr)
 203                 }
 204         }
 205 }
 206
 207 func TestVerifyBlockHeader(t *testing.T) {
 208         consensusProg := []byte{byte(OP_ADD), byte(OP_5), byte(OP_NUMEQUAL)}
 209         context := &Context{
 210                 VMVersion: 1,
 211                 Code:      consensusProg,
 212                 Arguments: [][]byte{{2}, {3}},
 213         }
 214         gotErr := Verify(context)
 215         if gotErr != nil {
 216                 t.Errorf("unexpected error: %v", gotErr)
 217         }
 218
 219         context = &Context{
 220                 VMVersion: 1,
 221                 Arguments: [][]byte{make([]byte, 50000)},
 222         }
 223         gotErr = Verify(context)
 224         if errors.Root(gotErr) != ErrRunLimitExceeded {
 225                 t.Error("expected block to exceed run limit")
 226         }
 227 }
 228
 229 func TestRun(t *testing.T) {
 230         cases := []struct {
 231                 vm      *virtualMachine
 232                 wantErr error
 233         }{{
 234                 vm: &virtualMachine{runLimit: 50000, program: []byte{byte(OP_TRUE)}},
 235         }, {
 236                 vm:      &virtualMachine{runLimit: 50000, program: []byte{byte(OP_ADD)}},
 237                 wantErr: ErrDataStackUnderflow,
 238         }}
 239
 240         for i, c := range cases {
 241                 gotErr := c.vm.run()
 242
 243                 if gotErr != c.wantErr {
 244                         t.Errorf("run test %d: got err = %v want %v", i, gotErr, c.wantErr)
 245                         continue
 246                 }
 247
 248                 if c.wantErr != nil {
 249                         continue
 250                 }
 251         }
 252 }
 253
 254 func TestStep(t *testing.T) {
 255         txVMContext := &Context{DestPos: new(uint64)}
 256         cases := []struct {
 257                 startVM *virtualMachine
 258                 wantVM  *virtualMachine
 259                 wantErr error
 260         }{{
 261                 startVM: &virtualMachine{
 262                         program:  []byte{byte(OP_TRUE)},
 263                         runLimit: 50000,
 264                 },
 265                 wantVM: &virtualMachine{
 266                         program:   []byte{byte(OP_TRUE)},
 267                         runLimit:  49990,
 268                         dataStack: [][]byte{{1}},
 269                         pc:        1,
 270                         nextPC:    1,
 271                         data:      []byte{1},
 272                 },
 273         }, {
 274                 startVM: &virtualMachine{
 275                         program:   []byte{byte(OP_TRUE), byte(OP_JUMP), byte(0xff), byte(0x00), byte(0x00), byte(0x00)},
 276                         runLimit:  49990,
 277                         dataStack: [][]byte{},
 278                         pc:        1,
 279                 },
 280                 wantVM: &virtualMachine{
 281                         program:      []byte{byte(OP_TRUE), byte(OP_JUMP), byte(0xff), byte(0x00), byte(0x00), byte(0x00)},
 282                         runLimit:     49989,
 283                         dataStack:    [][]byte{},
 284                         data:         []byte{byte(0xff), byte(0x00), byte(0x00), byte(0x00)},
 285                         pc:           255,
 286                         nextPC:       255,
 287                         deferredCost: 0,
 288                 },
 289         }, {
 290                 startVM: &virtualMachine{
 291                         program:   []byte{byte(OP_TRUE), byte(OP_JUMPIF), byte(0x00), byte(0x00), byte(0x00), byte(0x00)},
 292                         runLimit:  49995,
 293                         dataStack: [][]byte{{1}},
 294                         pc:        1,
 295                 },
 296                 wantVM: &virtualMachine{
 297                         program:      []byte{byte(OP_TRUE), byte(OP_JUMPIF), byte(0x00), byte(0x00), byte(0x00), byte(0x00)},
 298                         runLimit:     50003,
 299                         dataStack:    [][]byte{},
 300                         pc:           0,
 301                         nextPC:       0,
 302                         data:         []byte{byte(0x00), byte(0x00), byte(0x00), byte(0x00)},
 303                         deferredCost: -9,
 304                 },
 305         }, {
 306                 startVM: &virtualMachine{
 307                         program:   []byte{byte(OP_FALSE), byte(OP_JUMPIF), byte(0x00), byte(0x00), byte(0x00), byte(0x00)},
 308                         runLimit:  49995,
 309                         dataStack: [][]byte{{}},
 310                         pc:        1,
 311                 },
 312                 wantVM: &virtualMachine{
 313                         program:      []byte{byte(OP_FALSE), byte(OP_JUMPIF), byte(0x00), byte(0x00), byte(0x00), byte(0x00)},
 314                         runLimit:     50002,
 315                         dataStack:    [][]byte{},
 316                         pc:           6,
 317                         nextPC:       6,
 318                         data:         []byte{byte(0x00), byte(0x00), byte(0x00), byte(0x00)},
 319                         deferredCost: -8,
 320                 },
 321         }, {
 322                 startVM: &virtualMachine{
 323                         program:   []byte{255},
 324                         runLimit:  50000,
 325                         dataStack: [][]byte{},
 326                 },
 327                 wantVM: &virtualMachine{
 328                         program:   []byte{255},
 329                         runLimit:  49999,
 330                         pc:        1,
 331                         nextPC:    1,
 332                         dataStack: [][]byte{},
 333                 },
 334         }, {
 335                 startVM: &virtualMachine{
 336                         program:  []byte{byte(OP_ADD)},
 337                         runLimit: 50000,
 338                 },
 339                 wantErr: ErrDataStackUnderflow,
 340         }, {
 341                 startVM: &virtualMachine{
 342                         program:  []byte{byte(OP_INDEX)},
 343                         runLimit: 1,
 344                         context:  txVMContext,
 345                 },
 346                 wantErr: ErrRunLimitExceeded,
 347         }, {
 348                 startVM: &virtualMachine{
 349                         program:           []byte{255},
 350                         runLimit:          100,
 351                         expansionReserved: true,
 352                 },
 353                 wantErr: ErrDisallowedOpcode,
 354         }, {
 355                 startVM: &virtualMachine{
 356                         program:  []byte{255},
 357                         runLimit: 100,
 358                 },
 359                 wantVM: &virtualMachine{
 360                         program:  []byte{255},
 361                         runLimit: 99,
 362                         pc:       1,
 363                         nextPC:   1,
 364                 },
 365         }}
 366
 367         for i, c := range cases {
 368                 gotErr := c.startVM.step()
 369                 gotVM := c.startVM
 370
 371                 if gotErr != c.wantErr {
 372                         t.Errorf("step test %d: got err = %v want %v", i, gotErr, c.wantErr)
 373                         continue
 374                 }
 375
 376                 if c.wantErr != nil {
 377                         continue
 378                 }
 379
 380                 if !testutil.DeepEqual(gotVM, c.wantVM) {
 381                         t.Errorf("step test %d:\n\tgot vm:  %+v\n\twant vm: %+v", i, gotVM, c.wantVM)
 382                 }
 383         }
 384 }
 385
 386 func decompile(prog []byte) string {
 387         var strs []string
 388         for i := uint32(0); i < uint32(len(prog)); { // update i inside the loop
 389                 inst, err := ParseOp(prog, i)
 390                 if err != nil {
 391                         strs = append(strs, fmt.Sprintf("<%x>", prog[i]))
 392                         i++
 393                         continue
 394                 }
 395                 var str string
 396                 if len(inst.Data) > 0 {
 397                         str = fmt.Sprintf("0x%x", inst.Data)
 398                 } else {
 399                         str = inst.Op.String()
 400                 }
 401                 strs = append(strs, str)
 402                 i += inst.Len
 403         }
 404         return strings.Join(strs, " ")
 405 }
 406
 407 func TestVerifyTxInputQuickCheck(t *testing.T) {
 408         f := func(program []byte, witnesses [][]byte) (ok bool) {
 409                 defer func() {
 410                         if err := recover(); err != nil {
 411                                 t.Log(decompile(program))
 412                                 for i := range witnesses {
 413                                         t.Logf("witness %d: %x\n", i, witnesses[i])
 414                                 }
 415                                 t.Log(err)
 416                                 ok = false
 417                         }
 418                 }()
 419
 420                 vctx := &Context{
 421                         VMVersion: 1,
 422                         Code:      program,
 423                         Arguments: witnesses,
 424
 425                         // Leaving this out reduces coverage.
 426                         // TODO(kr): figure out why and convert that
 427                         // to a normal unit test.
 428                         MaxTimeMS: new(uint64),
 429                 }
 430                 Verify(vctx)
 431
 432                 return true
 433         }
 434         if err := quick.Check(f, nil); err != nil {
 435                 t.Error(err)
 436         }
 437 }
 438
 439 func TestVerifyBlockHeaderQuickCheck(t *testing.T) {
 440         f := func(program []byte, witnesses [][]byte) (ok bool) {
 441                 defer func() {
 442                         if err := recover(); err != nil {
 443                                 t.Log(decompile(program))
 444                                 for i := range witnesses {
 445                                         t.Logf("witness %d: %x\n", i, witnesses[i])
 446                                 }
 447                                 t.Log(err)
 448                                 ok = false
 449                         }
 450                 }()
 451                 context := &Context{
 452                         VMVersion:            1,
 453                         Code:                 program,
 454                         Arguments:            witnesses,
 455                         BlockHash:            new([]byte),
 456                         BlockTimeMS:          new(uint64),
 457                         NextConsensusProgram: &[]byte{},
 458                 }
 459                 Verify(context)
 460                 return true
 461         }
 462         if err := quick.Check(f, nil); err != nil {
 463                 t.Error(err)
 464         }
 465 }