SynGuar: Guaranteeing Generalization in Programming by Example
28/09/2021, 9am
Speaker
Abstract
Programming by Example (PBE) is a program synthesis paradigm in which the synthesizer creates a program that matches a set of given examples. In many applications of such synthesis (e.g., program repair or reverse engineering), we wish that the synthesized program generalizes well, i.e., has as few errors as possible on the unobserved examples. In this talk, I will present our recent work about achieving PAC-style generalization guarantee (low generalization error with high probability on i.i.d. samples) in PBE synthesis. Our approach dynamically calculates the sample size sufficient for generalization. We show how our methods can be used in 2 well-known program synthesis approaches: PROSE and STUN (synthesis through unification), for common string-manipulation PBEbenchmarks.
Speaker Bio
Bo Wang is a second-year PhD student at the National University of Singapore advised by Prateek Saxena. His research interests include program synthesis, programming by example, and program analysis. He has published in venues likeESEC/FSE, CHI, etc.