Applicable Lessons from the Embedded World (aka Forth rules)

Wes Brown | January 9th, 2009 | Filed Under: Development

Premise and Context

There’s a lot that us security researchers can learn from the embedded side of the computing world. Interestingly, some of the requirements that we have for injection vectors in exploits are congruent with what the embedded world has solved for many years.

One area where we can benefit from the experience of embedded programmers is in the art of writing shellcode. Shellcode needs to be compact to fit within the constraints of injection vectors, but yet needs to have enough functionality to be useful. In a survey of Windows shellcode, they typically range from 170 bytes to 320 bytes in size. Coincidentally, this also falls within the size of many small embedded devices. The ATmega8 used in early Arduino boards has 8K of flash memory and 1K of SRAM. Many early 8-bit computers also fell within this range of capabilities.

Shifting paradigms to view the target victim machine as an embedded device, and the host as a console and serial programmer can be very useful. We can then start to apply principles and capabilities that the embedded world has embraced and used for years.

Enter Forth

One language that was quite popular in the early days of the 8-bit microcomputer and often used in microcontroller projects is Forth. In the hierarchy of languages, Forth lies between assembler and C, but yet it has an interpreter. Forth programs are ‘words’. Forth does not distinguish between words from Forth itself, and words that you have written yourself. Words can even be defined by using an inline assembler.

I have used Lisp in the past to solve security problems, and Lisp is similar in this fashion in that you can redefine the entire language. Lisp and Forth are languages for writing other languages in. The difference is that Forth is far closer to the metal, whereas Lisp abstracts it out with abilities such as a garbage collector. Using Lisp, Scott Dunlop and I implemented MOSREF, a remote execution framework that uses secure communications channels to transmit dynamically compiled bytecode to the remote victim drone. However, the virtual machine was 64K in size, which was sufficient for a second stage payload, but not for first stage shellcode.

The core of Forth is a simple loop that does parsing, and executes Forth words that are responsible for control structures, and this is the ‘compiler’ for Forth programs. Forth does not really have data structures. It just allocates byes of memory and assigns a name to them. The name then returns the address to allow operation on the allocated bytes of memory.

In Forth, there is little difference between the compiler, interpreter, and VM. The nature of the Forth VM allows the sequential expression and execution of code. Every instruction is either inherently understood by the VM, or is defined in terms of things that are inherently understood. It is orthogonal to the extreme.

In sum, Forth is very much like a higher level assembler with a stack. By using Forth, we can abstract out the lower level details of the platform by writing Forth words for that specific architecture. We get the power of assembler in a denser package that is more portable across platforms.

Leveraging Forth

By using a tokenizer and a vocabulary, we can store and use Forth words in a much smaller space than the equivalent assembler instructions. In theory, we could implement a virtual machine inside of 2-bits of Forth vocabulary with the following instructions:

  • LOAD - loads from memory address
  • STORE - stores from
  • ADD - adds two values from the stack
  • IF - conditional branching

In this case, each Forth word would be 2-bits wide. This can be a great advantage when compared to the host instruction language that uses a 16 bit assembler instruction word. If we expand this to 4-bits to allow 16 words in our vocabulary, we can have four Forth instructions for every 16 bit assembler instruction word. We add a few Forth words for defining words, and then we can custom fit the remainder of the vocabulary to the exact purpose at hand.

If we implement a token-threaded Forth with one-byte tokens, we would have 256 possible words that we can define, and still be smaller than assembler programs even on 16-bit platforms. This is further magnified on 32-bit and 64-bit instruction sets.

There is a 3-instruction Forth on the MC68HC11 platform, which is 66 bytes when assembled. If we can get close to this target size on a modern platform such as Intel’s x86, then we would have a potential win in size compared to the 300-byte Windows shellcode. We would have vast tracts of hundreds of bytes to write our programs within!

Expanding Further

Once we have implemented a minimal Forth virtual machine, we can then define special purpose Forth words for our shellcode injection purposes. By defining common functionality that would be in every exploit such as ‘ESTABLISH’ to establish a communications channel to the attacker’s host, and ‘SEND’ and ‘RECEIVE’, we can abstract out common library functionality that differs with each payload. One payload’s ESTABLISH could be using TCP connections, while the other uses ICMP packets. By using a common vocabulary of words, we can then have lower level implementations that differ dramatically in execution. This allows us to have the same higher level logic across different platforms and operating systems, but still have the close-to-metal control. Not only do we gain the equivalent of a cross platform macro assembler, we get much heavier code density, allowing us to fit more functionality into a smaller space.

As Forth is a dynamic language, we can redefine words on the fly. This would allow us to inject our Forth virtual machine as shellcode, then establish communications back to the host. Once we have communications, we leverage the embedded philosophy of having the debugger and compiler on the host side. We can then modify the environment to fit our current needs and interactively control the remote side. The host would run a much larger version of our tiny Forth environment, and do the assembly for our remote drone. The vocabulary on the target would be redefined as we add more words, and then we can use these words in an interactive fashion.

In Conclusion

With the lessons that embedded programming had to offer us in the form of Forth and remote control of a minimal target, we gain much more functional and portable shellcode. By defining a common vocabulary of optimized Forth words in assembler, we gain enormous amounts of flexibility in mixing and matching needed functionality that is not otherwise available. We also gain the valuable concept of modifying the target environment on the fly from a more capable host due to the exigencies of minimal target platforms from the embedded world.

