Introduction

Non-cooperative setting Supervised setting with myopic followers Supervised setting with non-myopic followers Conclusions

The model Analysis

Ideas of the paper (ctd.)

Groundwater extraction: marginal cost depends on the level of the aquifer In general, resources with accessibility problems: cost depends on scarcity The main ingredient: make the cost depend on the projected evolution of the resource: before or after the extraction or rainfall The goal: deduce its economical and environmental consequences The method: a Stackelberg Game linear-quadratic static game between agents, different kinds of optimization for the regulator.

Introduction Non-cooperative setting Supervised setting with myopic followers Supervised setting with non-myopic followers Conclusions

The model Analysis

The model of Provencher and Burt

We consider the extraction of groundwater by K players. Dynamics of groundwater:

G t+1 = G t + R - K k=1 u k t , G 0 , given.
We suppose R is a constant.

Instantaneous profit:

π i (u i t , G t ) = F i (u i t ) -C i (G t ) × u i t .
Marginal extraction cost (C i (.)): depends on the current level of the groundwater. The model Analysis

The extended model

Introduce the more general instantaneous profit function:

π i (u t ) = F i (u i t ) -C i (G t + mR -n j u j t ) u i t where n, m ∈ [0, 1].
The extreme cases: n = 0, m = 0 (the standard case): cost based on current resource n = 1, m = 1: cost based on the state of the resource in the following period.

When n = 0 the profit function of player i depends on the action of the other player: strategic interaction not just through the dynamics.

Introduction Non-cooperative setting Supervised setting with myopic followers Supervised setting with non-myopic followers Conclusions

The model Analysis

Angles of analysis

In a previous work, we developped the non-cooperative, Nash-feedback solution for agents.

Here, we develop the supervised setting myopic followers, static Stackelberg leader myopic followers, dynamic Stackelberg leader → an exercise in sensitivity analysis of LQ dynamic games, and non-LQ, non-concave optimal control problems. Mostly work in progress...

Contents

Introduction Non-cooperative setting Supervised setting with myopic followers Supervised setting with non-myopic followers Conclusions

The myopic case

The case of myopic agents

Assume agents play Nash with their instantaneous profit:

max u i F i (u i t ) -C i (G t + mR -n K k=1 u k t ) u i t .
For convenience, we continue with the particular linear-quadratic functional form:

F i (u) = a i u - b i 2 u 2 , C i (x) = z i -c i x > 0.
Introduction Non-cooperative setting Supervised setting with myopic followers Supervised setting with non-myopic followers Conclusions

The myopic case

Myopic agent reaction

In the symmetric case we find:

u(G ) = c b + (K + 1)cn α G + a -z + cmR b + (K + 1)cn γ .
The value function of each player is:

π(G 0 ) = (cG 0 + a -z + cmR) 2 (b + (K + 1)cn) 2 b + 2cn 2 .
Introduction Non-cooperative setting Supervised setting with myopic followers Supervised setting with non-myopic followers Conclusions

The myopic case

Myopic stock dynamics

The stock dynamics is:

G t+1 = G t + R -K (αG t + γ) = (1 -K α) t G 0 + (R -K γ) 1 -(1 -K α) t K α .
The asymptotic stock is:

G ∞ = R -K γ K α = Rb Kc + K + 1 K Rn -Rm - a -z c .
Introduction Non-cooperative setting Supervised setting with myopic followers Supervised setting with non-myopic followers Conclusions

Static optimization Stackelberg game

Supervised setting

A regulator is in charge of selecting the cost model, by choosing the cost parameters n and m.

The choice is announced to players, who play Nash. Followers are myopic:

u i t = c b + (K + 1)cn G t + a -z + cmR b + (K + 1)cn
The supervisor optimizes her own criterion, taking this reaction into account.

Optimal static choice

The supervisor gets to choose n and m once and for all.

Optimal pricing problem The supervisor's problem is:

max (n,m)∈[0,1] 2 ∞ t=0 β t L i π i (u t , G t )
with the myopic agent reactions and stock dynamics

G t+1 = G t + R - i u i t .
Introduction Non-cooperative setting Supervised setting with myopic followers Supervised setting with non-myopic followers Conclusions

Static optimization Stackelberg game

Optimal static choice (ctd.)

Thanks to the explicit solution for the dynamics:

V nm (G 0 ) = b + 2cn 2 α 2 (G 0 -G ∞ ) 2 1 -β(1 -K α) 2 + 2R K α(G 0 -G ∞ ) 1 -β(1 -K α) + R 2 K 2 (1 -β) with G ∞ = R -K γ K α . α = c (K + 1)cn + b γ = mRc + a -z (K + 1)cn + b .
Introduction Non-cooperative setting Supervised setting with myopic followers Supervised setting with non-myopic followers Conclusions

Static optimization Stackelberg game

Optimal static choice (ctd.)

→ optimization wrt (n, m) for each G 0 .

Results: m * = 1 is always optimal if K α < 1 (monotonous traj.) the optimal n is:

n * =      0 if β L ≤ β(G 0 ) 1 if β L ≥ β(G 0 ) n * (β L ) otw.
but n * (β L ) is the root of a 4 th degree polynomial.

Stackelberg with myopic followers

Followers being myopic, they apply the Nash controls. If symmetric:

u i (G ) = c b + (K + 1)cn G + a -z + cmR b + (K + 1)cn .
The benevolent regulator maximizes the total discounted profit on their behalf:

max {nt ,mt } ∞ t=0 β t L i F (u i (G t )) -C (G t + m t R -n t U(G t ))u i (G t )
with the dynamics:

G t+1 = G t + R -Ku i (G t ) .
=⇒ an optimal control problem.

First-order conditions

From the maximum principle:

0 = β t L cU(G t , n t , m t )(b + 2cn t ) + (b + (K + 1)cn)(q t -q t-1 ) -Kcq t 0 = β t L cU(G t , n t , m t ) 2 (b -(K + 1)(b + cn t )) +(b + (K + 1)cn t )(λ (n) t -µ (n) t ) +Kcq t (K + 1)U(G t , n t , m t ) 0 = β t L cRU(G t , n t , m t )(b + 2cn t ) + (b + (K + 1)cn t )(λ (m) t -µ (m) t ) -KcRq t .
where:

λ (n) t , µ (n) t
multipliers for n t ≥ 0 and n t ≤ 1, id for λ

(m) t , µ (m)
t . U(. . .) is the feedback function of followers.

Stationary situations

If a stationary state and control exists, then: optimal m: m * = 1, optimal n:

n * =              0 if β L ≤ b b + c 1 if β L ≥ K (b + c) + c K (b + 2c) + c K K + 1 β(b + c) -b (1 -β)c otw.
But we don't know if a stationary state exists. Stationary situations (ctd.)

Example with corner solution:

a = 1, b = 1, c = 1 10 , z = 9 10 , R = 1, β L = 95 100
gives a candidate optimal strationary solution:

G ∞ = 9 2 , n * = 1.
Satisfies all first-order conditions. Stationary situations (ctd.)

Example with interior solution:

a = 1, b = 1, c = 1 10 , z = 9 10 , R = 1, β L = 0.919
gives a candidate optimal strationary solution:

G ∞ 4.35, n * = 218 243 .
Satisfies all first-order conditions.

Non-stationary situations

However, convexity plays us tricks.

Example:

a = 1, b = 1, c = 6 10 , z = 9 10 , R = 1, β L = 68 100
gives a candidate optimal strationary solution:

G ∞ = 1 8 , n * = 11 36 .
But... the optimal constant policy is not there! And the Hamiltonian has actually a local minimum there wrt n. Hamiltonian is for constant trajectory from the expected steady state.

A heuristic policy

These periodic policies were identified by using the following heuristic:

m(G ) = 1 n(G ) = argmax{V n1 (G ) | 0 ≤ n ≤ 1}.
i.e. use the best static policy... but as state feedback. Stackelberg with non-myopic followers (ctd)

A reasonable formulation: the supervisor announces feedback laws G → n(G ), G → m(G ).

Followers play Nash Feedback with criterion:

max {u i t } ∞ 0 β t F [F i (u i t ) -C i (G t + m(G t )R -n(G t ) k u k t ) u i t ],
and dynamics

G t+1 = G t + R - k u k t , G 0 , given.
Again an optimal control problem... to be studied.

  =⇒ very complicated control law... =⇒ not time-consistent?

	Introduction Introduction
	Non-cooperative setting Non-cooperative setting
	Supervised setting with myopic followers Supervised setting with myopic followers
	Supervised setting with non-myopic followers Supervised setting with non-myopic followers
	Conclusions Conclusions
	Stackelberg with non-myopic followers

