Transcript High-Assurance Transformation System HATS-GUI

A Framework for Verifying High-Assurance
Transformation System
(HATS)
Fares Fraij
December 3, 2003
Outline
•
•
•
•
•
•
•
Introduction
HATS architecture
HATS transformation rules and control strategies
Example of transformation rules
Sandia Secure Processor (SSP)
HATS model in ACL2
Proving properties about the HATS model
Introduction …(1)
• HATS is a language independent program
transformation system
• goal is to perform program transformation in a
provable correct fashion
– HATS transforms target program written in abstract
language to concrete output language (SDT)
– Transformation language program (TLP) consists of
sequence of transformation rules and a control strategy
Introduction …(2)
HATS High-Level Overview
Target
Program in
specification
language
HATS
SDT in an
implementation
language
HATS Architecture
Target file
Target Parser
Parsed target
HATS
Rewriting
Engine
SDT
Prettyprinter
Core Domain
(Grammar, lexer)
Program
Parser
Transformation
language
program
Parsed transformation
language program
User-defined
functions
Output
Text
HATS transformation rules and
control strategies
• Two universal control operators
– Once:
has three arguments:
• Traversal mode
• Identifier whose value is the SDT that is to be transformed
• Identifier whose value is the transformation sequence
– Fix:
Is usually avoided
Example of transformation rules
Transformation rule: (* x (+ y z))  (+ (* x y) (* x z))
*tree0*
*transformed-tree0*
Sandia Secure Processor (SSP)
• class loader (CL) for the SSP is correct if and only if:
source: JVM(C(source))  SSP(CL(C(source)))
– Where:
– Source is the Java source code of an application written in a
subset of Java supported by the SSP
– C is a function denotes a trusted Java compiler
– JVM(x) is the execution of the application x using the virtual
machine JVM
– SSP(x) is the execution of the application x using the SSP
– CL(C(source)) is the ROM image results from applying the class
loader CL to the class files produced by C(source)
HATS model in ACL2
• HATS system is described in terms of :
– state consists of:
•
•
•
•
Input SDT (sdt)
Transformation rules (trnsf)
Control strategy (ctrl)
Program Counter (pc-trnsf) to keep track of the next
transformation to be applied
• PC (pc-tree) to keep track of the candidate node in the SDT
• haltp predicate to determine whether the execution has
reached its end
– state transition: applies the current transformation rules to the
current tree nodes according to the control strategy