Курсы английского
<<  Design Considerations for Directly Imaging Earth-like Exoplanets A hybrid heuristic for an inventory routing problem  >>
Finding Application Errors and Security Flaws Using PQL: A Program
Finding Application Errors and Security Flaws Using PQL: A Program
The Problem
The Problem
Solution: Division of Labor
Solution: Division of Labor
Program Query Language
Program Query Language
System Architecture
System Architecture
Complementary Approaches
Complementary Approaches
Experimental Results
Experimental Results
System Architecture
System Architecture
Running Example: SQL Injection
Running Example: SQL Injection
SQL Injection 1
SQL Injection 1
SQL Injection 2
SQL Injection 2
Essence of Pattern the Same
Essence of Pattern the Same
Translates Directly to PQL
Translates Directly to PQL
Alternation
Alternation
SQL Injection 3
SQL Injection 3
SQL Injection 3
SQL Injection 3
Old Pattern Doesn’t Work
Old Pattern Doesn’t Work
Instance of Tainted Data Problem
Instance of Tainted Data Problem
Pattern Must Catch Derived Strings
Pattern Must Catch Derived Strings
Pattern Must Catch Derived Strings
Pattern Must Catch Derived Strings
Pattern Must Catch Derived Strings
Pattern Must Catch Derived Strings
Derived String Query
Derived String Query
New Main Query
New Main Query
Defending Against Attacks
Defending Against Attacks
Other PQL Constructs
Other PQL Constructs
Expressiveness
Expressiveness
System Architecture
System Architecture
Dynamic Matcher
Dynamic Matcher
Query to Translate
Query to Translate
main() Query Machine
main() Query Machine
derived() Query Machine
derived() Query Machine
Example Program Trace
Example Program Trace
main(): Top Level Match
main(): Top Level Match
derived(): call 1
derived(): call 1
main(): Top Level Match
main(): Top Level Match
derived(): call 1
derived(): call 1
derived(): call 2
derived(): call 2
derived(): call 1
derived(): call 1
main(): Top Level Match
main(): Top Level Match
Find Relevance Fast
Find Relevance Fast
System Architecture
System Architecture
Static Analysis
Static Analysis
Static Analysis
Static Analysis
Static Results
Static Results
System Architecture
System Architecture
Optimizing the Dynamic Analysis
Optimizing the Dynamic Analysis
Experiment Topics
Experiment Topics
Experiment Summary
Experiment Summary
Session Serialization Errors
Session Serialization Errors
SQL Injection
SQL Injection
Full derived() Query
Full derived() Query
Eclipse
Eclipse
Queries on Eclipse
Queries on Eclipse
Eclipse Results
Eclipse Results
Current Status
Current Status
Related work
Related work
Conclusions
Conclusions

Презентация на тему: «Finding Application Errors and Security Flaws Using PQL: A Program Query Language». Автор: Michael Martin. Файл: «Finding Application Errors and Security Flaws Using PQL: A Program Query Language.ppt». Размер zip-архива: 254 КБ.

Finding Application Errors and Security Flaws Using PQL: A Program Query Language

содержание презентации «Finding Application Errors and Security Flaws Using PQL: A Program Query Language.ppt»
СлайдТекст
1 Finding Application Errors and Security Flaws Using PQL: A Program

Finding Application Errors and Security Flaws Using PQL: A Program

Query Language

Michael Martin, Benjamin Livshits, Monica S. Lam Stanford University OOPSLA 2005

2 The Problem

The Problem

Lots of bug-finding research Null dereferences Buffer overruns Data races Many bugs application-specific Misuse of libraries Violation of application logic

3 Solution: Division of Labor

Solution: Division of Labor

Programmer Knows target program Doesn’t know analysis Program Analysis Specialists Knows analysis Doesn’t know specific bugs

Give the programmer a usable analysis

4 Program Query Language

Program Query Language

Queries operate on program traces Sequence of events representing a run Refers to object instances, not variables Events matched may be widely spaced Patterns resemble Java code Like a small matching code snippet No references to compiler internals

5 System Architecture

System Architecture

Question

Program

instrumenter

static analyzer

6 Complementary Approaches

Complementary Approaches

Dynamic analysis: finds matches at run time After a match: Can execute user code Can fix code by replacing instructions Static analysis: finds all possible matches Conservative: can prove lack of match Results can optimize dynamic analysis

7 Experimental Results

Experimental Results