Followers being non-myopic, at time t they react to the sequence of "announced" regulations: {(n t , m t ), (n t+1 , m t+1 ), . . .} while playing Nash!

  Introduction Non-cooperative setting Supervised setting with myopic followers Supervised setting with non-myopic followers Conclusions Extensions under investigation simulations for the optimal control problem of the regulator → numerical methods, value iteration, policy iteration... non-myopic followers in the case of constant regulator policies stochastic case → learning algorithms under test → importance of m

Contents

Introduction

The model Analysis Non-cooperative setting The myopic case

Conclusions and extensions

Conclusions: regulator charges users in function of their behavior, not just in function of the level of resource introduce strategic interaction where there was none, in case of myopic agents (n = 0) difficult optimal control problem


Yinghua Guo

Jill Slay

DATA RECOVERY FUNCTION TESTING FOR DIGITAL FORENSIC TOOLS

Keywords: Digital forensic tools, validation, verification, data recovery

Many digital forensic tools used by investigators were not originally designed for forensic applications. Even in the case of tools created with the forensic process in mind, there is the issue of assuring their reliability and dependability. Given the nature of investigations and the fact that the data collected and analyzed by the tools must be presented as evidence, it is important that digital forensic tools be validated and verified before they are deployed. This paper engages a systematic description of the digital forensic discipline that is obtained by mapping its fundamental functions. The function mapping is used to construct a detailed function-oriented validation and verification framework for digital forensic tools. This paper focuses on the data recovery function. The data recovery requirements are specified and a reference set is presented to test forensic tools that implement the data recovery function.

Introduction

Digital forensics is the process of identifying, preserving, analyzing and presenting digital evidence in a manner that is acceptable in courtroom proceedings [START_REF] Mckemmish | What is forensic computing? Trends and Issues in Crime and Criminal Justice[END_REF]. As identified in [START_REF] Beckett | Digital forensics: Validation and verification in a dynamic work environment[END_REF][START_REF] Guo | Validation and verification of computer forensic software tools -Searching function[END_REF], one of challenges in the discipline is to ensure that the digital evidence acquired and analyzed by investigative tools is forensically sound.

In our previous work [START_REF] Guo | Validation and verification of computer forensic software tools -Searching function[END_REF], we proposed a function-oriented framework for digital forensic tool validation and verification. The framework identified fundamental functions involved in digital forensic investigations such as search, data recovery and forensic copying. A process called "function mapping" was used to further identify the details of each function (e.g., sub-categories and components). The results enable the speci-fication of the requirements of each function and help develop a reference set against which digital forensic tools may be tested.

Our previous work addressed the first task in creating a validation and verification framework, i.e., the "search" function. This paper attempts to address the second task -to complete the function mapping, requirements specification and reference set development of the "data recovery" function. The following sections review our function-oriented validation and verification framework, present the details of the data recovery function mapping, and describe a pilot reference set for testing the data recovery function.

Validation and Verification Framework

Our validation and verification framework [START_REF] Guo | Validation and verification of computer forensic software tools -Searching function[END_REF] is function-oriented and incorporates detailed specifications that are absent in other work. The methodology begins with a systematic description of the digital forensic field using a formal model and function mapping. Digital forensic components and processes are defined in this model and fundamental functions in the investigative process such as searching, data preservation and file identification are specified (i.e., mapped). Having developed the model and function mapping, the validation and verification of a digital forensic tool is accomplished by specifying its requirements for each mapped function. Next, a reference set is developed comprising a test case (or scenario) corresponding to each function requirement. The reference set enables the forensic tool and/or its functions to be validated and verified independently.

This paper engages the CFSAP model [START_REF] Mohay | Computer and Intrusion Forensics[END_REF] to describe the basic procedures involved in a digital forensic investigation: identification, preservation, analysis and presentation. In the context of validation and verification, identification and presentation are skill-based concepts. On the other hand, preservation and analysis are predominantly process-, function-and tool-driven concepts and are, therefore, subject to tool validation and verification.

Beckett and Slay [START_REF] Beckett | Digital forensics: Validation and verification in a dynamic work environment[END_REF] have dissected the processes of preservation and analysis into fundamental functions. Figure 1 presents a function categorization of validation and verification.

In this work, we attempt to complete the mapping of the functional categories of the digital forensics discipline at a level of abstraction that would serve the purposes of a specification for a software developer, technical trainer or educator; or for tool validation or verification. In particular, we detail the specification of function categories (e.g., searching, data preservation and file rendering) and their sub-categories. Our focus is on the data recovery function: mapping the function, specifying its requirements and developing the reference set to validate and verify tools that implement the data recovery function.

If the domain of digital forensic functions and the domain of expected results (i.e., requirements of each function) are known, in other words, the range and specification of the results are known, then the process of validating a tool can be as simple as providing a set of references with known results. When a tool is tested, a set of metrics can also be derived to determine the fundamental scientific measurements of accuracy and precision. In summary, if the discipline is mapped in terms of functions (and their specifications) and, for each function, the expected results are identified and mapped as a reference set, then any tool, regardless of its original design intention, can be validated against known elements. As claimed in [START_REF] Guo | Validation and verification of computer forensic software tools -Searching function[END_REF], our function-oriented validation and verification regime has several distinctive features such as detachability, extensibility, tool version neutrality and transparency.

Data Recovery Function Mapping

Data recovery is generally regarded as the process of salvaging data partially or completely from damaged, failed, corrupted or inaccessible storage media. Recovery may be required due to physical damage to the storage device or logical damage to the file system that prevents it from being mounted by the host operating system.

A variety of failures can cause physical damage to storage media. CD-ROMs can have their metallic substrate or dye layer scratched off; hard disks can suffer any of several mechanical failures; tapes can simply break. The logical damage to the data may take the form of corrupt or missing boot-related records (e.g., main boot record, disk partition table and directories) or the loss of file signatures (e.g., header and footer). Since our focus is on validating and verifying digital forensic tools in terms of the data recovery function, the consideration of physical damage recovery techniques is outside the scope of this paper and is considered to be complementary to logical damage recovery techniques. Consequently, in the rest of this paper, data recovery refers to logical damage recovery unless otherwise stated.

Data recovery in the context of digital forensics has its own peculiarities and differs from traditional data recovery in the computer science discipline. First, data recovery in the digital forensic context is a process by which digital evidence is recovered for use in court. Therefore, it should be conducted by certified investigators, conform to standard operating procedures, utilize tools that are validated and verified by the appropriate authorities, and be supervised and documented. Traditional data recovery does not have these requirements because its goal is to recover as much data as possible without concern for its forensic soundness. Second, the techniques used in traditional data recovery and in the digital forensic context differ because of the forensic soundness issue. For example, in traditional data recovery, a corrupted main boot record may be repaired by laying a FAT2 over a FAT1 if the FAT2 is intact. However, this is not an appropriate forensic data recovery technique because the original evidence (FAT1) is modified. Instead, it would be necessary to repair the corrupted main boot record in a duplicate (i.e., image). Finally, forensic data recovery embraces a broader view of recovering data than traditional data recovery and, consequently, must consider issues (e.g., hidden data and trace data) that are beyond the purview of traditional data recovery.

The data recovery function is mapped by detailing its components, processes and relevant factors. Since the goal of data recovery is to retrieve data due to storage media abnormalities and/or intentional human manipulation, the function mapping is performed from three angles: (i) storage media; (ii) recovery object; and (iii) recovery reason. Figure 2 presents the top-level ontology of the data recovery function.

Storage Media

Data is typically stored as files on storage media. The files are managed (i.e., created, modified and deleted) by file systems. In order to perform data recovery effectively and efficiently, forensic investigators need to understand the physical media as well as the logical structures of files on the media. Data recovery may be conducted locally (i.e., the storage media are seized and are under the custody of the investigator) or remotely (i.e., the investigator uses a network to access the storage media).

!"#"$%&'()&*+ %&'()&*+$%&",(- ./00&- 1-"''&,,/23& %&'()&*+$425&'# 6*"'&$!"#" 7&#"0"#" 8,&*$!"#" 9+,#&:$!"#" 9
From the physical (material) point of view, storage media can be categorized as: magnetic, optical or semiconductor. The magnetic storage media category includes hard drives, RAID arrays, floppy disks, zip disks and tape drives (Figure 3). Typical hard drive types include ATA, SATA, SCSI, IDS and USB. The file systems used include FAT (12, 16, 32), NTFS, HFS (HFS+) and EXT [START_REF] Guo | Validation and verification of computer forensic software tools -Searching function[END_REF][START_REF] Huebner | Data hiding in the NTFS file system[END_REF][START_REF] Hurlbut | Orphans in the NTFS world[END_REF].

