Search Results

Documents authored by Banerjee, Anindya

Document
DOI: 10.4230/DARTS.3.2.4
Concurrent Data Structures Linked in Time (Artifact)

Authors: Germán Andrés Delbianco, Ilya Sergey, Aleksandar Nanevski, and Anindya Banerjee

Published in: DARTS, Volume 3, Issue 2, Special Issue of the 31st European Conference on Object-Oriented Programming (ECOOP 2017)

Abstract
This artifact provides the full mechanization in FCSL of the developments in the companion paper, "Concurrent Data Structures Linked in Time". In the latter, we propose a new method, based on a separation-style logic, for reasoning about concurrent objects with such linearization points. We embrace the dynamic nature of linearization points, and encode it as part of the data structure's auxiliary state, so that it can be dynamically modified in place by auxiliary code, as needed when some appropriate run-time event occurs. We illustrate the method by verifying (mechanically in FCSL) an intricate optimal snapshot algorithm due to Jayanti, as well as some clients. FCSL is the first completely formalized framework for mechanized verification of full functional correctness of fine-grained concurrent programs. It is implemented as an embedded domain-specific language (DSL) in the dependently-typed language of the Coq proof assistant, and is powerful enough to reason about programming features such as higher-order functions and local thread spawning. By incorporating a uniform concurrency model, based on state-transition systems and partial commutative monoids, FCSL makes it possible to build proofs about concurrent libraries in a thread-local, compositional way, thus facilitating scalability and reuse: libraries are verified just once, and their specifications are used ubiquitously in client-side reasoning.
Cite as

