ISN (the language)

There are times when people get together to make a new language like Esperanto and the result is derivative and frankly boring. Can a bona fide new language be born in this day and age and if it does how would it look like? would it follow the structures described by Chomsky? if you are intrigued, then meet ISN:

When the Greek historian Herodotus was traveling in Egypt, he heard of a bizarre experiment conducted by a King named Psammetichus. The inquisitive monarch, wrote Herodotus, decided to wall up two baby boys in a secluded compound. Whatever came out of the boys' mouths, reasoned the King, would be the root language of our species — the key to all others. Herodotus tells us that eventually the children came up with the Phrygian word for bread, bekos. In addition to demonstrating the superiority of the Phrygian tongue, the King's inquiry proved that even if left to their own devices, children wouldn't be without language for long. We are born, Herodotus suggested, with the gift of gab.

Ever since, philosophers have dreamed of repeating Psammetichus's test. If children grew up isolated on a desert island, would they develop a bona fide language? And if so, would it resemble existing tongues? Yet only someone with the conscience of a Josef Mengele would carry out such an experiment. Then, in the mid-1980's, linguists were confronted with an unexpected windfall. Psammetichus's experiment was repeated, but this time it came about unintentionally. And not in Egypt but in Nicaragua.

Here is the link to the full story [NY times]

Full Metal Planet

Iron Guts Morla (my alias) is the name of one of the possible players (factions) that you can choose when playing 'Full Metal Planet'; an old computer game made by Infogrames that was available for the Amiga, PC and Atari platforms. It was inspired by a french strategy war board game named "Full Metal Planète" made by a company called Ludodélire that went bankrupt long time ago. I have never played the board game but I played plenty of the computer version in my Amiga 500 computer. According to experts, the board game was better than the computer game;I imagine in the same way than 'the book is better than the movie' for almost all books that have a movie's made.

You can find the board game and the computer game in eBay, the board game sells for about US$300 (because it is so rare), and the computer game sells for $60 in good condition.

I enjoyed much, but I don't want to play it again. I don't delve in the past, it distracts me from the now. I just wanted to make this entry because it is hard to find this piece of trivia on the web.

The Zen of R3 Hooking

In my daytime job, from time to time we end up needing a way to patch user mode code (Ring 3, or R3 for short) to perform a targeted alteration of the behavior of a target application to improve the security or to make it behave better under a more locked down configuration. This modification typically this happens at the boundary between the application (which we treat as an undocumented black box) and the windows API. Thus, what we do in a hook is to 'take over' a particular API and execute some code of our choice before and then after the original API call.

If you google for patching or hooking or interception you will find plenty of code and articles out there. For example, last time I checked just codeproject.com has no fewer than 4 full blown articles in the subject. Today I will show you a neat trick that so far I have not seen disclosed widely.

To patch you need to solve two problems:

1) Injecting in the virtual address space of the target process the code that is going to be executed before and after the original API call and 2) Re-wire the target process so our code is called instead of the windows API.

I won't touch on the first item since I have nothing to add to it today. For the second item your options are:

a- Modify the IAT (in the PE-in-memory) to point to your code
b- Modify the EAT (in the PE-in-memory) to point to your code
c- Overwrite the start of the API call in memory with a 'jmp' stub

But I won't talk about them. What I want to talk about is a different way to do this in the context of a special (but fairly common) case. It being if you need to hook an API that you know jumps to kernel using the standard system call dispatch table.

This trick works only in 32 bits Windows XP SP2 and Win2K3 SP1. I also assume you need to patch R3 code from R3. If this is your case, read on:

You should know that when an application calls (for example) CreateMutex(..) it does so via a the appropriate EAT entry in kernel32.dll where after doing some simple transformations of the input parameters it calls ZwCreateMutant(..) which lives in ntdll.dll. Here what used to happen circa year 2000 under the covers:


