Abstract

When Forensic examiners and Incident response teams approach a computer system, quite often RAID Drives are involved. RAID arrays are now commonly found on many computers - from the expensive enterprise server machines, all the way to desktop machines. Imaging these machines is often challenging since reconstituting RAID logical images in the lab may be difficult without the identical controller used to create the array, and an identical configuration. Sometimes the controller may not accept the disks as members of the array if the array header is damaged or overwritten, making it impossible to reconstruct the logical image using conventional means.

This paper covers the manual reconstruction of RAID sets. A method is presented to manually recover the RAID reconstruction map, and tools are presented to use this map for reassembling the original RAID set or simply use the entire set as evidence without reassembly.

Introduction

RAID disks have become popular in recent years even in low end systems. When confronted with a RAID system, the investigator is often confronted with a difficult choice.

One reliable way for imaging this system is to attempt booting the system from a CDROM into a forensic platform such as KNOPPIX or Helix for example. These platforms have drivers for many RAID controller which would often allow the array to be seen as a single logical disk. Then the investigator would image the device over the network, USB or FireWire to another machine.

The above method is very reliable and certainly should be used as the first port of call. However, often this method fails:

Often the drivers present in the forensic operating system do not support the RAID controller. If the controller does not have native Linux support this might be a problem.
The RAID is done in software using a proprietary product. There are no Linux drivers that are capable of reading such an array.
The headers on the disks are damages or the disks are marked as bad, leading the array controller to refuse to use these disk, despite the fact that the disks themselves might be readable.
It is impossible to obtain the original controller and BIOS configuration. This might happen if the controller has been destroyed or is simply unavailable.

In these cases the RAID will have to be reconstructed by hand. This paper will detail a method to allow this process to be done reliably.

RAID Overview

RAID arrays are commonly found in a number of configurations. The following is simply a brief overview of some of the common configurations, although other configurations are possible, these are the most common. All configurations strike a balance between speed storage space and redundancy.

RAID 0

The RAID 0 (stripping) configuration does not provide any redundancy. It aims to increase the speed and space provided by the array. Data is stripped across all the disks, with consecutive blocks on consecutive disks:

RAID 0 allocation pattern

The diagram above shows how blocks are distributed among the disks in the array. As can be seen, the logical blocks are distributed sequentially through all the disks at the same physical block address. Hence the RAID 0 configuration provides n times the space storage (when n is the number of disks in the array). Write and read speed are also increased n fold as consecutive blocks may be stored in different disks simultaneously.

RAID 1

This configuration (mirroring) is designed to provide redundancy rather than storage or speed. The block allocation is shown in the figure:

RAID 1 allocation pattern

Logical blocks are copied to each disk separately. Hence if a disk is lost, the block may be recovered from one of the other disks. The configuration provides redundancy but uses n times the logical storage provided in hard disk space. This configuration also provides an n fold increase in sequential reading speed, since sequential blocks may be read simultaneously, but does not offer improvement in writing speed.

RAID 5

This configuration strikes a balance between redundancy and space. The redundancy is provided by using a parity block which is moved around the array in a specific pattern. The parity block is generated by taking performing an xor operation on all other physical blocks in the array:

RAID 5 allocation pattern

Performing an Xor operation of all the blocks at the same physical block location will result in 0. If one of the disks fail, its contents may be reconstructed by xoring all the other disks together.

Although the above description seems simple enough, the actual striping pattern on the disks is often different and implementation dependant. Further, the order of the disks may be unknown or completely different from the order with which the disks are labelled on the front of the machine. These factors contribute to making RAID reconstruction a more complex task.

Definitions

In this paper we concentrate on reconstructing RAID 5. RAID 0 reconstruction is analogous (except there is no parity to consider), while RAID 1 is trivial (simply take one of the disks). The following set of definitions is used:

