Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #105365 > unrolled thread

Stackoverflow, and how C uses stack to remember function calls

Back to article view | Back to comp.lang.c

Contents

  Stackoverflow, and how C uses stack to remember function calls Alla <vitale.alla@gmail.com> - 2017-03-04 14:40 +0300
    Re: Stackoverflow, and how C uses stack to remember function calls Malcolm McLean <malcolm.mclean5@btinternet.com> - 2017-03-04 03:53 -0800
      Re: Stackoverflow, and how C uses stack to remember function calls Alla <vitale.alla@gmail.com> - 2017-03-04 14:58 +0300
        Re: Stackoverflow, and how C uses stack to remember function calls Malcolm McLean <malcolm.mclean5@btinternet.com> - 2017-03-04 04:04 -0800
          Re: Stackoverflow, and how C uses stack to remember function calls Alla <vitale.alla@gmail.com> - 2017-03-04 15:12 +0300
      Re: Stackoverflow, and how C uses stack to remember function calls mark.bluemel@gmail.com - 2017-03-06 00:41 -0800
    Re: Stackoverflow, and how C uses stack to remember function calls David Brown <david.brown@hesbynett.no> - 2017-03-04 13:30 +0100
      Re: Stackoverflow, and how C uses stack to remember function calls Alla <vitale.alla@gmail.com> - 2017-03-04 15:34 +0300
        Re: Stackoverflow, and how C uses stack to remember function calls David Brown <david.brown@hesbynett.no> - 2017-03-04 15:23 +0100
          Re: Stackoverflow, and how C uses stack to remember function calls Alla <vitale.alla@gmail.com> - 2017-03-04 18:22 +0300
            Re: Stackoverflow, and how C uses stack to remember function calls Chad <cdalten@gmail.com> - 2017-03-04 07:53 -0800
          Re: Stackoverflow, and how C uses stack to remember function calls Alla <vitale.alla@gmail.com> - 2017-03-04 19:29 +0300
    Re: Stackoverflow, and how C uses stack to remember function calls "James R. Kuyper" <jameskuyper@verizon.net> - 2017-03-04 11:18 -0500
      Re: Stackoverflow, and how C uses stack to remember function calls Alla <vitale.alla@gmail.com> - 2017-03-04 20:10 +0300
        Re: Stackoverflow, and how C uses stack to remember function calls "James R. Kuyper" <jameskuyper@verizon.net> - 2017-03-04 13:18 -0500
          Re: Stackoverflow, and how C uses stack to remember function calls Alla <vitale.alla@gmail.com> - 2017-03-04 22:43 +0300
      Re: Stackoverflow, and how C uses stack to remember function calls supercat@casperkitty.com - 2017-03-04 14:33 -0800
        Re: Stackoverflow, and how C uses stack to remember function calls Ian Collins <ian-news@hotmail.com> - 2017-03-05 11:50 +1300
          Re: Stackoverflow, and how C uses stack to remember function calls supercat@casperkitty.com - 2017-03-05 11:12 -0800
            Re: Stackoverflow, and how C uses stack to remember function calls Ian Collins <ian-news@hotmail.com> - 2017-03-06 17:11 +1300
              Re: Stackoverflow, and how C uses stack to remember function calls supercat@casperkitty.com - 2017-03-06 07:23 -0800
                Re: Stackoverflow, and how C uses stack to remember function calls David Brown <david.brown@hesbynett.no> - 2017-03-06 17:22 +0100
                  Re: Stackoverflow, and how C uses stack to remember function calls scott@slp53.sl.home (Scott Lurndal) - 2017-03-06 16:40 +0000
                    Re: Stackoverflow, and how C uses stack to remember function calls jm.bourguet@gmail.com - 2017-03-06 09:04 -0800
                      Re: Stackoverflow, and how C uses stack to remember function calls scott@slp53.sl.home (Scott Lurndal) - 2017-03-06 17:18 +0000
                        Re: Stackoverflow, and how C uses stack to remember function calls Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2017-03-06 11:22 -0700
                      Re: Stackoverflow, and how C uses stack to remember function calls luser droog <luser.droog@gmail.com> - 2017-03-06 09:58 -0800
                        Re: Stackoverflow, and how C uses stack to remember function calls luser droog <luser.droog@gmail.com> - 2017-03-06 10:04 -0800
    Re: Stackoverflow, and how C uses stack to remember function calls Barry Schwarz <schwarzb@dqel.com> - 2017-03-04 09:33 -0800
      Re: Stackoverflow, and how C uses stack to remember function calls Alla <vitale.alla@gmail.com> - 2017-03-04 22:46 +0300
    Re: Stackoverflow, and how C uses stack to remember function calls Keith Thompson <kst-u@mib.org> - 2017-03-04 12:25 -0800

