Pages

October 16, 2014

Interlocked Instructions

In this post, I will discuss the implementation of the InterlockedIncrement API (and its counterpart, the InterlockedDecrement) found in Win32 SDK. I will also talk about how it is used in COM to track object lifetimes. This API is declared in WinBase.h and exported by kernel32.dll as specified in MSDN. This API is one of the many Interlocked functions available in the Win32 SDK. These APIs help in implementation of various synchronization mechanisms such as semaphores.

I first came across InterlockedIncrement when going through a COM application's source code. Every COM class is derived from the IUnknown interface and this interface has AddRef and Release functions. As specified in the MSDN article, these functions are together used to keep track of a COM object's lifetime by the reference counting mechanism. A COM server is designed such that a single server object can be used by more than one client. Whenever a COM client obtains a pointer to a COM server object, a call to AddRef must be made and when the object is no longer needed, a call to Release must be made. This way, the server can keep track of how many references to its object are present and can clean itself up when the reference count goes down to zero. The below snippet of pseudo-code should give you an idea of how this is implemented:

class ComServer : public IUnknown {
    UINT nRefs;
    ULONG AddRef() { InterlockedIncrement(&nRefs); } // ++nRefs
    ULONG Release() { InterlockedDecrement(&nRefs); } // --nRefs
    HRESULT QueryInterface(clsid, **ppObject)
    {
        ...
        AddRef();
        return pointer to ComServer object
    }
}

Since COM objects are designed to be used by multiple clients in a multi-threaded (and multi-processor) environment, the incrementing and decrementing of the counter variable (nRefs in above example) must be controlled using some synchronization mechanisms. This is where the InterlockedIncrement and InterlockedDecrement functions come into picture.

Implementation

According to MSDN, InterlockedIncrement "Increments (increases by one) the value of the specified 32-bit variable as an atomic operation." and the InterlockedDecrement function decreases the value of its argument by one. Let us see how these two functions ensure that operations on their arguments are atomic/synchronized. Looking at the assembly code of the function call and implementation of InterlockedIncrement:
Function Call

Function Implementation

The function call is a regular call to a system API. The function implementation is just 5 instructions. The increment is done by a single instruction - the xadd instruction which has a lock prefix. The Intel Developer's Manual Vol2 says about xadd: "This instruction exchanges the first operand(destination) with the second operand(source), then loads the sum of the two values into the destination operand." So ecx contains the address of the memory variable to be incremented and eax contains 1 before the xadd instruction. The xadd instruction does this:

Assert LOCK signal
        |
 temp = eax + *ecx
        |
    eax = *ecx
        |
   *ecx = temp

We can see that even though it is a single assembly instruction, it involves three steps. The LOCK signal assertion is the one that ensures the instruction executes as an atomic operation.

Looking at the same document for the lock prefix: "Asserts LOCK# signal for duration of the accompanying instruction. In a multiprocessor environment, the LOCK# signal insures that the processor has exclusive use of any shared memory while the signal is asserted".

What this means is that the when the LOCK signal is asserted, no other processor or bus agent(could be an memory-mapped IO device) can read/write to the main memory. This ensures that the read-write operations of the variable to be incremented is atomic. All other processors and bus agents must wait until this instruction is complete before accessing the main memory. The very simplified diagram of the system architecture should make it easy to understand:


What If The Variable is Cached?

There is a possibility that the memory variable to incremented/decremented is cached in the processor's cache. In this case, the processor's cache coherency mechanism ensures that the operation is atomic. Intel's developers manual Vol3 states that recent processors do not even assert the LOCK signal if the variable is in the cache, instead uses just the cache locking (a technique to achieve cache coherency) mechanism.

A Look At The 64bit Implementation

The assembly code above is from a 32bit build of the source code. I was curious if the 64bit implementation was any different. So, changing the architecture in VisualStudio, compiling the code and I get this:

No function call?? What's going on? I then looked at the WinBase.h header and found that this function is declared with the __forceinline compiler directive. So this explains why there is no function call. Simply, the address of nRefs is loaded into rax and the inc instruction increments the variable. However, the InterlockedIncrement function is supposed to return the updated value as the function return value. Those two instructions don't do that. So I modified the source code to save the return value to a temporary variable to see what the compiler does:

long tmp = InterlockedIncrement(&nRefs);

This time I saw an implementation similar to the 32bit version but is inlined:





How Does Decrement Work?

There is no subtract equivalent of the xadd instruction, so what does the compiler do? As you see below, it is quite clever - it just uses xadd with -1 so essentially it achieves *ecx = *ecx + (-1).



October 7, 2014

So You Want to Write An API?

The topic of this post is the design of an API. These are things I learnt in the course of writing the CHelpLib library. As most programmers know, API stands for Application Programming Interface. An API consists of a set of functions and data structures that provide some functionality to the user of the API. The most common example is the interface offered by an OS. All functions that are part of the OS, exposed to kernel mode applications like device drivers and user mode applications such as MS Word, make up the API of the OS. We all know the general guidelines around writing functions and designing data structures - clear functionality, keeping it simple, following naming conventions and so on. Many good programmers do follow these, of course, in developing applications but these are probably much more important in the design and implementation of an API because an API has the potential to be used much more widely since it is exposed to the public. Compare this to any module within a particular product, which is only used within the product itself and only the developers working on that product need to understand it.