Typical optical storage media are CDs and DVDs (Figure 4). CD storage media are in the form of CD-ROM, CD-R and CD-RW. Common file systems for CD media are ISO-9660, UDF, Joliet, HFS and HSG. DVD media include DVD-ROM, DVD-R(+R) and DVD-RW(+RW). The principal file systems for DVD media are UDF and HFS.

The principal semiconductor-based storage media are RAM and ROM (Figure 5). Flash memory, a type of EPROM (erasable programmable read-only memory), is widely used in computers and electronic devices and includes compact flash (CF) cards, smart media (SM) cards, secure digital (SD) cards, memory sticks and USB flash drives. File systems commonly used in flash memory include FFS, JFFS, LogFS and YAFS.

Reasons for Data Recovery

A data recovery method is used when data is unavailable. In the context of digital forensics, data is unavailable and must be salvaged for various reasons, including damage, corruption or hiding. From the point of view of the user (e.g., investigator), we assume that the data is unavailable because it is inaccessible or hidden. By inaccessible data, we mean that the user is aware of the existence of the data, but is unable to access it in a normal manner. On the other hand, hidden data is invisible to the user and the user does not know of its existence.

!"#$%&'()!%*'" +",%)-.'/% 012)-'34 567,,8)-'34 9:',%);".* 19<=>?> 19< !"# 19< !"" 19< !"? $%1- $%1-"? $%1-& $%1-" $%1-? '(&%.$"6))".*)-'34 *%&:7.4)9&7."#%)-%/'(% +,&-))".*)-.'/% #,&-))".*)-.'/% )".*)-.'/% +8,% .9/ 1-' 9;91 9%+% %+% 5'6%)983&%0 '1+)2+3)#3)=4 )59)2)5954 *+59 5%+)2"+3)"63)#+4
Inaccessible Data "Orphaned" files are inaccessible to users under normal operations. An orphaned file is one that no longer has a parent (the parent is the folder in which it was originally located) [START_REF] Hurlbut | Orphans in the NTFS world[END_REF]. The term orphaned is a broad concept that includes deleted files. In most cases, orphaned files are deleted files, but a file can be orphaned when the association with its parent is lost through other means (e.g., by removing a symbolic link in a Unix environment).

Ambient space (unallocated space) or space that is orphaned from the operating system or file system has many forms. Data in such space cannot be accessed by users under normal operations. For example, file slack space is ambient or unallocated space that exists at the end of a file in certain operating systems and can contain a variety of data, including data dumped from RAM (RAM slack) or the remnants of previouslyallocated files that may have been orphaned and partially overwritten. Data may also be inaccessible because its metadata is corrupted or missing. The associated metadata includes MBR, DPT, OBR (operating system boot record), BPB (BIOS parameter block), FAT and DIR (directory). In such scenarios, the file may not be located, but its data is intact and, therefore, can be recovered by "file carving" [START_REF] Pal | The evolution of file carving[END_REF].

Alternatively, a file can be located using metadata, but the data itself cannot be accessed because it is defective. This can occur for two reasons. One possibility is that the data feature (e.g., header or footer) is damaged. A file header is a "signature" placed at the beginning of a file to enable the operating system or application to know what to do with the following contents. The file cannot be recognized when this feature is damaged. The second possibility is that the data content is corrupted. In this case, it is necessary to analyze the structural characteristics and code of the damaged file to recover the data or portions of the data.

Finally, data may be inaccessible due to encryption and steganography. Although an encrypted file is visible to users, its contents are inaccessible without the key. Figure 6 summarizes the inaccessible data category. Hidden Data In the digital forensic context, it may be necessary to recover data that has intentionally been hidden. Data hiding methods may be categorized as hardware-based or software-based (Figure 7). Hardware-based methods hide data in specific areas of storage media. For example, data on a hard disk may be stored in the HPA (host protected area), DCO (device configuration overlay), UPA (unused partition area) and inter-partition space.

Software-based methods hide data using file system and/or operating system utilities [START_REF] Huebner | Data hiding in the NTFS file system[END_REF]. For example, modern hard disk controllers handle bad sectors without the involvement of the operating system by slipping (modifying the LBN (logical block number) to physical mapping to skip the defective sector) or remapping (reallocating the LBN from a defective area to a spare sector). For older hard disks that do not have this capability, the operating system and file system have to retain the ability to detect and mark defective sectors and clusters as damaged. This feature can be used to exclude undamaged clusters from normal file system activities and use them to hide data.

Software-based data hiding methods may also use ambient space. Slack space, which includes file slack space, volume slack space and partition slack space, are areas on the disk that cannot be used by the file system because of the discrete nature of space allocation. Data can be hidden in any of these locations.

Recovered Objects

File system data to be recovered belongs to one of four categories: system data, user data, metadata and trace data.

System Data System data includes general hardware and software information. Data recovery techniques include hardware rendering and software (operating system and file system) rendering (Figure 8).

!"#$%&'()$) *+,%'!"#$%&'-%./%0+.1 222222 34,5&%'6)7%,'8/%.$+9:)$+4.

;)0$+$+4.'8/%.$+9:)$+4. <=%0)$+.1'!"#$%&'-%./%0+.1 222222 -%1+#$0"'>?+./4 #! !"#$%&"##%0'$4.9150)$+4.'8/%.$+9:)$+4. %)0/ )0%'8/%.$+9:)$+4. Hardware rendering refers to the ability to accurately identify particular types of devices and media. This is accomplished through physical interaction with the device or media or by using metadata located on the device or media.

The goal of operating system or file system rendering is to reveal the underlying structure. Operating systems and file systems have a general structure, but each instance is unique. In addition, many of these systems are proprietary in nature and, as a result, are poorly documented (e.g., the detailed structure of NTFS has not been publicly released). Operating system and file system rendering may specify where certain structures are found and the data unit size that enables file folders, data and metadata to be accurately retrieved. For example, the volume label and the associated data are indicators of the method used to create the allocated components of a device. Different file systems record this information differently, so a digital forensic tool must be able to render the volume label(s) from a device or partition.

User Data User data is the principal object of data recovery. User data are categorized as document, graphic, sound or Internet files. Figure 9 presents the classification and provides typical instances of each class. This classification is by no means exhaustive and will have to be updated constantly to accommodate new applications and file formats. Note that user data files may be in special forms (e.g., compressed and encrypted), which should be taken into account by forensic examiners.

Metadata Metadata is data that describes data or files. It includes data about where the file content is stored, file size, dates and times of the last read and write, and access control information. Figure 10 presents examples of metadata in various storage and file systems. Metadata must be analyzed to determine details about a specific file or to search for a file that meets certain requirements. Trace Data As mentioned above, data recovery in the digital forensic context is a much broader concept than traditional data recovery. Trace data is the data that remains on the storage media after operations such as hard drive partitioning, formatting and file deletion (Figure 11). Trace data may not be substantial, but may constitute important digital evidence. For example, file operations (e.g., creation, modification and deletion) leave traces in the form of temporary files. Most temporary files are deleted by the operating system after the file operations are completed. However, if a temporary file is deleted, it contents can be recovered if the clusters allocated to the file are not reallocated. Also, even if the allocated clusters are reallocated, file metadata (e.g., name and timestamp) may exist and may prove to be useful in a digital forensic investigation.

!"#$%&'#(# !"#$%&'#(#&)*&+,-% .)/,0$#(,)1 2//,(,)1 '%-%(,)1 !"#$%&'#(#&)*&+)"3#( !"#$%&'#(#&)*&4#"(,(,)1

Requirements Specification

Requirements specification is the second step of the validation and verification framework. The data recovery function requirements are specified in the same way as the search function requirements in [START_REF] Guo | Validation and verification of computer forensic software tools -Searching function[END_REF].

The requirements are specified in an extensible and customized manner. As seen in function mapping, several issues have to be considered when specifying the requirements. For example, the storage media could be a hard disk, CD/DVD, flash memory, etc. The file system that manages data files on the storage media could be FAT12, FAT16, FAT32, EXT2, EXT3, NTFS, HFS(+), FFS, etc. The data could be inaccessible for any number of reasons; it could be orphaned, corrupted, encrypted, etc. Each of these sub-categories again has many variations.

The method of specifying requirements is highly abstract and generalized. We use italicized "variables" to reflect these variations. Thus, when a requirement has to be changed, it is only necessary to adjust (add, delete or modify) the variables. Moreover, the requirements can be unwrapped when it is necessary to develop a specific test scenario in a reference set. For example, the requirement: "The tool shall be able to accurately recover inaccessible recovery objects" may be unwrapped and instantiated as "The tool shall be able to accurately recover deleted JPG files" or "The tool shall be able to accurately recover hidden data in file slack."

A digital forensic tool has the following eight requirements with respect to the data recovery function:

The tool shall operate in at least one operational environment.