Page 2 of 2 — ← Prev page 1 [2]

#105482

On Sunday, March 5, 2017 at 10:11:23 PM UTC-6, Ian Collins wrote:
> I still don't see how any of this is related to the OP, or the mythical 
> past you keep referring to....

Although the way function calls were handled on the original PDP-11
version of C was never a capital-S "standard", people implementing C on
other platforms have nonetheless tended follow the same approach *even on
platforms where other calling conventions were already established*.  I used
compilers for the Z80, 8088, 80386, 68000, and 68HC11, among other platforms,
that used exactly the same approach.  If I were given a compiler for an
other platform which used a top-down function call stack and included a
frame pointer or a register that could be used as one, I would expect that
it would, likely as not, work the same way.  The ARM is a little weird
because its subroutine-call instruction does not push the return address, but
the return address often does end up getting stacked by the calling function
much as it would if the subroutine-call instruction had saved it.

Nothing in the C Standard requires that implementations use a stack in such a
fashion, but common implementations generally do whether or not the Standard
requires it.

[toc] | [prev] | [next] | [standalone]

#105486

On 06/03/17 16:23, supercat@casperkitty.com wrote:
> On Sunday, March 5, 2017 at 10:11:23 PM UTC-6, Ian Collins wrote:
>> I still don't see how any of this is related to the OP, or the mythical 
>> past you keep referring to....
> 
> Although the way function calls were handled on the original PDP-11
> version of C was never a capital-S "standard", people implementing C on
> other platforms have nonetheless tended follow the same approach *even on
> platforms where other calling conventions were already established*.  I used
> compilers for the Z80, 8088, 80386, 68000, and 68HC11, among other platforms,
> that used exactly the same approach.  If I were given a compiler for an
> other platform which used a top-down function call stack and included a
> frame pointer or a register that could be used as one, I would expect that
> it would, likely as not, work the same way.  The ARM is a little weird
> because its subroutine-call instruction does not push the return address, but
> the return address often does end up getting stacked by the calling function
> much as it would if the subroutine-call instruction had saved it.
> 
> Nothing in the C Standard requires that implementations use a stack in such a
> fashion, but common implementations generally do whether or not the Standard
> requires it.
> 

None of this is related to the OP's question.

It is nothing more than "We need to have a calling convention that works
even if we don't know the number of arguments.  What would work
efficiently?".

And no, the ARM is not "weird" about its subroutine calls - the majority
of RISC architectures use the same technique as it is more efficient
than stacking the return address (after all, most function calls are
leaf calls).

[toc] | [prev] | [next] | [standalone]

#105489

David Brown <david.brown@hesbynett.no> writes:
>On 06/03/17 16:23, supercat@casperkitty.com wrote:
 [snip]
>> The ARM is a little weird
>> because its subroutine-call instruction does not push the return address, but
>> the return address often does end up getting stacked by the calling function
>> much as it would if the subroutine-call instruction had saved it.
 [snip]
>And no, the ARM is not "weird" about its subroutine calls - the majority
>of RISC architectures use the same technique as it is more efficient
>than stacking the return address (after all, most function calls are
>leaf calls).

Weird is the PDP-8, which stored the return address in the
first word of the target codestream :-)

[toc] | [prev] | [next] | [standalone]

#105492

