Thread Basics

A thread consists of two components:

  1. A kernel object that the operating system uses to manage the thread. The kernel object is also where the system keeps statistical information about the thread.
  2. A thread stack that maintains all the function parameters and local variables required as the thread executes code.

Threads are always created in the context of some process and live their entire life within that process. What this really means is that the thread executes code and manipulates data within its process’ address space. So if you have two or more threads running in the context of a single process, the threads share a single address space. The threads can execute the same code and manipulate the same data. Threads can also share kernel object handles because the handle table exists for each process, not each thread.

Your First Thread Function

Every thread must have an entry-point function where it begins execution. We already discussed this entry-point function for your primary thread: _tmain or _tWinMain. If you want to create a secondary thread in your process, it must also have an entry-point function, which should look something like this:

DWORD WINAPI ThreadFunc(PVOID pvParam){
   DWORD dwResult = 0;
   ...
   return(dwResult);

}

The CreateThread Function

If you want to create one or more secondary threads, you simply have an already running thread call CreateThread.

HANDLE CreateThread( PSECURITY_ATTRIBUTES psa, DWORD cbStackSize, PTHREAD_START_ROUTINE pfnStartAddr, PVOID pvParam, DWORD dwCreateFlags, PDWORD pdwThreadID);

PDWORD pdwThreadID);

The CreateThread function is the Windows function that creates a thread. However, if you are writing C/C++ code, you should never call CreateThread. Instead, you should use the Microsoft C++ run-time library function _beginthreadex

Thread Stack Size

The cbStackSize parameter specifies how much address space the thread can use for its own stack. Every thread owns its own stack. When CreateProcess starts a process, it internally calls CreateThread to initialize the process’ primary thread. For the cbStackSize parameter, CreateProcess uses a value stored inside the executable file. You can control this value using the linker’s /STACK switch:

/STACK:[reserve][,commit]

The reserve argument sets the amount of address space the system should reserve for the thread’s stack. The default is 1 MB. The commit argument specifies the amount of physical storage that should be initially committed to the stack’s reserved region.

When you call CreateThread, passing a value other than 0 causes the function to reserve and commit all storage for the thread’s stack. The amount of reserved space is either the amount specified by the /STACK linker switch or the value of cbStack, whichever is larger. If you pass 0 to the cbStack parameter, CreateThread reserves a region and commits the amount of storage indicated by the /STACK linker switch information embedded in the .exe file by the linker.

Thread Termination

A thread can be terminated in four ways:

  1. The thread function returns. (This is highly recommended.)
  2. The thread kills itself by calling the ExitThread function. (Avoid this method.)
  3. A thread in the same process or in another one calls the TerminateThread function. (Avoid this method.)
  4. The process containing the thread terminates. (Avoid this method.)

The Thread Function Returns

You should always design your thread functions so that they return when you want the thread to terminate. This is the only way to guarantee that all your thread’s resources are cleaned up properly.

Having your thread function return ensures the following:

  • All C++ objects created in your thread function will be destroyed properly via their destructors.
  • The operating system will properly free the memory used by the thread’s stack.
  • The system will set the thread’s exit code (maintained in the thread’s kernel object) to your thread function’s return value.
  • The system will decrement the usage count of the thread’s kernel object.

When a thread dies by returning or calling ExitThread, the stack for the thread is destroyed. However, if TerminateThread is used, the system does not destroy the thread’s stack until the process that owned the thread terminates.

if several threads run concurrently in your application, you need to explicitly handle how each one stops before the main thread returns. Otherwise, all other running threads will die abruptly and silently.

When a Thread Terminates

The following actions occur when a thread terminates:

  1. All User object handles owned by the thread are freed. In Windows, most objects are owned by the process containing the thread that creates the objects. However, a thread owns two User objects: windows and hooks. When a thread dies, the system automatically destroys any windows and uninstalls any hooks that were created or installed by the thread. Other objects are destroyed only when the owning process terminates.
  2. The thread’s exit code changes from STILL_ACTIVE to the code passed to ExitThread or TerminateThread.
  3. The state of the thread kernel object becomes signaled.
  4. If the thread is the last active thread in the process, the system considers the process terminated as well.
  5. The thread kernel object’s usage count is decremented by 1

Working with C/C++ Run Time Libraries

To create a new thread, you must not call the operating system’s CreateThread function—you must call the C/C++ run-time library function _beginthreadex:

unsigned long _beginthreadex(
   void *security,
   unsigned stack_size,
   unsigned (*start_address)(void *),
   void *arglist,
   unsigned initflag,
   unsigned *thrdaddr);
The _beginthreadex function has the same parameter list as the CreateThread function, but the parameter names and types are not exactly the same.
If you really want to forcibly kill your thread, you can have it call _endthreadex (instead of ExitThread) 

The C/C++ run-time library also places synchronization primitives around certain functions. For example, if two threads simultaneously call malloc, the heap can become corrupted. The C/C++ run-time library prevents two threads from allocating memory from the heap at the same time. It does this by making the second thread wait until the first has returned from malloc. Then the second thread is allowed to enter.Obviously, all this additional work affects the performance of the multithreaded version of the C/C++ run-time library.

Gaining a Sense of One’s Own Identity

Windows offers functions that make it easy for a thread to refer to its process kernel object or to its own thread kernel object:

HANDLE GetCurrentProcess();
HANDLE GetCurrentThread();

The following functions allow a thread to query its process’ unique ID or its own unique ID:

DWORD GetCurrentProcessId();
DWORD GetCurrentThreadId();

Converting a Pseudohandle to a Real Handle

Usually, you use DuplicateHandle function to create a new process-relative handle from a kernel object handle that is relative to another process. However, we can use it in an unusual way convert a Pseudohandle to a Real Handle:

DWORD WINAPI ParentThread(PVOID pvParam) {
   HANDLE hThreadParent;

   DuplicateHandle(
      GetCurrentProcess(),     // Handle of process that thread
                               // pseudohandle is relative to

      GetCurrentThread(),      // Parent thread's pseudohandle
      GetCurrentProcess(),     // Handle of process that the new, real,
                               // thread handle is relative to

      &hThreadParent,          // Will receive the new, real, handle
                               // identifying the parent thread
      0,                       // Ignored due to DUPLICATE_SAME_ACCESS
      FALSE,                   // New thread handle is not inheritable
      DUPLICATE_SAME_ACCESS);  // New thread handle has same
                               // access as pseudohandle

   CreateThread(NULL, 0, ChildThread, (PVOID) hThreadParent, 0, NULL);
   // Function continues...
}
DWORD WINAPI ChildThread(PVOID pvParam) {
   HANDLE hThreadParent = (HANDLE) pvParam;
   FILETIME ftCreationTime, ftExitTime, ftKernelTime, ftUserTime;
   GetThreadTimes(hThreadParent,
      &ftCreationTime, &ftExitTime, &ftKernelTime, &ftUserTime);
   CloseHandle(hThreadParent);
   // Function continues...
}

Now when the parent thread executes, it converts the ambiguous pseudohandle identifying the parent thread to a new, real handle that unambiguously identifies the parent thread, and it passes this real handle to CreateThread. When the child thread starts executing, its pvParam parameter contains the real thread handle. Any calls to functions passing this handle will affect the parent thread, not the child thread.

Because DuplicateHandle increments the usage count of the specified kernel object, it is important to decrement the object’s usage count by passing the target handle to CloseHandle when you finish using the duplicated object handle.

API Table

Function

Description

HANDLE CreateThread(
   PSECURITY_ATTRIBUTES psa,
   DWORD cbStackSize,
   PTHREAD_START_ROUTINE pfnStartAddr,
   PVOID pvParam,
   DWORD dwCreateFlags,
   PDWORD pdwThreadID);

If you want to create one or more secondary threads, you simply have an already running thread call CreateThread:

VOID ExitThread(DWORD dwExitCode);

You can force your thread to terminate

BOOL TerminateThread(
   HANDLE hThread,
   DWORD dwExitCode);

Unlike ExitThread, which always kills the calling thread, TerminateThread can kill any thread

BOOL GetExitCodeThread(
   HANDLE hThread,
   PDWORD pdwExitCode);

Check whether the thread identified by hThread has terminated and, if it has, determine its exit code.

The exit code value is returned in the DWORD pointed to by pdwExitCode. If the thread hasn’t terminated when GetExitCodeThread is called, the function fills the DWORD with the STILL_ACTIVE identifier (defined as 0×103). If the function is successful, TRUE is returned

References

Windows® via C/C++, Fifth Edition

How process can skip from its JOB – A taste of dirty application

