cover image for post 'Practical Reverse Engineering Solutions – Page 35 (Part VI)'

Practical Reverse Engineering Solutions – Page 35 (Part VI)

my go at KeInitializeQueue, KeReadyThread, KiInitializeTSS and RtlValidateUnicodeString

This blog post presents my solution to KeInitializeQueue, KeReadyThread, KiInitializeTSS and RtlValidateUnicodeString of exercise 5 on page 35 from the book Practical Reverse Engineering by Bruce Dang, Alexandre Gazet and Elias Bachaalany (ISBN: 1118787315). The book is my first contact with reverse engineering, so take my statements with a grain of salt. All code snippets are on GitHub. For an overview of my solutions consult this progress page.

Problem Statement

Decompile the following kernel routines in Windows:

  • KeInitializeDpc
  • KeInitializeApc
  • ObFastDereferenceObject (and explain its calling convention)
  • KeInitializeQueue
  • KxWaitForLockChainValid
  • KeReadyThread
  • KiInitializeTSS
  • RtlValidateUnicodeString

Approach

I’m using a virtual Vista Ultimate 32bit with the kernel debugger in WinDbg as part of the Windows 7 SDK. I use the great LiveKd from Microsoft Sysinternals to access the kernel debugger on the live system. The syntax of the kernel routines are from Windows DevCenter.

Solutions

(see this blog post for my solutions to KeInitializeDpc, KeInitializeApc, and ObFastDereferenceObject).

► KeInitializeQueue

Syntax

The syntax according to Dev Center is:

VOID KeInitializeQueue(
  _Out_  PRKQUEUE Queue,
  _In_   ULONG Count
);

Structures

The parameter PRKQUEUE stands for the *restricted_pointer to a structure of type _KQUEUE, which has the following members:

ntdll!_KQUEUE
   +0x000 Header           : _DISPATCHER_HEADER
   +0x010 EntryListHead    : _LIST_ENTRY
   +0x018 CurrentCount     : Uint4B
   +0x01c MaximumCount     : Uint4B
   +0x020 ThreadListHead   : _LIST_ENTRY

or in C++:

typedef struct _KQUEUE {
    DISPATCHER_HEADER Header;
    LIST_ENTRY EntryListHead;
    ULONG CurrentCount;
    ULONG MaximumCount;
    LIST_ENTRY ThreadListHead;
} KQUEUE, *PKQUEUE, *RESTRICTED_POINTER PRKQUEUE;

The _DISPATCHER_HEADER has the following members:

ntdll!_DISPATCHER_HEADER
   +0x000 Type             : UChar
   +0x001 Abandoned        : UChar
   +0x001 Absolute         : UChar
   +0x001 NpxIrql          : UChar
   +0x001 Signalling       : UChar
   +0x002 Size             : UChar
   +0x002 Hand             : UChar
   +0x003 Inserted         : UChar
   +0x003 DebugActive      : UChar
   +0x003 DpcActive        : UChar
   +0x000 Lock             : Int4B
   +0x004 SignalState      : Int4B
   +0x008 WaitListHead     : _LIST_ENTRY

Many of those fields overlap, so the C++ version looks quite complicated:

typedef struct _DISPATCHER_HEADER {
    union {
        DWORD Lock;
        struct {
            UCHAR Type;
            union {
                UCHAR Abandoned;
                UCHAR Absolute;
                UCHAR NpxIrql;
                UCHAR Signalling;
            }
            union {
                UCHAR Size;
                UCHAR Hand;
            }
            union {
                UCHAR Inserted;
                UCHAR DebugActive;
                UCHAR DpcActive;
            }
        }
    }
    DWORD SignalState;
    DWORD WaitListHead;
} DISPATCHER_HEADER, *PDISPATCHER_HEADER;

The _LIST_ENTRY is used as pointer in a double-linked list:

ntdll!_LIST_ENTRY
   +0x000 Flink            : Ptr32 _LIST_ENTRY
   +0x004 Blink            : Ptr32 _LIST_ENTRY

