Smart Unpacking

Understanding Files Through Patter

Benjamin Long, AAFS 2009
Disclaimer

DisclaimerTrade names and company products arementioned in the text or identified. In no cas

does such identification imply

recommendation or endorsement by the

National Institute of Standards and Technolonor does it imply that the products are

necessarily the best available for the purposeStatement of Disclosure

This research was funded by the National

Institute of Standards and Technology Office 

Law Enforcement Standards, the Departmenof Justice National Institute of Justice, theFederal Bureau of Investigation and theNational Archives and Records Administratio
Outline

• NSRL Project Description

• Smart Unpacking Description

• Smart Unpacking use

• Smart Unpacking overview
Introduction to the N

• Is a computer forensics project a

• Is composed of 3 things:

1. library: physical collection of softwar

packages

2. database: logical collection of collect

information

• file name, size, type, package, MD5, SHA

3. RDS: (Reference Data Set) and other 

• Produced quarterly

• Metadata db – close to 75M files; public

db schema
NSRL Use (Data Reduc

RDS

UNKNOW

FILES

Disk Drive

KNOW

AnalysisProgram

NSRL

zUnpack 

archives

zProvide 

File info

File info
NSRL Use

• Application of NSRL unique identificati

– Law Enforcement

• Automated elimination of “known” app files fr

• Positive ID of “interesting” files

• Forensic tools use various metadata

• NIST/NSRL – provides – unbiased, court‐admis

DoD

– NARA Presidential search

– Voting – baseline maintenance; auditing

– Ongoing research – online archive of data

identification

– Used by all major tools
media

collect

files

ExtractableArchivefiles

UnextractableCompoundfiles

NSRLSmar

ExtractFiles

ExtractFiles

{deun

NSRL File Extraction

[nounpacker][unpackeravailable] (CDs,DVDs,...)

Compound

“Container”

Files
The Need

NSRL wants more files ...

– Two primary ways to get more

1.Get more media (containing files)

2.Unpack more compound files (i.e., archive

– Fundamental challenge

– get files out of archives

– Why is it hard?

– different versions, different formats

– corruption– unpacker not always available or current

This need will always exist
Smart Unpacking App

Addresses NSRL Need by creating a 

tools, and techniques for ...

1. Getting files out2. Doing this in a general, reliable, 

manner

3. Producing unpacker programs a

of unpacking results
Smart Unpacking ‐ How 

3 major steps

Representation Æ Inference Æ Unpacking

1. Representation

– choose primitives– encode data to differentiate key 

2. Inference

– perform pattern‐theoretic and

other analyses on representatio

– locate files and meta‐data– derive measures– derive + test unpacker

3. Unpacking

– extract files– measure results
Unextractable

Archive

SU process derives un

total files e

Archive 

tota

Example Smart Unpacking Ex

acpid*.deb

Chaos

Order

Representation & 

transformation
An Example Usage of Smart 

1. File ACPID*.deb was 1 archive in 

– Applied SU process, tools, techniq

2. Now it is 89 files

– Derived unpacker program, execut

extracted files

3. Verification

– Found alternate unpacker program 

SU result

– Original archive had corrupted dat

format variances from standard fo
Technical /Scientific Basis and M

Pattern Theory Formal Language 

Measurements a

•Derived from 

•Information Theory

•Statistics•Probability•Universal Algebra•Topology•Graph Theory, and more ...

Mathematical Modeling based on: Parser Theory

•Variable lookahe•Multi‐channel to•Augmentation w

predicates for con

...

_

min

min

),,,(

rulesR

rulestartS

alster

nonterV als

SRVG 

=

=

=∑

=

∑= =

...

)}(,...,2,1{)(

_)}(,...,3,2,1;{)(

,...,, _

__

,: _

},,...,,{ _

21

0

10

gwjgB

jbg bondgw structures

bondbbb values

GG partition of generators

SsGGS similarity group

ggggG generator space

v

s j

A

ii

==

==Β =

=

==

←⎯→ =∈

= =

∈

β

ω

α

α U

Context‐free gram

Methods used to Discern Structure and Metadata

‐Modeling‐Uniqueness features in – syntax, content, abstract pattern repre
Next Steps

• Production‐quality• Validation + Testing

• Integration into NSRL ops
NSRL + SU

Use (Data Reductio

RDS

UNKNOW

FILES

Disk Drive

KNOW

AnalysisProgram

NSRLzUnpack 

archives

zProvide FII

MORE 

File info

NSRL Unpackers Æ {extractable archives}

Smart Unpacking Æ {unextractable archives}
SU Useful for Other T

• SU can add to current NSRL/CF efforts

– Block hashing

• locate, optimize blocks to hash

• Associate parse‐rule for fixed‐sections with va

algorithm

– NOW:

» hash according to parse rule rather than f

– File Carving/Content Analysis

• Through pattern experiments, build up corpus 

primitives, and rules

• Make higher‐level reductions of content

– NOW:

» Use existing techniques (suffix arrays, bio

abstract, compressed representations rat
Contact

Benjamin LongSoftware and Systems Divisionwww.nsrl.nist.gov, NSRL Projectblong@nist.govBarbara GuttmanSoftware and Systems Divisionbarbara.guttman@nist.govDouglas White, NSRL Project LeadSoftware and Systems Divisiondwhite@nist.govSue Ballou, Office of Law EnforcemenStandardsRep. For State/Local Law Enforcemensusan.ballou@nist.gov