I am writing this post while I can’t believe if what I did is normal or not, I will mention what I`ve did then I will pose some questions that really need answer.

Job Object is a very powerful concept in Windows, and it us used to impose limitations on process assigned to it, some of this limitations enhance process security. For more information about jobs refer Jobs post.

An important information you should know about Jobs:

Once a process is part of a job, it cannot be moved to another job and it cannot become jobless (so to speak). Also note that when a process that is part of a job spawns another process, the new process is automatically made part of the parent’s job. However, you can alter this behavior in the following ways

Let’s consider this scenario:

you write a Host application that runs other applications and manages them, this applications may have unknown implementation (you are not its author), and you create these application as a child process (Client process) of your Host process. Imagine that some of these client process are infected by some virus which requires to cross the limitations you imposed by your Job (e.g spawn other children processes, access USER objects outside the process, etc..). To ensure that your client processes run in a safe environment you impose the necessary restrictions.

Imagine if one application (infected one) was written to skip from the Job assigned to it and run as a jobless process with no restrictions! HOW will you control such thing? This is horrible and this is what I could do! I though that doing such thing is not doable as it is very dangerous, but I could do it.

Dirty application code

#include <iostream>
#include <Windows.h>
#include <tchar.h>
#include <strsafe.h>
#include "XWinAssist.h"
using namespace std;

#define HostJobName _T("XHostJob")
#define AppName _T("cmd.exe")
#define AppCount 5

void CreateJoblessSelf()
{
    const int cchSize = 128;
    DWORD dwSize = cchSize;
    TCHAR szProcessName[cchSize];
    QueryFullProcessImageName(GetCurrentProcess(), 0, szProcessName, &dwSize);

    STARTUPINFO si = { sizeof(si) };
    PROCESS_INFORMATION pi;

    // Here I create myself again in the same console window
    // I specify that I want to create myself and skip the current job
    BOOL fCreate = CreateProcess(NULL, szProcessName, NULL, NULL, FALSE, CREATE_BREAKAWAY_FROM_JOB, NULL, NULL, &si, &pi);

    if(!fCreate)
    {
        _tprintf_s(_T("Failed to create jobless self\n"));
        PrintLastError();
    }

    CloseHandle(pi.hThread);
    CloseHandle(pi.hProcess);
}

void StartSomeProcess()
{
    const int iSize = 128;
    TCHAR szCommandLine[iSize];
    _tcscpy_s(szCommandLine, iSize, AppName);
   
    STARTUPINFO si = { sizeof(si) };
    PROCESS_INFORMATION pi;

    // Start some cmd.exe prcess, for sure this can be any process you imagine
    BOOL fCreate = CreateProcess(NULL, szCommandLine, NULL, NULL, FALSE, CREATE_NEW_CONSOLE, NULL, NULL, &si, &pi);

    if(!fCreate)
    {   
        _tprintf_s(_T("Failed to start some process\n"));
        PrintLastError();
    }

    CloseHandle(pi.hThread);
    CloseHandle(pi.hProcess);
}

int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])
{
    BOOL bInJob = FALSE;
    PROCESS_INFORMATION pi =  { 0 };

    // find if we are already assigned to a job
    IsProcessInJob(GetCurrentProcess(), NULL, &bInJob);

    // I will try to skip from the job already assigned to me
    if (bInJob)
    {
        _tprintf_s(_T("\nProcess already in a job\n"));
        _tprintf_s(_T("Spawining JOBLESS SELF …\n"));

        // instantiating myself but with no restrictions
        CreateJoblessSelf();

        _tprintf_s(_T("\nRestarting …\n"));
        return 0;
    }
    else
    {
        // Reaching this line means that I am totally free and have no job restrictions
        _tprintf_s(_T("\nMUHAHAHAHA … I am JOBLESS Process (Evil Laugh)\n"));
    }

    // Spawn some process to mobilize system resources
    // this could be some other infectious job
    for(int i = 0; i < AppCount; ++i)
    {
        StartSomeProcess();
    }

    return(0);
}

Environment:

  • Microsoft Win7 Professional
  • Visual Studio 2008 Team Suite

Questions and Exclamations

I have some questions in my mind I need answer for, I tried to search online but with no useful information.

  1. Is there any permission or access rights required to allow a process to spawn other process outside its job? I think there should be some.
  2. Can this behavior be really dangerous and be used to make havoc in the system?
  3. Is this considered as a security flaw?

Jobs

You often need to treat a group of processes as a single entity. For example, when you tell Microsoft Visual Studio to build a C++ project, it spawns Cl.exe, which might have to spawn additional processes (such as the individual passes of the compiler). But if the user wants to prematurely stop the build, Visual Studio must somehow be able to terminate Cl.exe and all its child processes. Solving this simple (and common) problem in Microsoft Windows has been notoriously difficult because Windows doesn’t maintain a parent/child relationship between processes. In particular, child processes continue to execute even after their parent process has been terminated.

When you design a server, you must also treat a set of processes as a single group. For instance, a client might request that a server execute an application (which might spawn children of its own) and return the results back to the client. Because many clients might connect to this server, it would be nice if the server could somehow restrict what a client can request to prevent any single client from monopolizing all of its resources. These restrictions might include maximum CPU time that can be allocated to the client’s request, minimum and maximum working set sizes, preventing the client’s application from shutting down the computer, and security restrictions.

Microsoft Windows offers a job kernel object that lets you group processes together and create a "sandbox" that restricts what the processes can do. It is best to think of a job object as a container of processes. However, it is also useful to create jobs that contain a single process because you can place restrictions on that process that you normally cannot.

If the process is already associated with a job, there is no way to move away from it: both for the current process or any other spawn process. This is a security feature to ensure that you can’t escape from the restrictions set for you.

By default, when you start an application through Windows Explorer, the process gets automatically associated to a dedicated job, whose name is prefixed by the "PCA" string.

Placing Restrictions on a Job’s Processes

After creating a job, you will typically want to set up the sandbox (set restrictions) on what processes within the job can do. You can place several different types of restrictions on a job:

  • The basic limit and extended basic limit prevent processes within a job from monopolizing the system’s resources.
  • Basic UI restrictions prevent processes within a job from altering the user interface.
  • Security limits prevent processes within a job from accessing secure resources (files, registry subkeys, and so on).

Once a process is part of a job, it cannot be moved to another job and it cannot become jobless (so to speak). Also note that when a process that is part of a job spawns another process, the new process is automatically made part of the parent’s job. However, you can alter this behavior in the following ways:

  • Turn on the JOB_OBJECT_LIMIT_BREAKAWAY_OK flag in JOBOBJECT_BASIC_LIMIT_INFORMATION‘s LimitFlags member to tell the system that a newly spawned process can execute outside the job. To make this happen, you must call CreateProcess with the new CREATE_BREAKAWAY_FROM_JOB flag. If you call CreateProcess with the CREATE_BREAKAWAY_FROM_JOB flag but the job does not have the JOB_OBJECT_LIMIT_BREAKAWAY_OK limit flag turned on, CreateProcess fails. This mechanism is useful if the newly spawned process also controls jobs.

  • Turn on the JOB_OBJECT_LIMIT_SILENT_BREAKAWAY_OK flag in the JOBOBJECT_BASIC_LIMIT_INFORMATION‘s LimitFlags member. This flag also tells the system that newly spawned processes should not be part of the job. However, there is no need to pass any additional flags to CreateProcess. In fact, this flag forces new processes to not be part of the job. This flag is useful for processes that were originally designed knowing nothing about job objects.

Jobs Sample

My StartRestrictedProcess function places a process in a job that restricts the process’ ability to do certain things:

void StartRestrictedProcess() {
   // Check if we are not already associated with a job.
   // If this is the case, there is no way to switch to
   // another job.
   BOOL bInJob = FALSE;
   IsProcessInJob(GetCurrentProcess(), NULL, &bInJob);
   if (bInJob) {
      MessageBox(NULL, TEXT("Process already in a job"),
         TEXT(""), MB_ICONINFORMATION | MB_OK);
      return;
   }

// Create a job kernel object.
HANDLE hjob = CreateJobObject(NULL,
   TEXT("Wintellect_RestrictedProcessJob"));

// Place some restrictions on processes in the job.

// First, set some basic restrictions.
JOBOBJECT_BASIC_LIMIT_INFORMATION jobli = { 0 };

// The process always runs in the idle priority class.
jobli.PriorityClass = IDLE_PRIORITY_CLASS;

// The job cannot use more than 1 second of CPU time.
jobli.PerJobUserTimeLimit.QuadPart = 10000; // 1 sec in 100-ns intervals

// These are the only 2 restrictions I want placed on the job (process).
jobli.LimitFlags = JOB_OBJECT_LIMIT_PRIORITY_CLASS
   | JOB_OBJECT_LIMIT_JOB_TIME;
SetInformationJobObject(hjob, JobObjectBasicLimitInformation, &jobli,
   sizeof(jobli));

// Second, set some UI restrictions.
JOBOBJECT_BASIC_UI_RESTRICTIONS jobuir;
jobuir.UIRestrictionsClass = JOB_OBJECT_UILIMIT_NONE;     // A fancy zero

// The process can't log off the system.
jobuir.UIRestrictionsClass |= JOB_OBJECT_UILIMIT_EXITWINDOWS;

// The process can't access USER objects (such as other windows)
// in the system.
jobuir.UIRestrictionsClass |= JOB_OBJECT_UILIMIT_HANDLES;

SetInformationJobObject(hjob, JobObjectBasicUIRestrictions, &jobuir,
   sizeof(jobuir));

// Spawn the process that is to be in the job.
// Note: You must first spawn the process and then place the process in
//      the job. This means that the process' thread must be initially
//      suspended so that it can't execute any code outside of the job's
//      restrictions.
STARTUPINFO si = { sizeof(si) };
PROCESS_INFORMATION pi;
TCHAR szCmdLine[8];
_tcscpy_s(szCmdLine, _countof(szCmdLine), TEXT("CMD"));
BOOL bResult =
   CreateProcess(
      NULL, szCmdLine, NULL, NULL, FALSE,
      CREATE_SUSPENDED | CREATE_NEW_CONSOLE, NULL, NULL, &si, &pi);
// Place the process in the job.
// Note: If this process spawns any children, the children are
//      automatically part of the same job.
AssignProcessToJobObject(hjob, pi.hProcess);

   // Now we can allow the child process' thread to execute code.
   ResumeThread(pi.hThread);
   CloseHandle(pi.hThread);

   // Wait for the process to terminate or
   // for all the job's allotted CPU time to be used.
   HANDLE h[2];
   h[0] = pi.hProcess;
   h[1] = hjob;
   DWORD dw = WaitForMultipleObjects(2, h, FALSE, INFINITE);
   switch (dw - WAIT_OBJECT_0) {
      case 0:
         // The process has terminated...
         break;
      case 1:
         // All of the job's allotted CPU time was used...
         break;
   }

   FILETIME CreationTime;
   FILETIME ExitTime;
   FILETIME KernelTime;
   FILETIME UserTime;
   TCHAR szInfo[MAX_PATH];
   GetProcessTimes(pi.hProcess, &CreationTime, &ExitTime,
      &KernelTime, &UserTime);
   StringCchPrintf(szInfo, _countof(szInfo), TEXT("Kernel = %u  |  User = %u\n"),
      KernelTime.dwLowDateTime / 10000, UserTime.dwLowDateTime / 10000);
   MessageBox(GetActiveWindow(), szInfo, TEXT("Restricted Process times"),
      MB_ICONINFORMATION | MB_OK);

   // Clean up properly.
   CloseHandle(pi.hProcess);
   CloseHandle(hjob);
}

 

Jobs API Table

Function

Description

BOOL IsProcessInJob
   HANDLE hProcess,
   HANDLE hJob,
   PBOOL pbInJob);

check whether or not the current process is running under the control of an existing job by passing NULL as the second parameter

HANDLE CreateJobObject(
   PSECURITY_ATTRIBUTES psa,
   PCTSTR pszName);

create a new job kernel object

HANDLE OpenJobObject(
   DWORD dwDesiredAccess,
   BOOL bInheritHandle,
   PCTSTR pszName);
 
BOOL SetInformationJobObject(
   HANDLE hJob,
   JOBOBJECTINFOCLASS JobObjectInformationClass,
   PVOID pJobObjectInformation,
   DWORD cbJobObjectInformationSize);

place restrictions on a job

BOOL UserHandleGrantAccess(
   HANDLE hUserObj,
   HANDLE hJob,
   BOOL bGrant);

Grants or denies access to a handle to a User object to a job that has a user-interface restriction. When access is granted, all processes associated with the job can subsequently recognize and use the handle. When access is denied, the processes can no longer use the handle

BOOL QueryInformationJobObject(
   HANDLE hJob,
   JOBOBJECTINFOCLASS JobObjectInformationClass,
   PVOID pvJobObjectInformation,
   DWORD cbJobObjectInformationSize,
   PDWORD pdwReturnSize);

once you have placed restrictions on a job, you might want to query those restrictions.

 

A process in a job can call QueryInformationJobObject to obtain information about the job to which it belongs by passing NULL for the job handle parameter. This can be very useful because it allows a process to see what restrictions have been placed on it. However, the SetInformationJobObject function fails if you pass NULL for the job handle parameter because this allows a process to remove restrictions placed on it.

clip_image001

BOOL AssignProcessToJobObject(
   HANDLE hJob,
   HANDLE hProcess);

This function tells the system to treat the process (identified by hProcess) as part of an existing job (identified by hJob). Note that this function allows only a process that is not assigned to any job to be assigned to a job, and you can check this by using the already presented IsProcessInJob function.

BOOL TerminateJobObject(
   HANDLE hJob,
   UINT uExitCode);

kill all the processes within a job

 

References

Windows® via C/C++, Fifth Edition

Processes Cont`d–Process Termination

A process can be terminated in four ways:

  1. The primary thread’s entry-point function returns. (This is highly recommended.)
  2. One thread in the process calls the ExitProcess function. (Avoid this method.)
  3. A thread in another process calls the TerminateProcess function. (Avoid this method.)
  4. All the threads in the process just die on their own. (This hardly ever happens.)

This section discusses all four methods and describes what actually happens when a process ends.

The Primary Thread’s Entry-Point Function Returns

You should always design an application so that its process terminates only when your primary thread’s entry-point function returns. This is the only way to guarantee that all your primary thread’s resources are cleaned up properly.

Having your primary thread’s entry-point function return ensures the following:

  • Any C++ objects created by this thread will be destroyed properly using their destructors.
  • The operating system will properly free the memory used by the thread’s stack.
  • The system will set the process’ exit code (maintained in the process kernel object) to your entry-point function’s return value.
  • The system will decrement the process kernel object’s usage count.