Le lundi 6 mars 2017 17:40:26 UTC+1, Scott Lurndal a écrit :
> David Brown <david.brown@hesbynett.no> writes:
> >On 06/03/17 16:23, supercat@casperkitty.com wrote:
>  [snip]
> >> The ARM is a little weird
> >> because its subroutine-call instruction does not push the return address, but
> >> the return address often does end up getting stacked by the calling function
> >> much as it would if the subroutine-call instruction had saved it.
>  [snip]
> >And no, the ARM is not "weird" about its subroutine calls - the majority
> >of RISC architectures use the same technique as it is more efficient
> >than stacking the return address (after all, most function calls are
> >leaf calls).
> 
> Weird is the PDP-8, which stored the return address in the
> first word of the target codestream :-)

Wasn't that more or less the standard of the time (D. Knuth's MIX was like that IIRC), and a major reason for which recursion was considered strange and costly (you had to use something else than what the processor provided to implement function call).

Yours,

-- 
Jean-Marc

[toc] | [prev] | [next] | [standalone]

#105494

jm.bourguet@gmail.com writes:
>Le lundi 6 mars 2017 17:40:26 UTC+1, Scott Lurndal a =C3=A9crit=C2=A0:
>> David Brown <david.brown@hesbynett.no> writes:
>> >On 06/03/17 16:23, supercat@casperkitty.com wrote:
>>  [snip]
>> >> The ARM is a little weird
>> >> because its subroutine-call instruction does not push the return addre=
>ss, but
>> >> the return address often does end up getting stacked by the calling fu=
>nction
>> >> much as it would if the subroutine-call instruction had saved it.
>>  [snip]
>> >And no, the ARM is not "weird" about its subroutine calls - the majority
>> >of RISC architectures use the same technique as it is more efficient
>> >than stacking the return address (after all, most function calls are
>> >leaf calls).
>>=20
>> Weird is the PDP-8, which stored the return address in the
>> first word of the target codestream :-)
>
>Wasn't that more or less the standard of the time (D. Knuth's MIX was like =
>that IIRC), and a major reason for which recursion was considered strange a=
>nd costly (you had to use something else than what the processor provided t=
>o implement function call).

Some minicomputers of the time were similar to the PDP-8.  The
larger systems (B5500, B2500, 360) used a hardware stack.

[toc] | [prev] | [next] | [standalone]

#105499

scott@slp53.sl.home (Scott Lurndal) writes:

> jm.bourguet@gmail.com writes:
>>Le lundi 6 mars 2017 17:40:26 UTC+1, Scott Lurndal a =C3=A9crit=C2=A0:
>>> David Brown <david.brown@hesbynett.no> writes:
>>> >On 06/03/17 16:23, supercat@casperkitty.com wrote:
>>>  [snip]
>>> >> The ARM is a little weird
>>> >> because its subroutine-call instruction does not push the return addre=
>>ss, but
>>> >> the return address often does end up getting stacked by the calling fu=
>>nction
>>> >> much as it would if the subroutine-call instruction had saved it.
>>>  [snip]
>>> >And no, the ARM is not "weird" about its subroutine calls - the majority
>>> >of RISC architectures use the same technique as it is more efficient
>>> >than stacking the return address (after all, most function calls are
>>> >leaf calls).
>>>=20
>>> Weird is the PDP-8, which stored the return address in the
>>> first word of the target codestream :-)
>>
>>Wasn't that more or less the standard of the time (D. Knuth's MIX was like =
>>that IIRC), and a major reason for which recursion was considered strange a=
>>nd costly (you had to use something else than what the processor provided t=
>>o implement function call).
>
> Some minicomputers of the time were similar to the PDP-8.  The
> larger systems (B5500, B2500, 360) used a hardware stack.

And of course the CDC 6600 was just one step stranger; it actually put a
branch instruction as the first instruction of the subroutine (and
started execution of the subroutine at the second instruction).

[toc] | [prev] | [next] | [standalone]

#105497