Thanks and Credits

Thanks go to Scott Dunlop and Jim Burnes for being my bouncing board and offering feedback for this project.

Viewing 9 Comments

    • ^
    • v
    Interesting project. Sounds very similar to the metepreter with a bent towards making the payload smaller once you've injected your interpreter. Also I'm surprised you didn't mention forth's role in open firmware as I think that's probably the most common place it's seen. That certainly was the first place I saw it. :-)

    Just out of curiosity any idea what the size in bytes is of the smallest forth implementation for the x86 family of processors?
    • ^
    • v
    Ooops -- answer below.
    • ^
    • v
    Good question, and that's actually kind of hard to answer. All the Forths out there are pretty small already. The answer to the question depends in part on what you're asking. Full featured Forths? Machine Forth for the ARM is 1478 cells of 32 bits. Jone's Forth, when you compile it and strip of symbols, is 8K including ELF headers. I've seen reference to 4K Forth systems. A gentleman said that he implemented Charlie Moore's Machine Forth in 5.5K, and that enough Forth to implement and build itself in.

    So, this is kind of a trick question, as you can probably see. We can get away with implementing our Forth on a host machine, and compiling down a very small Forth with just the words that we need for the purpose.
    • ^
    • v
    A Taste of FORTH

    Wes brings up a good point. Properly engineered, a minimal FORTH would be very useful for penetration and embedded hacking. Before discussing FORTH in the abstract, we should take a look at some basic FORTH. In the example FORTH session below:

    1. The colon character begins a word definition and the semicolon character ends the definition.
    2. To execute a word all you need to do is type in the word and press ENTER.
    3. Pressing ENTER doesn't automatically echo CR
    4. Any numbers entered are pushed onto the stack.
    5. Most words pull their arguments from the stack.
    6. I'll put comments in parentheses, which are also FORTH's words for starting/ending comments

    Example Session

    ( this is a comment. comment text follows an open paren and space -- a comment word )

    ( echo an asterisk to the terminal )

    42 EMIT <enter> * OK

    ( define a word )

    : STAR 42 EMIT ; <enter> OK

    STAR <enter> * OK

    : STARS 0 DO STAR LOOP ; <enter> OK

    CR <enter>
    OK

    CR 20 STARS <enter>
    ******************** OK

    This is the most powerful programming syntax in the world. It is also a knife with which you can cut yourself endlessly. It requires you to define an application-specific vocabulary with which to describe a solution to your programming problem. Your vocabulary will naturally pull its arguments off the stack and each word modifies the state of the program in sequence.

    But you have total control of the interpreter/compiler. If you wish, your new word can read the next word out of the input stream at compile or interpret time which allows you to define your own syntax and programming model. You can even detect whether your word is being run during compile or interpret time and alter it's behavior.

    This is a fantastically powerful and immediate extensible language. You could directly write a simple LISP or C interpreter in FORTH by simply defining a compiler vocabulary.

    Notes:

    While writing this small introduction I noticed that the two best books on FORTH programming and philosophy are now free on the web. They're written by Leo Brodie. Here they are:

    Starting FORTH: http://home.iae.nl/users/mhx/sf.html
    Thinking FORTH: http://thinking-forth.sourceforge.net/

    (I'm a senior software engineer and I believe these books to be some of the most significant works on programming. I'd rank them up there with Knuth's 'Art of Computer Programming', the Dragon compiler book, Wirth's 'Algorithms + Data Structures = Programs' and the Gamma et al "Design Patterns" book.)

    Even if your interest in FORTH is only fleeting, you should really study both of these books. Most programmer's don't get to use their favorite language on a daily basis, but like Tai Chi FORTH may not become your primary tool, but it could become your primary discipline as it focuses your mind and makes you a better practitioner in whichever language you use.

    Good luck

    Jim Burnes
    • ^
    • v
    In my hometown, we had a saying about FORTH:

    eww.

    :)
    • ^
    • v
    "However, the virtual machine was 64K in size, which was sufficient for a second stage payload, but not for first stage shellcode." Just wanted to add a datapoint from an interview this week with an adware author: http://philosecurity.org/2009/01/12/interview-w... : <quote>I said, “Let’s install a Turing-complete language,” and for that I used tinyScheme, which is a BSD licensed, very small, very fast implementation of Scheme that can be compiled down into about a 20K executable if you know what you’re doing.</quote>.
    • ^
    • v
    Keep in mind that much of the 64K budget went to a full out cryptography implementation, with primitives for ciphers and random numbers. Some of that also went to network I/O and the like. If we measured the actual VM implementation itself, it would be pretty close to 20K. I believe we ended up at 32K.
    • ^
    • v
    Hi Jim
    long time no see no hear
    ah yes , forth, fig forth etc ad nauseam is ported to more platforms on the planet than just about anything else.
    Also highly useful in writing portable worms/viruses/malware


    gwen hastings
    • ^
    • v
    Great read, I have enjoyed reading it.

    Rina

Trackbacks

close Reblog this comment
Powered by Disqus · Learn more
blog comments powered by Disqus