The ExitProcess Function

A process terminates when one of the threads in the process calls ExitProcess:

VOID ExitProcess(UINT fuExitCode);

This function terminates the process and sets the exit code of the process to fuExitCode. ExitProcess doesn’t return a value because the process has terminated. If you include any code following the call to ExitProcess, that code will never execute.

When your primary thread’s entry-point function (WinMain, wWinMain, main, or wmain) returns, it returns to the C/C++ run-time startup code, which properly cleans up all the C run-time resources used by the process. After the C run-time resources have been freed, the C run-time startup code explicitly calls ExitProcess, passing it the value returned from your entry-point function.

By simply allowing the primary thread’s entry-point function to return, the C/C++ run time can perform its cleanup and properly destruct all C++ objects. By the way, this discussion does not apply only to C++ objects. The C/C++ run time does many things on behalf of your process; it is best to allow the run time to clean it up properly.

Making explicit calls to ExitProcess and ExitThread is a common problem that causes an application to not clean itself up properly. In the case of ExitThread, the process continues to run but can leak memory or other resources.

The TerminateProcess Function

A call to TerminateProcess also ends a process:

BOOL TerminateProcess(
   HANDLE hProcess,
   UINT fuExitCode);

This function is different from ExitProcess in one major way: any thread can call TerminateProcess to terminate another process or its own process. The hProcess parameter identifies the handle of the process to be terminated. When the process terminates, its exit code becomes the value you passed as the fuExitCode parameter.

You should use TerminateProcess only if you can’t force a process to exit by using another method. The process being terminated is given absolutely no notification that it is dying—the application cannot clean up properly and cannot prevent itself from being killed (except by normal security mechanisms). For example, the process cannot flush any information it might have in memory out to disk.

A process will leak absolutely nothing once it has terminated. I hope that this is clear.

The TerminateProcess function is asynchronous. So you might want to call WaitForSingleObject.

When All the Threads in the Process Die

If all the threads in a process die (either because they’ve all called ExitThread or because they’ve been terminated with TerminateThread), the operating system assumes that there is no reason to keep the process’ address space around. This is a fair assumption because there are no more threads executing any code in the address space. When the system detects that no threads are running any more, it terminates the process. When this happens, the process’ exit code is set to the same exit code as the last thread that died.

When a Process Terminates

When a process terminates, the following actions are set in motion:

  1. Any remaining threads in the process are terminated.
  2. All the User and GDI objects allocated by the process are freed, and all the kernel objects are closed. (These kernel objects are destroyed if no other process has open handles to them. However, the kernel objects are not destroyed if other processes do have open handles to them.)
  3. The process’ exit code changes from STILL_ACTIVE to the code passed to ExitProcess or TerminateProcess.
  4. The process kernel object’s status becomes signaled. This is why other threads in the system can suspend themselves until the process is terminated.
  5. The process kernel object’s usage count is decremented by 1.

Note that a process’ kernel object always lives at least as long as the process itself. However, the process kernel object might live well beyond its process. When a process terminates, the system automatically decrements the usage count of its kernel object. If the count goes to 0, no other process has an open handle to the object and the object is destroyed when the process is destroyed.

Once again, let me remind you that you should tell the system when you are no longer interested in a process’ statistical data by calling CloseHandle. If the process has already terminated, CloseHandle will decrement the count on the kernel object and free it.

References

Windows® via C/C++, Fifth Edition

