The Challenges of Dynamic Software Analysis
undefined
Accelerating Dynamic
Software Analyses
Joseph L. Greathouse
Ph.D. Candidate
Advanced Computer Architecture Laboratory
University of Michigan
December 1, 2011
NIST: SW errors cost U.S. ~$60 billion/year as of 2002
FBI CCS: Security Issues $67 billion/year as of 2005
>⅓ from viruses, network intrusion, etc.
Software Errors Abound
2
Example of a Modern Bug
3
Thread 2
mylen=large
Thread 1
mylen=small
ptr
∅
Nov. 2010 OpenSSL Security Flaw
if(ptr == NULL) {len=thread_local->mylen;
ptr=malloc(len);
memcpy(ptr, data, len);
}
Example of a Modern Bug
4
if(ptr==NULL)
if(ptr==NULL)
ptr
LEAKED
TIME
Thread 2
mylen=large
Thread 1
mylen=small
∅
len2=thread_local->mylen;
len1=thread_local->mylen;
ptr=malloc(len1);
memcpy(ptr, data1, len1)
Dynamic Software Analysis
Analyze the program as it runs
+
System state, find errors on any executed path
–
LARGE runtime overheads, only test one path
5
LONG run time
Taint Analysis
(e.g.TaintCheck)
Dynamic Bounds
Checking
Data Race Detection
(e.g. Inspector XE)
Memory Checking
(e.g. MemCheck)
Runtime Overheads: How Large?
6
Symbolic Execution
Outline
Problem Statement
Background Information
Demand-Driven Dynamic Dataflow Analysis
Proposed Solutions
Demand-Driven Data Race Detection
Sampling to Cap Maximum Overheads
7
Dynamic Dataflow Analysis
A
s
s
o
c
i
a
t
e
m
e
t
a
-
d
a
t
a
w
i
t
h
p
r
o
g
r
a
m
v
a
l
u
e
s
P
r
o
p
a
g
a
t
e
/
C
l
e
a
r
m
e
t
a
-
d
a
t
a
w
h
i
l
e
e
x
e
c
u
t
i
n
g
C
h
e
c
k
m
e
t
a
-
d
a
t
a
f
o
r
s
a
f
e
t
y
&
c
o
r
r
e
c
t
n
e
s
s
Forms dataflows of meta/shadow information
8
a += y
z = y * 75
y = x * 1024
w = x + 42
Check w
Check w
Example: Taint Analysis
9
validate(x)
x = read_input()
Clear
a += y
z = y * 75
y = x * 1024
x = read_input()
Propagate
Associate
Input
Check a
Check a
Check z
Check z
Data
Meta-data
Demand-Driven Dataflow Analysis
10
Only Analyze Shadowed Data
Native
Application
Instrumented
Application
Instrumented
Application
Meta-Data Detection
N
o
n
-
S
h
a
d
o
w
e
d
D
a
t
a
S
h
a
d
o
w
e
d
D
a
t
a
N
o
m
e
t
a
-
d
a
t
a
Finding Meta-Data
11
No additional overhead when no meta-data
Needs hardware support
Take a fault when touching shadowed data
Solution: Virtual Memory Watchpoints
V→P
Results by Ho et al.
lmbench Best Case Results:
Results when everything is tainted:
12
Outline
Problem Statement
Background Information
Demand-Driven Dynamic Dataflow Analysis
Proposed Solutions
Demand-Driven Data Race Detection
Sampling to Cap Maximum Overheads
13
Software Data Race Detection
Add checks around every memory access
Find inter-thread sharing events
Synchronization between write-shared
accesses?
No? Data race.
14
Thread 2
mylen=large
Thread 1
mylen=small
if(ptr==NULL)
if(ptr==NULL)
len1=thread_local->mylen;
ptr=malloc(len1);
memcpy(ptr, data1, len1)
len2=thread_local->mylen;
ptr=malloc(len2);
memcpy(ptr, data2, len2)
Example of Data Race Detection
15
ptr write-shared?
TIME
SW Race Detection is Slow
16
Phoenix
PARSEC
Inter-thread Sharing is What’s Important
“
D
a
t
a
r
a
c
e
s
.
.
.
a
r
e
f
a
i
l
u
r
e
s
i
n
p
r
o
g
r
a
m
s
t
h
a
t
a
c
c
e
s
s
a
n
d
u
p
d
a
t
e
s
h
a
r
e
d
d
a
t
a
i
n
c
r
i
t
i
c
a
l
s
e
c
t
i
o
n
s
”
–
N
e
t
z
e
r
&
M
i
l
l
e
r
,
1
9
9
2
17
if(ptr==NULL)
if(ptr==NULL)
len1=thread_local->mylen;
ptr=malloc(len1);
memcpy(ptr, data1, len1)
len2=thread_local->mylen;
ptr=malloc(len2);
Thread-local data
N
O
S
H
A
R
I
N
G
Shared data
N
O
I
N
T
E
R
-
T
H
R
E
A
D
S
H
A
R
I
N
G
E
V
E
N
T
S
TIME
Very Little Inter-Thread Sharing
18
Phoenix
PARSEC
Use Demand-Driven Analysis!
19
Multi-threaded
Application
Software
Race Detector
Software
Race Detector
L
o
c
a
l
A
c
c
e
s
s
I
n
t
e
r
-
t
h
r
e
a
d
s
h
a
r
i
n
g
Inter-thread Sharing Monitor
Finding Inter-thread Sharing
Virtual Memory Watchpoints?
–
~100% of accesses cause page faults
Granularity Gap
Per-process not per-thread
20
I
n
t
e
r
-
T
h
r
e
a
d
S
h
a
r
i
n
g
Hardware Sharing Detector
Hardware Performance Counters
Intel’s HITM event: W→R Data Sharing
21
S
M
S
I
Pipeline
Cache
0
0
0
0
Perf. Ctrs
1
2
1
-1
Core 1
Core 2
-
-
-
-
PEBS
Armed
Debug Store
EFLAGS
EIP
RegVals
MemInfo
Potential Accuracy & Perf. Problems
Limitations of Performance Counters
HITM only finds W→R Data Sharing
Hardware prefetcher events aren’t counted
Limitations of Cache Events
SMT sharing can’t be counted
Cache eviction causes missed events
False sharing, etc…
PEBS events still go through the kernel
22
Demand-Driven Analysis on Real HW
23
Execute
Instruction
SW Race
Detection
Enable
Analysis
Disable
Analysis
HITM
Interrupt?
Sharing
Recently?
Analysis
Enabled?
N
O
N
O
N
O
Y
E
S
Y
E
S
Y
E
S
Performance Increases
24
Phoenix
PARSEC
51x
Demand-Driven Analysis Accuracy
25
1/1
2/4
3/3
4/4
3/3
4/4
4/4
2/4
4/4
4/4
2/4
Accuracy vs.
Continuous Analysis:
97%
Outline
Problem Statement
Background Information
Demand-Driven Dynamic Dataflow Analysis
Proposed Solutions
Demand-Driven Data Race Detection
Sampling to Cap Maximum Overheads
26
Reducing Overheads Further: Sampling
27
Lower overheads by skipping some analyses
Sampling Allows Distribution
28
Developer
Beta Testers
End Users
a += y
z = y * 75
y = x * 1024
w = x + 42
Cannot Naïvely Sample Code
29
Validate(x)
x = read_input()
a += y
y = x * 1024
w = x + 42
validate(x)
x = read_input()
Skip Instr.
Input
Check w
Check w
Check z
Check z
Skip Instr.
Check a
Check a
Sampling must be aware of meta-data
Remove meta-data from skipped dataflows
Prevents false positives
Solution: Sample
Data
, not Code
30
a += y
z = y * 75
y = x * 1024
w = x + 42
Dataflow Sampling Example
31
validate(x)
x = read_input()
a += y
y = x * 1024
x = read_input()
S
k
i
p
D
a
t
a
f
l
o
w
Input
Check w
Check w
Check z
Check z
S
k
i
p
D
a
t
a
f
l
o
w
Check a
Check a
Dataflow Sampling
32
R
e
m
o
v
e
d
a
t
a
f
l
o
w
s
i
f
e
x
e
c
u
t
i
o
n
i
s
t
o
o
s
l
o
w
Sampling Analysis Tool
Instrumented
Application
Native
Application
Instrumented
Application
Meta-Data Detection
M
e
t
a
-
d
a
t
a
C
l
e
a
r
m
e
t
a
-
d
a
t
a
O
H
T
h
r
e
s
h
o
l
d
Prototype Setup
Taint analysis sampling system
Network packets untrusted
Xen-based demand analysis
Whole-system analysis with modified QEMU
Overhead Manager (OHM) is user-controlled
33
Xen Hypervisor
Shadow
Page
Table
Admin VM
Taint
Analysis
QEMU
Net
Stack
OHM
Benchmarks
Performance – Network Throughput
E
x
a
m
p
l
e
:
s
s
h
_
r
e
c
e
i
v
e
Accuracy of Sampling Analysis
R
e
a
l
-
w
o
r
l
d
S
e
c
u
r
i
t
y
E
x
p
l
o
i
t
s
34
ssh_receive
Performance of Dataflow Sampling
35
Throughput
with no analysis
Accuracy with Background Tasks
ssh_receive
running in background
36
BACKUP SLIDES
37
Performance Difference
38
Phoenix
PARSEC
Width Test
39
This talk was given at VMware on December 1, 2011. (Thanks to Jim Chow). This is basically a mix of my CGO 2011 talk along with my ISCA 2011 talk. See those slides for detailed notes of what all the animations mean.
Delve into the world of dynamic software analyses, exploring the prevalence of software errors, modern bug examples, runtime overheads, and proposed solutions in this field. Learn about the complexities of analyzing programs as they run and the associated risks and considerations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Accelerating Dynamic Software Analyses Joseph L. Greathouse Ph.D. Candidate Advanced Computer Architecture Laboratory University of Michigan December 1, 2011
Software Errors Abound NIST: SW errors cost U.S. ~$60 billion/year as of 2002 FBI CCS: Security Issues $67 billion/year as of 2005 > from viruses, network intrusion, etc. Cataloged Software Vulnerabilities 9000 CVE Candidates CERT Vulnerabilities 6000 3000 0 2000 2001 2002 2003 2004 2005 2006 2007 2008 2
Example of a Modern Bug Thread 1 mylen=small Thread 2 mylen=large if(ptr == NULL) { Nov. 2010 OpenSSL Security Flaw len=thread_local->mylen; ptr=malloc(len); memcpy(ptr, data, len); } ptr 3
Example of a Modern Bug Thread 1 mylen=small Thread 2 mylen=large if(ptr==NULL) if(ptr==NULL) len2=thread_local->mylen; ptr=malloc(len2); TIME len1=thread_local->mylen; ptr=malloc(len1); memcpy(ptr, data1, len1) memcpy(ptr, data2, len2) ptr LEAKED 4
Dynamic Software Analysis Analyze the program as it runs + System state, find errors on any executed path LARGE runtime overheads, only test one path Analysis Instrumentation Program Instrumented Program In-House Test Machine(s) Developer Analysis Results LONG run time 5
Runtime Overheads: How Large? Data Race Detection (e.g. Inspector XE) 2-300x Taint Analysis (e.g.TaintCheck) 2-200x Memory Checking (e.g. MemCheck) 5-50x Dynamic Bounds Checking 10-80x Symbolic Execution 10-200x 6
Outline Problem Statement Background Information Demand-Driven Dynamic Dataflow Analysis Proposed Solutions Demand-Driven Data Race Detection Sampling to Cap Maximum Overheads 7
Dynamic Dataflow Analysis Associate meta-data with program values Propagate/Clear meta-data while executing Check meta-data for safety & correctness Forms dataflows of meta/shadow information 8
Example: Taint Analysis Data Input Meta-data Associate x = read_input() Clear validate(x) x = read_input() Propagate y = x * 1024 Check w Check w y = x * 1024 w = x + 42 a += y z = y * 75 Check z Check z a += y z = y * 75 Check a Check a 9
Demand-Driven Dataflow Analysis Only Analyze Shadowed Data Native Application Instrumented Application No meta-data Non- Shadowed Data Shadowed Data Meta-Data Detection 10
Finding Meta-Data No additional overhead when no meta-data Needs hardware support Take a fault when touching shadowed data Solution: Virtual Memory Watchpoints V P FAULT V P 11
Results by Ho et al. lmbench Best Case Results: System Taint Analysis On-Demand Taint Analysis Slowdown (normalized) 101.7x 1.98x Results when everything is tainted: 200 Slowdown (x) 150 100 50 0 netcat_transmit netcat_receive ssh_transmit ssh_receive 12
Outline Problem Statement Background Information Demand-Driven Dynamic Dataflow Analysis Proposed Solutions Demand-Driven Data Race Detection Sampling to Cap Maximum Overheads 13
Software Data Race Detection Add checks around every memory access Find inter-thread sharing events Synchronization between write-shared accesses? No? Data race. 14
Example of Data Race Detection Thread 1 mylen=small if(ptr==NULL) len1=thread_local->mylen; ptr=malloc(len1); memcpy(ptr, data1, len1) Thread 2 mylen=large ptr write-shared? Interleaved Synchronization? TIME if(ptr==NULL) len2=thread_local->mylen; ptr=malloc(len2); memcpy(ptr, data2, len2) 15
SW Race Detection is Slow Phoenix PARSEC 300 Race Detector Slowdown (x) 250 200 150 100 50 0 16
Inter-thread Sharing is Whats Important Data races ... are failures in programs that access and update shared datain critical sections Netzer & Miller, 1992 Thread-local data NO SHARING if(ptr==NULL) len1=thread_local->mylen; ptr=malloc(len1); memcpy(ptr, data1, len1) Shared data NO INTER-THREAD SHARING EVENTS TIME if(ptr==NULL) len2=thread_local->mylen; ptr=malloc(len2); memcpy(ptr, data2, len2) 17
Very Little Inter-Thread Sharing Phoenix PARSEC 3 % Write-Sharing Events 2.5 2 1.5 1 0.5 0 18
Use Demand-Driven Analysis! Multi-threaded Application Software Race Detector Inter-thread Local Access sharing Inter-thread Sharing Monitor 19
Finding Inter-thread Sharing Virtual Memory Watchpoints? Inter-Thread Sharing ~100% of accesses cause page faults FAULT FAULT Granularity Gap Per-process not per-thread 20
Hardware Sharing Detector Hardware Performance Counters Perf. Ctrs 1 2 -1 PEBS Debug Store 0 0 0 0 - - - - EFLAGS EIP RegVals MemInfo Pipeline Armed FAULT 1 Cache Precise Fault Intel s HITM event: W R Data Sharing Core 1 Core 2 S M S I HITM 21
Potential Accuracy & Perf. Problems Limitations of Performance Counters HITM only finds W R Data Sharing Hardware prefetcher events aren t counted Limitations of Cache Events SMT sharing can t be counted Cache eviction causes missed events False sharing, etc PEBS events still go through the kernel 22
Demand-Driven Analysis on Real HW Execute Instruction NO NO Disable Analysis HITM Interrupt? Analysis Enabled? YES YES NO Enable Analysis SW Race Detection Sharing Recently? YES 23
Performance Increases Phoenix 51x PARSEC 20 Demand-driven Analysis 18 16 14 Speedup (x) 12 10 8 6 4 2 0 24
Demand-Driven Analysis Accuracy 1/1 2/4 2/4 2/4 3/3 4/4 4/4 3/3 4/4 4/4 4/4 20 Demand-driven Analysis 18 16 14 Speedup (x) Accuracy vs. Continuous Analysis: 97% 12 10 8 6 4 2 0 25
Outline Problem Statement Background Information Demand-Driven Dynamic Dataflow Analysis Proposed Solutions Demand-Driven Data Race Detection Sampling to Cap Maximum Overheads 26
Reducing Overheads Further: Sampling Lower overheads by skipping some analyses 100 Detection Accuracy (%) 75 Ideal 50 25 0 No Analysis Overhead Complete Analysis 27
Sampling Allows Distribution 100 Detection Accuracy (%) End Users Beta Testers 75 Many users testing at little overhead see more errors than one user at high overhead. Ideal 50 25 Developer 0 Overhead 28
Cannot Navely Sample Code Input validate(x) x = read_input() Validate(x) x = read_input() Skip Instr. False Positive y = x * 1024 w = x + 42 Check w Check w y = x * 1024 w = x + 42 a += y False Negative a += y z = y * 75 Check z Check z Skip Instr. Check a Check a 29
Solution: Sample Data, not Code Sampling must be aware of meta-data Remove meta-data from skipped dataflows Prevents false positives 30
Dataflow Sampling Example Input x = read_input() validate(x) Skip Dataflow x = read_input() y = x * 1024 Check w Check w y = x * 1024 w = x + 42 Skip Dataflow a += y False Negative a += y z = y * 75 Check z Check z Check a Check a 31
Dataflow Sampling Remove dataflows if execution is too slow Sampling Analysis Tool Native Application Instrumented Application Application Instrumented OH Threshold Clear meta-data Meta-Data Detection Meta-data 32
Prototype Setup Taint analysis sampling system Network packets untrusted Xen-based demand analysis Whole-system analysis with modified QEMU Overhead Manager (OHM) is user-controlled Xen Hypervisor Admin VM OS and Applications Shadow Page Table Taint Analysis QEMU App App App Net Stack OHM Linux 33
Benchmarks Performance Network Throughput Example: ssh_receive Accuracy of Sampling Analysis Real-worldSecurity Exploits Name Apache Eggdrop Lynx ProFTPD Heap smashing attack on ProFTPD Server Squid Heap smashing attack on Squid proxy server Error Description Stack overflow in Apache Tomcat JK Connector Stack overflow in Eggdrop IRC bot Stack overflow in Lynx web browser 34
Performance of Dataflow Sampling ssh_receive 25 Throughput with no analysis 20 Throughput (MB/s) 15 10 5 0 0 20 40 60 80 100 Maximum % Time in Analysis 35
Accuracy with Background Tasks ssh_receive running in background 100 % Chance of Detecting Exploit Apache Eggdrop Lynx ProFTPD Squid 80 60 40 20 2 0.7 0.1 0 10% 25% Maximum % Time in Analysis 50% 75% 90% 36
Performance Difference Phoenix PARSEC 300 Race Detector Slowdown (x) 250 200 150 100 50 0 38
Width Test 39
