Magnetic-Based versus Flash-Based Storage

This article is the answer I wrote to an exam question for a basic cyber forensics course I took back in Feb 2009. I recently ran across this exam in my files and thought others might be interested in a high-level overview of the differences between magnetic-based and flash-based storage technologies…

The Question

“Briefly discuss the differences between magnetic-based storage and flash-based storage. What effect do these differences have on digital evidence investigations?”

My Answer

Between the two types of disk storage technology of magnetic-based and flash-based hard drives (HDDs and SSDs respectively), magnetic-based drives are more common, with flash-based drives quickly gaining speed in development and adoption rates.

Magnetic-based drives use a series of stacked metal or glass disks called “platters”, which store microscopic magnetic information on concentric rings called “tracks”, which are further split into smaller “sectors” of 571 bytes each. A sector only holds 512 bytes of actual data and uses the remaining bytes for syncing purposes, a header with a location ID, and error detection via CRC checksums. A magnetic read head hovers over the metal platters as they spin, and depending on the electrical impulses that motion creates, you get either a one or zero represented as binary data. A “cylinder” is the combined data for a single track on all of the platters in a drive (both sides of each platter). Once the data is read, on-board hardware decodes that information and transmits it to the computer via a standardized interface.

Flash-based drives are quite different. There are no physically moving parts, and they store data electronically instead of magnetically. Using a pair of transistor gates (a float gate and a control gate), flash-based storage sends electrical impulses to logically segmented areas in memory to store the appropriate ones and zeros in binary format (just like magnetic drives). Because they use only electricity and don’t have to wait for actuator arms to physically move heads into position for reads and writes, flash-based storage is typically much faster at I/O operations. Like magnetic drives, flash-based drives also have a built-in hardware controller to manage its operation and to convert the data into a standardized format to be read by the computer.

The effect each one of these has on a digital investigation is wide-spread. First of all, they both retain data for different amounts of time when left sitting. Magnetic data is not very reliable after a year or so, while flash-based data will usually last quite a bit longer. Flash-based memory also has a limited number of erase cycles, after which, whatever data is stored on that segment will not change. This can actually help in an investigation if you can trick the hardware controller into thinking it can no longer use the memory, you could essentially turn it into a read-only device and preserve evidence. Likewise, magnetic disks often have a residual magnetic signature of previous data, even if it has been overwritten. Sometimes these properties can be exploited by an expert lab with the proper equipment to recover data that was intentionally destroyed.

Both storage mediums will usually not overwrite data when it is deleted, but will simply update an allocation table to specify that a cluster or segment is free for writing again.

Keeping in mind how each of these technologies transforms physical properties into a common, logical storage interface can help you to make better decisions on how to preserve data, how to find evidence, and what to expect when doing an investigation. If you don’t pay attention to how these technologies differ, you have the potential to either miss important information, or in the worst case, destroy the information you do have.

Beginning Factor – Shufflers & Combinators

In the previous installment of Beginning Factor, we discussed some of the attributes of stack-based languages and the syntax for defining words in Factor. This time around, I’d like to introduce stack shufflers, quotations & combinators, and touch on some more basic data types and their properties.

Up until now, we’ve essentially been using Factor as an overqualified RPN calculator. I just wanted to make sure that you don’t underestimate Factor because of these particular examples; Factor is an extremely capable and modern language that can be used for everything from web applications, to game development, to complex text parsing, and so on. I’m purposefully using over-simplified examples as a means to demonstrate specific points about the language. Stick with me, and I assure you the examples will gradually get more expressive.

Stack Shufflers

Because of Factor’s stack-based nature, you sometimes need the ability to rearrange or copy items in the stack to ensure that they are in the correct position for future use. The way to go about this is a group of words called “stack shufflers”.

Much like the name implies, stack shufflers are merely words that change the order (or number) of the items on the top of the stack. It is said that shuffle words “control the flow of data between words that perform actions.” In fact, you already know one stack shuffler… drop

There are three basic varieties of stack shufflers. Here they are along with the most commonly used word for each type:

  1. Removing Shufflers

    drop ( x -- )
    removes the top item from the stack and discards it

  2. Duplicating Shufflers

    dup ( x -- x x )
    duplicates the top item on the stack

  3. Permuting Shufflers

    swap ( x y -- y x )
    exchanges the positions of the first and second items on the top of the stack

Swapping Two Items on the Top of a Stack

…and here are a couple of word definitions that use these shufflers appropriately:

: sq ( x -- y )
    dup * ;

: neg ( x -- -x )
    0 swap - ;

(scratchpad) 5 sq .
25
(scratchpad) 1 neg .
-1

Caveats

There are many more shuffle words that support intricate rearrangements and the duplication/removal of multiple items from differing locations within the stack. The problem is, code that is full of stack shufflers can easily become confusing. In general, you should try to minimize the use of stack shufflers to keep things understandable.