Processes Cont`d–Beauty of CreateProcess Function

The CreateProcess Function

You create a process with the CreateProcess function:

BOOL CreateProcess(
   PCTSTR pszApplicationName,
   PTSTR pszCommandLine,
   PSECURITY_ATTRIBUTES psaProcess,
   PSECURITY_ATTRIBUTES psaThread,
   BOOL bInheritHandles,
   DWORD fdwCreate,
   PVOID pvEnvironment,
   PCTSTR pszCurDir,
   PSTARTUPINFO psiStartInfo,
   PPROCESS_INFORMATION ppiProcInfo);

When a thread calls CreateProcess:

  1. The system creates a process kernel object with an initial usage count of 1. This process kernel object is not the process itself but a small data structure that the operating system uses to manage the process.
  2. The system then creates a virtual address space for the new process and loads the code and data for the executable file and any required DLLs into the process’ address space.
  3. The system then creates a thread kernel object (with a usage count of 1) for the new process’ primary thread. Like the process kernel object, the thread kernel object is a small data structure that the operating system uses to manage the thread.
  4. This primary thread begins by executing the application entry point set by the linker as the C/C++ run-time startup code, which eventually calls your WinMain, wWinMain, main, or wmain function.
  5. If the system successfully creates the new process and primary thread, CreateProcess returns TRUE.

pszApplicationName and pszCommandLine

The pszApplicationName and pszCommandLine parameters specify the name of the executable file the new process will use and the command-line string that will be passed to the new process, respectively.

Notice that the pszCommandLine parameter is prototyped as a PTSTR. This means that CreateProcess expects that you are passing the address of a non-constant string. Internally, CreateProcess actually does modify the command-line string that you pass to it. But before CreateProcess returns, it restores the string to its original form.

CreateProcess also searches for the executable in the following order:

  1. The directory containing the .exe file of the calling process
  2. The current directory of the calling process
  3. The Windows system directory—that is, the System32 subfolder as returned by GetSystemDirectory
  4. The Windows directory
  5. The directories listed in the PATH environment variable

All of this happens as long as the pszApplicationName parameter is NULL (which should be the case more than 99 percent of the time). Instead of passing NULL, you can pass the address to a string containing the name of the executable file you want to run in the pszApplicationName parameter. Note that you must specify the file’s extension; the system will not automatically assume that the filename has an .exe extension. CreateProcess assumes that the file is in the current directory unless a path precedes the filename. If the file can’t be found in the current directory, CreateProcess doesn’t look for the file in any other directory—it simply fails.

psaProcess, psaThread, and bInheritHandles

To create a new process, the system must create a process kernel object and a thread kernel object (for the process’ primary thread). Because these are kernel objects, the parent process gets the opportunity to associate security attributes with these two objects. You use the psaProcess and psaThread parameters to specify the desired security for the process object and the thread object, respectively. You can pass NULL for these parameters, in which case the system gives these objects default security descriptors. Or you can allocate and initialize two SECURITY_ATTRIBUTES structures to create and assign your own security privileges to the process and thread objects.

Another reason to use SECURITY_ATTRIBUTES structures for the psaProcess and psaThread parameters is if you want either of these two object handles to be inheritable by any child processes spawned in the future by this parent process.

fdwCreate

The fdwCreate parameter identifies flags that affect how the new process is created. You can specify multiple flags if you combine them with the bitwise OR operator.

The fdwCreate parameter also allows you to specify a priority class. However, you don’t have to do this, and for most applications you shouldn’t—the system will assign a default priority class to the new process.

pvEnvironment

The pvEnvironment parameter points to a block of memory that contains environment strings that the new process will use. Most of the time, NULL is passed for this parameter, causing the child process to inherit the set of environment strings that its parent is using.

pszCurDir

The pszCurDir parameter allows the parent process to set the child process’ current drive and directory. If this parameter is NULL, the new process’ working directory will be the same as that of the application spawning the new process. If this parameter is not NULL, pszCurDir must point to a zero-terminated string containing the desired working drive and directory. Notice that you must specify a drive letter in the path.

psiStartInfo

The psiStartInfo parameter points either to a STARTUPINFO or STARTUPINFOEX structure:

typedef struct _STARTUPINFO {
   DWORD cb;
   PSTR lpReserved;
   PSTR lpDesktop;
   PSTR lpTitle;
   DWORD dwX;
   DWORD dwY;
   DWORD dwXSize;
   DWORD dwYSize;
   DWORD dwXCountChars;
   DWORD dwYCountChars;
   DWORD dwFillAttribute;
   DWORD dwFlags;
   WORD wShowWindow;
   WORD cbReserved2;
   PBYTE lpReserved2;
   HANDLE hStdInput;
   HANDLE hStdOutput;
   HANDLE hStdError;
} STARTUPINFO, *LPSTARTUPINFO;

typedef struct _STARTUPINFOEX {
    STARTUPINFO StartupInfo;
    struct _PROC_THREAD_ATTRIBUTE_LIST *lpAttributeList;
} STARTUPINFOEX, *LPSTARTUPINFOEX;

Windows uses the members of this structure when it creates the new process. Most applications will want the spawned application simply to use default values. At a minimum, you should initialize all the members in this structure to zero and then set the cb member to the size of the structure:

STARTUPINFO si = { sizeof(si) };
CreateProcess(..., &si, ...);

If you fail to zero the contents of the structure, the members will contain whatever garbage is on the calling thread’s stack.

Now, if you want to initialize some of the members of the structure, you simply do so before the call to CreateProcess.

This dwFlags member contains a set of flags that modify how the child process is to be created. Most of the flags simply tell CreateProcess whether other members of the STARTUPINFO structure contain useful information or whether some of the members should be ignored

ppiProcInfo

The ppiProcInfo parameter points to a PROCESS_INFORMATION structure that you must allocate; CreateProcess initializes the members of this structure before it returns. The structure appears as follows:

typedef struct _PROCESS_INFORMATION {
   HANDLE hProcess;
   HANDLE hThread;
   DWORD dwProcessId;
   DWORD dwThreadId;
} PROCESS_INFORMATION;

As already mentioned, creating a new process causes the system to create a process kernel object and a thread kernel object. At creation time, the system gives each object an initial usage count of 1. Then, just before CreateProcess returns, the function opens with full access to the process object and the thread object, and it places the process-relative handles for each in the hProcess and hThread members of the PROCESS_INFORMATION structure. When CreateProcess opens these objects internally, the usage count for each becomes 2.

This means that before the system can free the process object, the process must terminate (decrementing the usage count by 1) and the parent process must call CloseHandle (decrementing the usage count again by 1, making it 0). Similarly, to free the thread object, the thread must terminate and the parent process must close the handle to the thread object.

When a process kernel object is created, the system assigns the object a unique identifier; no other process kernel object in the system will have the same ID number. The same is true for thread kernel objects. When a thread kernel object is created, the object is assigned a unique, systemwide ID number. Process IDs and thread IDs share the same number pool. This means that it is impossible for a process and a thread to have the same ID. In addition, an object is never assigned an ID of 0. Notice that Windows Task Manager associates a process ID of 0 to the "System Idle Process" as shown next. However, there is really no such thing as the "System Idle Process." Task Manager creates this fictitious process as a placeholder for the Idle thread that runs when nothing else is running. The number of threads in the System Idle Process is always equal to the number of CPUs in the machine. As such, it always represents the percentage of CPU usage that is not being used by real processes.

You can discover the ID of the current process by using GetCurrentProcessId and the ID of the running thread by calling GetCurrentThreadId. You can also get the ID of a process given its handle by using GetProcessId and the ID of a thread given its handle by using GetThreadId. Last but not least, from a thread handle, you can determine the ID of its owning process by calling GetProcessIdOfThread.

References

Windows® via C/C++, Fifth Edition

Remote Procedure Call (RPC)

a remote procedure call (RPC) is an inter-process communication that allows a computer program to cause a subroutine or procedure to execute in another address space(commonly on another computer on a shared network) without the programmer explicitly coding the details for this remote interaction. That is, the programmer writes essentially the same code whether the subroutine is local to the executing program, or remote.

An RPC is initiated by the client, which sends a request message to a known remote server to execute a specified procedure with supplied parameters. The remote server sends a response to the client, and the application continues its process. While the server is processing the call, the client is blocked (it waits until the server has finished processing before resuming execution).

An important difference between remote procedure calls and local calls is that remote calls can fail because of unpredictable network problems. Also, callers generally must deal with such failures without knowing whether the remote procedure was actually invoked.

Sequence of events during a RPC

  1. The client calls the Client stub. The call is a local procedure call, with parameters pushed on to the stack in the normal way.
  2. The client stub packs the parameters into a message and makes a system call to send the message. Packing the parameters is called marshalling.
  3. The kernel sends the message from the client machine to the server machine.
  4. The kernel passes the incoming packets to the server stub.
  5. Finally, the server stub calls the server procedure. The reply traces the same steps in the reverse direction.

The illustration shows a more detailed sequence, the client application calls a local stub procedure instead of the actual code implementing the procedure. Stubs are compiled and linked with the client application. Instead of containing the actual code that implements the remote procedure, the client stub code:

  • Retrieves the required parameters from the client address space.
  • Translates the parameters as needed into a standard NDR format for transmission over the network.
  • Calls functions in the RPC client run-time library to send the request and its parameters to the server.

The server performs the following steps to call the remote procedure.

  1. The server RPC run-time library functions accept the request and call the server stub procedure.
  2. The server stub retrieves the parameters from the network buffer and converts them from the network transmission format to the format the server needs.
  3. The server stub calls the actual procedure on the server.

The remote procedure then runs, possibly generating output parameters and a return value. When the remote procedure is complete, a similar sequence of steps returns the data to the client.

  1. The remote procedure returns its data to the server stub.
  2. The server stub converts output parameters to the format required for transmission over the network and returns them to the RPC run-time library functions.
  3. The server RPC run-time library functions transmit the data on the network to the client computer.

The client completes the process by accepting the data over the network and returning it to the calling function.

  1. The client RPC run-time library receives the remote-procedure return values and returns them to the client stub.
  2. The client stub converts the data from its NDR to the format used by the client computer. The stub writes data into the client memory and returns the result to the calling program on the client.
  3. The calling procedure continues as if the procedure had been called on the same computer.

Stub

A stub is a piece of code used for converting parameters passed during a Remote Procedure Call (RPC).

The main idea of an RPC is to allow a local computer (client) to remotely call procedures on a remote computer (server). The client and server use different address spaces, so conversion of parameters used in a function call have to be performed, otherwise the values of those parameters could not be used, because of pointers to the computer’s memory pointing to different data on each machine. The client and server may also use different data representations even for simple parameters (e.g., big-endian versus little-endian for integers.) Stubs are used to perform the conversion of the parameters, so a Remote Function Call looks like a local function call for the remote computer.

Stub libraries must be installed on client and server side. A client stub is responsible for conversion of parameters used in a function call and deconversion of results passed from the server after execution of the function. A server stub is responsible for deconversion of parameters passed by the client and conversion of the results after the execution of the function.

Marshalling/Unmarshalling

Marshalling (similar to serialization) is the process of transforming the memory representation of an object to a data format suitable for storage or transmission. It is typically used when data must be moved between different parts of a computer program or from one program to another.

Marshalling is a process that is used to communicate to remote objects with an object (in this case a serialized object). It simplifies complex communication, using custom/complex objects to communicate – instead of primitives.

The opposite, or reverse, of marshalling is called unmarshalling (or demarshalling, similar to deserialization).

Marshalling vs Serialization

To “marshal” an object means to record its state and codebase(s) in such a way that when the marshalled object is “unmarshalled”, a copy of the original object is obtained, possibly by automatically loading the class definitions of the object. Marshalling is like serialization, except marshalling also records codebases. Marshalling is different from serialization in that marshalling treats remote objects specially.

To “serialize” an object means to convert its state into a byte stream in such a way that the byte stream can be converted back into a copy of the object.

References

Processes

What is a process?

A process is usually defined as an instance of a running program and consists of two components:

  • A kernel object that the operating system uses to manage the process. The kernel object is also where the system keeps statistical information about the process.
  • An address space that contains all the executable or dynamic-link library (DLL) module’s code and data. It also contains dynamic memory allocations such as thread stacks and heap allocations.

For a process to accomplish anything, it must have a thread that runs in its context; this thread is responsible for executing the code contained in the process’ address space. In fact, a single process might contain several threads, all of them executing code "simultaneously" in the process’ address space. To do this, each thread has its own set of CPU registers and its own stack. Each process has at least one thread that executes code in the process’ address space. When a process is created, the system automatically creates its first thread, called the primary thread. This thread can then create additional threads, and these can in turn create even more threads. If there were no threads executing code in the process’ address space, there would be no reason for the process to continue to exist, and the system would automatically destroy the process and its address space.

For all of these threads to run, the operating system schedules some CPU time for each thread. It creates the illusion that all the threads run concurrently by offering time slices (called quantums) to the threads in a round-robin fashion.

Your First Windows Application

Windows supports two types of applications: those based on a graphical user interface (GUI) and those based on a console user interface (CUI). A GUI-based application has a graphical front end.

When you use Microsoft Visual Studio to create an application project, the integrated environment sets up various linker switches so that the linker embeds the proper type of subsystem in the resulting executable. This linker switch is /SUBSYSTEM:CONSOLE for CUI applications and /SUB-SYSTEM:WINDOWS for GUI applications. When the user runs an application, the operating system’s loader looks inside the executable image’s header and grabs this subsystem value

Your Windows application must have an entry-point function that is called when the application starts running. As a C/C++ developer, there are two possible entry-point functions you can use:

int WINAPI _tWinMain(
   HINSTANCE hInstanceExe,
   HINSTANCE,
   PTSTR pszCmdLine,
   int nCmdShow);

int _tmain(
   int argc,
   TCHAR *argv[],
   TCHAR *envp[]);

     

Notice that the exact symbol depends on whether you are using Unicode strings or not. The table below tells you which entry point to implement in your source code and when.

image

The linker is responsible for choosing the proper C/C++ run-time startup function when it links your executable.

All of the C/C++ run-time startup functions do basically the same thing. The difference is in whether they process ANSI or Unicode strings and which entry-point function they call after they initialize the C run-time library. Here’s a summary of what the startup functions found in the crtexe.c file do:

  1. Retrieve a pointer to the new process’ full command line.
  2. Retrieve a pointer to the new process’ environment variables.
  3. Initialize the C/C++ run time’s global variables. Your code can access these variables if you include StdLib.h.
  4. Initialize the heap used by the C run-time memory allocation functions (malloc and calloc) and other low-level input/output routines.
  5. Call constructors for all global and static C++ class objects.

After all of this initialization, the C/C++ startup function calls your application’s entry-point function. If you wrote a _tWinMain function with _UNICODE defined, it is called as follows:

GetStartupInfo(&StartupInfo);
int nMainRetVal = wWinMain((HINSTANCE)&__ImageBase, NULL, pszCommandLineUnicode,
   (StartupInfo.dwFlags & STARTF_USESHOWWINDOW)
      ? StartupInfo.wShowWindow : SW_SHOWDEFAULT);

And it is called as follows without _UNICODE defined:

GetStartupInfo(&StartupInfo);
int nMainRetVal = WinMain((HINSTANCE)&__ImageBase, NULL, pszCommandLineAnsi,
   (StartupInfo.dwFlags & STARTF_USESHOWWINDOW)
      ? StartupInfo.wShowWindow : SW_SHOWDEFAULT);

Notice that _ImageBase is a linker defined pseudo-variable that shows where the executable file is mapped into the application memory.

When your entry-point function returns, the startup function calls the C run-time exit function, passing it your return value (nMainRetVal). The exit function does the following:

  1. It calls any functions registered by calls to the _onexit function.
  2. It calls destructors for all global and static C++ class objects.
  3. In DEBUG builds, leaks in the C/C++ run-time memory management are listed by a call to the _CrtDumpMemoryLeaks function if the _CRTDBG_LEAK_CHECK_DF flag has been set.
  4. It calls the operating system’s ExitProcess function, passing it nMainRetVal. This causes the operating system to kill your process and set its exit code.

If you wrote a _tmain function, it is called as follows when _UNICODE is defined:

int nMainRetVal = wmain(argc, argv, envp);

And it is called as follows when _UNICODE is not defined:

int nMainRetVal = main(argc, argv, envp);

Process Entry-point Parameters

Process Handle

Every executable or DLL file loaded into a process’ address space is assigned a unique instance handle. Your executable file’s instance is passed as (w)WinMain‘s first parameter, hInstanceExe. The handle’s value is typically needed for calls that load resources.

The actual value of (w)WinMain‘s hInstanceExe parameter is the base memory address where the system loaded the executable file’s image into the process’ address space. For example, if the system opens the executable file and loads its contents at address 0×00400000, (w)WinMain‘s hInstanceExe parameter has a value of 0×00400000.

The GetModuleHandle function, shown next, returns the handle/base address where an executable or DLL file is loaded in the process’ address space:

HMODULE GetModuleHandle(PCTSTR pszModule);

A Process’ Previous Instance Handle

As noted earlier, the C/C++ run-time startup code always passes NULL to (w)WinMain‘s hPrevInstance parameter. This parameter was used in 16-bit Windows and remains a parameter to (w)WinMain solely to ease porting of 16-bit Windows applications. You should never reference this parameter inside your code.

A Process’ Command Line

When a new process is created, it is passed a command line. The command line is almost never blank; at the very least, the name of the executable file used to create the new process is the first token on the command line.

Following the example of the C run time, you can also obtain a pointer to your process’ complete command line by calling the GetCommandLine function:

PTSTR GetCommandLine();

This function returns a pointer to a buffer containing the full command line, including the full pathname of the executed file. Be aware that GetCommandLine always returns the address of the same buffer. This is another reason why you should not write into pszCmdLine: it points to the same buffer, and after you modify it, there is no way for you to know what the original command line was.

The following function declared in ShellAPI.h and exported by Shell32.dll, CommandLineToArgvW, separates any Unicode string into its separate tokens:

PWSTR* CommandLineToArgvW(
   PWSTR pszCmdLine,
   int* pNumArgs);

As the W at the end of the function name implies, this function exists in a Unicode version only

A Process’ Environment Variables

Every process has an environment block associated with it. An environment block is a block of memory allocated within the process’ address space that contains a set of strings with the following appearance, where ‘’ means null character:

=::=::\ ...
VarName1=VarValue1
VarName2=VarValue2
VarName3=VarValue3 ...
VarNameX=VarValueX

The first part of each string is the name of an environment variable. This is followed by an equal sign, which is followed by the value you want to assign to the variable.

When a user logs on to Windows, the system creates the shell process and associates a set of environment strings with it. The system obtains the initial set of environment strings by examining two keys in the registry.

The first key contains the list of all environment variables that apply to the system:

HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\
   Session Manager\Environment

The second key contains the list of all environment variables that apply to the user currently logged on:

HKEY_CURRENT_USER\Environment

Normally, a child process inherits a set of environment variables that are the same as those of its parent process. However, the parent process can control what environment variables a child inherits, as you’ll see later when we discuss the CreateProcess function. By inherit, I mean that the child process gets its own copy of the parent’s environment block; the child and parent do not share the same block. This means that a child process can add, delete, or modify a variable in its block and the change will not be reflected in the parent’s block.

If you still want to use environment variables, there are a few functions that your applications can call. The GetEnvironmentVariable function allows you to determine the existence and value of an environment variable:

DWORD GetEnvironmentVariable(
   PCTSTR pszName,
   PTSTR pszValue,
   DWORD cchValue);

Many strings contain replaceable strings within them. For example, you can this string somewhere in the registry:

%USERPROFILE%\Documents

The portion that appears in between percent signs (%) indicates a replaceable string. In this case, the value of the environment variable, USERPROFILE, should be placed in the string. On my machine, the value of my USERPROFILE environment variable is

C:\Users\jrichter

So, after performing the string replacement, the resulting string becomes

C:\Users\jrichter\Documents

Because this type of string replacement is common, Windows offers the ExpandEnvironmentStrings function:

DWORD ExpandEnvironmentStrings(
   PTCSTR pszSrc,
   PTSTR pszDst,
   DWORD chSize);

Finally, you can use the SetEnvironmentVariable function to add a variable, delete a variable, or modify a variable’s value:

BOOL SetEnvironmentVariable(
   PCTSTR pszName,
   PCTSTR pszValue);

You should always use these functions for manipulating your process’ environment block.

Process Related

A Process’ Error Mode

Associated with each process is a set of flags that tells the system how the process should respond to serious errors, which include disk media failures, unhandled exceptions, file-find failures, and data misalignment. A process can tell the system how to handle each of these errors by calling the SetErrorMode function:

UINT SetErrorMode(UINT fuErrorMode);

The fuErrorMode parameter is a combination of any of the flags shown in the below table bitwise ORed together.

image

A Process’ Current Drive and Directory

When full pathnames are not supplied, the various Windows functions look for files and directories in the current directory of the current drive. For example, if a thread in a process calls CreateFile to open a file (without specifying a full pathname), the system looks for the file in the current drive and directory.

The system keeps track of a process’ current drive and directory internally. Because this information is maintained on a per-process basis, a thread in the process that changes the current drive or directory changes this information for all the threads in the process.

A thread can obtain and set its process’ current drive and directory by calling the following two functions:

DWORD GetCurrentDirectory(
   DWORD cchCurDir,
   PTSTR pszCurDir);
BOOL SetCurrentDirectory(PCTSTR pszCurDir);

If the buffer you provide is not large enough, GetCurrentDirectory returns the number of characters required to store this folder, including the final ” character, and copies nothing into the provided buffer, which can be set to NULL in that case. When the call is successful, the length of the string in characters is returned, without counting the terminating ” character.

A Process’ Current Directories

The system keeps track of the process’ current drive and directory, but it does not keep track of the current directory for every drive. However, there is some operating system support for handling current directories for multiple drives. This support is offered via the process’ environment strings. For example, a process can have two environment variables, as shown here:

=C:=C:\Utility\Bin
=D:=D:\Program Files

These variables indicate that the process’ current directory for drive C is \Utility\Bin and that its current directory for drive D is \Program Files.

If you call a function, passing a drive-qualified name indicating a drive that is not the current drive, the system looks in the process’ environment block for the variable associated with the specified drive letter. If the variable for the drive exists, the system uses the variable’s value as the current directory. If the variable does not exist, the system assumes that the current directory for the specified drive is its root directory.

For example, if your process’ current directory is C:\Utility\Bin and you call CreateFile to open D:ReadMe.Txt, the system looks up the environment variable =D:. Because the =D: variable exists, the system attempts to open the ReadMe.Txt file from the D:\Program Files directory. If the =D: variable did not exist, the system would attempt to open the ReadMe.Txt file from the root directory of drive D. The Windows file functions never add or change a drive-letter environment variable—they only read the variables.

If a parent process creates an environment block that it wants to pass to a child process, the child’s environment block does not automatically inherit the parent process’ current directories. Instead, the child process’ current directories default to the root directory of every drive. If you want the child process to inherit the parent’s current directories, the parent process must create these drive-letter environment variables and add them to the environment block before spawning the child process. The parent process can obtain its current directories by calling GetFullPathName:

DWORD GetFullPathName(
   PCTSTR pszFile,
   DWORD cchPath,
   PTSTR pszPath,
   PTSTR *ppszFilePart);

For example, to get the current directory for drive C, you call GetFullPathName as follows:

TCHAR szCurDir[MAX_PATH];
DWORD cchLength = GetFullPathName(TEXT("C:"), MAX_PATH, szCurDir, NULL);

As a result, the drive-letter environment variables usually must be placed at the beginning of the environment block.

The System Version

Frequently, an application needs to determine which version of Windows the user is running.

BOOL GetVersionEx(POSVERSIONINFOEX pVersionInformation);

This function requires you to allocate an OSVERSIONINFOEX structure in your application and pass the structure’s address to GetVersionEx. The OSVERSIONINFOEX structure is shown here:

typedef struct {
   DWORD dwOSVersionInfoSize;
   DWORD dwMajorVersion;
   DWORD dwMinorVersion;
   DWORD dwBuildNumber;
   DWORD dwPlatformId;
   TCHAR szCSDVersion[128];
   WORD  wServicePackMajor;
   WORD  wServicePackMinor;
   WORD  wSuiteMask;
   BYTE  wProductType;
   BYTE  wReserved;
} OSVERSIONINFOEX, *POSVERSIONINFOEX;

The OSVERSIONINFOEX structure has been available since Windows 2000. Other versions of Windows use the older OSVERSIONINFO structure, which does not have the service pack, suite mask, product type, and reserved members.

References

Windows® via C/C++, Fifth Edition

Kernel Objects

What is Kernel Objects?

The system creates and manipulates several types of kernel objects, such as access token objects, event objects, file objects, file-mapping objects, I/O completion port objects, job objects, mailslot objects, mutex objects, pipe objects, process objects, semaphore objects, thread objects, waitable timer objects, and thread pool worker factory objects

Each kernel object is simply a memory block allocated by the kernel and is accessible only by the kernel. This memory block is a data structure whose members maintain information about the object. Some members (security descriptor, usage count, and so on) are the same across all object types, but most are specific to a particular object type. For example, a process object has a process ID, a base priority, and an exit code, whereas a file object has a byte offset, a sharing mode, and an open mode.

Windows offers a set of functions that manipulate these structures in well-defined ways. These kernel objects are always accessible via these functions. When you call a function that creates a kernel object, the function returns a handle that identifies the object.

To make the operating system robust, these handle values are process-relative. So if you were to pass this handle value to a thread in another process (using some form of interprocess communication), the calls that this other process would make using your process’ handle value might fail or, even worse, they will create a reference to a totally different kernel object at the same index in your process handle table.

Usage Counting

each kernel object has a data member called usage count. Kernel uses reference counting to keep track of kernel objects, and destroy them when no other process is using them.

Security

Kernel objects can be protected with a security descriptor. A security descriptor describes who owns the object (usually its creator), which group and users can gain access to or use the object, and which group and users are denied access to the object.

Almost all functions that create kernel objects have a pointer to a SECURITY_ATTRIBUTES structure as an argument.

When you want to gain access to an existing kernel object (rather than create a new one), you must specify the operations you intend to perform on the object. For example, if I want to gain access to an existing file-mapping kernel object so that I could read data from it, I call OpenFileMapping as follows:

HANDLE hFileMapping = OpenFileMapping(FILE_MAP_READ, FALSE, TEXT(“MyFileMapping”));

Neglecting proper security access flags is one of the biggest mistakes that developers make. Using the correct flags will certainly make it much easier to port an application between Windows versions. However, you also need to realize that each new version of Windows brings a new set of constraints that did not exist in the previous versions

In addition to using kernel objects, your application might use other types of objects, such as menus, windows, mouse cursors, brushes, and fonts. These objects are User objects or Graphical Device Interface (GDI) objects, not kernel objects

A Process’ Kernel Object Handle Table

When a process is initialized, the system allocates a handle table for it. This handle table is used only for kernel objects, not for User objects or GDI objects

All functions that create kernel objects return process-relative handles that can be used successfully by any and all threads that are running in the same process

Whenever you call a function that accepts a kernel object handle as an argument, you pass the value returned by one of the Create* functions. Internally, the function looks in your process’ handle table to get the address of the kernel object you want to manipulate and then manipulates the object’s data structure in a well-defined fashion.

If you pass an invalid handle, the function returns failure and GetLastError returns 6 (ERROR_INVALID_HANDLE). Because handle values are actually used as indexes into the process’ handle table, these handles are process-relative and cannot be used successfully from other processes. And if you ever tried to do so, you would simply reference the kernel object stored at the same index into the other process’ handle table, without any idea of what this object would be.

Unfortunately, a few functions return a handle value of -1 (INVALID_HANDLE_VALUE definedin WinBase.h) when they fail. For example, if CreateFile fails to open the specified file, it returns INVALID_HANDLE_VALUE instead of NULL. You must be very careful when checking the return value of a function that creates a kernel object. Specifically, you can compare the value with INVALID_HANDLE_VALUE only when you call CreateFile.

Closing a Kernel Object

Regardless of how you create a kernel object, you indicate to the system that you are done manipulating the object by calling CloseHandle: BOOL CloseHandle(HANDLE hobject);

Right before CloseHandle returns, it clears out the entry in the process’ handle table—this handle is now invalid for your process, and you should not attempt to use it.

Sharing Kernel Objects Across Process Boundaries

Frequently, threads running in different processes need to share kernel objects. Here are some of the reasons why:

File-mapping objects allow you to share blocks of data between two processes running on a single machine.

Mailslots and named pipes allow applications to send blocks of data between processes running on different machines connected to the network.

Mutexes, semaphores, and events allow threads in different processes to synchronize their continued execution, as in the case of an application that needs to notify another application when it has completed some task.

Object Handle Inheritance

Object handle inheritance can be used only when processes have a parent-child relationship. In this scenario, one or more kernel object handles are available to the parent process, and the parent decides to spawn a child process, giving the child access to the parent’s kernel objects

To create an inheritable handle, the parent process must allocate and initialize a SECURITY_ATTRIBUTES structure and pass the structure’s address to the specific Create function. The following code creates a mutex object and returns an inheritable handle to it:

SECURITY_ATTRIBUTES sa;

sa.nLength = sizeof(sa);

sa.lpSecurityDescriptor = NULL;

sa.bInheritHandle = TRUE; // Make the returned handle inheritable.

HANDLE hMutex = CreateMutex(&sa, FALSE, NULL);

This code initializes a SECURITY_ATTRIBUTES structure indicating that the object should be created using default security and that the returned handle should be inheritable.

The next step to perform when using object handle inheritance is for the parent process to spawn the child process. This is done using the CreateProcess function:

BOOL CreateProcess(

PCTSTR pszApplicationName,

PTSTR pszCommandLine,

PSECURITY_ATTRIBUTES psaProcess,

PSECURITY_ATTRIBUTES psaThread,

BOOL bInheritHandles,

DWORD dwCreationFlags,

PVOID pvEnvironment,

PCTSTR pszCurrentDirectory,

LPSTARTUPINFO pStartupInfo,

PPROCESS_INFORMATION pProcessInformation);

Set the bInheritHandles parameter to True, In addition to copying the handle table entry, the system increments the usage count of the kernel object because two processes are now using the object

Object handle inheritance has one very strange characteristic: when you use it, the child has no idea that it has inherited any handles. Kernel object handle inheritance is useful only when the child process documents the fact that it expects to be given access to a kernel object when spawned from another process. Usually, the parent and child applications are written by the same company; however, a different company can write the child application if that company documents what the child application expects.

Handle values can be passed from parent to child via 3 different ways:

Using environment variables set at parent and inherited by child processes

Passed as Command-line arguments at process creation

Inter-process communication like windows messaging, the parent waits until the child is completely initialized and send message to the child containing the handle values.

Changing Handles Flags

Occasionally, you might encounter a situation in which a parent process creates a kernel object retrieving an inheritable handle and then spawns two child processes. The parent process wants only one child to inherit the kernel object handle. In other words, you might at times want to control which child processes inherit kernel object handles. To alter the inheritance flag of a kernel object handle, you can call the SetHandleInformation function:

BOOL SetHandleInformation(

HANDLE hObject,

DWORD dwMask,

DWORD dwFlags);

to turn on the inheritance flag for a kernel object handle, do the following:

    SetHandleInformation(hObj, HANDLE_FLAG_INHERIT, HANDLE_FLAG_INHERIT);

To turn off this flag, do this:

    SetHandleInformation(hObj, HANDLE_FLAG_INHERIT, 0);

The HANDLE_FLAG_PROTECT_FROM_CLOSE flag tells the system that this handle should not be allowed to be closed:

    SetHandleInformation(hObj, HANDLE_FLAG_PROTECT_FROM_CLOSE,

    HANDLE_FLAG_PROTECT_FROM_CLOSE);

    CloseHandle(hObj); // Exception is raised

 

For the sake of completeness, I’ll also mention the GetHandleInformation function:

BOOL GetHandleInformation(

HANDLE hObject,

PDWORD pdwFlags);

This function returns the current flag settings for the specified handle in the DWORD pointed to by pdwFlags. To see if a handle is inheritable, do the following:

    DWORD dwFlags;

        GetHandleInformation(hObj, &dwFlags);

        BOOL fHandleIsInheritable = (0 != (dwFlags & HANDLE_FLAG_INHERIT));

Naming Objects

The second method available for sharing kernel objects across process boundaries is to name the objects

All kernel object creation functions have a common last parameter, pszName. When you pass NULL for this parameter, you are indicating to the system that you want to create an unnamed (anonymous) kernel object. When you create an unnamed object, you can share the object across processes by using either inheritance or DuplicateHandle). To share an object by name, you must give the object a name.

Unfortunately, Microsoft offers no guidance for assigning names to kernel objectsLet’s say that Process A starts up and calls the following function:

HANDLE hMutexProcessA = CreateMutex(NULL, FALSE, TEXT(“JeffMutex”));

This function call creates a new mutex kernel object and assigns it the name “JeffMutex”.

Some time later, some process spawns Process B.

HANDLE hMutexProcessB = CreateMutex(NULL, FALSE, TEXT(“JeffMutex”));

When Process B’s call to CreateMutex is made, the system first checks to find out whether a kernel object with the name “JeffMutex” already exists. Because an object with this name does exist, the kernel then checks the object type. Because we are attempting to create a mutex and the object with the name “JeffMutex” is also a mutex, the system then makes a security check to see whether the caller has full access to the object. If it does, the system locates an empty entry in Process B’s handle table and initializes the entry to point to the existing kernel object. If the object types don’t match or if the caller is denied access, CreateMutex fails (returns NULL).

An alternative method exists for sharing objects by name. Instead of calling a Create* function, a process can call one of the Open* functions shown here:

The main difference between calling a Create* function versus calling an Open* function is that if the object doesn’t already exist, the Create* function will create it, whereas the Open* function will simply fail.

Named objects are commonly used to prevent multiple instances of an application from running

To do this, simply call a Create* function in your _tmain or _tWinMain function to create a named object. (It doesn’t matter what type of object you create.) When the Create* function returns, call GetLastError. If GetLastError returns ERROR_ALREADY_EXISTS, another instance of your application is running and the new instance can exit

Terminal Services Namespaces

If you have to know in which Terminal Services session your process is running, the ProcessIdToSessionId function (exported by kernel32.dll and declared in WinBase.h) is what you need, as shown in the following example:

DWORD processID = GetCurrentProcessId();

DWORD sessionID;

if (ProcessIdToSessionId(processID, &sessionID)) {

tprintf(

TEXT(“Process ‘%u’ runs in Terminal Services session ‘%u’”),

processID, sessionID);

} else {

// ProcessIdToSessionId might fail if you don’t have enough rights

// to access the process for which you pass the ID as parameter.

// Notice that it is not the case here because we’re using our own process ID.

tprintf(

TEXT(“Unable to get Terminal Services session ID for process ‘%u’”),

processID);

}

Duplicating Object Handles

The last technique for sharing kernel objects across process boundaries requires the use of the DuplicateHandle function:

BOOL DuplicateHandle(

HANDLE hSourceProcessHandle,

HANDLE hSourceHandle,

HANDLE hTargetProcessHandle,

PHANDLE phTargetHandle,

DWORD dwDesiredAccess,

BOOL bInheritHandle,

DWORD dwOptions);

Simply stated, this function takes an entry in one process’ handle table and makes a copy of the entry into another process’ handle table. DuplicateHandle takes several parameters but is actually quite straightforward. The most general usage of the DuplicateHandle function could involve three different processes that are running in the system.

However, it is rarely used when three different processes are involved (partly because it is unlikely that Process C would know the handle value of an object in use by Process S). Usually, DuplicateHandle is called when only two processes are involved. Imagine a situation in which one process has access to an object that another process wants access to, or a case in which one process wants to give access to a kernel object to another process. For example, let’s say that Process S has access to a kernel object and wants to give Process T access to this object. To do this, you call DuplicateHandle as follows:

// All of the following code is executed by Process S.

// Create a mutex object accessible by Process S.

HANDLE hObjInProcessS = CreateMutex(NULL, FALSE, NULL);

// Get a handle to Process T’s kernel object.

HANDLE hProcessT = OpenProcess(PROCESS_ALL_ACCESS, FALSE,

dwProcessIdT);

HANDLE hObjInProcessT; // An uninitialized handle relative to Process T.

// Give Process T access to our mutex object.

DuplicateHandle(GetCurrentProcess(), hObjInProcessS, hProcessT,

&hObjInProcessT, 0, FALSE, DUPLICATE_SAME_ACCESS);

// Use some IPC mechanism to get the handle value of hObjInProcessS into Process T.

// We no longer need to communicate with Process T.

CloseHandle(hProcessT);

// When Process S no longer needs to use the mutex, it should close it.

CloseHandle(hObjInProcessS);

Here is another way to use DuplicateHandle: Suppose that a process has read and write access to a file-mapping object. At some point, a function is called that is supposed to access the file-mapping object by only reading it. To make our application more robust, we can use Duplicate-Handle to create a new handle for the existing object and ensure that this new handle has read-only access on it. We would then pass this read-only handle to the function; this way, the code in the function would never be able to accidentally write to the file-mapping object. The following code illustrates this example:

int WINAPI _tWinMain(HINSTANCE hInstExe, HINSTANCE,

LPTSTR szCmdLine, int nCmdShow) {

// Create a file-mapping object; the handle has read/write access.

HANDLE hFileMapRW = CreateFileMapping(INVALID_HANDLE_VALUE,

NULL, PAGE_READWRITE, 0, 10240, NULL);

// Create another handle to the file-mapping object;

// the handle has read-only access.

HANDLE hFileMapRO;

DuplicateHandle(GetCurrentProcess(), hFileMapRW, GetCurrentProcess(),

&hFileMapRO, FILE_MAP_READ, FALSE, 0);

// Call the function that should only read from the file mapping.

ReadFromTheFileMapping(hFileMapRO);

// Close the read-only file-mapping object.

CloseHandle(hFileMapRO);

// We can still read/write the file-mapping object using hFileMapRW.

// When the main code doesn’t access the file mapping anymore,

// close it.

CloseHandle(hFileMapRW);

}

References

Windows via C/C++, Fifth Edition : Jeffrey Richter , Christophe Nasarre

Events and Delegates: A C++ Implementation

Hi geeks! Hope for you a good coding and debugging day, free of Access Violation and Linkage errors.

First of all, Who should read this article?

  • C++ geek, who dreams of pointers, watches "Bug attack" movies, and prefers to trace the call stack all the night rather than going out with some friends.
  • C# cool dude, sick of Microsoft babysitting, and willing to move to C++, and aware of the trade-offs.
  • Java bean, that never heard of pointer to function concept, and wants to know how C++/C# guys suffer.

I have been using C# for around 2 years. I was totally fascinated by C# object oriented architecture. Events and delegates are of the most C# constructs I liked. However, there is a big trade-off here i.e using delegates in C#, it is flexibility and performance. Delegates in C# are no function to pointers rather they are implemented somehow using reflection. I was shocked when I read an article called Writing Faster Managed Code: Know what things cost, this article is talking about the cost of most common C# operations. You will be surprised when you find that in C# a function call using a delegate is slower 6 times than simply calling a function using its signature. The function call using its signature costs around 6 ns (nano second), while using delegate costs around 40 ns! If you are a normal geek then you should be shocked now. As a consequence to this shock, I don’t know how it happened, but months ago I felt that C++ is calling me. I started to code everything using C++. The geek inside me is controlling! Help me.

Coding C++ again after 1 year of pure C#ing is not easy. I was used to delegates and events heavily in my code to maintain a decoupling between classes. I couldn’t find something like: Click += new Handler(ClickHandler); The only way to achieve something near this in C++ is through function to pointers. A first attempt was done here in this article Meet Functors. The first attempt was about implementing generic delegates, but unfortunately it was over complex, and requires a lot of code to deal with. A second attempt was made, and it is about implementing Events and Delegates in C++ like those in C#. That is what this article is all about.

We are not going to explain the concept here. We will pose the code here, and any explanation required will be in the discussion.

The big goal is the line of code below, i.e approaching C# syntax as much as possible:

p_server->MessageSent += new ClientDelegate(this, &Client::MessageSentHandler);
driver.cpp

class Server;
class Client;

typedef Event<Server> ServerEvent;
typedef Delegate<Client, Server> ClientDelegate;

class Server
{
public:
    ServerEvent MessageSent;

    void SendMessage(char* p_msg)
    {
        MessageSent(this, p_msg);
    }
};

class Client
{
    static int s_id;
    int m_id;
    void MessageSentHandler(const Server* p_sender, void* p_parameter)
    {
        cout << "Client" << m_id << ": received: " << (char*)p_parameter << endl;
    }
public:
    Client(Server* p_server)
    {
        m_id = ++s_id;
        p_server->MessageSent += new ClientDelegate(this, &Client::MessageSentHandler);
    }
};
int Client::s_id = 0;

int main()
{
    Server server;
    Client client1(&server), client2(&server), client3(&server);

    server.SendMessage("Hello");

    return 0;
}

Console Output

Client1: received: Hello 
Client2: received: Hello

Client3: received: Hello

Press any key to continue . . .

Delegate.h

template<class TSender>
class BaseDelegate
{
public:
    virtual bool Equals( const BaseDelegate<TSender>* p_other) = 0;
    virtual void operator()( const TSender* p_sender, void* p_parameter) = 0;
    virtual void Call( const TSender* p_sender, void* p_parameter) = 0;
};

template<class TReciever, class TSender>
class Delegate : public BaseDelegate<TSender>
{
private:
    typedef void (TReciever::*PTF)(const TSender*, void* p_parameter);
    PTF         m_ptr2Func;
    TReciever*  m_ptr2Object;

public:
    Delegate(TReciever* p_ptr2Object, PTF p_ptr2Func)
    {
        m_ptr2Func      = p_ptr2Func;
        m_ptr2Object    = p_ptr2Object;
    }

    bool Equals(const BaseDelegate<TSender>* p_other)
    {
        const Delegate<TReciever, TSender>* other;

        other = static_cast<const Delegate<TReciever, TSender>*>(p_other);

        assert(other != NULL);
        assert(m_ptr2Object != NULL);

        return other->m_ptr2Object == m_ptr2Object && other->m_ptr2Func == m_ptr2Func;
    }

    virtual void operator()(const TSender* p_sender, void* p_parameter)
    {
        assert(p_sender != NULL);
        (m_ptr2Object->*m_ptr2Func)(p_sender, p_parameter);
    }

    virtual void Call(const TSender* p_sender, void* p_parameter)
    {
        assert(p_sender != NULL);
        (m_ptr2Object->*m_ptr2Func)(p_sender, p_parameter);
    }
};

Event.h

template<class TSender>
class Event
{
    list< BaseDelegate<TSender>* > m_observers;
    void Register( const BaseDelegate<TSender>* p_handler);
    void Unregister( const BaseDelegate<TSender>* p_handler);
public:
    void operator += ( const BaseDelegate<TSender>* p_handler);
    void operator -= ( const BaseDelegate<TSender>* p_handler);
    void operator () ( const TSender* p_sender, void* p_parameter);
    void Call( const TSender* p_sender, void* p_parameter);
    ~Event();
};

template<class TSender>
void Event<TSender>::operator += (const BaseDelegate<TSender>* p_handler)
{
    Register(p_handler);
}

template<class TSender>
void Event<TSender>::operator -= (const BaseDelegate<TSender>* p_handler)
{
    Unregister(p_handler);
}

template<class TSender>
void Event<TSender>::operator ()(const TSender* p_sender, void* p_parameter)
{
    Call(p_sender, p_parameter);
}

template<class TSender>
void Event<TSender>::Register(const BaseDelegate<TSender>* p_handler)
{
    assert(p_handler != NULL);

    for(list< BaseDelegate<TSender>* >::iterator itr = m_observers.begin();
       itr != m_observers.end();
       itr++)
    {
        if((*itr)->Equals(p_handler))
            return;
    }

    m_observers.push_back(const_cast<BaseDelegate<TSender>*>(p_handler));
}

template<class TSender>
void Event<TSender>::Unregister(const BaseDelegate<TSender>* p_handler)
{
    assert(p_handler != NULL);

    vector< BaseDelegate<TSender>* >::iterator where;
    for(list< BaseDelegate<TSender>* >::iterator itr = m_observers.begin();
        itr != m_observers.end();
        itr++)
    {
        if((*itr)->Equals(p_handler))
        {
            where = itr;
            break;
        }
    }

    m_observers.erase(where);
}


template<class TSender>
void Event<TSender>::Call(const TSender* p_sender, void* p_parameter)
{
    for(list< BaseDelegate<TSender>* >::iterator itr = m_observers.begin();
        itr != m_observers.end();
        itr++)
    {
        (*itr)->Call(p_sender, p_parameter);
    }
}

template<class TSender>
Event<TSender>::~Event()
{
    for(list< BaseDelegate<TSender>* >::iterator itr = m_observers.begin();
        itr != m_observers.end();
        itr++)
    {
        assert(*itr != NULL);
        delete (*itr);
    }
}

I leave you with the code, feel it and test it. If you detect any bug please don’t hesitate to fire it here. Any questions are very welcomed.

Paper Read: Case-Based Reasoning- Foundational Issues, Methodological Variations, and System Approaches

Agnar Aamodt, Enric Plaza. 1994. Case-Based Reasoning: Foundational Issues, Methodological Variations, and System Approaches. In AI COMMUNICATIONS.

The paper presents

  • Overview of the field in terms of its underlying foundations, its current state-of the art, future trends.
  • The description of CBR principles, methods and systems in analytical scheme.

Definitions

  • Case Based Reasoning (CBR):
    • CBR is a problem solving paradigm that instead of relying on general knowledge about the problem domain, CBR is able to utilize cases.
    • A new problem is solved by finding a similar past case, and reusing it in the new problem situation.
    • CBR is an approach to incremental learning, since new experience is retained each time a problem has been solved, making it available for future problems.
  • Case:
    • Case is a specific knowledge of previously experienced concrete problem situation.
    • In CBR terms, it denotes a problem situation.
    • A previously experienced situation, which has been captured and learned in a way that it can be reused in solving future problems.
    • Previous experience is known as retained case, solved case, past case.
    • New problem to be solved is called new case, or unsolved case.

Case-based problem solving

  • Reasoning by re-using past cases is powerful and frequently applied way to solve problems for humans.
  • Several studies have given evidence for the dominating role of specific, previously experienced situations in human problem solving.
  • It has been shown that human uses past-cases as models when learning to solve problems, in early learning.
  • Other results indicate that the use of past-cases isa predominant problem solving method among any domain experts as well.
  • Problem solving is not necessarily the finding of a concrete solution to an application problem.
  • The problem can be put by the user, such as criticize user solutions, generate set of solutions, interpret a problem situation, generate expectations in observable data.

Learning in Case-based reasoning

  • CBR is coupled to learning, it is regarded as a subfield of machine learning.
  • CBR denotes a machine learning paradigm that enables sustained and incremental learning by updating the case-base after a problem has been solved.
  • Learning in CBR occurs as a natural by product of problem solving.
  • When an attempt to solve a problem fails, the reason for the failure is identified and remembered in order to avoid the same mistake in the future.
  • CBR favor learning from experience, because it is easier to learn by retaining a concrete problem solving experience, than generalizing from it.
  • Effective learning in CBR requires a well worked methods in order to:
    • Extract relevant knowledge from the experience.
    • Integrate a case into an existing knowledge structure.
    • Index the case for later matching with a similar case.

Combining cases with other knowledge

  • Human learning and problem solving in general are processes that involve the representation and utilization of several types of knowledge, and the combination of several reasoning methods.

Fundamentals of case-based reasoning methods

  • Central tasks to all CBR methods:
    • Identify the current problem situation.
    • Find a past case similar to the new one.
    • Use the case to suggest a solution to the current problem.
    • Evaluate the proposed solution.
    • Update the system by learning from this experience.

Main types of CBR methods

  • The CBR paradigm covers a rage of different methods for organizing, retrieving, and indexing the knowledge retained in the past cases.
  • Exemplar-based reasoning:
    • The term is derived from a concept view (conceptual modeling) called “exemplar view”
    • Exemplar is a specific instance of a certain category, which is used to represent the category.
    • A concept is defined extensionally, as the set of its exemplars.
    • CBR methods that learn concepts are called exemplar-based.
    • Solving a problem is a classification problem by finding the right class for the unclassified exemplar.
    • The class of the most similar past case becomes the solution for the classification problem.
  • Instance-based reasoning:
    • A specialization of the exemplar-based reasoning into a highly syntactic CBR-approach.
    • To overcome the lack of guidance from general background knowledge, a large number of instances are used to go close to the concept definition.
  • Memory-based reasoning:
    • This approach emphasizes a collection of cases as a large memory, and reasoning as a process of accessing and searching this memory.
    • The utilization of parallel processing techniques is a characteristic of this method.
  • Case-based reasoning:
    • Case-based reasoning is sometimes used as a generic term to such systems. A typical case-based reasoning methods have some characteristics that distinguish them from other methods.
      • A typical case is usually assumed to have a certain degree of richness of information contained in it.
      • A certain complexity with respect to its internal organization.
      • Case-based methods are able to modify, or adapt a retrieved solution when applied in different problem solving context.
  • Analogy-based reasoning:
    • The analogy-based reasoning is sometimes used as a synonym to typical case-based reasoning.
    • The term can be used to characterize methods that solve new problems based on past cases from a different domain. While typical case-based methods focus on using past cases from the same domain.
    • Research on analogy reasoning is therefore a subfield concerned with mechanisms for identification and utilization of cross-domain analogies.
    • The major focus of study has been on the reuse of past, that is the mapping of a solution from an identified analogy (source) to the present problem (target).

A descriptive framework

Description of the CBR methods and system has two main parts:

  • A process model of the CBR cycle
    • A dynamic model that identifies the main sub-process of a CBR cycle, their interdependency and products
  • A task-method structure for CBR
    • A task-oriented view, where a task decomposition and related problem solving methods are described.

The CBR Cycle

  1. Retrieve the most similar case or cases.
  2. Reuse the information and knowledge in that case to solve the problem.
  3. Revise the proposed solution.
  4. Retain the parts of this experience likely to be useful for future problem solving.

 

  • An initial description of a problem defines a new case.
  • This new case is used to retrieve a case from the previous cases.
  • The new case and the retrieved case are combined in a solved case through reuse which forms an initial solution to the problem.
  • Through revise the solution tested for success by being tested in the real environment, and repaired if failed.
  • During retain the useful experience is retained for future use, and the case base is updated with the new learned case, or a modification of the existing cases.
  • General domain-dependant knowledge supports the CBR process, this support vary from very weak (may be none) to very strong depending on the CBR method used.

A hierarchy of CBR tasks

  • This is a task-oriented view to the CBR model which gives a description for the detailed mechanisms from the CBR perspective, while the process model gives a global, external view to what is happening.
  • A system is viewed as agent which has goals, and means to achieve this goals.
  • A description to the system can be made from 3 perspectives: tasks, methods, and domain knowledge model.
  • Tasks are set up by the system goals, and a task is performed by applying one or more methods.
  • For a method to accomplish a task, it needs a general knowledge about the application domain as well as information about the current problem and its context.
  • A method is an algorithm that identifies and controls the execution of subtasks, it accesses and utilize the information needed to accomplish this.

CBR Problem Areas

  • In AI, there are no universal CBR methods for all application domains.
  • The challenge in CBR is to come up with methods that are suited for problem solving and learning in a subject domain (e.g Medical), and for a particular application environments (e.g Heart failure diagnosis).
  • Core problems address by CBR research can be grouped into 5 areas, a solution to them constitute a CBR method:
    • Knowledge representation.
    • Retrieval methods.
    • Reuse methods.
    • Revise methods.
    • Retain methods.

Representation of Cases

  • A case-based reasoned is heavily dependent on the structure and content of its collection of cases, refereed as case memory.
  • Problem solving is achieved by recalling a previous experience suitable for solving the current new problem, so the case matching and retaining process should be effective and efficient enough.
  • Problems in case representation:
    • Deciding what to store in a case.
    • Finding an appropriate structure for describing the case content.
    • Deciding how the case memory (case-base) should be organized and indexed for fast retrieval and reuse.
    • How to integrate the case memory into a model of general domain knowledge.

The Dynamic Memory Model

  • In dynamic memory model, the case memory is organized in hierarchical structure of ‘episodic memory organization packets’ also known as generalized episodes.
  • The basic idea is to organize specific cases which share similar properties under a more general structure (generalized episodes).
  • A generalized episodes (GE) contains 3 different objects:
    • Norms: features common to all cases indexed under the GE.
    • Indices: features which discriminate between GE`s cases.
    • Cases
  • An index may point to a more specific GE or to a case.

 

  • Case retrieval
    • When a new case description is given, the input case structure is pushed down the network structure starting from the root.
    • When one or more features of a case match the norms of a GE, the case is further discriminated based on the remaining features.
    • The case with the most common features with the input case is used.
    • As overall:
      • Case retrieval is done by finding the GE with the norms in common with problem description.
      • Indices under the GE are then traversed in order to find the case which contains most of the additional problem features not found in the GE norms.
  • Case retaining
    • It is the same as retrieval in the search method.
    • During storing a new case, when a feature of the new case matches the feature of an existing case, a GE is created and the 2 cases are discriminated under the created GE with different indices.
    • So if during case storage two cases or GEs end under the same index, a new GE is created for them.
    • As overall:
      • Storing a new case is done as the case retrieval, with the additional process of dynamically creating GEs.
  • So the memory structure is dynamic in the sense that similar features of two cases are generalized in a GE, and the cases are indexed under the GE by their different features.
  • The index structure may lead to an explosive growth of indices with increased number of cases.
  • The primary role of a generalized episode is an indexing structure for matching and retrieval of cases.
  • This knowledge organization structure is suitable for learning general and specific knowledge, and it is a simplified model of human reasoning and learning.

