TMTodd Millstein

Todd Millstein

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Todd Millstein has a total of 57 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Tackling Ambiguity in User Intent for LLM-based Network Configuration Synthesis

    by Rajdeep Mondal, Nikolaj Bjorner, Todd Millstein, Alan Tang, George Varghese


  • Open Access

    Synthesizing Implication Lemmas for Interactive Theorem Proving

    by Ana Brendel, Aishwarya Sivaraman, Todd Millstein

    Interactive theorem provers (ITP) enable programmers to formally verify properties of their software systems. One burden for users of ITPs is identifying the necessary helper lemmas to complete a proof, for example those that define key inductive invariants. Existing approaches to lemma synthesis for ITPs have limited, if any, support for synthesizing implications : lemmas of the form P 1 ∧ ⋯ ∧ P n ⇒ Q . In this paper, we propose a technique and associated tool for synthesizing useful implication lemmas. Our approach employs a form of data-driven invariant inference to explore strengthenings of the current proof state, based on sample valuations of the current goal and assumptions. We have implemented our approach in a Rocq tactic called dilemma. We demonstrate its effectiveness in synthesizing necessary helper lemmas for proofs from the Verified Functional Algorithms textbook as well as from prior benchmark suites for lemma synthesis.


  • Open Access

    Tuning Random Generators: Property-Based Testing as Probabilistic Programming

    by Ryan Tjoa, Poorva Garg, Harrison Goldstein, Todd Millstein, Benjamin C. Pierce, Guy Van Den Broeck

    Property-based testing validates software against an executable specification by evaluating it on randomly generated inputs. The standard way that PBT users generate test inputs is via generators that describe how to sample test inputs through random choices. To achieve a good distribution over test inputs, users must tune their generators, i.e., decide on the weights of these individual random choices. Unfortunately, it is very difficult to understand how to choose individual generator weights in order to achieve a desired distribution, so today this process is tedious and limits the distributions that can be practically achieved. In this paper, we develop techniques for the automatic and offline tuning of generators. Given a generator with undetermined symbolic weights and an objective function, our approach automatically learns values for these weights that optimize for the objective. We describe useful objective functions that allow users to (1) target desired distributions and (2) improve the diversity and validity of their test cases. We have implemented our approach in a novel discrete probabilistic programming system, Loaded Dice, that supports differentiation and parameter learning, and use it as a language for generators. We empirically demonstrate that our approach is effective at optimizing generator distributions according to the specified objective functions. We also perform a thorough evaluation on PBT benchmarks, demonstrating that, when automatically tuned for diversity and validity, the generators exhibit a 3.1-7.4x speedup in bug finding.


  • Open Access

    If Layering is useful, why not Sublayering?

    by Rathin Singha, Rishabh Iyer, Charles Liu, Caleb Terrill, Todd Millstein, Scott Shenker, George Varghese

    The Internet's success arose from classical layering: protocols like TCP and Ethernet can be independently understood, changed, debugged, verified, and offloaded to hardware using a clean service interface between layers. To accrue the same benefits at a finer grain, we suggest sublayering, i.e., layering recursively within each layer. We show that the data link and routing layers have natural sublayers. However, while TCP intuitively decomposes into sub-functions (connection management, reliable delivery, congestion control) common state variables like sequence numbers and window sizes entangle these functions, making sublayering difficult. We propose an alternate sublayered TCP with equivalent functionality which enables easily changing congestion control and connection management. We also argue that sublayering can help create robust and verified Internet protocol implementations akin to seL4 for Operating Systems. To this end, we describe early experiments with a verified sublayered implementation of a simple bit-stuffing protocol using Coq, and a verified monolithic implementation of a lightweight TCP using Dafny. We end with a set of challenges for sublayered protocols.


  • Open Access

    Everything Is a Program (Even If It's Not) (Keynote)

    by Todd Millstein

    A brief discussion at a conference more than 15 years ago led to a collaborative research agenda that has been incredibly fun, intellectually challenging, and impactful. Internet protocols like BGP and DNS underlie everything that we do online, but they routinely break network security and reliability due to their complexity and fragility. While there are many moving parts and underlying causes, time and again the programming languages perspective has proven to be a powerful way to make progress. In short, everything is a program (even if it’s not), and once something is a program we can give it a precise semantics and bring to bear a host of techniques to reason about its behavior. I’ll illustrate this approach through examples from my work, but the ideas are applicable beyond computer networks. I’ll also distill some general lessons that I’ve learned about doing collaborative research and making an impact.

  • Open Access

    Bit Blasting Probabilistic Programs

    by Poorva Garg, Steven Holtzen, Guy Van Den Broeck, Todd Millstein

    Probabilistic programming languages (PPLs) are an expressive means for creating and reasoning about probabilistic models. Unfortunately hybrid probabilistic programs that involve both continuous and discrete structures are not well supported by today’s PPLs. In this paper we develop a new approximate inference algorithm for hybrid probabilistic programs that first discretizes the continuous distributions and then performs discrete inference on the resulting program. The key novelty is a form of discretization that we call bit blasting , which uses a binary representation of numbers such that a domain of 2 b discretized points can be succinctly represented as a discrete probabilistic program over poly b Boolean random variables. Surprisingly, we prove that many common continuous distributions can be bit blasted in a manner that incurs no loss of accuracy over an explicit discretization and supports efficient probabilistic inference. We have built a probabilistic programming system for hybrid programs called HyBit , which employs bit blasting followed by discrete probabilistic inference. We empirically demonstrate the benefits of our approach over existing sampling-based and symbolic inference approaches


  • Top Cited Papers
    Open Access

    What do LLMs need to Synthesize Correct Router Configurations?

    by Rajdeep Mondal, Alan Tang, Ryan Beckett, Todd Millstein, George Varghese

    We investigate whether Large Language Models (e.g., GPT-4) can synthesize correct router configurations with reduced manual effort. We find GPT-4 works very badly by itself, producing promising draft configurations but with egregious errors in topology, syntax, and semantics. Our strategy, that we call Verified Prompt Programming, is to combine GPT-4 with verifiers, and use localized feedback from the verifier to automatically correct errors. Verification requires a specification and actionable localized feedback to be effective. We show results for two use cases: translating from Cisco to Juniper configurations on a single router, and implementing a no-transit policy on multiple routers. While human input is still required, if we define the leverage as the number of automated prompts to the number of human prompts, our experiments show a leverage of 10X for Juniper translation, and 6X for implementing the no-transit policy, ending with verified configurations.


  • Open Access

    Lessons from the evolution of the Batfish configuration analysis tool

    by Matt Brown, Ari Fogel, Daniel Halperin, Victor Heorhiadi, Ratul Mahajan, Todd Millstein


  • Open Access

    Lightyear: Using Modularity to Scale BGP Control Plane Verification

    by Alan Tang, Ryan Beckett, Steven Benaloh, Karthick Jayaraman, Tejas Patil, Todd Millstein, George Varghese


  • Open Access

    What do LLMs need to Synthesize Correct Router Configurations?

    by Rajdeep Mondal, Alan Tang, Ryan Beckett, Todd Millstein, George Varghese

    We investigate whether Large Language Models (e.g., GPT-4) can synthesize correct router configurations with reduced manual effort. We find GPT-4 works very badly by itself, producing promising draft configurations but with egregious errors in topology, syntax, and semantics. Our strategy, that we call Verified Prompt Programming, is to combine GPT-4 with verifiers, and use localized feedback from the verifier to automatically correct errors. Verification requires a specification and actionable localized feedback to be effective. We show results for two use cases: translating from Cisco to Juniper configurations on a single router, and implementing no-transit policy on multiple routers. While human input is still required, if we define the leverage as the number of automated prompts to the number of human prompts, our experiments show a leverage of 10X for Juniper translation, and 6X for implementing no-transit policy, ending with verified configurations.