Abstract
Maintaining large-scale legacy software is a significant challenge, with developers often spending more than half their time understanding existing code. This paper presents an approach to automatically recover high-level Datalog specifications from low-level C implementations in database systems. By leveraging Inductive Logic Programming (ILP) and domain-specific biases, the authors demonstrate a system capable of reconstructing specifications for nearly two-thirds of a real-world database subsystem with perfect recall.
Introduction
The "specification recovery problem" involves generating a concise, human-readable logical description of a software component's behavior based on its implementation and execution examples. In database systems, high-level virtual relations (views) are often implemented as thousands of lines of complex C code. Manually reverse-engineering these is labor-intensive and error-prone. This research aims to bridge the gap between low-level implementation and high-level intent using automated learning techniques.
Methodology
The authors utilize Grendel2, an ILP algorithm enhanced with Augmented Antecedent Description Grammars (ADGs). Unlike standard ILP methods like FOIL, which struggle with the high arity of database relations, ADGs allow for the encoding of domain-specific constraints. This "bias" guides the learner toward valid database access patterns, making the search space tractable.
To handle data transformations (e.g., formatting changes or string conversions), the system uses "determinations"—logical assertions that one variable's value is functionally derived from another. This allows the specification to remain abstract, identifying that a transformation occurs without needing to synthesize the exact C logic for the conversion.
Key Insights and Challenges
A critical challenge in specification recovery is logical ambiguity. Multiple hypotheses may be consistent with the observed input/output behavior of the code. To address this, the system outputs a factored form representing all consistent hypotheses, ensuring 100% recall (the true specification is always included in the result set).
Interestingly, the study found that code complexity (measured in lines of C) does not necessarily correlate with learning complexity. A 2,000-line routine might be logically simpler than a 200-line one. By encoding just 11 rewrite rules about database view operations, the authors significantly improved the system's performance over off-the-shelf machine learning algorithms.
Experimental Results
The system was evaluated on the "Recent Change" (RC) subsystem of the 5ESS switching system, a massive telecommunications platform containing over one million lines of C code. The benchmark included 19 complex views with implementations averaging 747 lines of code.
The final Grendel2/MD system demonstrated substantial improvements:
- Scope: Successfully handled 63.1% of benchmark modules.
- Recall: Achieved 100% recall for modules within its scope.
- Precision: Maintained an overall precision of 61%, reaching 82.2% for simpler modules.
- Conciseness: The recovered Datalog specs were typically only a few lines long, replacing hundreds or thousands of lines of legacy C code.
Conclusion
By combining ILP with domain-specific grammars, this research demonstrates the feasibility of automated specification recovery in massive legacy systems. While challenges remain in handling multi-clause join views and improving precision as scope increases, the ability to generate concise, human-readable specifications offers a powerful tool for software maintenance and evolution.
Summary updated