The Category and Exemplar Model

  • Cases are referred to as exemplars.
  • The view of this method is that the ‘real world’ natural concept should be defined extensionally.
  • Different features are assigned different importance in describing a case membership to a category.
  • The case-memory is structured as a network of categories, cases, and index pointers.
  • Each case is associated with a category, and each case is stored according to its prototypicality strength to its category.
  • Features are key-value pair.
  • Indices are of three kinds:
    • Feature links: pointing from a feature to cases or categories.
    • Difference links: pointing from a case to its neighbor that differs in only a few numbers of features.
    • Case links: pointing from a category to its associated case (called exemplar links).

 

  • In this organization, the categories are linked within a semantic network, which also contains features and intermediate states.
  • Case retrieval
    • Finding a case in the case base that matches an input description is done by combining the input features of the problem case into a pointer to a case or category that shares most of the features.
    • If a pointer points to a category, the links to its strongest prototypical exemplar are traversed, and these cases are returned.
    • General domain knowledge is used to match cases semantically.
  • Case retaining
    • A new case is stored by searching for a matching case.
    • If a case is found with only minor differences to the input case, the new case may not be retained, or the two cases may be merged.

Case Retrieval

  • The retrieval task starts with a problem description, and ends when a best matching previous case has been found.
  • Subtasks of case retrieval:
    • Identify Features: it is about coming up with a set of relevant problem descriptors.
    • Initially match: return a set of cases that are sufficiently similar to the new cases, given a threshold for case similarity.
    • Search
    • Select: works on the initial set of cases to find out the best match.
  • Some case-based reasoners retrieve a previous case based on superficial(apparent), syntactical similarities among problem descriptors(features). Others retrieve a previous cases based on features that have deeper, semantical similarities.
  • Semantical similarities:
    • In order to retrieve a case based on semantic similarities and relative importance of features, an extensive body of general domain knowledge is required to say how 2 cases match and how strong is the match.
    • It is referred as “knowledge extensive” approach, and it is able to use the contextual meaning for the problem description in matching.
    • For domains where general domain knowledge is available.
  • Syntactical similarities:
    • It is referred as “knowledge poor” approach.
    • For domains where general domain knowledge is very difficult or impossible.
  • It is important to know the purpose of the retrieval task, If the purpose is to be adapted for reuse then this can be accounted for in the retrieval method.
  • Identify Feature
    • Can be done by simply noticing the input features, but a more elaborate way is to understand the problem within its context.
    • Unknown features may be disregarded or requested for explanation by the user.
    • Understanding a problem involves:
      • Filtering noisy problem features (ignore ineffective features).
      • Infer relevant problem features (values of effective features).
      • Check whether the feature values make sense within the problem context.
      • Expect feature values not provided as input.
    • Inferring the values of not provided features can be done by using general knowledge model, or by retrieving a similar case from the case-base and use its features as the expected features.
      • Example on such feature expectation: previous case-1 has the value of feature A, B and C. I have inferred values A and B for the new case, and if the new case and case-1 match in A, and B then I can infer that the value of C in the new case is as of case-1.
  • Initially Match
    • The task of finding a good match is about finding a set of good candidate cases, then from this set of cases, find the best matching one (Select task).
    • The idea of matching is to use the input features as indices to the case-memory in a direct or indirect way. (there should be a mapping function).
    • The 3 principles of indexing:
      • Follow a direct index pointer from the input features to the case-base. (direct mapping).
      • Searching an index structure.
      • Search in a model of general domain knowledge. (search is guided by the underlying model of the domain).
    • Some systems combine between the 3 principles of indexing to achieve a certain goal.
    • Cases may be retrieved directly from input features, or from inferred features from the input.
    • Cases with the most matching features are a good candidates, but sometimes cases matching a fraction of features may be retrieved depending on the retrieval strategy.
    • If case is retrieved on the basis of a subset of features, a relevance test should be done. This test is about finding whether the retrieved solution is of the type as the expected solution for the new problem.
    • Similarity assessment can be more knowledge-intensive by understand the problem in its context more deeply and use the goals, constraints, etc to guide the matching.
    • Another option is to weight the features according to their importance in categorizing the problem.
  • Select
    • The best matching is done by evaluating the degree of initial match more closely.
    • This is done by attempt to generate explanations to justify non-identical features based on the knowledge in the semantic network.
    • If a match is not strong enough, the difference link between cases is followed to reach the best matching case.
    • The selection typical process is to generate consequences and expectations from each retrieved case, and attempts to evaluate consequences and justify expectations.
    • This generation, evaluation and justification of consequences and expectation are based on model of general domain knowledge, or by asking the user.
    • Rankings are made for the cases using some metric or ranking criteria.
    • Knowledge-intensive selection methods generate explanations that support this ranking process.
    • The case with the strongest explanation for being similar to the new case is selected as a solution to the new problem.
    • Other properties in the case that are considered in some CBR systems:
      • Prototypicality of case with its assigned class.
      • Difference links to related cases.
      • Relative importance and discriminately strengths of features.

