FM/SE seminar

Event Type

Seminar/Symposium

Sponsor

PL/FM/SE

Location

0222 Siebel Center and Zoom

Virtual

Date

Oct 18, 2024   2:00 - 3:00 pm  

Speaker

Changshu Liu, UIUC and Nancy Jia, UIUC

Contact

Kristin Irle

E-Mail

kirle@illinois.edu

Phone

217-244-0229

Views

17

Originating Calendar

Siebel School Speakers Calendar

Talk 1 (2-2.30):

Title: Code-Aware Prompting: A Study of Coverage-Guided Test Generation in Regression Setting using LLM

Speaker: Changshu Liu, UIUC

Abstract: Testing plays a pivotal role in ensuring software quality, yet conventional Search Based Software Testing (SBST) methods often struggle with complex software units, achieving suboptimal test coverage. Recent work using large language models (LLMs) for test generation have focused on improving generation quality through optimizing the test generation context and correcting errors in model outputs but use fixed prompting strategies that prompt the model to generate tests without additional guidance. As a result, LLM-generated testsuites still suffer from low coverage. In this work, we present SymPrompt, a code-aware prompting strategy for LLMs in test generation. SymPrompt’s approach is based on recent work that demonstrates LLMs can solve more complex logical problems when prompted to reason about the problem in a multi-step fashion. We apply this methodology to test generation by deconstructing the testsuite generation process into a multi-stage sequence, each of which is driven by a specific prompt aligned with the execution paths of the method under test, and exposing relevant type and dependency focal context to the model. Our approach enables pretrained LLMs to generate more complete test cases without any additional training. We implement SymPrompt using the TreeSitter parsing framework and evaluate on a benchmark challenging methods from open-source Python projects. SymPrompt enhances correct test generations by a factor of 5 and bolsters relative coverage by 26% for CodeGen2. Notably, when applied to GPT-4, SymPrompt improves coverage by over 2× compared to baseline prompting strategies.

Reference: https://arxiv.org/abs/2402.00097

Talk 2 (2.30-3):

Title: Verifying Cake-Cutting, Faster

Speaker: Nancy Jia, UIUC

Abstract: Envy-free cake-cutting protocols procedurally divide an infinitely divisible good among a set of agents so that no agent prefers another’s allocation to their own. These protocols are highly complex and difficult to prove correct. Recently, Bertram, Levinson, and Hsu introduced a language called Slice for describing and verifying cake-cutting protocols. Slice programs can be translated to formulas encoding envy-freeness, which are solved by SMT. While Slice works well on smaller protocols, it has difficulty scaling to more complex cake-cutting protocols. We improve Slice in two ways. First, we show any protocol execution in Slice can be replicated using piecewise uniform valuations. We then reduce Slice’s constraint formulas to formulas within the theory of linear real arithmetic, showing that verifying envy-freeness is efficiently decidable. Second, we design and implement a linear type system which enforces that no two agents receive the same part of the good. We implement our methods and verify a range of challenging examples, including the first nontrivial four-agent protocol.

Reference: https://arxiv.org/abs/2405.14068