Block, Block size: A unit storing contiguous data. The Block is the basic unit used by the controller. Data within the block is contiguous. Blocks are usually multiples of 512 bytes (often 4k - 64k). The block size is the size in bytes of this unit. The block size is common to both logical blocks and physical blocks.
Logical Block: A logical block refers to the logical data stored on the array. Logical blocks represent contiguous logical data, but will be physically stored on different disks at different physical block locations.
Physical Block: Physical blocks reside on the disks. Physical block numbers are consecutive on the disk, but do not represent consecutive data within the logical data stream. For example, in the RAID 5 diagram above, the physical block 1 for disk 1 is said to store logical block 2.
Parity Block: A special type of block obtained by taking the Xor operation of all logical blocks found at the same physical block number on all the disks.
Striping Map: This is a map relating logical block numbers to physical block number and disk number tuples. For example in the RAID-5 figure above the map would start 0=>(0, disk 1), 1=>(0,disk 2) etc..
Physical Array period, Logical Array Period: All RAID implementations use repeatable patterns for their Striping maps. The physical period is the number of physical blocks used before that pattern is repeated, while the logical period is the total number of logical blocks that will fit within a physical period. For example, in the RAID-5 figure above, if the next physical block (3) was: 6,7,P(6+7), it would be exactly the same as physical block 0, and hence the physical period would be 3, while the logical period would be 5.
Slot: A slot represent a relative physical block within the period. That is, the slot is the remainder after dividing the Physical block with the period. Since the Striping Map repeats with the array period, a slot represents a sequence of physical blocks an integer number of array periods apart. For the example above, the slot 1 would represent physical blocks 1,4,7,10... Slots allow us to compress the Striping Map to the period length. The striping map is therefore represented as a table with as many columns as disks, as many rows as the physical period length and logical blocks numbered in the table cells (see examples above).

Reassembling the RAID

In order to reassemble the array, it is necessary to follow this rough order of tasks:

Find the block size.
Determine the physical array period by following the parity blocks around the disks.
Construct the Striping map by inspecting which physical blocks follow each other throughout the image. Reinforce this observation by looking at different physical blocks representing the same slot position.
Often reordering the disks will produce a much more obvious pattern in the striping map. This pattern will allow the investigator to guess the complete pattern without having to confirm each element in the map.
Reassemble the map, attempting to recover useful data from the array. If the map is correct the reassembled array will be error free.

Example

The following example helps to illustrate the technique. In order to allow readers to try this technique themselves, a test RAID set was generated and is available for download in PyFlags standard tutorial samples. The generated sample is very similar to a real hardware RAID implementation, but is far smaller to download. It is recommended that readers download the example and work through it as they read this paper to really gain a feel for the technique.

There are 3 images in this case d1.dd, d2.dd and d3.dd. Although the images are numbered sequentially, their number do not necessarily correspond to their position in the RAID set. The controller will usually assign an arbitrary ordering for the disks, such that permutations of the disk numbering will yield an array similar to the figure above.

Finding the block size

The first thing we must do is determine the block size of the array. This is done by noting where there may be discontinuities in the stream of data.

Note

Both the file-system and the RAID controller write data in blocks. The RAID block size is an independent concept from the filesystem blocksize. Note that filesystems will also tend to fragment files along filesystem block size. This fragmentation may be mistaken to be a discontinuity in the data stream. By taking repeated measurements at different places in the disk we can distinguish the filesystem and RAID block size.

We can use the hexdump utility to visually inspect for data discontinuities. It is most useful to search for areas containing a lot of text, making it easier to inspect the discontinuity:

