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/vapor/errors"
  12         "github.com/vapor/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(10000),
 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                 gasLeft int64
 178         }{
 179                 {
 180                         vctx: &Context{
 181                                 VMVersion: 1,
 182                                 Code:      []byte{byte(OP_ADD), byte(OP_5), byte(OP_NUMEQUAL)},
 183                                 Arguments: [][]byte{{2}, {3}},
 184                         },
 185                         gasLeft: 9986,
 186                 },
 187                 {
 188                         vctx:    &Context{VMVersion: 2},
 189                         wantErr: ErrUnsupportedVM,
 190                         gasLeft: 10000,
 191                 },
 192                 {
 193                         vctx: &Context{
 194                                 VMVersion: 1,
 195                                 Code:      []byte{byte(OP_ADD), byte(OP_5), byte(OP_NUMEQUAL)},
 196                                 Arguments: [][]byte{make([]byte, 50001)},
 197                         },
 198                         wantErr: ErrRunLimitExceeded,
 199                         gasLeft: 0,
 200                 },
 201         }
 202
 203         for _, c := range cases {
 204                 gasLeft, gotErr := Verify(c.vctx, 10000)
 205                 if errors.Root(gotErr) != c.wantErr {
 206                         t.Errorf("VerifyTxInput(%+v) err = %v want %v", c.vctx, gotErr, c.wantErr)
 207                 }
 208                 if gasLeft != c.gasLeft {
 209                         t.Errorf("VerifyTxInput(%+v) err = gasLeft doesn't match", c.vctx)
 210                 }
 211         }
 212 }
 213
 214 func TestRun(t *testing.T) {
 215         cases := []struct {
 216                 vm      *virtualMachine
 217                 wantErr error
 218         }{{
 219                 vm: &virtualMachine{runLimit: 50000, program: []byte{byte(OP_TRUE)}},
 220         }, {
 221                 vm:      &virtualMachine{runLimit: 50000, program: []byte{byte(OP_ADD)}},
 222                 wantErr: ErrDataStackUnderflow,
 223         }}
 224
 225         for i, c := range cases {
 226                 gotErr := c.vm.run()
 227
 228                 if gotErr != c.wantErr {
 229                         t.Errorf("run test %d: got err = %v want %v", i, gotErr, c.wantErr)
 230                         continue
 231                 }
 232
 233                 if c.wantErr != nil {
 234                         continue
 235                 }
 236         }
 237 }
 238
 239 func TestStep(t *testing.T) {
 240         txVMContext := &Context{DestPos: new(uint64)}
 241         cases := []struct {
 242                 startVM *virtualMachine
 243                 wantVM  *virtualMachine
 244                 wantErr error
 245         }{{
 246                 startVM: &virtualMachine{
 247                         program:  []byte{byte(OP_TRUE)},
 248                         runLimit: 50000,
 249                 },
 250                 wantVM: &virtualMachine{
 251                         program:   []byte{byte(OP_TRUE)},
 252                         runLimit:  49990,
 253                         dataStack: [][]byte{{1}},
 254                         pc:        1,
 255                         nextPC:    1,
 256                         data:      []byte{1},
 257                 },
 258         }, {
 259                 startVM: &virtualMachine{
 260                         program:   []byte{byte(OP_TRUE), byte(OP_JUMP), byte(0xff), byte(0x00), byte(0x00), byte(0x00)},
 261                         runLimit:  49990,
 262                         dataStack: [][]byte{},
 263                         pc:        1,
 264                 },
 265                 wantVM: &virtualMachine{
 266                         program:      []byte{byte(OP_TRUE), byte(OP_JUMP), byte(0xff), byte(0x00), byte(0x00), byte(0x00)},
 267                         runLimit:     49989,
 268                         dataStack:    [][]byte{},
 269                         data:         []byte{byte(0xff), byte(0x00), byte(0x00), byte(0x00)},
 270                         pc:           255,
 271                         nextPC:       255,
 272                         deferredCost: 0,
 273                 },
 274         }, {
 275                 startVM: &virtualMachine{
 276                         program:   []byte{byte(OP_TRUE), byte(OP_JUMPIF), byte(0x00), byte(0x00), byte(0x00), byte(0x00)},
 277                         runLimit:  49995,
 278                         dataStack: [][]byte{{1}},
 279                         pc:        1,
 280                 },
 281                 wantVM: &virtualMachine{
 282                         program:      []byte{byte(OP_TRUE), byte(OP_JUMPIF), byte(0x00), byte(0x00), byte(0x00), byte(0x00)},
 283                         runLimit:     50003,
 284                         dataStack:    [][]byte{},
 285                         pc:           0,
 286                         nextPC:       0,
 287                         data:         []byte{byte(0x00), byte(0x00), byte(0x00), byte(0x00)},
 288                         deferredCost: -9,
 289                 },
 290         }, {
 291                 startVM: &virtualMachine{
 292                         program:   []byte{byte(OP_FALSE), byte(OP_JUMPIF), byte(0x00), byte(0x00), byte(0x00), byte(0x00)},
 293                         runLimit:  49995,
 294                         dataStack: [][]byte{{}},
 295                         pc:        1,
 296                 },
 297                 wantVM: &virtualMachine{
 298                         program:      []byte{byte(OP_FALSE), byte(OP_JUMPIF), byte(0x00), byte(0x00), byte(0x00), byte(0x00)},
 299                         runLimit:     50002,
 300                         dataStack:    [][]byte{},
 301                         pc:           6,
 302                         nextPC:       6,
 303                         data:         []byte{byte(0x00), byte(0x00), byte(0x00), byte(0x00)},
 304                         deferredCost: -8,
 305                 },
 306         }, {
 307                 startVM: &virtualMachine{
 308                         program:   []byte{255},
 309                         runLimit:  50000,
 310                         dataStack: [][]byte{},
 311                 },
 312                 wantVM: &virtualMachine{
 313                         program:   []byte{255},
 314                         runLimit:  49999,
 315                         pc:        1,
 316                         nextPC:    1,
 317                         dataStack: [][]byte{},
 318                 },
 319         }, {
 320                 startVM: &virtualMachine{
 321                         program:  []byte{byte(OP_ADD)},
 322                         runLimit: 50000,
 323                 },
 324                 wantErr: ErrDataStackUnderflow,
 325         }, {
 326                 startVM: &virtualMachine{
 327                         program:  []byte{byte(OP_INDEX)},
 328                         runLimit: 1,
 329                         context:  txVMContext,
 330                 },
 331                 wantErr: ErrRunLimitExceeded,
 332         }, {
 333                 startVM: &virtualMachine{
 334                         program:           []byte{255},
 335                         runLimit:          100,
 336                         expansionReserved: true,
 337                 },
 338                 wantErr: ErrDisallowedOpcode,
 339         }, {
 340                 startVM: &virtualMachine{
 341                         program:  []byte{255},
 342                         runLimit: 100,
 343                 },
 344                 wantVM: &virtualMachine{
 345                         program:  []byte{255},
 346                         runLimit: 99,
 347                         pc:       1,
 348                         nextPC:   1,
 349                 },
 350         }}
 351
 352         for i, c := range cases {
 353                 gotErr := c.startVM.step()
 354                 gotVM := c.startVM
 355
 356                 if gotErr != c.wantErr {
 357                         t.Errorf("step test %d: got err = %v want %v", i, gotErr, c.wantErr)
 358                         continue
 359                 }
 360
 361                 if c.wantErr != nil {
 362                         continue
 363                 }
 364
 365                 if !testutil.DeepEqual(gotVM, c.wantVM) {
 366                         t.Errorf("step test %d:\n\tgot vm:  %+v\n\twant vm: %+v", i, gotVM, c.wantVM)
 367                 }
 368         }
 369 }
 370
 371 func decompile(prog []byte) string {
 372         var strs []string
 373         for i := uint32(0); i < uint32(len(prog)); { // update i inside the loop
 374                 inst, err := ParseOp(prog, i)
 375                 if err != nil {
 376                         strs = append(strs, fmt.Sprintf("<%x>", prog[i]))
 377                         i++
 378                         continue
 379                 }
 380                 var str string
 381                 if len(inst.Data) > 0 {
 382                         str = fmt.Sprintf("0x%x", inst.Data)
 383                 } else {
 384                         str = inst.Op.String()
 385                 }
 386                 strs = append(strs, str)
 387                 i += inst.Len
 388         }
 389         return strings.Join(strs, " ")
 390 }
 391
 392 func TestVerifyTxInputQuickCheck(t *testing.T) {
 393         f := func(program []byte, witnesses [][]byte) (ok bool) {
 394                 defer func() {
 395                         if err := recover(); err != nil {
 396                                 t.Log(decompile(program))
 397                                 for i := range witnesses {
 398                                         t.Logf("witness %d: %x\n", i, witnesses[i])
 399                                 }
 400                                 t.Log(err)
 401                                 ok = false
 402                         }
 403                 }()
 404
 405                 vctx := &Context{
 406                         VMVersion: 1,
 407                         Code:      program,
 408                         Arguments: witnesses,
 409                 }
 410                 Verify(vctx, 10000)
 411
 412                 return true
 413         }
 414         if err := quick.Check(f, nil); err != nil {
 415                 t.Error(err)
 416         }
 417 }
 418
 419 func TestVerifyBlockHeaderQuickCheck(t *testing.T) {
 420         f := func(program []byte, witnesses [][]byte) (ok bool) {
 421                 defer func() {
 422                         if err := recover(); err != nil {
 423                                 t.Log(decompile(program))
 424                                 for i := range witnesses {
 425                                         t.Logf("witness %d: %x\n", i, witnesses[i])
 426                                 }
 427                                 t.Log(err)
 428                                 ok = false
 429                         }
 430                 }()
 431                 context := &Context{
 432                         VMVersion: 1,
 433                         Code:      program,
 434                         Arguments: witnesses,
 435                 }
 436                 Verify(context, 10000)
 437                 return true
 438         }
 439         if err := quick.Check(f, nil); err != nil {
 440                 t.Error(err)
 441         }
 442 }