The tool shall operate under at least one operating system.

The tool shall operate on at least one type of storage media.

The tool shall be able to accurately render system data.

The tool shall be able to accurately recover inaccessible (recovery) objects.

The tool shall be able to accurately recover hidden (recovery) objects.

If there are unresolved errors when reconstructing data, then the tool shall report the error types and error locations.

The tool shall report the attributes of the recovered data.

Reference Set Development and Testing

A reference set consists of test scenarios (cases) against which a digital forensic tool or its individual function is validated. The development of test scenarios is based on the specification of function requirements. Using the requirements specification, it is possible to establish a reference set for testing the data recovery function of various digital forensic tools. Since the function requirements are specified in an extensible manner, the corresponding reference set is also extensible. This would enable practitioners, tool developers and researchers to identify critical needs and to target deterministic reference sets.

We have identified eight requirements for the data recovery function. Since each requirement has several variables, multiple test scenarios have to be designed for each requirement. Each scenario represents a single instantiation of each variable. The following are some pilot samples of the reference set for the data recovery function:

A deleted JPG file in a FAT32 file system on an IDE hard disk.

A deleted JPG file in an NTFS file system on a SCSI hard disk.

A deleted WAV file in a UDF file system on a CD.

A deleted Microsoft Word file in an FFS file system on flash memory.

A deleted compressed HTML file in an NTFS file system on an IDE hard disk.

An encrypted MP3 file in a FAT32 file system on an ATA hard disk.

Thus far, we have completed the function mapping, requirements specification and reference set development. We now know what needs to be tested and what the expectations are. Validating a digital forensic tool that professes to have a search function is now as simple as testing the tool against the reference set and applying metrics (accuracy and precision) to determine the quality of the results.

Conclusions

Mapping the fundamental functions of the digital forensic discipline is a powerful approach for creating a function-oriented validation and verification paradigm for digital forensic tools. The utility of the approach is demonstrated in the context of the data recovery function via the specification of data recovery requirements and a reference set for testing tools that implement the data recovery function. Validating a digital forensic tool is reduced to testing the tool against the reference set. Compared with traditional testing methods, this testing paradigm is extensible, and neutral and transparent to specific tools and tool versions.

More work remains to be done to complete the validation paradigm. Although the methodology holds promise, it needs to be tested extensively to evaluate its utility and identify potential weaknesses and shortcomings. Tests would have to be implemented against popular tools such as EnCase and FTK. A quantitative model is also required to evaluate the results of validation and verification. Metrics are needed to measure the accuracy and precision of testing results, and it is necessary to specify rules for judging the validity of digital forensic tools. Is a tool validated only when it passes all the test cases? Or is a tool validated when it passes the test cases for certain scenarios?

It is important to recognize that numerous variables are involved in function requirements specification and that the corresponding reference set can be very large. Indeed, the number of possible combinations for validating a single function in a digital forensic tool may well be in the thousands (even discounting the different versions of the tool). Interestingly, this problem is also faced by the Computer Forensics Tool Testing (CFTT) Program [7] created by the National Institute of Standards and Technology (NIST) to validate and verify digital forensic tools. This problem will be examined in our future work.

!Figure 1 .

 1 Figure 1. Validation and verification top-level mapping.

Figure 2 .

 2 Figure 2. Top-level data recovery function mapping.

Figure 3 .

 3 Figure 3. Magnetic storage media category.

!Figure 4 .Figure 5 .

 45 Figure 4. Optical storage media category.

Figure 6 .

 6 Figure 6. Inaccessible data category.

Figure 7 .

 7 Figure 7. Hidden data category.

Figure 8 .

 8 Figure 8. System data.

Figure 9 .

 9 Figure 9. User data.

Figure 11 .

 11 Figure 11. Trace data.


Clément Bertin

Sylvain Cros

Laurent Saint-Antonin

Nicolas Schmutz

Prediction of optical communication link availability: real-time observation of cloud patterns using a ground-based thermal infrared camera

Keywords: optical link, optical communication, long wave infrared, cloud pattern prediction, microbolometer, cloud microphysical properties, optical ground station

The growing demand for high-speed broadband communications with low orbital or geostationary satellites is a major challenge. Using an optical link at 1.55 μm is an advantageous solution which potentially can increase the satellite throughput by a factor 10. Nevertheless, cloud cover is an obstacle for this optical frequency. Such communication requires an innovative management system to optimize the optical link availability between a satellite and several Optical Ground Stations (OGS).

The Saint-Exupery Technological Research Institute (France) leads the project ALBS (French acronym for BroadBand Satellite Access). This initiative involving small and medium enterprises, industrial groups and research institutions specialized in aeronautics and space industries, is currently developing various solutions to increase the telecommunication satellite bandwidth. This paper presents the development of a preliminary prediction system preventing the cloud blockage of an optical link between a satellite and a given OGS. An infrared thermal camera continuously observes (night and day) the sky vault. Cloud patterns are observed and classified several times a minute. The impact of the detected clouds on the optical beam (obstruction or not) is determined by the retrieval of the cloud optical depth at the wavelength of communication. This retrieval is based on realistic cloud-modelling on libRadtran. Then, using subsequent images, cloud speed and trajectory are estimated. Cloud blockage over an OGS can then be forecast up to 30 minutes ahead. With this information, the preparation of the new link between the satellite and another OGS under a clear sky can be prepared before the link breaks due to cloud blockage.

INTRODUCTION

The demand for high-data-rate communication is generating interest in Earth-space optical links, as an alternative or an extension to conventional radio-frequency (RF) links. Indeed, the higher frequency of optical signal compared to RF permits to tremendously increase the transmitted bit rate responding to future communication needs. Moreover, optical link offers a safer way of communication because the transmitted information can be intercepted only by a receiver located in the line of sight [START_REF] Juarez | Free-space optical communications for next-generation military networks[END_REF].

Concretely, the optical link is a communication transmitted by a laser with a wavelength of 1.55 µm. This wavelength has been chosen rather than other common optical telecommunications (1.06 and 0.8 µm) for several reasons. It is the same than the one used by current terrestrial fiber-optic networks, permitting a convenient interface between free space and fiber networks. It enables an ultra-dense wavelength multiplexing providing an optimized data transmission rate. Moreover, this frequency is less sensitive to the rapid fluctuations of air refractive index occurring in turbulent atmospheres. Finally, this laser wavelength is recommended to protect the eyes of astronauts and aircraft pilots (Norm EN 60825-1 0 of the European Comity of Normalization (CEN)).

Even if a 1.55 µm laser benefits from a high atmospheric transmission (about 90 %) compared to the other common wavelengths, most of the clouds break the communication link with an attenuation superior to 10 dB [START_REF] Moll | Wavelength selection criteria and link availability due to cloud coverage statistics and attenuation affecting satellite, aerial, and downlink scenarios[END_REF]. To supply the continuity of the communication service, it is necessary to implement site diversity thanks to an optical ground station (OGS) network. The OGS network is optimized in order to maximize the link availability with a minimum number of stations.

Low attenuation of high semitransparent clouds (cirrus) could be incorporated into the optical link budget at the price of larger or more powerful optical terminals [START_REF] Poulenard | High altitude clouds impacts on the design of optical feeder link and optical ground station network for future broadband satellite services[END_REF].

Satellite imagery can provide worldwide cloud coverage data but with a trade-off between spatial and temporal resolutions. Satellites in geosynchronous orbits provide continuous data, but at low spatial resolutions. Satellites in Low Earth Orbits (LEO) provide higher spatial resolutions, but only once or twice a day. Moreover, for all these methods it is difficult to detect the effects of thin clouds in the aiming line of the telescope. Then, a ground-based cloud monitoring system must be set up at the OGS site. This paper presents our prediction system which prevents cloud blockage of the optical link. An uncooled microbolometer thermal infrared (8-13 µm band) camera continuously observes (night and day) the entire sky vault above each OGS. Processing these observations permits to deliver a cloud attenuation map every minute. Then, image processing techniques enable to forecast when the optical link will next be obstructed in order to manage a handover toward an available OGS.

The next section presents the principles of atmospheric radiative transfer and the observation of cloud properties in the thermal infrared spectrum. Section 3 shows the cloud attenuation map retrieval from the camera data. The prediction process is explained in section 4. The conclusion and perspectives are presented in the last section.

CLOUD OBSERVATION IN THERMAL INFRARED The LWIR atmospheric window

