Transcript PPT

Verifying Architecture
Jaein Jeong
Johnathon Jamison
1
Introduction
Processors are more vulnerable to
transient errors due to small feature
size.
Can detect transient errors with more
stable processors and execute
instructions again if an error occurs.
Overhead won't be high for errors
occurring rarely.
2
Introduction (Cont.)
DIVA: verifies execution each
individual instruction with a second,
slower.
Our idea: a dual-processor verification
system.
Proof-carrying code: A proof of safety
accompanies executable code.
Our idea: executable code is annotated
with invariants.
3
Assumptions
We assume there are no permanent
errors.
Thus we need not worry about
invariants failing always.
So, processor can work correctly if it is
verified by a more stable processor.
4
Assumptions (Cont.)
We assume the processor operates
correctly most of the time.
Therefore it is reasonable to check for
errors rarely.
The overhead is not problematic, for
errors occur rarely.
5
System Structure
 Implemented as two communicating
processors.
 The main processor executes instructions and
sends the verifier all its registers.
 If the verifier confirms the execution, the
main continues to execute instructions.
 Otherwise, the main processor loads the old
register values and re-executes its instructions.
6
System Structure (Cont.)
7
Programming for SimpleScalar
 Since gcc can not handle everything, we
intervene at the assembly code level.
 After changing the assembly code, we compile
it to object code.
 The message passing system calls qread and
qwrite are not implemented in gcc.
 So, we insert the syscall instruction and
pass arguments by explicitly filling registers.
8
Programming for SimpleScalar
(Cont.)

addiu $2,$0,258
la
$4,MQO
subu $5,$16,4
move $6,$0
syscall
Writing a message to a queue
 $L2:
addiu $2,$0,259
la
$4,MQI
addu $5,$sp,16
move $6,$0
syscall
bne
$7,$0,$L2
Reading a message from a queue.
9
Programming interface for C
 Assembly language programming is error
prone and unproductive.
 We wrote a interface for C with macros and
inline assembly.
 Since syscall is not accessible in C, we
generate a “jal syscall” in assembly.
 A Perl script replaces it with “syscall”.
 Now we can compile the assembly code
without further modification.
10
Multiprocessor Program Example
long regs[32];
char msg[]="\006\000\000\000cool\n";
long nullmsg[]={0};
char MQI[]="\003min";
char MQO[]="\004mout";
…
qwrite(MQO,msg,0,error);
do {
qread(length,MQI,regs,0,error);
} while(error);
…
11
Passing Invariants (1st method)
 The main program sends the invariant
instructions as a message.
 We enclosed the invariant instructions
with .rdata and .text directives and
insert the length of the message
after .rdata.
 Then the main can send the instructions
as a message.
 The verifying processor then can load its
registers with it, and do a jal to the
message that was sent.
12
Passing Invariants (2nd method)
 Generate a verifying program specific to the
main program.
 When running the main program, just send
the the contents of registers and the invariant
number.
 The verifying processor takes the invariant
number, calculates the value of the invariant,
and replies.
13
Passing Invariants (Cont.)
 A bit of a problem for the first method.
 The verifying program receives invariant
instructions as data.
 Execution of those instructions would bring
up the same issues as self-modifying code.
 Due to pitfalls of first method, we chose the
second method.
14
Using Invariants
We maintain two sets of registers in the
verifier for roll back purposes.
Not all registers must be sent to the
verifier, just those needed for the
invariant or possible rollback.
Currently, creating the verifier requires
careful inspection of the main program
We hope to automate some of this.
15
Performance
For best performance, the main
processor should not check for the
invariant reply immediately.
Rather, check when the next invariant
is reached, so to give time for
verification.
Then the read is done, and execution is
rolled back or continued as appropriate.
16
Tidbits
The message passing mechanism took
time to understand.
We found we could use the asm
directive in gcc so hand modification of
assembly was minimized.
We encountered a couple bugs in
SimpleScalar.
17
Future Work
Additional logic for floating point
registers, easily extended from what we
have now.
Memory rollback logic; this is more
substantial, for we need to retire
memory writes only on invariant
confirmation.
A program to generate the verifying
program automatically.
18
Thoughts
Seems like this is an energy intensive
method of verification.
Invariants are not easy to generate, and
must be done by hand.
There is a large amount of processing
overhead.
19
Summary
Decreasing feature size makes
verification necessary.
DIVA is on attempt to address the
problem.
We wrote programs for SimpleScalar.
This showed that we can have one
processor verify another with invariants.
20
Acknowledgement
Mark Whitney:
– Our work is based on the SimpleScalar
multiprocessing extension, written by him.
– He also helped us configure SimpleScalar
and fixed bugs.
21