WinDbg Commands and Extensions - SwishDbgExt Library

The SwishDbgExt library contains a number of interesting extensions which are imperative for deep debugging results. The SwishDbgExt library was written by Matt Suiche.

Note: If you wish to use the ProcDumpExt DLL for WinDbg, and also view the help information for the extensions provided in SwishDbgExt, then you'll need to unload ProcDumpExt first since ProcDumpExt will overload the !help extension with it's own version. You can simply load ProcDumpExt again afterwards. Alternatively, if you do not wish to unload the ProcDumpExt DLL, then simply use the longhand method of !SwishDbgExt.help <SwishDbgExt Extension>.

You must also omit the exclamation mark (!) from the extension name, otherwise the !help extension will not work.

Note: You can use the .chain command to check if you have the ProcDumpExt DLL loaded or not. The .chain command will dump all loaded DLLs for the dump file.

The available extensions from the DLL can be found by using the !SwishDbgExt.help extension without any extensions added.

I will provide a quick overview for the extensions which can be used with SwishDbgExt.

!ms_drivers:

The !ms_drivers extension is basically the same as the lm or lmnst command. There are some additional parameters you can add to the !ms_drivers extension to spice up the command. 

The !ms_drivers /scan extension can be used to find drivers using IRP Hooking.

IRP Hooking involves a hook within the array stored within the DRIVER_OBJECT structure, this array or table of IRP_MJ_ functions is hooked and the code responsible for the IRP is redirected to malicious code. Please note hooking is used for legitimate processes such as debugging and patch releases.

!ms_gdt

The !ms_gdt extension can be used to view the GDT and LDT within the GDT. The GDT is public for all processes, whereas, the LDT is designed to be private for a specific process.

!ms_ssdt

The !ms_ssdt extension will dump the SSDT and if any functions have been patched or hooked. Remember that hooking the SSDT is used by legitimate programs, and most modern rootkits tend to do not use this method anymore.

!ms_idt

The !ms_idt extension is the same as the traditional !idt extension but with the added feature of detecting hooks within the dump file.

!ms_timers



I wouldn't consider the !ms_timers as a replacement for !timer, however, it is a great extension for being used to conjunction with the WinDbg !timer extension. The !ms_timers can detect hooking within the _KTIMER_TABLE.

Discrete Geometry - Bin Packing Problem

This post is a little irrelevant to general contents of my blog, but I found this to be a interesting geometry problem and it does have some ties with Computational Geometry, which is form a of theoretical computer science. There is additionally some connection with Computational Complexity Theory too. The Bin Packing Problem isn't difficult to explain, and yet can be difficult to find a optimal solution.

With Discrete Mathematics, I personally find that the branches within this field are more accessible but the problems are difficult enough to be interesting and form a field of serious mathematical study. I'm only a amateur mathematician and a student, so if there are any problems then please highlight them in the comments section.

Bin Packing Problem:

The Bin Packing Problem is an example of a optimization problem which has a surprisingly large number of applications, especially in logistics and data management. The Bin Packing Problem asks to minimize the number of bins needed to pack a certain number and given volume for a list of objects. These objects can vary in size, but the bin volumes will remain fixed. There are some programs which will give valid suggestions for the most optimal method, however, the problem is a NP- Hard Combinatorial class type.

The sum of the sizes of the items must be less than or equal to the total volume of the bins being used. The size of the items can never be greater than the total volume of the bins. If the volume of one bin is reached, then a new bin will need to be used. The problem looks to find a packing method which will reduce the number of bins needed to provide a optimal method.

The First-Fit Algorithm is the best algorithm which has been used for the bin packing problem. The First-Fit Algorithm is an example of a greedy approximation algorithm, in that the items will processed in any given order. The algorithm will place as many items as possible into the first bin, and then create a new bin if no other additional bins can be found. The process is then repeated for the rest of the items.