ntdll!ZwCreateMutant:
77f853b8 b825000000 mov eax,0x25
77f853bd 8d542404 lea edx,[esp+0x4]
77f853c1 cd2e int 2e <-- jump to kernel


Where 2e is the standard system call interrupt gateway to ring zero (R0). Well, times have changed and most (if not all) processors now support a faster way to transition to R0 using the new instruction 'sysenter'. Here is what happens in XP with no service packs:


ntdll!ZwCreateMutant:
77f7e663 b82b000000 mov eax,0x2b
77f7e668 ba0003fe7f mov edx,0x7ffe0300
77f7e66d ffd2 call edx


where the routine at address 0x7ffe0300 is formally know as the SystemCallStub:


7ffe0300 8bd4 mov edx,esp
7ffe0302 0f34 sysenter <-- jump to kernel
7ffe0304 c3 ret


What they have done is to add one level of indirection, so in older processors where the sysenter instruction is not supported, then the SystemCall stub will contain the usual int 2e code. The memory page at 0x7ffe0000 is a fixed block known as the SharedUserData that is mapped at the same address in all processes. You could patch it, with a jmp instruction to your injected code but the good people at Microsoft changed things once again when XP SP2 was released. For example:


ntdll!ZwAllocateVirtualMemory:
7c90d4de b811000000 mov eax,0x11
7c90d4e3 ba0003fe7f mov edx,0x7ffe0300
7c90d4e8 ff12 call dword ptr [edx]


If you compare the last function with the previous ZwCreateMutant you'll see that the only difference is that the call using EDX is now an indirect call. Therefore the memory at 0x7ffe0300 does not contain code anymore but a pointer to the actual SystemCallStub. Cool.

So that is the punch line: if you overwrite the pointer at address 0x7ffe0300 you have patched every system call that the process can make. Make sure you modify the page protection to make it copy_on_write so you don't affect other processes; remember that your injected code lives only one the target process.

Of course, since in your hook routine you are getting every system call, you need to look at the EAX register for the API id that you care about.

It does not get more Zen than that.

Wish list (for somebody making a new OS)

From time to time it comes to me a neat feature for a new operating system. Before I forget about the last one, here it is: ..drum roll, please..

Lightweight Processes

What? I hear you say. Let me explain.

In your run of the mill OS, there are processes and they are good and they suffice most of the time, but once every so often a process becomes so popular, so successful that everyone wants to be part of it. Examples abound: the web browser, the e-mail client, the text editor and so on. In fact, it seems that every user-mode process harbors deep in it a secret desire to be some day, famous like that. If not itself maybe its descendants.

Anyhow, the problem is that the successful process, becomes a container of plug-ins, each plugin effectively being a peer of every other plugin attached to the process an a peer of the process itself, the result is that all the nice guarantees of an OS process go out the window, and in fact the process itself has become a poorly written, non-preemptive operational system. In other words a bad DOS clone.

I am sure it is similar to the experience of Shakira's mom when she visits her daughter house. Who are all these people hanging around, smoking and drinking? do you even know all of them? see that guy? he just spit in the carpet!! who drank all the milk and left the empty bottle in the fridge? this is chaos. I am leaving.

So, in my terminology (because I am sure lightweight process has been taken) a lightweight process has two key properties:

1- It depends on one (and only one) regular process, but
2- it is still a process: it has its own virtual memory space and security profile

The first point, being dependant on a regular process means:
a- A regular process can spawn a child lightweight process, but a lightweight process cannot spawn by itself other regular or lightweight processes
b- When the regular process terminates, all associated lightweight child processes will be terminated (with no recourse) by the operating system.
c- Lightweight processes have access only to a subset of the operating system API that regular processes have. For the rest, a child process will communicate with the parent process and the parent process can fulfill (or not) the request.

To the second point, a lightweight process can be forcefully terminated by the OS without having necessarily to terminate the parent process, and more importantly the parent process can terminate forcefully the child process without risking memory (or other) corruption.