On Monday, March 6, 2017 at 11:05:10 AM UTC-6, jm.bo...@gmail.com wrote:
> Le lundi 6 mars 2017 17:40:26 UTC+1, Scott Lurndal a écrit :
> > David Brown <david.brown@hesbynett.no> writes:
> > >On 06/03/17 16:23, supercat@casperkitty.com wrote:
> >  [snip]
> > >> The ARM is a little weird
> > >> because its subroutine-call instruction does not push the return address, but
> > >> the return address often does end up getting stacked by the calling function
> > >> much as it would if the subroutine-call instruction had saved it.
> >  [snip]
> > >And no, the ARM is not "weird" about its subroutine calls - the majority
> > >of RISC architectures use the same technique as it is more efficient
> > >than stacking the return address (after all, most function calls are
> > >leaf calls).
> > 
> > Weird is the PDP-8, which stored the return address in the
> > first word of the target codestream :-)
> 
> Wasn't that more or less the standard of the time (D. Knuth's MIX was like that IIRC), and a major reason for which recursion was considered strange and costly (you had to use something else than what the processor provided to implement function call).
> 

For reference, I have a brief description of function
calls in MIX and pdp-1 here:
http://stackoverflow.com/questions/516688/what-are-the-uses-of-self-modifying-code/7452758#7452758

to save clicks, I reproduce the content here:

1960s-era assembly languages used self-modifying code to implement function 
calls without a stack.

Knuth, v1, 1ed p.182:

    MAX100  STJ   EXIT   ;Subroutine linkage
            ENT3  100    ;M1. Initialize
            JMP   2F
    1H      CMPA  X,3    ;M3. Compare
            JGE   *+3
    2H      ENT2  0,3    ;M4. Change m
            LDA   X,3    ;(New maximum found)
            DEC3  1      ;M5. Decrease k
            J3P   1B     ;M2. All tested?
    EXIT    JMP   *      ;Return to main program

> In a larger program containing this coding as a subroutine, the single 
instruction "JMP MAX100" would cause register A to be set to the current 
maximum value of locations X + 1 through X + 100, and the position of the 
maximum would appear in rI2. Subroutine linkage in this case is achieved by 
the instructions "MAX100 STJ EXIT" and, later, "EXIT JMP *". Because of the 
way the J-register operates, the exit instruction will then jump to the 
location following the place where the original reference to MAX100 was made.

*Edit:* It may be hard to see what's going on, even with the brief explanation 
here. In the line `MAX100 STJ EXIT`, `MAX100` is a label for the instruction 
(and thus for the procedure as a whole), `STJ` means STORE the jump register 
(where we just came *from*), `EXIT` means the memory location labeled 'EXIT' 
is the target of the STORE. `EXIT`, we see later is the label for the last 
instruction. So it's overwriting code! But, many instructions (including `STJ` 
here) implicitly overwrite only the operand portion of the instruction word. 
So the `JMP` remains untouched, and the `*` is a dummy token, since there's 
really nothing meaningful to put there, it'd only get overwritten.

<hr>

Self-modifying code is also used where register-indirect addressing is not 
available, and yet the address you need is sitting right there in the 
register. PDP-1 LISP:

    dap .+1  ;deposit address part of accumulator in (IP+1)
    lac xy   ;load accumulator with (ADDRESS) [xy is a dummy symbol, just like * above]

These two instructions perform `ACC := (ACC)` by modifying the operand of the 
load instruction. 

Modifications like these are relatively safe, and on antique architectures, 
they are *necessary.*

[toc] | [prev] | [next] | [standalone]

#105498