The First-Fit Algorithm has a approximation factor of 2 (APX). The approximation factor is used for NP-Hard problems, since it is very unlikely that a efficient algorithm will be produced to solve the problem directly, and therefore a P class algorithm can be developed in order to find a approximate answer. The approximation factor of 2, means that the algorithm will never use more than twice the number of least bins needed for the bin packing problem. For instance, if the number of bins needed was 2, then the algorithm will never use more than 4.

References:

Bin Packing Problem

Mathematics for Theorectical Computer Science

I thought I would create a list of Maths topics which were relevant for those who are wishing to study Computer Science. I've seen most people on online communities referring to topics which have very little relevance or completely pointless in relation to Computer Science. This list is based upon my experiences and a friend who studies Computer Science at University. I've listed the most popular Computer Science fields and their Maths topics below.

General Computer Science:

These are the topics which you will typically study in your first year, and therefore will have to do.

• Graph Theory
• Linear Algebra (Matrices and Vectors)
• Calculus I and maybe some Calculus II
•  Analytical Geometry
• Set Theory
• Big O Notation
• Radicals, Logarithms and Polynomials
• Logic

Computer Graphics: 

I'm not too sure about Graphics, but these are the subjects which do have some relevance.

• Fractal Geometry
• Linear Algebra
• Analytical Geometry
• Differentiable Geometry
• Hyperbolic Geometry
• Differential Equations
• Functional Analysis

Information Theory:

• Differential Equations
• Real and Complex Analysis - Fourier Series
• Calculus II and Calculus III - Taylor Series
• Probability Theory

Algorithms and Data Structures:

Most algorithms are used to solve mathematical problems, rather than the algorithms you see in commercial programs.

• Graph Theory
• Number Theory
• Combinatorics
• Probability Theory
• Big O Notation
• Set Theory

Cryptography and Computational Number Theory: 

• Number Theory

Computability Theory, Computational Complexity Theory and Automata Theory:

•  Logic
• Set Theory
• Calculus I
• Recursion
• Proof Writing Techniques
• Number Theory
• Big O Notation 
• Probability Theory

In general, it's best to study Discrete Mathematics rather than Continuous Mathematics. There's some fields like Abstract Algebra which are used in Algebraic Coding Theory. Furthermore, Discrete Geometry has its applications too. Continuous Mathematics encompasses areas like Calculus/Analysis and Topology etc.
 

Computational Number Theory - Pseudo Random Numbers

Computers are increasingly being used to solve mathematical problems, and are becoming more prominent in solving problems in Number Theory and Graph Theory, as well as, fields of Physics and Biology. However, computers have been used to create seemingly random numbers for either games or security purposes; these seemingly random numbers are called Pseudo-Random. They may seem random but in fact they aren't random at all.

To illustrate the difference between a true random number and a pseudo random number, look a look at the two images I've taken from Bo Allen's blog:

True Random Number

Pseudo Random Number

The difference is very obvious and thus highlights the key differences between a true random generator and a pseudo random number generator. A pseudo random number generator uses a mathematical algorithm, which is able to produce seemingly random numbers. A true random number generator uses methods which can't be predicted, and therefore are truly random. The randomness of numbers is important for encryption purposes and cryptography. 

The true random number generators are hardware based, and most use the physics of Quantum Mechanics and it's probabilistic nature, like the quantization of electromagnetism which lead to discovery of photons and the Photoelectric effect. A pseudo random generator uses a software based mathematical algorithm to generate these random numbers.

A list of random number generators can be found here.

Exploring Artifical Intelligence - Can Machines Think?

Artificial Intelligence is both a topic of Computer Science and Philosophy, and begins to ask what really makes us human and if we are just a complex biological machine? Alan Turing first asked the question in his 1950 paper named Computing Machinery and Intelligence. The paper is much more accessible in comparison to his paper about Computability Theory and computable numbers, which are real numbers that can be calculated with a terminating algorithm, the computable numbers are also considered countable (number of axioms for this).

