Transcript Lightweight Modeling of the Java Virtual Machine's

Lightweight Modeling of Java
Virtual Machine Security
Constraints using Alloy
Mark Reynolds
BU CS511 Midterm Report
March 26, 2008
Outline
•
•
•
•
Motivation
The Model
Results
Future Work
Motivation
• Java enforces its security restrictions in
three ways:
– Compile time
– Load time (the Bytecode Verifier)
– Runtime
• Runtime type checks
• Array bounds checks
• SecurityManager checks
• How good are these checks?
A Long History of Java Exploits
• Edward Felten’s applet attacks (1997)
– “Securing Java” McGraw & Felten
• “Last Stage of Delirium” (Polish hacker
group) (2002)
– Extensive collection of exploit techniques
• Defects continue to be found
– Search for “jre” or “jdk” on http://cve.mitre.org
• Almost all defects are in the Bytecode
Verifier
The Bytecode Verifier
• Operates on binary class files
– “JVM assembly language”
• Performs a superset of the set of checks
performed by the Java compiler
• Uses a constraint based approach
–
–
–
–
–
Local variable constraint
Stack depth invariance constraint
Opcode constraint
Method argument constraint
Many others
Local Variable Constraint
• Every JVM local variable is written before
it is read
• In the JVM implementation local variables
are completely separate from the stack,
unlike most other architectures (e.g. x86)
• Goal: write an Alloy model that can
operate on a representation of method
bytecode and check the local variable
constraint
An Example in Java
public int fred(int input) {
int tmp;
if ( input < 10 )
tmp = input*5;
else
tmp = input;
return tmp;
}
An Incorrect Variant
public int fred(int input) {
int tmp;
if ( input < 10 )
/* tmp = input*5; */ {}
else
tmp = input;
return tmp;
}
Bytecodes for Correct Variant
// 0 0:iload_1
// 1 1:bipush 10
// 2 3:icmpge 13
// 3 6:iload_1
// 4 7:iconst_5
// 5 8:imul
// 6 9:istore_2
// 7 10:goto 15
// 8 13:iload_1
// 9 14:istore_2
// 10 15:iload_2
// 11 16:ireturn
Bytecodes for Incorrect Variant
// 0 0:iload_1
// 1 1:bipush 10
// 2 3:icmpge 13
// 3 6:iload_1
// 4 7:iconst_5
// 5 8:imul
// 6 9:nop // removed the “unnecessary” write to LV2
// 7 10:goto 15
// 8 13:iload_1
// 9 14:istore_2
// 10 15:iload_2
// 11 16:ireturn
The Model
• Define the relations on a sig Instruction:
– map: Int
– len: Int
– r: set Int
– w: set Int
– ubt: lone Int
– cbt: lone Int
– term: lone Int
Relations in the Model
map – byte offset of this instruction from start of
method
len – byte length of instruction
r, w – sets of local variables read/written by the
instruction
ubt – unconditional branch targets for this
instruction (e.g. goto)
cbt – conditional branch targets for this instruction
(e.g. icmpge 13)
term – does this instruction terminate the method
(e.g. ireturn)
Model Construction
Java
Alloy
Declarations
Class File
Class2Alloy
Translator
Method name
Initialization
Body
Facts
Predicates
Assertions
Example Initialization
one sig startup, iload_1a, bipush, icmpge, iload_1b, iconst, imul, istore_2a, goto, iload_1c, istore_2b, iload_2,
ireturn extends Instruction {}
fact maps {
map = startup->(-1) + iload_1a->0 + bipush->1 + icmpge->3 + iload_1b->6 + iconst->7 + imul->8 + istore_2a->9 +
goto->10 + iload_1c->13 + istore_2b->14 + iload_2->15 + ireturn->16
}
fact terms {
term = ireturn->1 }
fact lens {
len = startup->1 + iload_1a->1 + bipush->2 + icmpge->3 + iload_1b->1 + iconst->1 + imul->1 + istore_2a->1 +
goto->3 + iload_1c->1 + istore_2b->1 + iload_2->1 + ireturn->1
}
fact rs {
r = iload_1a->1 + iload_1b->1 + iload_1c->1 + iload_2->2 }
fact ws {
w = startup->0 + startup->1 + istore_2a->2 + istore_2b->2 }
fact ubts {
ubt = goto->15 }
fact cbts {
cbt = icmpge->13 }
Relations as a table
startup
iload_1
bipush
icmpge
iload_1
iconst_5
imul
istore_2
goto
iload_1
istore_2
iload_2
ireturn
10
13
15
map
-1
0
1
3
6
7
8
9
10
13
14
15
16
len
1
1
2
3
1
1
1
1
3
1
1
1
1
r
w
0,1
term
ubt
cbt
1
13
1
2
15
1
2
2
1
Model Execution
• Must simulation operation of the JVM
• “startup” instruction simulates method entry
– Stores “this” and method arguments into local variables 0, 1, …
• Use ordering module on State sig to keep track of
readers and writers
• “nextInstruction” predicate uses the following algorithm:
– If there is an unconditional branch take it
– Otherwise, form the set {conditional branches} U next-instruction
and choose a member of that set
• “solve” predicate checks that execution terminated
(reached an instruction with non-null value of “term”)
• “checkit” assertion checks that the set of readers is a
subset of the set of writers for all states
Key Components
sig State {
prog: Instruction,
readers: set Int,
writers: set Int
}
pred nextInstruction[from, to: Instruction] {
some from.ubt =>
( to.map = from.ubt ) else
( ( to.map = add[from.map, from.len] ) ||
some bt: from.cbt { to.map = bt } )
}
pred solve {
some finalState : State | finalState.prog.term = 1
}
assert checkit {
all s: State | s.readers in s.writers
}
Results
• Local variable constraint satisfied => no
counterexample to “checkit”, instance of
“solve” found (jvm.als)
• Local variable constraint violated =>
counterexample of “checkit” found
(badjvm.als)
• Website: http://cs-people.bu.edu/markreyn
Future Work
• Use cbt relation for try .. catch blocks
• Add stack depth invariance constraint
• Add opcode constraint