A Knowledge-Based Software Information System

Premkumar T. Devanbu, Peter G. Selfridge, Bruce W. Ballard, Ronald J. BrachmanIJCAI 1989

Maintaining a million-line codebase is often more akin to archaeology than engineering. When developers need to modify a massive, evolving system, they spend the vast majority of their time simply trying to understand how existing components interact. Researchers at AT&T Bell Labs identified this as the "Discovery Problem."

In their seminal paper, Devanbu et al. present LaSSIE (a Knowledge-Based Software Information System), an intelligent guide designed to help programmers navigate the complexities of large-scale software.

The Discovery Problem in Mega-Systems

The authors used the AT&T System 75—a PBX switch comprising over one million lines of C code—as their primary case study. They argued that traditional tools are insufficient for such "mega-systems":

  • Keyword searches (e.g., grep) lack semantic context and are too "bottom-up."
  • Cross-reference tools map function calls but fail to explain the high-level features (like "Call Forwarding") those functions implement.

As tribal knowledge vanishes with departing employees, LaSSIE aims to codify architectural intent so the system can explain itself to new developers.

Methods and Knowledge Representation

LaSSIE operates on a "formulate-retrieve-reformulate" cycle, integrating functional, architectural, and code-level data into a single searchable framework.

1. Domain Taxonomy (KANDOR)

The core of LaSSIE is a frame-based taxonomy built using the KANDOR representation language. It categorizes the software world into four primary types: Actions, Objects, Doers, and States.

The LaSSIE domain taxonomy, showing the hierarchical relationship between Actions, Objects, Doers, and States.

This hierarchy uses "subsumption" logic to automatically organize concepts. For instance, if a user searches for a "trunk" but finds no direct matches, the system can suggest broader "resource-objects," helping the user narrow down their search.

2. Frame-Based Logic

To represent complex operations, LaSSIE uses "verbframes." These frames define the relationships between different entities in the system, such as which "Doer" performs an "Action" on a specific "Object."

A verbframe representation of a connection action, illustrating how LaSSIE maps actors, recipients, and operands.

3. Multi-View Integration and Automated Ingestion

LaSSIE links four distinct "views":

  • Functional: High-level system actions (e.g., "Connect a user").
  • Architectural: Hardware and software layers.
  • Feature: Mapping functions to user-facing capabilities (e.g., "Hold").
  • Code: The underlying C files, functions, and macros.

To handle the scale of a million-line system, LaSSIE uses CScope to automatically extract relationships between C objects, populating the "Code View" without manual data entry.

Key Insights and Results

The researchers evaluated LaSSIE against real-world developer queries. The system successfully handled complex requests such as "How do I allocate an international toll trunk?" and "What C functions enable Call Forwarding?" by providing precise pointers to relevant code and hardware components.

A key insight from the study is that LaSSIE prevents "architectural rot." In large systems, developers often write redundant code because they cannot find existing primitives. LaSSIE makes these primitives discoverable. Furthermore, the natural language interface (TELI) allows users to see the formal logic generated by their queries, effectively teaching them the system's underlying architecture as they use it.

Limitations

While code extraction was automated, high-level functional and architectural views still required manual expert annotation. Additionally, the system struggled with extremely fine-grained dynamic behaviors, such as the specific contents of messages passed between processes, due to the complexity of representing such detail in a decidable knowledge base.

Summary updated

BibTeX
@inproceedings{devanbu1989knowledge,
  author = {Premkumar T. Devanbu and Peter G. Selfridge and Bruce W. Ballard and Ronald J. Brachman},
  title = {{A Knowledge-Based Software Information System}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1989},
}
Figure