-
Notifications
You must be signed in to change notification settings - Fork 0
/
publi_abstracts.html
executable file
·1389 lines (1225 loc) · 54.6 KB
/
publi_abstracts.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
<title>David Pichardie - Home page</title>
<link href="style.css" rel="stylesheet" type="text/css" />
</head>
<body>
<a name="top" id="top"></a>
<center>
<div id="header">
<h1>David Pichardie</h1>
<h2>Publications</h2>
</div>
<div id="content">
<div id="sidebar">
<div class="submenu">
<h1>Menu</h1>
<a href="index.html">Home</a>
<a href="research.html">Research</a>
<a href="publi.html">Publications</a>
<a href="teaching.html">Teaching</a>
</div>
</div>
<div id="mainbar">
<table>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="CSF17:Barthe:al">1</a>]
</td>
<td class="bibtexitem">
Gilles Barthe, Sandrine Blazy, Vincent Laporte, David Pichardie, and Alix
Trieu.
Verified translation validation of static analyses.
In <em>IEEE 30th Computer Security Foundations Symposium, CSF
2017</em>. IEEE Computer Society, 2017.
[ <a href="publi_bib.html#CSF17:Barthe:al">bib</a> ]
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="ITP17:Zakowski:al">2</a>]
</td>
<td class="bibtexitem">
Yannick Zakowski, David Cachera, Delphine Demange, Gustavo Petri, David
Pichardie, Suresh Jagannathan, and Jan Vitek.
Verifying a concurrent garbage collector using a rely-guarantee
methodology.
In <em>Proc. of the 8th International Conference on Interactive
Theorem Proving (ITP 2017)</em>, volume 10499 of <em>Lecture Notes in Computer
Science</em>. Springer-Verlag, 2017.
[ <a href="publi_bib.html#ITP17:Zakowski:al">bib</a> ]
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="ESORICS17:Blazy:al">3</a>]
</td>
<td class="bibtexitem">
Sandrine Blazy, David Pichardie, and Alix Trieu.
Verifying constant-time implementations by abstract interpretation.
In <em>Proc. of the 22nd European Symposium on Research in Computer
Security (ESORICS 2017)</em>, volume 10492 of <em>Lecture Notes in Computer
Science</em>. Springer-Verlag, 2017.
[ <a href="publi_bib.html#ESORICS17:Blazy:al">bib</a> ]
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="JAR16:Blazy:al">4</a>]
</td>
<td class="bibtexitem">
Sandrine Blazy, Vincent Laporte, and David Pichardie.
Verified Abstract Interpretation Techniques for Disassembling
Low-level Self-modifying Code.
<em>Journal of Automated Reasoning</em>, 56(3):26, 2016.
[ <a href="publi_bib.html#JAR16:Blazy:al">bib</a> |
<a href="https://hal.inria.fr/hal-01243700/document">http</a> ]
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="ICFP16:Blazy:al">5</a>]
</td>
<td class="bibtexitem">
Sandrine Blazy, Vincent Laporte, and David Pichardie.
An Abstract Memory Functor for Verified C Static Analyzers.
In <em>ACM SIGPLAN International Conference on Functional
Programming (ICFP 2016)</em>, page 14, Nara, Japan, September 2016. ACM.
[ <a href="publi_bib.html#ICFP16:Blazy:al">bib</a> |
<a href="https://hal.inria.fr/hal-01339969/document">http</a> ]
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="JCS16:Amorim:al">6</a>]
</td>
<td class="bibtexitem">
Arthur Azevedo de Amorim, Nathan Collins, André DeHon, Delphine Demange,
Catalin Hritcu, David Pichardie, Benjamin C. Pierce, Randy Pollack, and
Andrew Tolmach.
A verified information-flow architecture.
<em>Journal of Computer Security</em>, 24(6):689--734, 2016.
[ <a href="publi_bib.html#JCS16:Amorim:al">bib</a> |
<a href="https://arxiv.org/pdf/1509.06503">http</a> ]
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="ITP15:Blazy:al">7</a>]
</td>
<td class="bibtexitem">
Sandrine Blazy, Delphine Demange, and David Pichardie.
Validating dominator trees for a fast, verified dominance test.
In <em>Proc. of the 6th International Conference on Interactive
Theorem Proving (ITP 2015)</em>, Lecture Notes in Computer Science. Springer,
2015.
[ <a href="publi_bib.html#ITP15:Blazy:al">bib</a> |
<a href="papers/itp15.pdf">.pdf</a> ]
<blockquote>
The problem of computing dominators in a control flow graph is central
to numerous modern compiler optimizations. Many efficient algorithms
have been proposed in the litterature, but mechanizing the correctness
of the most sophisticated algorithms is still considered as too hard
problems, and to this date, verified compilers use less optimized
implementations.
In contrast, production compilers, like GCC or LLVM, implement the
classic, efficient Lengauer-Tarjan
algorithm, to compute dominator trees. And
subsequent optimization phases can then determine whether a CFG node
dominates another node in constant time by using their respective
depth-first search numbers in the dominator tree.<p>
In this work, we aim at integrating such techniques in verified
compilers. We present a formally verified validator of untrusted
dominator trees, on top of which we implement and prove correct a fast
dominance test following these principles.
We conduct our formal development in the Coq proof assistant, and
integrate it in the middle-end of the CompCertSSA verified
compiler. We also provide experimental results showing performance
improvement over previous formalizations.
</blockquote>
<p>
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="CC15:Demange:al">8</a>]
</td>
<td class="bibtexitem">
Delphine Demange David Pichardie and Léo Stefanesco.
Verifying fast and sparse ssa-based optimizations in coq.
In <em>Proc. of the 24th International Conference on Compiler
Construction (CC 2015)</em>, Lecture Notes in Computer Science. Springer, 2015.
[ <a href="publi_bib.html#CC15:Demange:al">bib</a> |
<a href="papers/cc15.pdf">.pdf</a> ]
<blockquote>
Abstract The Static Single Assignment (SSA) form is a predominant
technology in modern compilers, enabling powerful and fast
program optimizations. Despite its great success in the
implementation of pro- duction compilers, it is only very
recently that this technique has been introduced in verified
compilers. As of today, few evidence exist on that, in this
context, it also allows faster and simpler optimizations. This
work builds on the CompCertSSA verified compiler (an SSA branch
of the verified CompCert C compiler). We implement and verify two
prevail- ing SSA optimizations: Sparse Conditional Constant
Propagation and Global Value Numbering. For both transformations,
we mechanically prove their soundness in the Coq proof
assistant. Both optimization proofs are embedded in a single
sparse optimization framework, factoring out many of the
dominance-based reasoning steps required in proofs of SSA-based
optimizations. Our experimental evaluations indicate both a
better precision, and a significant compilation time speedup.
</blockquote>
<p>
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="POPL15:Jourdan:al">9</a>]
</td>
<td class="bibtexitem">
Jacques-Henri Jourdan, Vincent Laporte, Sandrine Blazy, Xavier Leroy, and David
Pichardie.
A formally-verified C static analyzer.
In <em>42nd symposium Principles of Programming Languages</em>, pages
247--259. ACM Press, 2015.
[ <a href="publi_bib.html#POPL15:Jourdan:al">bib</a> |
<a href="papers/popl15.pdf">.pdf</a> ]
<blockquote>
This paper reports on the design and soundness proof, using the
Coq proof assistant, of Verasco, a static analyzer based on
abstract interpretation for most of the ISO C 1999
language (excluding recursion and dynamic allocation). Verasco
establishes the absence of run-time errors in the analyzed
programs. It enjoys a modular architecture that supports the
extensible combination of multiple abstract domains, both
relational and non-relational. Verasco integrates with the
CompCert formally-verified C compiler so that not only the
soundness of the analysis results is guaranteed with mathematical
certitude, but also the fact that these guarantees carry over to
the compiled code.
</blockquote>
<p>
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="CPP15:Blazy:al">10</a>]
</td>
<td class="bibtexitem">
Sandrine Blazy, André Maroneze, and David Pichardie.
Verified validation of program slicing.
In <em>Proc. of the 5th Conference on Certified Programs and Proofs,
CPP 2015</em>. ACM, 2015.
[ <a href="publi_bib.html#CPP15:Blazy:al">bib</a> |
<a href="papers/cpp15.pdf">.pdf</a> ]
<blockquote>
Program slicing is a well-known program transformation which
simplifies a program with respect to a given criterion while
preserving its semantics. Since the seminal paper published by
Weiser in 1981, program slicing is still widely used in various
application domains. State of the art program slicers operate
over program de- pendence graphs (PDG), a sophisticated data
structure combining data and control dependences.
In this paper, we follow the a posteriori validation approach to
formally verify (in Coq) a general program slicer. Our validator
for program slicing is efficient and validates the results of a
run of an unverified program slicer. Program slicing is
interesting for a posteriori validation because the correctness
proof of program slicing requires to compute new supplementary
information from the PDG, thus decoupling the slicing algorithm
from its proof.
Our semantics-preserving program slicer is integrated into the
CompCert formally verified compiler. It operates over an
intermediate language of the compiler having the same
expressiveness as C. Our experiments show that our formally
verified validator scales on large realistic programs.
</blockquote>
<p>
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="CCS14:Barthe:al">11</a>]
</td>
<td class="bibtexitem">
Gilles Barthe, Gustavo Betarte, Juan Diego Campo, Carlos Luna, and David
Pichardie.
System-level non-interference for constant-time cryptography.
In <em>ACM SIGSAC Conference on Computer and Communications
Security, CCS'14</em>. ACM, 2014.
[ <a href="publi_bib.html#CCS14:Barthe:al">bib</a> |
<a href="papers/ccs14.pdf">.pdf</a> ]
<blockquote>
Cache-based attacks are a class of side-channel attacks that are
particularly effective in virtualized or cloud-based environments,
where they have been used to recover secret keys from cryptographic
implementations. One common approach to thwart cache-based attacks is
to use constant-time implementations, i.e., which do not
branch on secrets and do not perform memory accesses that depend on
secrets. However, there is no rigorous proof that constant-time
implementations are protected against concurrent cache-attacks in
virtualization platforms with shared cache; moreover, many prominent
implementations are not constant-time. An alternative approach is to
rely on system-level mechanisms. One recent such mechanism is stealth
memory, which provisions a small amount of private cache for programs
to carry potentially leaking computations securely. Stealth memory
induces a weak form of constant-time, called S-constant-time,
which encompasses some widely used cryptographic
implementations. However, there is no rigorous analysis of stealth
memory and S-constant-time, and no tool support for checking if
applications are S-constant-time.
We propose a new information-flow analysis that checks if an x86
application executes in constant-time, or in
S-constant-time. Moreover, we prove that constant-time
(resp. S-constant-time) programs do not leak confidential information
through the cache to other operating systems executing concurrently on
virtualization platforms (resp. platforms supporting stealth
memory). The soundness proofs are based on new theorems of independent
interest, including isolation theorems for virtualization platforms
(resp. platforms supporting stealth memory), and proofs that
constant-time implementations (resp. S-constant-time implementations)
are non-interfering with respect to a strict information flow policy
which disallows that control flow and memory accesses depend on
secrets. We formalize our results using the Coq proof
assistant and we demonstrate the effectiveness of our analyses on
cryptographic implementations, including PolarSSL AES, DES and RC4,
SHA256 and Salsa20.
</blockquote>
<p>
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="TOPLAS14:Jagannathan:al">12</a>]
</td>
<td class="bibtexitem">
Suresh Jagannathan, Vincent Laporte, Gustavo Petri, David Pichardie, and Jan
Vitek.
Atomicity refinement for verified compilation.
<em>ACM Trans. Program. Lang. Syst. (TOPLAS)</em>, 36(2):1, 2014.
[ <a href="publi_bib.html#TOPLAS14:Jagannathan:al">bib</a> |
<a href="papers/toplas_pldi14.pdf">.pdf</a> ]
<blockquote>
We consider the verified compilation of high-level managed languages like
Java or C# whose intermediate representations provide support for
shared-memory synchronization and automatic memory management. Our
development is framed in the context of the Total Store Order relaxed memory
model. Ensuring complier correctness is challenging because high-level
actions are translated into sequences of non-atomic actions with
compiler-injected snippets of racy code; the behavior of this code depends
not only on the actions of other threads, but also on out-of-order
executions performed by the processor. A naïve proof of correctness
would require reasoning over all possible thread interleavings. In this
paper we propose a refinement-based proof methodology that precisely relates
concurrent code expressed at different abstraction levels, cognizant
throughout of the relaxed memory semantics of the underlying processor. Our
technique allows the compiler writer to reason compositionally about the
atomicity of low-level concurrent code used to implement managed services.
We illustrate our approach with examples taken from the verification of a
concurrent garbage collector.
</blockquote>
<p>
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="PLDI14:Jagannathan:al">13</a>]
</td>
<td class="bibtexitem">
Suresh Jagannathan, Vincent Laporte, Gustavo Petri, David Pichardie, and Jan
Vitek.
Atomicity refinement for verified compilation.
In <em>ACM SIGPLAN Conference on Programming Language Design and
Implementation, PLDI'14</em>, page 5. ACM, 2014.
Submitted and accepted to TOPLAS vol 36, presented at PLDI the same
year.
[ <a href="publi_bib.html#PLDI14:Jagannathan:al">bib</a> |
<a href="papers/toplas_pldi14.pdf">.pdf</a> ]
<blockquote>
We consider the verified compilation of high-level managed languages like
Java or C# whose intermediate representations provide support for
shared-memory synchronization and automatic memory management. Our
development is framed in the context of the Total Store Order relaxed memory
model. Ensuring complier correctness is challenging because high-level
actions are translated into sequences of non-atomic actions with
compiler-injected snippets of racy code; the behavior of this code depends
not only on the actions of other threads, but also on out-of-order
executions performed by the processor. A naïve proof of correctness
would require reasoning over all possible thread interleavings. In this
paper we propose a refinement-based proof methodology that precisely relates
concurrent code expressed at different abstraction levels, cognizant
throughout of the relaxed memory semantics of the underlying processor. Our
technique allows the compiler writer to reason compositionally about the
atomicity of low-level concurrent code used to implement managed services.
We illustrate our approach with examples taken from the verification of a
concurrent garbage collector.
</blockquote>
<p>
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="TOPLAS14:Barthe:al">14</a>]
</td>
<td class="bibtexitem">
Gilles Barthe, Delphine Demange, and David Pichardie.
Formal verification of an ssa-based middle-end for compcert.
<em>ACM Trans. Program. Lang. Syst. (TOPLAS)</em>, 36(1):4, 2014.
[ <a href="publi_bib.html#TOPLAS14:Barthe:al">bib</a> |
<a href="papers/toplas14.pdf">.pdf</a> ]
<blockquote>
CompCert is a formally verified compiler that generates compact and
efficient code for a large subset of the C language. However, CompCert
foregoes using SSA, an intermediate representation employed by many
compilers that enables writing simpler, faster optimizers. In fact, it
has remained an open problem to verify formally an SSA-based compiler.
We report on a formally verified, SSA-based, middle-end for
CompCert. In addition to providing a formally verified SSA-based
middle-end, we address two problems raised by Leroy in 2009: giving an
intuitive formal semantics to SSA, and leveraging its global
properties to reason locally about program optimizations.
</blockquote>
<p>
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="ITP14:Blazy:al">15</a>]
</td>
<td class="bibtexitem">
Sandrine Blazy, Vincent Laporte, and David Pichardie.
Verified abstract interpretation techniques for disassembling
low-level self-modifying code.
In <em>Proc. of the 5th International Conference on Interactive
Theorem Proving (ITP 2014)</em>, volume 8558 of <em>Lecture Notes in Computer
Science</em>, pages 128--143. Springer, 2014.
[ <a href="publi_bib.html#ITP14:Blazy:al">bib</a> |
<a href="papers/itp14.pdf">.pdf</a> ]
<blockquote>
Static analysis of binary code is challenging for several
reasons. In particular, standard static analysis
techniques operate over control flow graphs, which are not available
when dealing with self-modifying programs which can modify
their own code at runtime.
We formalize in the Coq proof assistant some key abstract
interpretation techniques that automatically extract memory safety
properties from binary code. Our analyzer is formally proved
correct and has been run on several self-modifying challenges,
provided by Cai et al in their PLDI 2007 paper.
</blockquote>
<p>
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="WCET14:Maroneze:al">16</a>]
</td>
<td class="bibtexitem">
André Maroneze, Sandrine Blazy, David Pichardie, and Isabelle Puaut.
A formally verified wcet estimation tool.
In <em>14th International Workshop on Worst-Case Execution Time
Analysis, WCET 2014, July 8, 2014, Ulm, Germany</em>, volume 39, pages 11--20.
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014.
[ <a href="publi_bib.html#WCET14:Maroneze:al">bib</a> |
<a href="papers/wcet14.pdf">.pdf</a> ]
<blockquote>
The application of formal methods in the development of safety-critical
embedded software is recommended in order to provide strong guarantees about
the absence of software errors. In this context, WCET
estimation tools constitute an important element to be formally verified.
We present a formally verified WCET estimation tool, integrated to the formally
verified CompCert C compiler. Our tool comes with a machine-checked proof which
ensures that its WCET estimates are safe.
Our tool operates over C programs and is composed of two main parts,
a loop bound estimation and an Implicit Path Enumeration Technique (IPET)-based
WCET calculation method.
We evaluated the precision of the WCET estimates on a reference benchmark and
obtained results which are competitive with state-of-the-art WCET estimation
techniques.
</blockquote>
<p>
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="POPL14:Azevedo:al">17</a>]
</td>
<td class="bibtexitem">
Arthur Azevedo de Amorim, Nathan Collins, André DeHon, Delphine Demange,
Catalin Hritcu, David Pichardie, Benjamin Pierce, Randy Pollack, and Andrew
Tolmach.
A verified information-flow architecture.
In <em>Proc. of the 41th ACM SIGPLAN-SIGACT Symposium on Principles
of Programming Languages, POPL 2014</em>, pages 165--178. ACM, 2014.
[ <a href="publi_bib.html#POPL14:Azevedo:al">bib</a> |
<a href="papers/popl14.pdf">.pdf</a> ]
<blockquote>
SAFE is a clean-slate design for a highly secure computer system,
with pervasive mechanisms for tracking and limiting information
flows. At the lowest level, the SAFE hardware supports
fine-grained programmable tags, with efficient and flexible propagation
and combination of tags as instructions are executed. The
operating system virtualizes these generic facilities to present
an information-flow abstract machine that allows user programs to
label sensitive data with rich confidentiality policies. We
present a formal, machine-checked model of the key hardware and
software mechanisms used to control information flow in SAFE and
an end- to-end proof of noninterference for this model.
</blockquote>
<p>
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="VSTTE13:Blazy:al">18</a>]
</td>
<td class="bibtexitem">
Sandrine Blazy, André Maroneze, and David Pichardie.
Formal verification of loop bound estimation for WCET analysis.
In <em>Proc. of the 5th Working Conference on Verified Software:
Theories, Tools, and Experiments (VSTTE 2013)</em>, volume 8164 of <em>Lecture
Notes in Computer Science</em>, pages 281--303. Springer-Verlag, 2013.
[ <a href="publi_bib.html#VSTTE13:Blazy:al">bib</a> |
<a href="papers/vstte13.pdf">.pdf</a> ]
<blockquote>
Worst-case execution time (WCET) estimation tools are complex
pieces of software performing tasks such as computation on
control flow graphs (CFGs) and bound calculation.
In this paper, we present a formal verification (in Coq) of a loop bound
estimation. It relies on program slicing and bound calculation.
The work has been integrated into the CompCert verified C compiler.
Our verified analyses directly operate on non-structured CFGs. We
extend the CompCert RTL intermediate language with a notion of loop
nesting (a.k.a. weak topological ordering on CFGs) that is useful for
reasoning on CFGs.
The automatic extraction of our loop bound estimation into OCaml yields
a program with competitive results, obtained from experiments on a
reference benchmark for WCET bound estimation tools.
</blockquote>
<p>
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="SAS13:Blazy:al">19</a>]
</td>
<td class="bibtexitem">
Sandrine Blazy, Vincent Laporte, André Maroneze, and David Pichardie.
Formal verification of a C value analysis based on abstract
interpretation.
In <em>Proc. of the 20th Static Analysis Symposium (SAS 2013)</em>,
volume 7935 of <em>Lecture Notes in Computer Science</em>, pages 324--344.
Springer-Verlag, 2013.
[ <a href="publi_bib.html#SAS13:Blazy:al">bib</a> |
<a href="papers/sas13.pdf">.pdf</a> ]
<blockquote>
Static analyzers based on abstract interpretation are complex
pieces of software implementing delicate algorithms. Even if
static analysis techniques are well understood, their
implementation on real languages is still error-prone.
This paper presents a formal verification using the Coq proof
assistant: a formalization of a value analysis (based on abstract
interpretation), and a soundness proof of the value analysis. The
formalization relies on generic interfaces. The mechanized proof
is facilitated by a translation validation of a Bourdoncle
fixpoint iterator.
The work has been integrated into the CompCert verified
C-compiler. Our verified analysis directly operates over an
intermediate language of the compiler having the same
expressiveness as C. The automatic extraction of our value
analysis into OCaml yields a program with competitive results,
obtained from experiments on a number of benchmarks and
comparisons with the Frama-C tool.
</blockquote>
<p>
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="POPL13:Demange:al">20</a>]
</td>
<td class="bibtexitem">
Delphine Demange, Vincent Laporte, Lei Zhao, David Pichardie, Suresh
Jagannathan, and Jan Vitek.
Plan B: A buffered memory model for Java.
In <em>Proc. of the 40th ACM SIGPLAN-SIGACT Symposium on Principles
of Programming Languages, POPL 2013</em>. ACM, 2013.
[ <a href="publi_bib.html#POPL13:Demange:al">bib</a> |
<a href="papers/popl13.pdf">.pdf</a> ]
<blockquote>
Recent advances in verification have made it possible to envision trusted
implementations of real-world languages. Java with its type-safety and
fully specified semantics would appear to be an ideal candidate; yet, the
complexity of the translation steps used in production virtual machines
have made it a challenging target for verifying compiler technology. One
of Java's key innovations, its memory model, poses significant obstacles
to such an endeavor. The Java Memory Model is an ambitious attempt at
specifying the behavior of multithreaded programs in a portable, hardware
agnostic, way. While experts have an intuitive grasp of the properties
that the model should enjoy, the specification is complex and not
well-suited for integration within a verifying compiler infrastructure.
Moreover, the specification is given in an axiomatic style that is distant
from the intuitive reordering-based reasonings traditionally used to
justify or rule out behaviors, and ill suited to the kind of operational
reasoning one would expect to employ in a compiler. This paper takes a
step back, and introduces a Buffered Memory Model (BMM) for
Java. We choose a pragmatic point in the design space sacrificing
generality in favor of a model that is fully characterized in terms of the
reorderings it allows, amenable to formal reasoning, and which can be
efficiently applied to a specific hardware family, namely x86
multiprocessors. Although the BMM restricts the reorderings compilers are
allowed to perform, it serves as the key enabling device to achieving a
verification pathway from bytecode to machine instructions. Despite its
restrictions, we show that it is backwards compatible with the Java Memory
Model and that it does not cripple performance on TSO architectures.
</blockquote>
<p>
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="MSCS13:Barthe:Pichardie:Rezk">21</a>]
</td>
<td class="bibtexitem">
Gilles Barthe, David Pichardie, and Tamara Rezk.
A certified lightweight non-interference Java bytecode verifier.
<em>Mathematical Structures in Computer Science (MSCS)</em>,
23(5):1032--1081, 2013.
[ <a href="publi_bib.html#MSCS13:Barthe:Pichardie:Rezk">bib</a> |
<a href="papers/mscs13.pdf">.pdf</a> ]
<blockquote>
Non-interference guarantees the absence of illicit information
flow throughout program execution. It can be enforced by appropriate
information flow type systems. Much of previous work on type systems for
non-interference has focused on calculi or high-level programming languages,
and existing type systems for low-level languages typically omit objects,
exceptions, and method calls. We define an information flow type system for
a sequential JVM-like language that includes all these programming features,
and we prove, in the Coq proof assistant, that it guarantees non-interference.
An additional benefit of the formalization is that we have extracted from our
proof a certified lightweight bytecode verifier for information flow. Our work
provides, to our best knowledge, the first sound and certified information
flow type system for such an expressive fragment of the JVM.
</blockquote>
<p>
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="LMCS12:Jensen:Kirchner:Pichardie">22</a>]
</td>
<td class="bibtexitem">
Thomas Jensen, Florent Kirchner, and David Pichardie.
Secure the clones: Static enforcement of policies for secure object
copying.
<em>Logical Methods in Computer Science (LMCS)</em>, 8(2), 2012.
[ <a href="publi_bib.html#LMCS12:Jensen:Kirchner:Pichardie">bib</a> |
<a href="papers/lmcs12.pdf">.pdf</a> ]
<blockquote>
Exchanging mutable data objects with untrusted code is a delicate
matter because of the risk of creating a data space that is accessible by
an attacker. Consequently, secure programming guidelines for Java stress the
importance of using defensive copying before accepting or handing out
references to an internal mutable object. However, implementation of a copy
method (like clone()) is entirely left to the programmer. It may not provide a
sufficiently deep copy of an object and is subject to overriding by a
malicious subclass. Currently no language-based mechanism supports secure
object cloning. This paper proposes a type-based annotation system for
defining modular copy policies for class-based object-oriented programs. A
copy policy specifies the maximally allowed sharing between an object and its
clone. We present a static enforcement mechanism that will guarantee that all
classes fulfil their copy policy, even in the presence of overriding of copy
methods, and establish the semantic correctness of the overall approach in
Coq. The mechanism has been implemented and experimentally evaluated on clone
methods from several Java libraries.
</blockquote>
<p>
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="ESOP12:Barthe:demange:Pichardie">23</a>]
</td>
<td class="bibtexitem">
Gilles Barthe, Delphine Demange, and David Pichardie.
A formally verified SSA-based middle-end - Static Single
Assignment meets CompCert.
In <em>Proc. of 21th European Symposium on Programming (ESOP 2012)</em>,
volume 7211 of <em>Lecture Notes in Computer Science</em>, pages 47--66.
Springer-Verlag, 2012.
[ <a href="publi_bib.html#ESOP12:Barthe:demange:Pichardie">bib</a> |
<a href="papers/esop12.pdf">.pdf</a> ]
<blockquote>
CompCert is a formally verified compiler that generates compact
and efficient PowerPC, ARM and x86 code for a large and realistic subset
of the C language. However, CompCert foregoes using Static Single
Assignment (SSA), an intermediate representation that allows for
writing simpler and faster optimizers, and is used by many
compilers. In fact, it has remained an open problem to verify
formally a SSA-based compiler middle-end.
We report on a formally verified, SSA-based, middle-end for
CompCert. Our middle-end performs conversion from CompCert
intermediate form to SSA form, optimization of SSA programs,
including Global Value Numbering, and transforming out of SSA to
intermediate form. In addition to provide the first formally
verified SSA-based middle-end, we address two problems
raised by Leroy: giving a simple and intuitive formal
semantics to SSA, and leveraging the global properties
of SSA to reason locally about program optimizations.
</blockquote>
<p>
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="CPP11:Besson:Cornilleau:Pichardie">24</a>]
</td>
<td class="bibtexitem">
Frédéric Besson, Pierre-Emmanuel Cornilleau, and David Pichardie.
Modular SMT proofs for fast reflexive checking inside Coq.
In <em>Proc. of the 1st International Conference on Certified
Programs and Proofs (CPP 2011)</em>, volume 7086 of <em>Lecture Notes in
Computer Science</em>, pages 151--166. Springer-Verlag, 2011.
[ <a href="publi_bib.html#CPP11:Besson:Cornilleau:Pichardie">bib</a> |
<a href="papers/cpp11.pdf">.pdf</a> ]
<blockquote>
We present a new methodology for exchanging unsatisfiability
proofs between an untrusted SMT solver and a sceptical proof
assistant with computation capabilities like Coq. We advocate
modular SMT proofs that separate boolean reasoning and theory
reasoning; and structure the communication between theories
using Nelson-Oppen combination scheme. We present the design
and implementation of a Coq reflexive verifier that is modular
and allows for fine-tuned theory-specific verifiers. The
current verifier is able to verify proofs for quantifier-free
formulae mixing linear arithmetic and uninterpreted functions.
Our proof generation scheme benefits from the efficiency of
state-of-the-art SMT solvers while being independent from a
specific SMT solver proof format. Our only requirement for the
SMT solver is the ability to extract unsat cores and generate
boolean models. In practice, unsat cores are relatively small
and their proof is obtained with a modest overhead by our
proof-producing prover. We present experiments assessing the
feasibility of the approach for benchmarks obtained from the
SMT competition.
</blockquote>
<p>
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="ESOP11:Jensen:Kirchner:Pichardie">25</a>]
</td>
<td class="bibtexitem">
Thomas Jensen, Florent Kirchner, and David Pichardie.
Secure the clones: Static enforcement of policies for secure object
copying.
In <em>Proc. of 20th European Symposium on Programming (ESOP 2011)</em>,
volume 6602 of <em>Lecture Notes in Computer Science</em>, pages 317--337.
Springer-Verlag, 2011.
[ <a href="publi_bib.html#ESOP11:Jensen:Kirchner:Pichardie">bib</a> |
<a href="papers/esop11.pdf">.pdf</a> ]
<blockquote>
Exchanging mutable data objects with untrusted code is a delicate
matter because of the risk of creating a data space that is
accessible by an attacker. Consequently, secure programming guidelines for
Java stress the importance of using defensive copying before accepting or
handing out references to an internal mutable object.<p>
However, implementation of a copy method (like clone()) is entirely
left to the programmer. It may not provide a sufficiently deep copy of
an object and is subject to overriding by a malicious sub-class. Currently
no language-based mechanism supports secure object cloning. <p>
This paper proposes a type-based annotation system for defining modular
copy policies for class-based object-oriented programs.
A copy policy specifies the maximally allowed sharing between an
object and its clone. We present a static
enforcement mechanism that will guarantee that all classes fulfill their
copy policy, even in the presence of overriding of copy methods, and
establish the semantic correctness of the overall approach in Coq.<p>
The mechanism has been implemented and experimentally evaluated on
clone methods from several Java libraries.
</blockquote>
<p>
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="TSI11:Cachera:Pichardie">26</a>]
</td>
<td class="bibtexitem">
David Cachera and David Pichardie.
Programmation d'un interpréteur abstrait certifié en logique
constructive.
<em>Technique et Science Informatiques (TSI)</em>, 30(4):381--408, 2011.
[ <a href="publi_bib.html#TSI11:Cachera:Pichardie">bib</a> ]
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="BYTECODE10:Pichardie">27</a>]
</td>
<td class="bibtexitem">
David Pichardie, editor.
<em>Fifth Workshop on Bytecode Semantics, Verification, Analysis and
Transformation (Bytecode 2010). Proceedings</em>, Electronic Notes in Theoretical
Computer Science, 2010.
[ <a href="publi_bib.html#BYTECODE10:Pichardie">bib</a> ]
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="FOVEOOS10:sawja">28</a>]
</td>
<td class="bibtexitem">
Laurent Hubert, Nicolas Barré, Frédéric Besson, Delphine Demange, Thomas
Jensen, Vincent Monfort, David Pichardie, and Tiphaine Turpin.
Sawja: Static Analysis Workshop for Java.
In <em>Proc. of the 1st International Conference on Formal
Verification of Object-Oriented Software (FoVeOOS 2010)</em>, volume 6461 of <em>
Lecture Notes in Computer Science</em>, pages 92--106. Springer-Verlag, 2010.
[ <a href="publi_bib.html#FOVEOOS10:sawja">bib</a> |
<a href="papers/foveoos10.pdf">.pdf</a> ]
<blockquote>
Static analysis is a powerful technique for automatic verification
of programs but raises major engineering challenges when developing
a full-fledged analyzer for a realistic language such as Java.
Efficiency and precision of such a tool rely partly on low level
components which only depend on the syntactic structure of the
language and therefore should not be redesigned for each
implementation of a new static analysis. This paper describes the
Sawja library: a static analysis workshop fully compliant with
Java 6 which provides OCaml modules for efficiently
manipulating Java bytecode programs. We present the main features
of the library, including i) efficient functional data-structures
for representing a program with implicit sharing and lazy parsing,
ii) an intermediate stack-less representation, and iii) fast
computation and manipulation of complete programs. We provide
experimental evaluations of the different features with respect to
time, memory and precision.
</blockquote>
<p>
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="APLAS10:Demange:Jensen:Pichardie">29</a>]
</td>
<td class="bibtexitem">
Delphine Demange, Thomas Jensen, and David Pichardie.
A provably correct stackless intermediate representation for Java
bytecode.
In <em>Proc. of the 8th Asian Symposium on Programming Languages and
Systems (APLAS 2010)</em>, volume 6461 of <em>Lecture Notes in Computer
Science</em>, pages 97--113. Springer-Verlag, 2010.
[ <a href="publi_bib.html#APLAS10:Demange:Jensen:Pichardie">bib</a> |
<a href="papers/aplas10.pdf">.pdf</a> ]
<blockquote>
The Java virtual machine executes stack-based bytecode. The
intensive use of an operand stack has been identified as a
major obstacle for static analysis and it is now common for
static analysis tools to manipulate a stackless
intermediate representation (IR) of bytecode programs.
This paper provides such a bytecode
transformation, describes its semantic
correctness and evaluates its performance.
We provide the semantic foundations for proving that an initial
program and its IR behave similarly, in particular with respect
to object creation and throwing of exceptions. The correctness
of this transformation is proved with respect to a relation on
execution traces taking into account that the object allocation
order is not preserved by the transformation.
</blockquote>
<p>
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="ESORICS10:Hubert:Pichardie">30</a>]
</td>
<td class="bibtexitem">
Laurent Hubert, Thomas Jensen, Vincent Monfort, and David Pichardie.
Enforcing secure object initialization in Java.
In <em>Proc. of the 15th European Symposium on Research in Computer
Security (ESORICS 2010)</em>, volume 6345 of <em>Lecture Notes in Computer
Science</em>, pages 101--115. Springer-Verlag, 2010.
[ <a href="publi_bib.html#ESORICS10:Hubert:Pichardie">bib</a> |
<a href="papers/esorics10.pdf">.pdf</a> ]
<blockquote>
Sun and the CERT recommend for secure Java development to not
allow partially initialized objects to be accessed. The CERT considers the
severity of the risks taken by not following this recommendation as
high. The solution currently used to enforce object initialization is
to implement a coding pattern proposed by Sun, which is not formally checked.
We propose a modular type system to formally specify the initialization policy
of libraries or programs and a type checker to statically check at load time
that all loaded classes respect the policy. This allows to prove the absence
of bugs which have allowed some famous privilege escalations in Java. Our
experimental results show that our safe default policy allows to prove 91% of
classes of java.lang, java.security and
javax.security safe without any annotation and by adding 57 simple
annotations we proved all classes but four safe. The type system and its
soundness theorem have been formalized and machine checked using Coq.
</blockquote>
<p>
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="ITP10:Cachera:Pichardie">31</a>]
</td>
<td class="bibtexitem">
David Cachera and David Pichardie.
A certified denotational abstract interpreter.
In <em>Proc. of International Conference on Interactive Theorem
Proving (ITP-10)</em>, volume 6172 of <em>Lecture Notes in Computer Science</em>,
pages 9--24. Springer-Verlag, 2010.
[ <a href="publi_bib.html#ITP10:Cachera:Pichardie">bib</a> |
<a href="papers/itp10.pdf">.pdf</a> ]
<blockquote>
Abstract Interpretation proposes advanced techniques for
static analysis of programs that raise specific challenges for
machine-checked soundness proofs. Most classical dataflow analysis
techniques iterate operators on lattices without infinite ascending
chains. In contrast, abstract interpreters are looking for fixpoints
in infinite lattices where widening and narrowing are used for
accelerating the convergence. Smart iteration strategies are crucial
when using such accelerating operators because they directly impact
the precision of the analysis diagnostic. In this paper, we show
how we manage to program and prove correct in Coq an abstract
interpreter that uses iteration strategies based on program syntax.
A key component of the formalization is the introduction of an
intermediate semantics based on a generic least-fixpoint operator
on complete lattices and allows us to decompose the soundness proof in an
elegant manner.
</blockquote>
<p>
</td>
</tr>
<tr valign="top">
<td align="right" class="bibtexnumber">
[<a name="TGC10:Besson:Jensen:Pichardie:Turpin">32</a>]