This blog post won't be long, and I'll probably conclude with a link to my OneDrive account which has a copy of Alan Turing's paper. I'm going to be mostly be talking about the philosophy of Artificial Intelligence.

There is one concept which has been of great interest to philosophers since the beginning of civilization, and that is the concept of consciousness, which is the ability to be able to be aware of our own existence. This concept of consciousness is what separates us from being a very complex biological machine. In essence, our behavior is typically determined through learning and our own past experiences. Yes, we can incorporate this concept of learning into machines and measure how well it performs when learning, but a machine will never be aware of it's own existence naturally like a human, unless we find some method of enabling the machine to be aware of it's own existence, however, that would be cheating since it is still relying on predetermined behaviors created by us.

A machine is usually regarded as being intelligent if it is able to imitate a human successfully (it able to play the imitation game in Turing's paper); that is to say that a human is unable to distinguish a machine from another person. Turing outlines in his paper the similarities between a person and a computer. However, can a machine think? What is thinking? Computer programs are based upon a defined set of rules which can't be broken, unless the rules weren't correctly defined to begin with, and therefore is the machine thinking about a problem or just going based upon a defined set of rules? 

Behaviorists will suggest that all thoughts are based on defined set of rules, and these rules give the false impression of free will and thought. This doesn't explain the idea of consciousness and what exactly creates consciousness. I believe machines will be able to solve mathematical problems and think, but they won't ever possess the strange and rather beautiful consciousness. Most robots aren't able to intelligently move around objects yet.

At the moment, most machines can only given Boolean valued answers to decision problems, they aren't able to think about the another answer, just give a simple "Yes" or "No" based upon some algorithm. There are learning algorithms, though I don't believe you can consider that as true thought. There is a popular idea of that a machine can only do what it is told to do, and this seems to very much true for almost all machines as of now.

I would suggest reading the paper Computing Machinery and Intelligence, which is available here.

It would be nice to hear some of my readers thoughts on the concept, and any ideas they may have about Machine Learning.

Fibonacci Number Series

This is going to very loosely related to Programming and Computer Science I know, but I thought it was quite a interesting little simple programming project to do. I've written the code in C++, but you could easily adapt it to C or any other language if you so wish.

The Fibonacci Number Series is a special sequence of numbers which is the sum of the two numbers before the current number. All the numbers will be integers (whole numbers). There is a simple mathematical equation for expressing this relationship:

Our seed values, or starting numbers, are going to be 0 and 1. This can be seen with the variables shown in my code. The seed numbers have to be 0 and 1, or 1 and 1 in order for the above equation to work.

I've commented the code, so it should be easier to understand, even though it is a simple program, the components would only really make sense if you understood the Fibonacci Number Series.

The number of terms within the sequence can be selected by the user, and is then used to control the for loop for using the equation which I've named the Fibonacci Number Equation.

 The main body of code comprises of a for loop and a if-else statement. I've applied the equation into the code on line 21. You can find lots of examples of this code on the Internet, but I thought I would comment the code to make it more user-friendly and give some general information about the number series, in which the other blog posts and tutorials seem to be lacking in.

The Fibonacci Number Series is also applied to Computer Science in terms of the Fibonacci Search algorithm and the Fibonacci Heap data structure.

The Fibonacci Number Series can also be found in Pascal's Triangle.

I'll most likely expand upon this topic in the future, and write a blog post about the applications in Computer Science. In the meantime, the next blog posts will be about exploring the Registry with WinDbg, and I might add a tutorial for Stop 0x133, but it's one of those bugchecks which is difficult without a Kernel Memory Dump.

Virtual Functions and VTables

Virtual Functions are a fundamental aspect of OOP programming features such as polymorphism. Any Virtual Functions are stored within a dispatch table called a VTable or Virtual Method Table. The VTable is essentially a array of virtual function pointers. It is possible to find the VTable using WinDbg, and I will demonstrate this within this blog post.

Virtual Functions and Virtual Function Table Pointers

I've written a very simple program using C++ to demonstrate the syntax of Virtual Functions.

As you can see, there are two classes called A and B. A is the base class in which Class B will inherit any members or member functions from. By using the virtual keyword on the function in Class A called Function, it specifies that the function is a Virtual Function and not a standard function.

When Class B inherits Class A's properties, then the Function is redefined within Class B which can be seen on Line 14. Please note this is not function overloading, since the function still retains the same type and the same of number parameters, which wouldn't be the case for function overloading. The redefinition of a function within a class is called overriding, therefore Class B is overriding the definition stated originally within Class A.

By looking at the main function of our program, we can see two objects called of Class A and Class B respectively, and then a base pointer for Class A. We will use the base pointer to access any derived Classes from the base class of A. Note how we can access the Function in Class B using the base class pointer, this a demonstration of supporting polymorphism.

Each Class will actually have a pointer into the Vtable corresponding to that Class. For Example, Class B will have it's own VTable, and each entry within the VTable will correspond to the number of virtual functions which can be called by the object belonging to that class.

These VTable pointers will be set up by the compiler, and the corresponding object pointers or this pointers will be used to as a function parameter to be used by the compiler to find the entries within the VTables. It's important to remember that the pointer for Class A's VTable can't access the members for Class B's VTable, although, Class B is able to access Class A's table members. Another key point to consider is that the function pointers within VTable for a inherited class, will point to the overridden version of that function.

For example, Class B's Function() will not point to Class A's version of Function. Here's a good illustration to demonstrate this concept:

 In real terms, you can use the same kind of prototype or interface of a function, and then make it specific to your needs or that particular object.

VTables and WinDbg

Please bear in mind, that the following extensions only apply to processes which were written with the .NET Framework, I created a similar program with C# to demonstrate these debugging extensions. There is another method but I've heard it's very tedious.

To use the following extensions you will need .NET Framework 4 or .NET Framework 4.5. The .NET Framework is required due to the DLLs we need to load into WinDbg. Some people have found this difficult to set up and therefore I will show some basic steps.

1) Load the executable into WinDbg using CTRL + E.

