OLD | NEW |
(Empty) | |
| 1 // Copyright 2015 Google Inc. All Rights Reserved. |
| 2 // |
| 3 // Licensed under the Apache License, Version 2.0 (the "License"); |
| 4 // you may not use this file except in compliance with the License. |
| 5 // You may obtain a copy of the License at |
| 6 // |
| 7 // http://www.apache.org/licenses/LICENSE-2.0 |
| 8 // |
| 9 // Unless required by applicable law or agreed to in writing, software |
| 10 // distributed under the License is distributed on an "AS IS" BASIS, |
| 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 12 // See the License for the specific language governing permissions and |
| 13 // limitations under the License. |
| 14 |
| 15 #include "syzygy/experimental/protect/protect_lib/code_randomizer.h" |
| 16 |
| 17 #include <string.h> |
| 18 #include <algorithm> |
| 19 #include <iostream> |
| 20 #include <vector> |
| 21 #include <type_traits> |
| 22 #include <iterator> |
| 23 |
| 24 #include "syzygy/core/disassembler_util.h" |
| 25 #include "syzygy/assm/assembler.h" |
| 26 #include "syzygy/assm/assembler_base.h" |
| 27 #include "syzygy/block_graph/basic_block_subgraph.h" |
| 28 #include "syzygy/block_graph/basic_block_assembler.h" |
| 29 #include "syzygy/block_graph/basic_block_decomposer.h" |
| 30 #include "syzygy/block_graph/analysis/liveness_analysis.h" |
| 31 |
| 32 #include "syzygy/experimental/protect/protect_lib/equation_gen.h" |
| 33 |
| 34 |
| 35 #define MOV "MOV" |
| 36 #define PUSH "PUSH" |
| 37 #define POP "POP" |
| 38 |
| 39 // Calculates N0 as N1 OP1 N2 OP2 N3 and stores it in reg |
| 40 void CodeRandomizer::GenerateAddress(block_graph::BasicBlockAssembler &assm, |
| 41 const assm::Register32 ®, uint32_t N0, assm::ValueSize reg_size) |
| 42 { |
| 43 uint32_t N1 = rand(); |
| 44 uint32_t N2 = rand(); |
| 45 uint32_t N3 = 0; |
| 46 int OP1_types = 8; |
| 47 |
| 48 assm.mov(reg, block_graph::Immediate(N1, reg_size)); |
| 49 |
| 50 switch (rand() % OP1_types) { |
| 51 case 0: |
| 52 // ADD |
| 53 assm.add(reg, block_graph::Immediate(N2, reg_size)); |
| 54 N3 = N1 + N2; |
| 55 break; |
| 56 |
| 57 case 1: |
| 58 // SUB |
| 59 assm.sub(reg, block_graph::Immediate(N2, reg_size)); |
| 60 N3 = N1 - N2; |
| 61 break; |
| 62 |
| 63 case 2: |
| 64 // IMUL |
| 65 assm.imul(reg, reg, block_graph::Immediate(N2, reg_size)); |
| 66 N3 = N1 * N2; |
| 67 break; |
| 68 |
| 69 case 3: |
| 70 // XOR |
| 71 assm.xor(reg, block_graph::Immediate(N2, reg_size)); |
| 72 N3 = N1 ^ N2; |
| 73 break; |
| 74 |
| 75 case 4: |
| 76 // AND |
| 77 assm.and(reg, block_graph::Immediate(N2, reg_size)); |
| 78 N3 = N1 & N2; |
| 79 break; |
| 80 |
| 81 case 5: |
| 82 // OR |
| 83 //assm.or(reg, block_graph::Immediate(N2, reg_size)); |
| 84 //N3 = N1 | N2; |
| 85 //break; |
| 86 |
| 87 case 6: |
| 88 // SHR |
| 89 N2 = N2 % 32; |
| 90 assm.shr(reg, block_graph::Immediate((uint8_t)N2, |
| 91 assm::ValueSize::kSize8Bit)); |
| 92 N3 = N1 >> N2; |
| 93 break; |
| 94 |
| 95 default: |
| 96 // SHL |
| 97 N2 = N2 % 32; |
| 98 assm.shl(reg, block_graph::Immediate((uint8_t)N2, |
| 99 assm::ValueSize::kSize8Bit)); |
| 100 N3 = N1 << N2; |
| 101 } |
| 102 |
| 103 // We now have (N1 OP1 N2) in reg and the result as N3 |
| 104 // Chose an inversable operation |
| 105 int OP2_types = 3; |
| 106 switch (rand() % OP2_types) { |
| 107 case 0: |
| 108 // ADD |
| 109 N3 = N0 - N3; |
| 110 assm.add(reg, block_graph::Immediate(N3, reg_size)); |
| 111 break; |
| 112 |
| 113 case 1: |
| 114 // SUB |
| 115 N3 = N3 - N0; |
| 116 assm.sub(reg, block_graph::Immediate(N3, reg_size)); |
| 117 break; |
| 118 |
| 119 default: |
| 120 // XOR |
| 121 N3 = N0 ^ N3; |
| 122 assm.xor(reg, block_graph::Immediate(N3, reg_size)); |
| 123 break; |
| 124 } |
| 125 |
| 126 // We now have in reg the value of the address, and we can use it |
| 127 } |
| 128 |
| 129 |
| 130 // Finds an unused register, in the context of the given state |
| 131 // @param assm assembler in use |
| 132 // @param state current state of the registers |
| 133 // @param save_reg out parameter marks the fact that the returned register |
| 134 // needs to be saved onto the stack |
| 135 // @returns the register which can be used |
| 136 const assm::Register32 FindSafeRegister(block_graph::BasicBlockAssembler &assm, |
| 137 RegState &state, bool &save_reg) |
| 138 { |
| 139 // Try all registers |
| 140 std::vector<const assm::Register32> regs; |
| 141 regs.push_back(assm::eax); |
| 142 regs.push_back(assm::ebx); |
| 143 regs.push_back(assm::ecx); |
| 144 regs.push_back(assm::edx); |
| 145 //regs.push_back(assm::esi); |
| 146 //regs.push_back(assm::edi); |
| 147 |
| 148 std::random_shuffle(regs.begin(), regs.end()); |
| 149 |
| 150 for (int i = 0; i < (int)regs.size(); ++i) |
| 151 if (state.IsSafe(regs[i].id())) { |
| 152 save_reg = false; |
| 153 return regs[i]; |
| 154 } |
| 155 |
| 156 save_reg = true; |
| 157 return regs[0]; |
| 158 } |
| 159 |
| 160 #define MAX_STEPS 32 |
| 161 #define INC_STEP 4 |
| 162 #define SKIPPING_LIKELINESS 6 |
| 163 |
| 164 void CodeRandomizer::RandModifyESP(block_graph::BasicBlockAssembler &assm, |
| 165 RegState &state) |
| 166 { |
| 167 int range = MAX_STEPS; |
| 168 int val = (std::rand() % range) * INC_STEP; |
| 169 |
| 170 // On the first two cases we do either a SUB or an ADD |
| 171 switch (std::rand() % SKIPPING_LIKELINESS) { |
| 172 case 0: |
| 173 RandAdd(assm, assm::esp, val * 4, //bytes not bits |
| 174 assm::ValueSize::kSize32Bit, state); |
| 175 state.extra_stack -= val; |
| 176 state.instruction_count += 1; |
| 177 break; |
| 178 |
| 179 case 1: |
| 180 RandSub(assm, assm::esp, val * 4, //bytes not bits |
| 181 assm::ValueSize::kSize32Bit, state); |
| 182 state.extra_stack += val; |
| 183 state.instruction_count += 1; |
| 184 break; |
| 185 |
| 186 default: |
| 187 ; |
| 188 } |
| 189 } |
| 190 |
| 191 void CodeRandomizer::ClearExtraStack(block_graph::BasicBlockAssembler &assm, |
| 192 RegState &state) |
| 193 { |
| 194 if (state.extra_stack) { |
| 195 RandAdd(assm, assm::esp, state.extra_stack * 4, // bytes not bits |
| 196 assm::ValueSize::kSize32Bit, state); |
| 197 state.instruction_count += 1; |
| 198 state.extra_stack = 0; |
| 199 } |
| 200 } |
| 201 |
| 202 void CodeRandomizer::RandAdd(block_graph::BasicBlockAssembler &assm, |
| 203 const assm::Register32 ®, uint32_t val, assm::ValueSize reg_size, |
| 204 RegState &state) |
| 205 { |
| 206 assm.add(reg, block_graph::Immediate(val, reg_size)); |
| 207 state.instruction_count += 1; |
| 208 } |
| 209 |
| 210 void CodeRandomizer::RandSub(block_graph::BasicBlockAssembler &assm, |
| 211 const assm::Register32 ®, uint32_t val, assm::ValueSize reg_size, |
| 212 RegState &state) |
| 213 { |
| 214 assm.sub(reg, block_graph::Immediate(val, reg_size)); |
| 215 state.instruction_count += 1; |
| 216 } |
| 217 |
| 218 template<typename T> |
| 219 void CodeRandomizer::RandPush(block_graph::BasicBlockAssembler &assm, |
| 220 const T &source, assm::ValueSize size, RegState &state) |
| 221 { |
| 222 uint32_t reg_size = (uint32_t)size / 8; |
| 223 if (std::rand() % 3 == 0) { |
| 224 ClearExtraStack(assm, state); |
| 225 assm.push(source); |
| 226 state.instruction_count += 1; |
| 227 |
| 228 } |
| 229 else { |
| 230 bool save_temp = true; |
| 231 bool transfer_directly = false; // mov from register or via another reg |
| 232 uint32_t offset = 0; |
| 233 const assm::Register32 temp = FindSafeRegister(assm, state, save_temp); |
| 234 |
| 235 // Unless the source is an operand, we can try to transfer |
| 236 // it directly to the stack |
| 237 if (!std::is_same<T, block_graph::BasicBlockAssembler::Operand>::value) |
| 238 if (std::rand() % 2) |
| 239 transfer_directly = true; |
| 240 |
| 241 // If there are no free registers, save the temp value |
| 242 if (save_temp && !transfer_directly) { |
| 243 // Bring back ESP to it's correct value and allocate |
| 244 // one extra space so that the temp can be saved |
| 245 ClearExtraStack(assm, state); |
| 246 RandSub(assm, assm::esp, reg_size, assm::ValueSize::kSize32Bit, state); |
| 247 assm.push(temp); |
| 248 |
| 249 state.instruction_count += 1; |
| 250 offset += reg_size; |
| 251 } |
| 252 |
| 253 // Emit the code |
| 254 // (maybe)SUB/ADD ESP, RAND * REG_SIZE |
| 255 // (maybe) PUSH TEMP |
| 256 // (maybe) MOV TEMP, SOURCE |
| 257 // (maybe)SUB / ADD ESP, RAND * REG_SIZE |
| 258 // MOV [ESP + offset], TEMP/SOURCE |
| 259 // (maybe)SUB / ADD ESP, RAND * REG_SIZE |
| 260 // (maybe) POP TEMP |
| 261 RandModifyESP(assm, state); |
| 262 |
| 263 if (transfer_directly) { |
| 264 state.extra_stack--; |
| 265 offset += state.extra_stack; |
| 266 |
| 267 if (std::is_same<T, assm::Register32>::value) { |
| 268 assm.mov(block_graph::Operand(assm::esp, |
| 269 block_graph::Displacement(offset * reg_size, |
| 270 assm::ValueSize::kSize32Bit)), |
| 271 *((assm::Register32 *)(&source))); |
| 272 } |
| 273 else if (std::is_same<T, |
| 274 block_graph::BasicBlockAssembler::Immediate>::value) { |
| 275 assm.mov(block_graph::Operand(assm::esp, |
| 276 block_graph::Displacement(offset * reg_size, |
| 277 assm::ValueSize::kSize32Bit)), |
| 278 *((block_graph::BasicBlockAssembler::Immediate *)(&source))); |
| 279 } |
| 280 |
| 281 state.instruction_count += 1; |
| 282 |
| 283 } |
| 284 else { |
| 285 assm.mov(temp, source); |
| 286 RandModifyESP(assm, state); |
| 287 |
| 288 state.extra_stack--; |
| 289 offset += state.extra_stack; |
| 290 assm.mov(block_graph::Operand(assm::esp, |
| 291 block_graph::Displacement(offset * reg_size, |
| 292 assm::ValueSize::kSize32Bit)), |
| 293 temp); |
| 294 |
| 295 state.instruction_count += 2; |
| 296 } |
| 297 |
| 298 // Restore the register if it was saved |
| 299 if (save_temp) { |
| 300 ClearExtraStack(assm, state); |
| 301 assm.pop(temp); |
| 302 state.instruction_count++; |
| 303 state.extra_stack++; |
| 304 } |
| 305 |
| 306 RandModifyESP(assm, state); |
| 307 } |
| 308 |
| 309 state.Delete(((assm::Register32 *)(&source))->id()); |
| 310 } |
| 311 |
| 312 template<typename T> |
| 313 void CodeRandomizer::RandPop(block_graph::BasicBlockAssembler &assm, |
| 314 const T &destination, assm::ValueSize reg_size, RegState &state) |
| 315 { |
| 316 if (std::rand() % 3) { |
| 317 ClearExtraStack(assm, state); |
| 318 assm.pop(destination); |
| 319 state.instruction_count += 1; |
| 320 |
| 321 } |
| 322 else { |
| 323 bool save_temp = true; |
| 324 bool transfer_directly = false; |
| 325 uint32_t offset = 0; |
| 326 const assm::Register32 temp = FindSafeRegister(assm, state, save_temp); |
| 327 |
| 328 |
| 329 // Unless the source is an operand, we can try to transfer |
| 330 // it directly to the stack |
| 331 if (!std::is_same<T, block_graph::BasicBlockAssembler::Operand>::value) |
| 332 if (std::rand() % 2) |
| 333 transfer_directly = true; |
| 334 |
| 335 // If there are no free registers, save the temp register |
| 336 if (save_temp && !transfer_directly) { |
| 337 // Bring back ESP to it's correct value and allocate |
| 338 // one extra space so that the temp can be saved |
| 339 ClearExtraStack(assm, state); |
| 340 assm.push(temp); |
| 341 state.instruction_count += 2; |
| 342 offset += reg_size; |
| 343 } |
| 344 |
| 345 // Emit the code |
| 346 // (maybe)SUB / ADD ESP, RAND * REG_SIZE |
| 347 // (maybe) PUSH TEMP |
| 348 // (maybe)SUB / ADD ESP, RAND * REG_SIZE |
| 349 // MOV TEMP/DEST, [ESP + offset] |
| 350 // (maybe) MOV DEST, TEMP |
| 351 // (maybe)SUB / ADD ESP, RAND * REG_SIZE |
| 352 // (maybe) POP TEMP |
| 353 RandModifyESP(assm, state); |
| 354 |
| 355 // Pretty bad. |
| 356 if (transfer_directly) { |
| 357 offset += state.extra_stack; |
| 358 assm.mov(block_graph::Operand(assm::esp, |
| 359 block_graph::Displacement(offset, assm::ValueSize::kSize32Bit)), |
| 360 *((assm::Register32 *)(&destination))); |
| 361 |
| 362 state.instruction_count++; |
| 363 state.extra_stack++; |
| 364 |
| 365 } |
| 366 else { |
| 367 RandModifyESP(assm, state); |
| 368 offset += state.extra_stack; |
| 369 assm.mov(temp, block_graph::Operand(assm::esp, |
| 370 block_graph::Displacement(offset, assm::ValueSize::kSize32Bit))); |
| 371 assm.mov(destination, temp); |
| 372 |
| 373 state.instruction_count += 2; |
| 374 state.extra_stack++; |
| 375 } |
| 376 |
| 377 |
| 378 // Restore the register if it was saved |
| 379 if (save_temp) |
| 380 assm.pop(temp); |
| 381 |
| 382 // Restore the register if it was saved |
| 383 if (save_temp) { |
| 384 ClearExtraStack(assm, state); |
| 385 assm.pop(temp); |
| 386 state.instruction_count++; |
| 387 } |
| 388 |
| 389 RandModifyESP(assm, state); |
| 390 } |
| 391 |
| 392 if (std::is_same<T, assm::Register32>::value) |
| 393 state.Add(((assm::Register32 *)(&destination))->id()); |
| 394 } |
| 395 |
| 396 template void CodeRandomizer::RandPush<assm::Register32>( |
| 397 block_graph::BasicBlockAssembler &, |
| 398 const assm::Register32 &, assm::ValueSize, RegState &); |
| 399 |
| 400 template void CodeRandomizer:: |
| 401 RandPush<block_graph::BasicBlockAssembler::Immediate>( |
| 402 block_graph::BasicBlockAssembler &, |
| 403 const block_graph::BasicBlockAssembler::Immediate &, |
| 404 assm::ValueSize, RegState &); |
| 405 |
| 406 template void CodeRandomizer:: |
| 407 RandPush<block_graph::BasicBlockAssembler::Operand>( |
| 408 block_graph::BasicBlockAssembler &, |
| 409 const block_graph::BasicBlockAssembler::Operand &, |
| 410 assm::ValueSize, RegState &); |
| 411 |
| 412 template void CodeRandomizer::RandPop<assm::Register32>( |
| 413 block_graph::BasicBlockAssembler &, |
| 414 const assm::Register32 &, assm::ValueSize, RegState &); |
| 415 |
| 416 template void CodeRandomizer:: |
| 417 RandPop<block_graph::BasicBlockAssembler::Operand>( |
| 418 block_graph::BasicBlockAssembler &, |
| 419 const block_graph::BasicBlockAssembler::Operand &, assm::ValueSize, |
| 420 RegState &); |
OLD | NEW |