Suggestions

Last Posts

  • Java: Thread notification

    Greetings. I thought I’d share a technique I like to use to have my threads work together. Here is the plot: you have a pool of working threads that do some heaving lifting operations, time consuming. They are here waiting for the next job to process, (...)

  • Java: full duplex socket communication

    Hello world. Today I’d like to share with you a piece of code to have a full duplex communication between Java Sockets. The idea is to open a ServerSocket on a dedicated port, and then to have several client Sockets to connect to it. The clients will use a (...)

  • The great journey of a little ICMP packet across the wide and dangerous Internet

    In this article we are going to see how an ICMP packet (a "ping") finds its way to reach a machine at the other side of the planet, and come back, all of it in a matter of milliseconds. Our case study We will not study every possible type of network that (...)

  • Tip: Linux immutable files

    Under Linux, using an EXT file system, you can make a file "immutable," meaning that nobody can change it, not even root. Here is how it’s done (as root): sudo chattr +i <file> To revert the operation, you type (as root): sudo chattr -i <file> (...)

  • Buffer Overflows: hacking the stack, again

    Here is another small tutorial where we will dig a little further into what is possible with the stack. Preparation In order for this tutorial to work, please temporarily deactivate the OS protection against Buffer Overflows: $ cat (...)

  • Buffer Overflows, a first approach

    Nearly half of security breaches come from Buffer Overflows. Buffer Overflows take advantage of a flaw in the code that created an application. The code basically allocates some memory but stores more data in it than what has been allocated. The result is (...)

  • Ruby metaprogramming

    To be able to understand this article about ruby metaclasses, you need to have in mind some basics of the Ruby language. Discovering the existence of metaclasses Ruby allows you to define methods on any object: o = Object.new def o.hello "Hello !" end (...)

  • Ruby fundamental concepts

    This post will lay out some important facts about the Ruby language in preparation of another post about Ruby metaprogramming. 1. Methods visibility public : always accessible. private : accessible only for that instance. It is often said that private (...)

  • Add a new hard drive to LVM partition

    Are you reaching the maximum capacity of your LVM partition? It is time to extend! We will see in this article how to add a new hard drive to a LVM partition. So shut your machine down, add the new hard drive, then start the machine again and read on! (...)

  • Ruby and oracle shared libraries

    You may experience the same problem as below if you are using the ruby-oci8 gem to connect to an oracle database: require ’oci8’ $ ruby test.rb /usr/lib/ruby/gems/1.8/gems/ruby-oci8-1.0.6/lib/oci8lib.so: libclntsh.so.10.1: cannot open shared object file: No (...)

  • Shell: cd current directory

    Quick post to share a useful command that I often use in my scripts to make sure that I know where "I am": cd $(readlink -f $(dirname $0)) Explanation: $0 is the first element of the command line invoked = the script itself dirname will give us the (...)

  • Launch a batch script without the command line window

    Hi folks, today we are going to talk a bit about a useful windows scripting trick that allows you to launch a batch script without seeing the extra CMD window popping up. Using a .exe launcher So you already have a batch file. The solution to avoid the (...)

  • Linux: File descriptor limits

    Sometimes a software can be refused the opening of a new resource by the Operating System because it has reached the maximum number of file descriptors used. This is usually cause by a code poorly implemented forgetting to properly close() the resources (...)

  • Redhat ssh auto login

    When you try to setup auto ssh login on a RedHat machine, don’t forget to setup the .ssh/ directory permissions so that only you can write on it : chmod a-w -R ~/.ssh chmod u+w -R ~/.ssh Otherwise the auto login will never (...)

  • Maven java webapp and jetty

    I very often use the jetty-maven-plugin in my Java Webapps. Basically it allows you to be able to run any webapp right after having checked out the project with the simple command: mvn jetty:run-exploded Then go by default on http://localhost:8080/ and (...)

  • CVSNT : read only

    Quick tip to share how to set your CVSNT in a read-only mode. The only thing you have to do is to create an empty file there: $CVSROOT/CVSROOT/writers And that’s it! No writers allowed means that nobody can write anything, job done. Source : CVS NT (...)

  • Creating and Applying Patches

    You sometimes need to use patches to hold some code changes to keep it safe and eventually apply it again later. Using Subversion You can easily create a path file with SVN like this: $ svn diff Index: testfile (...)

  • Max execution time with ruby threads

    This post will describe a way to define a maximum execution time for an operation using threads. Let’s start with a really simple program that takes 5 seconds to run : start=Time.now sleep 5 puts "Script finished in #Time.now-start" Let’s (...)

  • JVM Out Of Memory notification

    This is a quick tip for how to be notified of an OutOfMemory exception from the JVM. This is made possible using the option: -XX:OnOutOfMemoryError option of the JVM. Let’s write a simple program that is going to allocate a lot of memory: public class Oom (...)

  • 12
    29

    Java: Thread notification

    Greetings.

    I thought I’d share a technique I like to use to have my threads work together. Here is the plot: you have a pool of working threads that do some heaving lifting operations, time consuming. They are here waiting for the next job to process, probably monitoring a queue or something. Then you have another set of Threads that is going to take an order for processing, add it to the queue, wait for the processing to be complete and finalize the order. Those "teller" threads are usually lightweight and need little memory/CPU time if any.

    In that scenario the threads will have to coordinate so that the teller Thread can complete the order as soon as the processing is over. That is the focus of this article: how do you "pause" the teller Thread and "resume" it when the processing Thread has finished working?

    There used to be a "suspend" and a "resume" method on the Thread class. There are now deprecated because inherently deadlock-prone. So we’ll use the methods "wait()" and "notify()" of Object to have the same behaviour.

    For our example, we need some kind of Thread that does a time consuming job. Let’s have one that figures out if a number is prime or not, called PrimeNumberThread, offering 2 methods: "enqueue" to add a number to the processing queue; and "dequeue" that fetches the result.

    The Teller Thread

    The idea is to have each incoming request served by a "teller" thread. Let’s call it SchedulerThread. It deals with the comunication with the customer: it takes the order (the number to process), schedules it for processing, waits for the processing to complete and then gets back to the customer with the response. There will be as many SchedulerThreads as there are "requests" (in our case there is no limitation, in real life you need a max).

    public class SchedulerThread extends Thread {
     static Integer counter = 1;

     long num;

     public SchedulerThread(long num) {
       this.num = num;
     }

     public void run() {
       PrimeNumberThread.enqueue(num, this);
       try {
         // wait for somebody to notify this thread
         synchronized (this) {
           wait();
         }
       } catch (InterruptedException e) {
         e.printStackTrace();
         return;
       }
       synchronized (counter) {
         System.out.println((counter++) + "- " + num + " is "
             + (PrimeNumberThread.dequeue(num) ? "" : "not ") + "prime.");
       }
     }
    }

    To request the processing of a number N, all you have to do is:

    new SchedulerThread(N).start();

    This will add N to the processing queue and then call wait(). From the Javadoc: "wait() causes the current thread to wait until another thread invokes the notify() method or the notifyAll() method for this object.". This is the key. Once the number is processed, we need the PrimeNumberThread to invoke notify() on the SchedulerThread object, so that it can resume and complete the request. For that reason we need to provide the thread object itself along with the number to enqueue.

    The Processing Thread

    We need a processing Queue. It has to be a static Queue because it will be shared by all the PrimeNumberThreads. Note that any usage of this Queue will have to be synchronized.

    We will also use a Map to store the result and another Map to hold the teller Thread. But let’s see the code first, and then dive more into the details:

    public class PrimeNumberThread extends Thread {

     // the numbers queue awaiting processing
     static List<Long> numbers = new ArrayList<Long>();

     // a map that stores the results
     static Map<Long, Boolean> results = new HashMap<Long, Boolean>();

     // a map that holds the thread that are waiting
     static Map<Long, Thread> waitObjects = new HashMap<Long, Thread>();

     @Override
     public void run() {
       try {
         while (true) {
           boolean empty = false;
           Long num = null;
           synchronized (numbers) {
             if (numbers.isEmpty()) {
               empty = true;
             } else {
               num = numbers.remove(0);
             }
           }
           if (empty) {
             // if empty, just wait and retry
             Thread.sleep(50);
           } else {

             // most of the COU is spent here:
             boolean prime = isPrime(num);

             // stores the result
             synchronized (results) {
               results.put(num, prime);
             }
             // notify end of processing
             synchronized (waitObjects) {
               Thread waitObject = waitObjects.remove(num);
               synchronized (waitObject) {
                 waitObject.notify();
               }
             }
           }
         }
       } catch (InterruptedException e) {
         e.printStackTrace();
       }
     }

     public static void enqueue(long num, Thread waitObject) {
       synchronized (waitObjects) {
         waitObjects.put(num, waitObject);
       }
       synchronized (numbers) {
         numbers.add(num);
       }
     }

     public static boolean dequeue(long num) {
       synchronized (results) {
         return results.remove(num);
       }
     }

     // inefficient code to find prime numbers
     public static boolean isPrime(long num) {
       boolean prime = true;
       long limit = (long) Math.sqrt(num);
       for (long i = 2; i <= limit; i++) {
         if (num % i == 0) {
           prime = false;
           break;
         }
       }
       return prime;
     }
    }

    So we have a isPrime(long) method that does the heavy work, an enqueue and a dequeue method that allow to add a new number to process and to retrieve the result. Most of the complexity here is to keep the Collections synchronized. The "run" method does the actual job to get the next number to process (if any), process it, update the results Map and notify the SchedulerThread stored in the waitObjects Map.

    In action

    Here is the code to process 100 primes numbers (randomly generated) with 8 processing threads:

    public static void main(String[] args) {
     int nbPrimeThreads = 8; // set to number of cores
     int nbNumbersToAnalyze = 100;

     // starts the processing threads
     for (int i = 0; i < nbPrimeThreads; i++) {
       new PrimeNumberThread().start();
     }

     // generate numbers
     Random r = new Random();
     long[] numbers = new long[nbNumbersToAnalyze];
     for (int i = 0; i < nbNumbersToAnalyze; i++) {
       numbers[i] = (long) (r.nextDouble() * (Long.MAX_VALUE - 1)) + 1;
     }
     
     // schedule all the numbers!
     for (long num : numbers) {
       new SchedulerThread(num).start();
     }
    }

    The point of using a pool of processing threads is to keep control of how much of your resources are used. Here most of the processing is heavy on the CPU so it is a good idea to keep the number of processing threads equal to you number of available cores of you CPU.

    The output:

    1- 372281293763079169 is not prime.
    10- 1106522284603503617 is not prime.
    11- 4505642750654164993 is not prime.
    12- 6295184702160283649 is not prime.
    16- 3690429631313886209 is not prime.
    17- 6637291068156567553 is not prime.
    18- 2976140522999570433 is not prime.
    (...)
    93- 7951101352683392001 is not prime.
    94- 7446226462970158081 is not prime.
    95- 6810305470554089473 is not prime.
    96- 314272017611928577 is prime.
    97- 3531645579569108993 is prime.
    98- 6201886719324952577 is prime.
    99- 6564108545411756033 is prime.
    100- 8033214365761463297 is prime.

    Note that as it often the case when working with thread, your output is not ordered. Also note that you will be likely to see your prime numbers at the end because it takes much more time to figure out that they are actually prime numbers.

    Peace.

    Author: Benjamin Jaton

  • 12
    21

    Java: full duplex socket communication

    Hello world.

    Today I’d like to share with you a piece of code to have a full duplex communication between Java Sockets. The idea is to open a ServerSocket on a dedicated port, and then to have several client Sockets to connect to it. The clients will use a dynamically assigned port number to send messages to the server, but also to receive some from the server. The attractive feature of this architecture is to only have to use/reserve 1 designated port for the server.

    The "Agent" class

    The Agent class below holds the reader and the writer for a connection. The run() method will keep listening to the reader and simply print whatever it receives. A send(String) method allows to use the writer to send a message through the connection.

    public class Agent extends Thread {
      public String name;
      public PrintWriter writer;
      public BufferedReader reader;

      public void connect(int serverPort) throws Exception {
         Socket socket = new Socket(InetAddress.getLocalHost(), serverPort);
         writer = new PrintWriter(socket.getOutputStream(), true);
         reader = new BufferedReader(new InputStreamReader(
               socket.getInputStream()));
      }

      @Override
      public void run() {
         try {
            startAgent();
         } catch (Exception e) {
            e.printStackTrace();
         }
      }

      private void startAgent() throws Exception {
         try {
            while (true) {
               System.out.println(name + " received: " + reader.readLine());
            }
         } finally {
            writer.close();
            reader.close();
         }
      }

      public void send(String msg) {
         writer.println(msg);
      }
    }

    The Client

    The client is an Agent that can connect to a ServerSocket. For simplicity, I’ll just add a connect(int) method to the Agent class instead of extending it:

    public class Agent extends Thread {
      public String name;
      public PrintWriter writer;
      public BufferedReader reader;

      @Override
      public void run() {
         try {
            startAgent();
         } catch (Exception e) {
            e.printStackTrace();
         }
      }

      private void startAgent() throws Exception {
         try {
            while (true) {
               System.out.println(name + " received: " + reader.readLine());
            }
         } finally {
            writer.close();
            reader.close();
         }
      }

      public void send(String msg) {
         writer.println(msg);
      }

      public void connect(int serverPort) throws Exception {
         Socket socket = new Socket(InetAddress.getLocalHost(), serverPort);
         writer = new PrintWriter(socket.getOutputStream(), true);
         reader = new BufferedReader(new InputStreamReader(
               socket.getInputStream()));
      }
    }

    The Server

    The Server is also going to be a Thread that opens a port to listen for incoming connections. For each of those new connections a new "Agent" will be created to handle the communication server side.

    Each Agent created is saved into a List that will be used by the sendAll() method to send a message to each client.

    public class Server extends Thread {
      public int port;
      ServerSocket serverSocket;

      public Server(int port) {
         this.port = port;
      }

      @Override
      public void run() {
         try {
            startServer();
         } catch (Exception e) {
            e.printStackTrace();
         }
      }

      private void startServer() throws Exception {
         try {
            serverSocket = new ServerSocket(port, 0, InetAddress.getLocalHost());
            while (true) {
               createServerAgent(serverSocket);
            }
         } finally {
            if (serverSocket != null) {
               serverSocket.close();
            }
         }
      }

      List<Agent> agents = new ArrayList<Agent>();

      private void createServerAgent(ServerSocket serverSocket)
            throws IOException {
         Socket clientSocket = serverSocket.accept();
         System.out.println("Server: received connection from port "
               + clientSocket.getPort());

         Agent agent = new Agent();
         agent.name = "Server agent (for client port " + clientSocket.getPort()
               + ")";
         agent.writer = new PrintWriter(clientSocket.getOutputStream(), true);
         agent.reader = new BufferedReader(new InputStreamReader(
               clientSocket.getInputStream()));
         agent.start();
         synchronized (agents) {
            agents.add(agent);
         }
      }

      private void sendAll(String msg) {
         synchronized (agents) {
            for (Agent agent : agents) {
               agent.send(msg);
            }
         }
      }
    }

    The main

    Now let’s use all our new toys and write a simple program that will: create the Server, start it, create 2 clients, start them, and begin to play:

    public static void main(String[] args) throws Exception {
         Server server = new Server(1234);
         server.start();

         // client 1
         Agent client1 = new Agent();
         client1.name = "Client1";

         client1.connect(1234);
         client1.start();
         client1.send("Hello server!");

         // client 2
         Agent client2 = new Agent();
         client2.name = "Client2";

         client2.connect(1234);
         client2.start();
         client2.send("Hi boss!");

         Thread.sleep(100);
         server.sendAll("Welcome my minions.");
         Thread.sleep(100);
         System.exit(0);
    }

    Both of the clients say hello to the server, and the server welcome them back:

    Server: received connection from port 58974
    Server agent (for client port 58974) received: Hello server!
    Server: received connection from port 58975
    Server agent (for client port 58975) received: Hi boss!
    Client1 received: Welcome my minions.
    Client2 received: Welcome my minions.

    As long as the clients are running, the ports 58974 and 58975 will be used by them. They have been assigned dynamically these ports by the Operating System from a dynamic (or "private") range. This means that your clients’ ports are unlikely to be the same every time that you run the program.

    About those Ephemeral ports, Wikipedia states:

    The Internet Assigned Numbers Authority (IANA) suggests the range 49152 to 65535 for dynamic or private ports.

    This method is great to reduce the amount of dedicated port your application is using. You can imagine have a single Server as a hub to forward messages to another client. You can build you communication protocol upon this kind of architecture.

    Author: Benjamin Jaton

  • 12
    7

    The great journey of a little ICMP packet across the wide and dangerous Internet

    In this article we are going to see how an ICMP packet (a "ping") finds its way to reach a machine at the other side of the planet, and come back, all of it in a matter of milliseconds.

    Our case study

    We will not study every possible type of network that exists in the immensity of the Internet. This is only an example. We will focus on a specific case where a computer is directly connected to an ISP router with an Ethernet cable.

    Genesis of an ICMP packet

    The user types in a ping command in a terminal:

    $ ping google.com

    And then he hits [Enter]...

    From that very basic command, the amount of technology that will be involved to actually have an ICMP packet reach one of the servers at google and come back is significant. This most simple command will use numerous protocols and hundreds of pieces of equipment accross the world.

    - Name resolution

    The very first step is to translate the destination domain name «google.com» into an IP address. This is the job of a Domain Name Server. A machine connected to a network usually has a file that contains the IP addresses of some Domain Name Servers to use (see /etc/resolv.conf under Debian). This file is updated by the DHCP protocol when the machine starts. When the Operating System wants to resolve google.com, it will first query the DNS to get the corresponding IP address. Note that your DNSs are usually the ones provided by your ISP which keeps this information for a few hours before synchronizing against the Root Name Servers.

    - Building an ICMP packet

    When you ping a remote host, you use the ICMP protocol which is part of the IP protocol. The kernel of the machine creates this "layer 3" (network) ICMP packet and sets the destination to the IP address resolved above for "google.com". Then, the ICMP packet is forwarded to the network card (the interface) that matches the proper route to reach the remote host. You can access this interfaces-routes mapping under Debian with:

    $ route -n
    Kernel IP routing table
    Destination     Gateway         Genmask         Flags Metric Ref    Use Iface
    192.168.1.0       0.0.0.0         255.255.255.0   U     1      0        0 eth0
    0.0.0.0         192.168.1.1    0.0.0.0         UG    0      0        0 eth0

    The Destination "0.0.0.0" means "everything else." In the example above, the first route is only to be used when trying to reach local machines (192.168.1.xxx). We will use the second one: interface "eth0" and gateway "192.168.1.1".

    - Building an Ethernet packet

    The IP packet to send will be encapsulated by the network card into an Ethernet frame (layer 2, data link). In order to do that, the card uses its ARP cache to fetch the Ethernet address for the gateway to use (see above routes). In our case, we are looking for the Ethernet address for 192.168.0.1. If this address is not found in the ARP cache, the network card will broadcast ARP requests asking everybody (within the same level 2 network): "Who has 192.168.0.1?" and update the cache according to the replies. Once the card finds the Ethernet address, the Ethernet frame is built and ready to be sent.

    To see the ARP cache under Debian:

    $ sudo arp -n
    Address                  HWtype  HWaddress           Flags Mask            Iface
    192.168.0.1              ether   00:14:25:E1:D3:E5   C                     eth0

    - Sending the Ethernet packet

    The network then sends the Ethernet frame in the form of electrical impulses onto the physical media: the Ethernet cable (layer 1, physical).

    protocol layer
    ICMP (IP) 3, network
    Ethernet 2, data link

    Local Router

    The frame now reaches one of the network card of our router (at the other end of the Ethernet cable). Seeing that this frame matches its Ethernet address, the router network card de-encapsulates the IP packet and pass it to the kernel (layer 3, network). The ketrnel sees that this packet doesn’t match any of the router’s IP addresses so it must be routed. In order to to that, the kernel will read its own IP routing table et then forwards the ICMP packet, now encapsulated into a new layer 2 protocol: the ATM protocol. The ATM is very often used to carry the data from a customer to the ISP network (even if declining to be replaced by "All IP").

    However, for obvious security reasons, note that the communication between the router and the ISP network is secured, often with a Point-to-Point Protocol connection (often PPPoA for PPP over ATM). It authenticates the customer (with login/password) and allows the communication to be encrypted.

    At this point we have:

    protocol layer
    ICMP(IP) 3, network
    PPP "2,5"
    ATM 2, data link

    ATM (Asynchronous Transfer Mode) is the protocol used to connect the customers to the ISP network. The router is going to create small ATM "cells" (only 53 bytes to reduce the latency, or "jitter") and convert them into electrical signals to use the higher frequencies (called "channels") available on the phone line. ADSL uses the unused frequencies of the human voice to communicate data.

    The final signal (voice + data) is sent through the output interface of the router towards the ISP network through the phone line.

    The DSLAM

    So this electrical signal travels using ATM to the DSLAM (Digital Subscriber Line Access Multiplexer). It may come accross one or several "repeaters" which is a layer 1 network piece of equipment that keeps the signal strong and clear.

    The DSLAM is a piece of equipment that aggregates the "low speed" streams from customers. First, each signal is demodulated to extract the data signal from the voice signal. The voice signal is sent to the Public Switched Telephone Network (PSTN). All the data signals will be regrouped into a bigger one in a process called Multiplexing.

    The BRAS

    This big multiplexed ATM data stream is carried over Optical Fiber to arrive to a BRAS (BroadBand Remote Access Server) which is going to aggregate ATM streams from about a dozen of DSLAM into one again!

    The BRAS will send the aggregated ATM frames through the ISP’s VPN by encapsulating them in a L2TP tunnel that ends at the LNS (L2TP Network Server) of the ISP.

    L2TP uses the UDP protocol (port 1701) to carry the PPP sessions:

    protocol layer
    ICMP(IP) 3, netword
    PPP "2,5"
    ATM 2, data link
    UDP 4, transport
    IP 3, network
    ATM 2, data link

    The stream will travel through the L2TP VPN to the core of the ISP network.

    The Internet Backbone

    The ATM stream is traveling through multiple layer 2 ATM switches to reach the LNS. From there, the IP stream is extracted from the PPP session and routed through the ISP backbone. If the recipent of the IP packet doesn’t belong to the same ISP as the source, then the ISP will have to figure out which ISP has to be reached and how to reach it. Those high level routing operations are achieved using the Border Gateway Protocol which is the way Autonomous Systems (big network entities like your ISP) communicate the IP ranges they serve to each other as well as information used for figuring out the quickest way to get there.

    So, after going through one or several Autonomous Systems using very high speed pieces of equipment commonly refered as the Internet Backbone (see image below), the ICMP packet reaches the target Autonomous System for Google (who probably is its own Autonomous System).

    I can’t really speak to Google’s internal network architecture but it is safe to assume that they use a similar method to transport their data as what I have just described. No matter what, one of the Google servers will receive that little ICMP packet, then craft an ICMP reply packet to original user. It will probably not follow the exact same path but close.

    All that, in a matter of a few milliseconds. Isn’t it incredible?

    References

    - The OSI model.

    Note that you can have an idea, even if it’s not perfect, of the level 3 equipment involved in this transmission by using the ’traceroute’ command under Debian.

    Author: Benjamin Jaton

  • 12
    26

    Tip: Linux immutable files

    Under Linux, using an EXT file system, you can make a file "immutable," meaning that nobody can change it, not even root.

    Here is how it’s done (as root):

    sudo chattr +i <file>

    To revert the operation, you type (as root):

    sudo chattr -i <file>

    It came in handy in my case when I wanted to "lock" my resolv.conf file that I prepared manually. Somehow my networking tool kept modifying it with wrong DNSs.

    Hope this helps!

    References

    See the Wikipedia article about Chattr for more details about the attributes available.

    Author: Benjamin Jaton

  • 12
    23

    Buffer Overflows: hacking the stack, again

    Here is another small tutorial where we will dig a little further into what is possible with the stack.

    Preparation

    In order for this tutorial to work, please temporarily deactivate the OS protection against Buffer Overflows:

    $ cat /proc/sys/kernel/randomize_va_space
    2
    $ echo 0 > /proc/sys/kernel/randomize_va_space

    The compiler options used in this tutorial will be "-ggdb -fno-stack-protector -m32", please refer to the first article about Buffer Overflows for more details.

    Goal

    Consider this piece of code:

    /* buf.c */
    #include <stdio.h>

    void t() {
    }

    int main(){
     int x;
     x = 0;
     t();
     x = 1;
     printf("%d\n",x);
    }

    As is, the program simply displays ’1’:

    $ gcc buf.c -ggdb -fno-stack-protector -m32 -o buf && ./buf
    1

    The objective for today is to write some code in t() that will ignore the instruction "x=1;". If we succeed, the program will display ’0’ instead of ’1’. This is clearly an exercise to play with the stack, registers and C pointer. Yes, I know, this is fun.

    Assembly and procedure calls

    Let’s examine the program below, where t() only declares a 1 byte array:

    /* test.c */
    #include <stdio.h>

    void t() {
     char * buffer[1];
    }

    int main(){
     t();
    }

    We compile it:

    $ gcc test.c -ggdb -fno-stack-protector -m32 -o test

    Now let’s use GDB to disassemble the main() function:

    $ gdb test
    GNU gdb (GDB) 7.2-ubuntu
    Copyright (C) 2010 Free Software Foundation, Inc.
    License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
    This is free software: you are free to change and redistribute it.
    There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
    and "show warranty" for details.
    This GDB was configured as "x86_64-linux-gnu".
    For bug reporting instructions, please see:
    <http://www.gnu.org/software/gdb/bugs/>...
    Reading symbols from /home/benji/buf/test...done.
    (gdb) disas main
    Dump of assembler code for function main:
      0x0804839c <+0>:        push   %ebp
      0x0804839d <+1>:        mov    %esp,%ebp
      0x0804839f <+3>:        call   0x8048394 <t>
      0x080483a4 <+8>:        pop    %ebp
      0x080483a5 <+9>:        ret    
    End of assembler dump.

    For now, just note the call to the procedure "call 0x8048394 <t>".

    CALL & RET

    The CALL instruction:
    - pushes the return address onto the stack ( push 0x080483a4 ),
    - decreases the ESP register by 4 bytes ( sub $0x4,%esp ) to take into account the previous change in size of the stack (the ESP register must always point to the top of the stack),
    - copies the address of the procedure in the EIP register to actually process it.

    The RET instruction:
    - pops the last value from the stack and puts it into EIP (0x08048392)
    - increases ESP by 0x4

    Assembly and procedures

    Let’s now disassemble t():

    (gdb) disas t
    Dump of assembler code for function t:
      0x08048394 <+0>:        push   %ebp
      0x08048395 <+1>:        mov    %esp,%ebp
      0x08048397 <+3>:        sub    $0x10,%esp
      0x0804839a <+6>:        leave  
      0x0804839b <+7>:        ret    
    End of assembler dump.

    First there is the "function prologue" of t():

    0x08048394 <+0>:        push   %ebp
    0x08048395 <+1>:        mov    %esp,%ebp
    0x08048397 <+3>:        sub    $0x10,%esp

    And then there is the "function epilogue":

    0x0804839a <+6>:        leave  
    0x0804839b <+7>:        ret  

    The prologue:
    - saves (pushes) the old EBP (pointer to the beginning of the stack, in the context of the current procedure)
    - resets EBP to the old ESP (pointer to the top of the stack)
    - moves ESP to allocate the memory needed for the variables of the C function (here: "buffer").

    The epilogue:
    - restores the values of the stack pointers: the LEAVE instruction resets ESP to EBP ( mov %ebp, %esp ) and pops the old EBP ( pop %ebp )
    - executes the instruction following the call of the procedure. (RET)

    Note that 0x10 units of memory (16 bytes) are allocated for the variable "char * buffer[1]" which only needs 4. For some reason, allocations are made in sets of 16 bytes, some of which is left unused:

    <— top of the pile
    12 bytes 4 bytes (buffer)

    State of the stack

    The key to this tutorial is right here. We are going to summarize the previous steps and predict the state of the stack just before the epilogue of t().

    - main+17: call 0x8048374 t The CALL instruction pushes the return address 0x08048392.

    - t+0: push %ebp The old EBP is pushed.

    - t+3: sub $0x10,%esp Here we allocate 16 bytes: 12 will be unused, 4 will be our local variable "buffer."

    <— top of the stack
    12 bytes 4 bytes 4 bytes 4 bytes
    ESP buffer old EBP RET ( 0x0804837a )

    The trick will be to directly change the return address of the procedure as C allows us to do so:

    - buffer + 1 = old EBP pushed
    - buffer + 2 = return address of the procedure

    Let’s go back to the initial program (buf.c) and disassemble it:

    (gdb) disas main
    Dump of assembler code for function main:
      0x080483df <+0>:        push   %ebp
      0x080483e0 <+1>:        mov    %esp,%ebp
      0x080483e2 <+3>:        and    $0xfffffff0,%esp
      0x080483e5 <+6>:        sub    $0x20,%esp
      0x080483e8 <+9>:        movl   $0x0,0x1c(%esp)
      0x080483f0 <+17>:        call   0x80483c4 <t>
      0x080483f5 <+22>:        movl   $0x1,0x1c(%esp)
      0x080483fd <+30>:        mov    $0x80484e0,%eax
      0x08048402 <+35>:        mov    0x1c(%esp),%edx
      0x08048406 <+39>:        mov    %edx,0x4(%esp)
      0x0804840a <+43>:        mov    %eax,(%esp)
      0x0804840d <+46>:        call   0x80482f4 <printf@plt>
      0x08048412 <+51>:        leave  
      0x08048413 <+52>:        ret    
    End of assembler dump.

    The goal here is to ignore "main+22: movl $0x1,0x1c(%esp)" which is the line "x=1;". In order to do that, the return address of the procedure will have to be modified from 0x080483f5 to 0x080483fd = +0x8.

    So we are going to increase by 8 the value of the pointer (buffer+2) :

    /* buf.c */
    #include <stdio.h>

    void t() {
     char * buffer[1];
     (*(buffer+2))+=8;
    }

    int main(){
     int x;
     x = 0;
     t();
     x = 1;
     printf("%d\n",x);
    }

    Let’s try it:

    $ gcc buf.c -ggdb -fno-stack-protector -m32 -o buf && ./buf
    0

    Boom, take that, x!

    Before you forget

    Protect yourself:

    $ echo 2 > /proc/sys/kernel/randomize_va_space

    References

    Smashing the stack for fun and profit, the legendary article about Buffer Overflows.

    Author: Benjamin Jaton

enfants soldats