nyte's New Writeups

frame pointer (thing)

2008-10-12T03:18:58Z

The frame pointer is a register which holds the address of the bottom of the stack frame. In the x86 ISA, this register is known as ebp. The 'b' here stands for 'base', because the frame pointer is also known as the base pointer. In the Linux/x86 ABI, the frame pointer points to the bottom-most byte of the saved frame pointer of the previous stack frame. Conceptually, imagine foo() has called bar() (keep in mind that the stack grows downwards):

     |           ...             |
     |    rest of the stack      |
     |           ...             |
100: |    saved frame pointer    |
104: |    foo()'s stack frame    |
     |           ...             |
132: | return address from bar() |
136: |  100 [saved fp for foo()] | <-- bar()'s frame pointer points here
140: |    bar()'s stack frame    |
     |           ...             |

The frame pointer is useful because unlike the…

return-to-libc attack (idea)

2008-10-11T05:21:17Z

The buffer overflow attack has long been one of the most common vulnerabilities exploited to gain access to or control of a system. The standard form, explained very well in destrius' writeup at that node (read it first), has the attacker submit as input a string consisting of machine code at the beginning and the address at which the machine code is stored at the end, such that this address overwrites the return address stored at the top of the stack frame; this way, when the function returns, it actually jumps to the beginning of the buffer, executing the (arbitrary) machine code that the attacker placed there. Usually this is code to execute a shell. Pictorially, where each line represents four bytes, and the function declares char buffer[6] somewhere:

pre attack:                                    post attack:
|  argument 2      |                           |  argument 2      |
|  argument 1

…

C++: computing Fibonacci numbers at compile time (idea)

2008-09-16T13:50:48Z

First, a version of the code that will compile on a modern g++:

#include <iostream>
template<int N> struct fib {
  static const int result = fib<N-1>::result + fib<N-2>::result;
};

template<> struct fib<0> {
  static const int result = 0;
};

template<> struct fib<1> {
  static const int result = 1;
};

int main(int ac, char *av[])
{
  std::cout << "Fib(10) = " << fib<10>::result << std::endl;
  return 0;
}

It might be worth exploring why exactly the above program is linear in compile time rather than exponential. After all, if the computation is being done at compile time, and the run-time of the algorithm is expected to be exponential, then compiling the program should be exponential, right? Let's take a look.

First, let's consider what fib(n) depends on, in this algorithm. Obviously, fib(10) (to continue with the…

Balmoral (thing)

2008-08-09T14:10:49Z

The word Balmoral ("Bal"), in shoe terminology, refers the way certain shoes tie up, also known as closed lacing. Picture a shoe (please note that we are specifically talking about dress shoes here) with the toe up. Now superimpose a capital "T" on top, with the vertical part of the T at the opening between the eyelets. In a Balmoral shoe, the horizontal part of the T is where the flaps for the eyelets (the "quarters") would be sewn down, with the vamp on top. When properly tied, only the tip of the tongue can be seen on a Balmoral. This is as opposed to a Blucher shoe, which has open lacing, wherein the quarters are not sewn down at the top at all, and can flap open. Because of the way a Bal is sewn, the part of the shoe around the ball of the foot can only be one circumference and is not adjustable; therefore, people with narrow or wide foot can find it more…

Nesting Models in Software Transactional Memory (idea)

2007-09-14T22:58:19Z

Background

The current dominant paradigm in synchronizing multi-threaded programs is lock-based. One associates a lock with a piece of data, and by convention, any thread that wishes to read or modify this data must acquire this lock. The lock provides the guarantee of mutual exclusion: only one thread may have acquired the lock at any point in time. All other threads that wish to do so must wait. Lock-based parallel programming comes with a number of problems, some of which have been explored elsewhere. With chip designers, for the time being, having given up on increased clock speed and opted instead for increased parallelism, it has become increasingly important to find a better paradigm for concurrent programming.

Software Transactional Memory (STM) is one such alternative…

Lock-freedom and Obstruction-freedom in Software Transactional Memory (idea)

2007-09-09T17:28:07Z

Background

Dealing effectively with multi-threaded programming is a hot topic these days. Clock speeds have more or less plateaued, but the number of threads on a chip (and the number of chips in a machine) is going up. Locks are hard and prone to bugs. Software transactional memory is one possible alternative, and one that is popular in the research community. The basic idiom of STM is to throw away the locking paradigm entirely, and to replace it with merely declaring a certain section of code atomic. The run-time system (1), be it the virtual machine in a managed language such as Java, or merely a library (2) in the case of a language such as C++ then guarantees that the actions performed within that section of code are isolated from the rest of the program, and any updates to shared memory appear, to the rest of the program, to either happen…