Some points that I incorporated into the CHelpLib library's APIs:

  • Consistent experience in the usage of all the APIs within the library. This has two aspects: Consistent API usage experience across all functions within the library and consistency with the industry or platform specific conventions.
  • Consistency with the industry/platform makes it easy for the programmer using the API. In my case, this was the Windows platform programming conventions since I was developing for this platform. Consistency of the API includes:
    • Object(data structures) creation, usage and disposal semantics must be similar across the library.
    • Function signatures and naming must be consistent and follow the Windows API model.
    • All functions must be consistent in the way they handle memory allocation/deallocation. This could either be left to the caller or usually shared between the caller and the callee.
    • All functions within the API must follow the same method of error/failure reporting to the caller.
  • A public API must be very well documented and the documentation must be up to date. This means the documentation must include what exactly each function does, how it is supposed to be used, what are the failure scenarios and so on.
  • All known bugs must be documented and made visible to the users.
  • An API/library is meant to provide functionality with as less complexity in usage as possible. To this end, the API must expose very little implementation details (this must be documented, however).
  • If the API consists of functions that provide functionality such as algorithms and data structures: the algorithm design, memory requirements and expected performance should be specified so that the users can make better choices and use the API in a better way.

The most important changes I made to the CHelpLib library in order to incorporate the above points:

  • Simplifying the naming of all functions and avoiding naming collisions with system functions. All function names follow this pattern: "CHL_{module_name}{function_name}". For example, CHL_DsCreateHT - 'Ds' indicates DataStructures, 'CreateHT' indicates that the function creates a hashtable.
  • Standardizing the error/failure reporting using HRESULT as the return type of most functions. This type is the recommended return type on the Windows platform.
  • Since return type is used only to indicate function success or failure, programmatic return values are passed back to caller via 'out' parameters, i.e., using pointer parameters. For example: CHL_DsCreateHT(**pHTableOut, nEstEntries, keyType, valType, fValInHeapMem). This function creates a hashtable and returns a pointer to the hashtable object in the first parameter pHTableOut.
  • Each module has its own header file. API users only need to include the used module's header file. Earlier, all exported functions and data structures were specified within a single header file.
  • Usage of Microsoft's SAL2(Source Annotation Language) to annotate the function parameters. This enables better static code checking and also conveys the meaning of the parameters better.
  • The data structures - hashtable, linkedlist and queue - all have identical support for storage and retrieval of values (and keys).
  • More test code was written to test the new changes and older tests provided the necessary regressions.
  • Writing documentation for the full API. This is still a work in progress.
The code for CHelpLib along with the Test code and documentation can be found at Github: https://github.com/shishir993/CHelpLib. Future work for this particular library will see additions in the area of data structures, algorithms and some stuff around Windows process access APIs.

September 7, 2014

Learnings From A Diffing Tool

TL;DR - Source code and screenshots.

Motivation

This post is about the things I learned in the course of developing a folder diffing tool I wrote recently, as a pastime project. Couple of weeks back I was wondering if there was any tool that I could use to diff two folders to find duplicate files and delete those from either folder. I wanted to see if I had any duplicates in the files that I copied from my friend. So, I started thinking about a diffing tool which offers these capabilities. I could think of BeyondCompare and few other diffing tools but off the top of my head, couldn't think of any tool that could diff folders and help me delete the duplicates from either of the folders.

I said to myself that this is the perfect opportunity for a project! So, I went home that day and immediately listed down my requirements for the diffing tool. I decided to call it 'FDiffDelete' - Folder Diff and Delete. The initial set of requirements that I came up with was:

  1. Compare two folders(a left folder and a right folder), highlight the common/duplicate files(name and size match - later, use hash).
  2. Give choice to user to delete the common/duplicate files from any folder.
  3. Ver1.0: Only single level files in a folder. Later, recursive compare.
  4. UI stuff: Has a dialog box. The box is split into two. Each has a text area to specify the folder path and a list view to display the file list in the specified folder(s). There is also a delete button in each half of the dialog box that enables the user to delete selected files(or all duplicate files) from either of the two folders.
I later realized that I should compare files based on their Last Modified Date as well, so I added that to the requirements list.
  • Duplicate files determined based on name, size, last-modified-date (later, or by using the file hash(SHA1)).

Nitty gritty design details

With the requirements set, I started designing the tool. I needed a data structure to actually hold information about the files in a folder and to also allow comparisons between files from the two folders. The very first thing that came to mind was a hash table to store file information of all files in the folder.

Pros and cons of hash table:

  • + Fast inserts and lookups.
  • + Pretty straight-forward implementation in C. There is no need for complicated stuff like rebalancing in case of a binary tree.
  • + I already had a hash table implementation in my CHelpLib project :-) .

  • - Not very space efficient when size of hash table is much larger than the actual number of items in the table, i.e., when it is sparse.
  • - Iterating through the hash table wastes CPU cycles when it is sparse. You have to traverse all slots in the table to find all that have valid entries.
  • - Efficiency of a hash table is only as good as it's hash function. A bad one will introduce too many key conflicts and will lead to bad performance.

One other data structure to think was a tree. This will offer average insert and lookup times. It is more space efficient compared to a hash table. However, there is also the implementation complexity due to need for re-balancing a binary tree on inserts and also I did not have a binary-tree implementation in C. So I finally decided that the hash table is the way to go. So, the hash table would be (key, value) = (filename, fileinfo-struct). This hash table would be associated with a folder object(DIRINFO) to hold all files within the folder.