2) Load the following DLLs with the !load extension, you must specify the full file path, otherwise WinDbg will show a can't find file error:

3) Now, hopefully you inserted a Console.ReadLine function into your code, so the program pauses while in WinDbg. If so, then enter the g command into WinDbg and press Enter. This should enable the process to continue running and will load the CLR.dll.

4) Use the .loadby command with sos clr, and then enter the desired .NET debugging extensions.

 If you followed the steps correctly, then the !dumpheap extension should work correctly. If not, then please make sure you have followed the instructions or leave a comment in the comments section.

I've named the namespace of my program VirtualTable, so that's the reasoning for the VirtualTable name appearing. The MT column contains the address of the Method Table or the Function Table (in terms of C/C++).

We can then use the !dumpmt extension to show some information about the Method Table for that particular class or class object.

A listing of the debugging extensions associated with SOS.dll can found in the Additional Reading section.

VTable Security

As a result of the possible exploits related to the VTable, some compilers have introduced some security features which help combat against these exploits. Some of these protections include VtGuard for Microsoft Visual Studio and Virtual Table Verification for GCC compilers.
 
The exploit I have read, is related to changing the VTable pointer to a different VTable and then executing the virtual functions from that VTable which would allow the injection of shellcode.

VtGuard uses a combination ASLR and then adding a extra entry to the VTable for a given class. The extra member is called _vtguard, and is hidden from the attacker with the use of ASLR. The method uses the cmp instruction to compare the address of the VTable Entry against the VTable Guard, and will terminate the process if these two addresses do not match.

Virtual Table Verification works by verifying that VTable pointers point to the base class and are valid for that class. Place any important data structures in protected areas of memory. The Base Class Virtual Table Pointers will be gathered at runtime, and then assigned to a _vtable map variable which can be used for comparison between the mapped _vtable map pointer and the _vptr gathered from the class object. 

