Article

SMArTIC: towards building an accurate, robust and scalable specification miner

Authors:

Siau-Cheng KhooAuthors Info & Claims

SIGSOFT '06/FSE-14: Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering

Pages 265 - 275

https://doi.org/10.1145/1181775.1181808

Published: 05 November 2006 Publication History

Abstract

Improper management of software evolution, compounded by imprecise, and changing requirements, along with the "short time to market" requirement, commonly leads to a lack of up-to-date specifications. This can result in software that is characterized by bugs, anomalies and even security threats. Software specification mining is a new technique to address this concern by inferring specifications automatically. In this paper, we propose a novel API specification mining architecture called SMArTIC Specification Mining Architecture with Trace fIltering and Clustering) to improve the accuracy, robustness and scalability of specification miners. This architecture is constructed based on two hypotheses: (1) Erroneous traces should be pruned from the input traces to a miner, and (2) Clustering related traces will localize inaccuracies and reduce over-generalizationin learning. Correspondingly, SMArTIC comprises four components: an erroneous-trace filtering block, a related-trace clustering block, a learner, and a merger. We show through experiments that the quality of specification mining can be significantly improved using SMArTIC.

References

[1]

G. Ammons, R. Bodik, and J. R. Larus. Mining specification. In Proc. of Principles of Programming Languages, 2002.

Digital Library

[2]

G. Ammons, D. Mandelin, R. Bodik, and J.R. Larus. Debugging temporal specifications with concept analysis. In Proc. of Programming Language Design and Implementation, 2003.

Digital Library

[3]

T. Arts and L. Fredlund. Trace analysis of Erlang program. In Proc. of Erlang Workshop, 2002.

Digital Library

[4]

A.W. Biermann and J.A. Feldman. On the synthesis of finite-state machines from samples of their behaviour. IEEE Transactions on Computers, 21:591--597, 1972.

[5]

R. Capilla and J.C. Dueñas. Light-weight product-lines for evolution and maintenance of web sites. In Proc. of European Conf. On Software Maintenance And Reengineering, 2003.

Digital Library

[6]

J. E. Cook and A. L. Wolf. Discovering models of software processes from event-based data. ACM Transactions on Software Engineering and Methodology, 7(3):215--249, July 1998.

Digital Library

[7]

T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2001.

Digital Library

[8]

S. Deelstra, M. Sinnema, and J. Bosch. Experiences in software product families: Problems and issues during product derivation. In Proc. of Software Product Line Conf., 2004.

[9]

D.Lo and S-C.Khoo. QUARK: Empirical assessment of automaton-based specification miners. In Proc. of Working Conf. on Reverse Engineering, 2006.

Digital Library

[10]

M. Dwyer, G. Avrunin, and J. Corbett. Patterns in property specifications for finite-state verification. In Proc. of Int. Conf. on Software Engineering, 1999.

Digital Library

[11]

M. El-Ramly, E. Stroulia, and P. Sorenson. Interaction-pattern mining: Extracting usage scenarios from run-time behavior traces. In Proc. of ACM-SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, 2002.

Digital Library

[12]

M.D. Ernst, J. Cockrell, W.G. Griswold, and D. Notkin. Dynamically discovering likely program invariants to support program evolution. IEEE Transaction on Software Engineering, 27(2):99--123, February 2001.

Digital Library

[13]

A. Foss and O.R. Zaiane. A parameterless method for efficiently discovering clusters of arbitrary shape in large datasets. In Proc. IEEE Int. Conf. on Data Mining, 2002.

Digital Library

[14]

A. Fox. Addressing software dependability with statistical and machine learning techniques. In Proc. of Int. Conf. of Software Engineering, 2005. Invited Talk.

Digital Library

[15]

N. Gupta. Generating test data for dynamically discovering likely program invariants. In Proc. of the workshop on dynamic analysis, 2003.

[16]

J. Han and M. Kamber. Data Mining Concepts and Techniques. Morgan Kaufmann, 2001.

Digital Library

[17]

M. Huth and M. Ryan. Logic in Computer Science. Cambridge, 2004.

[18]

The Java hotspot performance engine architecture. http://java.sun.com/products/hotspot/whitepaper.html.

[19]

J. Henkel and A. Diwan. Discovering algebraic specifications from java classes. In Proc. of the Euro. Conf. of Object Oriented Programming, 2003.

[20]

JRat. http://jrat.sourceforge.net/.

[21]

L. Kaufman and P.J. Rousseeuw. Finding Groups in Data: an Introduction to Cluster Analysis. John Wiley & Sons, 1990.

[22]