The folder info(DIRINFO) and file info(FILEINFO) structures used in the code:

// Structure to hold the files that have same name within
// the same directory tree. This is required because the hashtable
// in DIRINFO uses filename as key, which means there will be name
// conflicts.
typedef struct _dupWithin
{
    int nCurFiles;
    int nCurSize;
    PFILEINFO *apFiles;
}DUPFILES_WITHIN, *PDUPFILES_WITHIN;

typedef struct _DirectoryInfo
{
    WCHAR pszPath[MAX_PATH];
    int nDirs;
    int nFiles;

    // Was hash comapre used when this DIRINFO was built?
    BOOL fHashCompare;

    // Use a hashtable to store file list.
    // Key is the filename, value is a FILEINFO structure - if hash compare is turned OFF
    // Key is hash string, value is a PCHL_LLIST that is the
    // linked list of files with the same hash string - if hash compare is turned ON
    CHL_HTABLE *phtFiles;

    // List of FILEINFO of files that have the same name in 
    // the same dir tree. - if hash compare is turned OFF
    DUPFILES_WITHIN stDupFilesInTree;

}DIRINFO, *PDIRINFO;

// Structure to hold information about a file
typedef struct _FileInfo
{
    BOOL fIsDirectory;
    BOOL fAccessDenied;

    // This structure must know about the duplicacy of a file
    // because otherwise the directory must hold an additional
    // list of duplicate files.
    BYTE bDupInfo;
    
    LARGE_INTEGER llFilesize;
    BYTE abHash[HASHLEN_SHA1];
    SYSTEMTIME stModifiedTime;
    FILETIME ftModifiedTime;

    WCHAR szPath[MAX_PATH];
    WCHAR szFilename[MAX_PATH];

}FILEINFO, *PFILEINFO;

And so, I started to write the code and reached a good first version which was able to find duplicates based on the file's name, size and last-modified-date. I was even able to use it to find duplicates and delete them. Great! The tool served it's initial purpose. Now I wanted to implement recursive diff, i.e., diff a full folder tree and not just one level. Traversing the folder tree is easy, a BFS using a queue is quite trivial once you have a queue data structure. I did not have a queue implementation but I did have a linked-list implementation. I just added the Queue implementation to my CHelpLib project using linked list as the underlying data structure. Now I had to tackle the problem of how to store the files' information when recursively traversing the folder tree. Two options came to my mind:

  1. Use a tree of folder-info structs to hold information of all files in each folder in the tree starting from the specified folder as the root. This brings the complication of finding duplicate files within two trees. I vaguely remembered a sub-graph compare problem from my algorithms class. But wait, this wasn't even a sub-graph compare problem. It was more trivial than that - how the heck do I search for a file by name among the two folders with an algorithm better than O(n*n). Remember that a duplicate file could be in any folder in the tree rooted at the specified folder.
  2. Use only one hash table, as described earlier, to store the files' information from all folders in the tree. This offers the same fast inserts and is trivial to find duplicate files since the file name is a key.
I chose to use the second option of using hash table to store file info. So, files from all folders in the tree will be in a single hash table. Started writing the code and soon realized another issue to tackle - there could be files with same name in one folder tree. This was a common occurrence, for example, music files that are named as "Track 1", "Track 2". As we all know, hash table cannot handle the duplicate keys, it will just overwrite or fail to insert when a key already exists, depending upon the implementation. So, I had come to up with a way to store duplicate file names within a folder tree. I chose to put the duplicate files in a separate array of file-information structs. This worked out well. Yes it is slow, O(1) insert and O(n) worst case lookup but I do not expect too many duplicate file names in the folder tree as the most common scenario. This worked well and it was pretty fast too. I was able to diff the System32 folder with ~2k files in under 2 seconds on my Core i7 laptop.

Can I Haz Moar Features?

Next feature to add was file comparison using the hash of the file content(file-digest). I decided to use SHA1 as my hashing function since MD5 has more probability of hash collisions. Although, a SHA1 hash collision has also been found and I should probably use SHA2? I wanted to balance speed and collision-resistance. SHA1 is slightly faster than SHA2, however small the difference. I know, I know, I didn't put too much effort into thinking out this part. I can change the hash function easily enough. Anyway, coming back to the feature. In order to find duplicate files using their hashes, the file names no longer matter; only the file digest matters. The file name cannot be used as a key to the hash table in order to find duplicate files. The key to the hash table has to be 160bit(20byte) hash value of a file represented as a string. This brings another issue - files within same hash(duplicate files) within the same folder tree. I solved this by having a list of file-info structs as the value of the hash table entry. So, the hash table of the hash-comparison feature was (key, value) = (hash-value-as-string, list-of-file-info-structs).

By this time, the code had gotten quite complicated mainly due to the two very different ways of using the hash table to store files' information. One was using the file name as key and the other used the file's hash-value. So I decided to separate the folder traversal for the usual comparison and hash comparison features. This made is much easier to maintain and read the code.