Of course there are exceptions to that rule, times when shufflers make the most sense, but the preferred alternative to complicated stack shufflers is the use of a “combinator” that fits your use case. That said, combinators will take a bit of explaining…

Quotations

Before we can get to the idea of combinators, we first have to discuss quotations:

(scratchpad) 5 [ "hello" print ] times
hello
hello
hello
hello
hello

In this example, [ "hello" print ] is a quotation.

In layman’s terms, a quotation is a way to encapsulate a snippet of code so it doesn’t get called right away, but can be passed around on the stack and called later. The computer science term for this is an “anonymous function”. It’s referred to as “anonymous” because it is fundamentally a word that has no name.

If we didn’t have quotations, that same example would get ugly real fast:

(scratchpad) "hello" dup dup dup dup print print print print print
hello
hello
hello
hello
hello

Imagine if you wanted to print “hello” 1000 times!

To create a quotation, you just surround your code snippet with square brackets, and it will be pushed onto the stack: [ ... ]. In order to do anything useful with that quotation once it’s on the stack, what you need is a combinator.

What is a Combinator?

A combinator is just a fancy name for a word that takes a quotation as one of its inputs. In the example above, times is a combinator which takes an integer (n) and a quotation from the stack, and it calls that quotation n times.

Factor uses quotations & combinators extensively for conditionals, sequence traversal, namespaces, closures, and more…but that’s jumping the gun a bit. Before we dive into all of that, I’d like to get back to the idea of minimizing the use of stack shufflers by replacing them with appropriate combinators instead.

Combinators That Express Intent

While our code examples thus far have been easy to follow, when you start tackling more realistic problems, stack shufflers will begin to obfuscate your code. If we can represent our intentions consistently with a combinator instead, then code becomes cleaner and you can consequently focus more on your problem domain and less on mentally organizing your stack.

To illustrate this point, I’d like to introduce a couple of simple combinators:

dip ( x quot -- x )
calls a quotation while temporarily hiding the top item on the stack
keep ( x quot -- x )
calls a quotation with an item on the stack, restoring that item after the quotation returns

While both of these combinators have the same stack effect declaration, their usage is a bit different:

(scratchpad) 1 2 4 [ + ] dip

--- Data stack:
3
4

(scratchpad) clear
(scratchpad) 1 2 4 [ + ] keep

--- Data stack:
1
6
4

These two combinators alone can greatly reduce the number of stack shufflers your code will need. If you’re curious about how these combinators work, they both secretly take advantage of an auxiliary stack (called the “retain stack”) to temporarily store items while the supplied quotation is being executed. There are a few other preserving combinators that are worth exploring as well.

Cleave, Spread, and Apply

The cleave, spread, and apply combinators are your best weapons when trying to reduce the use of stack shufflers while simultaneously expressing intent. The key point being that they should express intent…if you find yourself writing code where these combinators don’t fit logically, then try another option.

  1. Cleave Combinators

    These are used when you want to apply multiple quotations to the same set of items on the top of the stack.

    Let’s say that you want to find the average of a bunch of numbers in an array. The steps are straightforward, you take the sum of all the numbers and divide that sum by how many numbers you have (the length of the array):

    (scratchpad) { 1 2 3 } dup sum swap length / .
2

    We can eliminate the need for those stack shufflers and better express our intent by using a cleave combinator to achieve the same thing:

    bi ( x p q -- )
    applies quotation p to x, then applies quotation q to x

    Cleave Combinator Demonstration

    (scratchpad) { 1 2 3 } [ sum ] [ length ] bi / .
2

    The different cleave combinators change either the number of quotations applied to your items (bi vs. tri), or the number of items used as input for your quotations (bi vs. 2bi).

  2. Spread Combinators

    These are used when you want to apply a different quotation to different items on the top of the stack. The spread combinators are closely related to dip, but provide a bit more flexibility while also expressing intent.

    Let’s say that you have two coordinate positions in the form of { x y }, and you’d like to extract the x-coordinate from the first position, and the y-coordinate from the second position to form a new position with those values:

    (scratchpad) { 1 2 } { 3 4 } swap first swap second 2array .
{ 1 4 }

    We can eliminate the need for those stack shufflers and better express our intent by using a spread combinator to achieve the same thing:

    bi* ( x y p q -- )
    applies quotation p to x, then applies quotation q to y

    Spread Combinator Demonstration

    (scratchpad) { 1 2 } { 3 4 } [ first ] [ second ] bi* 2array .
{ 1 4 }

    When you want to do the same thing with more than two quotations/items, then using spread combinators eliminates the need for nested dips or shufflers and the added clarity becomes much more evident.

    The different spread combinators change the number of quotations applied to the corresponding number of items on the stack (bi* vs. tri*).

  3. Apply Combinators

    These are used when you want to apply a single quotation to multiple items on the top of the stack.

    Let’s say that you have two strings, each containing a name, and you want to see if those names are the same. In order to ignore case when doing the comparison, you decide to convert both strings to upper case before checking for equality:

    (scratchpad) "john" "John" swap >upper swap >upper = .