Additional Reading:

C++ Virtual Table

SOS.dll Debugging Extensions

BH_US_12_Miller_Exploit_Mitigation_Slides

Virtual Table Verification

Recursive !dumpmt - WinDbg

Algorithms and Data Structures - Calculating Insertion and Deletion Time Complexity of Singly Linked Lists

Prerequisites: 
- Knowledge of C/C++
- Knowledge of Calculus/Algebra

Time Complexity and O(n)

You could consider this topic as a Computer Science/Programming topic. However, I always consider Computer Science and Programming to be two different topics rather than the same thing, even though they both share the same programming principles, such as understanding how to write code to begin with. Computer Science is more like Applied Mathematics, and is more theory based, whereas, Programming is more practical and using a language or multiple languages as tools to create real-life programs.

I've written a simple program which creates nodes within a linked list, and then walks this linked list when the user has decided they do not wish to insert any more nodes into the list. I've commented the code where necessary so it will be easier to understand. We'll then calculate the time complexity of the algorithm used to insert the nodes within the linked list.

Firstly, let's consider and investigate the concept of time complexity and what it means in terms of Computer Science. Time Complexity refers to the amount of time for a operation to complete, as a result of the input required. There are different forms of Time Complexity, and therefore different methods apply to the type of Time Complexity. For Singly Linked Lists, the Time Complexity is often regarded as Constant Time Complexity.

Constant Time Complexity or simply Constant Time, isn't affected by the size of the input, or the number of elements. For example, if we had a sorted linked list or array, it would only take one operation to find the element within the array. Although, the same can still apply, if the number of elements within the linked list was unsorted, but the number of elements within the linked list is known within advance. To simply, the number of elements within the linked list, does not affect the complexity of the insertions or deletions within the linked list. The Big O Notation for calculating constant time within a linked list is O(1). On the other hand, the Big O Notation for  walking the list, is given by the O(n), which implies that the complexity for walking the list, increases with direct proportion to the number of elements within the linked list.

The Big-O Complexity Interactive Graph supports this point.

Singly Linked List Code (C++)

Figure 1 - Node Structure

Let's examine this simple node structure. The structure has two members: node_data and next_node. The node_data is of a integer type, and represents any data stored within each node. The next_node is a pointer with a type of node (structure), this is used to point to the next node within the singly linked list.

Remember that linked lists start with a list head, which is essentially the beginning of the linked list.

Figure 2 - create_node() Function

The function will keep creating new nodes as long as the user wants to. The node_data can be defined by the user.

Figure 3 - create_node() Function

Once, the user has created all the desired nodes within the linked list, the walk_list function will be called.

References

Big O Notation
Time Complexity
Complexity Theory - Definitions of an algorithm running in polynomial time and strongly polynomial time
A Beginner's Guide to Big O Notation
How To Create a Linked List Using C/C++

Understanding Memory Barriers

Memory Barriers in Code

Memory Barriers are used to enforce some kind of ordering on how the compiler or CPU execute memory ordering operations. Since most CPUs have some form of technology which is used to optimize the execution of code, the problem of out-of-order execution can occur in programs leading to unpredictable results. Each variable or data structure we create is referred to as a an object, and each object has a memory address and memory address load order. This load order defines which variables are written to and loaded first.

You probably will never notice this with program which has one thread, typically this is simply main. However, if you create two threads and have these two threads run concurrently, the question of which thread runs first raises? Although, we can add synchronization dispatcher objects to our code, the point of this blog post is to look at the concept of memory barriers and examine the Assembly code which is produced through binary analysis.

In the Main thread, I've created a global atomic boolean value called y, and have set it to false. Two separate additional threads are created, which have functions called Processor and Processor2.

The code for the Processor function is above, while y is not being read, we need to wait until the fence instruction has created a synchronization with relationship with the fence instruction in the other thread. When using fence instructions, there must be two different types of fence instructions (store and load) to generate a relationship otherwise we will not achieve the purpose of our synchronization.