$ hexdump -C d1.dd | less
...
0001dfe0  73 04 53 28 02 68 72 65  28 00 02 00 00 00 05 0d  |s.S(.hre(.......|
0001dff0  19 18 04 4b 65 73 09 00  28 01 70 6f 73 1a 7c 70  |...Kes..(.pos.|p|
0001e000  20 61 73 20 70 6f 73 73  69 62 6c 65 20 73 6f 20  | as possible so |
0001e010  69 74 20 6d 61 79 20 62  65 20 69 6e 73 74 61 6c  |it may be instal|

Clearly there is a discontinuity on offset 0x1e000. Now we look around the same area to find discontinuities at:

offset Disk

0x1e000 D1

0x20000 D1

0x21000 D1

0x23000 D1

0x1f000 D2

0x20000 D2

0x22000 D2

0x1f000 D3

0x21000 D3

Note that although the first disk does not have a discontinuity at 0x1f000, D3 does. It is perfectly normal for a disk to not display a discontinuity where another disk does. This just means that consecutive blocks are stored on that disk.

From the above we deduce that the block size is 0x1000 = 4096 bytes since all discontinuities are aligned on this boundary. Note that we could have selected a block which is smaller than this (since all discontinuities align on the 0x100 boundary as well). If we did that we would have ended with a more complex reassembly map, but it would have still worked.

Constructing the RAID re-assembly map

The next step requires us to follow the parity blocks around the disks, this sounds simple, but there are a number of pitfalls:

When one of the disks is 0, the other two disks will be the same which makes it impossible to tell which one is the actual parity.
When the disk is full of random binary data, it is impossible to tell which disk carries the parity and which is just binary data.

Hence we need to tabulate where the parity is. It is ok to leave some rows empty, so if there is an ambiguity (e.g. too many zeros on one of the disks), we just leave that row as blank. To make it easier we can work in the region found before which is known to contain a lot of plain text. Its also useful to note down what text the block starts and ends with:

Offset

0x1e000(30)

as possible..

...

during scann

Binary

...

Binary

Parity

...

Parity

0x1f000(31)

ing...

...

href="./Documen

Parity

...

Parity

tation/tutorials

...

href="./defau

0x20000(32)

Parity

...

Parity

g has not

...

class="a

lt.css"

...

<p>PyFla

0x21000(33)

<a href=

...

dmonition-

...

Parity

...

In the above table we document the start and end of each block from block (30) to block (33) across all disks. After close examination we can deduce which block follows which (D1B30 means disk 1 block 30 below):

D1B30->D1B31 : scanning
D1B31->D3B31 : href="./Documentation/tutorials
D3B31->D3B32 : href="./default.css"
D3B32->D2B32 : <p>PyFlag has not
D2B32->D2B33 : class="admonition-

We can now tabulate the striping order:

Block D1 D2 D3

30 1 0 P

31 2 P 3

32 P 5 4

33 7 6 P

We deduce therefore that the period is 3 (Because it takes 3 block before the parity returns to the same disk). If the period is 3, then block 30 corresponds to slot 0, block 31 - slot 1 etc. We can thus rewrite out reassembly map in terms of slots, logical blocks and disks:

Slot D1 D2 D3

0 1 0 P

1 2 P 3

2 P 5 4

As a final check we use the file program to determine the headers of each disk:

$ file d?.dd
d1.dd: data
d2.dd: x86 boot sector, extended partition table
d3.dd: x86 boot sector, extended partition table

It may seem odd at first that we have 2 disks with partition tables on them, but after inspecting the first block of d1.dd we find it to consist of a run of zeros. From our RAID map we know that Disk 2 carries the first logical block, and that Disk 3 is the parity - which happens to be a copy of Disk 2 since disk 1 is zero.

Finally we reassemble the RAID. PyFlag has the ability to use the RAID set directly given a RAID map, without needing to actually rebuild the array. The PyFlag hooker allows us to run forensic utilities directly on the RAID's logical data:

~/pyflag$ ./bin/iowrapper -i raid -o blocksize=4k,slots=3,\
  map=1.0.P.2.P.3.P.5.4,filename=d1.dd,filename=d2.dd,\
  filename=d3.dd mmls -t dos foo

Set number of slots to 3
Set file number 0 as d1.dd
Set file number 1 as d2.dd
Set file number 2 as d3.dd
DOS Partition Table
Units are in 512-byte sectors

     Slot    Start        End          Length       Description
00:  -----   0000000000   0000000000   0000000001   Primary Table (#0)
01:  -----   0000000001   0000000062   0000000062   Unallocated
02:  00:00   0000000063   0000009829   0000009767   Linux (0x83)
03:  00:01   0000009830   0000020479   0000010650   Win95 FAT32 (0x0C)

We see that we have a linux partition and a FAT partition on the array. Let us list the files in the Linux partition:

~/pyflag$ ./bin/iowrapper -i raid -o blocksize=4k,slots=3,\
  map=1.0.P.2.P.3.P.5.4,filename=d1.dd,filename=d2.dd,\
  filename=d3.dd,offset=63s ./bin/fls -r -f linux-ext2 foo

Set number of slots to 3
Set file number 0 as d1.dd
Set file number 1 as d2.dd
Set file number 2 as d3.dd

d/d 11: lost+found
d/d 1281:       website
+ d/d 12:       _darcs
++ d/d 13:      patches
...

Let us reconstruct the array into a single dd image so other forensic packages may be able to use it. This is done by hooking dd and redirecting the output:

~/pyflag$ ./bin/iowrapper -i raid -o blocksize=4k,slots=3,\
  map=1.0.P.2.P.3.P.5.4,filename=d1.dd,filename=d2.dd,\
  filename=d3.dd dd bs=4k if=foo > /tmp/reassembled.dd
Set number of slots to 3
Set file number 0 as d1.dd
Set file number 1 as d2.dd
Set file number 2 as d3.dd
20480+0 records in
20480+0 records out
10485760 bytes transferred in 0.072855 seconds (143926572 bytes/sec)

Assume now that one of the disks is missing, or corrupted and we did not want to use it. Since RAID 5 provides us with redundancy as well, we are now able to rebuild the third disk on the fly as needed:

~/pyflag$ ./bin/iowrapper -i raid -o blocksize=4k,slots=3,\
  map=1.0.P.2.P.3.P.5.4,filename=d1.dd,filename=d2.dd,\
  filename=foo,offset=63s ./bin/fls -r -f linux-ext2 foo

Set number of slots to 3
Set file number 0 as d1.dd
Set file number 1 as d2.dd
Set file number 2 as foo
Could not open file foo, marking as missing
d/d 11: lost+found
d/d 1281:       website
+ d/d 12:       _darcs
++ d/d 13:      patches
...

As can be seen in the above example, the missing disk was automatically rebuilt on the fly by using the parity in the other disk. This is done without having to perform a time-consuming rebuild operation.

Guessing the RAID configuration

The above paper discussed the deduction of a RAID map from first principles. Clearly this process is manual and time consuming. Traditionally after deducing the map, the analyst needs to re-assemble the array by copying the data into a single logical image. This process could take a very long time, particularly if the array is large. Once the image is reconstructed, the analyst may attempt to mount the partition and hope that the map is correct.

Due to this time intensive process it is traditionally not practical to guess the map. However the PyFlag hooker iosubsystem allows for the array to be transparently reconstructed on demand. In combination with a tool that is sensitive to errors in the image, it is possible to guess the RAID map and disk order rapidly.

Lets illustrate this technique with the above sample image. We can deduce where a partition should occur by running the mmls tool on all the physical disks, as before deducing the first partition begins 63 sectors into the logical disk.

We now run the pyflag guess_raid.py program to try and guess the RAID map and disk order. This program guesses a disk order and runs an external program to determine if the resulting reassembled logical disk makes sense. We use fls from the Sleuthkit to list the content of the partition. If the RAID map is incorrect, there will be errors in the resulting logical disk, leading to fls not being able to list all the files in that partition:

~/pyflag$ ./launch.sh utilities/raid_guess.py -o 63s d1.dd d2.dd d3.dd

------------------------------------------------------
Trying map 0.1.P.2.P.3.P.4.5 with 3 slots
------------------------------------------------------
Running ./bin/iowrapper -i raid -o blocksize=4k,slots=3,
map=0.1.P.2.P.3.P.4.5,offset=63s,filename=d1.dd,filename=d2.dd,
filename=d3.dd ./bin/fls -r -f linux-ext2 foo:
- produced 0 lines of data:

Running ./bin/iowrapper -i raid -o blocksize=4k,slots=3,
map=0.1.P.2.P.3.P.4.5,offset=63s,filename=d1.dd,filename=d3.dd,
filename=d2.dd ./bin/fls -r -f linux-ext2 foo:
d/d 11:       lost+found
d/d 1281:     website
+ d/d 12:     _darcs
++ d/d 13:    patches
...
+ d/d 1297:   libs
+ r/r 1298:   faq.txt
+ r/r 1299:   faq.txt~
- produced 53 lines of data:
...
Running ./bin/iowrapper -i raid -o blocksize=4k,slots=3,
map=0.1.P.P.2.3.5.P.4,offset=63s,filename=d2.dd,filename=d1.dd,
filename=d3.dd ./bin/fls -r -f linux-ext2 foo:
d/d 11:       lost+found
d/d 1281:     website
+ d/d 12:     _darcs
++ d/d 13:    patches
...
+ d/d 1297:   libs
+ r/r 1298:   faq.txt
+ r/r 1299:   faq.txt~
- produced 184 lines of data:
...
**********************************************
Best result produced 184 lines with command line:
./bin/iowrapper -i raid -o blocksize=4k,slots=3,
map=0.1.P.P.2.3.5.P.4,offset=63s,filename=d2.dd,filename=d1.dd,
filename=d3.dd ./bin/fls -r -f linux-ext2 foo
**********************************************

As can be seen above, if the map or order are incorrect, the fls tool is unable to list all the files (although it may be able to list some of the files). The correct map can then be determined by the combination yielding the most files in the listing.

Clearly this technique is prone to problems. Some of the problems may be:

If the filesystem is corrupted on the logical image, we may not be able to distinguish between the filesystem being corrupted or the RAID being reassembled incorrectly.

The raid_guess.py program uses a library of possible maps to try. These maps were derived by observation of implementations in the wild, but none of these may be applicable for this specific case.

It is always worth giving the guess method a go first because it is very quick and has a good chance of working. If this method does not work, it is possible to go through the more elaborate and time consuming method described previously.

Conclusions

We have presented a technique that may be used to reassemble an arbitrary RAID configuration with no knowledge of the particular type or configuration of the RAID controller. This can be used in cases where the array can not be imaged as a single logical drive, and individual drives must be imaged separately.

RAID Reassembly - A forensic Challenge