Case Reuse

  • The retrieval of a previous case solution to be used in the new case context focus on 2 aspects:
    • What parts of the retrieved case should be transferred to the new case.
    • The difference among the past and the current case.
  • Copy
    • In a simple classification task, the differences are abstracted away (ignored), and the similarities are considered relevant.
    • The solution class of the retrieved case is transferred to the new case as its solution.
    • Other systems adapt the retrieved case to the new case context by taking into account the differences, and adaptation of the solution to account for those differences.
  • Adapt
    • There are 2 ways to reuse past cases:
      • Transformational reuse
        • Reuse the past case solution.
        • It doesn’t look how a problem was solved, it focus on the equivalence of solutions.
        • The past case solution is not directly a solution, there exist some knowledge in the form of transformational operator {T} that when applied to the past case solution transform it into a solution for the new case.
        • This requires a strong domain-dependant model in the form of the {T} operator.
      • Derivational reuse
        • Reuse the past methods that constructed the solution.
        • It looks how the problem was solved in the retrieved case.
        • The retrieved method holds information about the methods used for solving the retrieved problem including operators used, sub goals considered, alternatives generated, failed search path, etc…
        • Derivational reuse re-instantiate the retrieved methods to the new case and replays the old plan in the new case context.
        • During replay, the successful alternatives, paths and operators will be explored first, while unsuccessful ones will be avoided.

Case Revision

  • When a case solution generated by the reuse phase is not correct, an opportunity for learning from failure arise.
  • The revision task is divided in 2 subtasks:
    • Evaluate the case solution generated by reuse.
    • If success, then learn and retain it (a separate phase called Retain).
    • If failure, then repair the case solution using domain-specific knowledge.
  • Evaluate Solution
    • Takes the result from applying the reused case in the real environment.
    • Applying a case is a task outside the CBR, this can be done by asking a teacher or by performing it directly in the real world.
    • Results of applying the suggested solution may take time depending on the type of application:
      • In Medical CBR, in diagnosis, a case result may appear after hours, or may be months, so the case must be marked as unevaluated, so that it can be evaluated later when its results are out.
      • A solution may be applied to a model of the domain, using simulation program.
  • Repair Fault
    • Involves detecting the errors of the current solution and retrieving or generating explanation for them.
    • Failure detection in CHEF system:
      • Casual knowledge is used to generate explanations of why goals of the solution plan where not achieved.
      • Learns the general situations that will cause the failures using explanation-based system.
      • These learnt general situations are used during the reuse phase, to predict the shortcomings of using a certain solution plan.
      • This allows for early detection of errors so that they can be predicted, avoided and handled.
    • Solution repair task:
      • uses the explanations to modify the solution in such a way that failures don’t occur.
    • Solution repair in CHEF system:
      • Failed plan is corrected by a repair module, that adds steps to the plan that will assure that the causes of the errors will not occur.
      • The repair module possesses domain-knowledge about how to compensate or disable the cause of errors in the domain.
    • The revised plan can be retained directly if approved to be successful by the revise module or it can be repaired and revised again.

