Plastic Displays

Polyester may be the material of choice for future flat panel displays. Researchers in the U.S. have recently made breakthroughs in developing thin film transistor displays out of polyethylene terephthalate (PET) - a thin, flexible and rugged plastic that you can bend, roll up, fold, or bend into practically any shape you need.

How do you coax a seemingly inflexible, delicate display to perform such acrobatics? The answer is in the roll to roll technique, a process for manufacturing thin film transistors (TFTs). Conventional TFTs are manufactured onto a rigid glass substrate, but the new technique calls for making the transistors on flexible plastic. In fact plastic displays can be manufactured in much the same way that potato chip bags are produced, in which a giant sheet is spooled onto a machine that prints the packaging and cuts the material into individual chip bags.

In manufacturing displays, the plastic would be spooled through a machine, transistor circuit layers would be deposited onto the material, etching processes would produce patterns to form the pixels, and the display would then be cut to size.

Technical challenges still remain. This type of process of making semiconductors doesn't exist yet. The concept holds promise not only for a new generation of ultralight, flexible displays but also for cost savings. Since manufacturing plants will need to be retooled for the roll to roll process, startup costs will be substantial. But the potential for cost savings in the long run because of cheap plastic and mass production techniques is also significant.

The real technical challenge though, is a matter of heat. In conventional TFT production, temperatures reach up to 350 degrees Celsius, hotter than plastic can withstand without deforming. The Lawrence Livermore group, funded by DARPA's High Definition Systems Project recently built high performance transistors at or below 100 degrees Celsius by using a short burst of light lasting 35 nanoseconds to produce the polycrystalline silicon (polysilicon).

Meanwhile, Philips Semiconductors Lab in Red Hill, Surrey, England, is also making headway in developing plastic displays. Its recipe calls for making polysilicon transistors on plastic by baking the plastic first, so that the heat used in the transistor production process doesn't cause expansion.

Although mass production of plastic displays is five years away, they could be used in all sorts of ways. The applications could include notebook and desktop displays, video game machines, and hand held appliances, as well as displays that don't exist now, for example, wrap around simulators, roll up displays, wearable displays sewn into clothing, and paper thin electronic books and newspapers. E Ink, based in Boston, is currently developing an ultrathin electronic book based on plastic technology.

Protonic Memory

One of the minor horrors of the computer age is to be working on a document not yet saved to the hard drive and lose everything because of a power outage or a system crash that forces the operator to shut down the computer.

Attempts to create circuits that store the information when the power is interrupted have used high voltages, which quickly wear down computer electronic components, and have been expensive. Now scientists at Sandia and at France Telecom have applied for a patent on a prototype memory retention device that is inexpensive, low-powered, and simple to fabricate.

To transmit data, the device uses embedded protons, which remain where they are when the power turns off, thus preserving the information. In devices such as DRAM's (dynamic random access memory), typically based on electron flow, the information is lost when the power is turned off.

To create the memory retentive chip, only a few steps must be added to the hundreds currently used to fabricate microchips. The key additional step is to bathe the hot microchip in hydrogen gas. The gas, permeating the chip, breaks up into single ions - protons - at defects in the silicon dioxide. (The defects are created by the heat of the manufacturing process.) The protons can roam only within the chip's central layer of silicon dioxide, where they are trapped by two layers of silicon that sandwich the silicon dioxide.

The Sandia researchers found that:

A positive low voltage applied to one side of the silicon repels the protons to the far side of the silicon dioxide.

A negative low voltage applied to the silicon attracts the protons to the near side of the silicon dioxide.

If the power is turned off, the protons stay where they are, retaining information in the chip circuit.

First observation of the effect that protons remain in silicon when it is baked at high temperatures in hydrogen gas came as part of a systematic study at Sandia and France Telecom of the effects of hydrogen on silicon.

Life

इन्टरनेट

Today another sunny day and I still sit on my couch thinking about another boring day for me, there would not be power in my region for empowering my computer for evading my boredom. But whatsoever, life never stops. Unfortunately always in life you think a lot to you but it never comes true. I also weaved my dreams in my life but, have broken now. And now struggling with my broken dreams to get rid off but it still continue to arise endless hope. In life as I think, it gives you the way it wants to, but when it fails to get the right direction as if decided. Then the life has messed around and it has nothing to stay with. Life is very pouring thing as water it always want to pour in its direction. When you direct its way by yourself then it denies. As my dream has broken, I am sheer confused. Now I am sitting around my chair and thinking about my future life, how is it going to be? After all I am not leaving my hope cause of life is an on going property and it never stops. Just I want to share my personal family condition to all of you, well I don’t know whether it is right or not as a family member after describing all, I think I will feel better than before that bottled away. I born in a small village of Bihar, the state of India called Babhanauli. And then I came to a small town of Bihar, Katihar. I have been brought here by my aunty. My uncle don’t want me very much as my aunty, they bring up me. I have studied in very difficulties. But forgot that all now I am 23 old and I think this is the right age to start my carrier. And I am going abroad for getting by my life. I should think life is the gift of god and we should live it in the manner that life wants by its own way. Always listen to your life and your heart because life is precious and so beautiful….