Some people can point that you can do this kind of things today with the infrastructure provided by rich OS such as Windows. For example, if a plug-in model in windows is similar to COM, then a lightweight process is similar to an out-of-process COM server. But if you thing about it you'll see it is not the case.

There is more to the subject. For example I think it will be appropiate to have a special memory model between the parent and the child process, one that comes to me right now is that the parent process can write to the child process memory, and the child process can read the parent process memory, except that the parent can designate pages that are not readable and the child can do the same and specify pages that are not writeable. There would be no option for the child to write to the parent memory or for the parent to read memory. There is also a case to be made for some special model for threads and some specially efficient IPC model, where doing an IPC between parent/children does not cause a full blown context switch but cause more like a continuation [1] kind of deal.


[1] "Using Continuations to Implement Thread Management and Communication in Operating Systems" by Draves, Bershad, Rashid and Dean. 1991 Carnegie Mellon University.

Voodoo logic at MSRT

From the Microsoft Security Response Team press release:

But the update deemed by analysts to be most important is [number] which patches a critical bug in [component] used by Windows [product] and [product]. The flaw can be leveraged by a hacker to hijack a supposedly
protected PC, because the [component] improperly parses [data], Microsoft said. Attackers could feed malformed [data] to PCs via e-mail, for instance, and grab control of the machines without any interaction from users.

So far nothing out of the ordinary, a standard day in the life of windows, I am sorry to to say, but the kicker comes in the last sentence of news:

According to Microsoft, the attack vector hasn't been used yet by attackers.

Now let's recap how logic works: you start with a premise (to prove) of the form for all X -> Y holds true. To prove it you need to examine all X. This is, in most cases impossible, but to prove the opposite is easy: as long you can find at least one example where it does not true, then you can say ~(X -> Y).

So according to the press release we can only conclude that either Microsoft has knowledge of how each infected PC in the world (that is running Windows) got compromised or that the spokesman is lying.

Ahh, that trick middle school logic...

Thinking out of logic

From one very interesting slashdot thread about Virtualization from a user with alias njdj (458173):

It reminds me of an influential paper in the RISC/CISC debate, about 20 years ago. Somebody wrote a C compiler for the VAX that output only a RISC-like subset of the VAX instruction set. The generated code ran faster than the output of the standard VAX compiler, which used the whole (CISC) VAX instruction set. The naive conclusion was that complex instructions are useless. The correct conclusion was that the original VAX compiler was a pile of manure.

This is an important part of thinking logically: It is easy to get to the wrong general conclusion based on a single example, specially if such example is just a benchmark.

In this particular case, twenty years latter we see the CISC architectures doing fine and it is not just a marketing feat.

Winter of code (part 4: Ramblings)

In this episode I am going to continue talking about NTFS details that I think will be important to this project. I do not have this project ready so I am blogging as I think about it so expect some 'wardrobe malfunctions' along the way.

In fact the most important item in my mind so far is here: the The File Reference Number (FRN). The FRN is a 64-bit number that uniquely identifies each file in an NTFS volume. The FRN is comprised of a 48-bit part and a 16-bit part. The former part is the sector offset of the first record about the file in the MFT and the latter part (called the ‘generation’) is just a counter that monotonically increases each time NTFS reuses a MFT record. Taken together the FRN should be unique in time and space. Or I least I wish, but this is not exactly true.

The conditions under a FRN for a given file changes are kind of complicated and better left for another day.

The good news is that the FRN of a file should ‘rarely’, if ever, change because as long as the file has not been deleted, there is no reason to free/reuse its first record entry in the MFT which is really is what makes the FRN a stable id for a file. By the way, FAT volumes also have the notion of FRNs but with the disadvantage that they can change under much more common conditions making them more or less unusable. Lucky for us we don't care about FAT volumes.

So let me introduce a little command line test program called fdb1.exe. The only parameter it takes is a path to a file or directory and it outputs the corresponding FRN in hex along with the VSN (volume serial number). Taken together, this two numbers can uniquely identify a file in your computer. The total line count including blank lines is 113.