The long wave infrared (LWIR) thermal atmospheric window from 8 to 13 μm is well suited for cloud observation. Figure 1 shows the downwelling radiance emitted by three different sky states above a punctual ground location. Spectral radiances have been simulated by the radiative transfer model libRadtran [START_REF] Mayer | Technical note: The libRadtran software package for radiative transfer calculations and examples of use[END_REF]. The red curve clearly indicates the presence of an atmospheric window between 8 and 13 µm. Thick cloud emission (blue curve) is significantly high to present a strong contrast with a clear sky radiometric signature. However, this contrast is smaller for the detection of thin clouds (green curve) such as cirrus. Atmospheric emission in this window is however very sensitive to water vapor presence. Thus, the determination of cloud-free atmospheric emission must be very accurate to consistently detect thin clouds with varying water vapor contents.

A thermal infrared imager has the advantage of directly detecting cloud emission rather than relying on reflected and scattered sunlight in the case of visible or near-infrared observation systems. Thus cloud detection performance does not depend on the illumination of the cloud cover by the sun. Thus, the time of the day has absolutely no influence on the thermal infrared imager's performance, enabling continuous night and day observation.

However, observations at a low angular elevation (typically less than 20° above the horizon) encounter the issue of an increasing atmospheric thickness in the line of sight. This case leads to two distinct effects. Firstly, emission of atmospheric components (mainly water vapor and aerosols) increase with atmosphere thickness (quantified by the air mass). Secondly, a thick atmosphere is less transparent to a cloud signal. Consequently, the observed radiance ratio between clouds and a clear atmosphere decreases drastically. The detection of thin clouds and the retrieval of their physical property becomes problematic.

Instrumental observation

Several sky vault observation systems have been set-up to monitor the cloud cover in the LWIR band. A Radiometric All-Sky Infrared CaMera (RASICAM) was developed by the SLAC National Accelerator Laboratory to astronomically monitor night-time observations at the Cerro Tololo Inter-American Observatory [START_REF] Lewis | A radiometric all-sky infrared camera (RASICAM) for DES/CTIO[END_REF]. The camera provides a real time sky quality map which guarantees sufficient sky clearness to validate the photometric acquisition. The Infrared Cloud Imager (ICI) is a camera developed by the University of Montana. Dedicated to climate studies, ICI is primarily used for day and night cloud-cover monitoring to assess cloud contribution in the atmospheric radiative budget, especially in high latitudes, where satellites have difficulties distinguishing between clouds and the underlying surface [START_REF] Thurairajah | Cloud statistics measured with the infrared cloud imager (ICI)[END_REF]. ICI is also used by NASA to assess different sites' space-to-earth communication feasibility [START_REF] Nugent | Infrared cloud imaging in support of Earth-space optical communication[END_REF]. The All-Sky Infrared Visible Analyzer (ASIVA) is a Solrimus Corporation product that provides multiple products on clouds, as sky quality map, for observatories and weather offices [START_REF] Klebe | Ground-based all-sky mid-infrared and visible imagery for purposes of characterizing cloud properties[END_REF].

The prediction system currently developed at IRT Saint-Exupéry and presented in this paper is based on the instrument SIONS-T (French acronym for ground-based thermal infrared imager for cloud observation) developed by the company Reuniwatt (figure 2).

Figure 2. SIONS-T instrument

The instrument is composed of a LWIR camera core with a 640 by 480 spatial resolution. A hemispherical mirror provides a 180° field of view. The chromed coating of mirror surface ensures an optimal reflection of LWIR radiation. The resolution of the field of view is about 0.35° per pixel. Humidity and temperature sensors, installed in a radiation shield located near the camera, provide in-situ meteorological information improving the estimation of clear atmosphere radiance. An embedded computer is used to acquire and upload the data on a server for measurement processing.

CLOUD PROPERTY RETRIEVAL METHOD Atmospheric radiative transfer modeling inversion

The principle of the present cloud property retrieval method consists in inverting a radiative transfer model which simulates the downwelling LWIR (8 to 13 µm) radiance of the sky as observed by the instrument. We chose the radiative transfer model libRadtran developed by the German Aerospace Center under the GNU license [START_REF] Mayer | Technical note: The libRadtran software package for radiative transfer calculations and examples of use[END_REF]. This model permits to simulate the downward or upward radiations emitted by atmosphere layers in function of their assumed physical state and chemical composition (temperature and humidity profiles, aerosol and greenhouse gas concentration…). It has been widely used for various remote sensing applications and includes full solar and thermal spectrums.

The forward modeling of the radiance considers three different sky states: a clear (cloud-free) atmosphere, an atmosphere containing a thick cloud and an atmosphere containing a thin cloud. Simulating a clear atmosphere permits to subtract a cloud-free atmosphere radiance from the observed radiance in order to assess the radiance emitted by clouds only. We assume thick cloud emission depends only on cloud base temperature (directly related to its altitude). This assumption cannot be valid for thin cloud radiance which also depends on its optical depth (OD).

Clear atmosphere LWIR modeling

Simulating clear sky radiance (Rcs) requires the availability of temperature (T) and relative humidity (RH) vertical profiles. However, obtaining these meteorological products anywhere in real-time is impossible in most cases. Atmospheric radiosoundings are available only for a few locations. Weather offices can provide modelled profiles but real-time or near-real-time delivery is expensive. Ground instrumentation such as LIDAR is also very costly. We proposed an empirical method permitting to estimate Rcs from ground temperature and relative humidity measured by our instrument.

The University of Wyoming offers a worldwide atmospheric radio sounding historical database [9]. Density of radiosounding stations is relatively scarce. If profiles are not available near the instrument's location, the reanalysis data from ECMWF (ERA-INTERIM) [START_REF] Dee | The ERA-Interim reanalysis: Configuration and performance of the data assimilation system[END_REF] can be used. We collect at least one year of vertical profiles, representing 1 to 4 profiles per day. For each couple of (T, RH) profile, we simulate the associated Rcs with libRadtran. We determine, for a given site, the relationship between Rcs and the dew point temperature (Td), generally delivered with the atmospheric profiles, with a second order polynomial regression. Equation 1and figure 4 show the fitted relationship using the radiosounding data of Nîmes (France) during the years 2012 and 2013. We use this relationship to assess Rcs from our T and RH ground measurements. We compute Td using the formula of Magnus-Tetens [START_REF] Barenbrug | Psychrometry and Psychrometric Charts[END_REF].

Thick cloud altitude retrieval

As shown on figure 1, the presence of thick clouds is detected when the radiance is much larger than Rcs appears on the instrument image. The radiance threshold to distinct a thick cloud must be preliminarily determined according to the climatic area (tropical, temperate, artic…).

We consider that Rcs is the downward radiance emitted by the entire cloud-free atmospheric column. RTkC is the downward radiance emitted by the base of a thick cloud. A cloud is considered here as "thick" if atmospheric radiance above it cannot be detected from the ground (OD > 3). The downward radiance viewed from ground level (Rg), in the presence of a single thick cloud layer in the atmosphere, is modelled by a combination of RTkC and the contribution of the clear sky layer between the cloud base and the ground. For several discrete values of Rcs, a thick cloud is modelled at different realistic altitudes. Then, for a given Rcs, a correspondence is set up between Rg and cloud base altitude.

Thin cloud property retrieval

The case of thin clouds raises an issue. Low and thin cirrus clouds can show the same radiance as thicker and higher cirrus. In order to maximize the precaution to avoid cloud blockage during optical communications, the cloud property retrieval considers that any thin cloud detected is considered as a thicker and higher cirrus for the observed radiance.

We simulate cirrus cloud radiances according to physical properties observed from a 12-year observation made by a Rayleigh-Mie-Raman ground-based lidar and CALIOP space borne lidar at the Observatory of Haute-Provence (South of France) [START_REF] Hoareau | A decadal cirrus clouds climatology from ground-based and spaceborne lidars above the south of France (43.9° N-5.7° E)[END_REF]. In this climatological study, cirrus are categorized into three classes. Figure 5 shows the relationship between cloud optical depth at 1.55 µm for each classes and the simulated radiometric contrast (Rg -Rcs) observable by our instrument. OD at 1.55 µm has been computed by converting cloud OD in the visible range given by [START_REF] Hoareau | A decadal cirrus clouds climatology from ground-based and spaceborne lidars above the south of France (43.9° N-5.7° E)[END_REF], extrapolated at 1.55 µm using a microphysical model from the University of Madison-Wisconsin [START_REF] Baum | Bulk scattering models for the remote sensing of ice clouds. Part 2: Narrowband models[END_REF][14] and assuming that effective cloud radius is equal to 57 µm. Even if class 1 (thin middle troposphere) and class 3 (high upper troposphere) cannot be properly differentiated, we can deduce a linear relationship (red line) which provides the maximal cloud optical depth for a given (Rcs -Rg) value.

CLOUD MOTION PREDICTION

The cloud property retrieval scheme described in section 3 leads to the real-time delivery of an optical link attenuation map. For each exploitable pixel of the SIONS-T's field of view, the pixel is flagged as clear sky, thick cloud or thin cloud. For the last flag, we associate the retrieved cloud optical depth at 1.55 µm.