or in C++:

typedef struct _LIST_ENTRY {
  struct _LIST_ENTRY  *Flink;
  struct _LIST_ENTRY  *Blink;
} LIST_ENTRY, *PLIST_ENTRY;

Disassembly

Here’s the unassembled version of KeInitializeQueue on a Vista 32bit environment:

nt!KeInitializeQueue:
81a3c346 8bff            mov     edi,edi
81a3c348 55              push    ebp
81a3c349 8bec            mov     ebp,esp
81a3c34b 8b4508          mov     eax,dword ptr [ebp+8]
81a3c34e c60004          mov     byte ptr [eax],4
81a3c351 33d2            xor     edx,edx
81a3c353 885001          mov     byte ptr [eax+1],dl
81a3c356 c640020a        mov     byte ptr [eax+2],0Ah
81a3c35a 895004          mov     dword ptr [eax+4],edx
81a3c35d 8d4808          lea     ecx,[eax+8]
81a3c360 894904          mov     dword ptr [ecx+4],ecx
81a3c363 8909            mov     dword ptr [ecx],ecx
81a3c365 8d4810          lea     ecx,[eax+10h]
81a3c368 894904          mov     dword ptr [ecx+4],ecx
81a3c36b 8909            mov     dword ptr [ecx],ecx
81a3c36d 8d4820          lea     ecx,[eax+20h]
81a3c370 894904          mov     dword ptr [ecx+4],ecx
81a3c373 8909            mov     dword ptr [ecx],ecx
81a3c375 8b4d0c          mov     ecx,dword ptr [ebp+0Ch]
81a3c378 3bca            cmp     ecx,edx
81a3c37a 895018          mov     dword ptr [eax+18h],edx
81a3c37d 7509            jne     nt!KeInitializeQueue+0x42 (81a3c388)

nt!KeInitializeQueue+0x39:
81a3c37f 8a0dee49b581    mov     cl,byte ptr [nt!KeNumberProcessors (81b549ee)]
81a3c385 0fbec9          movsx   ecx,cl

nt!KeInitializeQueue+0x42:
81a3c388 89481c          mov     dword ptr [eax+1Ch],ecx
81a3c38b 5d              pop     ebp
81a3c38c c20800          ret     8

Calling Convention

The routine takes two parameters, both of which are passed on the stack as [ebp + 8] (= Queue) and [ebp + 0Ch] (= Count) respectively.

Pseudocode

The first part is:

mov     edi,edi                  
    push    ebp
    mov     ebp,esp
    mov     eax,dword ptr [ebp+8]      
    mov     byte ptr [eax],4           
    xor     edx,edx                    
    mov     byte ptr [eax+1],dl        
    mov     byte ptr [eax+2],0Ah       
    mov     dword ptr [eax+4],edx       

Line 2 is the hot patch point. Line 3 and 4 are the function prologue. The next lines set members of Queue:

Queue->Header.Type = 4
    Queue->Header.Abandoned = 0
    Queue->Header-Size = 10
    Queue->Header.SignalState = 0

Next we have:

lea     ecx,[eax+8]                 
    mov     dword ptr [ecx+4],ecx       
    mov     dword ptr [ecx],ecx         

which initializes the head of the doubly linked list WaitList:

Queue->WaitListHead.Blink = &Queue->WaitListHead
    Queue->WaitListHead.Flink = &Queue->WaitListHead

In the same fashion:

lea     ecx,[eax+10h]               
    mov     dword ptr [ecx+4],ecx 
    mov     dword ptr [ecx],ecx

initializes the head of the doubly linked list EntryList:

Queue->EntryListHead.Blink = &(Queue->EntryListHead)
    Queue->EntryListHead.Flink = &(Queue->EntryListHead)

and

lea     ecx,[eax+20h]               
    mov     dword ptr [ecx+4],ecx
    mov     dword ptr [ecx],ecx

