Loop Detection - Chapter 3 Algorithms Used to Detect Loops

Loop Detection

Peter Silberman

peter.silberman@gmail.com

Chapter 3

Algorithms Used to Detect Loops

 

A lot of research has been done on the subject of loop detection. The research, however, was not done for the purpose of finding and exploiting vulnerabilities that exist inside of loops. Most research has been done with an interest in recognizing and optimizing loops (A good article about loop optimization and compiler optimization is http://www.cs.princeton.edu/courses/archive/spring03/cs320/notes/loops.pdf.

Research on the optimization of loops has led scientists to classify various types of loops. There are two distinct categories to which any loop will belong. Either the loop will be an irreducible loop (Irreducible loops are defined as ”loops with multiple entry [points]” (http://portal.acm.org/citation.cfm?id=236114.236115) or a reducible loop (3Reducible loops are defined as ”loops with one entry [point]” (http://portal.acm.org/citation.cfm?id=236114.236115). Given that there are two different distinct categories, it stands to reason that the two types of loops are detected in different fashions. Two popular papers on loop detection are Interval Finding Algorithm[1] and Identifying Loops Using DJ Graphs[2]. This document will cover the most widely accepted theory on loop detection.

3.1 Natural Loop Detection

One of the most well known algorithms for loop detection is demonstrated in the book Compilers Principles, Techniques, and Tools by Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman. In this algorithm, the authors use a technique that consists of two components to find natural loops (A natural loop ”Has a single entry point. The header dominates all nodes in the loop.” (http://www-2.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15745-s03/public/lectures/L7 handouts.pdf all loops are not natural loops).

The first component of natural loop detection is to build a dominator tree out of the control flow graph (CFG). A dominator can be found when all paths to a given node have to go through another node. A control flow graph is essentially a map of code execution with directional information. The algorithm in the

book calls for the finding of all the dominators in a CFG. Let’s look at the actual algorithm.

Starting from the entry node, the algorithm needs to check if there is a path to the slave from the entry node. This path has to avoid the master node.

If it is possible to get to the slave node without touching the master node, it can be determined that the master node does not dominate the slave node.

If it is not possible to get to the slave node, it is determined that the master node does dominate the slave. To implement this routine the user would call the is path to(ea t from, ea t to, ea t avoid) function included in loop detection.cpp. This function will essentially check to see if there is a path from the parameter from that can get to the parameter to, and will avoid the node specified in avoid.

As the reader can see from Figure 1, there is a loop in this CFG. Let B to C to D be the path of nodes that create a loop, it will be represented as B->C->D. There is also another loop from nodes B->D. Using the algorithm described above it is possible to verify which of these nodes is involved in the natural loop. The first question to ask is if the flow of the program can get from A to D while avoidingB. As the reader can see, it is impossible in this case to get to D avoiding B.

As such, a call to the is path to function will tell the user that B Dominates D. This can be represented as B Dom D, and B Dom C. This is due to the fact that there is no way to reach C or D without going through B. One question that might be asked is how exactly does this demonstrate a loop? The answer is that, in fact, it doesn’t. The second component of the natural loop detection checks to see if there is a link, or backedge, from D to B that would allow the flow of the program to return to node B to complete the loop. In the case of B->D there exists a backedge that does complete the loop.

3.2 Problems with Natural Loop Detection

There is a very big problem with natural loops. The problem is with the natural loop definition which is “a single entry point whose header dominates all the nodes in the loop”. Natural loop detection does not deal with irreducible loops, as defined previously.

As the reader can see both B and D are entry points into C. Also neither D nor B dominates C. This throws a huge wrench into the algorithm and makes it only able to pick up loops that fall under the specification of a natural loop or reducible loop (5It is important to note that it is next that it is next to impossible to reproduce ??F:fig2) without using nested for loops and goto’s statements. For this reason it is rare that the reader will see an example of this in a binary. However, it is possible therefore the author thought it important to mention).

Loop Detection - Chapter 1 & 2

Loop Detection

Peter Silberman

peter.silberman@gmail.com

 

Chapter 1

Foreword

Abstract: During the course of this paper the reader will gain new knowledge about previous and new research on the subject of loop detection. The topic of loop detection will be applied to the field of binary analysis and a case study will given to illustrate its uses. All of the implementations provided in this document have been written in C/C++ using Interactive Disassembler (IDA) plug-ins.

Thanks: The author would like to thank Pedram Amini, thief, Halvar Flake, skape, trew, Johnny Cache and everyone else at nologin who help with ideas, and kept those creative juices flowing.

Chapter 2

Introduction

The goal of this paper is to educate the reader both about why loop detection is important and how it can be used. When a security researcher thinks of insecure coding practices, things like calls to strcpy and sprintf are some of the first things to come to mind. These function calls are considered low hanging fruit. Some security researchers think of integer overflows or off-by-one copy errors as types of vulnerabilities. However, not many people consider, or think to consider, the mis-usage of loops as a security problem. With that said, loops have been around since the beginning of time (e.g. first coding languages). The need for a language to iterate over data to analyze each object or character has always been there. Still, not everyone thinks to look at a loop for security problems.

What if a loop doesn’t terminate correctly? Depending on the operation the loop is performing, it’s possible that it could corrupt surrounding memory regions if not properly managed. If the loop frees memory that no longer exists or is not memory, a double-free bug could’ve been found. These are all things that could, and do, happen in a loop.

As the low hanging fruit is eliminated in software by security researchers and companies doing decent to moderate QA testing, the security researchers have to look elsewhere to find vulnerabilities in software. One area that has only been touched on briefly in the public relm, is how loops operate when translated to binaries (BugScan is an example of a company that has implemented ”buffer iteration” detection but hasn’t talked publically about it. http://www.logiclibrary.com). The reader may ask: why would one want to look at loops? Well, a lot of companies implement their own custom string routines, like strcpy and strcat, which tend to be just as dangerous as the standard string routines.

These functions tend to go un-analyzed because there is no quick way to say that they are copying a buffer. Due to this reason, loop detection can help the security research identify areas of interest. During the course of this article the reader will learn of the different ways to detect loops using graph analysis, how to implement loop detection, see a new loop detection IDA plug-in, and a case study that will tie it all together

Mac OS X PPC Shellcode Tricks - Chapter 4 Avoiding NULLs

Mac OS X PPC Shellcode Tricks

H D Moore

hdm@metasploit.com

Chapter 4

Avoiding NULLs

One of the most common problems encountered with shellcode development in general and RISC processors in particular is avoiding NULL bytes in the assembled code. On the IA32 platform, NULL bytes are fairly easy to dodge, mostly due to the variable-length instruction set and multiple opcodes available

for a given task. Fixed-width opcode architectures, like PowerPC, have fixed field sizes and often pad those fields with all zero bits. Instructions that have a set of undefined bits often set these bits to zero as well. The result is that a many of the available opcodes are impossible to use with NULL-free shellcode

without modification.

On many platforms, self-modifying code can be used to work around NULL byte restrictions. This technique is not useful for single-instruction patching on PowerPC, since the instruction pre-fetch and instruction cache can result in the non-modified instruction being executed instead.

4.1 Undefined Bits

To write interesting shellcode for Mac OS X, you need to use system calls. One of the first problems encountered with the PowerPC platform is that the system call instruction assembles to 0x44000002, which contains two NULL bytes. If we take a look at the IBM PowerPC reference for the ’sc’ instruction, we see that the bit layout is as follows:

010001 00000 00000 0000 0000000 000 1 0

------ ----- ----- ---- ------- --- - -

A B C D E F G H

These 32 bits are broken down into eight specific fields. The first field (A), which is 5 bits wide, must be set to the value 17. The bits that make up B, C, and D are all marked as undefined. Field E is must either be set to 1 or 0.

Fields F and H are undefined, and G must always be set to 1. We can modify the undefined bits to anything we like, in order to make the corresponding byte values NULL-free. The first step is to reorder these bits along byte boundaries and mark what we are able to change.

? = undefined

# = zero or one

[010001??] [????????] [????0000] [00#???1?]

The first byte of this instruction can be either 68, 69, 70, or 71 (DEFG). The second byte can be any character at all. The third byte can either be 0, 16, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, or 240 (which contains ’0’, ’P’, and ’p’, among others). The fourth value can be any of the following

values: 2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 23, 26, 27, 30, 31, 34, 35, 38, 39, 42, 43, 46, 47, 50, 51, 54, 55, 58, 59, 62, 63. As you can see, it is possible to create thousands of different opcodes that are all treated by the processor as a system call. The same technique can be applied to almost any other instruction that has undefined bits. (Although the current line of PowerPC chips used with Mac OS X seem to ignore the

undefined bits, future processors may actually use these bits. It is entirely possible that undefined bit abuse can prevent your code from working on newer processors).

;;

;; Patching the undefined bits in the ’sc’ opcode

;;

main:

li r0, 1 ; sys_exit

li r3, 0 ; exit status

.long 0x45585037 ; sc patched as "EXP7"

4.2 Index Registers

On the PowerPC platform, immediate values are encoded using all 16 bits. If the assembled value of your immediate contains a NULL, you will need to find another way to load it into the target register. The most common technique is to first load a NULL-free value into a register, then substract that value minus the difference to your immediate.

;;

;; Demonstrate index register usage

;;

main:

li r7, 1999 ; place a NULL-free value into the index

subi r5, r7, 1999-1 ; substract our value minus the target

; the r5 register is now set to 1

If you have a rough idea of the immediate values you will need in your shellcode, you can take this a step further. Set your initial index register to a value, that when decremented by the immediate value, actually results in a character of your choice. If you have two distant ranges (1-10 and 50-60), then consider using two index registers. The example below demonstrates an index register that works for the system call number as well as the arguments, leaving the assembled bytes NULL-free. As you can see, besides the four bytes required to set the index register, this method does not significantly increase the size of the code.

;;

;; Create a TCP socket without NULL bytes

;;

main:

li r7, 0x3330 ; 0x38e03330 = NULL-free index value

subi r0, r7, 0x3330-97 ; 0x3807cd31 = system call for sys_socket

subi r3, r7, 0x3330-2 ; 0x3867ccd2 = socket domain

subi r4, r7, 0x3330-1 ; 0x3887ccd1 = socket type

subi r5, r7, 0x3330-6 ; 0x38a7ccd6 = socket protocol

.long 0x45585037 ; patched ’sc’ instruction

4.3 Branching

Branching to a forward address without using NULL bytes can be tricky on PowerPC systems. If you try branching forward, but less than 256 bytes, your opcode will contain a NULL. If you obtain your current address and want to branch to an offset from it, you will need to place the target address into the count register (ctr) or the link register (lr). If you decide to use the link register, you will notice that every valid form of ”blr” has a NULL byte. You can avoid the NULL byte by setting the branch hint bits (19-20) to ”11” (unpredictable branch, do not optimize). The resulting opcode becomes 0x4e804820 instead of 0x4e800020 for the standard ”blr” instruction.

The branch prediction bit (bit 10) can also come in handy, it is useful if you need to change the second byte of the branch instruction to a different character.

The prediction bit tells the processor how likely it is that the instruction will result in a branch. To specify the branch prediction bit in the assembly source, just place ’-’ or ’+’ after the branch instruction.