To predict a cloud blockage of the communication in the next half hour, we assume that the cloud pattern will be translated without any modification of optical cloud properties. Some intra-hour solar power forecasting methods use allsky cameras in visible spectrum to predict cloud obstruction of the solar disk and then forecast an abrupt decrease of photovoltaic production [START_REF] West | Short-term irradiance forecasting using skycams: Motivation and development[END_REF][16] [START_REF] Nitche | Using cloud fraction derived from all-sky camera to improve beam solar irradiance forecasting by time-series modelling[END_REF]. Reusing such algorithms for optical communication blockage prediction consists in considering the satellite's position instead of the sun's. We briefly present the chosen algorithm steps.

The first step consists in assessing the cloud motion field. Using two subsequent cloud maps, an optical flow analysis method provides the vector field describing the cloud motion between the two considered instants. The method of Lucas-Kanade [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF], widely used in computer vision, is a convenient algorithm for this application. The second step is the temporal filtering of the cloud motion vector to minimize abrupt changes of cloud speed between subsequent vector fields. This process permits to suppress unrealistic cloud motions [START_REF] Marquez | Intra-hour DNI forecasting based on cloud tracking image analysis[END_REF]. The final step consists in translating the cloud attenuation map according to the directions and speeds imposed by the cloud motion vector field. Consequently, the predicted attenuation maps are obtained for a series of selected time horizons. In parallel, if the satellite is not geosynchronous, its position is calculated for each time horizon. We can then derive the period duration from present to optical link blockage.

CONCLUSION

We presented the first elements of a cloud obstruction prediction system composed of an original all-sky observation instrument and algorithms retrieving and forecasting cloud attenuation characteristics in the next half hour. The objective of this system consists in preventing optical link cloud blockage interruption by providing operational forecasts of critical cloud cover passing through the laser line of sight. Compared to the state-of-the art, it has the advantage to providing a larger field of view of the sky vault and proposes empirical cloud property retrieval methods which are simple to implement in operational conditions.

The validation and refinement of our algorithms can be undertaken by installing a ground based lidar next to our system. Then, uncertainty of cloud altitude and cloud optical depth can be objectively assessed. An operational limit of our system concerns the lowest angular elevations. In the case of a communication with low orbit satellites, the maximization of communication time leads to the necessity of applying our algorithms at a low elevation above the horizon. The atmosphere's higher thickness for these longer lines of sight attenuates the contrast between clear and cloudy scenes in the LWIR vision. Experimental optical communication campaigns must be undertaken to properly assess the possibility of preventing cloud blockage at a low elevation according to the quality of the optical link budget in such situations.

Simultaneous observations using geostationary meteorological satellites such as Meteosat will permit to extend the forecast time horizon by monitoring cloud cover at a higher spatial scale.

Figure 1 .

 1 Figure 1. Spectral emission of clear sky, thin cloud and thick cloud in the LWIR band.

Figure 3 .

 3 Figure 3. Infrared and visible images of the sky.

Figure 3

 3 Figure3shows a raw image of our instrument (left) obtained during an optical communication test. A sky imager has been installed next to the SIONS-T, simultaneously acquiring the same scene in the visible spectrum (right). The LWIR image clearly shows a better contrast between clear sky and clouds. The visible camera presents a strong sun flare where the sun disk has almost no impact in the infrared image. Illumination effects (light and shadows) on the cloud surface due to the reflection of the sun's radiance confirm that the image from the visible sky imager is influenced by the sun's position in the sky, which is not the case of the LWIR sensor.

Figure 4 .

 4 Figure 4.Clear sky radiance as function of dew point temperature

Figure 5 .

 5 Figure 5. Relationship between cirrus optical depth and simulated radiometric contrast.


VIRTUAL EXPANSION OF RAINBOW TABLES Vrizlynn Thing

Keywords: Password recovery, cryptanalysis, rainbow table, time-memory trade-off

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Password protection of potential digital evidence by suspects makes investigative work more complex and time consuming. Traditional password recovery techniques include password guessing, dictionary attacks and brute force attacks.

A password guessing technique attempts easily-formed and common passwords such as "qwerty" and "password." These passwords could be based on a user's personal information or a fuzzy index of words on the user's storage media. A statistical analysis of 28,000 passwords revealed that 16% of the users relied on their first names as passwords and 14% relied on "easy-to-remember" keyboard combinations [START_REF]Favorite passwords: "1234" and "password[END_REF]. Therefore, the password guessing method can be effective in cases where users are willing to compromise security for convenience.

A password dictionary attack attempts to match the hash values of dictionary words with the stored password hash value. Well-known tools that employ this technique include Cain and Abel [START_REF] Montoro | Cain and Abel[END_REF], John the Ripper [START_REF]John the Ripper password cracker[END_REF] and LCP [6].

In a brute force cryptanalytic attack, the hash value of each unique combination of password characters is compared with the password hash value until a match is found. Although such an attack is extremely time consuming, the password is recovered eventually. Cain and Abel, John the Ripper and LCP also support brute force attacks.

Traditional password recovery techniques are losing their effectiveness as suspects use stronger passwords to protect their data. Hellman [START_REF] Hellman | A cryptanalytic time-memory trade-off[END_REF] introduced a method that trades off the computational time and storage space needed to make a hash-to-plaintext recovery. This method can retrieve Windows login passwords as well as passwords used in other applications (e.g., Adobe Acrobat) that employ the LM and NTLM hash algorithms [START_REF] Todorov | Mechanics of User Identification and Authentication: Fundamentals of Identity Management[END_REF]. Also, the method supports encryption key recovery for Microsoft Word and Excel documents. Passwords encrypted with hashing algorithms such as MD5 [START_REF] Rivest | The MD5 Message-Digest Algorithm[END_REF], SHA-2 [START_REF]Secure Hash Standard[END_REF] and Ripemd-160 [START_REF] Dobbertin | Ripemd-160: A strengthened version of RIPEMD[END_REF] can also be recovered using this method. In general, Hellman's method is applicable to searching for solutions to knapsack and discrete logarithm problems.

Oechslin [START_REF] Oechslin | Making a faster cryptanalytic time-memory trade-off[END_REF] proposed a cryptanalytic time-memory trade-off method that is based on Hellman's password recovery method. This "rainbow table" method generates password recovery tables with higher efficiency because it employs multiple reduction functions to reduce the probability of collisions in a single table.

Thing and Ying [START_REF] Thing | A novel time-memory trade-off method for password recovery[END_REF] enhanced the rainbow table method via initial chain generation. In this technique, a plaintext value is chosen and its hash value is computed by applying the password hash algorithm. Based on this hash value, other hashes are computed; these form the branches of the initial plaintext value. Multiple blocks are created from the different initial plaintext values. The final values of the chains in the blocks are stored with the single initial plaintext value in each block.

The rainbow table method is widely used for password recovery. Products that use pre-computed rainbow tables include RainbowCrack [START_REF] Zhu | RainbowCrack: The time-memory trade-off hash cracker[END_REF] and Ophcrack [10]. RainbowCrack is an implementation of Oechslin's method that supports hash algorithms such as LM, NTLM, MD5 and SHA-1 [START_REF]Secure Hash Standard[END_REF]. Ophcrack also implements the rainbow table method, but it only supports the LM and NTLM hash algorithms. Rainbow tables are also used in several popular commercial tools such as AccessData's Password Recovery Toolkit [START_REF]AccessData, Decryption tools[END_REF] to perform efficient and effective password recovery.

This paper proposes the virtual expansion of rainbow tables (VERT) method, a new time-memory trade-off technique that relies on a pre-computed table structure. Comparisons with the original rainbow table method [START_REF] Oechslin | Making a faster cryptanalytic time-memory trade-off[END_REF] and the enhanced rainbow table method [START_REF] Thing | A novel time-memory trade-off method for password recovery[END_REF] demonstrate higher password recovery success rates of 16.92% to 28.15% without corresponding increases in computational complexity and storage space.

Related Work

In 1980, Hellman [START_REF] Hellman | A cryptanalytic time-memory trade-off[END_REF] conceived of a general time-memory trade-off hash-to-plaintext recovery method. We begin by describing Hellman's algorithm in the context of password recovery.

Let X be the plaintext password and Y be its corresponding stored hash value. Given Y , it is necessary to find X that satisfies the equation h(X) = Y where h is the known hash function. However, finding X = h -1 (Y ) is not feasible because the hash values are computed using oneway functions for which the reversal function h -1 is unknown.

