5 Search Results for "Gulwani, Sumit"


Document
Formal Proof and Analysis of an Incremental Cycle Detection Algorithm

Authors: Armaël Guéneau, Jacques-Henri Jourdan, Arthur Charguéraud, and François Pottier

Published in: LIPIcs, Volume 141, 10th International Conference on Interactive Theorem Proving (ITP 2019)


Abstract
We study a state-of-the-art incremental cycle detection algorithm due to Bender, Fineman, Gilbert, and Tarjan. We propose a simple change that allows the algorithm to be regarded as genuinely online. Then, we exploit Separation Logic with Time Credits to simultaneously verify the correctness and the worst-case amortized asymptotic complexity of the modified algorithm.

Cite as

Armaël Guéneau, Jacques-Henri Jourdan, Arthur Charguéraud, and François Pottier. Formal Proof and Analysis of an Incremental Cycle Detection Algorithm. In 10th International Conference on Interactive Theorem Proving (ITP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 141, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{gueneau_et_al:LIPIcs.ITP.2019.18,
  author =	{Gu\'{e}neau, Arma\"{e}l and Jourdan, Jacques-Henri and Chargu\'{e}raud, Arthur and Pottier, Fran\c{c}ois},
  title =	{{Formal Proof and Analysis of an Incremental Cycle Detection Algorithm}},
  booktitle =	{10th International Conference on Interactive Theorem Proving (ITP 2019)},
  pages =	{18:1--18:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-122-1},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{141},
  editor =	{Harrison, John and O'Leary, John and Tolmach, Andrew},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2019.18},
  URN =		{urn:nbn:de:0030-drops-110739},
  doi =		{10.4230/LIPIcs.ITP.2019.18},
  annote =	{Keywords: interactive deductive program verification, complexity analysis}
}
Document
Eventually Sound Points-To Analysis with Specifications

Authors: Osbert Bastani, Rahul Sharma, Lazaro Clapp, Saswat Anand, and Alex Aiken

Published in: LIPIcs, Volume 134, 33rd European Conference on Object-Oriented Programming (ECOOP 2019)


Abstract
Static analyses make the increasingly tenuous assumption that all source code is available for analysis; for example, large libraries often call into native code that cannot be analyzed. We propose a points-to analysis that initially makes optimistic assumptions about missing code, and then inserts runtime checks that report counterexamples to these assumptions that occur during execution. Our approach guarantees eventual soundness, which combines two guarantees: (i) the runtime checks are guaranteed to catch the first counterexample that occurs during any execution, in which case execution can be terminated to prevent harm, and (ii) only finitely many counterexamples ever occur, implying that the static analysis eventually becomes statically sound with respect to all remaining executions. We implement Optix, an eventually sound points-to analysis for Android apps, where the Android framework is missing. We show that the runtime checks added by Optix incur low overhead on real programs, and demonstrate how Optix improves a client information flow analysis for detecting Android malware.

Cite as

Osbert Bastani, Rahul Sharma, Lazaro Clapp, Saswat Anand, and Alex Aiken. Eventually Sound Points-To Analysis with Specifications. In 33rd European Conference on Object-Oriented Programming (ECOOP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 134, pp. 11:1-11:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{bastani_et_al:LIPIcs.ECOOP.2019.11,
  author =	{Bastani, Osbert and Sharma, Rahul and Clapp, Lazaro and Anand, Saswat and Aiken, Alex},
  title =	{{Eventually Sound Points-To Analysis with Specifications}},
  booktitle =	{33rd European Conference on Object-Oriented Programming (ECOOP 2019)},
  pages =	{11:1--11:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-111-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{134},
  editor =	{Donaldson, Alastair F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2019.11},
  URN =		{urn:nbn:de:0030-drops-108038},
  doi =		{10.4230/LIPIcs.ECOOP.2019.11},
  annote =	{Keywords: specification inference, static points-to analysis, runtime monitoring}
}
Document
Bridging the Gap Between General-Purpose and Domain-Specific Compilers with Synthesis

Authors: Alvin Cheung, Shoaib Kamil, and Armando Solar-Lezama

Published in: LIPIcs, Volume 32, 1st Summit on Advances in Programming Languages (SNAPL 2015)


Abstract
This paper describes a new approach to program optimization that allows general purpose code to benefit from the optimization power of domain-specific compilers. The key to this approach is a synthesis-based technique to raise the level of abstraction of general-purpose code to enable aggressive domain-specific optimizations. We have been implementing this approach in an extensible system called Herd. The system is designed around a collection of parameterized kernel translators. Each kernel translator is associated with a domain-specific compiler, and the role of each kernel translator is to scan the input code in search of code fragments that can be optimized by the domain-specific compiler embedded within each kernel translator. By leveraging general synthesis technology, it is possible to have a generic kernel translator that can be specialized by compiler developers for each domain-specific compiler, making it easy to build new domain knowledge into the overall system. We illustrate this new approach to build optimizing compilers in two different domains, and highlight research challenges that need to be addressed in order to achieve the ultimate vision.

Cite as

Alvin Cheung, Shoaib Kamil, and Armando Solar-Lezama. Bridging the Gap Between General-Purpose and Domain-Specific Compilers with Synthesis. In 1st Summit on Advances in Programming Languages (SNAPL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 32, pp. 51-62, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{cheung_et_al:LIPIcs.SNAPL.2015.51,
  author =	{Cheung, Alvin and Kamil, Shoaib and Solar-Lezama, Armando},
  title =	{{Bridging the Gap Between General-Purpose and Domain-Specific Compilers with Synthesis}},
  booktitle =	{1st Summit on Advances in Programming Languages (SNAPL 2015)},
  pages =	{51--62},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-80-4},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{32},
  editor =	{Ball, Thomas and Bodík, Rastislav and Krishnamurthi, Shriram and Lerner, Benjamin S. and Morriset, Greg},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SNAPL.2015.51},
  URN =		{urn:nbn:de:0030-drops-50162},
  doi =		{10.4230/LIPIcs.SNAPL.2015.51},
  annote =	{Keywords: compilers, domain-specific languages, program synthesis, cross compilation, verification}
}
Document
Approaches and Applications of Inductive Programming (Dagstuhl Seminar 13502)

Authors: Sumit Gulwani, Emanuel Kitzelmann, and Ute Schmid

Published in: Dagstuhl Reports, Volume 3, Issue 12 (2014)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13502 "Approaches and Applications of Inductive Programming". After a short introduction to inductive programming research, an overview of the talks and the outcomes of discussion groups is given.

Cite as

Sumit Gulwani, Emanuel Kitzelmann, and Ute Schmid. Approaches and Applications of Inductive Programming (Dagstuhl Seminar 13502). In Dagstuhl Reports, Volume 3, Issue 12, pp. 43-66, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@Article{gulwani_et_al:DagRep.3.12.43,
  author =	{Gulwani, Sumit and Kitzelmann, Emanuel and Schmid, Ute},
  title =	{{Approaches and Applications of Inductive Programming (Dagstuhl Seminar 13502)}},
  pages =	{43--66},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{3},
  number =	{12},
  editor =	{Gulwani, Sumit and Kitzelmann, Emanuel and Schmid, Ute},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.12.43},
  URN =		{urn:nbn:de:0030-drops-45078},
  doi =		{10.4230/DagRep.3.12.43},
  annote =	{Keywords: inductive program synthesis, end-user programming, universal artificial intelligence, constraint programming, probabilistic programming, cognitive mod}
}
Document
Software Synthesis (Dagstuhl Seminar 12152)

Authors: Rastislav Bodík, Sumit Gulwani, and Eran Yahav

Published in: Dagstuhl Reports, Volume 2, Issue 4 (2012)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 12152 ``Software Synthesis''. During the seminar, several participants presented their current research, ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar are put together in this paper. The rise of multiprocesser computers and of software verification as applied in industry combine to create an opportune moment for software synthesis. To facilitate research in this area, research from several fields of Computer Science presented tutorials on techniques they developed. This lead to (1) the definition of what challenges synthesis has to tackle in the future and (2) insights into how the several fields of synthesis are related. Finally, several groups described their experience with teaching synthesis to graduate and undergraduate students, demonstrating that synthesis is challenging for students but that they can also rise to the challenge and enjoy the field.

Cite as

Rastislav Bodík, Sumit Gulwani, and Eran Yahav. Software Synthesis (Dagstuhl Seminar 12152). In Dagstuhl Reports, Volume 2, Issue 4, pp. 21-38, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@Article{bodik_et_al:DagRep.2.4.21,
  author =	{Bod{\'\i}k, Rastislav and Gulwani, Sumit and Yahav, Eran},
  title =	{{Software Synthesis (Dagstuhl Seminar 12152)}},
  pages =	{21--38},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2012},
  volume =	{2},
  number =	{4},
  editor =	{Bod{\'\i}k, Rastislav and Gulwani, Sumit and Yahav, Eran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.4.21},
  URN =		{urn:nbn:de:0030-drops-35956},
  doi =		{10.4230/DagRep.2.4.21},
  annote =	{Keywords: Software Synthesis, Verification and Model Checking, Theorem Proving, Program Analysis, Programming by Demonstration, Program Derivation, Compiler Optimization}
}
  • Refine by Author
  • 2 Gulwani, Sumit
  • 1 Aiken, Alex
  • 1 Anand, Saswat
  • 1 Bastani, Osbert
  • 1 Bodík, Rastislav
  • Show More...

  • Refine by Classification
  • 1 Software and its engineering → Correctness
  • 1 Software and its engineering → Software performance
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Program analysis
  • 1 Theory of computation → Program verification

  • Refine by Keyword
  • 1 Compiler Optimization
  • 1 Program Analysis
  • 1 Program Derivation
  • 1 Programming by Demonstration
  • 1 Software Synthesis
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2019
  • 1 2012
  • 1 2014
  • 1 2015

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