-1

I have written two small programs in which I declare a very small array.

Then I try to access values out of bounds.

The interesting thing I noticed that when I try to decrement the index I can decrement this very very further away. If I try to increment it the program crashes much faster.

This is my two codes and the results:

 #include<stdio.h>
 int main()
 {
     int i=0;                                                                
     int a[2];

     while(1)
     {
         a[-10000]=8;
         printf("i is: %d and the value a[i] is: %d\n",i,a[i]);
         i--;

      }

      return 0;
 }

The final lines of the result are:

i is: -3143957 the value of a[i] is: 0 i is: -3143958 the value of a[i] is: 0 i is: -3143959 the value of a[i] is: 0 i is: -3143960 the value of a[i] is: 0 i is: -3143961 the value of a[i] is: 0 i is: -3143962 the value of a[i] is: 0 i is: -3143963 the value of a[i] is: 0 i is: -3143964 the value of a[i] is: 0 Segmentation fault

However when I try to increment the index i

 #include<stdio.h>
 int main()
 {
     int i=0;                                                                
     int a[2];

     while(1)
     {
         a[-10000]=8;
         printf("i is: %d and the value a[i] is: %d\n",i,a[i]);
         i++;

      }

      return 0;
 }

I get the following result: i is: 2306 and the value a[i] is: 1869098813 i is: 2307 and the value a[i] is: 1764713837 i is: 2308 and the value a[i] is: 1634624869 i is: 2309 and the value a[i] is: 795175011 i is: 2310 and the value a[i] is: 1802724676 i is: 2311 and the value a[i] is: 7368564 i is: 2312 and the value a[i] is: 778121006 i is: 2313 and the value a[i] is: 7632239 i is: 2314 and the value a[i] is: 0 i is: 2315 and the value a[i] is: 0

The difference between how much I can go UP and how much I can go DOWN is HUGE. Why is that.

Some things to mention: I KNOW that this is undefined behavior. My question is strictly about WHY can I go much much further UP vs DOWN when going OUT OF BOUNDS of an array.

8
  • Both behaviours are undefined, so what specifically happens on each run is going to be because of how that particular compiler decided to lay things out. It is totally arbitrary
    – Caleth
    Sep 14, 2017 at 10:00
  • @Caleth you're correct it's UB but it's not completely arbitrary. The compiler is doing something deterministically. Although it's necessary to warn folk of the dangers of relying on UB in shipped code, IMO this kind of experimentation is healthy. Having an understanding of what the compiler is doing can also be very useful when debugging esp in C.
    – Alex
    Sep 14, 2017 at 10:30
  • What the something is, is completely arbitrary. It is also permitted to not be deterministic
    – Caleth
    Sep 14, 2017 at 11:20
  • @Caleth it is permitted to be non-deterministic but it very rarely is. It's also rarely arbitrary for a given compiler. Again, relying on the behaviour is fraught and should be avoided as far as possible. Understanding the behaviour seems entirely reasonable as a learning opportunity.
    – Alex
    Sep 14, 2017 at 11:29
  • @Alex someone on the compiler team chose "push stack is increment sp" or "push stack is decrement sp". Someone else choose "sp starts at 0x00800000" or w/e. Those were arbitrary choices, from the pov of correctly implementing C semantics
    – Caleth
    Sep 14, 2017 at 11:33

1 Answer 1

2

It is mostly coincidence that you can read more garbage by decrementing than incrementing.

What's likely happening is that the compiler has put the address of a[0] on the stack. The compiler will also have reserved some memory for the stack in general and probably put a guard page after that memory to catch stack overflows.

What I suspect is happening when you decrement is that you're walking along the reserved stack memory until you hit the guard page and seg faulting.

Now, the compiler will have reserved some global memory for various things in the runtime above the stack. What I suspect is happening when you increment is that it is walking that memory until it hits another page fault on memory that it can't read. It is likely that it reserved less global memory than it did stack memory hence it can increment less than it can decrement.

You can experiment with this. For example, by putting a large array on the stack before the int a[2] declaration, you should be able to walk that extra memory on increment before it barfs. If that doesn't work (it might not as the compiler can re-order the variables on the stack within a function) then having the large array in main and putting the stack walk loop in a function called by main should do the trick.

Note, however, this is all largely supposition without knowing details about the machine, OS and compiler. For example, I am assuming that the stack grows downwards which isn't universally true.

BTW not sure why you have the statement a[-10000]=8; but it's probably not doing what you think it's doing. Specifically, the compiler will, almost definitely be able to establish statically that this is UB and, being UB, could choose to do just about anything with it; complete removal being the most likely.

9
  • you are correct. I modified the code and I added a large array before the declaration of my array that I am testing. Now I can go upwards much more than before. However I have another strange behavior. Although my array is of type INT, all the values in the memory are interpreted as positive values. This seems really strange to me. Do you have any idea why that might be happening?
    – yoyo_fun
    Sep 14, 2017 at 10:17
  • @yoyo_fun The zeros in the decrement are probably because your OS is zeroing out memory pages when it gives them to a process. As the compiler hasn't written anything yet, they're still zero. For the increment, it'll depend on what data is stored there for the runtime. Conceivably, some of it is interned ASCII strings which never have their high bit set but that's just a wild stab in the dark.
    – Alex
    Sep 14, 2017 at 10:39
  • @yoyo_fun Thinking further, pointers to userspace may not have their high bit set, depending on the OS. So some of the larger numbers that are all of a similar size may be pointers. I thought this unlikely initially but alignment considerations make it more probable.
    – Alex
    Sep 14, 2017 at 11:22
  • what do you mean by "ASCII strings which never have their high bit set" ?
    – yoyo_fun
    Sep 14, 2017 at 11:23
  • @yoyo_fun string literals that are in code e.g. the specification string in your printf, are stored in memory when the program is loaded. Now, if they are ASCII strings, like yours is, they are encoded using only 7-bits of the byte and every byte will have zero as its high bit. If your a[i] happens to pick any 4 of them to make an int, then it will always produce a positive integer. What I'm not sure is whether or not the compiler would put them where you're looking or in read only memory with the program binary.
    – Alex
    Sep 14, 2017 at 11:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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