Abstract
The increasing presence of multicore execution environments is stimulating the development of concurrent software, an inherently error-prone task that affects the trust on the reliability of third-party code. There is thus a pressing need of providing verifiable evidence on a concurrent software correctness. Certificate Translation provides a means to generate verification certificates for complex functional properties. This technique, consists on progressively transferring verification results for source programs along a sequence of compilation steps. In previous work, we have shown how to transform certificates of a sequential program in the presence of compiler optimizations. In this article, we have shown that it is possible to extend certificate translation to the verification of concurrent programs, based on an Owicki/Gries-like proof system for a shared memory model.
This work is partially funded by the EU projects Mobius and HATS, and by the Spanish project Desafios 10, and by the Community of Madrid project Prometidos.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Barthe, G., Grégoire, B., Heraud, S., Kunz, C., Pacalet, A.: Implementing a direct method for certificate translation. In: Breitman, K., Cavalcanti, A. (eds.) ICFEM 2009. LNCS, vol. 5885, pp. 541–560. Springer, Heidelberg (2009)
Barthe, G., Grégoire, B., Kunz, C., Rezk, T.: Certificate translation for optimizing compilers. ACM Transactions on :Programming Languages and Systems 31(5), 18:1–18:45 (2009)
Barthe, G., Kunz, C.: Certificate translation in abstract interpretation. In: Drossopoulou, S. (ed.) ESOP 2008. LNCS, vol. 4960, pp. 368–382. Springer, Heidelberg (2008)
Chaieb, A.: Proof-producing program analysis. In: Barkaoui, K., Cavalcanti, A., Cerone, A. (eds.) ICTAC 2006. LNCS, vol. 4281, pp. 287–301. Springer, Heidelberg (2006)
Flanagan, C., Freund, S.N., Qadeer, S.: Thread-modular verification for shared-memory programs. In: Le Métayer, D. (ed.) ESOP 2002. LNCS, vol. 2305, pp. 262–277. Springer, Heidelberg (2002)
Jones, C.B.: Tentative steps toward a development method for interfering programs. ACM Transactions on Programming Languages and Systems 5(4), 596–619 (1983)
Müller, P., Nordio, M.: Proof-transforming compilation of programs with abrupt termination. Technical Report 565, ETH Zurich (2007)
Necula, G.C.: Proof-carrying code. In: Principles of Programming Languages, pp. 106–119. ACM Press, New York (1997)
Nordio, M., Müller, P., Meyer, B.: Proof-transforming compilation of eiffel programs. In: Paige, R. (ed.) TOOLS-EUROPE. LNBIP. Springer, Heidelberg (2008)
O’Hearn, P.W.: Resources, concurrency and local reasoning. Theoretical Computer Science 375(1-3), 271–307 (2007)
Owicki, S., Gries, D.: An axiomatic proof technique for parallel programs. Acta Informatica Journal 6, 319–340 (1975)
Saabas, A., Uustalu, T.: Type systems for optimizing stack-based code. In: Huisman, M., Spoto, F. (eds.) Bytecode Semantics, Verification, Analysis and Transformation. Electronic Notes in Theoretical Computer Science, vol. 190(1), pp. 103–119. Elsevier, Amsterdam (2007)
Seo, S., Yang, H., Yi, K.: Automatic Construction of Hoare Proofs from Abstract Interpretation Results. In: Ohori, A. (ed.) APLAS 2003. LNCS, vol. 2895, pp. 230–245. Springer, Heidelberg (2003)
Seo, S., Yang, H., Yi, K., Han, T.: Goal-directed weakening of abstract interpretation results. ACM Transactions on Programming Languages and Systems 29(6), 39:1–39:39 (2007)
Vafeiadis, V., Parkinson, M.J.: A marriage of rely/guarantee and separation logic. In: Caires, L., Vasconcelos, V.T. (eds.) CONCUR 2007. LNCS, vol. 4703, pp. 256–271. Springer, Heidelberg (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kunz, C. (2010). Certificate Translation for the Verification of Concurrent Programs. In: Wirsing, M., Hofmann, M., Rauschmayer, A. (eds) Trustworthly Global Computing. TGC 2010. Lecture Notes in Computer Science, vol 6084. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15640-3_16
Download citation
DOI: https://doi.org/10.1007/978-3-642-15640-3_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15639-7
Online ISBN: 978-3-642-15640-3
eBook Packages: Computer ScienceComputer Science (R0)