The code for the Processor2 function, shows that the address of x will be stored or written with the value of 42. Again, x is a global variable, and is thus available to all parts of the program. We then insert a fence instruction between the storing of x and the y, this is used to ensure that the value of y isn't read until the memory fence has been acquired in the other thread.

If the fence instruction notices the store after the release fence instruction, then the acquire fence instruction will form a synchronize with relationship with that release fence instruction. 

It's easier to understand with the insertion of a assert function to our code in the the Main thread. The assert function will be controlled by the value of a global atomic variable called z. If this function is incremented by 1, then the assert function will not be called.

Once the two threads have synchronized together, the value of x will be evaluated and then the value of z will be incremented to 1, ensuring that the assert function isn't called and terminates the program.

You may have heard or seen people talk about the use of the volatile keyword. This keyword is used to tell the hardware that it can modify this value, and this brings in the term of modification ordering. The use of the volatile keyword will alter the modification ordering of executed instructions. See the references section for more information.

Memory Barriers Internals

I assume you know generally how the cache works, and what cache hits and misses are. In this case, I'm going to discuss some of the features of the cache and then explain how memory barriers relate to the operation of the CPU Cache.

The above is the general structure of the cache, and its relationship to memory. Initially, each there will be a cache miss, since no longer is present within the cache, however, once this data has been gathered from memory and placed into the cache, a cache hit will occur for each sequent read on that same object. 

Although, the cache is a limited resource and therefore will not hold every possible address of all the objects being read from memory. When the cache becomes full, and the processor is attempting to write new data to the the cache, then cache capacity misses will result. These cache misses, as the name suggests, are a result of lack of space within the cache.

The cache is organized as hash table with fixed-size buckets called sets, and no chaining. The hash table is a data structure used to implement and construct a associative array, each hash function will be able to match a key to the correct value within the array. Essentially, the key is used to index into the bucket stored in the hash table. The key would the name of our object.

Looking at the above example of a cache, we can see there is currently 16 different buckets or sets. The hash function is based upon a algorithm which knows the name of the key and the size of the array. Furthermore, hash tables used with the cache do not support chaining, and therefore hash collisions are always possible. Separate Chaining is the concept that a index can have multiple entries in a linked list, this avoids the problem of hash collisions.

When the cache has become full, the data within one of the sets will need to be removed, and the new the data will need to be added. On the other hand, when data is being wrote by a different processor to another processor's cache, the operation will result in unnecessary stalling of hundreds of instructions.

The CPU 0 sends a message to CPU 1's cache line, the invalidate message contains the physical address of the cache line, and causes the processor to remove the data, to enable CPU 0 to be able to write to that set within the cache. As you can see, this is a expensive operation and there is a better method. The answer lies with Store Buffers, whereby a processor can store it's write instructions within it's buffer, and continue executing until it's appropriate to make the write to the other cache, but this leads to the problems of memory ordering and out-of-order execution.

 Due to the problem of memory ordering and store buffers, memory barriers were introduced to enable programmers to be able to perform synchronization at level which was close to the hardware of the system.

Memory Barriers Disassembly

The main thread of the program begins at mainCRTStartup, which jumps to a block of code which contains the necessary thread creation functions. By jumping to the location pointed to by the jump instruction, we can see how our thread is started. Please note all default compiler linker options are enabled, so you may notice things like security cookies etc.

We push some integer variable onto the stack stored in the register called ebp, this register value is then moved into the esp register, which is our current stack frame pointer. We then call some functions, and remove the value of the ebp register from the stack. The function then returns.

Most of the fence instructions, and thread functions I was able to find, we can jump to where these instructions begin, and examine the Assembly code used to produce them.

Let's look at the jump instruction for the loading of a fence instruction (std::atomic_load_explicit), and have a quick look at a few of the details.

We can see that function takes the atomic variable and the memory ordering constant, which are later pushed onto the stack.