initializes the head of the doubly linke list ThreadList:

Queue->ThreadListHead.Blink = &(Queue->ThreadListHead)
    Queue->ThreadListHead.Flink = &(Queue->ThreadListHead)

After that, the following code follows:

mov     ecx,dword ptr [ebp+0Ch] 
    cmp     ecx,edx
    mov     dword ptr [eax+18h],edx
    jne     nt!KeInitializeQueue+0x42 

nt!KeInitializeQueue+0x39:
    mov     cl,byte ptr [nt!KeNumberProcessors (81b549ee)]
    movsx   ecx,cl

nt!KeInitializeQueue+0x42:
    mov     dword ptr [eax+1Ch],ecx
    pop     ebp
    ret     8

which translates to

Queue->CurrentCount = 0
    IF Count == 0 THEN
        Queue->MaximumCount = [nt!KeNumberProcessors]
    ELSE
        Queue->MaximumCount = Count
    ENDIF
    RETURN

C++ Code

Here’s the translation of the pseudocode to C++:

VOID KeInitializeQueue(
  _Out_  PRKQUEUE Queue,
  _In_   ULONG Count
)
{
    Queue->Header.Type = 4;
    Queue->Header.Abandoned = 0;
    Queue->Header.Size = 10; 
    Queue->Header.SignalState = 0;


    Queue->WaitListHead.Blink = &Queue->WaitListHead;
    Queue->WaitListHead.Flink = &Queue->WaitListHead;

    Queue->EntryListHead.Blink = &(Queue->EntryListHead);
    Queue->EntryListHead.Flink = &(Queue->EntryListHead);

    Queue->ThreadListHead.Blink = &(Queue->ThreadListHead);
    Queue->ThreadListHead.Flink = &(Queue->ThreadListHead);

    Queue->CurrentCount = Count;
    if( Count == 0 )
        Queue->MaximumCount = [nt!KeNumberProcessors]
    else
        Queue->MaximumCount = Count
    return
}

► KxWaitForLockChainValid

This routine doesn’t exist on Vista 32bit, I’m solving this later.

► KeReadyThread

Syntax

The syntax according to this website is:

VOID NTAPI KeReadyThread	(	      
   IN PKTHREAD 	Thread	
);

Structures

The routine doesn’t access members of Thread directly, so no need to know the internals.

Decompilation

The kernel routine decompiles to:

kd> uf KeReadyThread
nt!KeReadyThread:
81a5bf06 8bff            mov     edi,edi
81a5bf08 55              push    ebp
81a5bf09 8bec            mov     ebp,esp
81a5bf0b 53              push    ebx
81a5bf0c 33c9            xor     ecx,ecx
81a5bf0e ff1568e0a181    call    dword ptr [nt!_imp_KeAcquireQueuedSpinLockRaiseToSynch (81a1e068)]
81a5bf14 8b4d08          mov     ecx,dword ptr [ebp+8]
81a5bf17 8ad8            mov     bl,al
81a5bf19 e88b860600      call    nt!KiReadyThread (81ac45a9)
81a5bf1e 648b0d20000000  mov     ecx,dword ptr fs:[20h]
81a5bf25 81c118040000    add     ecx,418h
81a5bf2b e88c7b0600      call    nt!KeReleaseQueuedSpinLockFromDpcLevel (81ac3abc)
81a5bf30 8acb            mov     cl,bl
81a5bf32 e8fd8f0600      call    nt!KiExitDispatcher (81ac4f34)
81a5bf37 5b              pop     ebx
81a5bf38 5d              pop     ebp
81a5bf39 c20400          ret     4

Calling Convention

The routine takes one argument, which is passed on the stack and can be accessed with [ebp+8].

Pseudocode

Lines 1-8 contain the function prologue and a call to KeAcquireQueuedSpinLockRaiseToSynch. This function takes one argument which is passed in ecx. The function returns a UCHAR value in register al.

irql = KeAcquireQueuedSpinLockRaiseToSynch(0)

