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 4//go:generate bash -c "go run gen/gen.go gen/all-enc-instructions.txt > generated/insns.go" 5 6// Package ifuzz allows to generate and mutate x86 machine code. 7package ifuzz 8 9import ( 10 "math/rand" 11 "sync" 12) 13 14const ( 15 ModeLong64 = iota 16 ModeProt32 17 ModeProt16 18 ModeReal16 19 ModeLast 20) 21 22type Insn struct { 23 Name string 24 Extension string 25 26 Mode int // bitmask of compatible modes 27 Priv bool // CPL=0 28 Pseudo bool // pseudo instructions can consist of several real instructions 29 30 Opcode []byte 31 Prefix []byte 32 Suffix []byte 33 Modrm bool 34 Mod int8 35 Reg int8 // -6 - segment register, -8 - control register 36 Rm int8 37 Srm bool // register is embed in the first byte 38 NoSibDisp bool // no SIB/disp even if modrm says otherwise 39 Imm int8 // immediate size, -1 - immediate size, -2 - address size, -3 - operand size 40 Imm2 int8 41 NoRepPrefix bool 42 No66Prefix bool 43 Rexw int8 // 1 must be set, -1 must not be set 44 Mem32 bool // instruction always references 32-bit memory operand, 0x67 is illegal 45 Mem16 bool // instruction always references 16-bit memory operand 46 47 Vex byte 48 VexMap byte 49 VexL int8 50 VexNoR bool 51 VexP int8 52 Avx2Gather bool 53 54 generator func(cfg *Config, r *rand.Rand) []byte // for pseudo instructions 55} 56 57type Config struct { 58 Len int // number of instructions to generate 59 Mode int // one of ModeXXX 60 Priv bool // generate CPL=0 instructions 61 Exec bool // generate instructions sequences interesting for execution 62 MemRegions []MemRegion // generated instructions will reference these regions 63} 64 65type MemRegion struct { 66 Start uint64 67 Size uint64 68} 69 70const ( 71 typeExec = iota 72 typePriv 73 typeUser 74 typeAll 75 typeLast 76) 77 78var modeInsns [ModeLast][typeLast][]*Insn 79 80var ( 81 Insns []*Insn 82 initOnce sync.Once 83) 84 85func initInsns() { 86 if len(Insns) == 0 { 87 panic("no instructions") 88 } 89 initPseudo() 90 for mode := 0; mode < ModeLast; mode++ { 91 for _, insn := range Insns { 92 if insn.Mode&(1<<uint(mode)) == 0 { 93 continue 94 } 95 if insn.Pseudo { 96 modeInsns[mode][typeExec] = append(modeInsns[mode][typeExec], insn) 97 } else if insn.Priv { 98 modeInsns[mode][typePriv] = append(modeInsns[mode][typePriv], insn) 99 modeInsns[mode][typeAll] = append(modeInsns[mode][typeAll], insn) 100 } else { 101 modeInsns[mode][typeUser] = append(modeInsns[mode][typeUser], insn) 102 modeInsns[mode][typeAll] = append(modeInsns[mode][typeAll], insn) 103 } 104 } 105 } 106} 107 108// ModeInsns returns list of all instructions for the given mode. 109func ModeInsns(cfg *Config) []*Insn { 110 initOnce.Do(initInsns) 111 if cfg.Mode < 0 || cfg.Mode >= ModeLast { 112 panic("bad mode") 113 } 114 var insns []*Insn 115 insns = append(insns, modeInsns[cfg.Mode][typeUser]...) 116 if cfg.Priv { 117 insns = append(insns, modeInsns[cfg.Mode][typePriv]...) 118 if cfg.Exec { 119 insns = append(insns, modeInsns[cfg.Mode][typeExec]...) 120 } 121 } 122 return insns 123} 124 125func Generate(cfg *Config, r *rand.Rand) []byte { 126 initOnce.Do(initInsns) 127 var text []byte 128 for i := 0; i < cfg.Len; i++ { 129 insn := randInsn(cfg, r) 130 text = append(text, insn.Encode(cfg, r)...) 131 } 132 return text 133} 134 135func Mutate(cfg *Config, r *rand.Rand, text []byte) []byte { 136 initOnce.Do(initInsns) 137 insns := split(cfg, text) 138 retry := false 139 for stop := false; !stop || retry || len(insns) == 0; stop = r.Intn(2) == 0 { 140 retry = false 141 switch x := r.Intn(100); { 142 case x < 10 && len(insns) != 0: 143 // delete instruction 144 i := r.Intn(len(insns)) 145 copy(insns[i:], insns[i+1:]) 146 insns = insns[:len(insns)-1] 147 case x < 40 && len(insns) != 0: 148 // replace instruction with another 149 insn := randInsn(cfg, r) 150 text1 := insn.Encode(cfg, r) 151 i := r.Intn(len(insns)) 152 insns[i] = text1 153 case x < 70 && len(insns) != 0: 154 // mutate instruction 155 i := r.Intn(len(insns)) 156 text1 := insns[i] 157 for stop := false; !stop || len(text1) == 0; stop = r.Intn(2) == 0 { 158 switch x := r.Intn(100); { 159 case x < 5 && len(text1) != 0: 160 // delete byte 161 pos := r.Intn(len(text1)) 162 copy(text1[pos:], text1[pos+1:]) 163 text1 = text1[:len(text1)-1] 164 case x < 40 && len(text1) != 0: 165 // replace a byte 166 pos := r.Intn(len(text1)) 167 text1[pos] = byte(r.Intn(256)) 168 case x < 70 && len(text1) != 0: 169 // flip a bit 170 pos := r.Intn(len(text1)) 171 text1[pos] ^= 1 << byte(r.Intn(8)) 172 default: 173 // insert a byte 174 pos := r.Intn(len(text1) + 1) 175 text1 = append(text1, 0) 176 copy(text1[pos+1:], text1[pos:]) 177 text1[pos] = byte(r.Intn(256)) 178 } 179 } 180 insns[i] = text1 181 case len(insns) < cfg.Len: 182 // insert a new instruction 183 insn := randInsn(cfg, r) 184 text1 := insn.Encode(cfg, r) 185 i := r.Intn(len(insns) + 1) 186 insns = append(insns, nil) 187 copy(insns[i+1:], insns[i:]) 188 insns[i] = text1 189 default: 190 retry = true 191 } 192 } 193 text = nil 194 for _, insn := range insns { 195 text = append(text, insn...) 196 } 197 return text 198} 199 200func randInsn(cfg *Config, r *rand.Rand) *Insn { 201 var insns []*Insn 202 if cfg.Priv && cfg.Exec { 203 insns = modeInsns[cfg.Mode][r.Intn(3)] 204 } else if cfg.Priv { 205 insns = modeInsns[cfg.Mode][r.Intn(2)] 206 } else { 207 insns = modeInsns[cfg.Mode][typeUser] 208 } 209 return insns[r.Intn(len(insns))] 210} 211 212func split(cfg *Config, text []byte) [][]byte { 213 text = append([]byte{}, text...) 214 var insns [][]byte 215 var bad []byte 216 for len(text) != 0 { 217 n, err := Decode(cfg.Mode, text) 218 if err != nil || n == 0 { 219 bad = append(bad, text[0]) 220 text = text[1:] 221 continue 222 } 223 if bad != nil { 224 insns = append(insns, bad) 225 bad = nil 226 } 227 insns = append(insns, text[:n]) 228 text = text[n:] 229 } 230 if bad != nil { 231 insns = append(insns, bad) 232 } 233 return insns 234} 235 236func generateArg(cfg *Config, r *rand.Rand, size int) []byte { 237 v := generateInt(cfg, r, size) 238 arg := make([]byte, size) 239 for i := 0; i < size; i++ { 240 arg[i] = byte(v) 241 v >>= 8 242 } 243 return arg 244} 245 246func (insn *Insn) isCompatible(cfg *Config) bool { 247 if cfg.Mode < 0 || cfg.Mode >= ModeLast { 248 panic("bad mode") 249 } 250 if insn.Priv && !cfg.Priv { 251 return false 252 } 253 if insn.Pseudo && !cfg.Exec { 254 return false 255 } 256 if insn.Mode&(1<<uint(cfg.Mode)) == 0 { 257 return false 258 } 259 return true 260} 261 262func generateInt(cfg *Config, r *rand.Rand, size int) uint64 { 263 if size != 1 && size != 2 && size != 4 && size != 8 { 264 panic("bad arg size") 265 } 266 var v uint64 267 switch x := r.Intn(60); { 268 case x < 10: 269 v = uint64(r.Intn(1 << 4)) 270 case x < 20: 271 v = uint64(r.Intn(1 << 16)) 272 case x < 25: 273 v = uint64(r.Int63()) % (1 << 32) 274 case x < 30: 275 v = uint64(r.Int63()) 276 case x < 40: 277 v = specialNumbers[r.Intn(len(specialNumbers))] 278 if r.Intn(5) == 0 { 279 v += uint64(r.Intn(33)) - 16 280 } 281 case x < 50 && len(cfg.MemRegions) != 0: 282 mem := cfg.MemRegions[r.Intn(len(cfg.MemRegions))] 283 switch x := r.Intn(100); { 284 case x < 25: 285 v = mem.Start 286 case x < 50: 287 v = mem.Start + mem.Size 288 case x < 75: 289 v = mem.Start + mem.Size/2 290 default: 291 v = mem.Start + uint64(r.Int63())%mem.Size 292 } 293 if r.Intn(10) == 0 { 294 v += uint64(r.Intn(33)) - 16 295 } 296 default: 297 v = uint64(r.Intn(1 << 8)) 298 } 299 if r.Intn(50) == 0 { 300 v = uint64(-int64(v)) 301 } 302 if r.Intn(50) == 0 && size != 1 { 303 v &^= 1<<12 - 1 304 } 305 return v 306} 307 308var specialNumbers = []uint64{0, 1 << 15, 1 << 16, 1 << 31, 1 << 32, 1 << 47, 1 << 47, 1 << 63} 309