On Monday, March 6, 2017 at 11:59:16 AM UTC-6, luser droog wrote:
> On Monday, March 6, 2017 at 11:05:10 AM UTC-6, jm.bo...@gmail.com wrote:
> > Le lundi 6 mars 2017 17:40:26 UTC+1, Scott Lurndal a écrit :
> > > David Brown <david.brown@hesbynett.no> writes:
> > > >On 06/03/17 16:23, supercat@casperkitty.com wrote:
> > >  [snip]
> > > >> The ARM is a little weird
> > > >> because its subroutine-call instruction does not push the return address, but
> > > >> the return address often does end up getting stacked by the calling function
> > > >> much as it would if the subroutine-call instruction had saved it.
> > >  [snip]
> > > >And no, the ARM is not "weird" about its subroutine calls - the majority
> > > >of RISC architectures use the same technique as it is more efficient
> > > >than stacking the return address (after all, most function calls are
> > > >leaf calls).
> > > 
> > > Weird is the PDP-8, which stored the return address in the
> > > first word of the target codestream :-)
> > 
> > Wasn't that more or less the standard of the time (D. Knuth's MIX was like that IIRC), and a major reason for which recursion was considered strange and costly (you had to use something else than what the processor provided to implement function call).
> > 
> 
> For reference, I have a brief description of function
> calls in MIX and pdp-1 here:
<snip> 
> Self-modifying code is also used where register-indirect addressing is not 
> available, and yet the address you need is sitting right there in the 
> register. PDP-1 LISP:
> 
<snip>
> 
> These two instructions perform `ACC := (ACC)` by modifying the operand of the 
> load instruction. 
> 

Oops. The pdp-1 example was not of function calls. But it does some similar
register gymnastics.

[toc] | [prev] | [next] | [standalone]

#105381

On Sat, 4 Mar 2017 14:40:48 +0300, Alla <vitale.alla@gmail.com> wrote:

>Below is an example a completely incorrect code that doesn't perform any 
>error checking, and used for illustration purpose. This program will 
>"blindly" copy one string into another. If the length of bar exceeds the 
>length of c, then something longer than allocated memory on stack will 
>creep into c's return address space (almost quoting), and worse yet
>(here starts the part I would like your help on) as C language secretly 
>uses stack also to remember when the function is called and what is the 
>address of the previous function called, a "bad guy" can "jump back" to 

Be aware that while this may be a common approach, it is still very
system specific, both hardware and software.  My system does not have
a hardware stack though it does store local variables in a similar
manner.  Return addresses are passed to the called function in a
register, not in memory, and therefore cannot be corrupted this way.
Furthermore, the "stacks" used to store the local variables of
different functions need not be contiguous; it looks more like a
linked list than a typical hardware stack.

Unless you intend to write a compiler (or a piece of malware)  or need
to debug the memory dump produced when a large program fails, the
exact details of how this is done are clutter that serves only to
obscure the important details most new programmers need to absorb.
Curiosity is a virtue but not when it kills the cat.

-- 
Remove del for email

[toc] | [prev] | [next] | [standalone]

#105384

On 3/4/17 20:33, Barry Schwarz wrote:
> On Sat, 4 Mar 2017 14:40:48 +0300, Alla <vitale.alla@gmail.com> wrote:
>
>> Below is an example a completely incorrect code that doesn't perform any
>> error checking, and used for illustration purpose. This program will
>> "blindly" copy one string into another. If the length of bar exceeds the
>> length of c, then something longer than allocated memory on stack will
>> creep into c's return address space (almost quoting), and worse yet
>> (here starts the part I would like your help on) as C language secretly
>> uses stack also to remember when the function is called and what is the
>> address of the previous function called, a "bad guy" can "jump back" to
>
> Be aware that while this may be a common approach, it is still very
> system specific, both hardware and software.  My system does not have
> a hardware stack though it does store local variables in a similar
> manner.  Return addresses are passed to the called function in a
> register, not in memory, and therefore cannot be corrupted this way.
> Furthermore, the "stacks" used to store the local variables of
> different functions need not be contiguous; it looks more like a
> linked list than a typical hardware stack.
>
> Unless you intend to write a compiler (or a piece of malware)  or need
> to debug the memory dump produced when a large program fails, the
> exact details of how this is done are clutter that serves only to
> obscure the important details most new programmers need to absorb.
> Curiosity is a virtue but not when it kills the cat.
>
Yes, we've met the enemy, and it's us )

Thank you! Very interesting: I didn't yet heard about different types of 
systems, such as your one.
I am not trying to dig deeper than I should at this moment. I only 
wanted to understand the basics of this process.

Respectfully,

Alla

[toc] | [prev] | [next] | [standalone]

#105388

