TL;DR
This paper introduces IPM2, an algorithm that mines user interaction traces from legacy software to automatically discover usage scenarios, effectively recovering lost functional requirements. This approach is crucial for reengineering and modernizing old systems, especially for web enablement, by providing a clear understanding of how users actually interact with the software.
What Problem Does This Paper Address?
Many organizations rely on legacy software systems that are essential but often lack up-to-date documentation of their functional requirements. Over time, original requirements can become obsolete or lost due to continuous maintenance and evolution, a phenomenon known as "software requirements loss." This poses a significant challenge when these systems need to be reengineered, for example, to be accessible via the web. Traditional reverse engineering methods often focus on analyzing source code, which can be complex, contain "dead" code, and produce models that don't align with functional packages. The authors propose a novel approach: leveraging the actual run-time interactions between users and the legacy system as a source of information to reconstruct these lost requirements in the form of usage scenarios.
Methods
The core contribution is the IPM2 (Interaction-Pattern Miner 2) algorithm. IPM2 tackles the problem of discovering usage scenarios by treating user interaction traces as sequences of screen IDs. The process involves:
- Preprocessing: Interaction traces are first encoded using run-length encoding to handle immediate repetitions of screen IDs, creating a more compact representation (R1).
- Pattern Discovery (Procedure 1): The algorithm identifies initial candidate patterns of length 2. It exhaustively searches the input sequences, considering a user-defined
maxErrorparameter to allow for insertion errors (extra screen IDs) within a pattern instance. A "location list" is maintained for each pattern, recording where it appears in the traces. Patterns with insufficient support (minSupp) are filtered out. - Pattern Extension (Procedure 2): This is the key recursive step. IPM2 extends shorter candidate patterns into longer ones using a depth-first search strategy. It leverages the location lists of existing patterns to efficiently construct location lists for new, extended patterns. This process continues until patterns can no longer be extended while meeting the minimum support threshold. The algorithm is designed to identify "maximal qualified patterns," meaning patterns that are not sub-patterns of other discovered patterns with the same support.
- Location List Construction (Procedure 3): A specialized procedure to merge location lists of two patterns to create the location list for their combined pattern, ensuring that the combined pattern instances are valid within the
maxErrorconstraint.
The algorithm is guided by a user-defined qualification criterion c, a quadruplet consisting of minLen (minimum pattern length), minSupp (minimum support), maxError (maximum allowed insertion errors), and minScore (minimum score for ranking patterns).
Datasets
The paper uses a case study involving the Library of Congress Information System (LOCIS). Four interaction traces were recorded from users performing information retrieval tasks. These traces were used to evaluate the IPM2 algorithm. The paper does not introduce a new benchmark dataset but rather uses a real-world legacy system for its evaluation.
Key Insights and Ideas
- Run-time behavior as a proxy for requirements: The fundamental insight is that how users actually interact with a system (its run-time behavior) is a valuable, albeit noisy, operational specification of its intended functionality. This is particularly useful when formal documentation is missing.
- Handling "noisy" data: The inclusion of
maxErroris crucial. Real user interactions are rarely perfect; users make mistakes, take detours, or use alternative paths. IPM2's ability to tolerate insertion errors makes it robust for real-world data. - Efficiency through location lists: Instead of repeatedly scanning the entire dataset, IPM2 maintains and propagates location lists. This significantly improves efficiency, especially for large datasets, by avoiding redundant computations.
- Maximality is key: The focus on discovering "maximal qualified patterns" ensures that the output is concise and represents distinct user tasks, rather than redundant sub-patterns.
Key Results
The paper demonstrates the effectiveness of IPM2 through a case study on the LOCIS system. After applying IPM2 with a specific criterion c = (minLen=6, minSupp=9, maxError=1, minScore=7), the algorithm discovered 12 qualified patterns. These patterns were further analyzed and compacted. The authors identified four key patterns that closely corresponded to three distinct user tasks, each with alternative paths. These patterns were then manually augmented with semantic information to describe the corresponding usage scenarios, showcasing the algorithm's utility in recovering functional requirements.
Limitations and Future Work
- Manual Augmentation: While IPM2 discovers the structure of usage scenarios (the sequence of screen interactions), it requires manual effort to add semantic information (e.g., what data is exchanged, what the user inputs mean).
- Criterion
cTuning: The effectiveness of the discovered patterns is dependent on the user-defined criterionc. Finding the optimal parameters might require experimentation. - Scalability for Extremely Large Alphabets: While IPM2 is designed to be more scalable than its predecessor (IPM) for systems with many screens, the paper notes that it can generate more candidate patterns.
- Future Work: The authors plan to evaluate IPM2 further with larger artificial and real datasets covering a wider range of applications and interaction styles. They also aim to compare its effectiveness and efficiency against other related algorithms. A key future direction is to automate the semantic augmentation of discovered patterns.
Summary updated