Transcript Diversity Algorithms for Worrisome Software and

Diversity Algorithms for Worrisome
Software and Networks
(DAWSON)
James Just, GITI
Karl Levitt & Jeff Rowe, UC Davis
Approved for Public Release, Distribution Unlimited
The DAWSON Team
• Global InfoTek, Inc (GITI)
– James Just , Bruce Wilner, Mark Cornwell
• UC Davis
– Karl Levitt, Hao Chen, Zhendong Su, Jeff
Rowe
– Ivan Balepin, Allen Ting, Ebrima Ceesay,
Tufan Demir
• R. Sekar (consultant, SUNY)
20 July 2004
Approved for Public Release, Distribution Unlimited
2
The Problem Space
• Increasing monoculture in operating systems and key
applications create opportunity for massive common
mode failures
– Highly susceptible to viruses and worms
– Spread widely and quickly (or slowly)
• Intrusion tolerant systems difficult to build
– Expensive, large hw/sw footprints, a priori knowledge of
attack modalities
– Need significant diversity of spares -- even if intrusion
tolerance is affordable approach, practical limits exist on
diversity of spares
• N-version programming is costly
• Limited commercial diversity of similar apps
• Foreseeable cyber-risks dominated by static, durable
executable monoculture
20 July 2004
Approved for Public Release, Distribution Unlimited
3
Synthetic Diversity Approaches
• Source code:
– Easiest area to introduce diversity via compilers
– Complicates distribution and updating
– Significant market penetration problems with software
vendors
• Binary (executable) code:
– More difficult to introduce diversity
• Disassembly is not exact science
• Runtime and randomized modification is harder still
– Can be implemented by organizations and users who need
the benefits
• Binary code with annotations (hints)
20 July 2004
Approved for Public Release, Distribution Unlimited
4
DAWSON Approach
• Runtime randomized transformations of executable
–
–
–
–
Preserve functionality of executable modules (e.g., dll)
Transform binary code, machine addresses, names, etc
Can use annotations to facilitate
Random “cryptographic” keys will cause unique
transformations on each application restart
– Similar approach for network protocols
• Low overhead transforms (runtime performance)
• Goal: Beat program metric by 10X for large fraction
of exploit space
– 100 functional equivalents with no more than 3 susceptible
to same exploit as baseline code for most exploits
• Policies can determine which type of transform is
favored
20 July 2004
Approved for Public Release, Distribution Unlimited
5
Evaluation
• Internal testing with
– Fabricated applications with known vulnerabilities
and exploits
– Real applications with known vulnerabilities and
exploits
• Independent test team?
20 July 2004
Approved for Public Release, Distribution Unlimited
6
Impacts
• Introducing spatial and temporal diversity to common
Windows applications will reduce the effective size of
world’s largest computer monoculture
– Size and breadth of transform space vs vulnerability space
– Extent of penetration
– Counter-measures
• Fine-grained diversity mechanisms are key enabler
for intrusion tolerance
– Fourth generation, secure, survivable systems
– Easily integrated with other SRS components.
20 July 2004
Approved for Public Release, Distribution Unlimited
7
Transition and Future Work
• Standard research publications
• Integrate with follow-on projects/products
• If successful
–
–
–
–
Possible GITI commercial product
Possible open source “toolkit” approach
Microsoft or other software vendors
Military users
• More definitive plans as project develops
20 July 2004
Approved for Public Release, Distribution Unlimited
8
Software:
Concept to
Implementation
Software
Specification
Source
Code
Executable
Code
Linker
Loader
Machine-level
Code
Machine Code
Specification
20 July 2004
Approved for Public Release, Distribution Unlimited
9
Illustrative Common Techniques & Assumptions
Segment of Code Red 1 Disassembly1
01
02
03
04
05
06
07
1. Relative Virtual Addressing is
Windows name for identifying
loc_4B4:
; CODE XREF: DO_RVA+26Dj
specific memory addresses in
mov esi, esp
executable files without
mov ecx, [ebp-198h]; set ecx with the data segment pointer
hardcoding (offset to virtual
push ecx; push data segment (pointer of function to load)
memory load location).
mov edx, [ebp-1CCh]; get current RVA base offset
push edx; push module handle(base loaded address)
call dword ptr [ebp-190h]; call GetProcAddress
2. This calls dll’s specific API
(GetProcAddress) via IAT.
GetProcAddress is one of two
key functions for the exploit.
LoadLibraryA (not shown) is the
other.
3. After this, GetProcAddress and
LoadLibraryA are used to load
kernel32.DLL, infocomm.DLL and
WS2_32.DLLto access the file
system, open network
andAnalysis by Ryan Permeh, Marc Maiffret. http://www.eeye.com/html/advisories/codered.zip.
Excerpted fromsockets
Code Red Disassembly
send and receive network packets.
Approved for Public Release, Distribution Unlimited
1
20 July 2004
10
Many Assumptions Made
• Breaking the assumptions mechanically
–
–
–
–
–
–
–
–
20 July 2004
Re-arrange the run-time stack
Permute the addresses in the jump table
Change the machine code (table transformation)
Change the interpretation of (encrypt) filenames
Change the order of parameters for system calls
Encrypt file name parameters to system calls
Rename ports for network connections
Put return pointers on a separate stack
Approved for Public Release, Distribution Unlimited
11
Current
Attack
Problem
Known
V-Spec
Software
Specification
Source
Code
Executable
Code
Linker
Loader
Attack
Machine-level
Code
Machine Code
Specification
20 July 2004
Approved for Public Release, Distribution Unlimited
12
Software
Specification
Breaking the
V-Spec
Known
V-Spec
Source
Code
Transform
Specifications
Executable
Code
Transformer
Linker
Loader
Attack
X
Doesn’t
Match
20 July 2004
Machine-levelMachine-level
Code
Machine-level
Code
Machine-level
Code
Machine-level
Code
Machine-level
Machine-level
Code
Code
Code
Machine-levelMachine-level
Machine-level
Code
Code
Code
Machine-level
Machine-level
Machine-level
Code
Machine-levelCode
Machine Code
Code
Code
Specification
V-Spec Unknown Until Load-Time
Approved for Public Release, Distribution Unlimited
13
Transform Techniques in Literature*
•
Obfuscation
–
–
–
–
Layout obfuscation (scramble identifiers, remove comments, change formats)
Control flow obfuscations (Statement grouping, ordering, computation, opaque constructs)
Data obfuscation (Storage, encoding, grouping, ordering)
Preventative transformations (prevent decompilers from operating by exploiting weaknesses)
•
•
•
Inherent (aliases, variable or bogus dependencies, opaqueness side effect & difficulty)
Targeted
Source code
–
–
N-version programming
Functional-behavior preserving diversity in components used (e.g., different encryption
algorithms, different scales for data such as Celsius or Fahrenheit)
Semantics preserving source code transformations
–
•
•
•
–
–
•
Place sensitive data (such as function and data pointer) below the starting address of any buffer
Variable ordering
Equivalent instructions
Variable compilation --Variable internal names, padding and addresses, linking orders
Insertion of opaque constructs or other dead code to change memory layout
Binary code
–
Address transformation on binary code
•
•
•
–
–
20 July 2004
Randomize base address of memory regions (Stack, Heap, DLL, routines/static data in executable)
Permute order of variable/routines (Local variables in stack frame, static variables, routines in shared
libraries or routines in executables)
Introduce random gaps between objects (Padding in stack frames, between successive malloc allocation
requests, between variables in the static area; Gaps within routines and add jump instructions to skip over
gaps)
System resource, system call, or DLL name/address transformation
Instruction set transformation
*References at end of document
Approved for Public Release, Distribution Unlimited
14
ver
sio
nP
Be
rog
ha
ram
vio
r
mi
In t
Tr
ng
an
ern
sfo
al
r
Da
ms
In t
ta
ern
(So
Flo
al
urc
wT
Co
eC
Pla
n
r
an
tro
od
ce
s
e)
l
Sen
for
Flo
m
s
wT
itiv
En
s (S
cry
eD
ran
ou
pt
at a
rce
sfo
E
r
B
Co
x
Ob
m
e
e
cut
low
s (S
de)
fus
a
ou
c at
ble
Bu
r
e
f
c
fer
eC
Tr
Ex
s (S
an
ecu
od
sfo
e)
o
t
urc
ab
rm
l
e
eC
Tr
R
C
an
ela
od
od
sfo
e
tiv
e)
rm
eA
Tr
d
A
d
an
bso
res
sfo
lut
se s
rm
e
(Ex
Ad
Tr
Sy
an
d
ecu
ste
r
sfo
e
m
sse
ta b
rm
R
s (E
le)
eso
Tr
(
V
xec
an
urc
irt
sfo
u
u
es
tab
al)
rm
(E
le)
Ho
Tr
xec
Pr
an
s
oto
t In
uta
sfo
c
ble
str
ols
rm
uct
)
En
Sta
Ex
i on
cry
te
ecu
Sp
pt
Set
tab
ac e
Ne
le P
tw
(
S
ork
rot
ou
rce
oc o
/In
)
ter
ls v
f ac
ia
Pr
eP
ox
rot
ies
oco
ls
Effectiveness of Transforms
Vulnerability
Class
Sample Vulnerabilities in Class
Improper
Memory error
Code injection attacks (stack,
Validation
heap, and integer overflows)
Existing code exploits (printf)
Design errors
Code injection attacks (SQL
injection, cross site scripting)
Improper exception handling
Protocol errors (IP session
hijacking, Unicode attacks,
ARP cache poisoning)
Improper
System misconfiguration, e.g.,
Exposure
default passwords and accounts
Inadequate
Randomness
Improper
Deallocation
Race condition
Address or data leakage
Social engineering, dumpster diving
Weak passwords
Weakly encrypted passwords
Memory leakage
Resource exhaustion
N-
Diversity is not a panacea
for achieving cybersecurity. There are many
other ways to penetrate a
system
+
+
+
+
+
+
+
+
+



+
+
+















+







+
+
+




































+
+




















+
+
+
< [1] ++ ++ ++ ++
< [1] ++ ++ ++ ++








++



+
+





+
+
+



























+
+
+
+
+
+








+
+





Key: Effectiveness in preventing attack: ++ = highly effective, + = effective, · = negligable, < = potentially counterproductive
Approved for Public Release, Distribution Unlimited
20 July 2004
15
Diversity System Architecture Overview
Input
Input
Policy
Key
Generator
Original
Program
Key
Analyzer
Transformer
Annotation
20 July 2004
Monitor
Executio
n
Space
Transforme
d
Code
Loader
Wrapper
Approved for Public Release, Distribution Unlimited
16
Diversity System Functional Architecture
Modified loader
Attacker
transforms original
stored program and
generates wrapper
that retranslates User Inputs
external calls
Untranslation
Response to
normal user
inputs are
translated &
untranslated
so they work
Other
System
Resources
Original
Program
Annotation
File
20 July 2004
Modified
Loader
Random
Key
Wrapper
Transformed Some attacks
In-memory
fail because
program
assumed
vulnerability
is gone
Approved for Public Release, Distribution Unlimited
Other attacks
fail because
injected
commands
are wrong
17
DAWSON Project Schedule &
Milestones
FY04
Baseline Tasks
1.
Requirement
Refinement
2.
Program. Code
Diversity
3.
Protocol
Diversity
4.
Integration
5.
T&E
6.
Program Mgt.
Prototype
FY06
FY05
Q2 Q3 Q4 Q1 Q2 Q3 Q4 Q1 Q2 Q3 Q4
1
2
3
Optional Task
- Self-Monitoring
20 July 2004
Approved for Public Release, Distribution Unlimited
18
Creating heterogeneous
environments for malicious code
Karl Levitt, Hao Chen, Zhendong Su, Jeff Rowe, Ivan
Balepin, Allen Ting, Ebrima Ceesay, Tufan Demir
UC Davis Computer Security Lab
Approved for Public Release, Distribution Unlimited
Why do we want heterogeneity?
• Homogeneity is a natural requirement
– As for software: development, distribution,
maintenance, data sharing, etc.
– Fixed protocols for communications and
interoperability
• The real challenge is in achieving both
– Create a heterogeneous vulnerability environment
– Keep all the benefits of homogeneity.
20 July 2004
Approved for Public Release, Distribution Unlimited
20
Host level Heterogeneity
• Microsoft Windows
– Most prevalent platform
– Many security flaws
• Defense against Scripted Attacks
– Windows forms a wide homogeneous environment for
large scale attacks.
– Single attack implementation compromises all machines
with the vulnerable service.
– Buffer overflow is the most common vulnerability in
widespread attacks.
20 July 2004
Approved for Public Release, Distribution Unlimited
21
Windows Execution Environment
• Windows executables must call API functions
for any significant tasks
– System calls are not accessible by a user program.
• All API functions are provided in DLLs.
– Load address of API functions is not known until
the program loads
– Load address of API functions varies from host to
host
20 July 2004
Approved for Public Release, Distribution Unlimited
22
How does DLL system work?
80000000
stack
20000000
.text
IAT
`LoadLibraryA’
77E9D961
kernel32.dll
LoadLibraryA()
77E9D961
010031A0
77E80000
Call *010031A0
01001000
heap
00070000
00000000
20 July 2004
Approved for Public Release, Distribution Unlimited
65D60000
23
Permute IAT
80000000
stack
Call *010031A0
20000000
.text
IAT
`LoadLibraryA’
010031A0
77E90332
`GetProcAddress’
77E9D961
0100308C
Call *010031A0
*0100308C
kernel32.dll
LoadLibraryA()
77E9D961
GetProcAddress()
77E90332
77E80000
01001000
heap
00070000
00000000
20 July 2004
Approved for Public Release, Distribution Unlimited
65D60000
24
Case study: Code Red
stack
Injected code
kernel32.dll
20000000
LoadLibraryA()
77E9D961
.text
EAT
01001000
`LoadLibraryA’
77E9D961
heap
`KERNEL32’
00070000
00000000
20 July 2004
Approved for Public Release, Distribution Unlimited
77E80000
25
Case study: SQL Sapphire
stack
Injected code
kernel32.dll
LoadLibraryA()
20000000
77E9D961
.text
sqlsort.dll
01001000
IAT
77E9D961
heap
00070000
00000000
20 July 2004
Approved for Public Release, Distribution Unlimited
77E80000
26
Case study: MS Blaster
stack
PEB
Injected code
`KERNEL32’
77E80000
20000000
.text
kernel32.dll
LoadLibraryA()
77E9D961
01001000
heap
EAT
00070000
00000000
20 July 2004
`LoadLibraryA’
77E9D961
Approved for Public Release, Distribution Unlimited
77E80000
27
Operand hijacking
80000000
PEB
stack
Injected code
20000000
LoadLibraryA()
IAT
.text
kernel32.dll
77E9D961
Call *0100308C
77E9D961
0100308C
77E80000
01001000
heap
00070000
00000000
20 July 2004
Approved for Public Release, Distribution Unlimited
65D60000
28
Heterogeneous Network Protocols
• Many common attacks rely upon security
flaws in network protocols.
• Invariant properties of protocols are the
foundation of network communications.
• How can network protocols be diversified
while still maintaining the critical invariant
requirements.
20 July 2004
Approved for Public Release, Distribution Unlimited
29
Approach
• Use a state-machine specification of protocols to
express the required invariant properties.
• Transitions between states, representing protocol
messages, can be modified as long as a path to the
subsequent state is maintained.
• Variation in the modifications can create a diverse
collection of network protocols whose protocol
messages may differ, but with the required invariant
properties needed for functionality.
20 July 2004
Approved for Public Release, Distribution Unlimited
30
Example: The DHCP Protocol
Reallocate
DHCP Server FSM
Request
arrive
INI
T
IP
Prepar
e
Allocate
IP
Released
Expire
Selected
END
Boun
d
ReplyWait
Renew/InfoReq
Rejected/Timeout
No Available IP
T2 Timeout
DHCP Client FSM
Request
INIT
ReplyTimeOut
20 July 2004
Offer
Waiting
Offer
Confirm
Bind
Relinquish
Bind
Confirm
Selecting
Bind_Dec/Timeout
Approved for Public Release, Distribution Unlimited
Bound
Binding
Release
Renew/InfoReq
31
A DHCP Protocol Variation
•Introduce two new
states: S1 and C1.
•Introduce two new
transitions: Snew and
Cnew.
Reallocate
INI
T
Request
arrive
•Standard DHCP
protocol messages take
the server and client
from the new state to
the invariant state
preserving protocol
functionality.
•Attacks depending
upon forged AllocateIP
messages will fail since
the attacker assumes
that server is in the
IP_prepare state
20 July 2004
Released
S1
Allocate IP
Snew
Expire
Selected
IP
Prepare
Boun
d
ReplyWait
END
Renew/InfoReq
Rejected/Timeout
No Available IP
T2 Timeout
C1
Cnew
Request
INIT
ReplyTimeOut
Offer
Waiting
Offer
Confirm
Bind
Relinquish
Bind
Confirm
Selecting
Bind_Dec/Timeout
Approved for Public Release, Distribution Unlimited
Bound
Binding
Release
Renew/InfoReq
32
Research Topics
• Evaluation of diversity approach for known
large-scale attacks.
• Evaluation for hypothesized attacks.
• Analyze complexity of diversified system
– How does it affect normal system operations
– Does it increase the attacker’s work factor
• Prototypes
– Heterogeneous host-based Windows environment
– Heterogeneous network environments
20 July 2004
Approved for Public Release, Distribution Unlimited
33
Related research
• Source code checker
– Flawfinder, ITS4, PScan, Splint, etc.
• Compiler techniques
– StackGuard, StackShield
• Non-executable stack
– OverflowGuard
– SecureStack
– Service pack for Windows (will be available in ‘04)
• Run-time protection
– Baratloo et. al.
• Code Obfuscation
20 July 2004
Approved for Public Release, Distribution Unlimited
34
References
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Lee Badger, Larry D'Anna, Doug Kilpatrick, Brian Matt, Andrew Reisse, Tom Van Vleck. “Self-Protecting Mobile Agents Obfuscation Techniques
Evaluation Report,” Network Associates Laboratories, Report #01-036, Nov 30, 2001, updated March 22, 2002.
[Balzer-99] R. Balzer, N. Goldman. Mediating Connectors. Proceedings of the 19th IEEE International Conference on Distributed Computing Systems,
Austin, Texas, May 31-June 4, 1999, IEEE Computer Society Press 73-77
Boaz Barak, Oded Goldreich, Russell Impagaliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang. “On the (im)possibility of obfuscating
programs.” In J. Kilian, editor, Advances in Cryptology-CRYPTO ‘01, Lecture Notes in Computer Science. Springer-Verlag.
Elena Gabriela Barrantes, David H. Ackley, Stephanie Forrest, Trek S. Palmer, Darko Stefanovic and Dino Dai Zovi, “Randomized instruction set
emulation to disrupt binary code injection attacks,” 10th ACM Conference on Computer and Communications Security, Washington DC, October 27-31,
2003.
Sandeep Bhatkar, Daniel C. DuVarney, and R. Sekar, “Address Obfuscation: An Efficient Approach to Combat a Broad Range of Memory Error
Exploits,” 12th USENIX Security Symposium, August 2003.
M. Chew, D. Song. “Mitigating Buffer Overflows by Operating System Randomization,” Technical Report CMU-CS-02-197.
C. Collberg, C. Thomborson, and D. Low. “A Taxonomy of Obfuscating Transformations”. Technical Report 148, Department of Computer Science,
University of Auckland, July 1997.
C. Collberg, C. Thomborson, and D. Low. “Manufacturing Cheap, Resilient, and Stealthy Opaque Constructs” Department of Computer Science,
University of Auckland. ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'98). January 1998
C. Collberg, C. Thomborson, D. Low. “Breaking Abstractions and Unstructuring Data Structures”, Proceedings of the 1998 International Conference on
Computer Languages, pages 28-38. IEEE Computer Society Press. May 1998.
Larry D’Anna, Brian Matt, Andrew Reisse, Tom Van Vleck, Steve Schwab, Patrick LeBlanc, “Self-Protecting Mobile Agents Obfuscation Report - Final
report,” Network Associates Laboratories, Report #03-015, June 30, 2003
Hiroaki Etoh and Kunikazu Yoda. Protecting from stack smashing attacks. Published on World-WideWeb at URL
http://www.trl.ibm.com/projects/security/ssp/main.html, June 2000.
Stephanie Forrest, Anil Somayaji, and David H. Ackley. “Building diverse computer systems.” In 6th Workshop on Hot Topics in Operating Systems,
pages 67-72, Los Alamitos, CA, 1997. IEEE Computer Society Press.
James E. Just, et al., “Learning Unknown Attacks A Start,” Recent Advances in Intrusion Detection, 5th International Symposium, Zurich, Switzerland,
October 16-18, 2002, Proceedings, A. Wespi, G. Vigner, and L. Deri, (Eds.), Springer, Lecture Notes in Computer Science.
Gaurav S. Kc, Angelos D. Keromytis, Vassilis Prevelakis, “Countering Code-Injection Attacks with Instruction-Set Randomization,” 10th ACM
Conference on Computer and Communications Security, Washington DC, October 27-31, 2003.
Cullen Linn, Saumya Debray, “Obfuscation of Executable Code to Improve Resistance to Static Disassembly,” ACM Conference on Computer and
Communications Security, Washington DC, October 27-31, 2003.
D. L. Lough. A Taxonomy of Computer Attacks with Applications to Wireless Networks. PhD Thesis, Virginia Polytechnic and State University,
Blackburg, VA.
Douglas Low, Java Control Flow Obfuscation, MS Thesis, Univ. Auckland, 3 June 1998
Pax. Published on World-Wide Web at URL http://pageexec.virtualave.net, 2001.
Ryan Permeh, Marc Maiffret, Code Red Disassembly Analysis, eEye Digital Security, http://www.eeye.com/html/advisories/codered.zip.
Chenxi Wang, “A Security Architecture for Survivability Mechanisms.” PhD thesis, University of Virginia, October 2000.
Gregory Wroblewski, “General Method of Program Code Obfuscation,” PhD Dissertation, Wroclaw University of Technology, Institute of Engineering
Cybernetics, 2002.
Jun Xu, Z. Kalbarczyk and R. K. Iyer. Transparent Runtime Randomization for Security. Proc. of 22nd Symposium on Reliable
20 July 2004
Approved for Public Release, Distribution Unlimited
35