Explored a wide range of PQL queries Bad session stores (API violations) SQL injections (security flaws) Mismatched calls (API violations) Lapsed listeners (memory leaks) Automatically repaired and prevented many bugs at runtime Fixed memory leaks, prevented security flaws Runtime overhead is reasonable Overhead in the 9-125% range Static optimization removed 82-99% of instr. points Found 206 bugs in 6 real-life Java applications Eclipse, popular web applications 60,000 classes combined

8 System Architecture

System Architecture

Question

PQL Query

Program

instrumenter

static analyzer

9 Running Example: SQL Injection

Running Example: SQL Injection

Unvalidated user input passed to a database back-end for execution If SQL in embedded in the input, attacker can take over database Unauthorized data reads Unauthorized data modifications One of the top web security flaws

10 SQL Injection 1

SQL Injection 1

HttpServletRequest req = /* ... */; java.sql.Connection conn = /* ... */; String q = req.getParameter(“QUERY”); conn.execute(q); CALL o1.getParameter(o2) RET o2 CALL o3.execute(o2) RET o4

11 SQL Injection 2

SQL Injection 2

String read() { HttpServletRequest req = /* ... */; return req.getParameter(“QUERY”); } /* ... */ java.sql.Connection conn = /* ... */; conn.execute(read()); CALL read() CALL o1.getParameter(o2) RET o3 RET o3 CALL o4.execute(o3) RET o5

12 Essence of Pattern the Same

Essence of Pattern the Same

The object returned by getParameter is then argument 1 to execute

1 CALL o1.getParameter(o2) 2 RET o3 3 CALL o4.execute(o3) 4 RET o5

1 CALL read() 2 CALL o1.getParameter(o2) 3 RET o3 4 RET o3 5 CALL o4.execute(o3) 6 RET o5

13 Translates Directly to PQL

Translates Directly to PQL

query main() uses String x; matches { x = HttpServletRequest.getParameter(_); Connection.execute(x); } Query variables ? heap objects Instructions need not be adjacent in trace

14 Alternation

Alternation

query main() uses String x; matches { x = HttpServletRequest.getParameter(_) | x = HttpServletRequest.getHeader(_); Connection.execute(x); }

15 SQL Injection 3

SQL Injection 3

HttpServletRequest req = /* ... */; n = getParameter(“NAME”); p = getParameter(“PASSWORD”); conn.execute( “SELECT * FROM logins WHERE name=” + n + “ AND passwd=” + p ); Compiler translates string concatenation into operations on String and StringBuffer objects

16 SQL Injection 3

SQL Injection 3

CALL o1.getParameter(o2) RET o3 CALL o1.getParameter(o4) RET o5 CALL StringBuffer.<init>(o6) RET o7 CALL o7.append(o8) RET o7 CALL o7.append(o3) RET o7 CALL o7.append(o9) RET o7 CALL o7.append(o5) RET o7 CALL o7.toString() RET o10 CALL o11.execute(o10) RET o12

17 Old Pattern Doesn’t Work

Old Pattern Doesn’t Work

CALL o1.getParameter(o2) RET o3 CALL o1.getParameter(o4) RET o5 CALL o11.execute(o10) o10 is neither o3 nor o5, so no match

18 Instance of Tainted Data Problem

Instance of Tainted Data Problem

User-controlled input must be trapped and validated before being passed to database Objects derived from an initial input must also be considered user controlled Generalizes to many security problems: cross-site scripting, path traversal, response splitting, format string attacks...

o1

19 Pattern Must Catch Derived Strings

Pattern Must Catch Derived Strings

CALL o1.getParameter(o2) RET o3 CALL o1.getParameter(o4) RET o5 CALL o7.append(o3) RET o7 CALL o7.append(o9) RET o7 CALL o7.toString() RET o10 CALL o11.execute(o10)

20 Pattern Must Catch Derived Strings

Pattern Must Catch Derived Strings

CALL o1.getParameter(o2) RET o3 CALL o1.getParameter(o4) RET o5 CALL o7.append(o3) RET o7 CALL o7.append(o9) RET o7 CALL o7.toString() RET o10 CALL o11.execute(o10)

21 Pattern Must Catch Derived Strings

Pattern Must Catch Derived Strings

CALL o1.getParameter(o2) RET o3 CALL o1.getParameter(o4) RET o5 CALL o7.append(o3) RET o7 CALL o7.append(o9) RET o7 CALL o7.toString() RET o10 CALL o11.execute(o10)

22 Derived String Query

Derived String Query

query derived (Object x) uses Object temp; returns Object d; matches { { temp.append(x); d := derived(temp); } | { temp = x.toString(); d := derived(temp); } | { d := x; } }

23 New Main Query

New Main Query

query main() uses String x, final; matches { x = HttpServletRequest.getParameter(_) | x = HttpServletRequest.getHeader(_); final := derived(x); Connection.execute(final); }

24 Defending Against Attacks

Defending Against Attacks

query main() uses String x, final; matches { x = HttpServletRequest.getParameter(_) | x = HttpServletRequest.getHeader(_); final := derived(x); } replaces Connection.execute(final) with SQLUtil.safeExecute(x, final); Sanitizes user-derived input Dangerous data cannot reach the database

25 Other PQL Constructs

Other PQL Constructs

Partial order { x.a(), x.b(), x.c(); } Match calls to a, b, and c on x in any order. Forbidden Events Example: double-lock x.lock(); ~x.unlock(); x.lock(); Single statements only

26 Expressiveness

Expressiveness

Concatenation + alternation = Loop-free regexp + Subqueries = CFG + Partial Order = CFG + Intersection Quantified over heap Each subquery independent Existentially quantified

27 System Architecture

System Architecture

Question

Program

PQL Engine

Instrumented Program

instrumenter

static analyzer

28 Dynamic Matcher

Dynamic Matcher

Subquery ? state machine Call to subquery ? new instance of machine States carry “bindings” with them Query variables ? heap objects Bindings are acquired as the variables are referenced for the first time in a match

29 Query to Translate

Query to Translate

query main() uses Object x, final; matches { x = getParameter(_) | x = getHeader(); f := derived (x); execute (f); } query derived(Object x) uses Object t; returns Object y; matches { { y := x; } | { t = x.toString(); y := derived(t); } | { t.append(x); y := derived(t); } }

30 main() Query Machine

main() Query Machine

*

*

x = getParameter(_)

x = getHeader(_)

f := derived(x)

*

execute(f)

?

?

?

?

31 derived() Query Machine

derived() Query Machine

*

*

y := x

?

?

?

t=x.toString()

y := derived(t)

?

?

?

t.append(x)

y := derived(t)

32 Example Program Trace

Example Program Trace

o1 = getHeader(o2) o3.append(o1) o3.append(o4) o5 = execute(o3)

33 main(): Top Level Match

main(): Top Level Match

{ }

*

*

x = getParameter(_)

x = getHeader(_)

{ x=o1 }

{ x=o1 }1

f := derived(x)

*

execute(f)

?

?

?

?

o1 = getHeader(o2)

34 derived(): call 1

derived(): call 1

{x=y=o1}

*

{x=y=o1}

{x=o1}

*

y := x

?

?

?

t=x.toString()

y := derived(t)

?

?

?

t.append(x)

y := derived(t)

o1 = getHeader(o2)

35 main(): Top Level Match

main(): Top Level Match

{ }

*

*

x = getParameter(_)

x = getHeader(_)

{ x=o1 }

{ x=o1 }1

f := derived(x)

{x=o1,f=o1}

*

execute(f)

?

?

?

?

o1 = getHeader(o2)

o3.append(o1)

36 derived(): call 1

derived(): call 1

{x=o1}

{x=y=o1}

*

{x=y=o1}

{x=o1}

{x=o1}

*

{x=o1}

{x=o1, t=o3}2

y := x

?

?

?

t=x.toString()

y := derived(t)

?

?

?

t.append(x)

y := derived(t)

o1 = getHeader(o2) o3.append(o1)

37 derived(): call 2

derived(): call 2

{x=y=o3}

*

{x=y=o3}

{x=o3}

*

y := x

?

?

?

t=x.toString()

y := derived(t)

?

?

?

t.append(x)

y := derived(t)

o1 = getHeader(o2) o3.append(o1)

38 derived(): call 1

derived(): call 1

{x=y=o1}

{x=o1}

{x=o1, y=t=o3}

{x=y=o1}

*

{x=o1}

{x=o1}

*

{x=o1}

{x=o1, t=o3}2

{x=o1, y=t=o3}

y := x

?

?

?

t=x.toString()

y := derived(t)

?

?

?

t.append(x)

y := derived(t)

o1 = getHeader(o2) o3.append(o1)

39 main(): Top Level Match

main(): Top Level Match

{ }

*

*

x = getParameter(_)

x = getHeader(_)

{ x=o1 }

{ x=o1 }1

f := derived(x)

{x=o1,f=o1}

, {x=o1,f=o3}

*

execute(f)

{x=o1,f=o3}

?

?

?

?

o1 = getHeader(o2)

o3.append(o1)

o3.append(o4)

o5 = execute(o3)

40 Find Relevance Fast

Find Relevance Fast

Hash map for each transition Every call-instance combined Key on known-used variables All used variables known-used ? one lookup per transition