References:

volatile (C++)

std::memory_order 

Hash Table

Memory Barriers : a Hardware View for Software Hackers

Multiprocessor Considerations for Kernel-Mode Drivers

Understanding Splay Trees

Splay Trees are an example of a binary search tree, which is a data structure for arranging and sorting data, which is sorted into nodes. They make good use of pointers. Splay Trees share the same structure as a standard binary search tree, but provide benefits such as the most accessed node always being the root or top of the tree. There three standard algorithms for splaying the node to the root of the tree, and these depend upon the positioning and depth of the node within the Splay Tree.

Splay Trees are used in IFS (Installable File Systems).

The length of the time taken to complete a algorithm for a Splay Tree, can be calculated with the Big O notation. There's no randomisation within Splay Trees, and therefore some operations can be expensive and time consuming, this is especially true when Splay Trees become unbalanced and very tall. It could take many Zig operations to splay a node to the root of the tree. Each rotation is called a Splay Step, and the process is called Splaying.

Here is an example of a very tall Splay Tree:

Let's discuss the three algorithms, used to search or walk through a Splay Tree, and then Splay this tree to rebalance it.

Zig Zag Algorithm:

The algorithm, begins like a ordinary binary search tree, you start at the root, and then begin to walk down the tree, deciding if you take the left child or the right child of the current grandparent (root), depending upon the data sorted within the node your looking for. You continue this process, until you come across the node and the key your looking for, or until you reach a dead end, since the node may not be sorted within the search tree.

 The general rule here, is if x (node) which we are splaying up the tree, is the left child of right child, or the right child of the left child. It's easier to understand it, in a picture or in a video.

Zig Zig Algorithm:

The node (x) is left child of the left child, or right child of the right child. The Parent is rotated through the Grandparent, before the splay of the node takes place. The Grandparent is the root of the tree, and the Parent is the child which the node is the child of: right child of the right child.

Zig Algorithm:

This is the most easy algorithm, the node (x) is the child of the Grandparent or the root.

Splay Tree Node Insertion:

Now, let's discuss the Insertion and Deletion of nodes within a Splay Tree. The general rules apply to a binary search tree, and since a Splay Tree is a binary search tree, it inherits these properties. You can use your own defined relationships (properties) with the insertion of new nodes.

• The left subtree of a node is less than the key stored in the Parent node.
• The right subtree of a node is greater than the key stored in the Parent node.
• There can't be any duplicate nodes. 

Remember the Parent Node, would the node above the subtree. All subtrees must be binary search trees too.  A key typically refers to the data stored within the tree.

This Splay Tree contains one node, with a data value of 60. It is the Root Node, and as a result will not have any associated Parents, but it doesn't have any children either. Until, we insert another node into the Splay Tree. RtlIsRoot can be called to decide if the current node is the root node, or techically the Grandparent node. Each node contains usually three different pointers. The Parent, Left Child and Right Child.

RtlSplay is used to call, and add a node to the Splay Tree, and rebalance the Splay Tree, so the node becomes the root.

This process can continue with the adding of new nodes. Remember you will need to call
RtlInitializeSplayLinks, to create a new link between the newly inserted node and the original node, before even adding the node to the tree and calling other routines.

Splay Tree Node Deletion:

A node can be deleted with the RtlDelete, which deletes a node and then splays the tree. You can specify not to re-balance the tree, with the RtlDeleteNoSplay.

Synchronization in Splay Trees:

 This really depends upon the IRQL Level, if your going to need to raise the IRQL Level to greater or to DISPATCH_LEVEL (IRQL Level 2), then spinlocks must be used along with non-paged pool. Otherwise, if lower than DISPATCH_LEVEL, then general dispatcher objects can be used along with paged pool. 

References: 

Kernel Mode Basics: Splay Trees

Binary Search Trees

Binary Search Trees - Wikipedia

Splay Tree - Wikipedia

All the routines should be fully documented within the WDK.