How to measure number of executed assembler instructions?

Question

I want to somehow get the "number of executed assembler instructions" from a binary. Consider the following piece of code:

if(password[0] == 'p') {
 if(password[1] == 'a') {
   ......
     printf("Correct Password\n");
 }
}

Then if I would start the program with e.g. "abc" it would not take the first branch, thus it would execute less instructions. If I put in "pbc" it would take the first branch, thus it would execute a little bit more (about 4-5) instructions. (This is some Research for CTF (Capture The Flag) files). So my idea is instead of reversing a binary and trying to understand the algorithm, I use the faster approach in counting the number of executed assembler instructions for different setups (like different characters or password lengths and so on to see if I can take another branch using another input thus creating more assembler instructions).

My basic idea would be to write a simple debugger just placing a int3 after the current Instruction, increment there a counter, disassembler the next instruction and place a int3 right after this instruction (strong simplified version of my idea).

Is there any program/library/... which already done that stuff? (Because I see some problemens when the program deals with signals, ...)

(I already tried using high precises timers to measure the time, but that was a complete fail because of the difference are just 4-5 instructions)

Koger

Apparently this kind of crack has a name, Timing attack en.wikipedia.org/wiki/Timing_attack However, it only works if the algorithm in question fails fast, or otherwise takes different amounts of time to execute based on its input, which is not guaranteed to be the case. – Spacial

Basically you're talking about doing an instruction trace. – Closeknit

No, I do not want to make a "timing attack" I don't want to use the "time" for comparison, I want to use the "number of executed instructions". Use time is not possible because of the bias. And I search for programs which I can use to do that – Totter

@rené freing Timing attacks can be done statistically, e.g. if you measure the average length taken to check password X 100,000 times, and then measure the average length taken to check password Y 100,000 times. (Although it's tricky to catch just 1 instruction differences without forcing the extra instruction to cause a page fault or otherwise delay it artificially). – Spacial

@Spacial I already tried this. E.g. I used the RDTSC register and measure the time for one password. I let it measure 10 000 000 times for the same password (and always printed out the fastest one). I did this for starting characters from "a" to "z" and the bias was always too high. E.g. I got values of about ~350 000 everytime (for the correct character and also for the incorrect ones) and sometimes some char had a very low number e.g. 290 000 and sometime a char had a very high number like 440 000. So from my tests it is not possible to make timing attacks for elf files on linux this way.. – Totter

@Spacial If we use time, the time will always vary between 2 executions. But if we measure the number of executed instructions they will always be the same for the same input. Thus they would be reliable and what give a much better feedback than using time. E.g. if a page fault occures the time will be much higher, but the number of executed instructions (from my process) will be the same! – Totter

Answer 1

The Linux "perf" tool can use hardware performance counters to give you precise numbers for lots of things including instructions executed.

$ perf stat true

 Performance counter stats for 'true':

          0.183734 task-clock                #    0.314 CPUs utilized          
                 0 context-switches          #    0.000 M/sec                  
                 0 CPU-migrations            #    0.000 M/sec                  
               118 page-faults               #    0.642 M/sec                  
           627,313 cycles                    #    3.414 GHz                    
           396,604 stalled-cycles-frontend   #   63.22% frontend cycles idle   
           268,222 stalled-cycles-backend    #   42.76% backend  cycles idle   
           404,935 instructions              #    0.65  insns per cycle        
                                             #    0.98  stalled cycles per insn
            75,949 branches                  #  413.364 M/sec                  
             3,602 branch-misses             #    4.74% of all branches        

       0.000584503 seconds time elapsed

To get only user-mode instructions:

$ perf stat -e instructions:u true

 Performance counter stats for 'true':

            92,687 instructions:u            #    0.00  insns per cycle        

       0.000520925 seconds time elapsed

I see a little bit of variance in this though, like 5-6 instructions. Not sure if that's real or just a measurement artifact. To get more reliable results, I think of turning to a simulator like Valgrind. I had some luck getting stable instruction counts that only vary by 1 instruction from these two commands:

$ valgrind --tool=callgrind true
$ valgrind --tool=exp-bbv true

Kazim

Hm, yeah that's exactly the output I'm looking for but with 1 problem: This tool gives me ALL instructions (also kernel instructions). Thus If I start it 100 times with the same input the instruction count will change everytime (in about 1000 - 10000 instructions). And I want to see a difference of 5 instructions, thus it is not possible if I use a CPU logging register. Anyone else knows a program which only monitors Usermode Instructions? – Totter

Try: perf stat -e instructions:u command. That will count only user-mode instructions. More info at perf.wiki.kernel.org/index.php/Tutorial#Counting_with_perf_stat – Kazim