Pavol Černý

Welcome!

  • I am an assistant professor in the ECEE department at CU Boulder.
  • My research areas are computer-aided verification and programming languages, with focus on program synthesis. I recently worked on applications in networking, artificial intelligence, and software engineering.
  • I am fortunate to work with a great group of PhD students. We are members of CUPLV. I am looking for postdocs and PhD students who are enthusiastic about verification and programming languages.
  • I teach undergraduate courses on (concurrent) programming and graduate courses on computer-aided verification and program synthesis.

News

Current Projects

Program synthesis for networks

Nets

Programming models [PLDI16] and program synthesis algorithms [PLDI15, DISC16, FMCAD16, CAV17] to help developers with tricky distributed systems issues in software-defined networking.

ML+PL for performance and security

Nets

Machine learning algorithms and programming languages techniques for finding performance [AAAI18] and security [TACAS17] bugs in software.

Learning typestates

Nets

Automata-theoretic learning algorithms for inference of classic typestates for Java [POPL05] and input-output typestates for Android [ICSE18].

Students

Alumni

  • Nilesh Jagnik. MS, Spring 2016. First employment: Google.
  • Parker Evans. (Undergraduate) Discovery Learning Apprenticeship, 2013-14.
  • Prabhash Krishnan (2015-16), Aniket Lata (2015-16), Krishna Sripada (2015-16), Vaibhav Singh (2014-15). Graduate Independent Study.
  • Andrew Dudney (Fall 2016). Undergraduate Independent Study.

Student awards

  • Saeid Tizpaz Niari. ECEE Departmental Outstanding Gold Research Award. 2018.
  • Jedidiah McClurg. Computer Science Departmental Outstanding Research Award. 2017.
  • Saeid Tizpaz Niari. Second prize, Microsoft Research Open Source Challenge. 2016.

Open positions

We are looking for enthusiastic PhD students and postdocs to join CUPLV. Please send me an email if you are interested in research on program verification and program synthesis.

Current Projects

See the home tab for current projects.

Past Projects

Streaming transducers

Nets

Streaming string transducers [POPL11] are as appealing a model for regular string transformations as deterministic finite automata are for regular languages. The transformations definable by streaming string transducers are exactly those that are definable by classical two-way transducers and monadic second-order logic [FSTTCS10].

Simulation distances

Nets

Standard verification tools return a yes/no answer that indicates whether a system satisfies its specification. However, not all correct implementations are equally good, and not all incorrect implementations are equally bad. Simulation distances [CONCUR10,EMSOFT12,GandALF12] capture a finer and more quantitative view of the relationship between specifications and systems.

Quantitative abstraction refinement

Nets

To enable efficient static analysis of programs for estimating the value of a quantitative property such as worst-case execution time, we need to abstract the program. We have proposed an abstract interpretation technique to reason about quantitative properties [POPL13], and applied it to worst-case execution time analysis [ESOP15].

Synchronization synthesis

Nets

Our program synthesis techniques for concurrency [CAV13,CAV14,CAV15b] allow programmers to program assuming a friendly, non-preemptive scheduler, and our synthesis procedure inserts synchronization to ensure that the final program works even with a standard, more aggressive, preemptive scheduler. The correctness specification is implicit, inferred from the non-preemptive behavior.

Software model checking for confidentiality

Nets

A specification framework for confidentiality [ICALP06], novel decision procedures for finite state systems [TACAS07] and for classes of programs [CSL09], and abstraction-based program analysis techniques [CAV09].

Courses at CU Boulder

  • ECEN 1310: Programming for Engineers. Spring 2018.
  • ECEN 5139, CSCI 5135: Computer-Aided Verification. Fall 2017.
  • ECEN 4313, CSCI 4830: Concurrent Programming. Spring 2017.
  • ECEN 5033, CSCI 7000-005: Program Synthesis. Fall 2016.
  • ECEN 4003, CSCI 4830: Concurrent Programming. Spring 2016.
  • ECEN 5033, CSCI 7000-005: Program Synthesis. Fall 2015.
  • ECEN 4003, CSCI 4830: Concurrent Programming. Spring 2015.
  • ECEN 5139, CSCI 5135: Computer-Aided Verification. Fall 2014.
  • ECEN 5033, CSCI 7000-007: Concurrent Programming. Spring 2014.
  • ECEN 5139, CSCI 5135: Computer-Aided Verification. Fall 2013.
  • ECEN 5033, CSCI 7000-007: Program Synthesis. Spring 2013.