Just a day for our beautiful life that has one end motion even after many hardship and difficulties.

By—Rajesh Kumar

Thank you.

IEEE 802.22 WRAN Standard

The IEEE 802.22 standard defines a system for a Wireless Regional Area Network, WRAN that uses unused or white spaces within the television bands between 54 and 862 MHz, especially within rural areas where usage may be lower.

To achieve its aims, the 802.22 standard utilises cognitive radio technology to ensure that no undue interference is caused to television services using the television bands. In this way 802.22 is the first standard to fully incorporate the concept of cognitive radio.

The IEEE 802.22 WRAN standard is aimed at supporting license-exempt devices on a non-interfering basis in spectrum that is allocated to the TV Broadcast Service. With operating data rates comparable to those offered by many DSL / ADSL services it can provide broadband connectivity using spectrum that is nominally allocated to other services without causing any undue interference. In this way IEEE 802.22 makes effective use of the available spectrum without the need for new allocations.

IEEE 802.22 background

The IEEE 802.22 standard for a Wireless Regional Area Network or WRAN system has been borne out of a number of requirements, and also as a result of a development in many areas of technology.

In recent years there has been a significant proliferation in the number of wireless applications that have been deployed, and along with the more traditional services this has placed a significant amount of pressure on sharing the available spectrum. Coupled to this there is always a delay in re-allocating any spectrum that may come available.

In addition to this the occupancy levels of much of the spectrum that has already been allocated is relatively low. For example in the USA, not all the TV channels are used as it is necessary to allow guard bands between active high power transmitters to prevent mutual interference. Also not all stations are active all of the time. Therefore by organising other services around these constraints it is possible to gain greater spectrum utilisation without causing interference to other users. Despite the fact that the impetus for 802.22 is coming from the USA, the aim for the standard is that it can be used within any regulatory regime.

One particular technology that is key to the deployment of new services that may bring better spectrum utilisation is that of cognitive radios technology. By using this the radios can sense their environment and adapt accordingly. The use of cognitive radio technology is therefore key to the new IEEE 802.22 WRAN standard.

IEEE 802.22 standard history

The concept for 802.22 can trace its origins back to the first ideas for cognitive radio. With the development of technologies for the software defined radio, J Mitola in his doctoral thesis in 2000 coined the name "Cognitive Radio" for a form of radio that would change its performance by detecting its environment and changing accordingly.

In 2004 the FCC issued and NPRM (notice of proposed rulemaking) regarding the television spectrum. As a result in November 2004 the IEEE 802.22 working group was formed to develop a WRAN system that would deliver broadband connectivity particularly to rural areas by sharing the television spectrum.

By May 2006 draft v0.1 of the IEEE 802.22 standard was available, although much work was still required. Also discussions were required with broadcasters whose spectrum was being shared as they were fearful of interference and reduced revenues from advertising as a result.

The standard is expected to be completed by the first quarter of 2010 and with this some of the first networks could be deployed.

802.22 basics

There are a number of elements that were set down for the basis of the 802.22 standard. These include items such as the system topology, system capacity and the projected coverage for the system. By setting these basic system parameters in place, the other areas fall into place.
System topology: The system is intended to be a point to multipoint system, i.e. it has a base station with a number of users or Customer Premises Equipments, CPEs located within a cell. The base station obviously links back to the main network and transmits the data on the downlink to the various users and receivers data from the CPEs in the uplink. It also controls the medium access and addition to these traditional roles for a base station, it also manages the "cognitive radio" aspects of the system. It uses the CPEs to perform a distributed measurement of the signal levels of possible television (or other) signals on the various channels at their individual locations. These measurements are collected and collated and the base station decides whether any actions are to be taken. In this way the IEEE 802.22 standard is one of the first cognitive radio networks that has been defined.
Coverage area: The coverage area for the IEEE 802.22 standard is much greater than many other IEEE 802 standards - 802.11, for example is limited to less than 50 metres in practice. However for 802.22, the specified range for a CPE is 33 km and in some instances base station coverage may extend to 100 km. To achieve the 33 km range, the power level of the CPE is 4 Watts EIRP (effective radiated power relative to an isotropic source).
System capacity: The system has been defined to enable users to achieve a level of performance similar to that of DSL services available. This equates to a downlink or download speed of around 1.5 Mbps at the cell periphery and an uplink or upstream speed of 384 kbps. These figures assume 12 simultaneous users. To attain this the overall system capacity must be 18 Mpbs in the downlink direction.