t

    We can eliminate the need for those stack shufflers and better express our intent by using an apply combinator to achieve the same thing:

    bi@ ( x y quot -- )
    applies the quotation to x, then to y

    Apply Combinator Demonstration

    (scratchpad) "john" "John" [ >upper ] bi@ = .
t

    The different apply combinators change the number of items on the stack your quotation is applied to (bi@ vs. tri@).

The cleave, spread, and apply combinators are all closely related; if you’re having trouble keeping them apart, try to memorize the naming convention:

Once you learn these combinators, you should be able to express almost any pattern of complicated stack shufflers. Note that there are also generic forms for all of these combinators that can take additional inputs from the stack. If you find that you resort to using the generic forms more often then not, that’s usually a good indication that you should rethink your approach or put your data into a more appropriate structure.

Data Type Details

Before I turn you loose, I wanted to offer a few extra details about some of Factor’s basic data types…

Sequences

In the cleave and spread examples above, I was sneaky and used sequences without explaining them formally. A sequence is a finite, ordered, collection of elements. Any data type that implements the sequence mixin class (meaning a data type that knows its length and will let you set/get an element at a specific index) gains the ability to use the powerful built-in sequence operators. Read through that documentation to get an idea on how to manipulate sequences and their elements.

Factor has many sequence types that you may already be familiar with, such as arrays (fixed-size mutable sequences) and vectors (resizable mutable sequences), but there are also other data types that you might not expect to be sequences, such as strings. In Factor, a string is merely an array of Unicode 5.0 code points.

Using the sequence operators and combinators together, you can create all sorts of powerful abstractions that I’ll talk more about next time. Here are a couple of examples to whet your appetite:

(scratchpad) { 1 2 3 4 5 } [ even? ] filter .
{ 2 4 }
(scratchpad) { 1 2 3 } [ . ] each
1
2
3
(scratchpad) "Hello" [ alpha? ] all? .
t
(scratchpad) "Hello!!!" [ alpha? ] all? .
f

Keep in mind that in Factor, sequences are zero-based.

Numbers

So far, we have only used integers, but Factor also supports rational numbers (fractions), floats (decimal approximations of a number), and complex numbers (imaginary numbers).

(scratchpad) 100 330 / .
10/33
(scratchpad) 5/4 1/2 + .
1+3/4
(scratchpad) 5/4 0.5 + .
1.75
(scratchpad) 2 5 rect> .
C{ 2 5 }

Iota

One last thing that is going to come in handy, is a word for creating sequences from integers:

iota ( n -- iota )
creates a sequence of length n, whose elements are its non-negative predecessors (i.e. 0 to n-1 inclusive)

This word can be very helpful when performing counted loops or other control flow statements. For example, the following two lines are equivalent:

{ 0 1 2 3 4 5 6 7 8 9 } [ . ] each

10 iota [ . ] each

Next Time

Next time we’ll stick with a theme of “flow” and discuss control flow for your words and after that, the typical work flow when developing code with Factor. Hope you enjoyed this installment!

Beginning Factor – Introduction

I’ve been involved in the Factor programming language community for about a year now, and am constantly amazed with how productive its contributors are. Large improvements to the language and its libraries are made on a weekly (if not daily) basis, and it’s finally starting to attract some much-deserved attention from the programming community.

The problem is, the language is a huge departure from the norm for most developers and it can be overwhelming to someone just getting started. I would like to help ease that transition by posting on various topics that I know have been confusing to me over the past year.

Note that many topics are covered in the official FAQ — which is well worth a read — and I won’t spend time covering how to install Factor on the 14 or so platforms it supports, but beyond that, I’ll try to give enough information (from basic to advanced) to get you going.

The Basics of the Basics

First of all, Factor is a stack-based language, which means that it uses a stack to store all arguments and returned values from functions (called “words” in Factor). To put that another way, Factor words don’t receive arguments in the traditional manner; all input values that your word needs are expected to already exist on the top of the stack.

What is a Stack?

If you’re unfamiliar with the data structure called a stack, the concept is fairly simple. It centers around the idea of “Last In First Out” (LIFO), meaning the last item placed onto the stack is the first item that will you will get when you remove an item from the stack. You cannot get to the lower items until the all of the items above it have been removed.

I like to picture a stack like a tower of LEGOs. The only thing you can do with it are add another brick to the top (“push” an item onto the stack), or take the top brick off to use it for something else (“pop” an item off the stack). That’s all there is to stacks!

Pushing an Item onto a Stack