Previous Courses

  • Programming Paradigms for Concurrency. Co-instructor, Fall 2010, IST Austria and TU Wien.
  • CIS 399: C++ programming. Instructor, Spring 2009, University of Pennsylvania.
  • CSE 399: C/C++ programming. Co-instructor, Spring 2006, University of Pennsylvania.
  • CIS 511: Theory of Computation. TA, Spring 2005, University of Pennsylvania.
  • CSE 482: Logic in Computer Science. TA, Fall 2004, University of Pennsylvania.

Program committees

  • ATVA 2018, PC member
  • CAV 2018, PC member
  • POPL 2018, PC member
  • CAV 2016, PC member
  • EC2 2016, workshop PC chair
  • TACAS 2016, PC member
  • POPL 2016, ERC member
  • GandALF 2015, PC member
  • SYNT 2015, workshop PC chair
  • EC2 2015, PC member
  • PLVNET 2015, workshop PC chair
  • CAV 2014, PC member
  • EMSOFT 2014, PC member
  • SYNT 2014, workshop PC member
  • MEMICS 2011, workshop PC member

Funding

Publications (DBLP, Google Scholar)

Selective conferences

  • Starling: Callback Typestates for Android Classes New!
    Arjun Radhakrishna, Nicholas Lewchenko, Shawn Meier, Sergio Mover, Krishna Chaitanya Sripada, Damien Zufferey, Bor-Yuh Evan Chang, Pavol Černý.
    ICSE, 2018.
    [pdf]
  • Differential Performance Debugging with Discriminant Regression Trees. New!
    Saeid Tizpaz-Niari, Pavol Černý, Bor-Yuh Evan Chang, Ashutosh Trivedi.
    AAAI, 2018.
    [pdf]
  • Synchronization Synthesis for Network Programs. New!
    Jedidiah McClurg, Hossein Hojjat, Pavol Černý.
    CAV, 2017.
    [pdf]
  • Discriminating Traces with Time. New!
    Saeid Tizpaz-Niari, Pavol Černý, Bor-Yuh Evan Chang, Sriram Sankaranarayanan, Ashutosh Trivedi.
    TACAS, 2017.
    [pdf]
  • Optimizing Horn Solvers for Network Repair. 
    Hossein Hojjat, Philipp Ruemmer, Jedidiah McClurg, Pavol Černý, Nate Foster.
    FMCAD, 2016.
    [pdf]
  • Optimal Consistent Network Updates in Polynomial Time. 
    Pavol Černý, Nate Foster, Nilesh Jagnik, Jedidiah McClurg.
    DISC, 2016.
    [pdf]
  • Event-driven network programming. 
    Jedidiah McClurg, Hossein Hojjat, Nate Foster, Pavol Černý.
    PLDI, 2016.
    [pdf]
  • Synthesis Through Unification. 
    Rajeev Alur, Pavol Černý, Arjun Radhakrishna.
    CAV, 2015.
    [pdf]
  • From Non-preemptive to Preemptive Scheduling Using Synchronization Synthesis. 
    Pavol Černý, Edmund M. Clarke, Thomas A. Henzinger, Arjun Radhakrishna, Leonid Ryzhyk, Roopsha Samanta, Thorsten Tarrach.
    CAV, 2015.
    [pdf]
  • Segment Abstraction for Worst-Case Execution Time Analysis. 
    Pavol Černý, Thomas A. Henzinger, Laura Kovács, Arjun Radhakrishna, Jakob Zwirchmayr.
    ESOP, 2015.
    [pdf]
  • Efficient synthesis of network updates. 
    Jedidiah McClurg, Hossein Hojjat, Pavol Černý, Nate Foster.
    PLDI, 2015.
    [pdf]
  • Regression-Free Synthesis for Concurrency. 
    Pavol Černý, Thomas A. Henzinger, Arjun Radhakrishna, Leonid Ryzhyk, Thorsten Tarrach.
    CAV, 2014.
    [pdf]
  • Efficient Synthesis for Concurrency by Semantics-Preserving Transformations. 
    Pavol Černý, Thomas A. Henzinger, Arjun Radhakrishna, Leonid Ryzhyk, Thorsten Tarrach.
    CAV, 2013.
    [pdf]
  • Quantitative abstraction refinement. 
    Pavol Černý, Thomas A. Henzinger, Arjun Radhakrishna.
    POPL, 2013.
    [pdf]
  • Synthesis from incompatible specifications. 
    Pavol Černý, Sivakanth Gopi, Thomas A. Henzinger, Arjun Radhakrishna, Nishant Totla.
    EMSOFT, 2012.
    [pdf]
  • Interface Simulation Distances 
    Pavol Černý, Martin Chmelik, Thomas A. Henzinger, Arjun Radhakrishna.
    GandALF, 2012.
    [pdf]
  • Quantitative Synthesis for Concurrent Programs. 
    Pavol Černý, Krishnendu Chatterjee, Thomas A. Henzinger, Arjun Radhakrishna, Rohit Singh.
    CAV, 2011.
    [pdf]
  • The Complexity of Quantitative Information Flow Problems. 
    Pavol Černý, Krishnendu Chatterjee, Thomas A. Henzinger.
    CSF, 2011.
    [pdf]
  • Streaming transducers for algorithmic verification of single-pass list-processing programs. 
    Rajeev Alur, Pavol Černý.
    POPL, 2011.
    [pdf]
  • Model Checking of Linearizability of Concurrent List Implementations. 
    Pavol Černý, Arjun Radhakrishna, Damien Zufferey, Swarat Chaudhuri, Rajeev Alur.
    CAV, 2010.
    [pdf]
  • Simulation Distances. 
    Pavol Černý, Thomas A. Henzinger, Arjun Radhakrishna.
    CONCUR, 2010.
    [pdf]
  • Automated Analysis of Java Methods for Confidentiality. 
    Pavol Černý, Rajeev Alur.
    CAV, 2009.
    [pdf]
  • Algorithmic Analysis of Array-Accessing Programs. 
    Rajeev Alur, Pavol Černý, Scott Weinstein.
    CSL, 2009.
    [pdf]
  • Parallel programming with object assemblies. 
    Roberto Lublinerman, Swarat Chaudhuri, Pavol Černý.
    OOPSLA, 2009.
    [pdf]
  • Model Checking on Trees with Path Equivalences. 
    Rajeev Alur, Pavol Černý, Swarat Chaudhuri.
    TACAS, 2007.
    [pdf]
  • Preserving Secrecy Under Refinement. 
    Rajeev Alur, Pavol Černý, Steve Zdancewic.
    ICALP, 2006.
    [pdf]
  • Synthesis of interface specifications for Java classes. 
    Rajeev Alur, Pavol Černý, P. Madhusudan, Wonhong Nam.
    POPL, 2005.
    [pdf]