To solve this problem, Hellman suggested applying alternate hashing and reduction operations to plaintext values in order to generate a precomputed table. For example, given a 7-character password (using the English alphabet), the MD-5 hash algorithm is used to compute the corresponding 128-bit hash value. Using a reduction function such as H mod 26 7 , where H is the hash value converted to decimal digits, the resulting values are distributed in a best-effort uniform manner.

For an initial plaintext password of abcdefg, the binary hash output could be: 00000000,00000000,00000000,00000000,00000000,00000000, 00000000,00000000,10000000,00000000,00000000,00000000, 00000000,00000000,00000000,00000001.

Therefore, H = 9223372036854775809. The reduction function converts this value to 3665127553, which corresponds to the plaintext representation of lwmkgij. This is computed as: 11(26 6 ) + 22(26 5 ) + 12(26 4 ) + 10(25 3 ) + 6(26 2 ) + 8(26 1 ) + 9(26 0 ).

In table generation, the hashing and reduction operations are repeatedly performed on different initial plaintext values to produce different rows or chains. The pre-defined multiple rounds of hashing and reduction operations in each chain increase the length of the chains and the table contents; this contributes to higher computational overhead during password recovery. The reason is that the initial and final plaintext values (i.e., "heads" and "tails") of the chains are the only elements stored in the table. The recovery of passwords "residing" in the intermediate columns requires computations to regenerate the plaintext-hash pairs. The password recovery success rate depends on the size of the precomputed table. A larger pre-computed table contains more plaintexthash pairs, which increases the password recovery success rate. However, the generation of the intermediate chain columns may result in collisions of elements in the table. Collisions cause the chains to merge and reduce the number of (distinct) plaintext-hash pairs. This decreases the password recovery success rate.

To increase the success rate, Hellman proposed using multiple tables where each table has a different reduction function. If P (t) is the success rate using t tables, then P (t) = 1 -(1 -P (1)) t , which is an increasing function of t. Hence, introducing more tables increases the password recovery success rate but increases the computational complexity and storage requirements.

A plaintext password is recovered from its hash value by performing a reduction operation on the hash value. Next, a search is conducted for a match of the computed plaintext value with a final value in the table. If a match is not found, the hashing and reduction operations are performed on the computed plaintext value to obtain a new plaintext value for another round of search. The maximum number of rounds of hashing, reduction and searching operations depend on the pre-defined chain length.

Rivest [START_REF] Denning | Cryptography and Data Security[END_REF] suggested using distinguished points as end points when generating the chains. Distinguished points are values that satisfy a given criterion (e.g., the first q bits are 0). In this method, chains are not generated with a fixed length; instead, they terminate upon reaching a pre-defined distinguished point.

This method decreases the number of memory lookups compared with Hellman's method and is capable of loop detection. If a distinguished point is not reached after a large number of operations, it is assumed that the chain contains a loop and is discarded. One limitation is that the chains will merge if there are collisions within the same table. The variable lengths of the chains also increase the number of false alarms. Additional computations are needed to rectify these errors.

Oechslin [START_REF] Oechslin | Making a faster cryptanalytic time-memory trade-off[END_REF] proposed a new table structure that reduces the probability of chains merging. The method uses a different reduction function to generate the elements in each chain column. Therefore, chains merge only when a collision occurs in the same column. For m chains of length n, the total number of possible chain merges (i.e., when two similar elements appear in the same column) is:

nm(m -1) 2 .
The total number of possible pairs not in the same chain column is:

n 2 m(m -1) 2 .
Therefore, given a collision in the table, the probability that there is a chain merge is:

nm(m-1) 2 n 2 m(m-1) 2 = 1 n .
Oechslin showed that the measured coverage in a single "rainbow" is 78.8% compared with 75.8% in a classical rainbow table constructed using distinguished points. In addition, the search effort is reduced, which contributes to an improvement in performance.

Thing and Ying [START_REF] Thing | A novel time-memory trade-off method for password recovery[END_REF] proposed an enhancement to the rainbow table method. The enhancement is achieved through initial chain generation by systematically manipulating the initial hash values based on an adjustable parameter k. A plaintext value is chosen and its hash value is computed using the password hash algorithm. The resulting hash value H is used to compute:

(H + 1) mod 2 j , (H + 2) mod 2 j , . . . , (H + k) mod 2 j ,
where j is the number of bits in the hash output. These hash values form the branches of the initial plaintext value. Alternate hashing and reduction operations are then applied to these branches. The resulting extended chains form a block. The final values of the chains in each block are stored with the single initial plaintext value. The same operations are performed on all the other initial plaintext values. These sets of initial and final values form the new pre-computed table.

Instead of storing all the initial and final plaintext values as pairs as in the rainbow table, an initial plaintext value is stored with multiple output plaintext values. This results in significant storage space savings compared with the rainbow table method. In particular, for the same storage space as the rainbow table method, the enhanced method yields 13.28% to 19.14% improvement in the total number of distinct plaintexthash pairs generated. However, some passwords "residing" in the first column will not be recovered because they are not stored in the table. This limits the search to n -1 chain columns instead of n columns.

Rainbow Table Method

We use the following notation in our discussion of the rainbow table method and its extensions: x i denotes the initial value of a chain; y i denotes the hash value of a password; z i denotes the reduced value of a hash; c i denotes the final value of a chain; h denotes a hash function; r i denotes a reduction function; n denotes the number of reduction functions or chain length; and m denotes the number of chains.

In order to generate a rainbow table, it is necessary to specify reduction functions r 1 , r 2 , . . . , r n that convert hash values y i to plaintext values z i . A large set of plaintext values x 1 , x 2 , . . . , x m are then chosen as the initial values of the table. As shown in Figure 1, these plaintext values are alternately hashed using the password hashing algorithm and reduced using the reduction functions. A rainbow table is created by only storing the final values c i along with their corresponding initial values x i (Figure 2). A password is recovered by alternately applying reduction and hashing operations to the corresponding hash values until a value is obtained that matches one of the final values in the rainbow table.

Consider the situation where it is necessary to find the password corresponding to the password hash v. One round of the reduction operation is applied to the password hash v to obtain the plaintext value w. Next, a search is performed and a match of w is found at the final value of the 212 th chain in the rainbow table in Figure 3 (i.e., w = c 212 ). The chain is then computed from its initial value x 212 until the password hash v is reached, which is equal to y 212,3000 . The password is the plaintext value z 212,3000 , which is before the password hash y 212,3000 .

If no matching value is found, it is assumed that the particular password does not exist in the rainbow table and cannot be recovered. The password recovery success rate can be improved by increasing the number of reduction functions and chains, but this increases the computational complexity and storage requirements.

Virtual Expansion of Rainbow Tables Method

Our proposed virtual expansion of rainbow tables (VERT) method virtually expands the rainbow table contents while maintaining the storage space requirements of the original rainbow table method. In VERT, the character set is first remapped to numerical equivalent values using the VERT mapping table .  An example VERT mapping for the alphanumeric character set is shown in Table 1. For a 7-character password, the initial plaintext value in the first chain of the VERT table is selected to be 0000000 and the initial plaintext value in the last chain is selected to be zzzzzzz. The initial plaintext values of the remaining chains are chosen from the rest of the password space based on evenly-distributed gaps. The gap size depends on the storage contraint. For example, if the storage space is only sufficient to store four plaintext values, the gap size is: (36 7 -1)/(4 -1) = 26121388032 after rounding up to the next integer. The four initial plaintext values are 0000000, c000001 (computed from 26121388032 = 12(36 6 )+1(36 0 )), n000000 (computed from 2(26121388032) = 52242776064 = 24(36 6 )) and zzzzzzz. These initial plaintext values are not stored in the VERT [START_REF] Oechslin | Making a faster cryptanalytic time-memory trade-off[END_REF]. Also, it supports password recovery to the first column unlike the enhanced rainbow table method [START_REF] Thing | A novel time-memory trade-off method for password recovery[END_REF].

The VERT method also incorporates an efficient storage mechanism that can support a larger table while using the same amount of storage as the original rainbow table. As seen in Table 1, each character in the VERT mapping table can be represented by six bits. Therefore, the final plaintext values of the chains are converted to their numerical representations before storage. Because eight bits of storage are required for each plaintext character in a rainbow table, the VERT method provides an additional storage conservation of up to 25% and an additional 33.33% increase in the number of chains without increasing the storage requirements.

Theoretical Analysis

This section presents a theoretical analysis and comparison of the performance of the VERT, original rainbow table and enhanced rainbow table methods.

Success Rate without Collisions

The password recovery success rate depends on the number of distinct plaintext-hash pairs generated in the chains, which, in turn, depends on the total number of plaintext-hash pairs generated. First, we perform the analysis ignoring element collisions. Next, we perform an analysis based on the number of distinct pairs and evaluate the effect on the password recovery success rate.