Alla <vitale.alla@gmail.com> writes:
> One of the lectures touched upon the following:
>
> Before writing my question, I would like to say that I might have not 
> correctly written down the material, so it might sound incorrect, to say 
> the least; therefore, please, correct what I will write now and help me 
> to understand how it works, maybe with the help of some functions 
> (please, nothing too fancy and complicated). Please, read to the end 
> before answering because it might not be clear what I would like to ask 
> about and thus to understand.
>
> Below is an example a completely incorrect code that doesn't perform any 
> error checking, and used for illustration purpose. This program will 
> "blindly" copy one string into another. If the length of bar exceeds the 
> length of c, then something longer than allocated memory on stack will 
> creep into c's return address space (almost quoting), and worse yet
> (here starts the part I would like your help on) as C language secretly 
> uses stack also to remember when the function is called and what is the 
> address of the previous function called, a "bad guy" can "jump back" to 
> that function using swap() (not in the code below) in the main(), and 
> this swap() not only swaps local variables/arguments, but also make 
> main() return back to the function to execute it; thus a computer 
> blindly assumes that bytes in that "address" part are the address to 
> which it should return. Therefore, these bytes might be some other, 
> rogue address, which the "bad guy" wants the program to go to - sort of 
> tricking the system. And this is done by copying more elements into the 
> c array.
>
> #include <stdio.h>
> #include <string.h>
>
> void f(char *bar)
> {
>     char c[12];
>     strncpy(c, bar, strlen(bar));
> }

The use of strncpy() here is a distraction from the main point.
The whole point of strncpy vs. the simpler strcpy is that you can
tell it how many bytes to copy -- but the number of byte that would
be copied by strcpy() is strlen(bar)+1.  Using sizeof c as the number
of bytes would make some sense.  Using strlen(bar)+1 would make the
call equivalent to the simpler strcpy(c, bar).  Using strlen(bar)
means that the target array will probably not contain a properly
null-terminated string, which is an added complication that has
nothing to do with the issue being demonstrated.

And there are other problems with strncpy, which I've written about
here: http://en.cppreference.com/w/c/language/operator_precedence

> int main (int argc, char **argv)
> {
>     f(argv[1]);
> }

No check that there's actually an argument to copy, another irrelevant
distraction.

> How does this "redirection" happen, and what is actually happening 
> underneath the hood? As I understand it, when the program is compiled, 
> first a memory for
> int main() with its local variables is allocated on the stack; if we 
> assume that a stack is a vertically placed rectangle, then the memory 
> block for the main function will be at the bottom. Next, as main() 
> contains a call to function f(), the memory for f and its local 
> variables is allocated "above" the memory for main(). When the program 
> is executed, once f() is called and finished its job, the memory on 
> stack is "cleared". So how that redirection can happen?

The C standard doesn't even mention a "stack", but the semantics of
function calls are such that they allocate memory in a stack-like
(last-in first-out) manner.  Memory is needed to store local
variables (including parameters) and metadata such as the return
address.  There is no specification of exactly how and where this
storage is allocated.  On some systems, some of this information
might be stored in registers rather than on the "stack" (though
register contents will eventually have to be spilled to memory,
because registers are a scarce resource).

The manner in which this information is stored is typically defined
by the ABI (Application Binary interface) for a given system.

*If* the return address for the call to f() happens to be stored
just after the array object c in memory, then yes, calling f() with
a pointer to a string that's too long to fit in c could overwrite
the return address and cause control to "return" to code of the
attacker's choice.

People who exploit this kind of thing are depending on low-level
details of specific implementations, not on anything specified
by the C standard.  As in any other kind of programming, there's
nothing wrong with depending on system-specific details if you need
to do so; not all code can be portable.

Incidentally, I don't think this kind of exploit is what would
normally be called a "stack overflow".  It overflows the end of the
array object to overwrite other data, but it doesn't go beyond the
top of the stack.  The term "stack overflow" normally refers to a
situation where the attempt to allocate memory for a new function
call fails because not enough memory is available.  This exploit
isn't about running out of available memory.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.c

csiph-web