Lessons learned

  • Data structures used can make or break a program. They can either make a program fast or painfully slow, a memory hogger or space efficient, easy to maintain vs. PITA spaghetti code. Choose wisely.
  • Start with a initial set of requirements and design accordingly. As you add more requirements, remember to go back to the design board since you may have to rethink the whole design(worst-case) when new requirements are added.
  • Object oriented concepts are your friend in making any challenging problem easy to solve and implement in code. Encapsulation and abstraction are very powerful and quite sufficient. You do not necessarily have to use polymorphism and inheritance all the time.

Source code is on github at: https://github.com/shishir993/fdiffdelete. Built using Microsoft VS2010 Professional and Windows SDK 8.100.26837. Dependent on my other C library CHelpLib.

Some screenshots of the tool at work:

January 21, 2014

Determining Integer Overflow

This topic was running through my mind and I was wondering what the easiest way would be to detect overflow and underflow of integers. I searched on the internet and found some answers but all were not quite simple. Then it dawned on me that the CPU has an Overflow flag as part of the EFLAGS register! Consulted the Intel SW Developers manual and found that I was right. There are instructions that test this register - the JO (Jump if overflow) for signed integers and JC (Jump if carry) for unsigned integers. So, we perform an addition and then immediately check the status of the flags using the JO/JC instructions. The branch instruction targets can then return the correct value if this logic is enclosed within a function that tests this overflow condition. I have added the two small functions that test for overflow in INT and UINT to my CHelpLib git repository. I have included one of the functions below. Given two integers, this function returns TRUE if an addition causes overflow. It basically uses assembly instructions to perform the addition and then uses jo instruction to jump to the correct location that returns the TRUE or FALSE value.

BOOL Chl_fIsOverflowINT(int a, int b)
{
    __asm
    {
        mov eax, dword ptr [a]
        mov ecx, dword ptr [b]
        add eax, ecx
        jo ret_overflow
    }

    return FALSE;
    
ret_overflow:
    return TRUE;
}

October 4, 2013

Timing Your Code - Inside and Outside a Debugger

John Bentley talks about timing software code in his book Programming Pearls. I was recently reading this and thought I'd time my hashtable implementation(source). Windows has two APIs that can help in doing this: QueryPerformanceFrequency and QueryPerformanceCounter. There are other ways to measure time but I chose these for their high resolution. These APIs provide values from the high-performance counter in the system, if one is present. This counter is like a variable that keeps incrementing many many times per second. The frequency of increments depends on the specific system you have. MSDN says that sometimes this can be the cycle rate of the processor's clock.

QueryPerformanceFrequency returns this frequency value and this value does not change during the system's up-time operation. My system, for example, has a counter that ticks 2143623 times per second and this translates to a resolution of 466.499940 nanoseconds.

QueryPerformanceCounter returns the value of the counter when it is called. By calling this immediately before and after a block of code, we can calculate the number of increments that took place while the code was running and then convert this to a time value. Both the APIs take a pointer to a LARGE_INTEGER variable. If we look in WinNT.h, we see that this is an 8-byte structure with members for accessing each of the 4-byte values. 8-bytes gives plenty of bits to hold the counter value.

Coming to the timing of the hashtable implementation. I timed only the insertion operation using a DWORD type for both key and value. Ran the tests with multiple number of entries each time: 50000, 100000, 700000, 8388608(1<<23), 16777216(1<<24). I initially had a count of 33554432(1<<25) and this run failed because of an out-of-memory condition! Each process by default is limited to 2GB of main memory space. Part of the scaffolding code I used for this is here:

LARGE_INTEGER freq = {0};
LARGE_INTEGER counterStart = {0};
LARGE_INTEGER counterEnd = {0};

LONGLONG elapsedCounts = 0;
double elapsedTime[10] = {0};

int numRuns = 0;
int sizes[MAX_RUNS] = { 50000, 100000, 700000, 1<<23, 1<<24 };

DWORD dwError = 0;
BOOL testSuccess[MAX_RUNS] = {TRUE};

// This retrieves the counts per second
if(!QueryPerformanceFrequency(&freq))
{
    dwError = GetLastError();
    wprintf(L"testHashtable(): QueryPerformanceFrequency() failed %d\n", dwError);
    return;
}