E. Keogh, S. Lonardi, and C.A. Ratanamahatana. Towards parameter-free data mining. Proc. of Int. Conf. on Knowledge Discovery and Data Mining, 2004.

Digital Library

[23]

J.R. Larus. Whole program paths. In Proc. of Programming Language Design and Implementation, 1999.

Digital Library

[24]

A.M. Law and W. D. Kelton. Simulation modelling and analysis. McGraw-Hill, 2000.

Digital Library

[25]

D. Lo and S-C. Khoo. SMArTIC: Specification mining architecture with trace filtering and clustering. In SoC-NUS tech. report, TRA 8/06, 2006.

[26]

R.B. Lyngsø, C.N.S. Pedersen, and H. Nielsen. Metrics and similarity measures for hidden Markov models. In Proc. of National Conf. on Artificial Intelligence, 1999.

Digital Library

[27]

D.S. Moore and G.P. McCabe. Introduction to the Practice of Statistics. W.H. Freeman & Co., Third Edition, 1998.

Digital Library

[28]

Jakarta Commons Net. http://jakarta.apache.org/commons/net/.

[29]

C.G. Nevill-Manning, I.H. Witten, and D.L. Maulsby. Compression by induction of hierarchical grammars. In Proc. of Data Compression Conf., 1994.

[30]

J. W. Nimmer and M. D. Ernst. Automatic generation of program specifications. In Proc. of Int. Symposium on Software Testing and Analysis, 2002.

Digital Library

[31]

S.C. Ntafos. A comparison of some structural testing strategies. IEEE Transactions on Software Enginering, 14(6):868--874, 1988.

Digital Library

[32]

A. V. Raman and J. D. Patrick. The sk-strings method for inferring PFSA. In Proc. of the workshop on automata induction, grammatical inference and language acquisition, 1997.

[33]

O. Raz, P. Koopman, and M. Shaw. Semantic anomaly detection in online data sources. In Proc. of Int. Conf. on Software Engineering, 2002.

Digital Library

[34]

S. P. Reiss and M. Renieris. Encoding program executions. In Proc. of the Int. Conf. on Software Engineering, 2001.

Digital Library

[35]

S. P. Reiss and M. Renieris. Generating java trace data. In Proc. of the ACM Conf. on Java Grande, 2000.

Digital Library

[36]

M. Tompa. Lecture notes on biological sequence analysis. Technical Report 2000-06-01 University of Washington, 2000.

[37]

C. J. van Rijsbergen. Information Retrieval. Butterworths, London, 1979.

Digital Library

[38]

J. Wang and J. Han. BIDE: Efficient mining of frequent closed sequences. In Proc. of Int. Conf. on Data Engineering, 2004.

Digital Library

[39]

J. Whaley, M. C. Martin, and M. S. Lam. Automatic extraction of object oriented component interfaces. In Proc. of the Int. Symposium on Software Testing and Analysis, 2002.

Digital Library

[40]

W. Weimer and G. Necula. Mining temporal specifications for error detection. In Proc. of Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems, 2005.

Digital Library

[41]

J. Yang, D. Evans, D. Bhardwaj, T. Bhat, and M. Das. Perracotta: Mining temporal API rules from imperfect traces. In Proc. of Int. Conf. on Software Engineering, 2006.

Digital Library

Cited By

Fan YWang M(2024)Specification Mining Based on the Ordering Points to Identify the Clustering Structure Clustering Algorithm and Model CheckingAlgorithms10.3390/a1701002817:1(28)Online publication date: 10-Jan-2024
https://doi.org/10.3390/a17010028
Clun DShin DFilieri ABianculli D(2024)Rigorous Assessment of Model Inference Accuracy using Language CardinalityACM Transactions on Software Engineering and Methodology10.1145/364033233:4(1-39)Online publication date: 16-Jan-2024
https://dl.acm.org/doi/10.1145/3640332
Lo D(2024)Requirements Engineering for Trustworthy Human-AI Synergy in Software Engineering 2.02024 IEEE 32nd International Requirements Engineering Conference (RE)10.1109/RE59067.2024.00011(3-4)Online publication date: 24-Jun-2024
https://doi.org/10.1109/RE59067.2024.00011
Show More Cited By

Index Terms

SMArTIC: towards building an accurate, robust and scalable specification miner
1. Software and its engineering
  1. Software creation and management
    1. Designing software
      1. Requirements analysis
  2. Software notations and tools
    1. Context specific languages

Recommendations

Discovering complete API rules with mutation testing
MSR '12: Proceedings of the 9th IEEE Working Conference on Mining Software Repositories