Germán Andrés Delbianco, Ilya Sergey, Aleksandar Nanevski, and Anindya Banerjee. Concurrent Data Structures Linked in Time (Artifact). In Special Issue of the 31st European Conference on Object-Oriented Programming (ECOOP 2017). Dagstuhl Artifacts Series (DARTS), Volume 3, Issue 2, pp. 4:1-4:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{delbianco_et_al:DARTS.3.2.4,
  author =	{Delbianco, Germ\'{a}n Andr\'{e}s and Sergey, Ilya and Nanevski, Aleksandar and Banerjee, Anindya},
  title =	{{Concurrent Data Structures Linked in Time (Artifact)}},
  pages =	{4:1--4:4},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2017},
  volume =	{3},
  number =	{2},
  editor =	{Delbianco, Germ\'{a}n Andr\'{e}s and Sergey, Ilya and Nanevski, Aleksandar and Banerjee, Anindya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.3.2.4},
  URN =		{urn:nbn:de:0030-drops-72850},
  doi =		{10.4230/DARTS.3.2.4},
  annote =	{Keywords: separation logic, linearization Points, concurrent snapshots, FCSL}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2017.8
Concurrent Data Structures Linked in Time

Authors: Germán Andrés Delbianco, Ilya Sergey, Aleksandar Nanevski, and Anindya Banerjee

Published in: LIPIcs, Volume 74, 31st European Conference on Object-Oriented Programming (ECOOP 2017)

Abstract
Arguments about correctness of a concurrent data structure are typically carried out by using the notion of linearizability and specifying the linearization points of the data structure's procedures. Such arguments are often cumbersome as the linearization points' position in time can be dynamic (depend on the interference, run-time values and events from the past, or even future), non-local (appear in procedures other than the one considered), and whose position in the execution trace may only be determined after the considered procedure has already terminated. In this paper we propose a new method, based on a separation-style logic, for reasoning about concurrent objects with such linearization points. We embrace the dynamic nature of linearization points, and encode it as part of the data structure's auxiliary state, so that it can be dynamically modified in place by auxiliary code, as needed when some appropriate run-time event occurs. We name the idea linking-in-time, because it reduces temporal reasoning to spatial reasoning. For example, modifying a temporal position of a linearization point can be modeled similarly to a pointer update in separation logic. Furthermore, the auxiliary state provides a convenient way to concisely express the properties essential for reasoning about clients of such concurrent objects. We illustrate the method by verifying (mechanically in Coq) an intricate optimal snapshot algorithm due to Jayanti, as well as some clients.
Cite as

Germán Andrés Delbianco, Ilya Sergey, Aleksandar Nanevski, and Anindya Banerjee. Concurrent Data Structures Linked in Time. In 31st European Conference on Object-Oriented Programming (ECOOP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 74, pp. 8:1-8:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{delbianco_et_al:LIPIcs.ECOOP.2017.8,
  author =	{Delbianco, Germ\'{a}n Andr\'{e}s and Sergey, Ilya and Nanevski, Aleksandar and Banerjee, Anindya},
  title =	{{Concurrent Data Structures Linked in Time}},
  booktitle =	{31st European Conference on Object-Oriented Programming (ECOOP 2017)},
  pages =	{8:1--8:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-035-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{74},
  editor =	{M\"{u}ller, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2017.8},
  URN =		{urn:nbn:de:0030-drops-72558},
  doi =		{10.4230/LIPIcs.ECOOP.2017.8},
  annote =	{Keywords: Separation logic, Linearization Points, Concurrent snapshots, FCSL}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2016.11
Relational Logic with Framing and Hypotheses

Authors: Anindya Banerjee, David A. Naumann, and Mohammad Nikouei

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Abstract
Relational properties arise in many settings: relating two versions of a program that use different data representations, noninterference properties for security, etc. The main ingredient of relational verification, relating aligned pairs of intermediate steps, has been used in numerous guises, but existing relational program logics are narrow in scope. This paper introduces a logic based on novel syntax that weaves together product programs to express alignment of control flow points at which relational formulas are asserted. Correctness judgments feature hypotheses with relational specifications, discharged by a rule for the linking of procedure implementations. The logic supports reasoning about program-pairs containing both similar and dissimilar control and data structures. Reasoning about dynamically allocated objects is supported by a frame rule based on frame conditions amenable to SMT provers. We prove soundness and sketch how the logic can be used for data abstraction, loop optimizations, and secure information flow.
Cite as

Anindya Banerjee, David A. Naumann, and Mohammad Nikouei. Relational Logic with Framing and Hypotheses. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{banerjee_et_al:LIPIcs.FSTTCS.2016.11,
  author =	{Banerjee, Anindya and Naumann, David A. and Nikouei, Mohammad},
  title =	{{Relational Logic with Framing and Hypotheses}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.11},
  URN =		{urn:nbn:de:0030-drops-68465},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.11},
  annote =	{Keywords: Relational Hoare logic, program equivalence, product programs, frame conditions, region logic}
}
Document
DOI: 10.4230/DagSemProc.03411.1
03411 Final Report – Language Based Security

Authors: Anindya Banerjee, Heiko Mantel, David Naumann, and Andrei Sabelfeld

Published in: Dagstuhl Seminar Proceedings, Volume 3411, Language-Based Security (2005)

Abstract
This paper summarizes the objectives and structure of a seminar with the same title, held from October 5th to 10th 2003 at Schloss Dagstuhl, Germany.
Cite as

Anindya Banerjee, Heiko Mantel, David Naumann, and Andrei Sabelfeld. 03411 Final Report – Language Based Security. In Language-Based Security. Dagstuhl Seminar Proceedings, Volume 3411, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{banerjee_et_al:DagSemProc.03411.1,
  author =	{Banerjee, Anindya and Mantel, Heiko and Naumann, David and Sabelfeld, Andrei},
  title =	{{03411  Final Report – Language Based Security}},
  booktitle =	{Language-Based Security},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{3411},
  editor =	{Anindya Banerjee and Heiko Mantel and David Naumann and Andrei Sabelfeld},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.03411.1},
  URN =		{urn:nbn:de:0030-drops-1724},
  doi =		{10.4230/DagSemProc.03411.1},
  annote =	{Keywords: Access control , information flow , noninterference , downgrading protocol analysis}
}
Document
DOI: 10.4230/DagSemProc.03411.2
03411 Abstracts Collection – Language Based Security

Authors: Anindya Banerjee, Heiko Mantel, David Naumann, and Andrei Sabelfeld

Published in: Dagstuhl Seminar Proceedings, Volume 3411, Language-Based Security (2005)

Abstract
From October 5th to 10th 2003,the Dagstuhl Seminar 03411 ``Language Based security'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar are put together in this paper.
Cite as

Anindya Banerjee, Heiko Mantel, David Naumann, and Andrei Sabelfeld. 03411 Abstracts Collection – Language Based Security. In Language-Based Security. Dagstuhl Seminar Proceedings, Volume 3411, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{banerjee_et_al:DagSemProc.03411.2,
  author =	{Banerjee, Anindya and Mantel, Heiko and Naumann, David and Sabelfeld, Andrei},
  title =	{{03411 Abstracts Collection – Language Based Security}},
  booktitle =	{Language-Based Security},
  pages =	{1--20},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{3411},
  editor =	{Anindya Banerjee and Heiko Mantel and David Naumann and Andrei Sabelfeld},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.03411.2},
  URN =		{urn:nbn:de:0030-drops-1731},
  doi =		{10.4230/DagSemProc.03411.2},
  annote =	{Keywords: Access control , information flow , noninterference , downgrading protocol analysis}
}
Document
DOI: 10.4230/DagSemRep.397
Language-Based Security (Dagstuhl Seminar 03411)

Authors: Anindya Banerjee, Heiko Mantel, David A. Naumann, and Andrei Sabelfeld

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Anindya Banerjee, Heiko Mantel, David A. Naumann, and Andrei Sabelfeld. Language-Based Security (Dagstuhl Seminar 03411). Dagstuhl Seminar Report 397, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{banerjee_et_al:DagSemRep.397,
  author =	{Banerjee, Anindya and Mantel, Heiko and Naumann, David A. and Sabelfeld, Andrei},
  title =	{{Language-Based Security (Dagstuhl Seminar 03411)}},
  pages =	{1--10},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{397},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.397},
  URN =		{urn:nbn:de:0030-drops-152779},
  doi =		{10.4230/DagSemRep.397},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact