Data Structure and Algorithms

Array

Why not use Arrays for Everything?
1. In unordered array the insertion is fast Q(1), but search takes slow O(N) time.
2. In ordered array, you can search quickly, in O(logN) time, but insertion takes O(N) time.
For both above kinds, the deletion takes O(N) time

Another problem with arrays is that their size is fixed when they are first created with new.

Simple Sorts

Bubble sort
Bubble sort makes about Square(N)/2 comparisons. Both swaps and comparisons are proportional to  N². Bubble sort runs in  O(N²)  time.

Selection Sort
The Selection sort improves on bubble sort by reducing the number of swaps necessary from  O(N²)  to O(N). Unfortunately, the number of comparisons remains  O(N²).  

Insertion Sort
Insertion sort executes twice as fast as bubble sort and somewhat faster that selection sort in normal situation. Insertion Sort runs  in O(N²) for random data. For data already sorted (O(N)) or almost sorted, the insertion sort does much better. However, for data, that is reverse sorted, this runs no faster that bubble sort.


Comparisons of simple sorts

There’s probably no point in using the bubble sort, unless you don’t have your algorithm book handy. The bubble sort is so simple that you can write it from memory. Even so, it’s practical only if the amount of data is small.


The selection sort minimizes the number of swaps, but the number of comparisons is still high. This sort might be useful when the amount of data is small and swapping data items is very time-consuming compared with comparing them.


The insertion sort is the most versatile of the three and is the best bet in most situations, assuming the amount of data is small or the data is almost sorted. For larger amounts of data, quicksort is generally considered the fastest approach;


We’ve compared the sorting algorithms in terms of speed. Another consideration for any algorithm is how much memory space it needs. All three of the algorithms in this chapter carry out their sort in place, meaning that, besides the initial array, very little extra memory is required. All the sorts require an extra variable to store an item temporarily while it’s being swapped.


Stacks and Queues

There are basically three operations that can be performed on stacks . They are 1) inserting an item into a stack (push). 2) deleting an item from the stack (pop). 3) displaying the contents of the stack(pip).

Below are some of operations a stack data type normally supports:
Push, pop, top, isempty, isfull, get-size,
All operations except get-size() can be performed in  time. get-size() runs in at worst 

Queue, Circular queue.
As with stacks, items can be inserted and removed from a queue in O(1) time. 

Deques

A deque is a double-ended queue. You can insert items at either end and delete them from either end. The methods might be called insertLeft() and insertRight(), and removeLeft() and removeRight().


Priority Queue
A de

Linked list
double ended list

Shell sort run in about O(N*(logN)²⁾ The Shellsort is good for medium-sized arrays, perhaps up to a few thousand items, depending on the particular implementation. 

- What is Gap sequence

Quick sort in about O(N*logN) time

Red-Black Rules
1. Every node is either red or black.
2. The root is always black.

3. If a node is red, its children must be black (although the converse isn’t necessarily true).
4. Every path from the root to a leaf, or to a null child, must contain the same number of black nodes.

The number of black nodes on a path from root to leaf is called the black height.

Fixing Rule Violations

• You can change the colors of nodes.
• You can perform rotations.

Color Flips on the Way Down

Here’s the rule: Every time the insertion routine encounters a black node that has two red children, it must
change the children to black and the parent to red (unless the parent is the root, which always remains black).

Like ordinary binary search trees, a red-black tree allows for searching, insertion, and deletion in O(log2N) time.



Hash Tables

A hash table is a data structure that offers very fast insertion and searching. Hash tables are significantly faster than trees, which, as we learned in the preceding chapters, operate in relatively fast O(logN) time. Not only are they fast, hash tables are relatively easy to program.


Hash tables do have several disadvantages. They’re based on arrays, and arrays are difficult to expand after they’ve been created. For some kinds of hash tables, performance may degrade catastrophically when a table becomes too full, so the programmer needs to have a fairly accurate idea of how many data items will need to be stored (or be prepared to periodically transfer data to a larger hash table, a time-consuming process). Also, there’s no convenient way to visit the items in a hash table in any kind of order
However, if you don’t need to visit items in order, and you can predict in advance the size of your database, hash tables are unparalleled in speed and convenience.

Open Addressing

• Linear Probing
• Quadratic Probing
• Double Hashing

The ratio of the number of items in a table to the table’s size is called the load factor.

Double Hashing
Experience has shown that this secondary hash function must have certain characteristics:

• It must not be the same as the primary hash function.
• It must never output a 0 (otherwise, there would be no step; every probe would land on the same cell, and the algorithm would go into an endless loop).

Experts have discovered that functions of the following form work well:
stepSize = constant - (key % constant); where constant is prime and smaller than the array size.

Double hashing requires that the size of the hash table is a prime number.

Separate Chaining

In open addressing, performance degrades badly as the load factor increases above one-half or two-thirds. In separate chaining the load factor can rise above 1 without hurting performance very much. This makes separate chaining a more robust mechanism, especially when it’s hard to predict in advance how much data will be placed in the hash table.


Another approach similar to separate chaining is to use an array at each location in the hash table, instead of a linked list. Such arrays are sometimes called buckets.

Hash Functions
Quick Computation
Random Keys
Use a Prime Number for the Modulo Base










Miscellaneous 
1. Insertion sort is preferable to quicksort for small files and for almost-sorted files.
2. Some sorting algorithm that retains secondary order is said to be stable

Programming Applications for Microsoft Windows

Thread Synchronization with Kernel Objects

Event Kernel Objects

When a manual-reset event is signaled, all threads waiting on the event become schedulable. When an auto-reset event is signaled, only one of the threads waiting on the event becomes schedulable.

Waitable Timer Kernel Objects

Semaphore Kernel Objects

They contain a usage count, as all kernel objects do, but they also contain two additional signed 32-bit values: a maximum resource count and a current resource count.

The rules for a semaphore are as follows

·         If the current resource count is greater than 0, the semaphore is signaled.

·         If the current resource count is 0, the semaphore is nonsignaled.

·         The system never allows the current resource count to be negative.

·         The current resource count can never be greater than the maximum resource count.

When you use a semaphore, do not confuse the semaphore object's usage count with its current resource count.

Test-and-set operation is done atomically; that is, when you request a resource from a semaphore, the operating system checks whether the resource is available and decrements the count of available resources without letting another thread interfere

There is just no way to get the current resource count of a semaphore without altering it.

Mutex Kernel Objects

A mutex object contains a usage count, a thread ID, and a recursion counter.

The rules for a mutex are as follows:

·         If the thread ID is 0 (an invalid thread ID), the mutex is not owned by any thread and is signaled.

·         If the thread ID is nonzero, a thread owns the mutex and the mutex is nonsignaled

·         Unlike all the other kernel objects, mutexes have special code in the operating system that allows them to violate the normal rules.

o   The system checks to see whether the thread attempting to acquire the mutex has the same thread ID as recorded inside the mutex object. If the thread IDs match, the system allows the thread to remain schedulable—even though the mutex was nonsignaled.

o   When a mutex becomes abandoned, the system automatically resets the mutex object's thread ID to 0 and its recursion counter to 0.

Other Thread Synchronization Functions

WaitForInputIdle

This function waits until the process identified by hProcess has no input pending in the thread that created the application's first window.

SignalObjectAndWait

The SignalObjectAndWait function signals a kernel object and waits on another kernel object in a single atomic operation:

Thread Pooling

The new thread pooling functions let you do the following:

·         Call functions asynchronously

·         Call functions at timed intervals

·         Call functions when single kernel objects become signaled

·         Call functions when asynchronous I/O requests complete

To accomplish these tasks, the thread pool consists of four separate components. Table 11-1 shows the components and describes the rules that govern their behavior.

Table 11-1. Thread pool components and their behavior

Component
	Timer	Wait	I/O	Non-I/O
Initial Number of Threads	Always 1	1	0	0
When a Thread Is Created	When first thread pool timer function is called	One thread for every 63 registered objects	The system uses heuristics, but here are some factors that affect the creation of a thread: Some time (in seconds) has passed since the thread was added The WT_EXECUTELONGFUNCTION flag is used The number of queued work items exceeds a certain threshold
When a Thread is Destroyed	When a process terminates	When the number of registered wait objects is 0	When the thread has no pending I/O requests and has been idle for a threshold period (about a minute)	When the thread is idle for a threshold period (about a minute)
How a Thread Waits	Alertable	WaitForMultipleObjectsEx	Alertable	GetQueuedCompletionStatus
What Wakes Up a Thread	Waitable timer is signaled queuing a user APC	Kernal object becomes signaled	Queued user APC or completed I/O request	Posted completion status or completed I/O request (The completion port allows at most 2 * number of CPUs threads to run concurrently)

Windows Memory Architecture

How a Virtual Address Space Is Partitioned

·         NULL-Pointer Assignment

·         DOS/16-bit Windows Application Compatibility

·         User-Mode

·         64-KB Off-Limits (Windows 2000 Only)

·         Shared Memory-Mapped File (MMF)(only Windows 98)

·         Kernel-Mode

Using the /3GB switch reduces the number of threads, stacks, and other resources that the system can create. In addition, the system can only use a maximum of 16 GB of RAM vs. the normal maximum of 64 GB because there isn't enough virtual address space in kernel mode to manage the additional RAM.

when you invoke an application, the system opens the application's .exe file and determines the size of the application's code and data. Then the system reserves a region of address space and notes that the physical storage associated with this region is the .exe file itself. That's right—instead of allocating space from the paging file, the system uses the actual contents, or image, of the .exe file as the program's reserved region of address space. This, of course, makes loading an application very fast and allows the size of the paging file to remain small.

Protection Attributes

you should not pass either PAGE_WRITECOPY or PAGE_ EXECUTE_WRITECOPY when you are reserving address space or committing physical storage using the VirtualAlloc function. Doing so will cause the call to VirtualAlloc to fail; calling GetLastError returns ERROR_ INVALID_PARAMETER. These two attributes are used by the operating system when it maps .exe and DLL file images.

Special Access Protection Attribute Flags

·         PAGE_NOCACHE : it exists mostly for hardware device driver developers who need to manipulate memory buffers

·         PAGE_WRITECOMBINE : is also for device driver developers. It allows multiple writes to a single device to be combined together in order to improve performance

·         PAGE_GUARD : allows an application to receive a notification (via an exception) when a byte on a page has been written to.

The Importance of Data Alignment

you can still tell the system to silently correct misaligned data accesses for all threads in your process by having one of your process's threads call the SetErrorMode (SEM_NOALIGNMENTFAULTEXCEPT) function.

Changing this flag affects all threads contained within the process that owns the thread that makes the call.

You should also note that a process's error mode flags are inherited by any child processes. Therefore, you might want to temporarily reset this flag before calling the CreateProcess function (although you usually don't do this).

For x86 systems, this flag is always on and cannot be turned off. For Alpha systems, you can turn this flag off only if the EnableAlignmentFaultExceptions registry value is set to 1.

Microsoft's C/C++ compiler for the Alpha supports a special keyword called _ _unaligned

You use the _ _unaligned modifier just as you would use the const or volatile modifiers except that the _ _unaligned modifier is only meaningful when applied to pointer variables. When you access data via an unaligned pointer, the compiler generates code that assumes that the data is not aligned properly and adds the additional CPU instructions necessary to access the data.

the _ _unaligned keyword is not supported by the x86 version of the Visual C/C++ compiler.

So, if you are trying to create a single source code base for your application, you'll want to use the UNALIGNED macro instead of the _ _unaligned keyword.

Exploring Virtual Memory

System Information

The GetSystemInfo function retrieves the values relevant to the host machine.

Virtual Memory Status

A Windows function called GlobalMemoryStatus retrieves dynamic information about the current state of memory

If you anticipate that your application will run on machines with more than 4 GB of RAM or if the total swap file size might be larger than 4 GB, you may want to use the new GlobalMemoryStatusEx function:

Determining the State of an Address Space

function is called VirtualQuery

Windows also offers a function that allows one process to query memory information about another process: VirtualQueryEx

Using Virtual Memory in Your Own Applications

Windows offers three mechanisms for manipulating memory:

·         Virtual memory, which is best for managing large arrays of objects or structures

·         Memory-mapped files, which are best for managing large streams of data (usually from files) and for sharing data between multiple processes running on a single machine

·         Heaps, which are best for managing large numbers of small objects

Reserving a Region in an Address Space

You reserve a region in your process's address space by calling VirtualAlloc:

System rounds that address down to a multiple of 64 KB

You cannot use the protection attribute flags PAGE_GUARD, PAGE_NOCACHE, or PAGE_WRITECOMBINE when reserving regions—they can be used only with committed storage.

Committing Storage in a Reserved Region

you can specify a different protection attribute than the ones used at the time of reserving

Decommitting Physical Storage and Releasing a Region

Call the VirtualFree function

When releasing a region, you must release all the address space that was reserved by the region.

You must pass 0 for the dwSize parameter or the call to VirtualFree will fail.

Changing Protection Attributes

You can alter the protection rights of a page of memory by calling VirtualProtect:

flNewProtect can represent any one of the PAGE_* protection attribute identifiers except for PAGE_WRITECOPY and PAGE_EXECUTE_WRITECOPY.

Address Windowing Extensions (Windows 2000 only)

Microsoft had two goals when creating AWE:

·         Allow applications to allocate RAM that is never swapped by the operating system to or from disk.

·         Allow an application to access more RAM than fits within the process's address space.

One limitation of AWE is that all storage mapped to the address window must be readable and writable.

A Thread's Stack

By default, the system reserves 1 MB of address space and commits 2 pages of storage.

Memory-Mapped Files

Injecting a DLL Using Remote Threads

Injecting a DLL with a Trojan DLL

Injecting a DLL as a Debugger

Injecting Code with CreateProcess

Termination Handlers

With SEH, you can separate the main job from the error-handling chores.

Don't confuse structured exception handling with C++ exception handling. C++ exception handling is a different form of exception handling, a form that makes use of the C++ keywords catch and throw. Microsoft's Visual C++ also supports C++ exception handling and is implemented internally by taking advantage of the structured exception handling capabilities already present in the compiler and in Windows operating systems.

SEH really consists of two main capabilities: termination handling and exception handling.

A termination handler guarantees that a block of code (the termination handler) will be called and executed regardless of how another section of code (the guarded body) is exited.

The _ _try and _ _finally keywords delineate the two sections of the termination handler.

A call to ExitThread or ExitProcess will immediately terminate the thread or process without executing any of the code in a finally block.

Code in a finally block always starts executing as a result of one of these three situations

·         Normal flow of control from the try block into the finally block

·         Local unwind: premature exit from the try block (goto, longjump, continue, break, return, and so on) forcing control to the finally block

·         a global unwind—occurred without explicit identification

To determine which of the three possibilities caused the finally block to execute, you can call the intrinsic function  AbnormalTermination:

This intrinsic function can be called only from inside a finally block and returns a Boolean value indicating whether the try block associated with the finally block was exited prematurely.

It is impossible to determine whether a finally block is executing because of a global or a local unwind

Exception Handlers and Software Exceptions

Whenever you create a try block, it must be followed by either a finally block or an except block. A try block can't have both a finally block and an except block, and a try block can't have multiple finally or except blocks. However, it is possible to nest try-finally blocks inside try-except blocks and vice versa.

Unlike termination handlers (discussed in the previous chapter), exception filters and exception handlers are executed directly by the operating system—the compiler has little to do with evaluating exception filters or executing exception handlers.

When this exception is raised, the system will locate the beginning of the except block and evaluate the exception filter expression, an expression that must evaluate to one of the following three identifiers

-          EXCEPTION_EXECUTE_HANDLER

-          EXCEPTION_CONTINUE_SEARCH

-          EXCEPTION_CONTINUE_EXECUTION

EXCEPTION_EXECUTE_HANDLER

The system performs a global unwind,jumps to the code inside the except block. After the code inside the except block finishes executing, control resumes at the first instruction after the except block.

Global Unwinds

When an exception filter evaluates to EXCEPTION_EXECUTE_HANDLER, the system must perform a global unwind. The global unwind causes all of the outstanding try-finally blocks that started executing below the try-except block that handles the exception to resume execution.

Halting Global Unwinds

It's possible to stop the system from completing a global unwind by putting a return statement inside a finally block. It means that the code inside exception block is not executed.

EXCEPTION_CONTINUE_EXECUTION

When the system sees EXCEPTION_CONTINUE_EXECUTION, it jumps back to the instruction that generated the exception and tries to execute it again.

EXCEPTION_CONTINUE_SEARCH

This identifier tells the system to walk up to the previous try block that's matched with an except block and call this previous try block's exception filter.

Any try blocks that are matched with finally blocks instead of except blocks are skipped by the system while it walks up the chain. The reason for this should be pretty obvious: finally blocks don't have exception filters and therefore give the system nothing to evaluate.

GetExceptionCode

The GetExceptionCode intrinsic function can be called only in an exception filter (between the parentheses following _ _except) or inside an exception handler.

You cannot call GetExceptionCode from inside an exception filter function.

GetExceptionInformation

When an exception occurs, the operating system pushes the following three structures on the stack of the thread that raised the exception:

-          EXCEPTION_RECORD structure

-          CONTEXT structure

-          EXCEPTION_POINTERS structure

GetExceptionInformation  can be called only in an exception filter. Once control has been transferred to the exception handler, the data on the stack is destroyed.

Software Exceptions

You simply call RaiseException to raise a software exception.

Unfortunately, most developers do not get into the habit of using exceptions for error handling.

There are two basic reasons for this. The first reason is that most developers are unfamiliar with SEH. Even if one developer is acquainted with it, other developers might not be. If one developer writes a function that raises an exception but other developers don't write SEH frames to trap the exception, the process will be terminated by the operating system.

The second reason why developers avoid SEH is that it is not portable to other operating systems. Many companies target multiple operating systems and would like to have a single source code base for their products, which is certainly understandable. SEH is a Windows-specific technology.

Unhandled Exceptions and C++ Exceptions

Windows offers another function, SetUnhandledExceptionFilter, which allows you to wrap all your thread functions in an SEH frame:

The UnhandledExceptionFilter function is a fully documented Windows function that you can call directly from within your own code.

C++ Exceptions Versus Structured Exceptions

If you're writing a C++ application, you should use C++ exceptions instead of structured exceptions. The reason is that C++ exceptions are part of the language and therefore the compiler knows what a C++ class object is. This means that the compiler automatically generates code to call C++ object destructors in order to guarantee object cleanup.

C++ exceptions can never be re-executed, and it would be an error for a filter diagnosing a C++ exception to return EXCEPTION_CONTINUE_EXECUTION.

Catching Structured Exceptions with C++

Window Messaging

The thread that creates a window must be the thread that handles all messages for the window.

This also means that every thread that creates at least one window is assigned a message queue by the system.

A Thread's Message Queue

When a thread is first created, the system assumes that the thread will not be used for any user interface_related tasks. This reduces the system resources required by the thread. However, as soon as the thread calls a graphical UI-related function (such as checking its message queue or creating a window) the system automatically allocates some additional resources for the thread so that it can perform its UI-related tasks. Specifically, the system allocates a THREADINFO structure and associates this data structure with the thread.

The THREADINFO structure is an internal, undocumented data structure that identifies the thread's posted-message queue, send-message queue, reply- message queue, virtualized-input queue, and wake flags, as well as a number of variables that are used for the thread's local input state.

Posting Messages to a Thread's Message Queue

When a thread calls PostMessage function, the system determines which thread created the window identified by the hwnd parameter.

You can determine which thread created a window by calling GetWindowThreadProcessId

PostQuitMessage doesn't really post a message to any of the THREADINFO structure's queues. Internally PostQuitMessage just turns on the QS_QUIT wake flag (which I'll discuss later) and sets the nExitCode member of the THREADINFO structure.

Sending Messages to a Window

Here is how SendMessage works. If the thread calling SendMessage is sending a message to a window created by the same thread, SendMessage is simple: it just calls the specified window's window procedure as a subroutine. When the window procedure is finished processing the message, it returns a value back to SendMessage. SendMessage returns this value to the calling thread.

However, if a thread is sending a message to a window created by another thread, the internal workings of SendMessage are far more complicated.

Your thread is suspended while the other thread is processing the message. The system must perform the actions discussed next.

First, the sent message is appended to the receiving thread's send-message queue, which has the effect of setting the QS_SENDMESSAGE flag for that thread.

Second, if the receiving thread is already processing a message, system will not interrupt it. And when it is waiting for messages, the system first checks to see whether the QS_SENDMESSAGE wake flag is set, and if it is, the system scans the list of messages in the send-message queue to find the first sent message. It is possible that several sent messages could pile up in this queue.

While the receiving thread is processing the message, the thread that called SendMessage is sitting idle, waiting for a message to appear in its reply-message queue.

SendNotifyMessage places a message in the send-message queue of the receiving thread and returns to the calling thread immediately.

SendNotifyMessage differs from PostMessage in two ways.

1.       Sent message has higher priority than the posted message.

2.       It works same as SendMessage if the Window is created by the calling thread.

ReplyMessage is called by the thread receiving the window message. This is to inform the system that Window has completed enough to know the result of the message processing. This needs to be called by the Window Procedure.

ReplyMessage does nothing if you call it while processing a message sent from the same thread.

The function InSendMessage returns TRUE if the thread is processing an interthread sent message and FALSE if it is processing an intrathread sent or posted message.

Waking a Thread

When a thread is running, it can query the status of its queues by calling the DWORD GetQueueStatus(UINT fuFlags) function:

the fuFlags parameter tells GetQueueStatus the types of messages to check for in the queues and result can be found in can be found in the high word of the return value.  The low word indicates the types of messages that have been added to the queue and that haven't been processed since the last call to GetQueueStatus, GetMessage, or PeekMessage.

The Algorithm for Extracting Messages from a Thread's Queue

When a thread calls GetMessage or PeekMessage, the system examines the state of thread’s  queue status  flags and determine which message should be processed.

1.        

WI - Security

Key requirements for C2 security rating
- A Secure logon facility
- Discretionary access control
- Security Auditing
- Object reuse protection

Windows also meets two requirements of B-level security
- Trusted path functionality (Ctrl+Alt+Del)
- Trusted facility management

2 Security System Components

These are the core components and databases that implement Windows Security

1. Security reference monitor (SRM) that is responsible for defining the access token data structure to represent a security context, performing security access checks on objects, manipulating priviledges (user rights), and generating any resulting security audit messages.

2. Local security authority subsystem (lsass) is responsible for local system security policy, user authentication, and sending security audit messages to the Event log.

3. Lsass policy database. A database that contains the local system security policy settings, this is stored in HKLM\SECURITY. It includes such information as what domains are entrusted to authenticate logon attempts, who has permission to access the system and how (interactive, network, and service logons), who is assigned which privileges, and what kind of security auditing is to be performed. The Lsass policy database also stores "secrets" that include logon information used for caching domain logons and Windows service user-account logons.

4. Security accounts manager (SAM) service. A set of subroutines responsible for managing the database that contains user names and groups defined on the local machine. The SAM service, which is implemented in samsrv.dll, runs in the Lsass process.

5. SAM database. A database that on systems not functioning as domain controllers contains the defined local users and groups, along with their passwords and other attributes. On domain controllers, the SAM stores the system’s administrator recovery account definition and password. This database is stored in the registry under HKLM\SAM.

6. Active Directory A directory service that contains a database that stores information about objects in a domain. The Active Directory server, implemented as %SystemRoot%\System32\Ntdsa.dll, runs in the Lsass process.

7. Authentication packages These include dynamic-link libraries (DLLs) that run both in the context of the Lsass process and client processes and that implement Windows authentication policy. An authentication DLL is responsible for checking whether a given user name and password match, and if so, returning to the Lsass information detailing the user’s security identity, which Lsass uses to generate a token.

8. Interactive logon manager (Winlogon) A user-mode process running %System-Root%\System32\Winlogon.exe that is responsible for responding to the SAS and for managing interactive logon sessions. Winlogon creates a user’s first process when the user logs on, for example.

9. Logon user interface (LogonUI) A user-mode process that presents users with the user interface they can use to authenticate themselves on the system. Uses credential providers to query user credentials through various methods.

10. Credential providers (CPs) In-process COM objects that run in the LogonUI process (started on demand by Winlogon when the SAS is performed) and used to obtain a user’s name and password, smartcard PIN, or biometric data (such as a fingerprint). The standard CPs are %SystemRoot%\System32\authui.dll and %SystemRoot%\System32\SmartcardCredentialProvider.dll

11. Network logon service (Netlogon) A Windows service (%SystemRoot%\System32\Netlogon.dll) that sets up the secure channel to a domain controller, over which security requests—such as an interactive logon (if the domain controller is running Windows NT 4) or LAN Manager and NT LAN Manager (v1 and v2) authentication validation—are sent.

12. Kernel Security Device Driver (KSecDD) A kernel-mode library of functions that implement the local procedure call (LPC) interfaces that other kernel-mode security components, including the Encrypting File System (EFS), use to communicate with Lsass in user mode. KSecDD is located in %SystemRoot%\System32\Drivers\Ksecdd.sys.

SRM, which runs in kernel mode, and Lsass, which runs in user mode, communicate using ALPC facility.

During system initialization, the SRM creates a port, named SeRmCommandPort, to which Lsass connects. When the Lsass process starts, it creates an ALPC port named SeLsaCommandPort. The SRM connects to this port, resulting in the creation of private communication ports. The SRM creates a shared memory section for messages longer than 256 bytes, passing a handle in the connect call. Once the SRM and Lsass connect to each other during system initialization, they no longer listen on their respective connect ports. Therefore, a later user process has no way to connect successfully to either of these ports for malicious purposes—the connect request will never complete.

3. Protecting Objects

Object protection and access logging is the essence of discretionary access control and auditing. The objects that can be protected on Windows include files, devices, mailslots, pipes (named and anonymous), jobs, processes, threads, events, keyed events, event pairs, mutexes, semaphores, shared memory sections, I/O completion ports, LPC ports, waitable timers, access tokens, volumes, window stations, desktops, network shares, services, registry keys, printers, and Active Directory objects.


The Windows object manager plays a key role in enforcing object security.

3.1 Access Checks

A thread should specify what access its needs on an object, when opened, so that object manager can validate them through SRM.

Mutexes, events, and semaphores rely on default security.

The essence of the SRM's security model is an equation that takes three inputs: the security identity of a thread, the access that a thread wants to an object, and the security settings of the object.

Security Identifiers (SIDs)
Windows uses SIDs. Users have SIDs, and so do local and domain groups, local computers, domains and domain users. It is a 48 bit identifier authority value and a variable number of 32-bit subauthority or relative identifier (RID) values.

The authority value identifies the agent that issued the SID, Subauthority values identify trustees relative to the issuing authority.

RIDs for user accounts and groups start at 1000 and increase in increments of 1 for each new user or group.

Winlogon creates a unique logon SID for each interactive logon session. A typical use of a logon SID is in an access control entry (ACE) that allows access for the duration of a client’s logon session. The SID for a logon session is S-1-5-5-0, and the RID is randomly generated.



Integrity Levels:

integrity levels can override discretionary access to differentiate a process and objects running as and owned by the same user, offering the ability to isolate code and data within a user account.

Every process has an integrity level that is represented in the process's token and propagated according to following rules:
1. A process inherits the integrity level of its parent.
2. If the file object for the executable image to which the child process belongs has an integrity level and the parent's integrity level is medium or higher, the child process will inherit the lower of the two.
3. A parent process can also create child process with an explicit integrity level

Objects also have an integrity level that is stored as part of their security descriptor, in a structure called the mandatory label. The objects have implicit integrity level which is medium.


Apart from an integrity level, objects also have a mandatory policy, which defines the actual level of protection that’s applied based on the integrity level check. Three types are possible, shown in Table below. The integrity level and the mandatory policy are stored together in the same ACE.

Tokens

The SRM uses an object called a token (or access token) to identify the security context of a process or thread. A security context consists of information that describes the privileges, accounts, and groups associated with the process or thread. Tokens also include information such as the session ID, the integrity level, and UAC virtualization state.

The security mechanism in Windows use two components to determine what objects can be accessed and what secure operations can be performed. One component comprises the token's user account SID and group SID fields. The SRM uses SID fields to determine if the process or thread can obtain the requested access to a securable object.
The second component  is the privilege array. A token's privilege array is the list of rights associated with the token.

Token's type distinguishes a primary token from impersonation token. Impersonation tokens carry an impersonation level that signifies what type of impersonation is active in the token.

A token also include a mandatory policy for the process or thread how MIC will behave when processing this token.  There are two policies.
1. TOKEN_MANDATORY_NO_WRITE_UP. It is enabled by default.
2. TOKEN_MANDATORY_NEW_PROCESS_MIN. It is also enabled by default.

The field in a token are immutable.

Impersonation
Thread-control data structure contain optional entry for an impersonation token. However, thread's primary token, which represents the thread's real security credentials, is always accessible in process's control structure.

Restricted Tokens:
Restricted token is created from primary or impersonation token using Create-RestrictedToken function. It is copy of it with following possible modifications.
1. Privileges can be removed from the token's privilege array.
2. SIDs in the token can be marked as deny-only.
3. SIDs in the token can be marked as restricted.

Filtered Admin Token 
A filtered admin token as following characteristics.
1. The integrity level is set to medium.
2. The administrator and administrator like SIDs are marked as deny-only to prevent security holes if the group was removed altogether.
3. All privileges are stripped except Change Notify, Shutdown, Undock, Increase Working Set, and Time Zone.

Security Description and Access Control
Security descriptor is the data structure that specifies who can perform what actions on the object.
Security descriptor consists of following attributes:
1. Revision number: The version number that SRM security model used to create the descriptor.
2. Flags optional modifiers that define the behaviour or characteristics of the descriptor.
3. Owner SID
4. Group SID
5. Discretionary access control list (DACL) specifies who has what access to the object.
6. System access control list (SACL) specifies which operations by which users should be logged in the security audit log and the explicit integrity level of an object.

Access control list (ACL) is made up of a header and zero or more access control entry (ACE) structures. There are two types of ACLs: DACL and SACL. In DACL, each ACE contains a SID and access mask (and set of flags). Eight types of ACEs can appear in DACL.: access allowed, access denied, allowed-object, denied-object, allowed-callback, denied-callback, allowed-object-callback, denied-object-callback.

Accumulation of access rights granted by individual ACEs forms the set of access rights granted by an ACL. If no DACL is present in a security descriptor, everyone has the access to the object. If the DACL empty (that is, it has 0 ACE), no user has access to the object.
The ACEs used in DACL also have a set of  flags that control and specify characteristics  of the ACE related to inheritance.

A SACL contains two types of ACEs: System audit ACEs  and system audit-object ACEs. These ACEs specify which operations performed on the object by specific users or groups should be audited.

If a SACL is null, no auditing takes place on the object.

The inheritance flags that apply to DACL ACEs also apply to system audit and system audit-object ACEs.

To determine which DACL to assign to a new object, the security system uses first applicable rule  of the following assignment rules.

1. If the caller explicitly provides a security descriptor  when the object is created, the security systems applies it to the object. If the object has a name and resides in a container object (for example, a named event object in the \BaseNamedObjects object manager namespace directory), the system merges any inheritable ACEs (ACEs that might propagate from the object’s container) into the DACL unless the security descriptor has the SE_DACL_PROTECTED flag set, which prevents inheritance.

2. If a caller doesn’t supply a security descriptor and the object has a name, the security system looks at the security descriptor in the container in which the new object name is stored. Some of the object directory’s ACEs might be marked as inheritable, meaning that they should be applied to new objects created in the object directory. If any of these inheritable ACEs are present, the security system forms them into an ACL, which it attaches to the new object.

3. If no security descriptor is specified and the object doesn’t inherit any ACEs, the security system retrieves the default DACL from the caller’s access token and applies it to the new object. Several subsystems on Windows have hard-coded DACLs that they assign on object creation

4. If there is no specified descriptor, no inherited ACEs, and no default DACL, the system creates the object with no DACL, which allows everyone (all users and groups) full access to the object. This rule is the same as the third rule in which a token contains a null default DACL.


The rules the system uses when assigning a SACL to a new object are similar to those used for DACL assignment, with some exceptions. The first is that inherited system audit ACEs don’t propagate to objects with security descriptors marked with the SE_SACL_PROTECTED flag (similar to the SE_DACL_PROTECTED flag, which protects DACLs). Second, if there are no specified security audit ACEs and there is no inherited SACL, no SACL is applied to the object. This behavior is different from that used to apply default DACLs because tokens don’t have a default SACL.



The system uses the following rules for propagating inheritable ACEs:
1.If a child object with no DACL inherits an ACE, the result is a child object with a DACL containing only the inherited ACE.
2. If a child object with an empty DACL inherits an ACE, the result is a child object with a DACL containing only the inherited ACE.
3. For objects in Active Directory only, if an inheritable ACE is removed from a parent object, automatic inheritance removes any copies of the ACE inherited by child objects.
4. For objects in Active Directory only, if automatic inheritance results in the removal of all ACEs from a child object’s DACL, the child object has an empty DACL rather than no DACL.


The order of ACEs in an ACL is an important aspect of the Windows security model.

Determining Access
Two methods are used for determining access to an object:
1. The mandatory integrity check, which determines whether the integrity level of the caller is high enough to access the resource, based on the resource’s own integrity level and its mandatory policy.
2. The discretionary access check, which determines the access that a specific user account has to an object.


With the default integrity policy, processes can open any object—with the exception of process, thread, and token objects—for read access as long as the object’s DACL grants them read access.


user interface Privilege isolation (uiPi)

The Windows messaging subsystem also honors integrity levels to implement UIPI. The subsystem does this by preventing a process from sending window messages to the windows owned by a process having a higher integrity level, with the following informational messages being exceptions:
■ WM_NULL
■ WM_MOVE
■ WM_SIZE
■ WM_GETTEXT
■ WM_GETTEXTLENGTH
■ WM_GETHOTKEY
■ WM_GETICON
■ WM_RENDERFORMAT
■ WM_DRAWCLIPBOARD
■ WM_CHANGECBCHAIN
■ WM_THEMECHANGED


After the integrity check is complete, and assuming the mandatory policy allows access to the object based on the caller’s integrity, one of two algorithms is used for the discretionary check to an object, which will determine the final outcome of the access check:


1. One to determine the maximum access allowed to the object, a form of which is exported to user mode with the Windows GetEffectiveRightsFromAcl function. This is also used when a program specifies a desired access of MAXIMUM_ALLOWED, which is what the legacy APIs that don’t have a desired access parameter use.

2. One to determine whether a specific desired access is allowed, which can be done with the Windows AccessCheck function or the AccessCheckByType function.

The first algorithm examines the entries in the DACL as follows:
1. If the object has no DACL (a null DACL), the object has no protection and the security system grants all access.
2. If the caller has the take-ownership privilege, the security system grants write-owner access before examining the DACL.
3. If the caller is the owner of the object, the system looks for an OWNER_RIGHTS SID and uses that SID as the SID for the next steps. Otherwise, read-control and write-DACL access rights are granted.
4. For each access-denied ACE that contains a SID that matches one in the caller’s access token, the ACE’s access mask is removed from the granted-access mask.
5. For each access-allowed ACE that contains a SID that matches one in the caller’s access token, the ACE’s access mask is added to the granted-access mask being computed, unless that access has already been denied.
The preceding description applies only to the kernel-mode form of the algorithm. The Windows version implemented by GetEffectiveRightsFromAcl differs in that it doesn’t perform step 2, and it considers a single user or group SID rather than an access token.

Owner Rights


The Owner Rights SID exists for two main reasons: improving service hardening in the operating system, and allowing more flexibility for specific usage scenarios.


Whenever a service creates an object at run time, the Owner SID associated with that object is the account the service is running in (such as local system or local service) and not the actual service SID. This means that any other service in the same account would have access to the object by being an owner. The Owner Rights SID prevents that unwanted behavior.


The second algorithm is used to determine whether a specific access request can be granted, based on the caller’s access token. Each open function in the Windows API that deals with securable objects has a parameter that specifies the desired access mask, which is the last component of the security equation. To determine whether the caller has access, the following steps are performed:

1. If the object has no DACL (a null DACL), the object has no protection and the security system grants the desired access.
2. If the caller has the take-ownership privilege, the security system grants write-owner access if requested and then examines the DACL. However, if write-owner access was the only access requested by a caller with take-ownership privilege, the security system grants that access and never examines the DACL.



3. If the caller is the owner of the object, the system looks for an OWNER_RIGHTS SID and uses that SID as the SID for the next steps. Otherwise, read-control and write-DACL access rights are granted. If these rights were the only access rights that the caller requested, access is granted without examining the DACL
4. Each ACE in the DACL is examined from first to last. An ACE is processed if one of the following conditions is satisfied:

1. The ACE is an access-deny ACE, and the SID in the ACE matches an enabled SID (SIDs can be enabled or disabled) or a deny-only SID in the caller’s access token. 
2. The ACE is an access-allowed ACE, and the SID in the ACE matches an enabled SID in the caller’s token that isn’t of type deny-only.
3. It is the second pass through the descriptor for restricted-SID checks, and the SID in theACE matches a restricted SID in the caller’s access token.
4. The ACE isn’t marked as inherit-only.

5. If it is an access-allowed ACE, the rights in the access mask in the ACE that were requested are granted; if all the requested access rights have been granted, the access check succeeds. If it is an access-denied ACE and any of the requested access rights are in the denied-access rights, access is denied to the object.

6. If the end of the DACL is reached and some of the requested access rights still haven’t been granted, access is denied.
7. If all accesses are granted but the caller’s access token has at least one restricted SID, the system rescans the DACL’s ACEs looking for ACEs with access-mask matches for the accesses the user is requesting and a match of the ACE’s SID with any of the caller’s restricted SIDs. Only if both scans of the DACL grant the requested access rights is the user granted access to the object.


Because it wouldn’t be efficient for the security system to process the DACL every time a process uses a handle, the SRM makes this access check only when a handle is opened, not each time the handle is used. Thus, once a process successfully opens a handle, the security system can’t revoke the access rights that have been granted, even if the object’s DACL changes. Also keep in mind that because kernel-mode code uses pointers rather than handles to access objects, the access check isn’t performed when the operating system uses objects. In other words, the Windows executive “trusts” itself in a security sense.

The authZ aPi


The AuthZ Windows API implements the same security model as the security reference monitor, but it implements the model totally in user mode in the %SystemRoot%\System32\Authz.dll library. This gives applications that want to protect their own private objects, such as database tables, the ability to leverage the Windows security model without incurring the cost of user-mode to kernel-mode transitions that they would make if they relied on the security reference monitor.

4. Account Rights and Privileges



A privilege is the right of an account to perform a particular system-related operation, such as shutting down the computer or changing the system time. An account right grants or denies the account to which it’s assigned the ability to perform a particular type of logon, such as a local logon or interactive logon, to a computer.

4.1 Account Rights

Account rights are not enforced by the security reference monitor, nor are they stored in tokens.


Windows applications can add and remove user rights from an account by using the LsaAddAccountRights and LsaRemoveAccountRights functions, and they can determine what rights are assigned to an account with LsaEnumerateAccountRights.

4.2 Privileges

Unlike user rights, which are enforced in one place by the LSA, different privileges are defined by different
components and enforced by those components.
Unlike account rights, privileges can be enabled and disabled.

Table of privileges

Privilege	User Right	Privilege Usage
SeAssignPrimaryTokenPrivilege	Replace a process- level token	Checked for by various components, such as NtSetInformationJob, that set a process's token.
SeAuditPrivilege	Generate security audits	Required to generate events for the Security event log with the ReportEvent API.
SeBackupPrivilege	Backup files and directories	Causes NTFS to grant the following access to any file or directory, regardless of the security descriptor that's present:READ_CONTROLACCESS_SYSTEM_SECURITYFILE_GENERIC_READFILE_TRAVERSENote that when opening a file for backup, the caller must specify the FILE_FLAG_BACKUP_SEMANTICS flag.
SeChangeNotifyPrivilege	Bypass traverse checking	Used by NTFS to avoid checking permissions on intermediate directories of a multilevel directory lookup. Also used by file systems when applications register for notification of changes to the file system structure.
SeCreateGlobalPrivilege	Create global objects	Required for a process to create section and symbolic link objects in the directories of the Object Manager namespace that are assigned to a different session than the caller.
SeCreatePagefilePrivilege	Create a pagefile	Checked for by NtCreatePagingFile, which is the function used to create a new paging file.
SeCreatePermanentPrivilege	Create permanent shared objects	Checked for by the object manager when creating a permanent object (one that doesn't get deallocated when there are no more references to it).
SeCreateTokenPrivilege	Create a token object	NtCreateToken, the function that creates a token object, checks for this privilege.
SeDebugPrivilege	Debug programs	If the caller has this privilege enabled, the Process Manager allows access to any process using NtOpenProcess, regardless of the process's security descriptor.
SeEnableDelegationPrivilege	Enable computer and user accounts to be trusted for delegation	Used by Active Directory services to delegate authenticated credentials.
SeImpersonatePrivilege[2]	Impersonate a client after authentication	The Process Manager checks for this when a thread wants to use a token for impersonation and the token represents a different user than that of the thread's process token.
SeIncreaseBasePriorityPrivilege	Increase scheduling priority	Checked for by the Process Manager and is required to raise the priority of a process.
SeIncreaseQuotaPrivilege	Windows 2000:Increase quotas Windows XP/ Windows Server 2003: Adjust memory quotas for a process	Enforced when changing the Registry's quota (Windows 2000 only), a process's working set thresholds, and a process's paged and nonpaged pool quotas.
SeLoadDriverPrivilege	Load and unload device drivers	Checked for by the NtLoadDriver and NtUnload- Driver driver functions.
SeLockMemoryPrivilege	Lock pages in memory	Checked for by NtLockVirtualMemory, the kernel implementation of VirtualLock.
SeMachineAccountPrivilege	Add workstations to the domain	Checked for by the Security Accounts Manager on a domain controller when creating a machine account in a domain.
SeManageVolumePrivilege	Perform volume maintenance tasks	Enforced by file system drivers during a volume open operation, which is required to perform disk checking and defragmenting activities.
SeProfileSingleProcessPrivilege	Profile single process	Checked for by prefetcher's function that returns prefetch information for an individual process.
SeRemoteShutdownPrivilege	Force shutdown from a remote system	Winlogon checks that remote callers of the InitiateSystemShutdown function have this privilege.
SeRestorePrivilege	Restore files and directories	This privilege causes NTFS to grant the following access to any file or directory, regardless of the security descriptor that's present:WRITE_DAC WRITE_OWNER ACCESS_SYSTEM_SECURITY FILE_GENERIC_WRITE FILE_ADD_FILE FILE_ADD_SUBDIRECTORY DELETENote that when opening a file for restore, the caller must specify the FILE_FLAG_BACKUP_SEMANTICS flag.
SeSecurityPrivilege	Manage auditing and security log	Required to access the SACL of a security descriptor, read and clear the security event log.
SeShutdownPrivilege	Shut down the system	This privilege is checked for by NtShutdownSystem and NtRaiseHardError, which presents a system error dialog box on the interactive console.
SeSyncAgentPrivilege	Synchronize directory service data	Required to use the LDAP directory synchronization services and allows the holder to read all objects and properties in the directory, regardless of the protection on the objects and properties.
SeSystemEnvironmentPrivilege	Modify firmware environment variables	Required by NtSetSystemEnvironmentValue and NtQuerySystemEnvironmentValue to modify and read firmware environment variables using the HAL.
SeSystemProfilePrivilege	Profile system performance	Checked for by NtCreateProfile, the function used to perform profiling of the system. This is used by the Kernprof tool, for example.
SeSystemtimePrivilege	Change the system time	Required to change the time or date.
SeTakeOwnership	Take ownership of files and other object	Required to take ownership of an object without being granted discretionary access.
SeTcbPrivilege	Act as part of the operating system	Checked for by the Security Reference Monitor when the session ID is set in a token, by the Plug and Play Manager for Plug and Play event creation and management, the Windows 2000 implementation of LogonUser, BroadcastSystemMessageEx when called with BSM_ALLDESKTOPS, and LsaRegisterLogonProcess.
SeUndockPrivilege	Remove computer from a docking station	Checked for by the user-mode Plug and Play Manager when either a computer undock is initiated or a device eject request is made.

4.3 Super Privileges

5 Security Auditing

Two privileges, SeSecurityPrivilege and SeAuditPrivilege, relate to auditing. A process must have the SeSecurityPrivilege privilege to manage the security Event Log and to view or set an object’s SACL. Processes that call audit system services, however, must have the SeAuditPrivilege privilege to successfully generate an audit record.
The audit policy of the local system controls the decision to audit a particular type of security event. The audit policy, also called the local security policy, is one part of the security policy Lsass maintains on the local system, and it is configured with the Local Security Policy Editor

6 Logon
6.1 Winlogon Initialization

During system initialization, before any user applications are active, Winlogon performs the following steps to ensure that it controls the workstation once the system is ready for user interaction:

1. Creates and opens an interactive window station (for example, \Sessions\1\Windows \WindowStations\WinSta0 in the object manager namespace) to represent the keyboard, mouse, and monitor. Winlogon creates a security descriptor for the station that has one and only one ACE  containing only the System SID. This unique security descriptor ensures that no other process can access the workstation unless explicitly allowed by Winlogon.

2. Creates and opens two desktops: an application desktop (\Sessions\1\Windows\WinSta0 \Default, also known as the interactive desktop) and a Winlogon desktop (\Sessions\1\Windows \WinSta0\Winlogon, also known as the secure desktop). The security on the Winlogon desktop is created so that only Winlogon can access that desktop. The other desktop allows both Winlogon and users to access it. This arrangement means that any time the Winlogon desktop is active, no other process has access to any active code or data associated with the desktop. Windows uses this feature to protect the secure operations that involve passwords and locking and unlocking the desktop.

3. Before anyone logs on to a computer, the visible desktop is Winlogon’s. After a user logs on, pressing Ctrl+Alt+Delete switches the desktop from Default to Winlogon and launches LogonUI. (This explains why all the windows on your interactive desktop seem to disappear when you press Ctrl+Alt+Delete and then return when you dismiss the Windows Security dialog box.) Thus, the SAS always brings up a secure desktop controlled by Winlogon.

4. Establishes an ALPC connection with Lsass’s LsaAuthenticationPort. This connection will be used for exchanging information during logon, logoff, and password operations and is made by calling LsaRegisterLogonProcess.

5. It initializes and registers a window class data structure that associates a Winlogon procedure with the window it subsequently creates.

6. It registers the Winlogon RPC message server, which listens for SAS notifications from Win32k. This measure prevents Trojan horse programs from gaining control of the screen when the SAS is entered.

7. It registers the window so that the procedure associated with this window gets called if a user logs off or if the screen saver times out. The Windows subsystem checks to verify that the process requesting notification is the Winlogon process.

6.2 User Logon Steps