1// Copyright 2017 syzkaller project authors. All rights reserved. 2// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. 3 4package prog 5 6import ( 7 "encoding/hex" 8 "fmt" 9 "math/rand" 10 "reflect" 11 "sort" 12 "testing" 13) 14 15type ConstArgTest struct { 16 name string 17 in uint64 18 comps CompMap 19 res uint64Set 20} 21 22type DataArgTest struct { 23 name string 24 in string 25 comps CompMap 26 res map[string]bool 27} 28 29// Tests checkConstArg(). Is not intended to check correctness of any mutations. 30// Mutation are checked in their own tests. 31func TestHintsCheckConstArg(t *testing.T) { 32 t.Parallel() 33 var tests = []ConstArgTest{ 34 { 35 "One replacer test", 36 0xdeadbeef, 37 CompMap{0xdeadbeef: uint64Set{0xcafebabe: true}}, 38 uint64Set{0xcafebabe: true}, 39 }, 40 // Test for cases when there's multiple comparisons (op1, op2), (op1, op3), ... 41 // Checks that for every such operand a program is generated. 42 { 43 "Multiple replacers test", 44 0xabcd, 45 CompMap{0xabcd: uint64Set{0x2: true, 0x3: true}}, 46 uint64Set{0x2: true, 0x3: true}, 47 }, 48 // Checks that special ints are not used. 49 { 50 "Special ints test", 51 0xabcd, 52 CompMap{0xabcd: uint64Set{0x1: true, 0x2: true}}, 53 uint64Set{0x2: true}, 54 }, 55 } 56 for _, test := range tests { 57 t.Run(fmt.Sprintf("%v", test.name), func(t *testing.T) { 58 t.Parallel() 59 res := uint64Set{} 60 constArg := &ConstArg{ArgCommon{nil}, test.in} 61 checkConstArg(constArg, test.comps, func() { 62 res[constArg.Val] = true 63 }) 64 if !reflect.DeepEqual(res, test.res) { 65 t.Fatalf("\ngot : %v\nwant: %v", res, test.res) 66 } 67 }) 68 } 69} 70 71// Tests checkDataArg(). Is not intended to check correctness of any mutations. 72// Mutation are checked in their own tests. 73func TestHintsCheckDataArg(t *testing.T) { 74 t.Parallel() 75 // All inputs are in Little-Endian. 76 var tests = []DataArgTest{ 77 { 78 "One replacer test", 79 "\xef\xbe\xad\xde", 80 CompMap{0xdeadbeef: uint64Set{0xcafebabe: true}}, 81 map[string]bool{ 82 "\xbe\xba\xfe\xca": true, 83 }, 84 }, 85 // Test for cases when there's multiple comparisons (op1, op2), (op1, op3), ... 86 // Checks that for every such operand a program is generated. 87 { 88 "Multiple replacers test", 89 "\xcd\xab", 90 CompMap{0xabcd: uint64Set{0x2: true, 0x3: true}}, 91 map[string]bool{ 92 "\x02\x00": true, "\x03\x00": true, 93 }, 94 }, 95 // Checks that special ints are not used. 96 { 97 "Special ints test", 98 "\xcd\xab", 99 CompMap{0xabcd: uint64Set{0x1: true, 0x2: true}}, 100 map[string]bool{ 101 "\x02\x00": true, 102 }, 103 }, 104 // Checks that ints of various sizes are extracted. 105 { 106 "Different sizes test", 107 "\xef\xcd\xab\x90\x78\x56\x34\x12", 108 CompMap{ 109 0xef: uint64Set{0x11: true}, 110 0xcdef: uint64Set{0x2222: true}, 111 0x90abcdef: uint64Set{0x33333333: true}, 112 0x1234567890abcdef: uint64Set{0x4444444444444444: true}, 113 }, 114 map[string]bool{ 115 "\x11\xcd\xab\x90\x78\x56\x34\x12": true, 116 "\x22\x22\xab\x90\x78\x56\x34\x12": true, 117 "\x33\x33\x33\x33\x78\x56\x34\x12": true, 118 "\x44\x44\x44\x44\x44\x44\x44\x44": true, 119 }, 120 }, 121 // Checks that values with different offsets are extracted. 122 { 123 "Different offsets test", 124 "\xab\xab\xab\xab\xab\xab\xab\xab\xab", 125 CompMap{ 126 0xab: uint64Set{0x11: true}, 127 0xabab: uint64Set{0x2222: true}, 128 0xabababab: uint64Set{0x33333333: true}, 129 0xabababababababab: uint64Set{0x4444444444444444: true}, 130 }, 131 map[string]bool{ 132 "\x11\xab\xab\xab\xab\xab\xab\xab\xab": true, 133 "\xab\x11\xab\xab\xab\xab\xab\xab\xab": true, 134 "\xab\xab\x11\xab\xab\xab\xab\xab\xab": true, 135 "\xab\xab\xab\x11\xab\xab\xab\xab\xab": true, 136 "\xab\xab\xab\xab\x11\xab\xab\xab\xab": true, 137 "\xab\xab\xab\xab\xab\x11\xab\xab\xab": true, 138 "\xab\xab\xab\xab\xab\xab\x11\xab\xab": true, 139 "\xab\xab\xab\xab\xab\xab\xab\x11\xab": true, 140 "\xab\xab\xab\xab\xab\xab\xab\xab\x11": true, 141 "\x22\x22\xab\xab\xab\xab\xab\xab\xab": true, 142 "\xab\x22\x22\xab\xab\xab\xab\xab\xab": true, 143 "\xab\xab\x22\x22\xab\xab\xab\xab\xab": true, 144 "\xab\xab\xab\x22\x22\xab\xab\xab\xab": true, 145 "\xab\xab\xab\xab\x22\x22\xab\xab\xab": true, 146 "\xab\xab\xab\xab\xab\x22\x22\xab\xab": true, 147 "\xab\xab\xab\xab\xab\xab\x22\x22\xab": true, 148 "\xab\xab\xab\xab\xab\xab\xab\x22\x22": true, 149 "\x33\x33\x33\x33\xab\xab\xab\xab\xab": true, 150 "\xab\x33\x33\x33\x33\xab\xab\xab\xab": true, 151 "\xab\xab\x33\x33\x33\x33\xab\xab\xab": true, 152 "\xab\xab\xab\x33\x33\x33\x33\xab\xab": true, 153 "\xab\xab\xab\xab\x33\x33\x33\x33\xab": true, 154 "\xab\xab\xab\xab\xab\x33\x33\x33\x33": true, 155 "\x44\x44\x44\x44\x44\x44\x44\x44\xab": true, 156 "\xab\x44\x44\x44\x44\x44\x44\x44\x44": true, 157 }, 158 }, 159 { 160 "Replace in the middle of a larger blob", 161 "\xef\xcd\xab\x90\x78\x56\x34\x12", 162 CompMap{0xffffffffffff90ab: uint64Set{0xffffffffffffaabb: true}}, 163 map[string]bool{ 164 "\xef\xcd\xbb\xaa\x78\x56\x34\x12": true, 165 }, 166 }, 167 { 168 169 "Big-endian replace", 170 "\xef\xcd\xab\x90\x78\x56\x34\x12", 171 CompMap{ 172 // 0xff07 is reversed special int. 173 0xefcd: uint64Set{0xaabb: true, 0xff07: true}, 174 0x3412: uint64Set{0xaabb: true, 0xff07: true}, 175 0x9078: uint64Set{0xaabb: true, 0x11223344: true, 0xff07: true}, 176 0x90785634: uint64Set{0xaabbccdd: true, 0x11223344: true}, 177 0xefcdab9078563412: uint64Set{0x1122334455667788: true}, 178 }, 179 map[string]bool{ 180 "\xaa\xbb\xab\x90\x78\x56\x34\x12": true, 181 "\xef\xcd\xab\x90\x78\x56\xaa\xbb": true, 182 "\xef\xcd\xab\xaa\xbb\x56\x34\x12": true, 183 "\xef\xcd\xab\xaa\xbb\xcc\xdd\x12": true, 184 "\xef\xcd\xab\x11\x22\x33\x44\x12": true, 185 "\x11\x22\x33\x44\x55\x66\x77\x88": true, 186 }, 187 }, 188 } 189 for _, test := range tests { 190 t.Run(fmt.Sprintf("%v", test.name), func(t *testing.T) { 191 t.Parallel() 192 res := make(map[string]bool) 193 // Whatever type here. It's just needed to pass the 194 // dataArg.Type().Dir() == DirIn check. 195 typ := &ArrayType{TypeCommon{"", "", 0, DirIn, false, true}, nil, 0, 0, 0} 196 dataArg := MakeDataArg(typ, []byte(test.in)) 197 checkDataArg(dataArg, test.comps, func() { 198 res[string(dataArg.Data())] = true 199 }) 200 if !reflect.DeepEqual(res, test.res) { 201 s := "\ngot: [" 202 for x := range res { 203 s += fmt.Sprintf("0x%x, ", x) 204 } 205 s += "]\nwant: [" 206 for x := range test.res { 207 s += fmt.Sprintf("0x%x, ", x) 208 } 209 s += "]\n" 210 t.Fatalf(s) 211 } 212 }) 213 } 214} 215 216func TestHintsShrinkExpand(t *testing.T) { 217 t.Parallel() 218 // Naming conventions: 219 // b - byte variable (i8 or u8) 220 // w - word variable (i16 or u16) 221 // dw - dword variable (i32 or u32) 222 // qw - qword variable (i64 or u64) 223 // ----------------------------------------------------------------- 224 // Shrink tests: 225 var tests = []ConstArgTest{ 226 { 227 // Models the following code: 228 // void f(u16 w) { 229 // u8 b = (u8) w; 230 // if (b == 0xab) {...} 231 // if (w == 0xcdcd) {...} 232 // }; f(0x1234); 233 "Shrink 16 test", 234 0x1234, 235 CompMap{ 236 0x34: uint64Set{0xab: true}, 237 0x1234: uint64Set{0xcdcd: true}, 238 }, 239 uint64Set{0x12ab: true, 0xcdcd: true}, 240 }, 241 { 242 // Models the following code: 243 // void f(u32 dw) { 244 // u8 b = (u8) dw 245 // i16 w = (i16) dw 246 // if (a == 0xab) {...} 247 // if (b == 0xcdcd) {...} 248 // if (dw == 0xefefefef) {...} 249 // }; f(0x12345678); 250 "Shrink 32 test", 251 0x12345678, 252 CompMap{ 253 0x78: uint64Set{0xab: true}, 254 0x5678: uint64Set{0xcdcd: true}, 255 0x12345678: uint64Set{0xefefefef: true}, 256 }, 257 uint64Set{0x123456ab: true, 0x1234cdcd: true, 0xefefefef: true}, 258 }, 259 { 260 // Models the following code: 261 // void f(u64 qw) { 262 // u8 b = (u8) qw 263 // u16 w = (u16) qw 264 // u32 dw = (u32) qw 265 // if (a == 0xab) {...} 266 // if (b == 0xcdcd) {...} 267 // if (dw == 0xefefefef) {...} 268 // if (qw == 0x0101010101010101) {...} 269 // }; f(0x1234567890abcdef); 270 "Shrink 64 test", 271 0x1234567890abcdef, 272 CompMap{ 273 0xef: uint64Set{0xab: true}, 274 0xcdef: uint64Set{0xcdcd: true}, 275 0x90abcdef: uint64Set{0xefefefef: true}, 276 0x1234567890abcdef: uint64Set{0x0101010101010101: true}, 277 }, 278 uint64Set{ 279 0x1234567890abcdab: true, 280 0x1234567890abcdcd: true, 281 0x12345678efefefef: true, 282 0x0101010101010101: true, 283 }, 284 }, 285 { 286 // Models the following code: 287 // void f(i16 w) { 288 // i8 b = (i8) w; 289 // i16 other = 0xabab; 290 // if (b == other) {...} 291 // }; f(0x1234); 292 // In such code the comparison will never be true, so we don't 293 // generate a hint for it. 294 "Shrink with a wider replacer test1", 295 0x1234, 296 CompMap{0x34: uint64Set{0x1bab: true}}, 297 nil, 298 }, 299 { 300 // Models the following code: 301 // void f(i16 w) { 302 // i8 b = (i8) w; 303 // i16 other = 0xfffd; 304 // if (b == other) {...} 305 // }; f(0x1234); 306 // In such code b will be sign extended to 0xff34 and, if we replace 307 // the lower byte, then the if statement will be true. 308 // Note that executor sign extends all the comparison operands to 309 // int64, so we model this accordingly. 310 "Shrink with a wider replacer test2", 311 0x1234, 312 CompMap{0x34: uint64Set{0xfffffffffffffffd: true}}, 313 uint64Set{0x12fd: true}, 314 }, 315 // ----------------------------------------------------------------- 316 // Extend tests: 317 // Note that executor sign extends all the comparison operands to int64, 318 // so we model this accordingly. 319 { 320 // Models the following code: 321 // void f(i8 b) { 322 // i64 qw = (i64) b; 323 // if (qw == -2) {...}; 324 // }; f(-1); 325 "Extend 8 test", 326 0xff, 327 CompMap{0xffffffffffffffff: uint64Set{0xfffffffffffffffe: true}}, 328 uint64Set{0xfe: true}, 329 }, 330 { 331 // Models the following code: 332 // void f(i16 w) { 333 // i64 qw = (i64) w; 334 // if (qw == -2) {...}; 335 // }; f(-1); 336 "Extend 16 test", 337 0xffff, 338 CompMap{0xffffffffffffffff: uint64Set{0xfffffffffffffffe: true}}, 339 uint64Set{0xfffe: true}, 340 }, 341 { 342 // Models the following code: 343 // void f(i32 dw) { 344 // i64 qw = (i32) dw; 345 // if (qw == -2) {...}; 346 // }; f(-1); 347 "Extend 32 test", 348 0xffffffff, 349 CompMap{0xffffffffffffffff: uint64Set{0xfffffffffffffffe: true}}, 350 uint64Set{0xfffffffe: true}, 351 }, 352 { 353 // Models the following code: 354 // void f(i8 b) { 355 // i16 w = (i16) b; 356 // if (w == (i16) 0xfeff) {...}; 357 // }; f(-1); 358 // There's no value for b that will make the comparison true, 359 // so we don't generate hints. 360 "Extend with a wider replacer test", 361 0xff, 362 CompMap{0xffffffffffffffff: uint64Set{0xfffffffffffffeff: true}}, 363 nil, 364 }, 365 } 366 for _, test := range tests { 367 t.Run(fmt.Sprintf("%v", test.name), func(t *testing.T) { 368 t.Parallel() 369 res := shrinkExpand(test.in, test.comps) 370 if !reflect.DeepEqual(res, test.res) { 371 t.Fatalf("\ngot : %v\nwant: %v", res, test.res) 372 } 373 }) 374 } 375} 376 377func TestHintsRandom(t *testing.T) { 378 target, rs, iters := initTest(t) 379 iters /= 10 // the test takes long 380 r := newRand(target, rs) 381 for i := 0; i < iters; i++ { 382 p := target.Generate(rs, 5, nil) 383 for i, c := range p.Calls { 384 vals := extractValues(c) 385 for j := 0; j < 5; j++ { 386 vals[r.randInt()] = true 387 } 388 comps := make(CompMap) 389 for v := range vals { 390 comps.AddComp(v, r.randInt()) 391 } 392 p.MutateWithHints(i, comps, func(p1 *Prog) {}) 393 } 394 } 395} 396 397func extractValues(c *Call) map[uint64]bool { 398 vals := make(map[uint64]bool) 399 ForeachArg(c, func(arg Arg, _ *ArgCtx) { 400 if typ := arg.Type(); typ == nil || typ.Dir() == DirOut { 401 return 402 } 403 switch a := arg.(type) { 404 case *ConstArg: 405 vals[a.Val] = true 406 case *DataArg: 407 data := a.Data() 408 for i := range data { 409 vals[uint64(data[i])] = true 410 if i < len(data)-1 { 411 v := uint64(data[i]) | uint64(data[i+1])<<8 412 vals[v] = true 413 } 414 if i < len(data)-3 { 415 v := uint64(data[i]) | uint64(data[i+1])<<8 | 416 uint64(data[i+2])<<16 | uint64(data[i+3])<<24 417 vals[v] = true 418 } 419 if i < len(data)-7 { 420 v := uint64(data[i]) | uint64(data[i+1])<<8 | 421 uint64(data[i+2])<<16 | uint64(data[i+3])<<24 | 422 uint64(data[i+4])<<32 | uint64(data[i+5])<<40 | 423 uint64(data[i+6])<<48 | uint64(data[i+7])<<56 424 vals[v] = true 425 } 426 } 427 } 428 }) 429 return vals 430} 431 432func TestHintsData(t *testing.T) { 433 target := initTargetTest(t, "test", "64") 434 type Test struct { 435 in string 436 comps CompMap 437 out []string 438 } 439 tests := []Test{ 440 { 441 in: "0809101112131415", 442 comps: CompMap{0x12111009: uint64Set{0x10: true}}, 443 out: []string{"0810000000131415"}, 444 }, 445 } 446 call := target.SyscallMap["test$hint_data"] 447 for _, test := range tests { 448 input, err := hex.DecodeString(test.in) 449 if err != nil { 450 t.Fatal(err) 451 } 452 p := &Prog{ 453 Target: target, 454 Calls: []*Call{{ 455 Meta: call, 456 Args: []Arg{MakePointerArg(call.Args[0], 0, 457 MakeDataArg(call.Args[0].(*PtrType).Type, input))}, 458 Ret: MakeReturnArg(call.Ret), 459 }}, 460 } 461 if err := p.validate(); err != nil { 462 t.Fatal(err) 463 } 464 var got []string 465 p.MutateWithHints(0, test.comps, func(newP *Prog) { 466 got = append(got, hex.EncodeToString( 467 newP.Calls[0].Args[0].(*PointerArg).Res.(*DataArg).Data())) 468 }) 469 sort.Strings(test.out) 470 sort.Strings(got) 471 if !reflect.DeepEqual(got, test.out) { 472 t.Fatalf("comps: %v\ninput: %v\ngot : %+v\nwant: %+v", 473 test.comps, test.in, got, test.out) 474 } 475 } 476} 477 478func BenchmarkHints(b *testing.B) { 479 olddebug := debug 480 debug = false 481 defer func() { debug = olddebug }() 482 target, err := GetTarget("linux", "amd64") 483 if err != nil { 484 b.Fatal(err) 485 } 486 rs := rand.NewSource(0) 487 r := newRand(target, rs) 488 p := target.Generate(rs, 30, nil) 489 comps := make([]CompMap, len(p.Calls)) 490 for i, c := range p.Calls { 491 vals := extractValues(c) 492 for j := 0; j < 5; j++ { 493 vals[r.randInt()] = true 494 } 495 comps[i] = make(CompMap) 496 for v := range vals { 497 comps[i].AddComp(v, r.randInt()) 498 } 499 } 500 b.RunParallel(func(pb *testing.PB) { 501 for pb.Next() { 502 for i := range p.Calls { 503 p.MutateWithHints(i, comps[i], func(p1 *Prog) {}) 504 } 505 } 506 }) 507} 508