3

I am searching for an algorithm and/or snippet of code that provides a one-pass algorithm over a steady datastream that can detect a valid sequence of bytecode or opcode.

There are no PE32, ELF, or Mach0 header information available to assist; so that means, none of the following entry-point, offset, segment, nor section information are on hand.

I'd like to think that ARM is harder than Intel.

Google isn't turning up much, so I figured that I must be using wrong terminology here.

  • 1
    "detect a valid sequence of bytecode or opcode" -- define valid. – Jason Geffner Aug 1 '15 at 0:07
  • Valid, perhaps I've overused that word. How about "an executable sequence of opcode" (or bytecode)? – John Greene Aug 1 '15 at 0:10
  • Tempted to say, "no". What is this stream - can it start in the middle of an instruction? Must it be valid code all the way up to a ret instruction (or equivalent, for other CPUs)? Can it end with a call or jump to terminating code elsewhere? If you encounter an invalid instruction, would you restart your scan one byte later from the start and test again? – usr2564301 Aug 1 '15 at 10:44
  • I'm thinking of a 4-state latch on a byte-boundary to get that valid opcode stream detector. Perhap, we can "name that tune" in 3 states? – John Greene Aug 1 '15 at 12:32
  • Wild idea here, but couldn't you feed this stream into an emulator of the specific architecture you're working with? – Tomás Senart Aug 2 '15 at 8:45
2

First of all, ARM is much easier than Intel because it has fixed instruction length, (if I remember right) requires instructions to be aligned by 2 or 4 and has limited capabilities for arbitrary code self-modification because of its Harvard architecture.

I'd like to say that there is no such an algorithm, and in general case such an algorithm is impossible, for example because of possible self-modification of the code and using exceptions and traps in a regular code flow, so the only general way to achieve the desired result is an emulation.

The rest of the answer depends on more exact definition of required algorithm, target architecture and validity of the sequence.

0

I don't think there is an optimal algorithm to search for byte code... Unless you know something else about the data stream, such as it is base 64 encoded, etc.

One thing you could do is see if there is an excessive amount of NOP bytes (0x90, x86) but if one really wanted to, they could find ways to do the equivalent of NOP with different op codes.

  • Oh, the NOP sled. That's too specific. Perhaps, there's enough operands to key to the associative opcodes, no? – John Greene Aug 1 '15 at 2:08
  • I agree it is too specific. I would've put the above as a comment, but apparently there are some arcane rules about who may comment. I mean if you have an endless amount of free cpu cycles, you could disassemble the op codes at every byte and see if it results in any strange syscalls or shell execution. Then flag that for further analysis – Viktor Aug 1 '15 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.