SynGuar: Guaranteeing Generalization in Programming by Example

28/09/2021, 9am

Speaker

Bo Wang

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.