Specifications are important for many activities during software construction and maintenance process such as testing, verification, debugging and repairing. Despite their importance, specifications are often missing, informal or incomplete because they ...
Extracting significant specifications from mining through mutation testing
ICFEM'11: Proceedings of the 13th international conference on Formal methods and software engineering

Specification mining techniques are used to automatically infer interaction specifications among objects in the format of call sequences, but many of these specifications can be meaningless or insignificant. As a consequence, when used in program ...
Javert: fully automatic mining of general temporal properties from dynamic traces
SIGSOFT '08/FSE-16: Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of software engineering

Program specifications are important for many tasks during software design, development, and maintenance. Among these, temporal specifications are particularly useful. They express formal correctness requirements of an application's ordering of specific ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGSOFT '06/FSE-14: Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering

November 2006

298 pages

ISBN:1595934685

DOI:10.1145/1181775

General Chair:
Michal Young
University of Oregon
,
Program Chair:
Premkumar Devanbu
University of California, Davis

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGSOFT06/FSE-14

Sponsor:

SIGSOFT06/FSE-14: SIGSOFT 2006 -14th International Symposium on the Foundations of Software Engineering

November 5 - 11, 2006

Oregon, Portland, USA

Acceptance Rates

Overall Acceptance Rate 17 of 128 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

120
Total Citations
View Citations
585
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)3

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Fan YWang M(2024)Specification Mining Based on the Ordering Points to Identify the Clustering Structure Clustering Algorithm and Model CheckingAlgorithms10.3390/a1701002817:1(28)Online publication date: 10-Jan-2024
https://doi.org/10.3390/a17010028
Clun DShin DFilieri ABianculli D(2024)Rigorous Assessment of Model Inference Accuracy using Language CardinalityACM Transactions on Software Engineering and Methodology10.1145/364033233:4(1-39)Online publication date: 16-Jan-2024
https://dl.acm.org/doi/10.1145/3640332
Lo D(2024)Requirements Engineering for Trustworthy Human-AI Synergy in Software Engineering 2.02024 IEEE 32nd International Requirements Engineering Conference (RE)10.1109/RE59067.2024.00011(3-4)Online publication date: 24-Jun-2024
https://doi.org/10.1109/RE59067.2024.00011
Lo D(2023)Trustworthy and Synergistic Artificial Intelligence for Software Engineering: Vision and Roadmaps2023 IEEE/ACM International Conference on Software Engineering: Future of Software Engineering (ICSE-FoSE)10.1109/ICSE-FoSE59343.2023.00010(69-85)Online publication date: 14-May-2023
https://doi.org/10.1109/ICSE-FoSE59343.2023.00010
Peng BLiang PHan TLuo WDu JWan HYe RZheng YBissyandé TKlein JBird CSarro F(2023)PURLTL: Mining LTL Specification from Imperfect Traces in TestingProceedings of the 38th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE56229.2023.00202(1766-1770)Online publication date: 11-Nov-2023
https://dl.acm.org/doi/10.1109/ASE56229.2023.00202
Zhong HWang X(2023)An empirical study on API usages from code search engine and local libraryEmpirical Software Engineering10.1007/s10664-023-10304-z28:3Online publication date: 13-Apr-2023
https://dl.acm.org/doi/10.1007/s10664-023-10304-z
Nguyen HPhan HKhairunnesa SNguyen SYadavally AWang SRajan HNguyen T(2022)A Hybrid Approach for Inference between Behavioral Exception API Documentation and Implementations, and Its ApplicationsProceedings of the 37th IEEE/ACM International Conference on Automated Software Engineering10.1145/3551349.3560434(1-13)Online publication date: 10-Oct-2022
https://dl.acm.org/doi/10.1145/3551349.3560434
Blasi AGorla AErnst MPezzè M(2022)Call Me Maybe: Using NLP to Automatically Generate Unit Test Cases Respecting Temporal ConstraintsProceedings of the 37th IEEE/ACM International Conference on Automated Software Engineering10.1145/3551349.3556961(1-11)Online publication date: 10-Oct-2022
https://dl.acm.org/doi/10.1145/3551349.3556961
Mahadewa KWang KBai GShi LLiu YDong JLiang Z(2021)Scrutinizing Implementations of Smart Home IntegrationsIEEE Transactions on Software Engineering10.1109/TSE.2019.296069047:12(2667-2683)Online publication date: 1-Dec-2021
https://doi.org/10.1109/TSE.2019.2960690
Afzal AMotwani MStolee KBrun YLe Goues C(2021)SOSRepair: Expressive Semantic Search for Real-World Program RepairIEEE Transactions on Software Engineering10.1109/TSE.2019.294491447:10(2162-2181)Online publication date: 1-Oct-2021
https://doi.org/10.1109/TSE.2019.2944914
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten