source: Deliverables/D6.2/supplement.tex @ 3544

Last change on this file since 3544 was 2031, checked in by Ian Stark, 9 years ago

Mention FMICS 2012 paper

  • Property svn:eol-style set to native
  • Property svn:mime-type set to text/x-latex
File size: 14.6 KB
1% CerCo: Certified Complexity
3% Supplement to Deliverable 6.2
5% Plan for Dissemination and Use
7% At the end of year 1, this deliverable was rejected by the reviewers and
8% they asked for an addendum, which I wrote shortly after the review.  At the
9% end of year 1, that was itself rejected by the reviewers.  They said:
11% "The reviewers request the resubmission of the addenda to deliverables D2.1
12% and D6.2 within one month from the receipt of this report.
14% ...
16% Deliverable D6.2 does not contain a specific and clear dissemination
17% strategy or plan till the end of the project.  The reviewers request the
18% resubmission of D6.2 detailing an event targeting at the promoting the
19% results of the CerCo project.  It should be planned at least as a half-day
20% event solely presenting the CerCo project.  In order to attract an audience
21% from academia as well as from industry the event should try to focus on case
22% studies for the dependent labelling approach in more modern processor
23% architectures, e.g., as applied in the embedded domain."
25% I'm writing this supplement to D6.2 as our response to this.  At the May
26% 2012 meeting in Bologna we discussed:
28%  - Plans for the CerCo workshop at ETAPS 2013 (later HiPEAC 2013 too)
29%  - Subject areas for papers to be written and submitted
31% Strictly, the reviewers request only mentions the event.  However, if we can
32% make a good job of the paper list, then that would be an advance on the
33% addendum as of last year — and resubmitting the addendum is what was
34% requested. 
36% Ian Stark
37% 2012-05-24
48\vspace*{1cm}Project FP7-ICT-2009-C-243881 {\cerco}}
69Supplement to Deliverable 6.2\\[\jot]
70{\cerco} Workshop and Publication Planning
77Version 1.0
84Main Authors:\\
85I. Stark
91Project Acronym: {\cerco}\\
92Project full title: Certified Complexity\\
93Proposal/Contract no.: FP7-ICT-2009-C-243881 {\cerco}
95\clearpage\pagestyle{myheadings}\markright{{\cerco}, FP7-ICT-2009-C-243881}
99In March~2012 the second-year review panel for the {\cerco} project requested
100details of specific plans to promote the final results of the project.  This
101document is a response to that, with the following two contributions.
103\item Plans for the {\cerco} workshop at the HiPEAC~'13 meeting in Berlin
104  (Deliverables 6.4 and~6.5).
105\item A list of proposed publications reporting {\cerco} results.
107This report supplements the \emph{Plan for the Use and Dissemination of
108  Foreground}, Deliverable~6.2, from August 2010 and addendum \emph{Future
109  Dissemination Plans} of April 2011.
111\section{{\cerco} Workshop}
113We shall hold a {\cerco} one-day workshop for academic and industrial
114researchers.  Our preferred destination is \emph{HiPEAC '13}, to be held in
115Berlin at the end of January~2013.  This is an international meeting on
116high-performance and embedded architectures and compilers, organised by the
117European Network of Excellence in the field, and as such provides an ideal
118audience for {\cerco} results.  The conference workshops for 2013 have not yet
119been selected, but we have submitted our {\cerco} proposal for consideration.
120In case this is not successful, we are also holding an offer of a workshop day
121at ETAPS~2013, the European Joint Conferences on Theory and Practice of
122Software.  This too is a forum for a range of academic and industrial
123researchers, but it takes place in March 2013 and so does not fall within the
124{\cerco} timetable.
126This {\cerco} workshop has two objectives:
128\item To publicise the results of {\cerco} to members of the relevant
129  industrial and academic research communities.
130\item To stimulate discussion between the industrial and academic participants
131  about future work building on the current state of the art.
133To support these objectives, we propose to send invitations to a dozen
134industrial and academic research groups working in the field.  While the
135workshop will be open to anyone at HiPEAC who wishes to register, we consider
136an invitational workshop to be the most direct way to bring together {\cerco}
137researchers with potential users of the project results.  A list of possible
138invitees appears below.
140The workshop, with these objectives, is designed to meet the requirements of
141Deliverables 6.4 and~6.5 as set out in the original {\cerco} proposal (Annex~I
142``Description of Work'', Workplan Table 3, Work package~6).  In particular,
143that proposal envisioned overlapping the presentation of {\cerco} results to
144invited industrial and scientific audiences at an event co-located with an
145international conference.
147We plan the following draft structure for the workshop:
149\item Morning: Short talks by {\cerco} partners presenting the project and its
150  results.
151  \begin{itemize}
152  \item Project overview: a trustworthy framework for cost analysis of
153    embedded code.
154  \item Demonstration of Frama-C plugin: high-level static reasoning about
155    global runtime complexity.
156  \item Demonstration of Lustre plugin: automatic analysis of component
157    reaction time.
158  \item The {\cerco} compiler: what makes a certified compiler trustworthy.
159  \item The labelling approach to cost analysis: a modular way to prove
160    correctness.
161  \item Structured traces: tracking high-level structure in low-level
162    execution.
163  \item Dependent labels: managing refined cost information for richer
164    architectures.
165  \item Future directions: the latest very-low-power embedded processors;
166    other runtime costs; further languages.
167  \end{itemize}
168\item Afternoon: Short presentations by some of the invited participants on the
169  state of the art in static analysis of execution costs for embedded systems.
170\item Conclusion: Round-table discussion on potential applications and future
171  challenges.
173This structure addresses both of the listed objectives, with the morning
174dedicated to dissemination of {\cerco} results and the afternoon to promoting
175interaction between academic and industrial researchers working in the field.
177We have identified the following relevant groups as some initial invitees to
178the {\cerco} workshop.
180\item[AbsInt aIT] \emph{AbsInt} provide tools for validation of
181  safety-critical software, including static analysis for worst-case execution
182  time through abstract interpretation.  They have participated in a previous
183  {\cerco} event, and their insights into the requirements for precise timing
184  analysis are extremely relevant to the domain of {\cerco}.
185\item[Frama-C]  The \emph{Frama-C} platform for static analysis of C source
186  code provides the context for the {\cerco} plugin which demonstrates the use
187  of automated cost annotations on source code.
188\item[Rapita Systems] The \emph{RapiTime} timing analysis tool for real-time
189  embedded systems uses runtime instrumentation of C to identify source-level
190  execution costs and predict worst-cast execution time.
191\item[PASTA]  This research group at the University of Edinburgh are the
192  designers of the \emph{EnCore} family of configurable embedded
193  microprocessors.  Their \emph{ArcSim} tool offers cycle-accurate simulation
194  of these low-energy cores, giving significant insights into the
195  practicalities of precise cost analysis.
196\item[WCET-Aware Compilation]  Dr Heiko Falk at TU Dortmund leads this
197  research project investigating the optimizations and compilation techniques
198  appropriate to the requirements of worst-case rather than average-case
199  timing.
200\item[York RTS] The \emph{Real-Time Systems} research group at the University
201  of York are active in worst-case execution time analysis and the design of
202  time-predictable architectures.
203% \item[Hume/EmBounded]  Prof. Kevin Hammond at the University of St Andrews
204%   leads a research team working on the quantification and certification of
205%   resource use in concurrent real-time embedded software.
206\item[ARM Verification Project]  Gordon, Fox and Myreen at the University of
207  Cambridge have a machine-checked mathematical model of the ARM
208  microprocessor.  With the release of the ARM Cortex-M series of low-power
209  embedded processors, this is a potential application area for {\cerco}
210  technology in the future.
211\item[CompCertTSO]  Sewell's group, also at the University of Cambridge, have
212  a verified C compiler treating concurrency in a relaxed memory model.  Like
213  {\cerco}, they have relevant experience of extending CompCert-based
214  verification to additional code properties.
215\item[Gliwa Embedded Systems] The software consultancy \emph{Gliwa GmbH}
216  develop specialist tools for measurement and verification of execution time
217  in embedded systems.
218\item[Artemis]  The European industry association \emph{Advanced Research \&
219    Technology for Embedded Intelligence and Systems}.  We already have
220  contact with Artemis through the University of Bologna, which is a member of
221  the association.
222\item[IMDEA Software]  Dr Boris K\"opf applies quantitative analysis of code
223  execution time to evaluate potential security weaknesses by side-channel
224  attacks. 
225\item[ADSIG] The \emph{ArtistDesign Special Interest Group on Embedded Systems
226    Design} is a large consortium of experts in embedded systems design,
227  arising from the ARTIST Network of Excellence.
229We propose to invite each of these groups to send participants and, if they
230wish, contribute a short talk on their work to the afternoon session.  We
231shall also invite the {\cerco} project reviewers, who are experts in the area.
232This is not a closed list --- depending on responses, we are open to inviting
233further participants as appropriate.
236\section{Publication Planning}
238The original Deliverable~6.2 and its addendum, prepared earlier in the
239project, presented a list of conferences and journals suitable for publicising
240{\cerco} results.  Now that the project has progressed, we have reviewed the
241technical activities to date and identified a specific list of topics and
242results for dissemination in individual papers and articles.  Some of these
243have already been submitted, or accepted for publication: in particular, an
244FMICS~2012 paper on the labelling approach which also references the Frama-C
245plugin and Lustre case study.
247\item[Labelling] As presented in Deliverable~2.1, the use of labelling to
248  build cost annotations and prove their correctness is key to the {\cerco}
249  development.  It allows decoupling the certification of machine code
250  execution properties from the verification of the compilation map between C
251  source and assembler.
252\item[Dependent labelling] The indexing of labels with additional
253  data-dependent information makes is possible to track sources of variation
254  in execution cost: compiler optimizations such as unrolling or loop peeling;
255  or processor features like instruction pipelining and caches.
256\item[The {\cerco} Frama-C plugin] This was demonstrated at the second-year
257  review panel, and a paper would describe its operation and effect.  The
258  plugin annotates C source code with fine-grained cycle costs according to
259  {\cerco} analysis.  This instrumented code is passed to the \emph{Jessie}
260  plugin which can generate the verification conditions necessary to check the
261  cost specifications of complete procedures.  Finally, these conditions can
262  be passed to a range of automatic proof engines.  The overall result is
263  verified declarations of the cycle execution time of identified C functions,
264  in terms of input and other parameters, given in the ACSL specification
265  language.
266\item[Lustre analysis] This was also demonstrated at the review panel.  The
267  {\cerco} tools can perform automated analysis of response time for
268  individual components in the Lustre synchronous control language.  Lustre
269  automatically generates C source code for concurrent components, in a
270  sufficiently standard form to allow precise costing of execution paths.
271\item[Certifying machine code] {\cerco} extends previous work on compilation
272  by also verifying the final step from assembler to binary object code.  In
273  addition, it is essential to prove that cost annotations exactly capture
274  machine execution steps.  These are both substantial proofs with novel
275  features.
276\item[Correctness of branch selection] Many processors provide a range of
277  branch commands at the machine level, typically for different ranges of
278  jump.  Generating efficient and compact assembly code requires appropriate
279  branch selection.  This is non-trivial --- indeed, finding the optimum
280  selection is in some cases NP-hard --- and the complexity of any algorithm
281  here makes it a challenge for proving correctness.  {\cerco} have developed
282  a novel decomposition of branch selection into policy and implementation, to
283  separate concerns and allow for tractable proof.
284\item[Structured traces] {\cerco} reports execution costs at the level of C
285  source, where there is an evident code structure of nested call and return;
286  but these costs arise from unstructured individual steps at the machine
287  level.  We have developed a notion of structure on machine execution traces
288  which captures precisely the information necessary to correctly relay cost
289  information between these levels.  This is essential to the compiler proof,
290  and interesting in itself as a carrier of high-level information in a
291  low-level execution environment.
292\item[The {\cerco} formalisation] The large-scale structure of the {\cerco}
293  formalisation, its components, how they depend upon each other, and what is
294  required of them to complete the correctness proof.  Some parts of these are
295  related to analogous constructions in work such as CompCert; many are novel
296  and arise from our particular attention to verifying non-functional runtime
297  properties of code.
298\item[A survey of {\cerco} results] All the above papers deal with individual
299  parts of the {\cerco} project, or the technical details of its operation.  A
300  final paper should survey the outcome of the project, its achievements and
301  potential future work to build on these.
306%  LocalWords:  Frama AbsInt Rapita RapiTime EnCore ArcSim WCET Heiko HiPEAC
307%  LocalWords:  Falk EmBounded Myreen CompCertTSO ADSIG ArtistDesign ACSL FMICS
308%  LocalWords:  Gliwa GmbH
Note: See TracBrowser for help on using the repository browser.