In order to be able to meet these requirements using a 6 MHz television channel spectral efficiency of around 3 bits / sec / Hz are required to give the required physical layer raw data transfer rate.

A study of knowledge management

In the prevailing uncertain and ever-changing business environment knowledge has become the single certain source for sustainable competitive advantage. Learning from past mistakes and avoiding reinventing the wheel are crucial tasks and no organization can today afford not to look for ways to make the best use of its knowledge. With Siemens Industrial Turbomachinery AB (SIT) being an actor in a complex and high-technology industry managing and leveraging the organization’s knowledge becomes essential. It came to the authors’ attention that the project manager department (GL) within the gas division of SIT experienced a need for improved processes for managing and utilizing the organization’s knowledge-base.

On the first of January 2010 Siemens carried out a major reorganization, which affected SIT and the GL department by merging two previously separate departments of project managers into one unit. With efforts underway to harmonize the two department’s former working methods the situation implies timeliness for conducting a study on how to improve the company’s knowledge management initiative. This master thesis hence evolved to focus on examining and point out the improvement opportunities that exist with regards to knowledge sharing between projects, and between projects and the organization, and how tools and processes should be designed to collect, preserve, disseminate and reuse experiences, knowledge and lessons learned within a project-based organization in the best possible way.

The research approach of the study was of a qualitative character including interviews with the 16 project managers of GL and other key employees both at SIT and at Siemens Oil & Gas division’s new CS and IP business units. Combined with meeting participation and observations of the project managers in their daily operations an increased understanding of the current situation at SIT and GL emerged; an understanding needed to identify the reasons and factors affecting the low degree of retention and utilization of the organization’s knowledge-base; an understanding leading up to the development of a model highlighting the important aspects for successful knowledge management initiatives, and how these aspects correlate.

In order to improve the knowledge utilization a continuous lessons learned gathering throughout the project life-cycle needs to be implemented. This is primarily achieved through collecting lessons learned at the regular project meetings together with special lessons learned workshops. The collection and reutilization of knowledge hence needs to be integrated with the project management process. Improving the different forums available for knowledge sharing is also needed to enable an increased level of transformation of human capital into structural capital; augmenting the organization’s knowledge-base. Providing forums for knowledge sharing together with a visualized management support through actions, feedback and the introduction of a culture aimed at organizational learning further enhance the retention and utilization of the organization’s knowledge-base.

Although the approach of this study is based on a case study of the SIT organization the conclusions are regarded to be of value for other project-based organizations and thus rending the conclusions to be generalized and used within other lines of business. The generic conclusion of this study is that in order to implement a successful knowledge management initiative all factors of the model need to be considered and attended too.

System Implementation

