Madhusudan Parthasarathy

About

Madhusudan Parthasarathy is a professor at the Siebel School of Computing and Data Science at the University of Illinois Urbana-Champaign. He earned his Ph.D. in Theoretical Computer Science from the Institute of Mathematical Sciences, University of Madras, Chennai, India, in 2002. His research has significantly impacted the field of formal language theory, particularly through the definition of visibly pushdown languages, a formal language class that has influenced academia and practical applications such as XML processing, program verification, and programming languages. His research interests include reasoning with heaps in software verification, software verification, reliable and secure software engineering, security, program synthesis, and logic and automata theory.

Selected publications

• Perception Contracts for Safety of ML-Enabled Systems

  Proceedings of the ACM on Programming Languages · 2023-10-16 · 15 citations

  articleOpen access

  We introduce a novel notion of perception contracts to reason about the safety of controllers that interact with an environment using neural perception. Perception contracts capture errors in ground-truth estimations that preserve invariants when systems act upon them. We develop a theory of perception contracts and design symbolic learning algorithms for synthesizing them from a finite set of images. We implement our algorithms and evaluate synthesized perception contracts for two realistic vis…

  PublisherOA PDFDOI

• Model-guided synthesis of inductive lemmas for FOL with least fixpoints

  Proceedings of the ACM on Programming Languages · 2022-10-31 · 11 citations

  articleOpen accessSenior author

  Recursively defined linked data structures embedded in a pointer-based heap and their properties are naturally expressed in pure first-order logic with least fixpoint definitions (FO+lfp) with background theories. Such logics, unlike pure first-order logic, do not admit even complete procedures. In this paper, we undertake a novel approach for synthesizing inductive hypotheses to prove validity in this logic. The idea is to utilize several kinds of finite first-order models as counterexamples th…

  PublisherOA PDFDOI

• Synthesizing contracts correct modulo a test generator

  Proceedings of the ACM on Programming Languages · 2021-10-15 · 11 citations

  articleOpen access

  We present an approach to learn contracts for object-oriented programs where guarantees of correctness of the contracts are made with respect to a test generator. Our contract synthesis approach is based on a novel notion of tight contracts and an online learning algorithm that works in tandem with a test generator to synthesize tight contracts. We implement our approach in a tool called Precis and evaluate it on a suite of programs written in C#, studying the safety and strength of the synthesi…

  PublisherOA PDFDOI

• ConjunCT: Learning Inductive Invariants to Prove Unbounded Instruction Safety Against Microarchitectural Timing Attacks

  2024-05-19 · 7 citations

  article

  The past decade has seen a deluge of microarchitectural side channels stemming from a variety of hardware structures (the cache, branch predictor, execution ports, the TLB, speculation, etc). These attacks stem from software that passes sensitive data to so-called unsafe or transmitter instructions, i.e., those whose execution time depends on their operands’ values. Correspondingly, there has been a large number of defenses (spanning hardware and software) that attempt to enforce the policy: sen…

  PublisherDOI

• A Learning-Based Approach to Synthesizing Invariants for Incomplete Verification Engines

  Journal of Automated Reasoning · 2020-07-13 · 6 citations

  articleOpen access

  Abstract We propose a framework for synthesizing inductive invariants for incomplete verification engines, which soundly reduce logical problems in undecidable theories to decidable theories. Our framework is based on the counterexample guided inductive synthesis principle and allows verification engines to communicate non-provability information to guide invariant synthesis. We show precisely how the verification engine can compute such non-provability information and how to build effective lea…

  PublisherOA PDFDOI

Awards & honors

• ACM Europe Council Best Paper Award at PLDI '24

Similar researchers at University of Illinois Urbana-Champaign

• Jiawei Hanh-146
• Kaiyu Guanh-86
• ChengXiang Zhaih-83