41 System Architecture

System Architecture

Question

Program

PQL Engine

Static Results

instrumenter

static analyzer

42 Static Analysis

Static Analysis

“Can this program match this query?” Undecidable in general We give a conservative approximation No matches found = None possible

43 Static Analysis

Static Analysis

PQL query automatically translated to query on pointer analysis results Pointer analysis is sound and context-sensitive 1014 contexts in a good-sized application Exponential space represented with BDDs Analyses given in Datalog Whaley/Lam, PLDI 2004 (bddbddb) for details

44 Static Results

Static Results

Sets of objects and events that could represent a match OR Program points that could participate in a match No results = no match possible!

45 System Architecture

System Architecture

Question

Program

Optimized Instrumented Program

instrumenter

static analyzer

46 Optimizing the Dynamic Analysis

Optimizing the Dynamic Analysis

Static results conservative So, point not in result ? point never in any match So, no need to instrument Usually more than 90% reduction

47 Experiment Topics

Experiment Topics

Domain of Java Web applications Serialization errors SQL injection Domain of Eclipse IDE plugins API violations Memory leaks

48 Experiment Summary

Experiment Summary

Name

Classes

Inst Pts

Bugs

webgoat

1,021

69

2

personalblog

5,236

36

2

road2hibernate

7,062

779

1

snipsnap

10,851

543

8

roller

16,359

0

1

Eclipse

19,439

18,152

192

TOTAL

59,968

19,579

206

49 Session Serialization Errors

Session Serialization Errors

Very common bug in Web applications Server tries to persist non-persistent objects Only manifests under heavy load Hard to find with testing One-line query in PQL HttpSession.setAttribute(_,!Serializable); Solvable purely statically Dynamic confirmation possible

50 SQL Injection

SQL Injection

Our running example Static optimizes greatly 92%-99.8% reduction of points 2-3x speedup 4 injections, 2 exploitable Blocked both exploits Further applications and an improved static analysis in Usenix Security ’05

51 Full derived() Query

Full derived() Query

query derived (Object x) returns Object y; uses Object temp; matches { y := x | { temp = StringProp(x); y := derived(temp); } }

query StringProp (Object * x) returns Object y; uses Object z; matches { y.append(x, ...) | x.getChars(_, _, y, _) | y.insert(_, x) | y.replace(_, _, x) | y = x.substring(...) | y = new java.lang.String(x) | y = new java.lang.StringBuffer(x) | y = x.toString() | y = x.getBytes(...) | y = _.copyValueOf(x) | y = x.concat(_) | y = _.concat(x) | y = new java.util.StringTokenizer(x) | y = x.nextToken() | y = x.next() | y = new java.lang.Number(x) | y = x.trim() | { z = x.split(...); y = z[]; } | y = x.toLowerCase(...) | y = x.toUpperCase(...) | y = _.replaceAll(_, x) | y = _.replaceFirst(_, x); }

52 Eclipse

Eclipse

IDE for Java Very large (tens of MB of bytecode) Too large for our static analysis Purely interactive Unoptimized dynamic overhead acceptable

53 Queries on Eclipse

Queries on Eclipse

Paired Methods register/deregister createWidget/destroyWidget install/uninstall startup/shutdown Lapsed Listeners

54 Eclipse Results

Eclipse Results

All paired methods queries were run simultaneously 56 mismatches detected Lapsed listener query was run alone 136 lapsed listeners Can be automatically fixed

55 Current Status

Current Status

Open source and hosted on SourceForge http://pql.sf.net – standalone dynamic implementation

56 Related work

Related work

PQL is a query language JQuery on program traces Partiqle, Dalek, ... Observing behavior and finding bugs Metal, Daikon, PREfix, Clouseau, ... and automatically add code to fix them AspectJ

57 Conclusions

Conclusions

PQL – a Program Query Language Match histories of sets of objects on a program trace Targeting application developers Found many bugs 206 application bugs and security flaws 6 large real-life applications PQL provides a bridge to powerful analyses Dynamic matcher Point-and-shoot even for unknown applications Automatically repairs program on the fly Static matcher Proves absence of bugs Can reduce runtime overhead to production-acceptable

«Finding Application Errors and Security Flaws Using PQL: A Program Query Language»
http://900igr.net/prezentacija/anglijskij-jazyk/finding-application-errors-and-security-flaws-using-pql-a-program-query-language-186592.html
cсылка на страницу
Урок

Английский язык

29 тем
Слайды
900igr.net > Презентации по английскому языку > Курсы английского > Finding Application Errors and Security Flaws Using PQL: A Program Query Language