The implementation of the algorithms described in Chapter 3 consists of approximately 7000 lines of C++.
This code is logically divided into components that match the system diagram in Figure 3.1. In this Chapter
we will explain the details of our implementation, focusing on the instrumentation and analysis routines that
make up the core of the system and the corresponding data structures.
4.1 Binary Instrumentation
The implementation of stage 1 of our algorithm is essentially two components that work in tandem to
perform instrumentation and run-time analysis. Using the functionality provided by Pin we instrument a
variety of events, including thread creation, system calls, and instruction execution. The instrumentation
code analyses the events and registers callbacks to the correct run-time processing routines.
4.1.1 Hooking System Calls
All taint analysis algorithms require some method to seed an initial pool of tainted locations. One approach
is to hook system calls known to read data that may be potentially tainted by attacker input, e.g. read.
Another potential approach is to hook specific library calls, but as previously pointed out [14] this could
require one to hook large numbers of library calls instead of a single system call on which they all rely.
To mark memory locations as tainted we hook the relevant system calls and extract their destination
locations. Pin allows us to register functions to be called immediately before a system call is executed
(PIN AddSyscallEntryFunction) and after it returns (PIN AddSyscallExitFunction). We use
this functionality to hook read, recv and recvfrom. When a system call is detected we extract the
destination bu er of the function using PIN GetSyscallArgument and store the location. This provides
us with the start address for a sequence of tainted memory locations.
When a system call returns we extract its return value using Pin GetSyscallReturn. For the system
calls we hook a return value greater than 0 means the call succeeded and data was read in. When the return
value is greater than 0 it also indicates exactly how many contiguous bytes from the start address we should
consider to be tainted. On a successful system call we first store the data read in, the destination memory
location and the file or socket it came from in a DataSource object. The DataSource class is a class
we created to allow us to keep track of any input data so that it can be recreated later when building the
exploit. It also allows us to determine what input source must be used in order to deliver an exploit to the
target program. Once the DataSource object has been stored we mark the range of the destination bu er
as tainted.
Once a location has been marked as tainted the instruction level instrumentation code can propagate the
taint information through the programs memory and registers.
45
4.1.2 Hooking Thread Creation and Signals
As well as system calls we insert hooks on thread creation and on signals received from the OS. In multithreaded
applications it is necessary for us to determine when threads are created and destroyed and to
identify the currently active thread when calling our analysis routines. Threads do not share registers so
a register that is tainted by one thread should not be marked as tainted for any others. When a thread is
created we instantiate a new object in our taint analysis engine that represents the taint state of its registers.
This object is deleted when the thread is destroyed.
As mentioned in Chapter 3, one of the mechanisms one could potentially use to detect a possible vulnerability
is by analysing any signals sent to the program. Using the function PIN AddContextChangeFunction
we can register a routine to intercept such signals. If the signal is one of SIGKILL, SIGABRT or SIGSEGV
we pause the program and attempt to generate an exploit. We eventually decided not to use this mechanism
for vulnerability detection as it introduced complications when attempting to determine the exact cause of
the signal and hence the vulnerability.
4.1.3 Hooking Instructions for Taint Analysis
In Chapter 3 all of the binary instrumentation is performed by algorithm 3.1. In this section we will elaborate
on the methods by which this instrumentation takes place.
Our taint analysis engine provides a low level API through the TaintManager class. This class provides
methods for directly marking memory regions and registers as tainted or untainted. To reflect the
taint semantics of each x86 instruction at run-time we created another class titled x86Simulator. This
class interacts directly with the TaintManager class and provides a higher level API to the rest of our
analysis client. For each x86 instruction X the x86Simulator contains functions with names beginning
with simulateX e.g. simulateMOV corresponds to the mov instruction. Each of these functions takes
arguments specifying the operands of the x86 instruction and computes the set of tainted locations resulting
from the instruction and these operands.
For each instruction taint analysis is performed by inserting a callback into the instruction stream to the
correct simulate function and provide it with the instructions operands. As Pin does not utilise an IR this
requires us to do some extra processing on each instruction in order to determine the required simulation
function and extract the instructions operands.
The x86Simulator class provides a mechanism for taint analysis but to use it we must have a method of
analysing individual x86 instruction. Pin allows one to register a function to hook every executed instruction
via INS AddInstrumentFunction. We use this function to filter out those instructions we wish to process.
For every instruction executed we first determine exactly what instruction it is so we can model its taint
semantics. This process is made easier as Pin filters each instruction into one or more categories, e.g. the
movsb instruction belongs to the XED CATEGORY STRINGOP category. It also assigns each instruction a
unique type, e.g. XED ICLASS MOVSB for the movsb instruction. An example of the code that performs
this filtering is shown in Listing 4.1.
This code allows us to determine the type of instruction being executed. The code to process the actual
instruction and insert the required callback is encapsulated in the processX86.processX functions.
Inserting Taint Analysis Callbacks
When hooking an instruction the goal is to determine the correct x86Simulator function to register a
callback to so that at run-time we can model the taint semantics of the instruction correctly. The code in
Listing 4.1 allows us to determine the instruction being executed but each instruction can have di erent
taint semantics depending on the types of its operands. For example, the x86 mov instruction can occur
in a number of di erent forms with the destination and source operands potentially being one of several
combinations of memory locations, registers and constants. In order to model the taint semantics of the
instruction we must also know the type of each operand as well as the type of the instruction. Listing 4.2
demonstrates the use of the Pin API to extract the required operand information for the mov instruction.
The code shown is part of the processX86.processMOV function.
46
Listing 4.1: “Filtering x86 instructions”
1 UINT32 cat = INS_Category(ins);
2
3 switch (cat) {
4 case XED_CATEGORY_STRINGOP:
5 switch (INS_Opcode(ins)) {
6 case XED_ICLASS_MOVSB:
7 case XED_ICLASS_MOVSW:
8 case XED_ICLASS_MOVSD:
9 processX86.processREP_MOV(ins);
10 break;
11 case XED_ICLASS_STOSB:
12 case XED_ICLASS_STOSD:
13 case XED_ICLASS_STOSW:
14 processX86.processSTO(ins);
15 break;
16 default:
17 insHandled = false;
18 break;
19 }
20 break;
21
22 case XED_CATEGORY_DATAXFER:
23
24 ...
Listing 4.2: “Determining the operand types for a mov instruction”
1 if (INS_IsMemoryWrite(ins)) {
2 writesM = true;
3 } else {
4 writesR = true;
5 }
6
7 if (INS_IsMemoryRead(ins)) {
8 readsM = true;
9 } else if (INS_OperandIsImmediate(ins, 1)) {
10 sourceIsImmed = true;
11 } else {
12 readsR = true;
13 }
Listing 4.3: “Inserting the analysis routine callbacks for a mov instruction”
1 if (writesM) {
2 INS_InsertCall(ins, IPOINT_BEFORE, AFUNPTR(&x86Simulator::simMov_RM),
3 IARG_MEMORYWRITE_EA,
4 IARG_MEMORYWRITE_SIZE,
5 IARG_UINT32, INS_RegR(ins, INS_MaxNumRRegs(ins)-1),
6 IARG_INST_PTR,
7 IARG_END);
8 } else if (writesR) {
9 if (readsM)
10 INS_InsertCall(ins, IPOINT_BEFORE, AFUNPTR(&x86Simulator::simMov_MR), ..., IARG_END);
11 else
12 INS_InsertCall(ins, IPOINT_BEFORE, AFUNPTR(&x86Simulator::simMov_RR), ..., IARG_END);
13 }
47
Once the operand types have been extracted we can determine the correct function in x86Simulator
to register as a callback. The x86Simulator class contains a function for every x86 instruction we wish
to analyse and for each instruction it contains one or more variants depending on the possible variations in
its operand types. For example, a mov instruction takes two operands; ignoring constants it can move data
from memory to a register, from a register to a register or from a register to memory. This results in three
functions in x86Simulator to handle the mov instruction - simMov MR, simMov RR and simMov RM.
The code in Listing 4.3 is from the function processX86.processMOV. It uses function INS InsertCall
to insert a callback to the correct analysis routine depending on the types of the mov instructions operands.
Along with the callback function to register, INS InsertCall takes the parameters to pass to this function1.
This process is repeated for any x86 instructions we consider to propagate taint information.
Under-approximating the Set of Tainted Locations
Due to time constraints on our implementation we have not created taint simulation functions for all possible
x86 instructions. In order to avoid false positives it is therefore necessary to have a default action for all
non-simulated instructions. This default action is to untaint all destination operands of the instruction. Pin
provides API calls that allow us to access the destination operands of an instruction without considering its
exact semantics. By untainting these destinations we ensure that all locations that we consider to be tainted
are in fact tainted. We perform a similar process for instructions that modify the EFLAGS register but are
not instrumented.
4.1.4 Hooking Instructions to Detect Potential Vulnerabilities
We detect potential vulnerabilities by checking the arguments to certain instructions. For a direct exploit
we require the value pointed to by the ESP register at a ret instruction to be tainted or the memory location/
register used by a call instruction. We can extract the value of the ESP using the IARG REG VALUE
placeholder provided by Pin and the operands to call instructions can be extracted in the same way as for
the taint analysis callbacks.
For an indirect exploit we must check the destination address of the write instruction is tainted, rather
than the value at that address. As described in [19], an address to an x86 instruction can have a number of
constituent components with the e ective address computed as follows2:
Effective address = Displacement + BaseReg + IndexReg * Scale
In order to exploit a write vulnerability we must control one or more of these components. Pin provides
functions to extract each component of an e ective address. e.g. INS OperandMemoryDisplacement,
INS OperandMemoryIndexReg and so on. For each instruction that writes to memory we insert a callback
to run-time analysis routine that takes these address components as parameters and the value of the write
source.
4.1.5 Hooking Instructions to Gather Conditional Constraints
As described in Chapter 3, to gather constraints from conditional instructions we record the operands
of instructions that modify the EFLAGS register and then generate constraints on these operands when
a conditional jump is encountered. Detecting if an instruction writes to the EFLAGS register is done
by checking if the EFLAGS register is in the list of written registers for the current instruction, e.g. if
1At instrumentation-time it is sometimes not possible to determine the exact operand values an instruction will have at runtime.
To facilitate passing such information to run-time analysis routines Pin provides placeholder values. These placeholders
are replaced by Pin with the corresponding value at run-time. For example, there are placeholders for the address written
by the instruction (IARG MEMORYWRITE EA) and the amount of data written (IARG MEMORYWRITTEN EA). There are a number
of other placeholders defined for retrieving common variables such as the current thread ID, instruction pointer and register
values.
2From the Pin website, http://www.pintool.org
48
Listing 4.4: “Inserting a callback on EFLAGS modification”
1 if (op0Mem && op1Reg) {
2 INS_InsertCall(ins, IPOINT_BEFORE, AFUNPTR(&x86Simulator::updateEflagsInfo_RM),
3 IARG_MEMORYREAD_EA,
4 IARG_MEMORYREAD_SIZE,
5 IARG_UINT32, INS_RegR(ins, INS_MaxNumRRegs(ins)-1),
6 IARG_UINT32, eflagsMask,
7 IARG_CONTEXT,
8 IARG_THREAD_ID,
9 IARG_INST_PTR,
10 IARG_END);
11 }
Listing 4.5: “Inserting callbacks on a conditional jump”
1 VOID
2 processJCC(INS ins, JCCType jccType)
3 {
4 unsigned eflagsMask = extractEflagsMask(ins, true);
5 INS_InsertCall(ins, IPOINT_AFTER, AFUNPTR(&x86Simulator::addJccCondition),
6 IARG_UINT32, eflagsMask,
7 IARG_BOOL, true,
8 IARG_UINT32, jccType,
9 IARG_INST_PTR,
10 IARG_END);
11
12 INS_InsertCall(ins, IPOINT_TAKEN_BRANCH, AFUNPTR(&x86Simulator::addJccCondition),
13 IARG_UINT32, eflagsMask,
14 IARG_BOOL, false,
15 IARG_UINT32, jccType,
16 IARG_INST_PTR,
17 IARG_END);
18 }
INS RegWContain(ins, REG EFLAGS) is true. If an instruction does write to the EFLAGS register we
can extract from it a bitmask describing those flags written.
Using the same INS Is* functions as shown in Listing 4.2 we determine the types of each operand.
Once again this is necessary as we use a di erent simulation function for each combination of operand types,
where an operand type can be a memory location, register or constant. Once the operand types have been
discovered we register a callback to the correct run-time routine, passing it the instruction operands and a
bitmask describing the bits changed in the EFLAGS register. Listing 4.4 exemplifies how the callback is
registered for a two operand instruction where the first operand is a memory location and the second is a
register.
On lines 3 and 4 the Pin placeholders to extract the memory location used and its size are used. The
register ID is extracted on line 5 and passed as a 32-bit integer. Similarly the bitmask describing the EFLAGS
modified is passed as a 32-bit integer on line 6.
Inserting Callbacks to Record Conditions from Conditional Jumps
The above code is used to keep track of the operands on which conditional jumps depend on. To then
convert this information to a constraint we need to instrument conditional jumps. Algorithm 3.1 in Chapter
3 we described the process of instrumenting a conditional jump instruction. We insert two callbacks for each
conditional jump. One on the path resulting from a true condition and one on the path resulting from a
false condition.
49
Listing 4.6: “Simulating a mov instruction”
1 VOID
2 x86Simulator::simMov_MR(UINT32 regId, ADDRINT memR, ADDRINT memRSize, THREADID id, ADDRINT pc)
3 {
4 SourceInfo si;
5
6 // If the source location is not tainted then untaint the destination
7 if (!tmgr.isMemLocTainted(memR, memRSize)) {
8 tmgr.unTaintReg(regId, id);
9 return;
10 }
11
12 // Set the information on the source operand
13 si.type = MEMORY;
14 // The mov instruction reads from address memR
15 si.loc.addr = memR;
16
17 vector sources;
18 sources.push_back(si);
19
20 TaintInfoPtr tiPtr = tmgr.createNewTaintInfo(sources, (unsigned)memRSize,
21 DIR_COPY, X_ASSIGN, 0);
22 tmgr.updateTaintInfoR(regId, tiPtr, id);

MSc Computer Science Dissertation

Introduction
1.1 Introduction
In this work we will consider the problem of automatic generation of exploits for software vulnerabilities. We
provide a formal definition for the term “exploit” in Chapter 2 but, informally, we can describe an exploit
as a program input that results in the execution of malicious code1. We define malicious code as a sequence
of bytes injected by an attacker into the program that subverts the security of the targeted system. This is
typically called shellcode. Exploits of this kind often take advantage of programmer errors relating to memory
management or variable typing in applications developed in C and C++. These errors can lead to bu er
overflows in which too much data is written to a memory bu er, resulting in the corruption of unintended
memory locations. An exploit will leverage this corruption to manipulate sensitive memory locations with
the aim of hijacking the control flow of the application.
Such exploits are typically built by hand and require manual analysis of the control flow of the application
and the manipulations it performs on input data. In applications that perform complex arithmetic
modifications or impose extensive conditions on the input this is a very di cult task. The task resembles
many problems to which automated program analysis techniques have been already been successfully applied
[38, 27, 14, 43, 29, 9, 10, 15]. Much of this research describes systems that consist of data-flow analysis in
combination with a decision procedure. Our approach extends techniques previously used in the context of
other program analysis problems and also encompasses a number of new algorithms for situations unique to
exploit generation.
1.2 Motivation
Due to constraints on time and programmer e ort it is necessary to triage software bugs into those that
are serious versus those that are relatively benign. In many cases security vulnerabilities are of critical
importance but it can be di cult to decide whether a bug is usable by an attacker for malicious purposes or
not. Crafting an exploit for a bug is often the only way to reliably determine if it is a security vulnerability.
This is not always feasible though as it can be a time consuming activity and requires low-level knowledge
of file formats, assembly code, operating system internals and CPU architecture. Without a mechanism
to create exploits developers risk misclassifying bugs. Classifying a security-relevant bug incorrectly could
result in customers being exposed to the risk for an extended period of time. On the other hand, classifying
a benign bug as security-relevant could slow down the development process and cause extensive delays as it
is investigated. As a result, there has been an increasing interest into techniques applicable to Automatic
Exploit Generation (AEG).
1We consider exploits for vulnerabilities resulting from memory corruption. Such vulnerabilities are among the most common
encountered in modern software. They are typically exploited by injecting malicious code and then redirecting execution to
that code. Other vulnerabililty types, such as those relating to design flaws or logic problems, are not considered here.
3
The challenge of AEG is to construct a program input that results in the execution of shellcode. As the
starting point for our approach we have decided to use a program input that is known to cause a crash.
Modern automated testing methods routinely generate many of these inputs in a testing session, each of
which must be manually inspected in order to determine the severity of the underlying bug.
Previous research on automated exploit generation has addressed the problem of generating inputs that
corrupt the CPU’s instruction pointer. This research is typically criticised by pointing out that crashing a
program is not the same as exploiting it [1]. Therefore, we believe it is necessary to take the AEG process a
step further and generate inputs that not only corrupt the instruction pointer but result in the execution of
shellcode. The primary aim of this work is to clarify the problems that are encountered when automatically
generating exploits that fit this description and to present the solutions we have developed.
We perform data-flow analysis over the path executed as a result of supplying a crash-causing input
to the program under test. The information gathered during data-flow analysis is then used to generate
propositional formulae that constrain the input to values that result in the execution of shellcode. We
motivate this approach by the observation that at a high level we are trying to answer the question “Is it
possible to change the test input in such a way that it executes attacker specified code?”. At its core, this
problem involves analysing how data is moved through program memory and what constraints are imposed
on it by conditional statements in the code.
1.3 Related Work
Previous work can be categorised by their approaches to data-flow analysis and their final result. On one
side is research based on techniques from program analysis and verification. These projects typically use
dynamic run-time instrumentation to perform data-flow analysis and then build formulae describing the
programs execution. While several papers have discussed how to use such techniques to corrupt the CPU’s
instruction pointer they do not discuss how this corruption is exploited to execute shellcode. Significant
challenges are encountered when one attempts to take this step from crashing the program to execution of
shellcode.
Alternatives to the above approach are demonstrated in tools from the security community [37, 28] that
use ad-hoc pattern matching in memory to relate the test input to the memory layout of the program at the
time of the crash. An exploit is then typically generated by using this information to complete a template.
This approach su ers from a number of problems as it ignores modifications and constraints applied to
program input. As a result it can produce both false positives and false negatives, without any information
as to why the exploit failed to work or failed to be generated.
The following are papers that deal directly with the problem of generating exploits:
(i) Automatic Patch-Based Exploit Generation is Possible: Techniques and Implications - This paper [11]
is the closest academic paper, in terms of subject matter, to our work. An approach is proposed and
demonstrated that takes a program P and a patched version P0, and produces a sample input for P
that exercises the vulnerability patched in P0. Using the assumption that any new constraints added
by the patched version relate to the vulnerability they generate an input that violates these constraints
but passes all others along a path to the vulnerability point (e.g. the first out of bounds write). The
expected result of providing such an input to P is that it will trigger the vulnerability. Their approach
works on binary executables, using data-flow analysis to derive a path condition and then solving such
conditions using the decision procedure STP to produce a new program input.
As the generated program input is designed to violate the added constraints it will likely cause a
crash due to some form of memory corruption. The possibility of generating an exploit that results
in shellcode execution is largely ignored. In the evaluation a specific case in which the control flow
was successfully hijacked is given, but no description of how this would be automatically achieved is
described.
(ii) Convicting Exploitable Software Vulnerabilities: An E cient Input Provenance Based Approach - This
paper [35] again focuses on exploit generation but uses a “suspect input” as its starting point instead
4
of the di erences between two program binaries. Once again data-flow analysis is used to build a path
condition which is then used to generate a new input using a decision procedure. User interaction is
required to specify how to mutate input to meet certain path conditions. As in the previous case,
the challenges and benefits involved in generating an exploit that result in shellcode execution are not
discussed.
(iii) Byakugan - Byakugan [28] is an extension for the Windows debugger, WinDbg, that can search through
program memory attempt to match sequences of bytes from an input to those found in memory. It
can work with the Metasploit [39] tool to assist in generation of exploits. In terms of the desired end
result, this is similar to our approach although it su ers from the limitations of pattern matching.
When searching in memory the tool accounts for common modification to data such as converting to
upper/lower case and unicode encoding but will miss all others. It makes no attempt at tracking path
conditions and as a result can o er no guarantees on what parts of the input are safe to change and
still trigger the vulnerability.
(iv) Automated Exploit Development, The future of exploitation is here - This document [37] is a whitepaper
describing the techniques used in the Prototype-8 tool for automated exploit generation. The generation
of control flow hijacking exploits is the focus of the tool. This is achieved by attaching a debugger to
a running process and monitoring its execution for erroneous events as test cases are delivered to the
program. When such an event occurs the tool follows a static set of rules to create an exploit based
on what type of vulnerability was discovered (i.e. it distinguishes between stack and heap overflows).
These rules attempt to determine what parts of the input data overwrote what sensitive data and hence
may be used to gain control of the program execution. Once this is determined these values are used to
generate an exploit based on a template for the vulnerability type. No attempt is made to determine
constraints that may exist on this input or to customise the exploit template to pass these constraints.
(v) Automatic Discovery of API-Level Exploits - In this paper [25] a framework is presented to model the
details of the APIs provided by functions such as printf. Once the e ects of these API features have
been formalised they can be used in predicates to specifying conditions required for an exploit. These
predicates can then be automatically solved to provide API call sequences that exploit a vulnerability.
This approach is restricted to creating exploits where all required memory corruption can be introduced
via a single API, such as printf.
As well as the above papers, the BitBlaze project [50] has resulted in a number of papers that do not
deal explicitly with the generation of exploits but do solve related problems. Approaching the issue of
automatically generating signatures for vulnerabilities [9, 10] they describe a number of useful techniques
for gathering constraints up to a particular vulnerability point and using these constraints to describe data
that might constitute an exploit.
There is also extensive previous work on data-flow analysis, taint propagation, constraint solving and
symbolic execution. Combinations of these techniques to other ends, such as vulnerability discovery [27, 14],
dynamic exploit detection [43] and general program analysis [29] are now common.
1.4 Thesis
Our thesis is as follows:
Given an executable program and an input that causes it to crash there exists a sound algorithm to determine
if a control flow hijacking exploit is possible. If a control flow hijacking exploit is possible there exists
an algorithm that will automatically generate this exploit.
The purpose of this work is to investigate the above thesis and attempt to discover and implement a
satisfying algorithm. Due to the sheer number of ways in which a program may crash, and a vulnerability be
5
exploited, it is necessary to limit our research to a subset of the possible exploit types. In our investigation
we impose the following practical limits2:
1. Data derived from user input corrupts a stored instruction pointer, function pointer or the destination
location and source value of a write instruction.
2. Address space layout randomisation may be enabled on the system but no other exploit prevention
mechanisms are in place.
3. Shellcode is not automatically generated and must be provided to the exploit generation algorithm.