while(numRuns < MAX_RUNS)
{
    wprintf(L"Beginning run %d\n", numRuns);

    // Begin counter
    if(!QueryPerformanceCounter(&counterStart))
    {
        dwError = GetLastError();
        wprintf(L"testHashtable(): QueryPerformanceCounter() failed %d\n", dwError);
        return;
    }

    //
    // Code to test
    //
    testSuccess[numRuns] = testHashtable(HT_KEY_DWORD, HT_VAL_DWORD, 
                                         sizes[numRuns], FALSE);

    // End counter
    if(!QueryPerformanceCounter(&counterEnd))
    {
        dwError = GetLastError();
        wprintf(L"testHashtable(): QueryPerformanceCounter() 
                  failed %d\n", dwError);
        return;
    }

    // Get the elapsed time
    elapsedCounts = counterEnd.QuadPart - counterStart.QuadPart;
    elapsedTime[numRuns] = (double)(elapsedCounts / (double)freq.QuadPart);
    ++numRuns;
}

wprintf(L"Performance counter ticks %I64u times per second\n", freq.QuadPart);
wprintf(L"Resolution is %lf nanoseconds\n", (1.0/(double)freq.QuadPart)*1e9);

wprintf(L"%16s %13s %19s %s\n-----------------------------------------------\n",
        L"RunSize", L"TimeSeconds", L"TimeMicro", L"Result");

for(numRuns = 0; numRuns < MAX_RUNS; ++numRuns)
{
    wprintf(L"%16d %5.8lf %16.3lf %s\n", sizes[numRuns], elapsedTime[numRuns], 
                                         elapsedTime[numRuns] * 1e6, 
                                         testSuccess[numRuns]?L"PASSED":L"FAILED");
}

This code gave the following output:

--[ Hashtable insertion operation ]--

** Release mode, running inside Visual Studio **
         RunSize   TimeSeconds           TimeMicro Result
---------------------------------------------------------------
           50000 3.25054825      3250548.254 PASSED
          100000 6.17252521      6172525.206 PASSED
          700000 45.90315601     45903156.012 PASSED
         8388608 648.03144909    648031449.093 PASSED
        16777216 1480.01800177   1480018001.766 PASSED
---------------------------------------------------------------

** Release mode, running outside in a command window **
         RunSize   TimeSeconds     TimeMicro Result
---------------------------------------------------------------
           50000 0.07000345        70003.447 PASSED
          100000 0.12546702       125467.025 PASSED
          700000 0.98070789       980707.895 PASSED
         8388608 11.25297219     11252972.188 PASSED
        16777216 19.48300751     19483007.506 PASSED

As you see from the results above, the interesting learning is the amount of increase in processing time when running under a debugger. In these tests, running under a debugger was orders of magnitude slower than otherwise. In order to see whether this really was the case with even simple code, I timed the execution of a system API - GetCurrentThread() using the same technique. In order to get consistent times I executed the system API multiple times in a for loop. Here are the results. We see the same increase in execution time. The RunSize is the number of times GetCurrentThread() was executed in TimeSeconds seconds. Do note that this API took only ~366 microseconds to execute 100,000 times on my Core i7 powered laptop. That is blazing fast!

--[ Multiple Calls to GetCurrentThread() ]--

** Release mode, inside Visual Studio **
         RunSize   TimeSeconds TimeMicro
---------------------------------------------------------
             500 0.00000746            7.464
           50000 0.00062698          626.976
          100000 0.00125349         1253.485

** Release mode, running outside in a command window **
         RunSize   TimeSeconds TimeMicro
---------------------------------------------------------
             500 0.00000187            1.866
           50000 0.00016747          167.473
          100000 0.00033635          336.346

This brings us to another interesting idea that is probably already being used. This technique can be used by a program to check whether it is running under a debugger or not. I recall reading somewhere that using IsDebuggerPresent() is not a fool-proof way of determining this. So timing checks may well be better. However, we must account for the fact that processing times vary widely depending on the system hardware and system load while running. What can be done is draw up a table with a list of expected processing times for a particular operation on various types of hardware configurations and for various system loads. Then when our program is running, we time the same operation and compare it against the list we have. The program must be able to determine the hardware configuration(CPUID instruction comes to mind) and the system load(can do this by querying Windows - #processes, memory used,...) and use this information to make a good comparison.

September 17, 2013

Windows Debugging API - Part 1

I recently started exploring the Debugging APIs available in Microsoft Windows. Using these APIs, one can write their own software to write a debugger, process tracer/analyzer and what not. My goal is to write a full-fledged debugger using only Win32 APIs by the end of this learning stage. In today's post, I will explain what I have learned so far - some of the Debugging APIs themselves and a sample implementation of a so called process tracer, for lack of a better name, which uses those APIs.

The debugging APIs available in the Windows OS have been remained largely unchanged for many years now. Articles written way back in the 90s and 2000s are relevant even today. Scroll down to the end of this post to find some references that I have used so far. Before going in to the details of the APIs themselves, I will enumerate the tasks that a debugger should be able to perform in order to satisfy the user's requirements.

  1. First and foremost, the debugger must enable the user to fully control the execution of the process to be debugged, called the target process from here on. This means that the user must be able to start and stop execution of the target by setting breakpoints, single stepping, break-all threads immediately and so on.
  2. The user must also be able to control the data that the target process uses - register contents(even the EIP register to alter control flow), stack and heap contents, global variables and so on.
  3. Provide at least a disassembly of the code that the target process is executing whenever the user wishes to examine it.
  4. It must provide all details about the target process during its execution - threads, child processes, register and memory contents, loaded modules(DLLs), address in memory of the modules, current stack layout and so on.
The Windows debugging APIs consists of:
  • WaitForDebugEvent: The caller is blocked for the amount of time indicated or until a debug event occurs in the target process. When this function returns TRUE, a debugging event has occured and at this point the target process has been suspended completely. The debugger(caller) is free to process the debug event and update its own UI and do other stuff.
  • ContinueDebugEvent: Once the debugger(caller) has processed the debug event, it has to call this function in order to let the target process continue execution.
  • DebugActiveProcess: This enables the debugger to attach to an already running process in the system.
  • DebugActiveProcessStop: DebugActiveProcess() function's counterpart. This is used to detach the debugger from the target process. Once this is done, the target process is no longer under the control of the debugger and the debugger will not receive any debug events.

There are other debugging APIs which I have not used so far, so I will explain them in a future post. They are: DebugSetProcessKillOnExit(), DebugBreakProcess() and CheckRemoteDebuggerPresent(). Important APIs that are not specific to debugging but are very necessary for accomplishing the tasks of a debugger:

  • CreateProcess(): This is used to create the target process as a new process with the DEBUG_PROCESS or the DEBUG_ONLY_THIS_PROCESS flag which enables the calling thread in the debugger to receive debug events from this target process.
  • SuspendThread() and ResumeThread(): Suspend and resume a thread in the target process.
  • TerminateThread() and TerminateProcess(): To terminate a thread or the target process itself.
  • ReadProcessMemory() and WriteProcessMemory(): To read and write to the memory contents of the target process. These are essential because there is no direct way to access the target process's memory like using a pointer in the debugger. This is because the target process, obviously, is created in a different virtual address space than the debugger.

Before going into the details of the APIs, I will give a brief of the various events that a debugger will receive when it is attached to a target process. A DEBUG_EVENT structure is sent along with each debug event. This event has the target PID, thread ID where this debug event occurred and an associated structure inside that is filled with information related to the corresponding event. These structures contain very useful information about the target process. The debug events sent are:

  • CREATE_PROCESS_DEBUG_EVENT: This event is the very first event sent to the debugger when it creates a new target process or attaches to an existing process. The associated structure is CREATE_PROCESS_DEBUG_INFO. Important fields are:
    • hProcess, hThread: handle to target process and the first thread.
    • hFile: Handle to the memory area where the executable binary(of the target process) is mapped into memory. Use this to read information about the target binary for may be disassembly generation purposes. You must close this handle once you are finished using it.
    • lpBaseOfImage: The starting address of the executable image mapped into memory. For PE binaries, you will see that this points to the DOS header with "MZ" at the start.
  • CREATE_THREAD_DEBUG_EVENT: Event sent whenever a thread is created in the target process. The associated structure is CREATE_THREAD_DEBUG_INFO. The hThread member in this gives a handle to the thread.
  • LOAD_DLL_DEBUG_EVENT: This is sent when a DLL is loaded into the target process. hFile is the handle to the loaded DLL and can be used to obtain the image name of the DLL and must be closed after use. lpBaseOfDll gives the address at which the DLL is loaded in the target process's address space.
  • OUTPUT_DEBUG_STRING_EVENT: This is a special event that is sent when the target process a call to the OutputDebugString() function. This is used especially for the target process to be able to communicate to the debugger. The associated OUTPUT_DEBUG_STRING_INFO structure contains information needed to retrieve the string value passed to the OutputDebugString() function. lpDebugStringData gives the starting address of the string and nDebugStringLength gives the number of characters in the string. fUnicode specifies whether the string is a wide-char string or not. ReadProcessMemory() must be used to actually read the string value from the target process's address space. Keep in mind that if it is a unicode string then you will have to read length*sizeof(WCHAR) bytes in order to read the full string.
  • EXIT_PROCESS_DEBUG_EVENT and EXIT_THREAD_DEBUG_EVENT: Counterparts of the respective create events. Keep in mind that you will have to remember the PID of the target process so that when you receive the EXIT_PROCESS_DEBUG_EVENT with this PID, you will know that the target process has exited.
  • UNLOAD_DLL_DEBUG_EVENT: Sent when a DLL is unloaded in the target process. The only member in the associated UNLOAD_DLL_DEBUG_INFO structure is lpBaseOfDll which is the same as before. See that there is no information about which DLL is being unloaded. The debugger has to remember this information by mapping the base of DLL to the DLL name when it gets the LOAD_DLL_DEBUG_EVENT and can use this information when it receives the unload DLL event.
  • EXCEPTION_DEBUG_EVENT:Sent to the debugger whenever an exception occurs in the target process. The structure EXCEPTION_DEBUG_INFO has information about the exception itself. First chance exception means the exception has not yet been sent to the target process yet. The debugger is the first one to receive and can make use of it before it reaches the target process. This is useful when the debugger sets breakpoints which result in the breakpoint exception. In this case, the debugger handles the breakpoint exception and continues the target process. The target won't even know that an exception occurred in this case. If the debugger cannot handle the exception then it is passed onto the target process. The exception debug information structure also contains the exception code which indicates the kind of exception that occurred. There is a lot more detail to be written regarding the exception debug event and I will reserve that for the second part of this post.

Now, there are two starting points for debugging a target process - first is to create the new process as a child of the debugger using the CreateProcess() API and second, attach to a process that is already running using the DebugActiveProcess() API. Likewise, there are two ways to end a debug session - terminate the target using TerminateProcess() API or simply detach from the target using DebugActiveProcessStop() API and let it continue executing. Going into the specifics now...

Creating a new target process
You must specify the DEBUG_PROCESS or the DEBUG_ONLY_THIS_PROCESS flag while creating the new target process so that the debugger has full access to the target process. When this function returns, you will get the PID of the newly created target process and a handle to its main thread and the target process itself. It is better to close these handles now since we get these again later when the debugger receives the CREATE_PROCESS_DEBUG_EVENT. Once you the create the target process the following set of events happen from the debugger's perspective:

Attaching to an active target process
When DebugActiveProcess() function is called, the target process is first suspended by Windows. Then the following events are sent to the debugger: CREATE_PROCESS_DEBUG_EVENT and CREATE_THREAD_DEBUG_EVENT for the main process and thread, CREATE_THREAD_DEBUG_EVENT for all other threads currently in the target process and LOAD_DLL_DEBUG_EVENT for all loaded DLLs. Windows sends one EXCEPTION_DEBUG_EVENT with exception code 0x80000003(breakpoint) before resuming execution of the target process. So once the debugger continues this exception, the target process is resumed and now any debug event may be sent to the debugger as and when they are generated.

Receiving debug events
Debug events are sent to the debugger, specifically the thread within the debugger that called either CreateProcess() or DebugActiveProcess(), once it is attached to the target process. In order receive these events, the debugger must call the WaitForDebugEvent() API. This blocks the calling thread until a debug event is sent or the specified time runs out. If a debug event is sent within the specified time out, then a DEBUG_EVENT structure is sent along as described earlier. Calling ContinueDebugEvent() resumes execution of the target process.

Closing a debug session
Similar to starting a debugging session, there are two ways to end it.
First is to terminate the target process and the second is to simply detach the debugger from the target process and let it continue execution. Termination of a process is via the TerminateProcess() API. Many people recommend not to use this because it immediately terminates the target process without invoking any cleanup code in the target. However, if the user wants to stop debugging, the target process must be terminated this way because giving it a chance to cleanup first is the total opposite of wanting to terminate the process. Think about it - if you are debugging a malware you would not want to give it a chance to cleanup, would you?

Coming back to TerminateProcess() now. There is one thing you should absolutely remember not to do: do not exit the debug thread as soon as you call TerminateProcess. Doing so keeps the target process in an infinite wait state and it cannot even be killed. See the appendix for an explanation. Once TerminateProcess() has been called, the target process is suspended and Windows sends UNLOAD_DLL_DEBUG_EVENT for all loaded DLLs, EXIT_THREAD_DEBUG_EVENT for all threads and finally a EXIT_PROCESS_DEBUG_EVENT. Once all these events are processed, Windows calls CloseHandle and other clean-up code for any resources held by the target process and then proceeds to remove the process from the system.

Second, detaching from the target process is by calling the DebugActiveProcessStop() API. This simply causes the debugger to stop receiving any further debug events and closes all the debugger's open handles to the target process. From now on, the target process continues executing without an attached debugger. Any exception that occurs is handled by Windows the same way as for any other process.

Using these APIs
I wrote a small GUI program called ProcessTracer that receives debug events and displays them to the user. Source code for this can be found in Github here: ProcessTracer git repo.

Appendix

Terminating the target process
When TerminateProcess() is called, the target process is suspended just like when a debug event occurs. Windows then sends multiple UNLOAD_DLL_DEBUG_EVENTs and EXIT_THREAD_DEBUG_EVENTs followed by a final EXIT_PROCESS_DEBUG_EVENT. All this happens without the target process being resumed at all. So if the debugger does not process these events by calling ContinueDebugEvent() then the target process is in a wait-forever state within a kernel thread. Since this is in a kernel mode wait state it cannot be killed. See this article for an explanation of un-killable processes.

July 18, 2013

Modifying a Binary File?

In this post I will be talking about how I cracked one of the CTF challenges during the final semester in my university. The CTF competition was part of the Network Security course and was held for two days over a weekend in spring. Those two days were one of the most exciting times I have spent in front of a computer. The adrenaline rush of solving problems and getting points awarded is something that only the participants will know about.

So, coming to the challenge I'm talking about. Given were: a program binary that provides encryption/decryption services, an encrypted message and the key that was used to encrypt the message. The challenge was to decrypt the encrypted message. But.... Decryption capability in the program binary was disabled! The program took the following command line arguments "Usage: ./crypt INPUT-FILE OUTPUT-FILE KEY (DECRYPT|ENCRYPT)". So if we mentioned "DECRYPT" it would output "NO DECRYPT ENABLED !!!". Okay, so I opened up the GNU debugger gdb. Started stepping through code to see where the command line arguments were processed. I observed that the function names were still preserved, although they were mangled because the C++ compiler implements name mangling. There were two functions, '_Z7decryptSsSs' and '_Z7encryptSsSs' apart from the 'main' function. Stepping one instruction at a time through the main function I found the code where the command line argument was being checked for DECRYPT/ENCRYPT. Here it is:

Observe that the code is checking only whether the fifth argument's first character is 'D' or not. D is hex 44h. So if it is 'D' then register al is set and then the stack variable at [ebp-0x239] is also copied the value of al. The code then checks whether this value is zero, meaning 'E' was the first character of the fifth parameter, and then jumps based on this comparison. If the jump is not taken then the code calls std::cout to print the "NO DECRYPT ENABLED !!!" message and exits. When "ENCRYPT" was passed, jump was taken and the stack variable [ebp-0x236] was being used further down in the code when the decision was made to call either _Z7encryptSsSs() or _Z7decryptSsSs(). So the basic steps the code was taking is shown in this pseudo-code:

main()
{
  // x = ebp-0x239
  al = (argv[4][1] == 'D')? 1 : 0;
  x = al;
  if(x == 0) goto do_not_exit;
  std::cout << "NO DECRYPT ENABLED !!!\n";
  exit_program

  do_not_exit:
  read input file
  read key file
  open output file
  if(x == 1)
    call _Z7decryptSsSs()
  else
    call _Z7encryptSsSs()
  exit_program
}

As you can see there are two places where the control flow changes. Two ideas came to my mind on that day.

  1. Control the stack variable 'x' so that the correct branches are taken even though "DECRYPT" is passed.
  2. Change the binary file so that the call to the encrypt() function gets replaced with a call to the decrypt() function.
I chose the first option since it was easier. However I didn't quite succeed because the [ebp-0x239] was being over-written when some library functions were called. GDB has the functionality that enables you to monitor a memory location and break whenever a read/write operation is performed from/to that memory location. I tried using this but got tangled up in multiple places where this memory area was accessed. It was taking too much time. I then thought of the second option. For changing the binary file, all I had to do was to modify the target of the call instruction to point to the decrypt function instead of the encrypt function. The intel call instruction takes the target as an offset which means the call instruction simply does this to call a function: EIP = EIP+offset. See the disassembly below:

The call instruction at 0x080494ee is "e3 e1 f8 ff ff". Call opcode is 0xe3 and the code_offset is 0xfffff8e1. All we have to do is replace the immediate value 0xfffff8e1 by the new offset 0xfffffa1b. This will be the new offset that the call instruction will use. Simple enough right? Well... sort of. This binary was a 32bit ELF binary. We can use "objdump -h" to find out the offset of important sections of a binary file. What we are interested in is the offset of the .text section. The output of "objdump -h" (only .text information shown here):

The text section starts at offset 0xd20 in the binary file and its virtual address is 0x08048d20. The call instruction is at 0x08484ee. So, 0x08494ee - 0x08048d20 = 0x7ce. This is the distance between in the start of text section and the call to encryption routine instruction. Therefore, the call instruction is at offset 0xd20 + 0x7ce = 0x14ee in the binary file. The call instruction format is "opcode(1byte) code_offset(4bytes)". So we have to replace the integer(4bytes) at offset 0x14ee+1 with 0xfffffa1b. I wrote a program to do this by memory-mapping the binary and replacing the code_offset. Of course, we can simple open the file, seek to 0x14ee+1 and write an integer there but the reason I used memory mapping is because I wanted to see if I was modifying the correct place in the binary file and memory-mapping enables you to do this easily since you can view the file contents in the memory window of a debugger. Small snippet of the code to make the modification:

WCHAR *szFile = L"C:\\Users\\Shishir\\CTF\\kes\\crypt";
WCHAR *szOutFile = L"C:\\Users\\Shishir\\CTF\\kes\\crypt_new";
HANDLE hFile = NULL, hFileObj = NULL, hFileView = NULL;

DWORD dwFileSize = 0;

wprintf_s(L"Using input file: %s\n", szFile);

if( ! fOpenAndMapFile(szFile, &hFile, &hFileObj, 
        &hFileView, &dwFileSize) )
{
  wprintf_s(L"Error opening input file\n");
  return 1;
}

unsigned char *fptr = (unsigned char*)hFileView;

// Seek to offset where the call instruction's code_offset is
fptr += 0x14ee + 1;
    
unsigned int *iptr = (unsigned int*)fptr;
int old_data = *iptr;
int new_data = 0xfffffa1b;
*iptr = new_data;

Once this was done, I took the new modified binary and did an objdump of it and the call instruction at 0x08494ee was pointing to the decryption routine _Z7decryptSsSs() now!! Note the virtual address, 0x080494ee, is where the call instruction is in the following modified code and in the previous screenshot.

Executed the program by giving "ENCRYPT" as the fifth argument and got the decrypted message in the output file! Now, this was possible because the decryption and encryption routines both had the same function signatures - same arguments especially - so the code that setup arguments on the stack before the call to _Z7encryptSsSs() did not have to be changed.

Well, after submitting the flag and getting rewarded handsomely with points, I spoke to a fellow student who did it in a different, more easier, way. GDB allows you to control the contents of any register during debugging. So all you have to do is to make sure you break the program before each of the branching decision points and change the value of EIP register so that the correct branch is taken even though you specify "DECRYPT" at the command line. Anyway, it was fun playing around with gdb, objdump and the binary file even though my method was more complicated!

This actually brings us to the topic of packers. A packer, in the context of computers and security, is a program that can compress and/or encrypt a binary file that is provided as input. This is how many of today's software programs are distributed in order to protect Intellectual Property. The compressed/encrypted binary is the one that is distributed to consumers. This supposedly prevents competitors and crackers from reverse engineering the binary and stealing the code implemented by a company. You might ask how the OS manages to run these 'packed' programs. When a binary file is packed, the unpacker is included as part of the final output of the packer. So executing the output binary file actually first invokes the unpacker which has the logic and information to unpack - decompress and/or decrypt - the rest of the binary and then execute the unpacked program. The unpacked program is usually run by creating a child process by the unpacker. UPX is a popular open-source packer.

Even with packed a binary, we can still read the original code although it is a little more difficult. This difficulty arises because many packers are clever enough to not unpack everything at once. Unpacking may be done 'on-demand' and in-memory. So the challenge now is to determine when the unpacking process is finished and at this point we can dump the process's memory to disk for later analysis. The dump will hopefully have the whole binary in unpacked form to facilitate disassembly. This is why one must never ever depend on the fact that the source code will never be leaked. Remember, security through obscurity never works. The topic of packers and techniques for anti-packing and vice-versa is very interesting. I will write about it may be in a later post. That's it for now!