Assuming that I have binary file with code for unknow CPU can I somehow detect cpu architecture? I know that it depends mostly on compiler but I think that for most of CPU architectures it should be alot of CALL/RETN/JMP/PUSH/POP opcodes (statistically more than others). Or maybe should I search for some patterns in code specific for CPU (instead of opcodes occurrence)?
When you have a hammer, all the problems look like nails...
I´ve studied something called Normalized Compression Distance - NCD - some time ago, and I'd give it a try if I had a problem similar to yours.
I´d make a database of examples. Would take 20 programs for each architecture you want to know, with variable sizes, and save them.
When confronted with a program that I wanted to know which architecture it is, I´d compute it´s NCD against all my examples.
I´d pick the best (smaller) NCD and would then verify it if is was a real match (let´s say, trying to run it on the discovered architecture).
I´ve always done in by hand, when it comes to NCD. How I did it:
you have 20 files for SPARC and you call them A01, A02, A03, and so on. Your x86 files: B01, B02, etc.
You get the unknown file and call it XX.
Choose your preferred compression tool (I used Gzip, but see remarks at the end of this answer).
Calculate NCD for the first pair:
NCD(XX,A01) = ( Z(XX+A01) - min(Z(XX), Z(A01) ) / max(Z(XX), Z(A01))
Z( something ) -> means that you compress the something with Gzip and get the file size after compression. For example, 8763 bytes, so Z(something) = 8763.
XX + A01 -> means that you concatenate things. You append the A01 file to the end of the XX file. In linux, you could do a ´cat XX A01 > XXA01´.
min() and max() -> you calculate the compressed size of XX and A01, and use the minimum and maximum that you get.
So you´ll have a NCD value: it´ll lie between 0 and 1, and use as many decimals places as you can, because sometimes the difference is in the 7th or 8th digit. It´ll be like comparing 0.999999887 to 0.999999524.
You´ll do that for every file, so you´ll have 20 NCD results for SPARC, 20 for x86...
Get the smaller NCD of all. Let´s say that the B07 file gave you the smaller NCD. So, probably, the unknow file is a x86.
your unknow and your test files must have a similar size. When you compare a file with bigger or smaller ones, NCD won´t do it´s magic. So, if you´ll be testing files of 5 to 10k, I´d get test files of 2.5k, 5k, 7.5k, 10k, 12.5k ...
In my Master degree I got better results always using the smaller NCD value. The second best method was to do some voting: get the 5 smaller NCD results, and see which architecture got more votes. Ex.: smaller NCD were A03, A05, B02, B06, B07 -> B go 3 votes, so I´d say it´s a x86...
compressors based on the Zip construction have a limitation of 32kB: the way they compress things, they just consider 32kB at time. If your XX + A01 is bigger than this, Gzip, Zip, etc., won´t give you good results. So, for files that are bigger than 15 or 16kB, I´d choose another compressor: PPMD, Bzip...
There are some tools that can scan binary files for common opcodes found in various architectures. Binwalk's -A option does this for example (it scans for ARM/MIPS/x86 and several other architectures).
Typically, I try the most common CPUs first (ARM, PPC, MIPS and AVR), try to find if any of the plain strings says something about the processor, etc... And, when all else fail, I give a try to what you're asking for: statistical analysis of opcodes (if I'm sure it isn't neither encrypted nor compressed).
I recommend you to read the Alexander Chernov and Katerina Troshina presentation "Reverse engineering of binary programs for custom virtual machines". Writing a tool like the one they wrote must be very hard (I guess) but writing a tool to try to determine which CPU seems to be compiled for using the techniques described in that presentation is not that hard (as long as you can collect enough samples for multiple different architectures).
My lazy hack: a small Python script which calculates bigram and trigram counts. I then search for a couple of the most common sequences on Google (quoted hex). Quite often I manage to find some hex dumps and can figure the CPU from the context. It would work even better if Google could search by raw binary values...
Machine learning can be used to identify the target CPU of machine code with a high degree of accuracy. For example, the ISAdetect tool can identify machine code targeting 23 different architectures using machine learning. There is a web API that one can use to upload executable binaries or pieces of machine code to be analyzed by this tool.
Here is the paper discussing the techniques implemented by ISAdetect:
Two additional methods that haven't been mentioned yet.
binwalk's disassembly scan (note: must have
Disassembly Scan Options: -Y, --disasm Identify the CPU architecture of a file using the capstone disassembler -T, --minsn=<int> Minimum number of consecutive instructions to be considered valid (default: 500) -k, --continue Don't stop at the first match
Example output (image is ARM LE):
$ binwalk -Yk image.img DECIMAL HEXADECIMAL DESCRIPTION -------------------------------------------------------------------------------- 3 0x3 ARM executable code, 32-bit, big endian, at least 726 valid instructions 1048576 0x100000 ARM executable code, 32-bit, little endian, at least 1250 valid instructions 2099012 0x200744 ARM executable code, 32-bit, little endian, at least 846 valid instructions 3158316 0x30312C ARM executable code, 32-bit, little endian, at least 899 valid instructions 4201328 0x401B70 ARM executable code, 32-bit, little endian, at least 1250 valid instructions 5253066 0x5027CA ARM executable code, 16-bit (Thumb), big endian, at least 2499 valid instructions 6308406 0x604236 ARM executable code, 16-bit (Thumb), little endian, at least 2499 valid instructions
Can be used as either a standalone tool or a
Statistical CPU guessing Options: -%, --markov Identify the CPU opcodes in a file using statistical analysis
Example output, used as a binwalk module (image is ARM LE):
$ binwalk -% image.img DECIMAL HEXADECIMAL DESCRIPTION -------------------------------------------------------------------------------- 0 0x0 None (size=0x800, entropy=0.757822) 2048 0x800 CLIPPER (size=0x800, entropy=0.728492) 4096 0x1000 None (size=0x2000, entropy=0.129643) 12288 0x3000 ARMel (size=0x35c000, entropy=0.795123) 3534848 0x35F000 None (size=0x800, entropy=0.797443) 3536896 0x35F800 ARMel (size=0x16800, entropy=0.834972) 3629056 0x376000 None (size=0x800, entropy=0.764094) 3631104 0x376800 ARMel (size=0x16a000, entropy=0.797543) 5113856 0x4E0800 None (size=0x1800, entropy=0.841936) 5120000 0x4E2000 ARMel (size=0x1000, entropy=0.812677) 5124096 0x4E3000 None (size=0x1000, entropy=0.844949) 5128192 0x4E4000 ARMel (size=0xc000, entropy=0.792995) 5177344 0x4F0000 None (size=0x24000, entropy=0.763681) 5324800 0x514000 6502 (size=0x24000, entropy=0.974422) 5472256 0x538000 None (size=0x137800, entropy=0.728785)