Journals

  • From non-preemptive to preemptive scheduling using synchronization synthesis.  
    Pavol Černý, Edmund M. Clarke, Thomas A. Henzinger, Arjun Radhakrishna, Leonid Ryzhyk, Roopsha Samanta, Thorsten Tarrach.
    Formal Methods in System Design  50: 97-139  (2017).
    [pdf]
  • Interface simulation distances. 
    Pavol Černý, Martin Chmelik, Thomas A. Henzinger, Arjun Radhakrishna.
    Theor. Comput. Sci.  560: 348-363  (2014).
    [pdf]
  • Simulation distances. 
    Pavol Černý, Thomas A. Henzinger, Arjun Radhakrishna.
    Theor. Comput. Sci.  413: 21-35  (2012).
    [pdf]
  • Algorithmic analysis of array-accessing programs. 
    Rajeev Alur, Pavol Černý, Scott Weinstein.
    ACM Trans. Comput. Log.  13: 27  (2012).
    [pdf]

Invited contributions

  • From boolean to quantitative synthesis. 
    Pavol Černý, Thomas A. Henzinger.
    EMSOFT, 2011.
    [pdf]
  • Quantitative Simulation Games. 
    Pavol Černý, Thomas A. Henzinger, Arjun Radhakrishna.
    Essays in Memory of Amir Pnueli, 2010.
    [pdf]
  • Expressiveness of streaming string transducers. 
    Rajeev Alur, Pavol Černý.
    FSTTCS, 2010.
    [pdf]

Workshops with proceedings

  • Performance search engine driven by prior knowledge of optimization. 
    Youngsung Kim, Pavol Černý, John M. Dennis.
    ARRAY@PLDI, 2015.
    [pdf]
  • Toward Synthesis of Network Updates. 
    Andrew Noyes, Todd Warszawski, Pavol Černý, Nate Foster.
    SYNT, 2013.
    [pdf]
  • Security Evaluation of ES&S Voting Machines and Election Management System. 
    Adam J. Aviv, Pavol Černý, Sandy Clark, Eric Cronin, Gaurav Shah, Micah Sherr, Matt Blaze.
    EVT, 2008.
    [pdf]

Theses

  • Software Model Checking for Confidentiality. 
    Pavol Černý.
    PhD thesis.  University of Pennsylvania,  Philadelphia, PA, USA.  2009.
    [pdf]
  • Verification by Abstract Interpretation of Parameterized Predicates. 
    Pavol Černý.
    DEA thesis.  Ecole normale superieure (ENS),  Paris, France.  2003.
    [pdf]

Report