Here is a typical output:
file c:\$MFT
has FRN of 0x0001000000000000 and VSN is 0xc402ce7d
file c:\
has FRN of 0x0005000000000005 and VSN is 0xc402ce7d
file c:\boot.ini
has FRN of 0x0001000000000ca7 and VSN is 0xc402ce7d
file e:\
has FRN of 0x0005000000000005 and VSN is 0x481fccd6
file c:\$MFTMirr
has FRN of 0x0001000000000001 and VSN is 0xc402ce7d
Note how the FRN of C:\ and E:\ are the same but the VSN is different. This is somewhat explainable because the root of the volumen which is a directory named '.' is always the fifth record in the MFT. In fact the first 12 or so MFT records, all have very predictable contents.

Now let's get down an dirty. Here is main( ) :
int wmain(int argc, wchar_t* argv[])
{
try
{
if(2 != argc)
{
OutputUsageError();
return 1;
}
FileHandle file = CreateFile(argv[1], 0,
FILE_SHARE_READFILE_SHARE_WRITE,
NULL, OPEN_EXISTING,
FILE_FLAG_BACKUP_SEMANTICS,NULL);


BY_HANDLE_FILE_INFORMATION fi = {0};
BoolCheck bc =
::GetFileInformationByHandle(file.Get(),&fi);


OutputResults(argv[1], fi.nFileIndexLow,
fi.nFileIndexHigh,
fi.dwVolumeSerialNumber);

return 0;
}
catch(ApiError& ex)
{
OutputException(ex.error, ex.text);
return 2;
}
}

Yes, that is the actual program, *with* error handling included.

As you can see the code just calls two Win32 APIs and then spits the info collected to the standard output. The first one, CreateFile( ) opens the file or directory path received from the command line and gets you a handle that is fed into the second API GetFileInformationByHandle which returns a bunch of information about the file including the FRN. The only thing to note here is the use of the CreateFile parameters with “backup semantics” so that a single call can open both files and directories because the regular semantics (so to say) are meant for files and the API fail when opening a directory.

Besides showing some FRNs, I wanted to talk about the kind of code style I do. If you program Windows, take it as an advice. First of all, get rid of that ugly TCHAR and _T( ) macro stuff all over the place; Windows is Unicode and we are not coming back from that trip. One of the main purposes of adding all the extra complexity to C++ was to provide viable alternatives to C macros, therefore I feel is my duty to remove as many as I can. By the way, kudos to the VS2005 team that have made the win32 app project wizards with the Unicode switch enabled by default.

Second, use negative logic when testing a condition. The “true” part of the ‘if’ is where I expect to find the error/failure handling logic and possibly a return. The other option, which is to have the “true” part of the ‘if’ be the success condition leads to multiple nested levels of {, which is harder to read, verify and to code right.

However, in order to do this the right way you are going to need to follow the next item.

Third, use holders. A holder is a small, silly class that implements some form of the RAII pattern. I assume that you are familiar with this technique, if you are not, you really need to. The form that usually I like on a holder does not try to hide the native API to the ‘held’ resource; instead it handles in its constructor the possible error conditions that the ‘create/open’ API call can dish out.

class FileHandle
{
HANDLE file_;
public:
FileHandle(HANDLE file):file_(file)
{
if (INVALID_HANDLE_VALUE == file_)
{
throw
ApiError(WIDEN(__FUNCTION__),
::GetLastError());
}
}

~FileHandle()
{
_ASSERTE(INVALID_HANDLE_VALUE != file_);

if(!::CloseHandle(file_))
{
_ASSERTE(false);
}
}

HANDLE Get() const
{
return file_;
}

private:
FileHandle();
FileHandle(const FileHandle&);

};

Note bene: the built in macro __FUNCTION__ resolves to a quoted ANSI string containing the undecorated name of the enclosing function.

The holder as you can see it is quite simplistic. Oh I hear you say, ‘I have a better one, it uses templates’, and ‘yours does not do X, Y or Z’. Yes I know, I do have the fancy ones but they are hard to read, hard to test and they are overkill here.

Never underestimate the power of simple my little grasshopper.

And that goes for you too mr. boost:: lover. Not that there is anything wrong with liking boost.

Fourth, bake in some form of asserts, but in all things moderation. The best ones should be hidden somewhere in your helper classes, away from the main logic. For example in my code you see assert if CloseHandle fails. Why? Because that should not happen, unless somebody is violating the RAII contract, which it could actually happen at some point. I have seen way too many pointless asserts in my time. Besides, a destructor is a bad place to throw an exception.

Fifth, if you agree with the premise of using negative logic and if you buy the idea of using holders then you inevitably end using exception-based error handling because you end up handling API errors in a constructor. I know, I know, influential people have spoken against using exceptions, but frankly they use as examples in a language I call C+ code (a single plus) which is just C plus some type safety.

Speaking of exception-based error handling here two rules:
1. Throw a lot but catch just a few
2. Don’t catch what you cannot handle and thus never do a catch(…)

I also have seen that once you follow this 5-fold way what error is just an expected error and what is an exceptional condition become less blurry.

Without further ado, here is my silly exception class for this program:


struct ApiError
{
const wchar_t* text;
unsigned long error;

ApiError(const wchar_t* txt, unsigned long err)
:text(txt), error(err){}
};


The final trick that I want to show you is what do I do with the APIs that return a boolean result such as GetFileInformationByHandle. If you have seen a lot of windows code the pattern is all too familiar: if false then there was an error which can be recovered by calling GetLastError(), of course before calling any other API because the last error is a thread-local variable that will get overriten if you call any other Win32 API using the same thread


class BoolCheck
{
public:
BoolCheck(BOOL res)
{
if(FALSE == res)
{
throw
ApiError(WIDEN(__FUNCTION__),
::GetLastError());
}
}
private:
BoolCheck();
BoolCheck(const BoolCheck&);
};


And that's all there is to see. The rest of the program is the WIDEN macro that you can find anywhere (converts ansi strings into unicode), and two little ouput functions that just take the inputs and do your tipical std::wcout << stuff.

The bigger picture is that you can factor out into helper classes a lot of the noise that obscures the meat of the program and that I think is worth the effort.

Winter of Code (part 3)

I am going to talk today about some design criteria for the file explorer. See here and here for the previous posts in the series.

Up to this point I have stated that speed is a primary concern. So how I am going to beat explorer in this area? Two strategies I have in mind:

• Focus only on NTFS and Windows XP


• Be less flexible but more efficient

Let’s talk about each one.

Focus only on NTFS

I only use NTFS volumes. This has been the case for about 5 years now (even for external USB/Firewire disks). The only case where I use FAT is for key-sized memory sticks. All the people I know do the same but more importantly, most people out there also do. For example, a survey I trust is done by Steam (http://www.steampowered.com/status/survey.html) (which began on Nov 15, 2006): it had 942,000 unique PCs from which 93.66 % have NTFS as a mounted file system. The same survey shows also that the vast majority of people are running some flavor of Windows XP.

By targeting NTFS and XP I hope I can use efficient techniques and unique APIs that are simply not available for FAT32 volumes or Win2k. In some cases the difference is so dramatic that you can understand why Microsoft wants so dearly to get rid of the FAT legacy in Vista and beyond.

Be less flexible but more efficient

The amount of queries and miscellaneous operations that happen undercover related to COM and to the registry to render a folder view is truly frightening. This is what makes explorer a very extensible host but at the same time it makes it very slow. Not supporting complex extensibility models works well for me because I disagree with the overhead that they cause and I do not have the time or resources to provide them. Besides, I don't want to get rid of explorer, i just don't want it as the primary interface to manage my files.

Now, enough preliminaries, and before I bore myself to tears (as I am sure I have no readers), let's get down to business:

Some NTFS background
Let’s delve into some basic technical terms related to NTFS to be used on this series.

Sectors: While the physical construction of a disk dictates that it has several platters each divided in cylinders (which are akin to circular tracks) and so on, the built in microcontroller in the disk abstracts all that and presents to the computer a linear addressable space starting from sector 0 to sector N. A sector is thus the minimal addressable unit of I/O on a disk; or in other words, a sector is to a disk what a word is to RAM: There is no way to just read or write just 2 bits. Typically, a sector is 512 bytes and for example in my home PC I have 60115229 sectors in my boot partition.

Partition: A disk can be partitioned among several filesystems with the condition that each filesystem has to span a linear range of sectors. For example, you can have a Linux filesystem between sector m to sector m + p where p times 512 bytes is the size of the Linux partition and then have a NTFS filesystem starting at sector m+p+1 and ending on a sector farther down.

Volume: A volume is the OS representation of a partition that has been formatted with a filesystem that they can operate on so a single physical disk can be represented by several volumes. From the perspective of this project we only care about volumes and in particular NTFS volumes.

Cluster/LCN: The minimal addressable unit in NTFS is called a cluster. A cluster size is always an integer multiple of the sector size; in most cases being 32, 16, 8 or 4 sectors. This is a parameter that can be specified when a partition is formatted with NTFS. Every cluster in NTFS has a LCN (Logical Cluster Number). The cluster number starts with 0 at the first cluster of the file system. By the way the cluster 0 always contains the beginning of a special file known as $Boot, aka the boot record. The boot record is important because it contains the general parameters of the volume, such as total number of sectors, sectors per cluster and where the MFT is located.

MFT: Everything is a file in a NTFS volume. Even the very on-disk structures that control the operation of NTFS. The index to all and every file is the Master File Table ($Mft). The MFT file is really the heart of the volume and is located not too far from the beginning of the volume. There is, of course, a mirror copy of this important file somewhere in the middle of the volume, in case it gets corrupted. By the way, the MFT file is never fragmented and thus at format time it gets a contiguous cluster range reserved that can shrink up to 12.5% of the volume size.

MFT Record: Each entry in MFT is known as a file record and its default size is 1024 bytes. The first 42 bytes is fixed for header and the rest of the entry stores attribute, an example of an attribute is the file name or another one the modified date.

$ Files: The key files that control the operation of NTFS have as prefix the $ (dollar) sign and they are hidden; We have been introduced to two of them $Boot and $Mft but there are others that we'll meet in due time.

The image below is a screenshot of a third party tool showing a partial decoding of the boot record ($Boot) showing the key parameters of my XP boot volume:

Ok, that is all for this post, next time we'll get deep in enemy territory.

Kapor on Software Design

From Mitchell Kapor 1990 article titled "A Software Design Manifesto"

"One of the main reasons most computer software is so abysmal is that it's not designed at all, but merely engineered. Another reason is that implementors often place more emphasis on a program's internal construction than on its external design, despite the fact that as much as 75 percent of the code in a modern program deals with the interface to the user."

"The Roman architecture critic Vitruvius advanced the notion that well-designed buildings were those which exhibited firmness, commodity, and delight.

The same might be said of good software. Firmness: A program should not have any bugs which inhibit its function. Commodity: A program should be suitable for the purposes for which it was intended. Delight: The experience of using the program should be a pleasurable one. Here we have the beginnings of a theory of design for software."

"The software designer is concerned primarily with the overall conception of the product. Dan Bricklin's invention of the electronic spreadsheet is one of the crowning achievements of software design. It is the metaphor of the spreadsheet itself, its tableau of rows and columns with their precisely interrelated labels, numbers, and formulas -- rather than the user interface of VisiCalc -- or which he will be remembered. The "look and feel" of a product is but one part of its design."