1 | \documentclass{llncs} |
---|
2 | |
---|
3 | \usepackage{amsfonts} |
---|
4 | \usepackage{amsmath} |
---|
5 | \usepackage{amssymb} |
---|
6 | \usepackage[english]{babel} |
---|
7 | \usepackage{color} |
---|
8 | \usepackage{fancybox} |
---|
9 | \usepackage{graphicx} |
---|
10 | \usepackage[colorlinks]{hyperref} |
---|
11 | \usepackage{hyphenat} |
---|
12 | \usepackage[utf8x]{inputenc} |
---|
13 | \usepackage{listings} |
---|
14 | \usepackage{mdwlist} |
---|
15 | \usepackage{microtype} |
---|
16 | \usepackage{stmaryrd} |
---|
17 | \usepackage{url} |
---|
18 | |
---|
19 | \renewcommand{\verb}{\lstinline} |
---|
20 | \def\lstlanguagefiles{lst-grafite.tex} |
---|
21 | \lstset{language=Grafite} |
---|
22 | |
---|
23 | \newlength{\mylength} |
---|
24 | \newenvironment{frametxt}% |
---|
25 | {\setlength{\fboxsep}{5pt} |
---|
26 | \setlength{\mylength}{\linewidth}% |
---|
27 | \addtolength{\mylength}{-2\fboxsep}% |
---|
28 | \addtolength{\mylength}{-2\fboxrule}% |
---|
29 | \Sbox |
---|
30 | \minipage{\mylength}% |
---|
31 | \setlength{\abovedisplayskip}{0pt}% |
---|
32 | \setlength{\belowdisplayskip}{0pt}% |
---|
33 | }% |
---|
34 | {\endminipage\endSbox |
---|
35 | \[\fbox{\TheSbox}\]} |
---|
36 | |
---|
37 | \title{On the correctness of an assembler for the Intel MCS-51 microprocessor} |
---|
38 | \author{Dominic P. Mulligan \and Claudio Sacerdoti Coen} |
---|
39 | \institute{Dipartimento di Scienze dell'Informazione, Universit\'a di Bologna} |
---|
40 | |
---|
41 | \bibliographystyle{splncs03} |
---|
42 | |
---|
43 | \begin{document} |
---|
44 | |
---|
45 | \maketitle |
---|
46 | |
---|
47 | \begin{abstract} |
---|
48 | We consider the formalisation of an assembler for Intel MCS-51 assembly language in the Matita proof assistant. |
---|
49 | This formalisation forms a major component of the EU-funded CerCo project, concering the construction and formalisation of a concrete complexity preserving compiler for a large subset of the C programming language. |
---|
50 | |
---|
51 | The efficient expansion of pseudoinstructions---particularly jumps---into MCS-51 machine instructions is complex. |
---|
52 | We employ a strategy, involving the use of `policies', that separates the decision making over how jumps should be expanded from the expansion process itself. |
---|
53 | This makes the proof of correctness for the assembler significantly more straightforward. |
---|
54 | |
---|
55 | We prove, under the assumption of the existence of a correct policy, that the assembly process preserves the semantics of assembly programs. |
---|
56 | Correct policies fail to exist only in a limited number of pathological circumstances. |
---|
57 | \end{abstract} |
---|
58 | |
---|
59 | % ---------------------------------------------------------------------------- % |
---|
60 | % SECTION % |
---|
61 | % ---------------------------------------------------------------------------- % |
---|
62 | \section{Introduction} |
---|
63 | \label{sect.introduction} |
---|
64 | |
---|
65 | We consider the formalisation of an assembler for the Intel MCS-51 8-bit microprocessor in the Matita proof assistant~\cite{asperti:user:2007}. |
---|
66 | This formalisation forms a major component of the EU-funded CerCo project~\cite{cerco:2011}, concering the construction and formalisation of a concrete complexity preserving compiler for a large subset of the C programming language. |
---|
67 | |
---|
68 | The MCS-51 dates from the early 1980s and commonly called the 8051/8052. |
---|
69 | Despite the microprocessor's age, derivatives are still widely manufactured by a number of semiconductor foundries. |
---|
70 | As a result the processor is widely used, especially in embedded systems development, where well-tested, cheap, predictable microprocessors find their niche. |
---|
71 | |
---|
72 | The MCS-51 has a relative paucity of features compared to its more modern brethren. |
---|
73 | In particular, the MCS-51 does not possess a cache or any instruction pipelining that would make predicting the concrete cost of executing a single instruction an involved process. |
---|
74 | Instead, each semiconductor foundry that produces an MCS-51 derivative is able to provide accurate timing information in clock cycles for each instruction in their derivative's instruction set. |
---|
75 | It is important to stress that this timing information, unlike in more sophisticated processors, is not an estimate, it is a definition. |
---|
76 | For the MCS-51, if a manufacturer states that a particular opcode takes three clock cycles to execute, then that opcode \emph{always} takes three clock cycles to execute. |
---|
77 | |
---|
78 | This predicability of timing information is especially attractive to the CerCo consortium. |
---|
79 | We are in the process of constructing a certified, concrete complexity compiler for a realistic processor, and not for building and formalising the worst case execution time (WCET) tools that would be necessary to achieve the same result with, for example, a modern ARM or PowerPC microprocessor. |
---|
80 | |
---|
81 | However, the MCS-51's paucity of features is a double edged sword. |
---|
82 | In particular, the MCS-51 features relatively miniscule memory spaces (including read-only code memory, stack and internal/external random access memory) by modern standards. |
---|
83 | As a result our compiler, to have any sort of hope of successfully compiling realistic C programs, ought to produce `tight' machine code. |
---|
84 | This is not simple. |
---|
85 | |
---|
86 | We here focus on a single issue in the MCS-51's instruction set: unconditional jumps. |
---|
87 | The MCS-51 features three conditional jump instructions: \texttt{LJMP} and \texttt{SJMP}---`long jump' and `short jump' respectively---and an 11-bit oddity of the MCS-51, \texttt{AJMP}, that the prototype CerCo compiler~\cite{cerco-report-code:2011} ignores for simplicity's sake.\footnote{Ignoring \texttt{AJMP} and its analogue \texttt{ACALL} is not idiosyncratic. The Small Device C Compiler (SDCC)~\cite{sdcc:2011}, the leading open source C compiler for the MCS-51, also seemingly does not produce \texttt{AJMP} and \texttt{ACALL} instructions. Their utility in a modern context remains unclear.} |
---|
88 | Each of these three instructions expects arguments in different sizes and behaves in different ways. |
---|
89 | \texttt{SJMP} may only perform a `local jump' whereas \texttt{LJMP} may jump to any address in the MCS-51's memory space. |
---|
90 | Consequently, the size of each opcode is different, and to squeeze as much code as possible into the MCS-51's limited code memory, the smallest possible opcode should be selected. |
---|
91 | |
---|
92 | The prototype CerCo C compiler does not attempt to select the smallest jump opcode in this manner, as this was thought to unneccessarily complicate the compilation chain. |
---|
93 | Instead, the compiler targets an assembly language, complete with pseudoinstructions including bespoke \texttt{Jmp} and \texttt{Call} instructions. |
---|
94 | Labels, conditional jumps to labels, a program preamble containing global data and a \texttt{MOV} instruction for moving this global data into the MCS-51's one 16-bit register also feature. |
---|
95 | This latter feature will ease any later consideration of separate compilation in the CerCo compiler. |
---|
96 | An assembler is used to expand pseudoinstructions into MCS-51 machine code. |
---|
97 | |
---|
98 | However, this assembly process is not trivial, for numerous reasons. |
---|
99 | For example, our conditional jumps to labels behave differently from their machine code counterparts. |
---|
100 | At the machine code level, conditional jumps may only jump to a relative offset, expressed in a byte, of the current program counter, limiting their range. |
---|
101 | However, at the assembly level, conditional jumps may jump to a label that appears anywhere in the program, significantly liberalising the use of conditional jumps and further simplifying the design of the CerCo compiler. |
---|
102 | |
---|
103 | Further, trying to na\"ively relate assembly programs with their machine code counterparts simply does not work. |
---|
104 | Machine code programs that fetch from code memory and programs that combine the program counter with constant shifts do not make sense at the assembly level. |
---|
105 | More generally, memory addresses can only be compared with other memory addresses. |
---|
106 | However, checking that memory addresses are only compared against each other at the assembly level is in fact undecidable. |
---|
107 | In short, the full preservation of the semantics of the two languages is impossible. |
---|
108 | |
---|
109 | Yet more complications are added by the peculiarities of the CerCo project itself. |
---|
110 | As mentioned, the CerCo consortium is in the business of constructing a verified compiler for the C programming language. |
---|
111 | However, unlike CompCert~\cite{compcert:2011,leroy:formal:2009,leroy:formally:2009}---which currently represents the state of the art for `industrial grade' verified compilers---CerCo considers not just the \emph{intensional correctness} of the compiler, but also its \emph{extensional correctness}. |
---|
112 | That is, CompCert focusses solely on the preservation of the \emph{meaning} of a program during the compilation process, guaranteeing that the program's meaning does not change as it is gradually transformed into assembly code. |
---|
113 | However in any realistic compiler (even the CompCert compiler!) there is no guarantee that the program's time properties are preserved during the compilation process; a compiler's `optimisations' could, in theory, even conspire to degrade the concrete complexity of certain classes of programs. |
---|
114 | CerCo aims to expand the current state of the art by producing a compiler where this temporal degradation is guaranteed not to happen. |
---|
115 | |
---|
116 | In order to achieve this CerCo imposes a cost model on programs, or more specifically, on simple blocks of instructions. |
---|
117 | This cost model is induced by the compilation process itself, and its non-compositional nature allows us to assign different costs to identical blocks of instructions depending on how they are compiled. |
---|
118 | In short, we aim to obtain a very precise costing for a program by embracing the compilation process, not ignoring it. |
---|
119 | This, however, complicates the proof of correctness for the compiler proper: for every translation pass from intermediate language to intermediate language, we must prove that not only has the meaning of a program been preserved, but also its complexity characteristics. |
---|
120 | This also applies for the translation from assembly language to machine code. |
---|
121 | |
---|
122 | How do we assign a cost to a pseudoinstruction? |
---|
123 | As mentioned, conditional jumps at the assembly level can jump to a label appearing anywhere in the program. |
---|
124 | However, at the machine code level, conditional jumps are limited to jumping `locally', using a measly byte offset. |
---|
125 | To translate a jump to a label, a single conditional jump pseudoinstruction may be translated into a block of three real instructions, as follows (here, \texttt{JZ} is `jump if accumulator is zero'): |
---|
126 | \begin{displaymath} |
---|
127 | \begin{array}{r@{\quad}l@{\;\;}l@{\qquad}c@{\qquad}l@{\;\;}l} |
---|
128 | & \mathtt{JZ} & label & & \mathtt{JZ} & \text{size of \texttt{SJMP} instruction} \\ |
---|
129 | & \ldots & & \text{translates to} & \mathtt{SJMP} & \text{size of \texttt{LJMP} instruction} \\ |
---|
130 | label: & \mathtt{MOV} & \mathtt{A}\;\;\mathtt{B} & \Longrightarrow & \mathtt{LJMP} & \text{address of \textit{label}} \\ |
---|
131 | & & & & \ldots & \\ |
---|
132 | & & & & \mathtt{MOV} & \mathtt{A}\;\;\mathtt{B} |
---|
133 | \end{array} |
---|
134 | \end{displaymath} |
---|
135 | In the translation, if \texttt{JZ} fails, we fall through to the \texttt{SJMP} which jumps over the \texttt{LJMP}. |
---|
136 | Naturally, if \textit{label} is close enough, a conditional jump pseudoinstruction is mapped directly to a conditional jump machine instruction; the above translation only applies if \textit{label} is not sufficiently local. |
---|
137 | This leaves the problem, addressed below, of calculating whether a label is indeed `close enough' for the simpler translation to be used. |
---|
138 | |
---|
139 | Crucially, the above translation demonstrates the difficulty in predicting how many clock cycles a pseudoinstruction will take to execute. |
---|
140 | A conditional jump may be mapped to a single machine instruction or a block of three. |
---|
141 | Perhaps more insidious, the number of cycles needed to execute the instructions in the two branches of a translated conditional jump may be different. |
---|
142 | Depending on the particular MCS-51 derivative at hand, an \texttt{SJMP} could in theory take a different number of clock cycles to execute than an \texttt{LJMP}. |
---|
143 | These issues must also be dealt with in order to prove that the translation pass preserves the concrete complexity of the code. |
---|
144 | |
---|
145 | The question remains: how do we decide whether to expand a jump into an \texttt{SJMP} or an \texttt{LJMP}? |
---|
146 | To understand why this problem is not trivial, consider the following snippet of assembly code: |
---|
147 | \begin{displaymath} |
---|
148 | \text{dpm: finish me} |
---|
149 | \end{displaymath} |
---|
150 | |
---|
151 | As our example shows, given an occurence $l$ of an \texttt{LJMP} instruction, it may be possible to shrink $l$ to an occurence of an \texttt{SJMP} providing we can shrink any \texttt{LJMP}s that exist between $l$ and its target location. |
---|
152 | However, shrinking these \texttt{LJMP}s may in turn depend on shrinking $l$ to an \texttt{SJMP}, as it is perfectly possible to jump backwards. |
---|
153 | In short, unless we can somehow break this loop of circularity, and similar knotty configurations of jumps, we are stuck with a suboptimal solution to the expanding jumps problem. |
---|
154 | |
---|
155 | How we went about resolving this problem affected the shape of our proof of correctness for the whole assembler in a rather profound way. |
---|
156 | We first attempted to synthesize a solution bottom up: starting with no solution, we gradually refine a solution using the same functions that implement the jump expansion. |
---|
157 | Using this technique, solutions can fail to exist, and the proof quickly descends into a diabolical quagmire. |
---|
158 | |
---|
159 | Abandoning this attempt, we instead split the `policy'---the decision over how any particular jump should be expanded---from the implementation that actually expands assembly programs into machine code. |
---|
160 | Assuming the existence of a correct policy, we proved the implementation of the assembler correct. |
---|
161 | Further, we proved that the assembler fails to assemble an assembly program if and only if a correct policy does not exist. |
---|
162 | Policies do not exist in only a limited number of circumstances: namely, if a pseudoinstruction attempts to jump to a label that does not exist, or the program is too large to fit in code memory. |
---|
163 | The first case would constitute a serious compiler error, and hopefully certifying the rest of the compiler would rule this possibility out. |
---|
164 | The second case is unavoidable---certified compiler or not, trying to load a huge program into a small code memory will break \emph{something}. |
---|
165 | |
---|
166 | The rest of this paper is a detailed description of this proof. |
---|
167 | |
---|
168 | % ---------------------------------------------------------------------------- % |
---|
169 | % SECTION % |
---|
170 | % ---------------------------------------------------------------------------- % |
---|
171 | \subsection{Overview of the paper} |
---|
172 | \label{subsect.overview.of.the.paper} |
---|
173 | In Section~\ref{sect.matita} we provide a brief overview of the Matita proof assistant for the unfamiliar reader. |
---|
174 | In Section~\ref{sect.the.proof} we discuss the design and implementation of the proof proper. |
---|
175 | In Section~\ref{sect.conclusions} we conclude. |
---|
176 | |
---|
177 | % ---------------------------------------------------------------------------- % |
---|
178 | % SECTION % |
---|
179 | % ---------------------------------------------------------------------------- % |
---|
180 | \section{Matita} |
---|
181 | \label{sect.matita} |
---|
182 | |
---|
183 | Matita is a proof assistant based on the (Co)inductive Calculus of Constructions~\cite{asperti:user:2007}. |
---|
184 | For those familiar with Coq, Matita's syntax and mode of operation should be entirely familiar. |
---|
185 | We take time here to explain one of Matita's syntactic idiosyncracies, however. |
---|
186 | The use of `$\mathtt{?}$' or `$\mathtt{\ldots}$' in an argument position denotes a type or types to be inferred automatically by unification respectively. |
---|
187 | The use of `$\mathtt{?}$' in the body of a definition, lemma or axiom denotes an incomplete term that is to be closed, by hand, using tactics. |
---|
188 | |
---|
189 | % ---------------------------------------------------------------------------- % |
---|
190 | % SECTION % |
---|
191 | % ---------------------------------------------------------------------------- % |
---|
192 | \section{The proof} |
---|
193 | \label{sect.the.proof} |
---|
194 | |
---|
195 | \subsection{The assembler and semantics of machine code} |
---|
196 | \label{subsect.the.assembler.and.semantics.of.machine.code} |
---|
197 | |
---|
198 | The formalisation in Matita of the semantics of MCS-51 machine code is described in~\cite{mulligan:executable:2011}. |
---|
199 | We merely describe enough here to understand the rest of the proof. |
---|
200 | |
---|
201 | At heart, the MCS-51 emulator centres around a \texttt{Status} record, describing the current state of the microprocessor. |
---|
202 | This record contains fields corresponding to the microprocessor's program counter, special function registers, and so on. |
---|
203 | At the machine code level, code memory is implemented as a trie of bytes, addressed by the program counter. |
---|
204 | Machine code programs are loaded into \texttt{Status} using the \texttt{load\_code\_memory} function. |
---|
205 | |
---|
206 | We may execut a single step of a machine code program using the \texttt{execute\_1} function, which returns an updated \texttt{Status}: |
---|
207 | \begin{lstlisting} |
---|
208 | definition execute_1: Status $\rightarrow$ Status := $\ldots$ |
---|
209 | \end{lstlisting} |
---|
210 | The function \texttt{execute} allows one to execute an arbitrary, but fixed (due to Matita's normalisation requirement!) number of steps of a program. |
---|
211 | |
---|
212 | Naturally, assembly programs have analogues. |
---|
213 | The counterpart of the \texttt{Status} record is \texttt{PseudoStatus}. |
---|
214 | Instead of code memory being implemented as tries of bytes, code memory is here implemented as lists of pseudoinstructions, and program counters are merely indices into this list. |
---|
215 | Our analogue of \texttt{execute\_1} is \texttt{execute\_1\_pseudo\_instruction}: |
---|
216 | \begin{lstlisting} |
---|
217 | definition execute_1_pseudo_instruction: (Word $\rightarrow$ nat $\times$ nat) $\rightarrow$ |
---|
218 | PseudoStatus $\rightarrow$ PseudoStatus := $\ldots$ |
---|
219 | \end{lstlisting} |
---|
220 | Notice, here, that the emulation function for assembly programs takes an additional argument. |
---|
221 | This is a function that maps program counters (at the assembly level) to pairs of natural numbers representing the number of clock ticks that the pseudoinstruction needs to execute, post expansion. |
---|
222 | We call this function a \emph{costing}, and note that the costing is induced by the particular strategy we use to expand pseudoinstructions. |
---|
223 | If we change how we expand conditional jumps to labels, for instance, then the costing needs to change, hence \texttt{execute\_1\_pseudo\_instruction}'s parametricity in the costing. |
---|
224 | |
---|
225 | The costing returns \emph{pairs} of natural numbers because, in the case of expanding conditional jumps to labels, the expansion of the `true branch' and `false branch' may differ in the number of clock ticks needed for execution. |
---|
226 | This timing information is used inside \texttt{execute\_1\_pseudo\_instruction} to update the clock of the \texttt{PseudoStatus}. |
---|
227 | During the proof of correctness of the assembler we relate the clocks of \texttt{Status}es and \texttt{PseudoStatus}es. |
---|
228 | |
---|
229 | The assembler, mapping programs consisting of lists of pseudoinstructions to lists of bytes, operates in a mostly straightforward manner. |
---|
230 | To a degree of approximation, the assembler on an assembly program, consisting of $n$ pseudoinstructions $\mathtt{P_i}$ for $1 \leq i \leq n$, works as in the following diagram: |
---|
231 | \begin{displaymath} |
---|
232 | [\mathtt{P_1}, \ldots \mathtt{P_n}] \xrightarrow{\mathtt{flatten}\left(\mathtt{P_i} \xrightarrow{\mbox{\fontsize{7}{9}\selectfont$\mathtt{expand}$}} \mathtt{[I_1^i, \ldots I^q_i]} \xrightarrow{\mbox{\fontsize{7}{9}\selectfont$\mathtt{assembly1}^*$}} \mathtt{[0110]}\right)^{*}} \mathtt{[010101]} |
---|
233 | \end{displaymath} |
---|
234 | Here $\mathtt{I^i_j}$ for $1 \leq j \leq q$ are the $q$ machine code instructions obtained by expanding, with \texttt{expand\_pseudo\_instruction}, a single pseudoinstruction. |
---|
235 | Each machine code instruction $\mathtt{I^i_j}$ is then assembled, using the \texttt{assembly1} function, into a list of bytes. |
---|
236 | This process is iterated for each pseudoinstruction, before the lists are flattened into a single bit list representation of the original assembly program. |
---|
237 | |
---|
238 | By inspecting the above diagram, it would appear that the best way to proceed with a proof that the assembly process does not change the semantics of an assembly program is via a decomposition of the problem into two subproblems. |
---|
239 | Namely, we first expand any and all pseudoinstructions into lists of machine instructions, and provide a proof that this process does not change our program's semantics. |
---|
240 | Finally, we assemble all machine code instructions into machine code---lists of bytes---and prove once more that this process does not have an adverse effect on a program's semantics. |
---|
241 | By composition, we then have that the whole assembly process is semantics preserving. |
---|
242 | |
---|
243 | This is a tempting approach to the proof, but ultimately the wrong approach. |
---|
244 | In particular, it is important that we track how the program counter indexing into the assembly program, and the machine's program counter evolve, so that we can relate them. |
---|
245 | Expanding pseudoinstructions requires that the machine's program counter be incremented by $n$ steps, for $1 \leq n$, for every increment of the assembly program's program counter. |
---|
246 | Keeping track of the correspondence between the two program counters quickly becomes unfeasible using a compositional approach, and hence the proof must be monolithic. |
---|
247 | |
---|
248 | % ---------------------------------------------------------------------------- % |
---|
249 | % SECTION % |
---|
250 | % ---------------------------------------------------------------------------- % |
---|
251 | \subsection{Policies} |
---|
252 | \label{subsect.policies} |
---|
253 | |
---|
254 | Policies exist to dictate how conditional and unconditional jumps at the assembly level should be expanded into machine code instructions. |
---|
255 | Using policies, we are able to completely decouple the decision over how jumps are expanded with the act of expansion, simplifying our proofs. |
---|
256 | As mentioned, the MCS-51 instruction set includes three different jump instructions: \texttt{SJMP}, \texttt{AJMP} and \texttt{LJMP}; call these `short', `medium' and `long' jumps, respectively: |
---|
257 | \begin{lstlisting} |
---|
258 | inductive jump_length: Type[0] := |
---|
259 | | short_jump: jump_length |
---|
260 | | medium_jump: jump_length |
---|
261 | | long_jump: jump_length. |
---|
262 | \end{lstlisting} |
---|
263 | A \texttt{jump\_expansion\_policy} is a map from \texttt{Word}s to \texttt{jump\_length}s, implemented as a trie. |
---|
264 | Intuitively, a policy maps positions in a program (indexed using program counters implemented as \texttt{Word}s) to a particular variety of jump. |
---|
265 | \begin{lstlisting} |
---|
266 | definition jump_expansion_policy := BitVectorTrie jump_length 16. |
---|
267 | \end{lstlisting} |
---|
268 | Next, we require a series of `sigma' functions. |
---|
269 | These functions map assembly program counters to their machine code counterparts, establishing the correspondence between `positions' in an assembly program and `positions' in a machine code program. |
---|
270 | At the heart of this process is \texttt{sigma0} which traverses an assembly program building maps from program counter to program counter. |
---|
271 | This function fails if and only if an internal call to \texttt{assembly\_1\_pseudoinstruction} fails: |
---|
272 | \begin{lstlisting} |
---|
273 | definition sigma0: pseudo_assembly_program |
---|
274 | $\rightarrow$ option (nat $\times$ (nat $\times$ (BitVectorTrie Word 16))) := $\ldots$ |
---|
275 | \end{lstlisting} |
---|
276 | We eventually lift this to functions from program counters to program counters: |
---|
277 | \begin{lstlisting} |
---|
278 | definition sigma_safe: |
---|
279 | pseudo_assembly_program $\rightarrow$ option (Word $\rightarrow$ Word) := $\ldots$ |
---|
280 | \end{lstlisting} |
---|
281 | Now, it's possible to define what a `good policy' is i.e. one that does not cause \texttt{sigma\_safe} to fail. |
---|
282 | As mentioned, \texttt{sigma\_safe} can only fail if an assembly program fails to be assembled: |
---|
283 | \begin{lstlisting} |
---|
284 | definition policy_ok := $\lambda$p. sigma_safe p $\neq$ None $\ldots$. |
---|
285 | \end{lstlisting} |
---|
286 | Finally, we obtain \texttt{sigma}, a map from program counters to program counters, which is guranteed not to fail as we internally provide a that |
---|
287 | \begin{lstlisting} |
---|
288 | definition sigma: pseudo_assembly_program $\rightarrow$ Word $\rightarrow$ Word := $\ldots$ |
---|
289 | \end{lstlisting} |
---|
290 | |
---|
291 | % ---------------------------------------------------------------------------- % |
---|
292 | % SECTION % |
---|
293 | % ---------------------------------------------------------------------------- % |
---|
294 | \subsection{Total correctness of the assembler} |
---|
295 | \label{subsect.total.correctness.of.the.assembler} |
---|
296 | |
---|
297 | Using our policies, we now work toward proving the total correctness of the assembler. |
---|
298 | By total correctness, we mean that the assembly process does not change the semantics of an assembly program. |
---|
299 | Naturally, this necessitates keeping some sort of correspondence between program counters at the assembly level, and program counters at the machine code level. |
---|
300 | For this, we use the \texttt{sigma} machinery defined at the end of Subsection~\ref{subsect.policies}. |
---|
301 | |
---|
302 | We expand pseudoinstructions using the function \texttt{expand\_pseudo\_instruction}. |
---|
303 | This function accepts a `policy decision'---an element of type \texttt{jump\_length}---that is used when expanding a \texttt{Call}, \texttt{Jmp} or conditional jump to a label into the correct machine instruction. |
---|
304 | This \texttt{policy\_decision} is asssumed to originate from a policy as defined in Subsection~\ref{subsect.policies}. |
---|
305 | \begin{lstlisting} |
---|
306 | definition expand_pseudo_instruction: |
---|
307 | ∀lookup_labels, lookup_datalabels, pc, policy_decision. |
---|
308 | pseudo_instruction $\rightarrow$ option list instruction := $\ldots$ |
---|
309 | \end{lstlisting} |
---|
310 | Under the assumption that a correct policy exists, \texttt{expand\_pseudo\_instruction} should never fail, and therefore the option type may be dispensed with. |
---|
311 | This is because the only failure conditions for \texttt{expand\_pseudo\_instruction} result from trying to expand a pseudoinstruction into an `impossible' combination of machine code instructions. |
---|
312 | For instance, if the policy decision dictates that we should expand a \texttt{Call} pseudoinstruction into a `short jump', then we fail, as the MCS-51's instruction set only features instructions \texttt{ACALL} and \texttt{LCALL}. |
---|
313 | |
---|
314 | % dpm todo |
---|
315 | \begin{lstlisting} |
---|
316 | axiom assembly_ok: ∀program,assembled,costs,labels. |
---|
317 | Some $\ldots$ $\langle$labels, costs$\rangle$ = build_maps program $\rightarrow$ |
---|
318 | Some $\ldots$ $\langle$assembled, costs$\rangle$ = assembly program $\rightarrow$ |
---|
319 | let code_memory := load_code_memory assembled in |
---|
320 | let preamble := $\pi_1$ program in |
---|
321 | let datalabels := construct_datalabels preamble in |
---|
322 | let lk_labels := |
---|
323 | $\lambda$x. sigma program (address_of_word_labels_code_mem ($\pi_2$ program) x) in |
---|
324 | let lk_dlabels := $\lambda$x. lookup ? ? x datalabels (zero ?) in |
---|
325 | ∀ppc,len,assembledi. |
---|
326 | let $\langle$pi, newppc$\rangle$ := fetch_pseudo_instruction ($\pi_2$ program) ppc in |
---|
327 | let assembly' := assembly_1_pseudoinstruction program ppc |
---|
328 | (sigma program ppc) lk_labels lk_dlabels pi in |
---|
329 | let newpc := (sigma program ppc) + len in |
---|
330 | let echeck := |
---|
331 | encoding_check code_memory (sigma program ppc) slen assembledi in |
---|
332 | Some $\ldots$ $\langle$len, assembledi$\rangle$ = assembly' $\rightarrow$ |
---|
333 | echeck $\wedge$ sigma program newppc = newpc. |
---|
334 | \end{lstlisting} |
---|
335 | |
---|
336 | % dpm todo |
---|
337 | \begin{lstlisting} |
---|
338 | theorem fetch_assembly: $\forall$pc, i, cmem, assembled. |
---|
339 | assembled = assembly1 i $\rightarrow$ |
---|
340 | let len := length $\ldots$ assembled in |
---|
341 | encoding_check cmem pc (pc + len) assembled $\rightarrow$ |
---|
342 | let fetched := fetch code_memory (bitvector_of_nat $\ldots$ pc) in |
---|
343 | let $\langle$instr_pc, ticks$\rangle$ := fetched in |
---|
344 | let $\langle$instr, pc'$\rangle$ := instr_pc in |
---|
345 | (eq_instruction instr i $\wedge$ |
---|
346 | eqb ticks (ticks_of_instruction instr) $\wedge$ |
---|
347 | eq_bv $\ldots$ pc' (pc + len)) = true. |
---|
348 | \end{lstlisting} |
---|
349 | |
---|
350 | Lemma \texttt{fetch\_assembly\_pseudo} establishes a basic relationship between \texttt{expand\_pseudo\_instruction} and \texttt{assembly\_1\_pseudoinstruction}: |
---|
351 | \begin{lstlisting} |
---|
352 | lemma fetch_assembly_pseudo: $\forall$program, ppc, lk_labels, lk_dlabels. |
---|
353 | $\forall$pi, code_memory, len, assembled, instructions, pc. |
---|
354 | let jexp := jump_expansion ppc program in |
---|
355 | let exp := |
---|
356 | expand_pseudo_instruction lk_labels lk_dlabels pc jexp pi |
---|
357 | let ass := |
---|
358 | assembly_1_pseudoinstruction program ppc pc lk_labels lk_dlabels pi in |
---|
359 | Some ? instructions = exp $\rightarrow$ |
---|
360 | Some $\ldots$ $\langle$len, assembled$\rangle$ = ass $\rightarrow$ |
---|
361 | encoding_check code_memory pc (pc + len) assembled $\rightarrow$ |
---|
362 | fetch_many code_memory (pc + len) pc instructions. |
---|
363 | \end{lstlisting} |
---|
364 | Here, \texttt{len} is the number of machine code instructions the pseudoinstruction at hand has been expanded into, \texttt{encoding\_check} is a recursive function that checks for any possible corruption of the code memory, resulting from expanding the pseudoinstruction. |
---|
365 | We assemble a single pseudoinstruction with \texttt{assembly\_1\_pseudoinstruction}, which internally calls \texttt{jump\_expansion} and \texttt{expand\_pseudo\_instruction}. |
---|
366 | The function \texttt{fetch\_many} fetches multiple machine code instructions from code memory and performs some routine checks. |
---|
367 | |
---|
368 | Intuitively, Lemma \texttt{fetch\_assembly\_pseudo} can be read as follows. |
---|
369 | Suppose our policy \texttt{jump\_expansion} dictates that the pseudoinstruction indexed by the pseudo program counter \texttt{ppc} in assembly program \texttt{program} gives us the policy decision \texttt{jexp}. |
---|
370 | Further, suppose we expand the pseudoinstruction at \texttt{ppc} with the policy decision \texttt{jexp}, obtaining an (optional) list of machine code instructions \texttt{exp}. |
---|
371 | Suppose we also assemble the pseudoinstruction at \texttt{ppc} to obtain \texttt{ass}, a list of bytes. |
---|
372 | Then, under the assumption that neither the expansion of the pseudoinstruction to obtain \texttt{exp}, nor the assembly of the pseudoinstruction to obtain \texttt{ass}, failed, we check with \texttt{fetch\_many} that the number of machine instructions that were fetched matches the number of instruction that \texttt{expand\_pseudo\_instruction} expanded. |
---|
373 | |
---|
374 | At first sight, Lemma \texttt{fetch\_assembly\_pseudo2} appears to nearly establish the correctness of the assembler: |
---|
375 | \begin{lstlisting} |
---|
376 | lemma fetch_assembly_pseudo2: $\forall$program, assembled, costs, labels. |
---|
377 | Some $\ldots$ $\langle$labels, costs$\rangle$ = build_maps program $\rightarrow$ |
---|
378 | Some $\ldots$ $\langle$assembled, costs$\rangle$ = assembly program $\rightarrow$ $\forall$ppc. |
---|
379 | let code_memory := load_code_memory assembled in |
---|
380 | let preamble := $\pi_1$ program in |
---|
381 | let data_labels := construct_datalabels preamble in |
---|
382 | let lk_labels := |
---|
383 | λx. sigma program (address_of_word_labels_code_mem ($\pi_2$ program) x) in |
---|
384 | let lk_dlabels := λx. lookup ? ? x data_labels (zero ?) in |
---|
385 | let expansion := jump_expansion ppc program in |
---|
386 | let $\langle$pi, newppc$\rangle$ := fetch_pseudo_instruction ($\pi_2$ program) ppc in |
---|
387 | let ppc' := sigma program ppc in |
---|
388 | let newppc' := sigma program newppc in |
---|
389 | let instructions' := |
---|
390 | expand_pseudo_instruction lk_labels lk_dlabels ppc' expansion pi in |
---|
391 | let fetched := $\lambda$instr. fetch_many code_memory newppc' ppc' instr in |
---|
392 | $\exists$instrs. Some ? instrs = instructions' $\wedge$ fetched instrs. |
---|
393 | \end{lstlisting} |
---|
394 | Intuitively, we may read \texttt{fetch\_assembly\_pseudo2} as follows. |
---|
395 | Suppose we are able to successfully assemble an assembly program using \texttt{assembly} and produce a code memory, \texttt{code\_memory}. |
---|
396 | Then there exists some list of machine instructions equal to the expansion of a pseudoinstruction and the number of machine instructions that need to be fetched is equal to the number of machine instructions that the pseudoinstruction was expanded into. |
---|
397 | |
---|
398 | However, this property is \emph{not} strong enough to establish that the semantics of an assembly program has been preserved by the assembly process. |
---|
399 | In particular, \texttt{fetch\_assembly\_pseudo2} says nothing about how memory addresses evolve during assembly. |
---|
400 | Memory addresses in one memory space may be mapped to memory addresses in a completely different memory space during assembly. |
---|
401 | To handle this problem, we need some more machinery. |
---|
402 | |
---|
403 | We use an \texttt{internal\_pseudo\_address\_map} for this purpose. |
---|
404 | An \texttt{internal\_pseudo\_address\_map} associates positions in the memory of a \texttt{PseudoStatus} with a physical memory address: |
---|
405 | \begin{lstlisting} |
---|
406 | definition internal_pseudo_address_map := list (BitVector 8). |
---|
407 | \end{lstlisting} |
---|
408 | We use \texttt{internal\_pseudo\_address\_map}s to convert the lower internal RAM of a \texttt{PseudoStatus} into the lower internal RAM of a \texttt{Status}. |
---|
409 | The actual conversion process is performed by \texttt{low\_internal\_ram\_of\_pseudo\_low\_internal\_ram}:\footnote{An associated set of axioms describe how \texttt{low\_internal\_ram\_of\_pseudo\_low\_internal\_ram} behaves. This is a form of parametricity. We don't care about the particulars of the conversion functions, as long as they behave in accordance with our axioms.} |
---|
410 | |
---|
411 | \begin{lstlisting} |
---|
412 | axiom low_internal_ram_of_pseudo_low_internal_ram: |
---|
413 | internal_pseudo_address_map $\rightarrow$ BitVectorTrie Byte 7 $\rightarrow$ BitVectorTrie Byte 7. |
---|
414 | \end{lstlisting} |
---|
415 | A similar axiom exists for high internal RAM. |
---|
416 | |
---|
417 | Notice, the MCS-51's internal RAM is addressed with a 7-bit `byte'. |
---|
418 | % dpm: ugly English, fix |
---|
419 | The whole of the internal RAM space is addressed with bytes: the first bit is used to distinguish between the programmer addressing low and high internal memory. |
---|
420 | |
---|
421 | Next, we are able to translate \texttt{PseudoStatus} records into \texttt{Status} records using \texttt{status\_of\_pseudo\_status}. |
---|
422 | Translating a \texttt{PseudoStatus}'s code memory requires we expand pseudoinstructions and then assemble to obtain a trie of bytes. |
---|
423 | This can fail, as mentioned, in a limited number of situations, related to improper use of labels in an assembly program. |
---|
424 | However, it is possible to `tighten' the type of \texttt{status\_of\_pseudo\_status}, removing the option type, by using the fact that if any `good policy' exists, assembly will never fail. |
---|
425 | \begin{lstlisting} |
---|
426 | definition status_of_pseudo_status: |
---|
427 | internal_pseudo_address_map → PseudoStatus → option Status |
---|
428 | \end{lstlisting} |
---|
429 | After fetching an assembly instruction we must update any \texttt{internal\_pseudo\hyp{}\_address\_map}s that may be laying around. |
---|
430 | This is done with the following function: |
---|
431 | \begin{lstlisting} |
---|
432 | definition next_internal_pseudo_address_map: internal_pseudo_address_map |
---|
433 | $\rightarrow$ PseudoStatus $\rightarrow$ option internal_pseudo_address_map |
---|
434 | \end{lstlisting} |
---|
435 | Finally, we are able to state and prove our main theorem. |
---|
436 | This relates the execution of a single assembly instruction and the execution of (possibly) many machine code instructions. |
---|
437 | That is, the assembly process preserves the semantics of an assembly program, as it is translated into machine code: |
---|
438 | \begin{lstlisting} |
---|
439 | theorem main_thm: |
---|
440 | ∀M,M',ps,s,s''. |
---|
441 | next_internal_pseudo_address_map M ps = Some $\ldots$ M' $\rightarrow$ |
---|
442 | status_of_pseudo_status M ps = Some $\ldots$ s $\rightarrow$ |
---|
443 | status_of_pseudo_status M' |
---|
444 | (execute_1_pseudo_instruction |
---|
445 | (ticks_of (code_memory $\ldots$ ps)) ps) = Some $\ldots$ s'' $\rightarrow$ |
---|
446 | $\exists$n. execute n s = s''. |
---|
447 | \end{lstlisting} |
---|
448 | The statement can be given an intuitive reading as follows. |
---|
449 | Suppose our \texttt{PseudoStatus}, \texttt{ps}, can be successfully converted into a \texttt{Status}, \texttt{s}. |
---|
450 | Suppose further that, after executing a single assembly instruction and converting the resulting \texttt{PseudoStatus} into a \texttt{Status}, we obtain \texttt{s''}, being careful to track the number of ticks executed. |
---|
451 | Then, there exists some number \texttt{n}, so that executing \texttt{n} machine code instructions in \texttt{Status} \texttt{s} gives us \texttt{Status} \texttt{s''}. |
---|
452 | Theorem \texttt{main\_thm} establishes the correctness of the assembly process. |
---|
453 | |
---|
454 | % ---------------------------------------------------------------------------- % |
---|
455 | % SECTION % |
---|
456 | % ---------------------------------------------------------------------------- % |
---|
457 | \section{Conclusions} |
---|
458 | \label{sect.conclusions} |
---|
459 | |
---|
460 | We have proved the total correctness of an assembler for MCS-51 assembly language. |
---|
461 | In particular, our assembly language featured labels, arbitrary conditional and unconditional jumps to labels, global data and instructions for moving this data into the MCS-51's single 16-bit register. |
---|
462 | Expanding these pseudoinstructions into machine code instructions is not trivial, and the proof that the assembly process is `correct', in that the semantics of an assembly program are not changed is complex. |
---|
463 | |
---|
464 | The formalisation is a key component of the CerCo project, which aims to produce a verified concrete complexity preserving compiler for a large subset of the C programming language. |
---|
465 | The verified assembler, complete with the underlying formalisation of the semantics of MCS-51 machine code (described fully in~\cite{mulligan:executable:2011}), will form the bedrock layer upon which the rest of the CerCo project will build its verified compiler platform. |
---|
466 | |
---|
467 | Aside from their application in verified compiler projects such as CerCo, verified assemblers such as ours could also be applied to the verification of operating system kernels. |
---|
468 | Of particular note is the verified seL4 kernel~\cite{klein:sel4:2009,klein:sel4:2010}. |
---|
469 | This verification explicitly assumes the existence of, amongst other things, a trustworthy assembler and compiler. |
---|
470 | |
---|
471 | \paragraph{Use of dependent types and Russell} |
---|
472 | Our formalisation makes sparing use of dependent types. |
---|
473 | In certain datastructures, such as tries and vectors, they are used to guarantee invariants. |
---|
474 | However, we have currently shyed away from making extensive use of dependent types and inductive predicates in the proof of correctness for the assembler itself. |
---|
475 | This is because complex dependent types and inductive predicates tend not to co\"operate particularly well with tactics such as inversion. |
---|
476 | |
---|
477 | However, there are certain cases where the use of dependent types is unavoidable. |
---|
478 | For instance, when proving that the \texttt{build\_maps} function is correct, a function that collates the cost and data labels of an assembly program into map datastructures. |
---|
479 | In cases such as these we make use of Matita's implementation of Russell~\cite{sozeau:subset:2006}. |
---|
480 | In Matita, Russell may be implemented with two coercions and some notational sugaring. |
---|
481 | |
---|
482 | \subsection{Related work} |
---|
483 | \label{subsect.related.work} |
---|
484 | |
---|
485 | % piton |
---|
486 | We are not the first to consider the total correctness of an assembler for a non-trivial assembly language. |
---|
487 | Perhaps the most impressive piece of work in this domain is the Piton stack~\cite{moore:piton:1996,moore:grand:2005}. |
---|
488 | This was a stack of verified components, written and verified in ACL2, ranging from a proprietary FM9001 microprocessor verified at the gate level, to assemblers and compilers for two high-level languages---a dialect of Lisp and $\mu$Gypsy~\cite{moore:grand:2005}. |
---|
489 | %dpm more: weirich paper? |
---|
490 | |
---|
491 | % jinja |
---|
492 | Klein and Nipkow consider a Java-like programming language, Jinja~\cite{klein:machine:2006,klein:machine:2010}. |
---|
493 | They provide a compiler, virtual machine and operational semantics for the programming language and virtual machine, and prove that their compiler is semantics and type preserving. |
---|
494 | |
---|
495 | Finally, mention should be made of CompCert~\cite{compcert:2011,blazy:formal:2006,leroy:formal:2009,leroy:formally:2009}, another verified compiler project related to CerCo. |
---|
496 | As previously mentioned, CompCert considers only extensional correctness of the compiler, and not intensional correctness, which CerCo focusses on. |
---|
497 | However, CerCo also extends CompCert in other ways. |
---|
498 | Namely, the CompCert verified compilation chain terminates at the PowerPC or ARM assembly level, and takes for granted the existence of a trustworthy assembler. |
---|
499 | CerCo chooses to go further, by considering a verified compilation chain all the way down to the machine code level. |
---|
500 | In essence, the work presented in this publication is one part of CerCo's extension over CompCert. |
---|
501 | |
---|
502 | \bibliography{cpp-2011.bib} |
---|
503 | |
---|
504 | \end{document}\renewcommand{\verb}{\lstinline} |
---|
505 | \def\lstlanguagefiles{lst-grafite.tex} |
---|
506 | \lstset{language=Grafite} |
---|