| // Copyright 2017 syzkaller project authors. All rights reserved. |
| // Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. |
| |
| //go:generate bash -c "go run gen/gen.go gen/all-enc-instructions.txt > generated/insns.go" |
| |
| // Package ifuzz allows to generate and mutate x86 machine code. |
| package ifuzz |
| |
| import ( |
| "math/rand" |
| "sync" |
| ) |
| |
| const ( |
| ModeLong64 = iota |
| ModeProt32 |
| ModeProt16 |
| ModeReal16 |
| ModeLast |
| ) |
| |
| type Insn struct { |
| Name string |
| Extension string |
| |
| Mode int // bitmask of compatible modes |
| Priv bool // CPL=0 |
| Pseudo bool // pseudo instructions can consist of several real instructions |
| |
| Opcode []byte |
| Prefix []byte |
| Suffix []byte |
| Modrm bool |
| Mod int8 |
| Reg int8 // -6 - segment register, -8 - control register |
| Rm int8 |
| Srm bool // register is embed in the first byte |
| NoSibDisp bool // no SIB/disp even if modrm says otherwise |
| Imm int8 // immediate size, -1 - immediate size, -2 - address size, -3 - operand size |
| Imm2 int8 |
| NoRepPrefix bool |
| No66Prefix bool |
| Rexw int8 // 1 must be set, -1 must not be set |
| Mem32 bool // instruction always references 32-bit memory operand, 0x67 is illegal |
| Mem16 bool // instruction always references 16-bit memory operand |
| |
| Vex byte |
| VexMap byte |
| VexL int8 |
| VexNoR bool |
| VexP int8 |
| Avx2Gather bool |
| |
| generator func(cfg *Config, r *rand.Rand) []byte // for pseudo instructions |
| } |
| |
| type Config struct { |
| Len int // number of instructions to generate |
| Mode int // one of ModeXXX |
| Priv bool // generate CPL=0 instructions |
| Exec bool // generate instructions sequences interesting for execution |
| MemRegions []MemRegion // generated instructions will reference these regions |
| } |
| |
| type MemRegion struct { |
| Start uint64 |
| Size uint64 |
| } |
| |
| const ( |
| typeExec = iota |
| typePriv |
| typeUser |
| typeAll |
| typeLast |
| ) |
| |
| var modeInsns [ModeLast][typeLast][]*Insn |
| |
| var ( |
| Insns []*Insn |
| initOnce sync.Once |
| ) |
| |
| func initInsns() { |
| if len(Insns) == 0 { |
| panic("no instructions") |
| } |
| initPseudo() |
| for mode := 0; mode < ModeLast; mode++ { |
| for _, insn := range Insns { |
| if insn.Mode&(1<<uint(mode)) == 0 { |
| continue |
| } |
| if insn.Pseudo { |
| modeInsns[mode][typeExec] = append(modeInsns[mode][typeExec], insn) |
| } else if insn.Priv { |
| modeInsns[mode][typePriv] = append(modeInsns[mode][typePriv], insn) |
| modeInsns[mode][typeAll] = append(modeInsns[mode][typeAll], insn) |
| } else { |
| modeInsns[mode][typeUser] = append(modeInsns[mode][typeUser], insn) |
| modeInsns[mode][typeAll] = append(modeInsns[mode][typeAll], insn) |
| } |
| } |
| } |
| } |
| |
| // ModeInsns returns list of all instructions for the given mode. |
| func ModeInsns(cfg *Config) []*Insn { |
| initOnce.Do(initInsns) |
| if cfg.Mode < 0 || cfg.Mode >= ModeLast { |
| panic("bad mode") |
| } |
| var insns []*Insn |
| insns = append(insns, modeInsns[cfg.Mode][typeUser]...) |
| if cfg.Priv { |
| insns = append(insns, modeInsns[cfg.Mode][typePriv]...) |
| if cfg.Exec { |
| insns = append(insns, modeInsns[cfg.Mode][typeExec]...) |
| } |
| } |
| return insns |
| } |
| |
| func Generate(cfg *Config, r *rand.Rand) []byte { |
| initOnce.Do(initInsns) |
| var text []byte |
| for i := 0; i < cfg.Len; i++ { |
| insn := randInsn(cfg, r) |
| text = append(text, insn.Encode(cfg, r)...) |
| } |
| return text |
| } |
| |
| func Mutate(cfg *Config, r *rand.Rand, text []byte) []byte { |
| initOnce.Do(initInsns) |
| insns := split(cfg, text) |
| retry := false |
| for stop := false; !stop || retry || len(insns) == 0; stop = r.Intn(2) == 0 { |
| retry = false |
| switch x := r.Intn(100); { |
| case x < 10 && len(insns) != 0: |
| // delete instruction |
| i := r.Intn(len(insns)) |
| copy(insns[i:], insns[i+1:]) |
| insns = insns[:len(insns)-1] |
| case x < 40 && len(insns) != 0: |
| // replace instruction with another |
| insn := randInsn(cfg, r) |
| text1 := insn.Encode(cfg, r) |
| i := r.Intn(len(insns)) |
| insns[i] = text1 |
| case x < 70 && len(insns) != 0: |
| // mutate instruction |
| i := r.Intn(len(insns)) |
| text1 := insns[i] |
| for stop := false; !stop || len(text1) == 0; stop = r.Intn(2) == 0 { |
| switch x := r.Intn(100); { |
| case x < 5 && len(text1) != 0: |
| // delete byte |
| pos := r.Intn(len(text1)) |
| copy(text1[pos:], text1[pos+1:]) |
| text1 = text1[:len(text1)-1] |
| case x < 40 && len(text1) != 0: |
| // replace a byte |
| pos := r.Intn(len(text1)) |
| text1[pos] = byte(r.Intn(256)) |
| case x < 70 && len(text1) != 0: |
| // flip a bit |
| pos := r.Intn(len(text1)) |
| text1[pos] ^= 1 << byte(r.Intn(8)) |
| default: |
| // insert a byte |
| pos := r.Intn(len(text1) + 1) |
| text1 = append(text1, 0) |
| copy(text1[pos+1:], text1[pos:]) |
| text1[pos] = byte(r.Intn(256)) |
| } |
| } |
| insns[i] = text1 |
| case len(insns) < cfg.Len: |
| // insert a new instruction |
| insn := randInsn(cfg, r) |
| text1 := insn.Encode(cfg, r) |
| i := r.Intn(len(insns) + 1) |
| insns = append(insns, nil) |
| copy(insns[i+1:], insns[i:]) |
| insns[i] = text1 |
| default: |
| retry = true |
| } |
| } |
| text = nil |
| for _, insn := range insns { |
| text = append(text, insn...) |
| } |
| return text |
| } |
| |
| func randInsn(cfg *Config, r *rand.Rand) *Insn { |
| var insns []*Insn |
| if cfg.Priv && cfg.Exec { |
| insns = modeInsns[cfg.Mode][r.Intn(3)] |
| } else if cfg.Priv { |
| insns = modeInsns[cfg.Mode][r.Intn(2)] |
| } else { |
| insns = modeInsns[cfg.Mode][typeUser] |
| } |
| return insns[r.Intn(len(insns))] |
| } |
| |
| func split(cfg *Config, text []byte) [][]byte { |
| text = append([]byte{}, text...) |
| var insns [][]byte |
| var bad []byte |
| for len(text) != 0 { |
| n, err := Decode(cfg.Mode, text) |
| if err != nil || n == 0 { |
| bad = append(bad, text[0]) |
| text = text[1:] |
| continue |
| } |
| if bad != nil { |
| insns = append(insns, bad) |
| bad = nil |
| } |
| insns = append(insns, text[:n]) |
| text = text[n:] |
| } |
| if bad != nil { |
| insns = append(insns, bad) |
| } |
| return insns |
| } |
| |
| func generateArg(cfg *Config, r *rand.Rand, size int) []byte { |
| v := generateInt(cfg, r, size) |
| arg := make([]byte, size) |
| for i := 0; i < size; i++ { |
| arg[i] = byte(v) |
| v >>= 8 |
| } |
| return arg |
| } |
| |
| func (insn *Insn) isCompatible(cfg *Config) bool { |
| if cfg.Mode < 0 || cfg.Mode >= ModeLast { |
| panic("bad mode") |
| } |
| if insn.Priv && !cfg.Priv { |
| return false |
| } |
| if insn.Pseudo && !cfg.Exec { |
| return false |
| } |
| if insn.Mode&(1<<uint(cfg.Mode)) == 0 { |
| return false |
| } |
| return true |
| } |
| |
| func generateInt(cfg *Config, r *rand.Rand, size int) uint64 { |
| if size != 1 && size != 2 && size != 4 && size != 8 { |
| panic("bad arg size") |
| } |
| var v uint64 |
| switch x := r.Intn(60); { |
| case x < 10: |
| v = uint64(r.Intn(1 << 4)) |
| case x < 20: |
| v = uint64(r.Intn(1 << 16)) |
| case x < 25: |
| v = uint64(r.Int63()) % (1 << 32) |
| case x < 30: |
| v = uint64(r.Int63()) |
| case x < 40: |
| v = specialNumbers[r.Intn(len(specialNumbers))] |
| if r.Intn(5) == 0 { |
| v += uint64(r.Intn(33)) - 16 |
| } |
| case x < 50 && len(cfg.MemRegions) != 0: |
| mem := cfg.MemRegions[r.Intn(len(cfg.MemRegions))] |
| switch x := r.Intn(100); { |
| case x < 25: |
| v = mem.Start |
| case x < 50: |
| v = mem.Start + mem.Size |
| case x < 75: |
| v = mem.Start + mem.Size/2 |
| default: |
| v = mem.Start + uint64(r.Int63())%mem.Size |
| } |
| if r.Intn(10) == 0 { |
| v += uint64(r.Intn(33)) - 16 |
| } |
| default: |
| v = uint64(r.Intn(1 << 8)) |
| } |
| if r.Intn(50) == 0 { |
| v = uint64(-int64(v)) |
| } |
| if r.Intn(50) == 0 && size != 1 { |
| v &^= 1<<12 - 1 |
| } |
| return v |
| } |
| |
| var specialNumbers = []uint64{0, 1 << 15, 1 << 16, 1 << 31, 1 << 32, 1 << 47, 1 << 47, 1 << 63} |