Inferring state-based behavior models

ABSTRACT

Dynamic analysis helps to extract important information about software systems useful in testing, debugging and maintenance activities. Popular dynamic analysis techniques synthesize either information on the values of the variables or information on relations between invocation of methods. Thus, these approaches do not capture the important relations that exist between data values and invocation sequences.In this paper, we introduce a technique, called GK-tail, for generating models that represent the interplay between program variables and method invocations. GK-tail extends the k-tail algorithm for extracting finite state automata from execution traces, to the case of finite state automata with parameters.The paper presents the technique and the results of some preliminary experiments that indicate the potentialities of the proposed approach.

REFERENCES

• 1: Amazon. Amazon web services. www.amazon.com/gp/aws/landing, 2006.
• 2: Glenn Ammons , Rastislav Bodík , James R. Larus, Mining specifications, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.4-16, January 16-18, 2002, Portland, Oregon
• 3: A. Biermann and J. Feldman. On the synthesis of finite state machines from samples of their behavior. IEEE Transactions on Computer, 21:592--597, June 1972.
• 4: Jonathan E. Cook , Alexander L. Wolf, Discovering models of software processes from event-based data, ACM Transactions on Software Engineering and Methodology (TOSEM), v.7 n.3, p.215-249, July 1998 [doi>10.1145/287000.287001]
• 5: Pierre Dupont, Incremental regular inference, Proceedings of the 3rd International Colloquium on Grammatical Inference: Learning Syntax from Sentences, p.222-237, September 25-27, 1996
• 6: Michael D. Ernst , Jake Cockrell , William G. Griswold , David Notkin, Dynamically Discovering Likely Program Invariants to Support Program Evolution, IEEE Transactions on Software Engineering, v.27 n.2, p.99-123, February 2001 [doi>10.1109/32.908957]
• 7: Susumu Fujiwara , Gregor von Bochmann , Ferhat Khendek , Mokhtar Amalou , Abderrazak Ghedamsi, Test Selection Based on Finite State Models, IEEE Transactions on Software Engineering, v.17 n.6, p.591-603, June 1991 [doi>10.1109/32.87284]
• 8: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 9: A. Hamou-Lhadj and T. C. Lethbridge. An efficient algorithm for detecting patterns in traces of procedure calls. In proceedings of the ICSE Workshop on Dynamic Analysis (WODA), Portland, Oregon, May 2003. ACM Press.
• 10: Michael Harder , Jeff Mellen , Michael D. Ernst, Improving test suites via operational abstraction, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
• 11: Behavior Capture and Test: Automated Analysis of Component Integration, Proceedings of the 10th IEEE International Conference on Engineering of Complex Computer Systems (ICECCS'05), p.292-301, June 16-20, 2005 [doi>10.1109/ICECCS.2005.25]
• 12: Rajesh Parekh , Vasant G. Honavar, An incremental interactive algorithm for grammar inference, Proceedings of the 3rd International Colloquium on Grammatical Inference: Learning Syntax from Sentences, p.238-249, September 25-27, 1996
• 13: Sara Porat , Jerome A. Feldman, Learning Automata from Ordered Examples, Machine Learning, v.7 n.2-3, p.109-138, Sept. 1991 [doi>10.1007/BF00114841]
• 14: Steven P. Reiss , Manos Renieris, Encoding program executions, Proceedings of the 23rd International Conference on Software Engineering, p.221-230, May 12-19, 2001, Toronto, Ontario, Canada
• 15: L. Wendehals. Improving design pattern instance recognition by dynamic analysis. In proceedings of the ICSE Workshop on Dynamic Analysis (WODA), Portland, USA, May 2003. ACM Press.
• 16: T. Xie and D. Notkin. Exploiting synergy between testing and inferred partial specifications. In proceedings of the ICSE Workshop on Dynamic Analysis (WODA), Portland, Oregon, May 2003. ACM Press.
• 17: Tao Xie , David Notkin, Tool-assisted unit-test generation and selection based on operational abstractions, Automated Software Engineering, v.13 n.3, p.345-371, July 2006 [doi>10.1007/s10851-006-8530-6]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Formal methods
      D.2.5 Testing and Debugging
          Subjects: Debugging aids; Tracing
      D.2.8 Metrics
          Subjects: Complexity measures; Performance measures

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.3 Software Management
          Subjects: Software maintenance

General Terms:
Algorithms, Verification

Keywords:
behavioral models, dynamic analysis, finite-state machines, inference algorithms, verification