If there are m rainbow chains, each with n reduction functions and requiring storage for two plaintext values (initial value and final value of a chain), then a rainbow table has to store a total of 2m plaintext values. Thus, the number of plaintext-hash pairs is mn.

In the case of the enhanced rainbow table method, optimal performance is achieved when a single block is formed. Therefore, using the same storage space as in the original rainbow table, a total of n(2m -1) plaintext-hash pairs can be generated. This is computed from 2m(n -1)

-(n -2) ≈ 2mn -n ≈ n(2m -1) assuming that n ≫ 2.
The VERT method does not store the input plaintext values. Therefore, a VERT table can generate a total of 2(1.3333m) = 2.67m chains using the same storage space as the original rainbow table. Therefore, a VERT table would have 2.67mn plaintext-hash pairs. Compared with the original and enhanced rainbow table methods, this translates to 167% and 33% increases in the password recovery success rate, respectively. This success rate is based on the additional plaintext-hash pairs that are generated.

Success Rate with Distinct Pairs

The password recover success rate computed above ignores collisions. Because the collision probability increases with the size of a rainbow table, ignoring collisions is reasonable only for very small rainbow tables. We compute a more realistic password recovery success rate based on collisions with the distinct plaintext-hash pairs that are generated.

Our analysis assumes that storage space exists for m plaintext values. The password recovery success rate is computed based only on the distinct plaintext-hash pairs. The same number of reduction functions n is used for the original rainbow table, enhanced rainbow table and VERT methods.

Let N be the password space that comprises all possible plaintext passwords and let m i be the number of distinct plaintext-hash pairs in the i th column of the original rainbow table. Then, m i and m i+1 satisfy the recurrence relation:

m i+1 = N (1 -(1 - 1 N ) m i )
where m 1 = m. Thus, the probability of successful password recovery for the original rainbow table method is: In the case of the enhanced rainbow table method, let s i be the number of distinct plaintext-hash pairs in the i th column. Then, s i and s i+1 satisfy the following recurrence relation:

P (M ) = 1 -(1 - m 1 N )(1 - m 2 N ) . . . (1 - m n N ).
s i+1 = N (1 -(1 - 1 N ) s i ) ∀i > 1; s 1 = 1; s 2 = 2m -1.
Thus, the probability of successful password recovery for the original rainbow table method is:

P (S) = 1 -(1 - s 1 N )(1 - s 2 N ) . . . (1 - s n N ).
In the case of the VERT method, let v i be the number of distinct plaintext-hash pairs in the i th column of the VERT table. Then, v i and v i+1 satisfy the recurrence relation:

v i+1 = N (1 -(1 - 1 N ) v i )
where v 1 = 2.67m. Thus, the probability of successful password recovery for the VERT method is:

P (V ) = 1 -(1 - v 1 N )(1 - v 2 N ) . . . (1 - v n N ).
Note that v i > m i for all i ≥ 1. Thus, P (V ) > P (M ). In addition, P (V ) > P (S) since v i > s i for all i ≥ 1.

The password recovery success rates for the original and enhanced rainbow tables and for the VERT tables for different numbers of stored plaintext values (i.e., storage space) are computed based on the equations presented above. The results are presented in Table 2. The common parameters used in the methods are: (i) number of reduction functions (n): 5,700; (ii) character set: alphanumeric; (iii) plaintext/password length: 1-7 characters; and (iv) storage space (m): same for all methods.

Table 2 shows that the VERT method yields password recovery success rate improvements ranging from 16.92% for storage size m = 30 × 10 6 to 28.15% for storage size m = 10 × 10 6 . When compared with the enhanced rainbow table method, the VERT method provides password recovery success rate improvements ranging from 3.50% for m = 30 × 10 6 to 7.89% for m = 10 × 10 6 . The results show that even when collisions are considered, the VERT method offers substantial improvements in performance. Note also that the storage size constraint impacts the original rainbow table method much more significantly than the enhanced rainbow table and VERT methods.

Experimental Results

This section compares the results obtained with the VERT method and those obtained using RainbowCrack (source code version 1.2) [START_REF] Zhu | RainbowCrack: The time-memory trade-off hash cracker[END_REF].

Distinct Passwords and Success Rate

To evaluate the password recovery success rate when considering distinct pairs, we made a slight modification to RainbowCrack to log all the plaintext passwords (i.e., the stored initial and final columns as well as the intermediate chain columns). This logging was also performed for the VERT method. We also implemented scripts to detect collisions and count the distinct passwords in the logs.

The experiments were conducted using the following common parameters: (i) number of reduction functions (n): 3,000; (ii) character set: lower case alpha; (iii) plaintext/password length: 1-7 characters; and (iv) storage space (m): 10 6 . For fixed m = 10 6 , this translates to 10 6 chains for the RainbowCrack method and 2.67 × 10 6 chains for the VERT method.

The theoretical password recovery success rates for RainbowCrack and VERT when considering distinct pairs are 28.13% and 54.31%, respectively. In the experiments, the total plaintext-hash pairs generated were 3 × 10 9 by RainbowCrack and 8.01 × 10 9 by VERT. The total plaintext space was 8,353,082,582. A total of 2,349,122,955 distinct passwords were identified among the 3 × 10 9 plaintext passwords generated by RainbowCrack, corresponding to an actual password recovery success rate of 28.12%. On the other hand, VERT generated 4,536,258,880 distinct passwords, yielding an actual password recovery success rate of 54.31%. Thus, the experimental results match the theoretical results.

Note that the experiments conducted are preliminary in nature due to the scale of collision detection and distinct password count computa-tions. Additional experiments will be performed to study the impact of collisions for larger numbers of chains and reduction functions.

Computational Complexity

A password is computed by alternatively applying the reduction and hashing operations to the password hash value. However, VERT requires an additional final step of processing (numerical representation conversion) on the last computed plaintext value before it is stored in the table. This conversion is a simple operation; thus, it incurs insignificant computational overhead compared with hashing and reduction.

We conducted experiments on an Intel P4 3.06 GHz system to compute the time taken to perform: (i) random value generation for the initial column for RainbowCrack; (ii) deterministic value generation for the initial column for VERT, (iii) reduction and MD5 hashing operations for RainbowCrack and VERT (used for intermediate column processing); and (iv) single conversion of the final plaintext password to its numerical representation. A total of 10 9 rounds were performed for each operation and the average time for each round was computed. The average computation times were: (i) 1,656 ns; (ii) 7 ns; (iii) 644 ns; and (iv) 211 ns. Note that the final conversion operation only incurs an additional 211 ns for each chain. The initial value generation speed is greatly enhanced in VERT. The total time taken to generate the initial values for Rain-bowCrack is 1,656m ns while the time taken for VERT is (2.67 × 7)m = 18.69m ns. However, the main computational overhead is due to the reduction and hashing operations, which require a total of 644mn ns.

Conclusions

The novelty of the VERT method lies in the virtual expansion of the pre-computed tables, which increases the password recovery success rate while limiting the storage requirements. Compared with the original rainbow table method, the VERT method increases the password recovery success rate by 16.92% to 28.15% for the distinct pairs comparison while considering collision effects. The VERT method also shows an improvement in the password recovery success rate compared with the enhanced rainbow table method. In particular, the VERT method yields up to 33% improvement for the total plaintext-hash pairs comparison and 3.5% to 7.89% improvement for the distinct pairs comparison. Note also that it is possible to trade-off storage conservation in favor of high password recovery success rates for longer passwords (i.e., larger password spaces).

Our future work related to the VERT method will analyze collisions and password recovery success rates in larger tables. Additionally, we plan to investigate improvements in the password recovery time achieved by reducing the number of columns while maintaining the same storage requirements and password recovery success rates as the original and enhanced rainbow table methods.

Figure 1 .

 1 Figure 1. Rainbow table.

Figure 2 .

 2 Figure 2. Stored values in a rainbow table.

Figure 3 .

 3 Figure 3. Password recovery example.

Table 1 .

 1 VERT mapping table.

	Character Numerical
	Set	Equivalent
	0	0
	1	1
	2	2
	...	...
	a	10
	b	11
	...	...
	z	35
	table. Instead, only their final plaintext values are stored. Therefore,
	VERT provides a 100% increase in the number of chains compared with
	the original rainbow table

Table 2 .

 2 Success rate based on distinct plaintext-hash pairs.

	Storage	Original	Enhanced	VERT
	Size (m) Rainbow Table Rainbow Table	Table
	10 × 10 6	45.07%	65.33%	73.22%
	15 × 10 6	56.94%	76.15%	82.62%
	20 × 10 6	65.33%	82.60%	87.82%
	25 × 10 6	71.50%	86.74%	91.00%
	30 × 10 6	76.15%	89.57%	93.07%