Line 9-11 call KiReadyThread, which takes one argument passed in ecx (=Thread). The function doesn’t return anything:

KiReadyThread(Thread)

Lines 12-14 call KeReleaseQueuedSpinLockFromDpcLevel, which takes one argument and returns nothing. The parameter is passed in ecx. The code uses content of the segment register FS:

KeReleaseQueuedSpinLockFromDpcLevel(fs:[20h] + 0x418h)

Lines 15-16 call KiExitDispatcher, which takes one parameter in ecx and returns nothing:

KiExitDispatcher(irql)

The remaining lines just restore the preserved registers and return. The entire pseudocode is therefore:

irql = KeAcquireQueuedSpinLockRaiseToSynch(0)
KiReadyThread(Thread)
KeReleaseQueuedSpinLockFromDpcLevel(fs:[20h] + 0x418h)
KiExitDispatcher(irql)

C++ Code

Here’s the C++ code:

VOID NTAPI KeReadyThread(
    IN PKTHREAD 	Thread
)
{
    KIRQL irql = KeAcquireQueuedSpinLockRaiseToSynch(0);
    KiReadyThread(Thread);
    KeReleaseQueuedSpinLockFromDpcLevel(fs:[20h] + 0x418h);
    KiExitDispatcher(irql);
}

► KiInitializeTSS

Syntax

According to this site, the syntax of KiIntializeTSS is:

VOID NTAPI KiInitializeTSS	(	
    IN PKTSS 	Tss
);

Structures

The KTSS structure has the following members:

kd> dt _KTSS
ntdll!_KTSS
   +0x000 Backlink         : Uint2B
   +0x002 Reserved0        : Uint2B
   +0x004 Esp0             : Uint4B
   +0x008 Ss0              : Uint2B
   +0x00a Reserved1        : Uint2B
   +0x00c NotUsed1         : [4] Uint4B
   +0x01c CR3              : Uint4B
   +0x020 Eip              : Uint4B
   +0x024 EFlags           : Uint4B
   +0x028 Eax              : Uint4B
   +0x02c Ecx              : Uint4B
   +0x030 Edx              : Uint4B
   +0x034 Ebx              : Uint4B
   +0x038 Esp              : Uint4B
   +0x03c Ebp              : Uint4B
   +0x040 Esi              : Uint4B
   +0x044 Edi              : Uint4B
   +0x048 Es               : Uint2B
   +0x04a Reserved2        : Uint2B
   +0x04c Cs               : Uint2B
   +0x04e Reserved3        : Uint2B
   +0x050 Ss               : Uint2B
   +0x052 Reserved4        : Uint2B
   +0x054 Ds               : Uint2B
   +0x056 Reserved5        : Uint2B
   +0x058 Fs               : Uint2B
   +0x05a Reserved6        : Uint2B
   +0x05c Gs               : Uint2B
   +0x05e Reserved7        : Uint2B
   +0x060 LDT              : Uint2B
   +0x062 Reserved8        : Uint2B
   +0x064 Flags            : Uint2B
   +0x066 IoMapBase        : Uint2B
   +0x068 IoMaps           : [1] _KiIoAccessMap
   +0x208c IntDirectionMap  : [32] UChar

which translates to the following C++ structure:

typedef struct _KTSS
{
     WORD Backlink;
     WORD Reserved0;
     ULONG Esp0;
     WORD Ss0;
     WORD Reserved1;
     ULONG NotUsed1[4];
     ULONG CR3;
     ULONG Eip;
     ULONG EFlags;
     ULONG Eax;
     ULONG Ecx;
     ULONG Edx;
     ULONG Ebx;
     ULONG Esp;
     ULONG Ebp;
     ULONG Esi;
     ULONG Edi;
     WORD Es;
     WORD Reserved2;
     WORD Cs;
     WORD Reserved3;
     WORD Ss;
     WORD Reserved4;
     WORD Ds;
     WORD Reserved5;
     WORD Fs;
     WORD Reserved6;
     WORD Gs;
     WORD Reserved7;
     WORD LDT;
     WORD Reserved8;
     WORD Flags;
     WORD IoMapBase;
     KiIoAccessMap IoMaps[1];
     UCHAR IntDirectionMap[32];
} KTSS, *PKTSS;