Case Retainment – Learning

  • It is the process of incorporating what is useful to retain from the new problem solving episode in the existing knowledge.
  • The learning from success or failure from the proposed solution is triggered by the result of the evaluation and possible repairs.
  • Involves selecting which information from the case to retain, in what form to retain it, how to index the case for later retrieval for similar problems, and how to integrate the new case in the memory structure.
  • Extract
    • In CBR the case base is updated no matter how the problem was solved.
    • If it was solved by the use of a previous case, then a new case may be built, or the used case for solution can be generalized to include the new case.
    • If the problem was solved without using a previous case, by asking the user may be, then an entirely new case should be created.
    • It is important to know what to use as the source of learning?
      • Relevant problem descriptors (features) and problem solutions are good candidates.
      • Sometimes it is required to include in the new case the explanation of why a solution is a solution for a problem.
      • In some systems:
        • Explanations are included in the retained case, and they are used in later modification of the solution.
        • The explanation structure is used to search up the model for other states that explains the input data of the new case, and look for the causes of this states as answer to the new problem.
        • This focuses the search and speeds up the explanation process, compared to searching in the entire domain model.
      • The last thing that can be extracted for learning is the problem solving method.
    • Failures recognized from the revise task, can be extracted and retained, either as a separate failure case, or within total problem cases.
    • When a failure is encountered, the system gets a reminding to a similar failure case, and uses it to improve its understanding of the failure causes.
  • Index
    • It is a central and much focused problem in case-based reasoning.
    • It is about deciding what type of indices to use for future retrieval, and how to structure the search space of indices.
    • Direct indices skips the structuring of the indices search space, however, the type of indices used should be identified.
    • A trivial solution is to use all the input features as indices.
    • In memory-based reasoning, all the cases are matched in parallel on the relevant features, the cases with the few features in common are filtered out.
  • Integrate
    • It is the final step of updating the knowledge base with new case knowledge.
    • Modifying the indexing of the current cases improves the CBR system, and allows it to become a better similarity assessor.
    • Index strengths or importance relevant to the case are adjusted due to the success or failure of using the case to solve the input problem.
    • Features that are judged as relevant to the case their association with the case is strengthened, while weaken of those that lead to unsuccessful cases.
    • In PATDEX system:
      • There is a relevance matrix that links features to the diagnosis (problem solutions) for which they are relevant, this matrix represents the weights of such links, these weights are strengthened or weakened based on the feedback of success or failure.
    • In knowledge intensive-CBR approaches:
      • Learning can take place within the general conceptual knowledge model.
      • The system incrementally refines and extends its general domain knowledge model.
    • The case just learnt can be tested by re-entering initial problem to the system, and finds whether the system will behave as expected.

Integrated approaches

  • Most CBR systems use general domain knowledge in addition to the knowledge represented by cases.
  • The overall architecture of CBR system has to decide interactions between the CBR method and the other components.
  • CASEY system:
    • It integrates model-based casual reasoning in the diagnosis, when the case-based method fail to find a correct solution, the mode-based method is executed to find a solution, the solution is then stored as a new case for future use. Because the model-based method is complex and slow, the case-based method represents a speed up in reasoning when it can.
  • BOLERO system:
    • It integrates a rule-based system (base-level) with a case-based planner(meta-level).
    • The base-level contains domain knowledge, while the meta-level contains strategic knowledge.
    • The case-based planner is used to control the space searched by the base-level achieving a speed up.
    • The control is passed to the meta-level whenever a new information is know by the base-level assuming that the system will able to deduce a better strategic plan based on the new information.

Example applications and tools

  • Application
    • The CBR used because the knowledge needed to perform the task resides in the head of few people.
    • There is no theory, and very few generally applicable schemes for doing this job.
    • Building up experience in the form of previously successful and unsuccessful situations is important.


Follow

Get every new post delivered to your Inbox.