LLM-based Satisfiability Checking of String Requirements by Consistent Data and Checker GenerationShow others and affiliations
2025 (English)In: 2025 IEEE 33rd International Requirements Engineering Conference (RE), IEEE Computer Society, 2025, p. 231-243Conference paper, Published paper (Refereed)
Abstract [en]
Requirements over strings, commonly represented using natural language (NL), are particularly relevant for software systems due to their heavy reliance on string data manipulation. While individual requirements can usually be analyzed manually, verifying properties (e.g., satisfiability) over sets of NL requirements is particularly challenging. Formal approaches (e.g., SMT solvers) may efficiently verify such properties, but are known to have theoretical limitations. Additionally, the translation of NL requirements into formal constraints typically requires significant manual effort. Recently, large language models (LLMs) have emerged as an alternative approach for formal reasoning tasks, but their effectiveness in verifying requirements over strings is less studied. In this paper, we introduce a hybrid approach that verifies the satisfiability of NL requirements over strings by using LLMs (1) to derive a satisfiability outcome (and a consistent string, if possible), and (2) to generate declarative (i.e., SMT) and imperative (i.e., Python) checkers, used to validate the correctness of (1). In our experiments, we assess the performance of four LLMs. Results show that LLMs effectively translate natural language into checkers, even achieving perfect testing accuracy for Python-based checkers. These checkers substantially help LLMs in generating a consistent string and accurately identifying unsatisfiable requirements, leading to more than doubled generation success rate and F1-score in certain cases compared to baselines without generated checkers.
Place, publisher, year, edition, pages
IEEE Computer Society, 2025. p. 231-243
National Category
Computer Sciences Formal Methods Computer Systems
Identifiers
URN: urn:nbn:se:liu:diva-218877DOI: 10.1109/RE63999.2025.00030ISI: 001733909100022Scopus ID: 2-s2.0-105020011394ISBN: 9798331524135 (electronic)ISBN: 9798331524142 (print)OAI: oai:DiVA.org:liu-218877DiVA, id: diva2:2007011
Conference
IEEE 33rd International Requirements Engineering Conference (RE), Valencia, Spain, 01-05 September, 2025
Note
Funding: FRQNT-B2X project [319955, IT30340]; Wallenberg AI, Autonomous Systems and Software Program (WASP), Sweden
2025-10-162025-10-162026-08-12