How to Use the Stack

So, now we know that Factor manages its input and output with a stack, but how do we actually use it? Well, when entering data into Factor’s listener, one of two things is happening:

  1. You are pushing a literal onto the stack
    OR
  2. You are calling a word which will consume literals from the stack

Things do get slightly more complicated than that, but for the most part those two rules hold true. The most simple example of this behavior is the ubiquitous hello world program, shown entered directly into Factor’s interactive listener environment:

(scratchpad) "Hello world!" print
Hello world!

To understand what is happening, you can just type the string first, and then execute the print word later:

(scratchpad) "Hello world!"

--- Data stack:
"Hello world!"
(scratchpad) print
Hello world!

In this particular case, typing the literal string "Hello world!" will push that value onto the stack; then the word print, takes a single string off the stack and writes it to the output stream.

The same idea can be applied to simple arithmetic. Like strings, numbers are also literals, so you just have to type them in (separated by spaces) for them to be pushed onto the stack:

(scratchpad) 2 3

--- Data stack:
2
3

NOTE: the stack is displayed in the listener upside-down from the way you’d think, so the bottom number is actually the top of the stack.

…and if you want to add the top two numbers together, the + word will simply pop two numbers off the stack, add them together, and push the result back onto the stack:

--- Data stack:
2
3
(scratchpad) +

--- Data stack:
5

A Few More Words

If you start messing around in the listener, odds are your stack is going to grow pretty quickly and become unmanageable. There are a few words that are essential to know in order to keep things under control:

drop ( x -- )
removes the top item from the stack and discards it
. ( obj -- )
takes the top item from the stack and prettyprints it
clear ( -- )
removes all items from the stack
(scratchpad) 2 3 -

--- Data stack:
-1
(scratchpad) drop
(scratchpad) 20 5 / .
4
(scratchpad) 2 3 + 6 7

--- Data stack:
5
6
7
(scratchpad) clear
(scratchpad)

Ramifications of Stack-Based Design

From these simple examples, we can observe a couple of important things about Factor:

  1. Postfix Notation

    When using a stack, passing data becomes implicit and we can assume that all input needed by words already exists on the stack. This naturally lends itself to using postfix notation because you have to push your data onto the stack before you can use it.

    This also makes words more concise and unambiguous when compared to infix notation and eliminates the need for copious amounts of parentheses used by prefix notation languages, like Lisp or Scheme.

    POSTFIX:  6 5 4 * +
INFIX:    6 + 5 * 4 =
PREFIX:   (+ (* 4 5) 6)

    With the infix example above, you’d have to know order of operations rules in order to get the correct answer (or use parentheses to force the matter). When using postfix notation, the fact that multiplication is done first becomes explicit. Prefix notation also gets rid of that ambiguity, but becomes messier and harder to type with the more nesting you add.

  2. Calling Words is Implicit

    You don’t have to specify that you’re calling a word, you simply use the word. This, combined with postfix syntax, means that you can easily nest words or cut and paste parts of definitions into new words without disrupting the flow of data. This lends to keeping code modular, short, easily testable, and readable.

Your First Word

If you’ve typed in the examples from above and messed around in the listener, then you might want to know how to write your own word rather than just using ones that are predefined. Drawing on what we already know, here’s how to write your first word:

: plus-two ( x -- y )
    2 + ;

If you copy and paste that into your listener, than you can use the word plus-two anywhere you would like to add two to a number on the top of the stack:

(scratchpad) 15 plus-two .
17

Not very exciting, but it gives us a couple more things to talk about…

Syntax Specifics

If you study the word definition, you’ll see that it’s made up of a few elements:

: plus-two ( x -- y )
    2 + ;
  1. A colon (:) is used to start the definition of a word. This is required and must have a space after it.
  2. Right after the opening colon is the name of your word, also required.
  3. Following the name of your word is its stack effect declaration, which is a list of the word’s inputs and outputs separated by -- and surrounded by parentheses. All words must have a stack effect declaration unless it only pushes literals on the stack. The names of elements in the stack effect declaration don’t make a difference, only the number of elements. That means that ( elt elt -- seq ) and ( x y -- z ) are the same thing. There are some common conventions for these names, but don’t get caught up by it as I’ll talk more about them in a later article and it won’t change how your program runs.
  4. Next comes the word definition itself, in this case 2 +.
  5. And the last item is a semicolon (;), used to end the word definition. This is required and must have a space before it.

The reason that everything must be surrounded by spaces is that there aren’t any syntax-only elements to Factor…everything is a word! The colon/semicolon, the parentheses, etc. are all just parsing words working together in order to create the syntax.

Next Time

Next time we’ll talk more about stack shufflers, quotations & combinators, details about more datatypes, and more…

If something is unclear or if you’re having any trouble, let me know and I’ll try to help out!