CHAPTER 36. FIBONACCI NUMBERS CHAPTER 36. FIBONACCI NUMBERS
Let’s investigate the stack more closely. Comments were added by the author of this book^2 :
0035F940 00FD1039 RETURN to fib.00FD1039 from fib.00FD1000
0035F944 00000008 1st argument: a
0035F948 0000000D 2nd argument: b
0035F94C 00000014 3rd argument: limit
0035F950 /0035F964 saved EBP register
0035F954 |00FD1039 RETURN to fib.00FD1039 from fib.00FD1000
0035F958 |00000005 1st argument: a
0035F95C |00000008 2nd argument: b
0035F960 |00000014 3rd argument: limit
0035F964 ]0035F978 saved EBP register
0035F968 |00FD1039 RETURN to fib.00FD1039 from fib.00FD1000
0035F96C |00000003 1st argument: a
0035F970 |00000005 2nd argument: b
0035F974 |00000014 3rd argument: limit
0035F978 ]0035F98C saved EBP register
0035F97C |00FD1039 RETURN to fib.00FD1039 from fib.00FD1000
0035F980 |00000002 1st argument: a
0035F984 |00000003 2nd argument: b
0035F988 |00000014 3rd argument: limit
0035F98C ]0035F9A0 saved EBP register
0035F990 |00FD1039 RETURN to fib.00FD1039 from fib.00FD1000
0035F994 |00000001 1st argument: a
0035F998 |00000002 2nd argument: b
0035F99C |00000014 3rd argument: limit
0035F9A0 ]0035F9B4 saved EBP register
0035F9A4 |00FD105C RETURN to fib.00FD105C from fib.00FD1000
0035F9A8 |00000001 1st argument: a \
0035F9AC |00000001 2nd argument: b | prepared in main() for f1()
0035F9B0 |00000014 3rd argument: limit /
0035F9B4 ]0035F9F8 saved EBP register
0035F9B8 |00FD11D0 RETURN to fib.00FD11D0 from fib.00FD1040
0035F9BC |00000001 main() 1st argument: argc \
0035F9C0 |006812C8 main() 2nd argument: argv | prepared in CRT for main()
0035F9C4 |00682940 main() 3rd argument: envp /
The function is recursive^3 , hence stack looks like a “sandwich”. We see that thelimitargument is always the same (0x14or
20), but theaandbarguments are different for each call. There are also theRA-s and the savedEBPvalues. OllyDbg is able
to determine the EBP-based frames, so it draws these brackets. The values inside each bracket make thestack frame, in other
words, the stack area which each function incarnation uses as scratch space. We can also say that each function incarnation
must not access stack elements beyond the boundaries of its frame (excluding function arguments), although it’s technically
possible. It’s usually true, unless the function has bugs. Each savedEBPvalue is the address of the previousstack frame:
this is the reason why some debuggers can easily divide the stack in frames and dump each function’s arguments.
As we see here, each function incarnation prepares the arguments for the next function call.
At the end we see the 3 arguments formain().argcis 1 (yes, indeed, we have ran the program without command-line
arguments).
This easily to lead to a stack overflow: just remove (or comment out) the limit check and it will crash with exception
0xC00000FD(stack overflow.)
36.2 Example #2
My function has some redundancy, so let’s add a new local variablenextand replace all “a+b” with it:
#include <stdio.h>
void fib (int a, int b, int limit)
{
int next=a+b;
printf ("%d\n", next);
if (next > limit)
return;
fib (b, next, limit);
(^2) By the way, it’s possible to select several entries in OllyDbg and copy them to the clipboard (Ctrl-C). That’s what was done for this example.
(^3) i.e., it calls itself