Ryosuke Sato

Naoki Kobayashi, Ryosuke Sato, Ayumi Shinohara et al.

Despite the recent progress of automated program verification techniques, fully automated verification of programs manipulating recursive data structures remains a challenge. We introduce solvable tuple patterns (STPs) and conjunctive STPs (CSTPs), novel formalisms for expressing and inferring invariants between list-like recursive data structures. A distinguishing feature of STPs is that they can be efficiently inferred from only a small number of positive samples; no negative samples are required. After presenting properties and inference algorithms of STPs and CSTPs, we show how to incorporate the CSTP inference into a CHC (Constrained Horn Clauses) solver supporting list-like data structures, which serves as a uniform backend for automated program verification tools. A CHC solver incorporating the (C)STP inference has won the ADT-LIN category of CHC-COMP 2025 by a significant margin.

Taihei Oki, Ryosuke Sato

We develop a unified ascending-auction framework for computing Walrasian equilibria in combinatorial markets with strong substitutes valuations and piecewise-linear payment functions. Our auction extends the celebrated ascending auctions of Gul and Stacchetti (2000) and Ausubel (2006) to accommodate payment frictions (e.g., transaction taxes or commission fees). This is achieved by incorporating directional price updates that reflect heterogeneous payment structures. Our framework also generalizes the unit-demand imperfectly transferable utility models of Alkan (1989, 1992) to a fully combinatorial setting, thereby unifying these paradigms. Furthermore, this is the first study to compute the minimum -- also known as the buyer-optimal -- equilibrium in combinatorial markets with such frictions. Our analysis builds upon discrete convex analysis. Our main technical contribution is a characterization of valid price-update directions, together with a strongly polynomial-time algorithm for computing them. Notably, the algorithm uses only demand-oracle queries and never requires handling information of exponential size. To compute such a direction, we formulate a lexicographic extension of the polymatroid sum problem and characterize its dual solution via a reduction to a convex flow problem. Exploiting the $\text{L}^\natural$-convexity of the dual objective, we show that the desired direction can be constructed from the minimal dual solution. This convexity also yields transparent economic and potential-based interpretations of the auction dynamics, strengthening the connection between ascending auctions and discrete optimization.

Daito Nakano, Mingyang Yin, Ryosuke Sato et al.

Software is prone to bugs and failures. Security bugs are those that expose or share privileged information and access in violation of the software's requirements. Given the seriousness of security bugs, there are centralized mechanisms for supporting and tracking these bugs across multiple products, one such mechanism is the Common Vulnerabilities and Exposures (CVE) ID description. When a bug gets a CVE, it is referenced by its CVE ID. Thus we explore thousands of Free/Libre Open Source Software (FLOSS) projects, on Github, to determine if developers reference or discuss CVEs in their code, commits, and issues. CVEs will often refer to 3rd party software dependencies of a project and thus the bug will not be in the actual product itself. We study how many of these references are intentional CVE references, and how many are relevant bugs within the projects themselves. We investigate how the bugs that reference CVEs are fixed and how long it takes to fix these bugs. The results of our manual classification for 250 bug reports show that 88 (35%), 32 (13%), and 130 (52%) are classified into "Version Update", "Fixing Code", and "Discussion". To understand how long it takes to fix those bugs, we compare two periods, Reporting Period, a period between the disclosure date of vulnerability information in CVE repositories and the creation date of the bug report in a project, and Fixing Period, a period between the creation date of the bug report and the fixing date of the bug report. We find that 44% of bug reports that are classified into "Version Update" or "Fixing Code" have longer Reporting Period than Fixing Period. This suggests that those who submit CVEs should notify affected projects more directly.