Smart Unpacking Research:

Using Mathematics To Unpack More

Benjamin Long
Disclaimer

Disclaimer

Trade names and company products are

mentioned in the text or identified. In no

case does such identification imply

recommendation or endorsement by the

National Institute of Standards and

Technology, nor does it imply that the

products are necessarily the best available

for the purpose.

Statement of Disclosure

This research was funded by the National

Institute of Standards and Technology

Office of Law Enforcement Standards, the

Department of Justice National Institute of

Justice, the Federal Bureau of

Investigation and the National Archives

and Records Administration.
media

collect

files

Unpackable

Compound

files

Not

Unpackable

Compound

files

NSRL

Smart Unpacking

Extract

Files

Extract

Files

{derive

unpacker}

Reference

Data Set

(RDS)

Context – Smart Unpacking and NSRL Operations

{emulate

unpacker

operation} [no

unpacker]

[unpacker

available] (CDs,DVDs,...)

Compound

“Container”

Files

Provide

collected

info (FII)
Smart Unpacking

• NSRL collects files by unpacking

• New file types appear faster than new

unpackers

• NSRL goal: unpack and provide FII for as

many files as possible

• SU – attempts to facilitate this goal by

– Unpacking files when have no unpacker

– Forming measurements

(completeness,accuracy) of unpacking ops
Nature of Unpacking

• Unpacking: locate, identify, and extract

files completely and accurately from

compound structures

• SU studies and formalizes

– How to use mathematical methods to find

structure in content and nonstandard

packaging

– How to use this to detect, extract, and

measure files
SU Research – Early Stages

• To date has –

– Established basis for theoretical and practical

implementation

– Not yet formalized unpacking systems

– Implemented specific prototypes and experiments

• Experiments have shown capability to

– Do basic inline extractions

– Do similarity and grammatical pattern correlation

across many file types (binary and non-binary)
Experiment – Binary Similarity –

MSI File Type

0 20 40 60 80 100 120

a

b

d

f

k

n

w

z

0x00000000

0x00000000

0x00000000

0x00000000

0x00000000

0x00000000

-Grammatical/location-specific

similarity in binary data

-Graph of location-specific contentclass frequencies

- basis for preliminary unpacker

development

- metadata types: file size, location,

data size, unpacker version,

user/group ids, storage volume used

z 0x00

w white-space

n numeric

k brackets

f 0xff

d delimiter

b binary

a alpha

legend
Technical and Scientific Basis and Methods

Pattern Theory Formal Language Theory

Measurements and Measurability

•Derived from mathematical models

•Information Theory

•Statistics

•Probability

•Universal Algebra

•Topology

•Graph Theory, and more ...

Mathematical Modeling based on: Parser Theory

•Variable lookahead mechanisms

•Multi-channel token processors

•Augmentation with syntactic and

semantic predicates for contextsensitivity

...

_

min

min

( , , , )

R rules

S start rule

ter als

V nonter als

G V R S grammar

=

=

! =

=

= ! =

...

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

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

, ,..., _

_ _

: , _

{ , ,..., , } _

1 2

0

0 1

B g j w g

g b j w g bond structures

b b b bond values

G G partition of generators

S G G s S similarity group

G g g g g generator space

v

s j

A

i i

= =

! = = =

=

= =

%#$ " =

= =

"

&

'

(

(

U

Context-free grammars

Methods used to Discern Structure and Metadata

-Modeling

-Uniqueness features in – syntax, content, abstract pattern representations
Spectrum of Unpacking Scenarios

• Simplest – very little knowledge req’d, inline metadata

and content; just need an unpacker

• More complex – more complicated structure, nesting,

intermingled file, content, and encoding types, alignment

considerations (MSI experiment)

• Harder – req’s knowledge of metadata and structure

relationships; mathematical + experimental models

• Even Harder – at least 1 transform – compressed,

encrypted, etc – but still can get metadata and op

properties

• Hardest – 2 or more transforms, little to no metadata –

will often still get some metadata and specific properties
Unpacking Operation Measurement

• Measuring (at least) – accuracy and

completeness of unpacking operation

– Per file – from a given compound file

– Across all files/content from a given compound file

• Beginning – focus on simple, coarse-grained

ratios – total found/total extracted (files, content)

• Ongoing Objective –

– develop content and format-specific measures –

entropy-, probabilistic-, algebraic-based properties of

content and structure

– Simplify into classes of overall properties per file type
Work From Here

• Integrate prototype tools and experiments

into automated unpacking framework

• Research and integrate

– methods for harder cases

– Relevant measurements

• Track ability to increase overall coverage

of the NSRL
Contact

Benjamin Long

www.nsrl.nist.gov

nsrl@nist.gov

Barbara Guttman

Software Diagnostics & Conformance

Testing Division

barbara.guttman@nist.gov

Sue Ballou, Office of Law Enforcement

Standards

Rep. For State/Local Law Enforcement

susan.ballou@nist.gov