Disassembly

kd> uf KiInitializeTSS
nt!KiInitializeTSS:
81a16eea 8bff            mov     edi,edi
81a16eec 55              push    ebp
81a16eed 8bec            mov     ebp,esp
81a16eef 8b4508          mov     eax,dword ptr [ebp+8]
81a16ef2 6683606400      and     word ptr [eax+64h],0
81a16ef7 6683606000      and     word ptr [eax+60h],0
81a16efc 66c74066ac20    mov     word ptr [eax+66h],20ACh
81a16f02 66c740081000    mov     word ptr [eax+8],10h
81a16f08 5d              pop     ebp
81a16f09 c20400          ret     4

Calling Convention

The kernel routine gets one parameter passed on the stack. The callee cleans up the stack upon returning. The routine uses the STDCALL-convention.

Pseudocode

Given the type of Tss, the translation to pseudocode is trivial:

eax = Tss
Tss->Flags = 0
Tss->LDT = 0
Tss->IoMapBase = 0x20AC
Tss->Ss0 = 0x10

C++ Code

The kernel routine in C++ is:

VOID NTAPI KiInitializeTSS	(	
    IN PKTSS 	Tss
)	
{
    Tss->Flags = 0;
    Tss->LDT = 0;
    Tss->IoMapBase = 0x20AC;
    Tss->Ss0 = 0x10;
}

► RtlValidateUnicodeString

Syntax

The syntax of RtlValidateUnicodeString can be seen here:

NTSTATUS NTAPI RtlValidateUnicodeString	(	
    IN ULONG Flags,
    IN PCUNICODE_STRING	UnicodeString 
);	

Structures

The kernel routine doesn’t modify any structure.

Disassembly

The disassembly of RtlValidateUnicodeString is:

kd> uf RtlValidateUnicodeString
Flow analysis was incomplete, some code may be missing
ntdll!RtlValidateUnicodeString:
77bd489f 8bff            mov     edi,edi
77bd48a1 55              push    ebp
77bd48a2 8bec            mov     ebp,esp
77bd48a4 837d0800        cmp     dword ptr [ebp+8],0
77bd48a8 0f85047b0300    jne     ntdll!RtlValidateUnicodeString+0xb (77c0c3b2)

ntdll!RtlValidateUnicodeString+0x12:
77bd48ae 6800010000      push    100h
77bd48b3 ff750c          push    dword ptr [ebp+0Ch]
77bd48b6 e809000000      call    ntdll!RtlUnicodeStringValidateEx (77bd48c4)
77bd48bb 5d              pop     ebp
77bd48bc c20800          ret     8

Calling Convention

The kernel routine takes two parameters which are passed on the stack. The first parameter Flags is referenced by [ebp+8], the second parameter UnicodeString is located at [ebp+0Ch]. The routine cleans up the stack with ret 8, hence the convention is STDCALL.

Pseudocode

The RtlUnicodeStringValidateEx routine takes two parameters and uses the STDCALL convention, see Microsoft MSDN.

So the pseudo-code is:

IF Flags != 0 THEN
        GOTO ntdll!RtlValidateUnicodeString+0xb
    ELSE
        RETURN RtlUnicodeStringValidateEx(UnicodeString, 0x100)

C++ Code

NTSTATUS NTAPI RtlValidateUnicodeString	(	
    IN ULONG Flags,
    IN PCUNICODE_STRING	UnicodeString 
)	
{
    if( Flags == 0 )
        return RtlUnicodeStringValidateEx(UnicodeString, 0x100);
    else
        // GOTO ntdll!RtlValidateUnicodeString+0xb
}